RSA算法

/ 0评 / 0

RSA算法需要以下相关的数学概念:

素数:素数是一个比1大,其因子只有1和它本身,没有其它数可以整除它的数。素数是无限的。例如,2,3,5,7……等。

两个数互为素数:指的是它们除了1之外没有共同的因子。也可以说这两个数的最大公因子是1。例如,4和9,13和27等。

模运算:如A模N运算,它给出了A的余数,余数是从0到N-1的某个整数,这种运算称为模运算。

RSA加密算法的过程如下:

(1)取两个随机大素数p和q(保密)

(2)计算公开的模数r=pq(公开)

(3)计算秘密的欧拉函数j (r) =(p-1)(q-1)(保密),两个素数p和q不再需要,应该丢弃,不要让任何人知道。

(4)随机选取整数e,满足gcd(e, j (r))=1(公开e,加密密钥)

(5)计算d,满足de≡1(mod j (r))(保密d,解密密钥,陷门信息)

(6)将明文x(其值的范围在0到r-1之间)按模为r自乘e次幂以完成加密操作,从而产生密文y(其值也在0到r-1范围内)

y=xe (mod r)

(7)将密文y按模为r自乘d次幂,完成解密操作

x=yd (mod r)

下面用一个简单的例子来说明RSA公开密钥密码算法的工作原理。

取两个素数p=11,q=13,p和q的乘积为r=p×q=143,算出秘密的欧拉函数j (r)=(p-1)×(q-1)=120,再选取一个与j (r)=120互质的数,例如e=7,作为公开密钥,e的选择不要求是素数,但不同的e的抗攻击性能力不一样,为安全起见要求选择为素数。对于这个e值,可以算出另一个值d=103,d是私有密钥,满足e×d=1 mod j (r),其实7×103=721除以120确实余1。欧几里德算法可以迅速地找出给定的两个整数a和b的最大公因数gcd(a,b),并可判断a与b是否互素,因此该算法可用来寻找解密密钥。

120=7×17+1

1=120-7×17 mod 120=120-7×(-120+17) mod 120==120+7×103 mod 120

(n,e) 这组数公开,(n,d)这组数保密。

设想需要发送信息x=85。利用(n,e)=(143,7)计算出加密值:

y= xe (mod r)=857 mod 143=123

收到密文y=123后,利用 (n,d)=(143,103)计算明文:

x=yd (mod r) =123103mod 143=85

加密信息x(二进制表示)时,首先把x分成等长数据块 x1 ,x2,..., xi ,块长s,其中 2s ≤ n,s尽可能的大。对应的密文是:

yi = xie ( mod r )

解密时作如下计算:

xi = yid ( mod r )

RSA算法中的难点有以下几点:

(1)大数的运算

上百位大数之间的运算是实现RSA算法的基础,因此程序设计语言本身提供的加减乘除及取模算法都不能使用,否则会产生溢出,必须重新编制算法。在编程中要注意进位和借位,并定义几百位的大数组来存放产生的大数。

(2)素数的产生

Hadamard证明,当X变得很大时,从2到X区间的素数数目π(X)与X/ln(X)的比值趋近于1,即:

 

如果在2到X之间随机选取一个整数,其为素数的概率大约为1/ln(X)。对于1024位的模数r=pq,p和q将选取为512位的素数。一个随机选取的512位整数为素数的概率大约为1/ln2512» 1/355。

目前,适用于RSA算法的最实用的素数生成办法是概率测试法。该法的思想是随机产生一个大奇数,然后测试其是否满足一定的条件,如满足,则该大奇数可能是素数,否则是合数,经过充分多次运行该算法,把合数判断为素数的概率可以降低到任何所期望的值以下。如solovay和strassen的简明素性概率检测法。目前也存在多项式时间的确定性算法来判断一个数是否为素数。

(3)高次幂剩余的运算

要计算xe mod r,因x、e、r都是大数而不能采用先高次幂再求剩余的方法来处理,而要采用平方取模的算法,即每一次平方或相乘后,立即取模运算。设e可表示为:

e = bk 2k + bk-1 2k-1 + ... + bi 2i + ... + b2 22 + b1 2 + b0

那么有如下的计算xe算法:

Square-and-Multiply(x,e,r)

Z=1

For i=k downto 0

Do

z=z*z mod r

if bi=1

then z=z*x mod r

Return(z)

RSA的安全性在理论上存在一个空白,即不能确切知道它的安全性能如何。我们能够做出的结论是:对RSA的攻击的困难程度不比大数分解更难,因为一旦分解出r的因子p、q,就可以攻破RSA密码体制。对RSA的攻击是否等同于大数分解一直未能得到理论上的证明,因为没能证明破解RSA就一定需要作大数分解。目前,RSA的一些变种算法已被证明等价于大数分解。不管怎样,分解n是最显然的攻击方法。1977年,《科学美国人》杂志悬赏征求分解一个129位十进数(426比特),直至1994年3月才由Atkins等人在Internet上动用了1600台计算机,前后花了八个月的时间才找出答案。现在,人们已能分解155位(十进制)的大素数。因此,模数n必须选大一些,因具体适用情况而定。

若r=pq被因子分解,则RSA便被击破。

因为若p,q已知,则j (r) =(p-1)(q-1)便可算出。解密密钥d关于e满足:

de≡1(mod j (r) )

故d便也不难求出。因此RSA的安全依赖于因子分解的困难性。目前因子分解数度最快的方法,其时间复杂度为exp(sqrt(ln(n)lnln(n)))。

RSA实验室认为,512比特的r已不够安全。他们建议,现在的个人应用需要用768比特的r,公司要用1024比特的r,极其重要的场合应该用2048比特的r。

总之,随着硬件资源的迅速发展和因数分解算法的不断改进,为保证RSA公开密钥密码体制的安全性,最实际的做法是不断增加模r的位数。

为了安全起见,对p,q还要求:p,q长度差异不大;p-1和q-1有大素数因子;(p-1,q-1)很小。满足这些条件的素数称作安全素数。

其他的安全问题包括:

(1)公共模数攻击。每个人具有相同的r,但有不同的指数e和d,这是不安全的。

(2)低加密指数攻击。如果选择了较低的e值,虽然可以加快计算速度,但存在不安全性。

(3)低解密指数攻击。如果选择了较低的d值,这是不安全的。

(4)选择密文攻击。如A想让T对一个T不愿意签名的消息m’签名,A首先选择一个任意值x,计算y=xe(mod r),然后要求T对m=ym’签名,A最后计算(md mod r)x-1 mod r =( ym’) d x-1mod r= m’d mod r。记住不要对别人提交的随机消息进行签名。

RSA的缺点主要有:

(1)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。

(2)分组长度太大,为保证安全性,n 至少也要 600 bits以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。目前,SET(Secure Electronic Transaction)协议中要求CA采用2048比特长的密钥,其他实体使用1024比特的密钥。

(3)RSA的速度由于进行的都是大数计算,使得RSA最快的情况也比DES慢上100倍,无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。RSA与DES的优缺点正好互补。RSA的密钥很长,加密速度慢,而采用DES,正好弥补了RSA的缺点。即DES用于明文加密,RSA用于DES密钥的加密。由于DES加密速度快,适合加密较长的报文;而RSA可解决DES密钥分配的问题。美国的保密增强邮件(PEM)就是采用了RSA和DES结合的方法,目前已成为E-MAIL保密通信标准。

发表评论

电子邮件地址不会被公开。 必填项已用*标注