本文共 978 字，大约阅读时间需要 3 分钟。

RSA简介

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。

RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。

算法描述

随机选取两个大 的素数p和q，n = p×q

$\varphi(n) = (q-1)(p-1)$ 找到一个在$[1, \varphi(n)]$ 之间的数$e$，$gcd(e, \varphi(n)) = 1$; 找到e在模$\varphi(n)$下的数论倒数d， 即$ed \equiv 1 (mod \varphi(n))$ 假设明文是M，加密后的密文是C 加密过程

$$M^e \mathbf{mod }\ n = C$$

解密过程

$$C^d \mathbf{mod }\ n = M$$

原理

要用到的定理和公式：

• 欧拉定理，这里只要用到：
  • 两素数$p,q$，$n=pq$，欧拉函数$\varphi(n)\ =\ (p-1)(q-1)$ ，$a$和$n$互素，$a^{\varphi(n)}\ =\ 1\ (mod\ n)$
  • 一个素数$p$，欧拉函数$\varphi(p)\ =\ p-1$，$a$和$p$互素，$a^{\varphi(p)}\ =\ 1\ (mod\ p)$
• 以下两个可能是都知道的吧，也很容易证明，但本人数学渣渣，还是写上万一哪天忘了。
• $a=b\ (mod\ c)\implies a^d=b^d\ (mod\ c)$
• $a=b\ (mod\ c)\implies ad=bd\ (mod\ c)$

证明M经过加密解密之后可以得到M

$$M^e\ \mathbf{mod}\ n\ =\ C$$ 因为 $$M^e = C + kn$$ 所以 $$C = M^e - kn$$ $$C^d = (M^e-kn)^d \equiv M^{ed}\ (mod\ n)$$ 即我们要证明 Med≡M (mod n) $M^{ed} \equiv M\ (mod\ n)$ 因为 ed=1 (mod φ(n)) $ed=1\ (mod\ \varphi(n))$ 所以 ed=kφ(n)+1 $ed = k\varphi(n) + 1$ $$M^{ed} = M^{k\varphi(n)+1}$$ 即要证 $$M^{k\varphi(n)+1}\equiv M\ (mod\ n)$$ 下面分两种情况： 情况一：gcd(M,n) = 1 由欧拉定理知 $$M^{\varphi(n)}\equiv 1\ (mod\ n)$$ 进一步，得证 $$M^{k\varphi(n)+1}\equiv M\ (mod\ n)$$

情况二：$gcd(M, n)\neq 1$

M一定有因子p或q，不妨设$M=jq$ 由于M与p互素，由欧拉定理

$$M^{p-1}\equiv1\ (mod\ p)$$ 乘方后再乘上M $$M^{(p-1)(q-1)k}M\equiv M^{k\varphi(n)+1}\equiv M^{ed}\equiv M (mod\ p)$$ 由于 M=jq $M=jq$ $$(jq)^{ed}=jq+lp$$ 则q能整除l,设 l=Lq $l = Lq$ 最后 $$(jq)^{ed}=jq+Ln$$ $$M^{ed} \equiv M\ (mod\ n)$$

证明完毕

转载地址：http://zopjz.baihongyu.com/