RSA算法简述
http://pajhome.org.uk/crypt/rsa/rsa.html
1.密钥生成:
1.1 生成两个大的质数(素数)p和q.(质数就是只能被自己和1整除的数)
1.2 n=p*q
1.3 m=(p-1)*(q-1)
1.4 生成较小的数e, 使e与m互质
(特别借用隔壁豆豆的小学数学课本找出:
互质的概念其实和质数没有什么关系，互质的定义为：如果非0整数a,b的
最大公约数为1，则说这两个数互质)
1.5 生成d,使d*e%m=1,%代表求余数.
至此公钥为e和n,私钥为d和n. 至于p,q,m马上丢弃
2.加密过程:
产生密文c的公式为:c=p^e%n, 即p的e次方除以n求余,可见加密是用公钥进行的,加密只牵涉到明文
和公钥.
至此可以把密文传出去了,这样就是被截获也搞不懂原文是什么.
3.解密过程:
收到密文c后
产生明文(解密)p的公式为:p=c^d%n,即c的d次方除以n求余.可见解密只牵涉到私钥和密文.
因此从整个过程来看,只要你保管好私钥,不泄密,可以放心的把密文和公钥公开.
举个例子:
本例用较小的质数为例,以计算方便,小质数并不安全
1.密钥生成:
1.1 p=7, q=19
1.2 n=p*q=7*9=133
1.3 m=(p-1)*(q-1)=(7-1)*(19-1)=108
1.4 生成较小的数e,使e与108互质,2,3,4都不对,5是最小的,于是e=5
1.5 生成d,使d*e%m=1,d*5%108=1,d*5除以108余数为1,...于是算出d=65
至此公钥e=5,n=133.私钥d=65,n=133.密钥计算完毕
2.加密过程:
RSA的原则是被加密的信息应该小于p和q的较小者,所以在这个例子中,我们要指明被加密的数字要小于
7. 于是我们取6为例
加密:c=p^e%n=6^5%133=7776%133=62, 于是密文为62. 把62传出去.
(我想同时应把公钥也传出去,好在收到时知道对应的是那个私钥)
3.解密过程:
(我想接收者收到密文和公钥,找到对应的私钥)
解密: p=c^d%n=62^65%133=62*62^64%133 经过好一阵子运算,余数为6,参见
