RSA算法详解与练习

1977年，麻省理工学院的 Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出了一种非对称加密算法，用他们三人的姓氏缩写命名为 RSA。RSA 既不是惟一，也不是最早的非对称加密算法。但它是使用最广泛，因而也是最重要的非对称加密算法。

1.随机选择两个不相等的质数p和q。 2.计算p和q的乘积n(n=p*q),n的长度就是密钥长度。 3.计算n的欧拉函数φ(n)： φ(n) = (p-1)(q-1) 4.随机选择一个整数e，也就是公钥当中用来加密的那个数字 条件是1< e < φ(n)，且e与φ(n) 互质。 5.取e的模反数d，计算方法为:e * d ≡ 1 (mod φ) 6.将n和e封装成公钥，n和d封装成私钥，（n，e),(n，d)就是密钥对。

补充说明: 1.下面代码中使用phi代替欧拉函数φ(n) 2.如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。

首先对明文进行比特串分组，使得每个分组对应的十进制数小于n，然后依次对每个分组m做一次加密，所有分组的密文构成的序列就是原始消息的加密结果，即m满足0