随着计算机和网络通信的快速发展,人们开始重视个人数字信息保护和各种服务的安全性,如保护个人秘密信息,防止消息篡改,保证通信双方的公平性等。密码学为这些服务的安全性提供了技术,特别是公钥密码学,已成为当今社会信息安全技术的核心。1976年Diffie和Hellman在发表的论文《密码学的新方向》中首次提出公钥加密概念,是密码学方向的一个重要里程碑,开启了密码学的新纪元。麻省理工学院的Rivest, Shamir和Adleman设计出第一个实际的公钥密码体制,称为RSA算法,是迄今为止最著名的公钥密码算法之一,它可以同时用于数据加密和数字签名。1978年,Merkle和Hellman提出了基于子集和问题的背包公钥密码算法-Merkle-Hellman密码体制。此后,又有许多重要的公钥密码算法相继被提出,如McEliece加密算法,Rabin加密算法,ElGamal加密与签名算法,椭圆曲线密码(ECC)算法,Goldwasser-Micali概率加密算法等。目前,RSA加密与签名算法,ElGamal签名算法的变型(DSA)已成为国际上著名的加密签名标准,这些密码算法被广泛应用于网络安全领域和银行系统,为交互双方安全通信提供了保障和技术。因此,对公钥密码算法的安全性进行分析具有重要的理论意义和实际的应用价值。自从公钥密码学提出以来,密码学家一直致力于密码算法的安全性研究。本文针对RSA和背包两种公钥密码体制的安全性做了一些研究。我们的主要工作集中在中国剩余定理表示的RSA密码系统和RSA模特殊素因子的安全性分析,同时针对抵抗Shamir攻击和低密度攻击的两种新背包型密码算法,分别给出有效的破解算法。1.基于中国剩余定理表示(CRT)RSA密码系统小解密指数的攻击分析简单版本的RSA算法描述如下,首先选取比特长度相同的两个大素数p与q,它们的乘积N被称为RSA模。除此之外,另两个重要的参数是加密指数e和解密指数d,其中e与N的欧拉函数φ(N)：=(p-1)(q-1)互素,且满足RSA方程ed=1 mod(?)(N).RSA加密算法加密消息m时,计算C=me mod N,发送密文C给用户。用户收到密文C后,进行解密运算Cd mod N,由欧拉定理知Cd=med=m mod N,从而得到消息m。RSA的安全性基于求解模N的e次根的困难性。破解RSA公钥密码体制直接有效的方法是分解RSA模N。目前分解整数的方法有连分数方法,Pollardp-1方法,二次筛法,椭圆曲线方法,数域筛法等,其中分解RSA模最快的方法是数域筛法,其时间和空间复杂度都是亚指数的。最近,768比特的RSA挑战数宣告被分解,其算法的复杂度相当于分解512比特的RSA挑战数的上千倍。同时密码学家建议1024比特的RSA在三到四年内停止使用,为保证安全可以使用比特数为1536比特,甚至2048比特的RSA模。Shor 1992年在假设量子计算机模型存在的情况下,给出了分解整数的多项式时间算法,然而能否研究出多量子位的量子计算机还是一个未知数。1982年A.Lenstra,H.Lenstra和L.Lovasz提出计算格中近似短向量的多项式时间算法,并用此算法解决了有理系数多项式的分解问题。人们以三人姓氏的首字母命名此算法为LLL算法。LLL算法在RSA密码算法及其他公钥密码体制的安全性分析中有广泛的应用。最著名的是,Coppersmith利用LLL算法在多项式时间内求解单变量的模N方程fN(χ)=0 mod N的小根x0,其中N是分解未知的合数,和计算两个变量的整系数方程f(x,y)=0的小根(x0,y0)。此后,许多RSA的攻击结果都是基于Coppersmith的格构造技术和近似短向量求解算法-LLL算法,如小加密指数攻击,小解密指数攻击,密钥泄露攻击等。对于小解密指数攻击,Wiener在1990年提出当d<N0.25时,通过扩展欧几里得算法求解e/N的渐近连分数,得到解密指数d,从而在多项式时间内分解RSA模。目前最好的结果是Boneh和Durfee提出的。即当d<N0.292时,可以分解RSA模。基本思想是通过RSA方程ed=κ(?)(N)+1,利用Coppersmith的格构造技术构造格,然后使用格归约算法找到格中的较短向量,最后求解短向量所表示的二元方程的根。为了抵抗上述小解密指数攻击,Wiener指出使用中国剩余定理(CRT)表示私钥d来进行解密或签名是一种非常有效的方法,并且可以选取小的CRT解密指数代替小的解密指数使解密过程更加有效快速。这种表示形式最早是由Quisquater和Couvreur提出的。具体地,RSA密码算法的解密指数d由CRT解密指数dp和dq表示,且满足满足下面关系当解密密文c= me mod N时,不是计算m= cd mod N,而是mp= cdp mod p和mq= cdq mod q,然后通过中国剩余定理计算出明文m。可以看出,使用CRT解密指数dp和dq进行解密比标准RSA解密过程一般快四倍。Galbraith, Heneghan, Mckee[110]和Sun, Wu[110]基于素数分布理论分别设计了快速加密和解密的CRT-RSA密码体制,其密钥生成方法是,首先选取小的公钥指数e和私钥指数dp,dq,然后检测所得的p和q是否为素数。Bleichenbacher和May分析了文献[40,110]设计的CRT-RSA密码体制的安全性,指出当CRT解密指数dp和dq满足攻击者可以在多项式时间内有效分解RSA模N。其攻击方法是巧妙地利用CRT-RSA方程得到一个关于四个变元的线性方程,然后构造一个特殊的三维格,把分解RSA模问题转化成求解此三维格中的最短向量问题。LLL算法在三维格中可以找到最短向量,因此利用LLL算法就可以解决上述问题。文献[3]指出,假设所构造三维格中长度小于Minkowski界的短向量是唯一的,从而可以分解此向量所对应的多项式,得到CRT-RSA的私钥指数dp,dq。本文第三章指出此唯一性假设在一般情况下不成立,证明文献[3]中构造的格中长度小于Minkowski界的短向量是不唯一的,也就说明存在多个小于Minkowski界的短向量,并给出了反例。同时讨论能否改进格的构造使得文献[3]的攻击方法还可以有效,我们给出了否定的答案,并指出了原因。同时,我们对上述攻击进行了改进和完善,即在一般情况下可以求解此问题。特别地,对于e<N3/8和dp,dq<(1/3)N(1/4),指出利用连分数方法可以有效地求解此问题。2.特殊素因子的RSA密码系体制的安全性分析记RSA模N的两个素因子p和q的差p-q为∧,称为RSA模N的素因子差。记ip-jq为∧1,其中i,j是小整数,称为N的素因子组合差。de Weger研究分析了∧比较小的这种情况,且要求p和q的比特长度相同,给出了弱密钥解密指数d的界与∧之间的关系。指出当N的素因子差很小时,分别利用连分数方法和格基归约方法可以提高Wiener和Boneh,Durfee的弱密钥解密指数d的界。Blomer和May通过对等式ex+y≡0 mod(?)(N)进行分析,给出了新的弱密钥估计,同时也提出弱密钥的范围随着素因子差∧变小而增大。最近,Maitra和Sarkar考虑了2q-p的情况,本质上是Weger分析结果的补充。如果p和q的比特数不同,上述攻击分析方法是不成立的。因此,本文就此情况展开讨论,即允许p和q是不同比特的素数,分析N的素因子组合差A1=ip-jq与解密指数d之间的联系。首先,利用Fermat的分解方法,证明当Λ1≤(logN)″(|ij|N)(1/4)可以在多项式时间内计算出RSA模N的素因子p和q。其次,当Λ1≥(|ij|N)(1/4)利用连分数攻击方法分析∧1与d之间的关系,并给出当解密指数d满足条件d<N(3/4)-β-τ时,其中Λ1=Nβ，τ>0，RSA密码算法是不安全的。进一步,通过格归约分析方法,讨论RSA模N的素因子组合差∧1与弱密钥解密指数d的关系。以上情况下,当d>N0.292且p,q不同比特时,文献[9,72,116,117]中的攻击方法是不成功的,并给出了实例论证。同时,分析扩展了Blomer,May的攻击结果,得到更多新的弱密钥。3.两种背包型公钥密码算法的安全性分析背包加密算法是基于子集和问题的困难性设计的,该问题已被证明是NP完全问题。也就是说,不存在多项式时间算法求解子集和问题。Merkle和Hellman设计了第一个基于子集和问题的密码算法,具有重要的历史意义。随后人们提出了许多Merkle-Hellman背包算法的变体,其中大多数变体(包括原始方案)已被证明是不安全的。Shamir第一个提出了针对基本的Merkle-Hellman背包方案的多项式时间攻击,这种攻击利用H.Lenstra的整数规划算法,当变量的数目固定时,该算法是多项式时间的,但在实际中效率很低。Adleman指出Merkle-Hellman背包算法的分析也可以看成格基归约问题,利用LLL算法更简洁有效的破解Merkle-Hellman体制。Logarias和Brickell,以及Coster等人利用格基归约方法针对背包密码体制所基于的子集和问题进行了更为深入的研究,假设格基归约方法可以求解格中的最短向量问题(格的维数一般小于200),他们的方法适用于所有低密度的背包算法。1988年,Chor和Rivest基于有限域上的运算设计了一种背包密码算法,当参数选取合适时,可以Shamir攻击和低密度攻击。自该算法提出十年来,人们一直认为Chor-Rivest背包算法是安全的,直至1998年,Vaudenay针对Chor-Rivest背包算法通过分析其所基于的有限域的数学特征提出一种代数攻击。由于不存在多项式量子算法求解子集和问题,许多密码学家认为在后量子时代背包算法对于公钥密码学还是有价值的。2000年,Okamoto等人提出量子计算机模型下的背包密码体制。最近,张等人和王等人分别设计了新背包型密码算法和高密度型背包密码算法,可以抵抗Shamir攻击和低密度攻击,这两种背包体制都是基于易解的背包问题设计的,结构简单易于软硬件实现。首先,通过分析文献[120]中选择参数的要求,我们给出一种有效的攻击方法,其基本运算是欧几里德算法或整数分解,由于所分解的数是私钥很小的倍数,因此可以有效地求解出私钥,从而在多项式时间内破解了整个密码算法。其次,针对文献[121]中的高密度型背包体制,通过分析密码体制的公钥分量之间的数学特征,找到该密码体制的私钥-模M,然后在小空间(U或i比特的奇数)内搜索逐一确定其他的私钥,最终计算出所有的私钥。