公开密钥算法RSA简介及简单证明
公开密钥算法RSA简介
此博客争取以最精简的语言讲解RSA公钥加密算法的原理和结果证明
- 选取两个大素数p,q，并要求保密
- 计算n = p * q，以及欧拉函数φ(n) = (p-1) * (q-1)
- 随机选取加密秘钥 e ，要求 e 和 φ(n) 互质
- 根据Euclid算法计算解密秘钥 d ，应满足 d * e ≡ 1 mod φ(n) ,其中 n 和 d 也要满足互素。即**（e,n）即为公钥，(d,n)**即为私钥。
- 最终结果即 m ^ e ≡ c (mod n)和 c ^ d ≡ m (mod n)，其中m为明文，c为密文
RSA的简单证明 RSA的证明涉及简单的欧拉定理，不懂之处请自行百度 RSA算法的证明即是对最终结果中的两个公式证明 m ^ e ≡ c (mod n) ① c ^ d ≡ m (mod n) ② 根据欧拉定理，当满足条件p,q为素数，x与n互质，φ(n) = (p-1) * (q-1) ，n = p * q 则有 x ^ φ(n) ≡ 1 mod n 成立 将公式 ② 代入到公式 ① 可得 (c ^ d mod n)^e mod n ≡ c 证明RSA算法即是证明此式是否成立？
左边 = c ^de mod n 由于 d * e ≡ 1 mod φ(n) ，令 d * e = φ(n) * t + 1 ,为使公式显得更加简洁下面将用字母a代替φ(n). d * e = a * t + 1 所以左边 = c ^ (a * t + 1) mod n = c * c^(a * t) mod n =c * [(c^a) mod n] ^t mod n ———根据上述 c ^ a mod n ≡ 1 =c * 1 ^ t mod n =c 证明结束
上一篇：
Java架构师技术进阶路线图
下一篇：
基于epoll的高并发web服务器