RSA算法理论证明

原理

1. 选取两个极大的素数p,q
2. 令n=p*q, 则φ(n)=(p-1)(q-1), φ(n)是n的欧拉函数
3. 选取一个与φ(n)互质的数e, e∈(1,φ(n))
4. 计算出e对于φ(n)的模反元素d
5. M^emodn = C 这里C就是密文
6. C^dmodn = M

素数/质数

给定一个素数p, 则除了1与p本身外不存在其他因数

欧拉函数

φ(n)表示小于n的正整数且与n互质的数的个数

若n为质数, 则φ(n) = n-1

若n为两互质的整数之积, φ(n)=(p-1)(q-1)

模反元素

e与φ(n)互质,则有d, 使得ed-1能被φ(n)整除,即(ed)%φ(n)=1, 此时d称为e对于φ(n)的模反元素,

算法验证

由原理第五、第六步可得

C = M^emodn = (C^dmodn)^emodn

这里引用了公式 ((a^xmodp)^y)modp=a^xymodp

(C^dmodn)^emodn = C^demodn

这里d是e对于φ(n)的模反元素