公钥密码（精选6篇）
公钥密码 篇1
密码技术是保护信息安全的主要手段之一。它不仅具有保证信息机密性的信息加密功能,而且具有数字签名、身份验证、秘密分存、系统安全等功能。因此,使用密码技术不仅可以保证信息的机密性,而且可以保证信息的完整性和确定性,防止信息被篡改、伪造和假冒[1]。
当前最著名、应用最广泛的公钥系统RSA是在1978年在题为《获得数字签名和公开钥密码系统的方法》的论文中提出的。它是一个基于数论的非对称(公开钥)密码体制,是一种分组密码体制。它的安全性是基于大整数素因子分解的困难性,而大整数因子分解问题是数学上的著名难题,至今没有有效的方法予以解决,因此可以确保RSA算法的安全性[2]。RSA系统是公钥系统的最具有典型意义的方法,大多数使用公钥密码进行加密和数字签名的产品和标准使用的都是RSA算法。
2 RSA公钥密码体制简介
2.1 密码体制概述与RSA算法
2.1.1 对称密码体制
对称密码体制是一种传统密码体制,也称为私钥密码体制。在对称加密系统中,加密和解密采用相同的密钥。因为加解密密钥相同,需要通信的双方必须选择和保存他们共同的密钥,各方必须信任对方不会将密钥泄密出去,这样就可以实现数据的机密性和完整性。比较典型的算法有DES(Data Encryption Standard数据加密标准)算法及其变形Triple DES(三重DES),GDES(广义DES);欧洲的IDEA;日本的FEAL N、RC5等。对称密码算法的优点是计算开销小,加密速度快,是目前用于信息加密的主要算法。它的局限性在于它存在着通信的双方之间确保密钥安全交换的问题。另外,由于对称加密系统仅能用于对数据进行加解密处理,提供数据的机密性,不能用于数字签名。因而人们迫切需要寻找新的密码体制。
2.1.2 非对称密码体制
非对称密码体制也叫公钥加密技术,该技术就是针对私钥密码体制的缺陷被提出来的。在公钥加密系统中,加密和解密是相对独立的,加密和解密会使用两把不同的密钥,加密密钥(公开密钥)向公众公开,谁都可以使用,解密密钥(秘密密钥)只有解密人自己知道,非法使用者根据公开的加密密钥无法推算出解密密钥,顾其可称为公钥密码体制。最有影响的公钥密码算法是RSA,它能抵抗到目前为止已知的所有密码攻击。
RSA算法是第一个既能用于数据加密也能用于数字签名的算法,算法的名字以发明者的名字命名。RSA算法的安全性依赖于大数分解问题的难解性。算法中使用的公钥和私钥都是两个大素数(大于100个十进制位)的函数。据猜测,从一个密钥和密文推断出明文的难度等同于分解两个大素数的积[3]。
RSA算法在ISAKMP/Oakley框架中被用做一种可能的身份认证方式。Diffie-Hellman密钥交换算法是ISAKMPIOakley框架的一个关键组成部分。在一个密钥协商会话的开始阶段通信参与方通过使用Diffe-Hellman算法产生双方共享的密钥,这些密钥将被用于密钥协商协议的后续步骤。
在实际应用中,人们通常将对称密钥算法和公钥密码算法结合在一起使用,以实现最佳性能。即使用某个对称密钥密码体制来加密需传递的机要信息,而同时使用RSA等非对称密钥密码体制来传送DES的密钥。这样就可以综合发挥两种密码体制的优势,即DES高速简便性和RSA密钥管理的方便和安全性。
2.2 RSA体制的算法过程
RSA密码体制使用了模n的非负最小完全剩余系中的运算,这里n是两个不同的素数p和q的乘积[3]。RSA体制的算法过程如下:
首先产生密钥,过程如下:
1)随机产生两个长度为K/2位的素数P和Q。
2)计算公钥public Key=P*Q;(public Key是k位的长度)。
3)随机产生一个加密密钥key E,2<=key E<=Φ(n)-1,其中GCD(key E,Φ(n))=1。
注意这是保证解密密钥key E×key D mod(Φ)(n)=1有解的充要条件,Φ(n)称为n的欧拉函数,值为:Φ(n)=(P-1)*(Q-1)。
4)求解解密密钥key D=key E-1 mod(n),key E-1为解密密钥key D的逆元,此公式原方程为(key E×key D mod(n)=1)。
由此公钥,加密密钥和解密密钥全部产生。
其次,对明文加密或对密文进行解密,过程如下:
1)加密:C=Mkey E mod public Key;其中M表示明文,C表示密文。
2)解密:M=Ckey D mod public Key;其中M表示明文,C表示密文。
2.3 RSA体制的实现
RSA密码体制的实现是一个比较复杂的过程,它涉及到素数的产生、大整数模运算等数学运算。RSA体制中,p、q均为大的素数,如何有效地产生大素数将是实现RSA体制所需解决的第一个问题。
通常情况下,人们使用一种概率算法来产生大素数。这是因为p、q都是大素数,如果使用因子分解的办法来求素数p、q,这样的难度与对RSA进行攻击(既分解大合数)实际上是相同的,在计算机是可行的。
概率算法的工作过程一般并不着眼于产生素数,而是首先随机地产生一个大奇数,然后使用概率性算法判定该奇数是否为素数(这样的过程一般称为素性检测)。
2.4 RSA公钥密码体制的优势[4]
1)机密性(Confidentiality):保证非授权人员不能非法获取信息,通过数据加密来实现;
2)确认(Authentication):保证对方属于所声称的实体,通过数字签名来实现;
3)数据完整性(Data integrity):保证信息内容不被篡改,入侵者不可能用假消息代替合法消息,通过数字签名来实现;
4)不可抵赖性(Nonrepudiation):发送者不可能事后否认他发送过消息,消息的接受者可以向中立的第三方证实所指的发送者确实发出了消息,通过数字签名来实现。
可见公钥密码体制系统能够满足网络信息安全的所有主要目标。
3 在ASP.NET中实现RSA加密解密的主要方法[5]
在.Net Framework中提供常用的加密算法类中,支持RSA相关的类主要有两个:RSA类和RSACrypto Service Provider类。RSA类是“表示RSA算法的所有实现均从中继承的基类”,而RSACrypto Service Provider类是“使用加密服务提供程序(CSP)提供的RSA算法的实现执行不对称加密和解密”。另外,“表示RSA算法的标准参数”的RSAParameters结构也是很重要的,它保存了RSA算法的参数。
RSA参数的产生:RSA参数的类型就是上面提到的RSAParameters结构,其包含了D、DP、DQ、Exponent、Inverse Q、Modulus、P、Q八个字段。加密时仅需要Exponent和Modulus两个值,可看成公钥。解密时所有字段都需要,可看成私钥。下面这段程序显示了如何产生RSA两个参数:
RSACrypto Service Provider rsa=new RSACrypto Service Provider();
RSAParameters rsa Params Exclude Private=rsa.Export Parameters(false);
RSAParameters rsa Params Include Private=rsa.Export Parameters(true);
RSACrypto Service Provider类的Export Parameters(bool)方法用于导出RSA参数,true表示导出上述八个字段的“私钥”,false表示导出“公钥”。
使用RSA参数进行加密解密:这一步需要把上面两个参数导入到RSACrypto Service Provider类对象中,再用它对数据进行加密。如下面的代码所示,我们可以写一个函数来完成加密过程:
解密时只要把rsa.Import Parameters(rsa Params Exclude Private)换成rsa.Export Parameters(rsa Params Exclude Private),再把Encrypt换成Decrypt就行了。
保存和加载RSA参数:RSA参数可以保存为XML格式,下面代码说明了如何保存和加载(只列出了关键部分)
保存:
4 结论
RSA公开密钥加密算法发展至今,在电子安全领域的各方面已经形成了较为完备的国际规范。RSA作为最重要的公开密钥算法,在各领域的应用广泛。本文详细论述了RSA公钥体制的算法、安全性以及应用优势,以及利用当前常用的ASP.NET技术,简述设计实现对传输文件的RSA加密解密过程。
摘要：针对当前互联网常用密码安全技术——RSA公钥密码体制,该文简述了其算法原理、优势、安全性,并通过ASP.NET语言设计实现RSA加密解密。
关键词：互联网,RSA加密,解密,ASP.NET
参考文献
[1]杨义先,纽心忻,李名选.网络信息安全与保密[M].北京:北京邮电大学出版社,2001.
[2]辛运炜.密码学算法[M].北京:电子工业出版社,1998.
[3]Douglas R.Stinson.密码学原理与实践[M].北京:电子工业出版社,2003:131-132.
[4]安全技术——RSA公钥密码体制安全性分析.http://jxzhoumin.javaeye.com/blog/196011.
[5]ASP.NET中如何实现RSA加密.http://develop.csai.cn/dotnet_ASP/200812031123051891.htm.
公钥密码 篇2
公钥密码体制能够适应网络的开放性要求, 在数字签名、身份认证、电子支付等协议中具有不可替代的作用。公钥密码体制建立在数论和代数中的一些数学难题的基础上, 算法复杂, 运算效率比较低, 一直制约着公钥密码体制的发展, 如何快速实现公钥密码算法已成为密码学界普遍关注的问题。模运算在公钥密码算法中使用广泛, 如RSA[1]、DSA[2]以及椭圆曲线[3]等公钥密码算法中, 均需用到模运算。模运算是公钥密码算法中最基本的、使用频率最高的运算之一, 而除法运算是模运算的主要前提, 因此除法运算也是公钥密码学中的基本运算。除法运算的效率是影响公钥密码算法效率提高的关键因素之一, 提高大数除法的算法效率在公钥密码体系中具有重大意义, 也一直是密码学领域中关注的课题[4,5,6,7,8,9]。本文通过建立预处理表, 有效地减少了试除法过程中大数乘法次数, 提出了一种快速实现大数除法的方法。相对于普通的试商法, 改进后的算法时间复杂度降低到O (n) 。
1改进的大数相除算法
1.1预备知识
常用的大数相除法主要有:求倒数法 (牛顿迭代法) 、改进的求倒数法和试除法。前两种算法对于得到的商值精确度不如第三种方法, 并且不能同时得到余数。下面回顾一下这三种方法。
1) 求倒数法
用求倒数法[10]实现大数除法的思想是将除式X/Y化为的形式, 故可先求出Y的倒数1/Y, 再与X做乘积即可得到商值。求倒数可用牛顿迭代法, 牛顿迭代法是将非线性方程线性化, 从而得到迭代序列的一种方法。
对于方程f (x) =0, 设x0为它的一个近似根, 则函数f (x) 在x0附近截取泰勒多项式展开的线性部分, 作为非线性方程f (x) =0的近似方程, 即泰勒展开式的前两项:
则f (x) =0转化成f (x0) +f' (x0) (x-x0) =0, 这是一个线性方程。
设f' (x0) ≠0, 则有:
取x作为原方程新的近似根x1, 再代入方程, 如此反复, 得到迭代公式:
对于求除数Y的倒数, 构造非线性方程其中x为除数Y的倒数, 把f (x) =0代入牛顿迭代序列式 (3) 得到求倒数的牛顿迭代公式:
其中xn为第n次迭代的近似根, 迭代次数越多, 精度越高。
牛顿迭代法求倒数, 需要迭代logn次, 对于每一次迭代, 需要进行两次移位和两次乘法, 算法时间复杂度为O (nlog2n) 。
2) 改进的求倒数法
牛顿迭代法是局部收敛的, 对初值的要求是苛刻的, 若初值不在局部收敛的邻域内, 则难保证迭代的收敛性, 而在实际应用中, 往往很难给出与准确值充分接近的初值。针对这个问题, 可对牛顿迭代法求倒数进行改进[11]。改进算法的思想是将除式X/Y化为的形式, 根据分子分母同乘一个不为0的数, 商不变的性质, 对分母迭代变换, 使得分母的值趋向于1。在对分母进行迭代变换的同时, 对分子做相同的变换, 分母越趋近于1, 分子越趋近于商值。分母的迭代方法如下:
观察函数f (x) =x (2-x) , x∈ (0, 1) , f (x) 在其定义域内单调递增, 且随着x的增长趋近于1。将分母乘以一个常数a, 使得a Y∈ (0, 1) , 令x0=a Y, 将x0代入方程, 得x1, 再将x1作为原来的分母的值, 再代入方程, 如此反复, 得迭代公式:
由于每次迭代过程中仍然需要两次移位和两次乘法, 因此, 时间复杂度仍为O (nlog2n) 。
3) 试除法
相对于传统的除法运算思想, 我们往往进行估商运算。设两个大数X和Y, 其中, X的位数为m, Y的位数为n, 且X>Y, 所求X/Y。取X的高n位, 与Y作比较, 试除, 然后相减移位, 依次类推, 得最后的商值。算法步骤如下:
其中, result[i]存放每次试除的商值, Result对所得出的各个商值进行整合, 得到最后的商值;temp存放依次试出来的商;X'存放每次被除数与商和除数乘积的差值;Mod存放最后得到的余数。该算法需要多次试商移位运算, 从而需要大量的大数相乘和移位, 其时间复杂度为O (n2) [12]。
1.2本文算法改进思想
本文主要从两方面着手来提高算法的效率:一方面, 通过构建预处理表减少大数相乘的次数;另一方面, 采用窗口滑动方法提高大数相减的效率。
在普通的除法中, 要不断进行试商, 做乘法, 再比较做检验。然而, 对于公钥密码学中要求的位数较大的整数, 这种方法实行起来效率太低, 直接影响到加密算法的实现效率。通过观察, 试商过程中所做的乘法基本都是除数重复与1-9所做的乘法运算, 为了减少试商过程中不必要的乘法运算次数, 提高算法的整体效率, 本文主要对乘法做预处理如下:
建立一个二维预处理表Table[10][2], Table[i][0] (其中i值为0-9) 中存储的是0-9, 即为按位取商时提供方便。Table[0][1]和Table[1][1]分别存放0值和除数的值, Table[2][1]-Table[9][1]依次赋值为2-9和除数的乘积, 然后每次试商的时候直接进行查表比较即可得到相应的商值。使用该算法, 只需进行比较, 不需重复地做乘法, 就可得出相应的商值, 大大减少了大数相乘的次数, 提高了算法效率。
在大数除法中, 尽管预处理方法减少了乘法的次数, 但仍需要用到大量的减法运算, 故提高减法的效率对于大数除法也具有重要的意义。任何一个可计算问题的求解时间都与其规模有关, 规模越小, 所需的求解时间也就越少。针对这一思想, 文章采用窗口滑动的方法[13,14,15], 被减数分解成m个独立的整数组合, 即X=x[m-1]x[m-2]…x[1]x[0], 把大整数按位分解到窗口中, 进行窗口滑动求解。
设减式X-Y, 其中X, Y的长度分别为m, n, 且m>n。首先, 取被除数高n位x[m-1]x[m-2]…x[m-n]放入窗口中, 与除数做除法, 即根据Table表中预先存储的除数与0-9的乘积作比较, 记录相应的商值, 同时, 用除数与查询的乘积做减法, 完成该次减法后将窗口向下滑动一位, 即被除数的第x[m- (n+1) ]位落入窗口中, 若此状态时窗口中的值小于除数, 即在该位商0, 并将窗口继续向后滑动, 直至窗口内的值大于除数时, 再在Table表中查询相应商值。不断重复上述过程, 即逐位向后滑动窗口, 查询预处理表直至被除数的最后一位。
算法步骤如下:
其中, Table[10][2]为预处理表, 分别存放的除数与0-9的乘积;X'存放每次被除数与商和除数乘积的差值;result[i]存放每次试商的结果;Result存放由result[i]整合的最终商值;Mod存放余数。该算法中, 只需进行查表操作, 即可得到相应的商值, 之后只需进行相减移位即可, 该算法的时间复杂度为O (n) 。
2算法的分析与比较
2.1复杂度的比较
通过对以上部分的复杂度分析, 可得到上面提到的几种算法的复杂度比较表 (如表1所示) 。
由表1, 可明显看出, 改进后的算法时间复杂度最低, 占用空间最多。这是因为, 本文方法做了预处理, 需要存储预处理表, 占据一定的空间, 以牺牲空间为代价, 赢取了时间。本文的核心思想为以空间换取时间, 如今计算机硬件迅速发展, 为本文改进算法的实现提供了可行性条件。
2.2算法实现时间的比较
针对所提出的改进的算法, 进行了实验验证。实验使用Java编程语言[16], 对改进的大数相除算法进行了实现, 计算机配置如下:
以下是对普通算法和改进后的算法进行实验实现, 分别对操作位数为100, 200, 500, 800, 1 000, 1 500, 2 000, 2 500, 3 000时的运行时间做详细记录, 并对每种规模的操作数随机抽取其中的10组数据求取时间平均值, 得到算法运行位数—时间表 (如表2所示) 。
由表2可以看出, 改进算法的运行时间明显低于普通除法的运算时间。其中, 普通除法随着位数的增大运行时间增长迅速, 尤其在位数达到1 000位以上, 时间增长更加明显。对于各个位数阶段的数据, 改进的算法相比普通除法的效率都有所提高, 并且当位数大于1 500位, 提高的倍数可达到100倍以上。由于普通算法运行时间的数量级变化较大, 不便将其数据和改进算法的数据显示在同一图示中, 所以只根据表2中位数在1 000位以内的算法运行时间数据, 使用Matlab作图[17], 得到图1所示的时间比较。
由图1可明显看出, 在误差范围内, 普通算法的位数—时间函数随着位数的增长基本呈幂函数趋势增长, 而改进的算法的位数—时间函数随着位数的增长基本呈对数函数增长。从整体来看, 即随着位数的增长, 普通算法的时间增长速率逐渐变大, 改进算法的时间增长率越来越小。
实验结果表明, 位数越大, 改进后的算法效率越高, 越能体现出用预处理法来实现大数除法的优势, 充分证明改进的大数除法的高效性和可用性。
3算法在RSA加解密算法中的应用
3.1 RSA加解密算法的基本过程
(1) 独立选取保密大素数p和q, 并计算n=p×q, φ (n) = (p-1) (q-1) , n与φ (n) 均需保密;
(2) 通过gcd (e, φ (n) ) =1来随机选取加密密钥e, 1≤e≤φ (n) , e是公开的;
(3) 通过ed≡1modφ (n) 来计算解密密钥d, d是保密的。
以下分别为加、解密过程, 其中m为明文, c为密文。
加密:c=Ek (m) =memodn;
解密:m=Dk (c) =cdmodn。
3.2大数除法在RSA算法中应用及分析
根据3.1节可知RSA加、解密过程中用到大数的加、减、乘、除、模等运算。其中, (1) 中判断大素数一般使用拉宾米勒算法; (2) 与 (3) 中计算最大公约数和解密密钥过程是使用辗转相除法;加、解密过程使用大数模幂运算, 而模幂运算过程可以逐步分解为:模幂→模乘→模运算→除法运算。
由以上分析可看出整个RSA加、解密过程中需要多次用到大数除法运算。经实验结果可得, 改进后的大整数除法运算效率有很显著的提高, 从而提高RSA算法效率。
4结语
公钥密码RSA体制及安全性分析 篇3
公钥密码[1]是1976年提出的一类新的密码体制,公钥密码体制RSA[2]是1977年由美国麻省理工学院的Ron Rivest,Adi Shamir和Len Adleman在题为《获得数字签名和公开密钥密码系统的方法》的论文中提出的。RSA是一个基于数论的非对称密码体制,其名称来自于三位科学家的姓名首字母。RSA算法是和一个能同时用于数据加密和数字签名的算法,是公钥密码体制中最优秀、影响最大的加密算法。RSA的安全性是基于大整数素因子分解的困难性,在理论上一直未能得到证明。RSA经历了各种攻击,至今未能被完全攻破。
1 RSA 算法及分析
1.1 RSA算法描述
(1)找到2个大素数p,q。
(2)做乘法:n=pq;欧拉函数值φ(n)=(p-1)(q-1)。
(3)随机选取加密密钥e,满足gcd(e,(p-1)(q-1))=1。
(4)满足ed≡1mod(p-1)(q-1),则d=e-1mod((p-1)(q-1))。
(5)d和n互素。公钥是(n,e),私钥是(n,d)。
(6)两个素数p和q销毁(保密,不能泄露出去)。
1.2 RSA算法分析
加密消息m时,将m看成一个大整数,把其分成比n小的数据分组。按公式加密:
ci=m
解密消息时,取第一个加密后的分组ci并计算式(2):
mi=c
例如:设p=37,q=41(十进制),那么:n=pq=1517,随机选取e=17作为公钥。将n=1517和e=17公开,并对p和q保密。为了得到解密指数,需要找到e=17模(p-1)(q-1)的乘法逆元,于是可以通过使用欧几里得算法得到:
d=e-1mod1517=593
加密消息:m=1234567。
在此例中,按3位数字一分组就可以进行加密:
m1=123;
m2=456;m3=007(不足在左边填充0)。
加密:
12317mod1517=1107=C1;
45617mod1517=1292=C2;
00717mod1517=645=C3;
密文:C=11071292645
解密消息时需要密钥进行相同的指数运算。
如:1107593mod1517=123=m1
消息的其余可用同样的方法恢复出来。
2 几种针对RSA的攻击方法
2.1 RSA的公共模数攻击[3]
为了密钥管理的方便,对一个网络用户群的系统可以选取一个共同的RSA-n密码体制,而不同的人拥有不同的e和d。这样系统的安全性将受到威胁。一般的情况是同一信息用不同的公钥加密,这些公钥共模而且互素,那么该信息无需私钥就可以得到恢复。设m为信息明文,用两个互素的公钥e1,e2加密,公开模数为n,那么就有:
C1=me1modn
C2=me2modn
攻击者知道n,e1,e2,C1和C2,就能得到m。因为e1和e2互素,所以通过欧几里得算法可以知道存在r,s,使得re1+se2=1,且r,s中必有一个是负数,设r>0。再用欧几里得算法计算:
C
则(C
mre1+se2modn=
m
恢复出了明文。
对于RSA的公共模数攻击,解决的办法是不共享n。
2.2 低指数攻击[4]
2.2.1 小加密密钥e攻击
为了提高加密速度,尽量选取较小的加密密钥e。但是如果e选取过小,则系统是不安全的。
例如:对RSA-n,设明文为m,0≤m≺n。如果随机取e过小,则可能有:me≺n。那么C=(memodn)=me,这就是普通的指数,即
所以使用加密指数e=216+1=65537(费马素数!)可以避免一些对小加密密钥e的攻击。
2.2.2 小解密密钥d攻击
1990年Micgael Wiener证明了,若d的长度小于模n长度的
对于低指数攻击,对付的办法就是e和d都取较大的值。
2.3 选择密文攻击[5]
由于RSA密文是通过公开渠道传播的,攻击者可以获取密文。假设攻击者为A,密文收件人为T,A得到了发往T的一份密文c,他想不通过分解质因数的方法得到明文。换句话说,他需要m=cd。
为了恢复m,找一个随机数r,r<n,当然有T的公钥(e,n)。他计算:
x=re%n(用T的公匙加密r)
y=xc%n(将临时密文x与c相乘)
t=r-1%n
A知道RSA具有下面的一个特性:
如果x=re%n,那么r=xd%n
因此他想办法让T对y用T自己的私匙签名(实际上就是把y解密了),然后将结果u=yd%n寄回给A。A只要简单地计算:m=tu%n
上面结论的推导是:
tu%n=r-1yd%n=r-1xdcd%n=cd%n=m
对于选择密文攻击,可以采取的办法有两条:一是采用好的公钥协议,保证工作过程中实体不对其他实体任意产生的信息解密,不对自己一无所知的信息签名;二是决不对陌生人送来的随机文档签名。
3 RSA加密算法的安全性
RSA的安全性基础是数论和计算复杂性理论中的下述论断:求两个大素数的乘积是计算机上容易的,但要分解两个大素数的乘积求出他的素因子在计算上是困难的。在理论上,RSA的安全性取决于分解的困难性,但在数学上至今还未证明分解模就是攻击RSA的最佳方法,也未证明分解大整数就是NP问题,可能有尚未发现的多项式时间分解算法。
下文是几种因数分解的算法:
(1)试探除法,一种最老也是最笨的办法,穷举所有小于sqrt(n)的素数,耗时以指数率增长。
(2)二次筛法,对10110以内的数是最快的算法。
(3)MPQS,QS的改进版本,要快一些。
(4)分区筛法(NFS),目前对大于10110的数是最快的算法。曾被用来成功地分解过第九费马数。这些算法代表了人们对大数分解(也就是对RSA攻击)的探索历程。最好的算法具有超多项式率(次指率)的时间复杂度,NFS具有最接近于多项式率的表现。
但是随着计算机能力的提高和因子分解算法的不断改进,其中计算能力的提高包括由于计算机网络的发展所导致的联网众多计算机进行分布式计算能力的大力提高,将会对RSA的安全性造成较大威胁。
4 结束语
RSA算法是第一个同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛、最优秀的公钥方案之一。专家指出,就目前的计算机水平用1024-BITS的密钥是安全的,2048-BITS是绝对安全的。但是他们并不指望这个局面延续到下世纪,他们只是指出:如果RSA像有些人说的那样脆弱,就不可能从1978年一直保持到现在还没有被攻破。
摘要：RSA算法是一种公钥密码算法。RSA是一个基于数论的非对称密码体制,RSA的安全性是依赖于大整数素因子分解的困难性问题。其经历了各种攻击,至今未能被完全攻破。
关键词：公钥密码,RSA算法,加密,解密,安全性
参考文献
[1]Diffie W,Hellman M.A New Direction in Cryptography[J].IEEETrans on Info.Theory,1976,22(6):644-654.
[2]Rivest R L,Shamir A,Adleman L.A Method for Obtaining DigitalSignatures and Public-key Cyptosystem[J].Comm ACM,1978,21(2):120-126.
[3]Delaurentis J M.A Further Weakness in the Common Modulus Proto-col for the RSA Cryptosystem[J].Cryptologia,1984,8(3):253-259.
[4][美]Paul garrett.密码学导引[M].吴世忠,译.北京:机械工业出版社,2003.
公钥密码 篇4
密码学一直应用在社会的各个领域, 如军事、情报等。今天, 随着人们对于安全越来越重视, 密码学更是得到了前所未有的发展。众多类型的工作岗位, 如银行、证券、政府等都要求员工有相当程度的信息安全知识, 高等院校因此纷纷开设了密码学相关课程[1,2]。
在高职院校密码学课程的教学过程中, 常用的教学方法包括:讲授法、演示教学法、项目任务教学法、案例教学法等。教师可以根据实际情况采用多种方法进行教学, 但普遍存在的情况是教师在进行课程设计时无从下手。
2、基于RSA算法的公钥密码教学方法依据
公钥密码是现代密码学的重要分支, 自从1976年由Whitefield Diffie和Martin Hellman提出可以用陷门单向函数理解公钥密码的构造以来即得到很大发展。但是公钥密码技术大都基于复杂的数学难题, 如陷门单向函数等。其中包含的算法也涉及到大数分解、离散对数等数学问题, 相关的数学理论公式繁多, 比较难以理解, 对于数学基础一般的学生更是挑战。
将上述数学理论加入到常见公钥密码算法之后反而有较快速的理解方式。由于RSA算法的广泛应用以及该算法与后续数字签名课程的联系, 我们采用RSA算法进行公钥密码教学方法的设计。
3、基于RSA算法的公钥密码教学方法示例
RSA公钥密码算法的命名取自三个创始人:Rivest、Shamir和Adelman于1977年开发的第一个公钥密码算法。它是一种公认十分安全的算法, 也是目前网络上进行保密通信和数字签名的最有效的安全算法[3]。
3.1、RSA密钥生成算法
(1) 生成两个大素数p和q, 为了获得最大程度的安全性, p和q的长度最好一样;
(2) 计算p和q的乘积:n=p*q;
(3) 计算n的欧拉函数Ф (n) = (p-1) (q-1) ;
(4) 选取一个随机数a满足1<a<Ф (n) , 并且gcd (a, Ф (n) ) =1;
(5) 计算a的乘法逆元b=e-1modФ (n) ;
(6) 公钥PK= (a, n) , 私钥SK= (b, p, q) 。
3.2、RSA加密和解密算法
设m为要传送的明文, c为加密后的密文, RSA的加解密过程:
(1) 加密:利用公开密钥 (a, n) 加密, c=E (m) =memod (n) ;
(2) 解密:利用私有密钥 (b, p, q) 解密, m=D (c) =cbmod (n) , 其中E和D互为逆运算。
RSA算法的安全性主要依赖于大整数分解的困难性。从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。因子分解越困难, 密码就越难以破译, 加密强度就越高。所以, RSA需采用足够大的整数密钥。现有的整数分解方法如Pollard法、二次筛选法、随机平方法等分解1024位以上的大整数仍然比较困难, 因此采用1024位以上密钥时可以认为是安全的。
3.3、RSA加解密举例:
a) 选取p=11, q=13。则n=p*q=143。Ф (n) = (p-1) * (q-1) =10*12=120;
b) 选取a=17 (大于p和q的质数) , 计算其逆, b=17142 mod 143=113。
c) 那么公钥PK为 (143, 17) , 私钥SK为 (143, 113) 。
3.4、教学实践
除去基本原理的讲述, 设计一个简单的实践项目也十分必要。由于学习密码学的学生往往已经具备了一定的编程能力, 因此可以设计一个文本文件加密系统的项目, 要求学生编写一段代码, 对已有的文本文件进行加密, 实现RSA算法的基本功能, 既能够让学生进一步了解算法的原理, 又没有很高的编程要求, 还能够锻炼学生的动手能力, 编写出来的程序也具有一定的实际应用范围。
3.5、考核
公钥密码教学的最终考核由平时成绩和实践项目的完成情况两部分组成, 在实践项目上欢迎学生用多种方法完成加密系统的设计并鼓励创新。考核部分能够做到因材施教, 全面评价各类学生。
4、教学方法总结
采用基于RSA算法的教学方法目的在于提高学生对于涉及复杂数学问题的公钥密码技术的兴趣和理解能力。近几年在密码学课程中采用该教学方法后, 学生反映良好, 在评教活动中亦获得了较高的分数, 在国家级、省级各类信息安全相关比赛中成绩排名有所提高。因此, 可以认为本文研究的教学方法在实践中能够收到良好的效果。
摘要：根据多年的密码学教学经验, 提出一种基于RSA算法的公钥密码教学方法。该方法从公钥密码的运行原理出发, 对RSA算法进行了深入剖析, 并给出相关安全性验证。该方法可以让学生快速进入学习公钥密码的大门。
关键词：RSA算法,公钥密码,教学方法
参考文献
[1]胡小明, 杨寅春, 吴秀梅等.信息安全专业密码学课程教学改革[J], 计算机教育, 2014 (1) :49-52.
[2]李素娟.《密码学》课程教学方法和设计的探索[J], 无锡职业技术学院学报, 2010, 9 (1) :77-79.
公钥密码 篇5
从1978年Mc Eliece[1]提出M公钥密码体制以来,基于纠错码的公钥密码体制引起了广大学者的高度重视。1986年,Niderreiter[2]又提出N公钥体制。传统的M体制和N体制是以Goppa码为基础的,加解密简单,安全性高,但是存在公钥量大,传信率低等弱点,因此很少在实际中应用。随着纠错码的发展,用除Goppa码外的其他高性能纠错码,如BCH码,RS码,秩距离码,代数几何码及LDPC码等不同的码类构造公钥体制成为许多学者研究的主要内容,极大地促进了基于纠错码的公钥密码体制的发展。随着计算机水平的提高,传统的单公钥密码体制已经不再满足安全性需求。2008年,岳殿武、 张颖等人[3]利用双公钥对基于代数几何码的M公钥密码体制进行改进,提高了密码体制的安全性。2010年,杜伟章、杨磊鑫等人[4]也利用双公钥对传统的N公钥密码体制进行改进,增加解密复杂度, 提高了安全性。另一方面,在复杂环境下,实际传输信道中产生的错误一般是突发错误或者是突发错误和随机错误并存。尤其是在复杂环境的高速移动无线电波传输下,反射、绕射和障碍物的吸收都会使信号发生多径衰落,导致接收端收到数据可靠性下降。 此外,大部分纠错码都是在编码较长的时候能够有很好的性能,例如LDPC码,码长越长,越能够体现出其巨大的优势,然而在许多时候,例如对空传输控制指令,通信系统传输的编码都较短,RS码是通信系统中比较常用的码类,具有很强的纠正短突发错误的能力,构造简单,容易实现,尤其适合编码较短的情况。根据以上特点,本文提出基于RS的双公钥Niderreiter密码体制,既提高了纠错能力,又适合在编码较短的情况使用,且易于工程实现,在山峰、 海面等复杂环境下实用性较高,且安全性较传统的基于纠错码的公钥密码体制高。
1基本概念
1.1N公钥密码体制
设G为GF( 2) 上的( n,k,l) 二元既约Goppa码的k × n阶生成矩阵,设H为 ( n - k) × n阶一致校验矩阵,S是 ( n - k) × ( n - k) 阶可逆矩阵,P是n × n阶置换矩阵,计算H' = SHP ,令公钥为H' ,私钥为S、H、P ,明文m是GF( 2) 上长为n的比特向量,密文c是GF( 2) 上长为n - k的比特向量。
加密算法:
集合M是由GF ( 2 ) 上所有汉明重量等于t的n维矢量构成,。 而c与m实质上就是伴随式与错误图样的关系,且码能纠t个错误,因此, c与m之间必然存在一一映射关系,从而保证解密唯一性 。
解密算法:
1计算c ( ST)-1= m PTHT;
2利用Goppa码的快速译码算法对m PTHT进行快速译码,得到m PT,计算m PT( PT)-1,恢复明文m 。
目前,对于N体制最有效的攻击方法是解线性方程组,攻击式 ( 1 ) 的工作因 子为WN= ( n - k)3Ckn/ Ckn - t。设n = 1024 ,k = 1024 - 10t ,当t = 41时,N体制具有最高安全性,最高工作因子为WN= 282。传统N体制的加密、解密实际上是进行Goppa码的译码,根据Goppa码的快速译码算法,其计算复杂度为O( n log2n) 。N体制的公钥量是 ( n k) × n ,传信率是 ( log2Ctn) /( n - k) 。当n = 1024, t = 41时,N体制公钥量为42万比特,传信率为0. 59,由此可知,N体制公钥量较大,而传信率较小。 根据工作因子、公钥量及传信率随t的变化关系,在N体制中,t应该选用小的。
综上所述,虽然传统N体制的加解密有Goppa码的快速译码算法,计算复杂度较小,但是由于公钥量较大,传信率较低,不宜投入工程应用。
1. 2 RS 码
RS码,Reed-Solomon codes,由Irving Reed和Gus Solomon两人[5]于1960年首次提出,是一类具有很强突发性错误处理能力的多进制BCH码,在卫星通信、磁记录系统及数字电视传输等领域得到广泛应用。
RS码是q进制的BCH码 ,q = 2m,即每个q进制码元均可以表示成为m比特。每个码元取值为q元符号集 {0,α0,α1,…,αq -2} ,实际情况通常取q = 2m,使得q元符号集的非零元素 { α0,α1,…,αq -2} 是GF( 2m) 上的元素。一个可以纠正任意小于或者等于t个错误的RS码基本参数如下:
码长: n = q - 1;
校验位长: r = n - k = 2t ;
最小距离: d = n - k + 1 ;
生成多项式:
生成矩阵: G = [IkQk × r];
校验矩阵: H = [(Qk ×r)T,Ir]。
RS码的译码与其他线性分组码基本一致,分为三个步骤:
1根据接收到的码字计算伴随式S ;
2根据伴随式得到错误图样E ;
3根据接收码字与错误图样进行纠错计算,完成译码。
如果传输的信号是二元数据流,则连续m比特表示一个码元。由于任何少于m比特的差错都可能造成一个或者连续两个码元错误,所以RS码虽然能够纠正t个码元,但是只能够纠正任意连续 ( t - 1) m + 1个比特错误。根据这一特性,RS码成为二元信号传输中纠正短突发错误的首选纠错码之一。
2基于RS码的双公钥Niderreiter密码体制构建
根据RS码的特点,构建基于RS码的双公钥Niderreiter密码体制。密码体制流程如图1所示。
其中,公钥分别为Pk1和Pk2 ,Pk1 ,Pk1的私钥为Sk1 ,Pk2的私钥为Sk2 。
2.1参数设计
设多元 ( n1,k1,t1) 码C1和 ( n2,k2,t2) 码C2是GF( 2q) 上的RS码,n2= n1- k1,其生成矩阵G1、G2阶数分别为k1× n1,k2× n2,校验矩阵H1、H2阶数分别为 ( n1- k1) × n1,( n2- k2) × n2,纠错能力分别为。 在GF ( 2q) 上随机选取阶非奇异矩阵S1和阶非奇异矩阵S2,在GF ( 2 ) 上随机选取n1× n1阶可逆置换矩阵P1和n2× n2阶可逆置换矩阵P2,将两个矩阵中的 “1” 元素随机转换成多元域中非零的其他任意元素 。
计算
其中,H'1和H'2分别采用P1和P2替代传统N公钥密码体制中的置换矩阵,使得相同参数的P1和P2都增加至 ( 2m- 1)nn! 种,可以提高该体制的安全性。
最后可得参数如下:
公钥: H'1,H'2;
私钥: S1,H1,P1,S2,H2,P2,q 。
2.2加密算法
计算
其中,m为n1维明文向量,c1为 ( n1- k1) 维向量;
计算
其中,c2为 ( n2- k2) 维密文向量。
c2与m的关系,实质上是伴随式和错误图样的关系,因为该码能对t = min{ t1,t2} 个错误进行纠错,所以c2与m之间必定存在一一映射关系,从而保证解密唯一性。
2.3解密算法
当收到密文c2之后,通过以下步骤进行解密计算得到明文m :
1计算c2( S2T)-1,c2( S2T)-1= c1( P2TH2TS2T) ( S2T)-1= c1P2TH2T,通过RS码的快速译码算法对伴随式c2( S2T)-1进行译码,可以得到c1P2T。
2右乘 ( P2T)-1,计算c1P2T( P2T)-1得到c1。
3计算c1( S1T)-1,c1( S1T)-1= m H'1T( S1T)-1= m P1TH1TS1T( S1T)-1= m P1TH1T,通过RS码的快速译码算法对伴随式c1( S1T)-1进行译码,可以得到m P1T。
4右乘 ( P1T)-1,计算m P1T( P1T)-1,恢复明文m。
3安全性分析
经过双重RS码编码加密,体制安全性较传统的基于纠错码的公钥密码体制有了明显的提高。密码分析者进行分析需要的工作量接近于一次RS码加密的两倍。
现对该密码体制就可能的密码分析手段进行安全分析。
3.1直接译码攻击
c2与H'2、c1与H'1本质上就是伴随式与错误图样的关系。直接解方程( 4) 和( 5) ,就可以求出明文m 。但是,根据纠错码理论可知,一般线性码的最大似然译码是NPC问题,进而可以得出上述求解也为NPC问题,故该攻击方法不成立。
3.2直接解方程组
分析该密码体制最为常见的分析手段就是解线性方程组。与原始的分析N体制的方法不同,该方法需要分成两个步骤进行分析。
Step1:
设c2对应明文m = ( m1,m2,…,mn) ,令
设公钥分别为
式中,h'i和h″i分别为H'1和H'2的第i列,且
则有:
Step2:
在上述结果的基础上,分析方法类似,删除的分量数目为k1,最后解方程求得明文m 。
根据此密码分析方法,在Step1中解方程的工作因子为,密码分析者选取的概率为,因此在Step1中密码分析者分析 该体制的 工作因子 为; 同理,在Step2中密码分析者 分析该体 制的工作 因子为综上所述,通过该方法进行密码分析 的工作因 子为。 该工作因 子不是多项式时间,该密码分析算法不可行 。
3.3RS码码字特点攻击
相对于传统的基于Goppa码的M体制和N体制而言,采取RS码的N体制在相同参数的条件下的码字数目远远低于前者,密码分析者很容易猜出体制的私钥H1,也就是说,该方案以RS码为外码的安全性关键在于猜出一致性校验矩阵H1之后通过H'1分解出S1和P1的难度。文献[5]证明M体制在泄露私钥生成矩阵G的前提下仍然难以分解出S和P ,其难点在于求解二次非线性方程组的算法。同理,在N体制中,根据置换矩阵PT= P-1的特点,令H' = SHP ,则,则:
该问题转化为已知求解S的问题,一旦S被求解, P也可求解 。
将式( 6) 展开,化为n( n - k) 个联立的( n - k)2元二次非线性方程组。该问题最终转化成求解二次非线性方程组的问题。虽然目前没有求解二次非线性方程组的有效算法,但是一旦找到该算法,体制安全性将不复存在。因此,本方案将置换矩阵P1中的 “1”元素随机转换成多元域中其他非零元素,使得P1T≠ P1-1,此时矩阵分解问题再不能转化为求解二次非线性方程组问题,即使求解二次非线性方程组的算法被找到,在本方案中也不能从H'1中分解出S1和P1,且本方案是基于RS码的双公钥密码体制,公钥密码体制的安全性显著提高。
4性能分析
RS码是通信系统中常用的信道编码,构造简单,纠错能力尤其是纠正短突发错误的能力极强,尤其适合长度较短的编码。对于通信传输编码较短的信道,例如对空传输控制指令,遥控数据量较小,对纠错能力要求较高,尤其适合基于RS码的双公钥密码体制。该公钥密码体制的公钥量为 ( n1- k1) × n1+ ( n2- k2) × n2,纠错能力为t = min{ t1,t2} ,传信率为,公钥量为107400比特, R =0. 6217 。 显然,随着t的增加,该双公钥密码体制的公钥量增加 。 图1为当n1= 1024 , n2= 100时该双公钥N密码体制的传信率R随t的变化关系 。
从图2可得,随着纠错能力的提高,该密码体制的传信率降低。表1为不同的公钥密码体制的性能比较。
可以看出,与传统基于纠错码的公钥密码体制相比,该密码体制公钥量有所增加,但是在安全性有所提高的前提下,传信率也显著提高,尤其适合在通信编码较短或者环境较为复杂恶劣的情况下。
5结束语
纠错与加密结合,尤其是双公钥加密,对复杂环境下的密码系统是相当有意义的。根据信道传输编码的特点,选择合适的纠错码构建公钥密码体制,使得纠错能力、实用性、安全性都能得到兼顾。本文提出了基于RS码构建双公钥Niderreiter密码体制,克服了传统基于纠错码的公钥密码体制传信率低、实用性不强等弱点,可靠性和安全性较高,能够良好地适应编码长度较短的信道。在信道编码长度较短的情况下,该公钥密码体制一定能发挥重要的作用。
摘要：首先简要介绍了N公钥密码体制、RS码的基本概念,然后针对通信信道编码较短的情况提出了基于RS码的双公钥Niderreiter密码体制,最后对这种密码体制的安全性和性能进行了详细分析,证明了其安全性和性能要优于传统的基于纠错码的公钥密码体制,在复杂环境或者信道编码较短情况下的实用性也较高。
公钥密码 篇6
(1)密钥生成算法
选择两个参数(r,s)满足r
上式中X是公钥(r,s)是私钥。并且对(p,q)进行保密。
(2)加密生成算法
这里m是明文,C是密文,k是随机数,n=pq.其思想是将明文和公钥以及随机数结合在一起形成一个乱码的密文。
(3)解密生成算法
首先读出保密口令(p,q)通过密文C和(p,q)可以算出两个中间变量C1,C2方法是:
通过公式⑷可以进一步得到:
根据公式⑸通过选取一定的参数m,k使得
进一步得到:
因此由公式⑹和公式⑺得到明文:
其中(r-s)(r-s)-1≡1(mod p)。
(4)当明文比较长的时候其改进的新型公钥密码算法如下:
根据公式⑴、⑵获得X后,令
将Y作为公钥公布出去。
加密过程改为
解密时首先通过根据p从密文C中算出中间量CC,即
在将式⑾和式⑿联立便可得到
由式⒀可以立即求得
上述算法充分利用了NTRU的优点,速度快、所需存储少,实用性强。但是当随机数k较短时,可以利用格攻击[3]来恢复密文中的明文;当明文长度较长时,根据公式(10)中的公钥Y利用欧几里德定理可以成功分解其私钥,从而逆推出明文。因此上述方案是不安全的。下面我们利用格理论对该算法进行详细分析。
1 基本知识
1.1 LLL算法[4]的基本知识
格上的难题可以用于构建新型的密码方案,而格基规约理论则是密码分析[5]中的一个重要工具。一个格可以用不同的基来表示,在解决格上相关问题时,即使同一个算法,如果选择不同的基作为输入,算法实际运行的时间以及其结果有可能不同,所以有必要研究如何去找到有利于解决问题的那一组基,这种寻找基的过程称为格基规约,并且称找到的一组基为格的一组规约基。最常用的寻找规约基的独立算法就是LLL算法[2]其基本的算法描述为:
n维Rn空间的子集合。
其中R为实数集合,Z为整数集合,称L为格。b1,b2,…,bn∈Rn为格L的一组基,n是格L的秩。任给n个线性无关的向量b1,b2,…,bn∈Rn可使用Schmidt正交化过程获得一组两两正交的向量,我们可以用这种方法来构造格L的一组基:b*1,b*2,…,b*n其中
令如果格L的一组基b1,b2,…,bn∈Rn同时满足公式(15)与公式(16)所给定的两个条件:
则称b1,b2,…,bn∈Rn为格L的一组归约基。而格基约简算法就是通过b1,b2,…,bn。L3逐步构造一组归约基b1*,b2*,b3*,…bn*。
通过大量的实验表明当格维数小于300的时候,现有的格规约算法在应用实践上要比理论论证效果好得多,因此在低维格的情形下使用格规约算法得到的基可以更加接近实际值。在这种情况下,格基规约算法可以抽象成一个格预言机,该预言机能够输出最短向量问题和最近向量问题的一个解,当格的维数大于500的时候,现有的格规约算法对最短向量问题和最近向量问题就无法解决。
1.2 背包问题和背包密码的数学描述
给定n个正整数的集合B={a1,a2,a3,a4,…,an}及正整数C,求0、1向量x=(x1,x2,…,xn)使得
其中a=(a1x1,a2x2,…,anxn)称为背包向量。
说明:C表示背包的大小,每个数字ai表示能装到该背包中的物品的大小。
问题的焦点在于如何选择合适的物品,使得它们正好能填满这个背包。若xi为1表示物品在背包中,xi为0表示物品不在背包中。从原则上,我们只要能从集合B中找到一些元素使其和等于C就说明这个背包有解,否则这个背包就没有解。但是我们发现集合B中的子集个数为2n,说明其解的范围比较大,通过上面的式子我们也可以发现由集合B和0,1向量X很容易求出C,但是由C则很难求得0,1向量X,所以背包问题是NP完全问题。我们知道背包密码[6]的设计思想是把一个易解背包问题通过限门函数变换成一个看似困难的问题。限门信息作为私钥仅被合法接收者掌握,运用它可以把该问题恢复成一个易解背包问题,通过该易解背包重构明文;而对非法接收者来说,从密文恢复明文就相当于解一个困难的背包问题。
背包密度[6]是指0-1背包密度,它的定义是公钥序列H=(a1,…,an)n位长的二进制明文(m)2=(m1,…,mi,…,mn)被加密为C=a1m1+…+anmn,其中mi为0或1,背包密度公式为:
1.3 欧几里德算法
欧几里德算法又称为辗转相除法,它是用于计算两个正整数之间的最大公约数的算法。其计算原理是用下面的定理:gcd(A,B)=gcd(B,A mod B)(其中A>B且A mod B不为0)。
证明:若A可以表示成A=k B+r,则r=A mod B。假设D是A,B的一个公约数,则有D|A,D|B,而r=A-k B,因此D|r进一步可以知道D也是(B,A mod B)的公约数。
因此(A,B)和(B,A mod B)的公约数是一样的,所以它们的最大公约数也必然相等,举例如下:
若有两个数8656,7780,我们知道8656=7780*1+876,7780=876*8+772,876=772*1+104,772=104*7+44,104=44*2+16,44=16*2+12,16=12*1+4,12=4*3+0,所以这两个数的最大公约数为4。
2 攻击方法
2.1 安全隐患
公式(3)、公式(7)中当m和k以及s为较小的数时存在安全隐患,可以利用LLL算法来具体的解释其所存在的安全隐患:
假设
一般而言,X和n的二进制长度大体相当,而C是模n的最小非负剩余,因此,y的二进制长度也和m二进制长度大致相当。如果我们把(X,1,n)看做是公钥,把(m,k,y)看做明文,则利用C=m X+k*1+pn来求解m,k,p的问题就可以看做是一个背包问题,这里的C,X n(C是密文,X是公钥,n是大素数)都是已知的。通过ms+k
下面构造格:给定V1,V2,V3四个向量,分别表示为V1=(-C 0 0),V2=(x 1 0),V3=(n 0 1)。由向量的性质知道V1,V2,V3线性无关,通过格的定义以及与格相关的其他定理我们知道这几个向量满足格的构成,所以有这几个行向量的线性组合可以构成一个格V,如公式(20)所示。
3.2算法描述
Step1取格L的一组基
从给定的密文C=m X+k和X(其中密钥X≡r(mod p),X≡s(mod q))选取如下的基来构造格:
V1=(-C 0 0),V2=(x 1 0),V3=(n 0 1)
Step2利用L3-算法求L的规约基B
Step3如果在基B中寻找到如下形式的向量B=(k,m,-y),此时B是格中的最短向量。
数学描述:对V2和V3两个向量分别乘以m和-y,则m V2=(mx,m,0),-pv3=(-yn,0,1),然后把这两个式子加在向量V1上,进一步可以得到向量B=(k,m,-y)。
具体说明:
说明一:由于上述问题可以规约成一个背包问题,在此假设这个一般的背包问题可以被格攻击,通过大量实验证明当背包密度d小于0.9408通过一次格预言机就能由密文得到明文,这里来求解其随机数k长度为多少时是不安全的,采用文献[7]中定理2的方法求解其长度,假设|s|=z(说明||符号表示长度如|s|表示s的长度)我们由公式(19)知道m,y的二进制长度大致一样,进一步可以借助文献[8]中关于背包密码密度的定义来求解,由于知道|X|=|n|=1024,|m|=|y|=512,设|k|=A,则背包密度:
可得近似解(2*512+A)≈<1024+512,即512+A≈<1024,所以可以得到A的长度也不能超过512即k的长度是512,所以当k小于512的时候通过一次格预言机就能由密文得到明文。
说明二:利用格的性质,可以使用LLL格基规约算法来寻找V的一个最短非零向量B,关于B为何就是我们所求的最短向量,可以由Minkowski第一定理知道在上述格V中如果能找到一个向量B,其中向量的范数||L||≤(det L)2/m(det L)1/m(说明m是格的维数)则就说明其是最短的向量,通过观察格V发现它是一个上三角矩阵,所以det A=C,而通过C知道最大长度是1024并且m是3,进一步知道(det L)1/m≈512,而求得的向量B=(km-y)的欧几里德范数与m,k和y的大小大体一致,(由上述说明一,可以知道k,m,y的最大长度不超过512),即它们三个范数长度小于等于格v的范数长度,因此B是格中的最短向量。
2.3 具体格攻击计算实验如下:
使用NTL库验证上述格攻击算法的有效性。下面给出具体参数:取各自参数其最大值范围|p|=512,|q|=1024,|N|=|pq|=1536,背包密度≈0.9408。
q=179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137859
n=2410312426921032588580116606028314112912093247945688951359675039065257391591803200669085024107346049663448766280888004787862416978794958324969612987890788134153724806750933194559712995603183634504187610436683327313684175808590011681696340257898688530199399649883291032131297764514278509658481127525083830938318522200181546789476052751879210967108770791713216311023805153090916587234916313371769110946366661539984666684984497754934975951205740114138562888061729889
m=4432787894794704185685996601283593312347595251497772479538662432953768439971781955975352679150072795486781055738958267793425031004688595644109365792617763
A=[[0 0 0 0]
[-8180105489558735425426815539451805446253724143320571439560363504824172229055579430131843039640726252947908016808916023460811073294956913419955077956204
4432787894794704185685996601283593312347595251497772479538662432953768439971781955975352679150072795486781055738958267793425031004688595644109365792617763
1337869058338824181450960264919485675381607706014254440188995474644912908431568168651963006329061140727173894965082078772748189861796443090351445681761969 0]
[-7393689929277129363210445335585805545025726206144363498942590376484265307343842987660811504246621429020569622777137128719355028533165981617546380922826981
42325839823750311479996144331265334983144549317364767671923535455145224735311756051030326544095129368213886484088801427050167989364067603632484382750028
157260678841980558545352508883636728123061438367866385892816749198242646029385990780635393230834160850966105110060790865132546837099909248258409600951676 0]
[-1253839440050629773237015368083042159831125025988888839979105592359687831631071678354557574317542124315118404653430112269901480822044310923500869030470820
31731056959681323115403933483201578568384837456371328135373225346524447140531832072117984043164922699165222264505301026451164364446878443234515127232985848
-112213717161458508235751109205984191880695358505211407800357236970759646132331525321228762080565603097608368851747607013601518262030499753300743663607013885 0]
2.4 算法改进的安全分析
上述公式(10)中把Y当做公钥公布出来实际上是不安全的,由于Y作为公钥公布出去后,n作为大素数是已知的,这样攻击者可以利用两个已知的参数Y和n,用欧几里德定理分解得到Y=p X和n=pq,进而对Y和n求公约数很容易求出p,由式子n=pq可得q。攻击者求出(p,q)后就很容易推出明文,故其改进方案也是不安全的。
3 结束语
本文对张盈等人提出的一种简单而高效的公钥密码算法方案进行了分析,并从两方面证明了其算法的不安全性。当输入明文比较短且随机数k小于512时,使用LLL算法说明其存在的问题,当输入明文比较长时,欧几里德算法也说明其是不安全的。
摘要：文章对张盈等人提出的一种简单而高效的公钥密码算法进行了分析,发现当随机数k比较短时,使用LLL算法,采取不同参数的格攻击能够恢复密文中的明文;当明文长度较长时,利用欧几里德算法可以成功分解其私钥,从而逆推出明文。因此其方案是不安全的。
关键词：公钥密码体制,算法,密码分析,格攻击,安全
参考文献
[1]Hoffstein J,Pipher J,Silverman J H.NTRU:a new high speed public keycryptosystem[A].Proceedings of Algorithm Number Theory-ANTS III[C].LNCS 1423.Berlin,Springer-Verlag,1998:267-288.
[2]张盈,张磊.一种简单而高效的公钥密码算法[J].网络安全技术与应用,2008(6):87-88.
[3]SHAMIR A.A polynomial-time algorithm for breaking the basicMerkle-Hellman cryptosystem[J].IEEE Trans Trans on InformationThe-ory,1984,30(5):699-704.
[4]A.K.Lenstra,H.W.Lenstra,L.Lovaz,Factoring Polynomials withRationalCoefficients[J].MathematischeAnnalen,1982,261(4):515-534.
[5]WANG B,HU Y.Diophantine approximation attack on a fast public keycryptosystem[A].The 2nd Information Security Practice and Experience.Conference-ISPEC 2006[C].LNCS 3903,Hangzhou.China,Springer,2006:5-32.
[6]章照止.破译一个新的背包公钥密码系统[J].系统科学与数学,1991,11(01):91-96.
[7]于志强,罗世新,徐树民,等.一种简单而高效的公钥密码算法[J].信息安全与通信保密,2008(10):110-112.