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

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.

则结果如下

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