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$