RSA加密原理

RSA加密的数学原理

RSA加密基本基于欧拉函数。

两个数没有1以外的公因数的整数称为互质，记作\(gcd(a,b)=1\)。

欧拉函数（Euler's totient function），即 𝜑(𝑛)，表示的是小于等于 𝑛和 𝑛 互质的数的个数。

欧拉函数\(𝜑(𝑛\))具有以下性质：

1.若\(n\)为质数，则\(𝜑(𝑛)=n-1\)；

2.若\(n=p\cdot q\)，且\(p\)、\(q\)均为质数，则有\(𝜑(𝑛)=(p-1) \cdot (q-1)=𝜑(p) \cdot 𝜑(q)\)。

3.如果\(gcd（a,n）=1\)，则有\(a^{φ(n)}≡1(\mod n)\)。

已知\(gcd(a,n)=1\),如果存在\(b\)使\(a\cdot b≡1(\mod n)\)，则称\(b\)为\(a \mod n\)的逆元，写作\(a^{-1}\)。

根据定理可以得知：

由于对1取任何大于1的数的模，结果都为1，因此有\((a\cdot a^{-1})\mod n=1\)，即\(a\cdot a^{-1}-1=k\cdot n\)，或\(a\cdot a^{-1} -k\cdot n=1\)，其中k是任何符合条件的正整数。

且根据线性同余方程可以得到推论：当且仅当\(gcd(a,n)=1\)时，\(a\mod n\)的逆元\(a^{-1}\)存在且唯一。

选定2个保密的200位质数\(p\)、\(q\)，按以下步骤计算：

1.计算\(n=p\cdot q\)，\(𝜑(𝑛)=(p-1)*(q-1)\)。

2.选定任意系数\(e\)，满足\(1<e<𝜑(𝑛)\)，且\(gcd(𝜑(𝑛),e)=1\)。

3.计算\(e \mod 𝜑(𝑛)\)的逆元\(d\)。

4.以\((e,n)\)为公钥，\((d,n)\)为私钥。

1.加密使用公钥\((e,n)\)：\(c=m^e\mod n\)

2.解密使用私钥\((d,n)\)：\(m=c^d \mod n\)