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，要求(de) 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