关于RSA公钥加密算法及其安全性讨论
需积分: 9 38 浏览量
2010-05-19
21:18:09
上传
评论
收藏 37KB DOC 举报
RSA 公钥加密算法及其安全性
(RSA algorithm for public-key encryption and the security)
摘要（
DIGEST
）
:
RSA 算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。
RSA 是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受 ，
普遍认为是目前最优秀的公钥方案之一。T
RSA
的安全性依赖于大整数的因式分解问题
,
只要其钥匙的长度
足够长，用
RSA
加密的信息实际上是不能被解破的。但在分布式计算技术和量子计算机理论日趋成熟的
今天，
RSA
加密安全性受到了挑战。 RSA algorithm is the first one can be used for
both encryption and digital signature algorithms, but also easy to
understand and operate. RSA is the most widely studied public key algorithm,
first put forward nearly two decades now, has undergone the test of various
attacks, gradually accepted, widely considered the most outstanding public
key options. RSA's security depends on a large integer factorization
problem. As long as the length of its key long enough, with the RSA
encryption of information in fact can not be cracked in. However, in
distributed computing technology and the theory of quantum computers today
are becoming more mature, RSA encryption security has been challenged.
随着通信的飞速发展，信息安全也越来越显得重要。计算机密码体制的基本思想就是将要保护的信
息变成伪装信息，只有合法的接收者才能从中得到真实的信息。密码体制有对称密钥体制和非对称密钥体
制之分，这里讨论的
RSA
公钥体制便为非对称密钥体制，也叫做公开密钥体系。
RSA
加密演算法是一種非對稱加密演算法。在公鑰加密標準和電子商業中
RSA
被廣泛使用。
RSA
是
1977
年由羅納德
·
李維斯特（
Ron Rivest
）、 阿迪
·
薩莫爾（
Adi Shamir
）和倫納德
·
阿德曼（
Leonard
Adleman
）一起提出的。
RSA
就是他們三人姓氏開頭字母拼在一起組成的。他们在题为《获得数字签名和
公开钥密码系统的方法》的论文中提出了基于数论的非对称
(
公开钥
)
密码体制，称为
RSA
密码体制。
RSA
是建立在“大整数的素因子分解是困难问题”基础上的，是一种分组密码体制。
對極大整數做因式分解的難度決定了
RSA
演算法的可靠性。換言之，對一極大整數做因式分解愈困
難，
RSA
演算法愈可靠。假如有人找到一種快速因式分解的演算法的話，那麼用
RSA
加密的信息的可靠
性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的
RSA
鑰匙才可能被強力
方式解破。
RSA
算法T
:
首先
,
找出三个数
, p, q, r,
其中T
p, q
是两个相异的质数
, r
是与T
(p-1)(q-1)
互质的数
.p,
q, r
这三个数便是加密密钥。T接著
,
找出T
m,
使得T
rm == 1 mod (p-1)(q-1)
。这个T
m
一定存在
,
因为T
r
与T
(p-1)(q-1)
互质
,
用辗转相除法就可以得到了。T再来
,
计算T
n = pq
。T
m, n
这两个数便是公开密钥。
编码过程是
,
若资料为T
a,
将其看成是一个大整数
,
假设T
a < n
，如果T
a >= n
的话
,
就将T
a
表成T
s
进位
(s <= n,
通常取T
s = 2^t),
则每一位数均小於T
n,
然後分段编码。T接下来
,
计算T
b == a^m mod n, (0
<= b < n), b
就是编码後的资料。T解码的过程是
,
计算T
c == b^r mod pq (0 <= c < pq),
於是乎
,
解码完毕。等会会证明T
c
和T
a
其实是相等的T。如果第三者进行窃听时
,
他会得到几个数
: m,
n(=pq), b
，他如果要解码的话
,
必须想办法得到T
r
，T所以
,
他必须先对T
n
作质因数分解，T要防止他分解
,
最有效的方法是找两个非常的大质数T
p, q,
使第三者作因数分解时发生困难。T
<
定理
>
若T
p, q
是相异质数
, rm == 1 mod (p-1)(q-1), a
是任意一个正整数
, b == a^m mod pq, c ==
b^r mod pq,
则T
c == a mod pq
评论0
最新资源