RSA算法

RSA算法：
1.找两的大素数p和q
2.取n=p*q   n的二进制表示时所占用的位数，就是所谓的密钥长度。
3. 使用奇数公钥指数e的RSA数字签名方案的私钥SK由两个素数p和q，满足： p-1，q-1与e互质 且 1

  以及私钥d，满足： e*d=1 % (p-1)*(q-1)

  组成相对应的公钥PK由公钥模n=pq和公钥指数e组成。

公钥（n, e） 私钥（n, d）

    这样最终得到三个数： n   d   e

 

使用奇数公钥指数的RSA签名函数被定义为：

S＝Sign(SK)[X]：=Xd mod n，0

这里X是用于签名的数据，S为对应的数字签名。

恢复函数

使用奇数公钥指数的RSA恢复函数被定义为

X=Recover(PK)[S]：=Se mod n。

 

RSA加解密的算法完全相同，设A为明文，B为密文，则：

  A=B**e % n；B=A**d % n；

e和d可以互换使用，即：

  A=B**d % n；B=A**e % n;

设消息为数M (M 设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。

在对称加密中：
n d两个数构成公钥，可以告诉别人；
n e两个数构成私钥，e自己保留，不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。

rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法
求得d。

 

举例:

选p=7，q=17。 求n=p * q = 119,  T=(p-1)*(q-1)=96

取e=5，满足1

确定满足d*e=1 % 96且小于96的d, 因为77*5=385=4*96+1 ，所以d为77。

因此公钥为{5, 119}, 私钥为{77, 119};

设明文m=19, 则密文C = 19**5 % 119 =2476099 % 119 =66

解密 66**77 % 119 = 19