密码学公开密钥体系之RSA算法new

[密码学]公开密钥体系之RSA算法当前最著名、应用最广泛的公钥系统RSA是在1978年，由美国麻省理工学院(MIT)的Ron

Rivest,

Adi

Shamir

和Leonard

Adleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制，是一种分组密码体制。其名称来自于三个发明者的姓名首字母。

它的安全性是基于大整数素因子分解的困难性，而大整数因子分解问题是数学上的著名难题，至今没有有效的方法予以解决，因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法，大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。RSA算法是第一个既能用于数据加密也能用于数字签名的算法，因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA

密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册，人们用公钥加密文件发送给个人，个人就可以用私钥解密接受。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。该算法基于下面的两个事实,这些事实保证了RSA算法的安全有效性：1.已有确定一个数是不是质数的快速算法；2.尚未找到确定一个合数的质因子的快速算法。工作原理1)

任意选取两个不同的大质数p和q，计算乘积r=p*q；2)

任意选取一个大整数e，e与(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用。3)

确定解密密钥d：

d

*

e

=

1

modulo（p

-

1）*（q

-

1）

根据e、p和q可以容易地计算出d。4)

公开整数r和e，但是不公开d；5)

将明文P

(假设P是一个小于r的整数)加密为密文c，计算方法为：c

=

Pe

modulo

r6)

将密文c解密为明文P，计算方法为：P

=

cd

modulo

r然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。数学原理定理若

p,

q

是相异质数,

rm

==

1

mod

(p-1)(q-1),a

是任意一个正整数,

b

==

a^m

mod

pq,

c

==

b^r

mod

pq,则

c

==

a

mod

pq证明的过程,

会用到费马小定理,

叙述如下:m

是任一质数,

n

是任一整数,

则

n^m

==

n

mod

m(换另一句话说,

如果

n

和

m

互质,

则

n^(m-1)

==

1

mod

m)运用一些基本的群论的知识,

就可以很容易地证出费马小定理的........证明因为

rm

==

1

mod

(p-1)(q-1),

所以

rm

=

k(p-1)(q-1)

+

1,

其中

k

是整数因为在

modulo

中是

preserve

乘法的(x

==

y

mod

z

and

u

==

v

mod

z

=>

xu

==

yv

mod

z),所以,

c

==

b^r

==

(a^m)^r

==

a^(rm)

==

a^(k(p-1)(q-1)+1)

mod

pq1.

如果

a

不是

p

的倍数,

也不是

q

的倍数时,则

a^(p-1)

==

1

mod

p

(费马小定理)

=>

a^(k(p-1)(q-1))

==

1

mod

pa^(q-1)

==

1

mod

q

(费马小定理)

=>

a^(k(p-1)(q-1))

==

1

mod

q所以

p,

q

均能整除

a^(k(p-1)(q-1))

-

1

=>

pq

|

a^(k(p-1)(q-1))

-

1即

a^(k(p-1)(q-1))

==

1

mod

pq=>

c

==

a^(k(p-1)(q-1)+1)

==

a

mod

pq2.

如果

a

是

p

的倍数,

但不是

q

的倍数时,则

a^(q-1)

==

1

mod

q

(费马小定理)=>

a^(k(p-1)(q-1))

==

1

mod

q=>

c

==

a^(k(p-1)(q-1)+1)

==

a

mod

q=>

q

|

c

-

a因

p

|

a=>

c

==

a^(k(p-1)(q-1)+1)

==

0

mod

p=>

p

|

c

-

a所以,

pq

|

c

-

a

=>

c

==

a

mod

pq3.

如果

a

是

q

的倍数,

但不是

p

的倍数时,

证明同上4.

如果

a

同时是

p

和

q

的倍数时,则

pq

|

a=>

c

==

a^(k(p-1)(q-1)+1)

==

0

mod

pq=>

pq

|

c

-

a=>

c

==

a

mod

pqQ.E.D.这个定理说明

a

经过编码为

b

再经过解码为

c

时,

a

==

c

mod

n

(n

=

pq)....但我们在做编码解码时,

限制

0

<=

a

<

n,

0

<=

c

<

n,所以这就是说

a

等於

c,

所以这个过程确实能做到编码解码的功能.....为了说明该算法的工作过程,我们下面给出一个简单例子,显然我们在这只能取很小的数字，但是如上所述，为了保证安全，在实际应用上我们所用的数字要大的多得多。例：选取p=3,

q=5，则r=15，（p-1）*（q-1）=8。选取e=11（大于p和q的质数），通过d

*

11

=

1

modulo

8，计算出d

=3。假定明文为整数13。则密文c为c

=

Pe

modulo

r=

1311

modulo

15=

1,792,160,394,037

modulo

15=

7复原明文P为：P

=

cd

modulo

r=

73

modulo

15=

343

modulo

15=

13因为e和d互逆，公开密钥加密方法也允许采用这样的方式对加密信息进行"签名"，以便接收方能确定签名不是伪造的。两个在不安全信道中通信的人，假设为Alice（收信者）和Bob（发信者），他们希望能够安全的通信而不被他们的敌手Oscar破坏。Alice

想到了一种办法，她使用了一种锁（相当于公钥），这种锁任何人只要轻轻一按就可以锁上，但是只有Alice的钥匙（相当于私钥）才能够打开。然后

Alice

对外发送无数把这样的锁，任何人比如Bob想给她寄信时，只需找到一个箱子，然后用一把Alice的锁将其锁上再寄给Alice，这时候任何人（包括

Bob自己）除了拥有钥匙的Alice，都不能再打开箱子，这样即使Oscar能找到Alice的锁，即使Oscar能在通信过程中截获这个箱子，没有

Alice的钥匙他也不可能打开箱子，而Alice的钥匙并不需要分发，这样

Oscar也就无法得到这把“私人密钥”。优点RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现在已近二十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开，使得密钥分配更为方便。它特别符合计算机网络环境。对于

网上的大量用户，可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信，只需从公钥簿上查出对方的加密密钥，用它对所传送的信息加密发出即可。对方收到信息后，用仅为自己所知的解密密钥将信息脱密，了解报文的内容。由此可看出，RSA算法解决了大量网络用户密钥管理的难题，这是公钥密码系统相对于对称密码系统最突出的优点。缺点1)产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。2)安全性,

RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPc问题。目前，人们已能分解140多个十进制位的大素数，这就要求使用更长的密钥，速度更慢；另外，目前人们正在积极寻找攻击RSA的方法，如选择密文攻击，一般攻击者是将某一信息作一下伪装(Blind)，让拥有私钥的实体签署。然后，经过计算就可得到它所想要的信息。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构：(

XM

)d

=

Xd

*Md

mod

n前面已经提到，这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way

Hash

Function对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或φ（n）等等攻击.3)速度太慢,由于RSA

的分组长度太大，为保证安全性，n

至少也要

600

bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。目前，SET(Secure

Electronic

Transaction)协议中要求cA采用2048比特长的密钥，其他实体使用1024比特的密钥。为了速度问题,目前人们广泛使用单,公钥密码结合使用的方法,优缺点互补:单钥密码加密速度快,人们用它来加密较长的文件,然后用RSA来给文件密钥加密,极好的解决了单钥密码的密钥分发问题。公钥加密算法中使用最广的是RSA。RSA算法研制的最初理