浅析加密算法七【RSA密码】

一、简介

• RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制
• 在公开密钥密码体制中，加密密钥（即公开密钥）PK 是公开信息，而解密密钥（即秘密密钥） SK 是需要保密的。加密算法 E 和解密算法 D 也都是公开的。虽然解密密钥SK是由公开密钥 P K PK PK 决定的，但却不能根据 PK 计算出 SK
• 正是基于这种理论， 1978 1978 1978 年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为 500 500 500 位长，一般推荐使用 1024 1024 1024 位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的 DES 或 IDEA 对话密钥加密，然后使用 RSA 密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要
• RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一

二、原理 2.1 加密过程 步骤说明描述1选择一对不相等且足够大的质数p,q2计算 p , q p,q p,q 的乘积 n = p × q n=p\times q n=p×q3计算 n n n 的欧拉函数 φ ( n ) = ( p − 1 ) × ( q − 1 ) \varphi(n)=(p-1)\times(q-1) φ(n)=(p−1)×(q−1)4选一个与 φ ( n ) \varphi(n) φ(n) 互质的整数 e e e 1 < e < φ ( n ) 1