将CRT(中国剩余定理)与RSA结合
Created At :
Views 👀 :
- 使用中国剩余定理来加快RSA的运算速度，使用Zn中数字的CRT表示法，使用N的素因子预先计算出的三个额外值，来更有效的执行四次幂运算。
在RSA中的一些运算
- 正常的RSA解密，使用私钥(n,d)进行密文解密（或生成签名），不过在运算过程中，我们需要先通过公钥指数e求得私钥指数d，并不如e那么方便，所以可以选择一个值尽可能少的“1”位。
- 对于k位的模数N，私钥质数也有类似的长度，大约一半是“1”。计算指数的时间与k^3成正比,所以需要其他的计算。
- 基础解密：m=c^d mod n
1
2
3
| dp=(1/e) mod (p-1)
dq=(1/e) mod (q-1)
qInv=(1/q) mod p
|
- 1/e表示e关于phi的逆元，表达式x =（1 / e）mod N也写为x = e -1 mod N，并且x是满足xe≡1（mod N）的任何整数。
- 使用在Zn中的唯一值x，数字集合{0,1,2,…,n-1}
- 解密给定的C可以按照下面的步骤
1
2
3
4
| m1 = c^dP mod p
m2 = c^dQ mod q
h = qInv.(m1 - m2) mod p
m = m2 + h.q
|
- 可以发现，dp,dq,qInv,p,q正好是私钥中的内容。
中国剩余定理-特例
1
2
3
4
| 定理：令p,q为不同的素数，n=p*q对于任何对(x1,x2)，其中0≤x 1 <p和0≤x 2 <q
存在唯一的数x，其中0≤x <n
x 1 = x mod p，
x 2 = x mod q。
|
- 任何整数x（0≤x <n）都可以用其CRT表示形式（x 1，x 2）唯一表示。
欧拉定理与欧拉公式
1
2
3
4
5
6
7
8
9
10
11
| 如果n是一个正整数，并且a与n互质即gcd(a,n)=1，则a^φ(n) ≡ 1 (mod n)
φ(n) 是欧拉函数
欧拉函数是求小于等于n的数中与n互质的数的数目
即欧拉函数是求 （小于n的数 ）中 （与n互质的数 ）的数目
或者说欧拉函数是求 1到n-1 中 与n互质的数 的数目
如果n是质数
那么1到n-1所有数都是与n互质的，
所以φ(n) = n-1
如果n是合数。。。自己算吧
例如φ(8)=4，因为1,3,5,7均和8互质
|
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1259742453@qq.com
