对“RSA公开密钥密码体制”的粗浅学习
2019年8月11日星期日
关于什么是“RSA公开密钥密码体制”，我不敢狗尾续貂，自大赘述，以下简介引用自百度百科，详情用户可自行搜索、研读。
“RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中，RSA被广泛使用。RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。”
我对“密码学”中如何实现信息的加密传输充满好奇，抽空看了看相关文章。光阴蹉跎，天分有限，囫囵吞枣，了解了一些大概。本文至少算是一点整理笔记和备份，但同时也希望能做出一点点小科普，激发出更多的兴趣和好奇。
RSA主要是做什么的？
信息传递过程中的“明文”（或者就叫“人话”吧）是被一把“密钥”加密成“密文”的。这把“密钥”多数情况下是一串很长的由二进制字符0、1组成的“伪随机字符串”，形如：110100001000101101111110101110001100111011000001111001001010100。所以说是“伪随机”，是因为这个字符串不是由“掷硬币”生成的纯随机字符串（比如：正面向上取0，背面向上取1），而是根据给定的“初值序列”和“系数序列”，按通常“公开”的算法生成的，它只是很好地拟合了“纯随机字符串”的特点，尤其当长度很长时，比如说1000位。既然“生成算法”是公开的，在有利于指定信息接收者“自我生成”同样的密钥，将密文还原为明文的同时，也面临着“密钥”被截获、窃取的极大可能。这里的“被截获、窃取”其实具指生成密钥的初始条件：“初值序列”和“系数序列”。当采用“线下方式”或其他方式将“密钥生成条件”隐秘地传递给信息接收者时，倒不如直接将“明文”传递过去，不必多此一举，不过，这样的话，也就没有所谓“信息化”了。
RSA巧妙、完美地解决了“密钥”传递的问题。通常密文如同一把锁，锁里的信息是明文，即便这把“锁”被信息接收者拿到了手中，如果没有“钥匙”的话也是不能被打开的。当传递密钥的过程等价于传递一把打开的锁（明文）时，这种努力是没有价值的。
RSA大致的思路是这样的：
1.将“拟完美序列”（或叫“伪随机序列”，本文特指用以加密明文的“密钥”，也即上文谈到的“二进制字符串”）转换成十进制数，得到一个很大、很大、很大的整数，这个转换后的整数就记作x吧，方便下文叙述。
2.一般的RSA中，信息接收者B会生成一对密钥（a，b），a公开，叫公钥；b隐秘，叫私钥。信息发送者A使用信息接收者B提供的公钥a对x加密发送，只有私钥b可以解密，别人截获是徒劳的。
俗语说：“一把钥匙开一把锁”，RSA打破了这个固有观念，一把锁配两把钥匙，一把a只能将锁锁闭，不能自我打开，另一把b只能将由a锁闭的锁打开，用b锁闭时，也只有a才能打开。可见，创新点在于：将钥匙“打开”和“锁闭”的功能分开在两把钥匙上了。
信息接收者B“事先制作”两把钥匙，公开一把a，供信息发送者A将信息x上锁，然后将加锁的x堂而皇之地传递于网路中，飘散在电磁波中，哪怕被别人截获、窃取，也不用担心，因为他们在“有生之年”或者可遇见的时间、计算资源之内，是无法破解得到另一把钥匙b的。有幸破解了，估计也早都过了“信息时效”，毫无价值了。
但是，这个信息传递的过程——“一般的RSA”——面临被第三者冒用的风险，图示如下：
Alice：信息发送者（或信息接收者）
Bob：信息接收者（或信息发送者）
Eve：窃听者
Eve会这样做：准备两套密钥（a1，b1）、（a2，b2）；将公钥a1发送给Alice，让Alice以为是Bob发来的；将公钥a2发送给Bob，让Bob以为是Alice发来的；拦截Alice用公钥a1加密的信息，用私钥b1解密，查看信息，再用公钥a2加密转发给Bob；拦截Bob用公钥a2加密的信息，用私钥b2解密，查看信息，再用公钥a1加密转发给Alice。
这不得不说是一个重大的漏洞：原本的信息发送、接收双方，有可能始终都不会察觉。
加强版的RSA中有两对密钥（a1，b1）、（a2，b2），一对（a1，b1）由信息发送者A生成，另一对（a2，b2）由信息接收者B生成。这时，A、B约定这么做：A用B的公钥a2对信息加密，用自己的私钥b1对信息签名，然后发送给B；B用A的公钥a1对信息验证签名，用自己的私钥b2对信息解密。这样在防止窃秘的基础上，还防止了别人利用公钥发假消息，杜绝了冒名顶替！这个机制不得不说：牛！牛牛！！牛牛牛！！！将这个过程图示如下：
3.RSA的安全性基于这样一个事实：
由两个素数（p，q）乘出一个积（N）很容易（当然，超大结果我也不会算……），但由一个超大数比如长度500位的整数（N），反过来分解出这两个素数，是极端困难的。
由此我们也可以想到，密码的安全性是有时效的，随着计算能力的发展，10年前的密码可能现在破解起来很轻松。因此，加解密和破译总是互相推进的，这个由素数对（p，q）生成的超大整数（N）应该会越来越大。
4.“一般的RSA”的具体实现步骤如下：
①确保：N＞x。哪怕作为加密明文的钥匙——“拟完美序列”，形如“110100001000101101111110101110001100111011000001111001001010100”的二进制字符串——转换出的十进制整数x再大，我们总可以找到更大的整数N，使得：x＜N。
②可以用两个素数p、q的乘积生成N，使得：N=pq，p≠q。这时，N公开，作为公钥对（N，a）的一部分，但是（p，q）要严格保密或摸去痕迹。
③计算φ（N）＝（p-1）（q-1），并严格保密。这个φ（N）叫做“欧拉函数”——是的，就是“数学英雄”欧拉，强人啊！不懂的，就忽略吧，我也不完全懂。
④确定公钥对（N，a）中的a，a需满足条件：(a,N)=1、(a,φ(N))=1、1<a<φ(N)。这个找起来很费劲，慢慢试吧。
⑤根据（φ（N），a）计算出私钥对（N，b）中的b，并严格保密。计算关系如下：
ab≡1（mod φ（N））
呵呵，发明并证明这些的“xx家”们头脑真不是盖的！
⑥加密过程：模N运算，x一横^a＝y一横；
⑦解密过程：模N运算，y一横^b＝x一横。
怎么样？至少是一篇值得备注的入门探索“密码学”的资料吧，哈哈哈。