rsa密钥对生成，n/d-crt加解密示例，以及明文的格式要求

àì夳堔傛蜴生んèń 2022-04-11 04:28 233阅读 0赞

转载自：[https://blog.csdn.net/jennyvenus/article/details/79799100][https_blog.csdn.net_jennyvenus_article_details_79799100]

rsa加解密公式  
设A为明文，B为加密后的密文  
加密过程  B=A^e mod n；   
解密过程  A=B^d mod n；

从公式上可以看出，加解密时数据会mod n，那么大于N的数据，都会发生回绕，失去原有属性。

举例  
1）生成密钥对  
  a）选两个素数，为P和Q  
     设P = 13, Q = 7  
     则N = p \* q = 91  
       
  b）选择E，要求e 和 ( p - 1 ) \* ( q - 1 )互质  
       (p-1)\*(q-1) = 12 \* 6 = 72，选择E = 7则可以。  
     现在 N = 91, E = 7  
       
  c）选择D，要求(d\*e) mod (p-1)\*(q-1) = 1。  
      (p-1)\*(q-1)的值是72，所以  
      ( d \* e ) mod 72 = 1，( d \* e )可以是73, 145, 217..........  
      选d \* e = 217，则d = 31  
2）n-d格式加解密过程  
   a）设A为明文，B为密文，  
        加密过程  B=A^e mod n；   
        解密过程  A=B^d mod n；  
   b）加密  
        设a = 2 则 a ^ e = 2 ^ 7 = 128, mod 91 = 37，则 37为密文  
        b = 37  
   c）解密  
        b ^ d = 37 ^ 31 = 4.1138973036067710421568685993113e+48, mod 91 = 2  
        解密结果等于明文，加解密成功  
   d）若明文 大于 n，假设 a等于93  
        a ^ e = 93 ^ 7 = 60170087060757, mod 91 = 37，则密文还是37  
        对37进行解密，得到的明文是2，与原始输入数据不一致  
        所以明文 不能 大于 N

CRT部分  
1）dP=d mod (P-1)  
2）dq=d mod (q-1)  
3）q\*qinv=1 mod p, 即：qinv = q^(-1) mod p

则结果如下  
p = 13  
q = 7  
E = 7  
dp = 31 mod (13-1) = 7  
dq = 31 mod (7-1)  = 1  
q \* qinv 是与 p 互质，p = 13，则与13素质的整数，则q \* qinv 可能为 7, 14, 21, 28, ....，选择q \* qinv = 14，则qinv = 2

crt签名(解密)过程：(c 待签名的消息或密文，S签名结果或者明文)  
1）Cp=c mod p;  
2）Cq=c mod q;  
3）Mp=Cp^dp mod p;  
4）Mq=Cq^dq mod q;  
5）S=(((mp - mq) \* qinv) mod p)\*q + mq;

仍然设置明文 c = 2  
则  
cp = c mod p = 2  
cq = c mod q = 2  
mp = 2 ^ 7 mod p = 128 mod 13 = 11  
mq = 2 ^ 1 mod q = 2 mod 1 = 2  
s = (((11-2)\*2) mod 13)\*7 + 2 = ((9 \* 2) mod 13)\*7+2 = 5 \* 7 + 2 = 37

RSA---CRT故障攻击

攻击过程  
现在用旁路攻击的方法对其攻击：注入一个错误使得Mp变成mp,此时输出的签名结果变成：S’.  
S’= (mp-Mq)\*(qinv mod p)\*q+Mq;  
?  
求（S’^e-c）与n的最大公约，最大公约数就是素因子q,

举例1：  
在求mp的过程中出错，在某种攻击下，其p由13(00001101)变成了(00001001)，也就是9，那么  
1）Cp' = c mod p' = 2 mod 9               = 2  
2）Cq=c mod q                             = 2  
3）Mp'=Cp'^dp mod p;                      = 2 ^ 7 mod p' = 128 mod 9 = 2  
4）Mq=Cq^dq mod q;                        = 2  
5）S'=(((mp' - mq) \* qinv) mod p')\*q + mq;   = (((2-2)\*2)mod 9)\*7+2  = 2

则密文 s' = 2  
(s' ^ e) - c = 2 ^ 7 - 2 = 128 - 2 = 126  
126与91的最大公约数为 7，这个就是q，有了q，则计算p = n / q = 13，则p, q都被计算攻击

举例2:  
在求mp的过程中出错，在某种攻击下，其p由13(00001101)变成了(00001111)，也就是15，那么  
1）Cp' = c mod p' = 2 mod 15              = 2  
2）Cq=c mod q                             = 2  
3）Mp'=Cp'^dp mod p;                      = 2 ^ 7 mod p' = 128 mod 15 = 8  
4）Mq=Cq^dq mod q;                        = 2  
5）S'=(((mp' - mq) \* qinv) mod p')\*q + mq;   = (((8-2)\*2)mod 15)\*7+2  = 12 \* 7 + 2 = 86

则密文 s' = 86  
(s' ^ e) - c = 86 ^ 7 - 2 = 34792782221696 - 2 = 34792782221694  
34792782221694 与91的最大公约数为91的最大约数，91的最大约数很容易计算只有，1，7，13，91四个数，而13，91不能被34792782221694整除，所以q = 7  
同样马上可以计算出p = 13

[https_blog.csdn.net_jennyvenus_article_details_79799100]: https://blog.csdn.net/jennyvenus/article/details/79799100