第一章 基础知识 / 1.3 公钥算法

在公钥密码系统中,加密和解密使用的是不同的密钥,这两个密钥之间存在着相互依存关系:即用其中任一个密钥加密的信息只能用另一个密钥进行解密。这使得通信双方无需事先交换密钥就可进行保密通信。其中加密密钥和算法是对外公开的,人人都可以通过这个密钥加密文件然后发给收信者,这个加密密钥又称为公钥;而收信者收到加密文件后,它可以使用他的解密密钥解密,这个密钥是由他自己私人掌管的,并不需要分发,因此又成称为私钥,这就解决了密钥分发的问题。

主要的公钥算法有:RSADSADHECC

1RSA算法

当前最著名、应用最广泛的公钥系统RSA是在1978年,由美国麻省理工学院(MIT)RivestShamirAdleman在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制,是一种分组密码体制。其名称来自于三个发明者的姓名首字母。 它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性。RSA系统是公钥系统的最具有典型意义的方法,大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。

RSA算法是第一个既能用于数据加密也能用于数字签名的算法,因此它为公用网络上信息的加密和鉴别提供了一种基本的方法。它通常是先生成一对RSA 密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册,人们用公钥加密文件发送给个人,个人就可以用私钥解密接受。为提高保密强度,RSA密钥至少为500位长,一般推荐使用1024位。

RSA算法是R.RivestA.ShamirL.Adleman1977年在美国麻省理工学院开发,于1978年首次公布。

RSA公钥密码算法是目前网络上进行保密通信和数字签名的最有效的安全算法之一。RSA算法的安全性基于数论中大素数分解的困难性,所以,RSA需采用足够大的整数。因子分解越困难,密码就越难以破译,加密强度就越高。 

其算法如下:

A.       选择两质数pq

B.       计算n = p * q

C.       计算n的欧拉函数Φ(n) = (p - 1)(q - 1)

D.       选择整数e,使eΦ(n)互质,且1 < e < Φ(n)

E.       计算d,使d * e = 1 mod Φ(n)

其中,公钥KU{e, n},私钥KR={d, n}

 

加密/解密过程:

利用RSA加密,首先需将明文数字化,取长度小于log2n位的数字作为明文块。

对于明文块M和密文块C,加/解密的形式如下:

加密: C = Me mod n

解密: M = Cd mod n = (Me)d mod n = Med mod n

RSA的安全性基于大数分解质因子的困难性。因为若n被分解为n = p * q,则Φ(n)ed可依次求得。目前,因式分解速度最快的方法的时间复杂性为exp(sqrt(ln(n)lnln(n)))。统计数据表明,在重要应用中,使用512位的密钥已不安全,需要采用1024位的密钥。

2DSA算法

DSADigital Signature Algorithm,数字签名算法,用作数字签名标准的一部分),它是另一种公开密钥算法,它不能用作加密,只用作数字签名。DSA使用公开密钥,为接受者验证数据的完整性和数据发送者的身份。它也可用于由第三方去确定签名和所签数据的真实性。DSA算法的安全性基于解离散对数的困难性,这类签字标准具有较大的兼容性和适用性,成为网络安全体系的基本构件之一。 

DSA签名算法中用到了以下参数: 

pL位长的素数,其中L5121024且是64的倍数。 

q160位长且与p-1互素的因子 ,其中h是小于p-1并且满足 大于1的任意数。 

x是小于q的数。 

另外,算法使用一个单向散列函数Hm)。标准指定了安全散列算法(SHA)。三个参数pqg是公开的,且可以被网络中所有的用户公有。私人密钥是x,公开密钥是y 

对消息m签名时: 

1 发送者产生一个小于q的随机数k 

2 发送者产生:

rs就是发送者的签名,发送者将它们发送给接受者。 

3 接受者通过计算来验证签名:

如果v=r,则签名有效。 

3Diffie-Hellman密钥交换

DH算法是W.DiffieM.Hellman提出的。此算法是最早的公钥算法。它实质是一个通信双方进行密钥协定的协议:两个实体中的任何一个使用自己的私钥和另一实体的公钥,得到一个对称密钥,这一对称密钥其它实体都计算不出来。DH算法的安全性基于有限域上计算离散对数的困难性。离散对数的研究现状表明:所使用的DH密钥至少需要1024位,才能保证有足够的中、长期安全。

(4)   椭圆曲线密码体制(ECC)

1985年,N. KoblitzV. Miller分别独立提出了椭圆曲线密码体制(ECC),其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

为了用椭圆曲线构造密码系统,首先需要找到一个单向陷门函数,椭圆曲线上的数量乘就是这样的单向陷门函数。

椭圆曲线的数量乘是这样定义的:设E为域K上的椭圆曲线,GE上的一点,这个点被一个正整数k相乘的乘法定义为 kG相加,因而有

kG = G + G + + G       (共有kG)

若存在椭圆曲线上的另一点N G,满足方程kG = N。容易看出,给定kG,计算N相对容易。而给定NG,计算k = logG N相对困难。这就是椭圆曲线离散对数问题。

离散对数求解是非常困难的。椭圆曲线离散对数问题比有限域上的离散对数问题更难求解。对于有理点数有大素数因子的椭圆离散对数问题,目前还没有有效的攻击方法。