RSA算法研究

RSA算法研究（精选8篇）

RSA算法研究 篇1

0 引言

在当今信息社会中, 每天都有大量的加密信息在传输、交换、存储和处理, 一旦密码遭到破解就可能造成信息的丢失、篡改、伪造、假冒以及系统遭受破坏等严重后果, 因此, 如何保证信息的安全传输成为当前信息传输领域的热点问题[1]。W.Diffie和M.E.Hellmam在1976年发表了具有划时代意义的“密码学的新方向”一文, 提出了公钥密码体制思想, 克服了传统对称密码体制的缺点, 为近代密码学的发展指明了方向。它的出现是密码学研究领域中的一项重大突破, 也是现代密码学诞生的标志之一。

本文首先对非对称加密算法RSA的原理和优点进行研究, 然后实现其加密、解密功能。RSA算法在公钥密码体制中占有重要的地位。但该算法所采用的幂乘计算耗时太多, 一直是制约其广泛应用的瓶颈。因此, 为了提高加密和解密速度, 本文提出一种新型的加密算法即基于乘同余对称特性的SMM算法。该算法采用简单的迭代来实现, 不需要幂乘和乘法逆运算, 从而在提高加密解密的速度同时也使得程序设计更简洁紧凑[2,3]。

1 RSA加密算法原理

RSA加密算法的理论基础是一种特殊的可逆模指数运算, 其算法描述[4,5]如下:

(1) 选择两个互异的大质数p和q (p和q必须保密, 一般取1024位) 。

(2) 计算出n=p q, Φ (n) = (p-1) (q-1) 。

(3) 选择一个比n小且与Φ (n) 互质 (没有公因子) 的数e。

(4) 找出一个d, 使得ed-1能够被Φ (n) 整除。其中, ed=1 mod (p-1) (q-1) 。

(5) RSA是一种分组密码系统, 所以公开密钥= (n, e) , 私有密钥= (n, d) 。

其中, n为模数, 通信双方都必须知道, e为加密运算的指数, 发送方需要知道, d为解密运算的指数, 只有接受方才能知道。

将以上过程进一步描述如下:

公开密钥:n=pq (p, q分别为两个互异的大素数) , e与 (p-1) (q-1) 互质。

私有密钥:d=e-1{mod (p-1) (q-1) }。

加密:C=Memod n, 其中M为明文, C为密文。

解密:M=Cd (mod n) 。

若要破译密码必须知道p, q, 即对n作素因子分解, 这在数学上是非常困难的[6]。

2 RSA加密算法的实现

2.1 算法设计流程

RSA算法设计流程如图1所示, 主要采用下述加密/解密变换。

(1) 密钥的产生

a.选择两个保密的大素数p和q。

b.计算n=p q, φ (n) = (p-1) (q-1) , 其中φ (n) 是n的欧拉函数值。

c.选择一个整数e, 满足1

d.计算私钥d, 满足d=l (mod (n) ) /e, d是e在模 (n) 下的乘法逆元。

e.以 (e, n) 为公钥, (d, n) 为密钥, 销毁p, q, φ (n) 。

(2) 加密

加密时首先将明文比特串进行分组, 使得每个分组对应的串在数值上小于N, 即分组的二进制长度小于1 092 N。然后, 对每个明文分组M, 作加密运算。

加密:C=Me (modn) , 其中M为明文, C为密文。

(3) 解密

对密文分组的解密运算为:M=Cd (modn) 。

2.2 RSA加密算法的实现

(1) 生成密钥

随机选择两个大素数p和q, 如果p和q足够大, 那么n=p q就会变的很大, 在理论上因式分解一个大数并准确地分解出p和q是很难实现的。本文随机选择p和q为61和67。根据 (n) = (p-1) (q-1) 可得n的欧拉函数值 (n) 为3960, 如图2所示。

随机数e的选取要满足随机数和欧拉函数最大公约数gcd (e (n) ) =1这个条件。如果e比较大, 加、解密速度变慢, 也不便于存储, 但是太小的e会导致安全性问题。所以限定1

(2) 加密

输入明文, 根据公钥 (e, n) 和公式C=Me (modn) 可得密文。本文选择要加密的明文为1234, 由公式可得密文为2793。根据计算结果可知此加密算法加密所用的时间为2.667 ms。

(3) 解密

输入3调用第三个模块来实现解密功能。RSA加密算法解密所需要的条件是知道密文和私钥, 根据M=Cd (modn) 可得到明文。由计算得到密文为2793, 私钥为233, 所以可解的密文为1234, 从而实现了解密功能。

RSA加密算法的实现过程如图2所示。

大整数因子分解问题向来被数学界视为世界性难题。正是基于这一点, RSA公钥密码体制才能够以其较高的安全性为人们广泛接受[6]。但是RSA公钥密码体制也存在诸多不足之处:加解密算法中涉及大量的数值计算问题导致计算时间开销较大, 在一定程度上限制了其应用范围。且密钥的产生受到素数产生技术的限制, 因而很难做到一次一密。为保证安全性必须选取1024 bits或以上, 但这就使得运算速度较慢, 而且随着大数分解技术的发展, 这个长度还在增加, 不利于数据格式的标准化, 致使其实现的难度增大, 实用性降低[7]。

因此, 如何提高密钥产生技术, 发展更快速、更精确的大素数生成方法, 完善RSA加密算法的大整数模幂乘运算, 设计运算速度更快的求模和求幂算法, 是很有意义的一个探索方向。

3 RSA加密算法的改进及实现

针对RSA加密算法加密速度慢的问题, 经过进一步的研究, 提出了SMM算法[2,3]。SMM (Symmetry of Modulo Multiplication) 算法是利用乘同余对称特性来减少RSA加密计算中乘法和求模运算量的一种快速算法。RSA加密是对明文求幂剩余的过程为:

传统RSA算法是将指数表示成二进制数的形式, 并将幂乘变成一系列乘同余的迭代。SMM算法是在每步迭代中对乘数进行有条件的代换。乘同余和平方剩余的对称性有:

其代换情况如下:如果ai-1表示第i-1步迭代的结果, 则在进行第i步迭代时, 若ai-1或g< (n-1) /2, 则保持原数不变;如果ai-1或g≥ (n-1) /2则使用n-ai或n-g来代替ai-1或g[8,9]。

由于使用SMM方法, 减少了乘法时间和求模运算量, 改进后的RSA加密算法理论上可以使得算法速度得到一定程度的提高。

为了方便将改进前后的算法做比较, 本文随机素数p、q仍选择61和67。根据f (n) = (p-1) (q-1) 可得f (n) 为3960。随机数e选择17, 可得公钥为 (17, 4087) , 私钥为233。改进后的RSA加密算法运行结果如图3所示。与图2对比可知, 相同初始条件下原RSA算法所用的加密时间为2.667 ms, 改进后算法所用的加密时间为1.669 ms, 加密速度提高了约37.4%, 且程序的复杂度也有所降低。

改进后的RSA加密算法可以通过简单的循环迭代完成整个RSA加解密过程, 减少了将十进制数据转化为二进制数组和用扩展的欧几里得算法求乘法逆元这两步, 不仅降低了程序的复杂性, 而且提高了运算的效率。

4 结论

本文针对RSA加密算法时间开销高和程序复杂的缺点, 提出一种基于乘同余特性的SMM加密改进算法, 该改进算法可减少RSA模幂乘运算过程耗时以及提高RSA加解密速度。最后通过改进前后算法的实例对比证明了本文所提改进RSA加密算法的有效性。

参考文献

[1]冯登国, 裴定一.密码学引导[M].北京:科学出版社, 1999:10-13.

[2]兰海兵, 程胜利.RSA算法及其实现技术的改进研究[J].交通与计算机, 2006 (10) :2-6.

[3]许金玲, 唐勇, 杨华玲.动态组合RSA算法[J].计算机工程与设计, 2006 (13) :2452-2456.

[4]R.Schoof.Ell iptic Curves over Finite Field and the Computation of Square Roots Mod P[J].Mathematics of Computation, 1985 (53) :483-494.

[5]胡军.RSA加密算法的研究与实现[D].马鞍山:安徽工业大学, 2010.

[6]李继.ElGamal型数字签名方案及其应用的研究[D].西安:西安电子科技大学, 1999.

[7]杨维忠, 李彤, 郝林.RSA加密体制的安全隐患[J].云南大学学报 (自然科学版) , 2004 (18) :35-38.

[8]陈运.一种组合RSA算法[J].电子科技大学学报, 2010 (19) :116-119.

[9]兰海兵, 程胜利.RSA算法及其实现技术的改进研究[J].交通与计算机, 2006 (10) :2-6.

RSA算法研究 篇2

【摘 要】Zigbee新作为一种新兴的低成本，低功耗，近距离，双向通信网络技术，在物联网飞速发展的进程中得到了广泛的应用。随着应用范围越来越广泛，ZigBee网络的数据安全也变得原来越重要。目前，在ZigBee平台上，尚未有非对称加密算法的相关研究，本文给出了在cc2530平台上，实现RSA算法的过程，并给出了收集的相关运行数据。最后，本文给出了运行的结果和分析数据。

【关键词】通信安全 Zigbee 非对称加密算法 性能分析

引言

基于IEEE 802.15.4无线技术的ZigBee，被广泛应用于工业，家庭，医疗等对数据率和QoS要求不高，但覆盖面积较大的无线通信场合之中。随着基于ZigBee的应用实例越来越多，其数据的安全性也变得越来越重要。作为ZigBee实现方式之一的ZStack虽然自带了一套基于AES128加密解密算法，但在互联网应用之中，普遍认为非对称加密技术比对称加密算法更为优越。所以实现一套基于非对称秘钥的加密算法变得非常具有参考意义。

一、利用RSA算法的加密体系

在cc2530平台上，我们实现了简单的RSA加密解密算法，并根据对于该算法的统计信息，试探性地探讨在ZigBee系列的小型嵌入式芯片上，在不使用协处理器的情况下，RSA算法的性能。整个算法的实现是基于ZStack平台进行的。算法在Windows平台下开发后进行结果验证。最后移植到ZStack平台上进行相关数据的收集。

二、实现过程

为方便对多种加密长度运行结果进行采样，必须将算法实现在长度可变的整形数据结构基础之上。所以在实现过程中，建立了一个长度可变的简易整形数据结构。

由于硬件资源有限，必须在设计和实现上，权衡安全性和性能开销。开销主要分为两方面：占用的内存空间大小及运算时间。

三、内存占用的统计过程及方法

为统计使用内存，对内存分配及释放函数（ZStack上为osal_mem_alloc及osal_mem_free，在Windows下为malloc及free）进行封装。统计整个加密解密过程中，占用内存空间的高峰值，所分配的最大内存块等信息。在PC端运行算法时，由于统计结果小于ZStack预计的动态管理内存的范围32768Bytes[4]，所以直接写入，试运行。但由于频繁地申请和释放用来保存临时结果的内存块，导致内存严重碎片化，致使ZStack无法分配出更大的内存空间而导致算法无法正常进行。所以更改方案为：将表示整数的内存块长度进行统一，并利用对象池技术来复用所分配到的内存块。

在优化的过程中，通过分析对象池所统计的信息，确定了算法分配的最多内存块数量。然后，通过将内存块声明为全局静态变量，来减少调用内存管理功能的开销，以此优化整体性能。最后采用覆盖方法，实现内存块的复用，减少内存空间的占用。

在分配静态内存空间时，需要重新调整XDATA布局。因为动态管理的内存空间是在编译时设定好的，无法在运行时改变 [4]，所以在实现算法过程中，将ZStack代码的OnBoard.h文件中的INT_HEAP_LEN从3027改为2048。以此减少动态管理內存所占用的空间，以增加静态变量所占用空间。

四、运算时间统计过程及方法

运算占用时间，通过在运算前后获得系统时钟（在ZStack上为osal_getSystemClock），计算差值来获得。值得注意的是osal_getSystemClock本身仅仅返回uint32_t类型的， osal_systemClock数值，并不会自动更新系统时钟。所以在每次获得系统时钟之前，必须主动更新系统时钟（即主动调用osalTimeUpdate）。

对于MUC，RSA加密位数不宜过长。初次测试采取很小的64位加密。在节点A对明文进行加密，加密后，发送加密统计信息和密文到节点B。节点B进行解密并对解密过程进行统计，在核对解密结果是否和明文一致后，将核对结果和所有统计信息通过串口发送到PC进行数据处理。

五、算法伪代码

由于被加密的数据长度是不确定的，所以应先对被加密数据进行分块，不满一块的，填零补齐。然后对每块依次进行加密，返回加密数据。

六、生成秘钥

八、解密算法的伪代码

九、运行结果

在实现中，大数的长度是在宏中定义的，为44字节。整个实现中，一共使用了34个大数，总共占用的静态内存空间为34*sizeof（bn），即1496字节。

根据收集到的数据，可以计算出：平均加密耗时为1819.96ms，平均解密耗时为8371.66ms。

十、结论

根据初步收集的数据，在加密位数很低的情况下（相对于普遍使用的1024位加密解密而言），耗时过长。由于cc2530附带AES协处理器，所以，对比于AES128的100ms以下的耗时[1]，RSA算法在没有协处理器的情况下，不宜在8051芯片上进行大量数值计算的应用意义并不是很大。虽然cc2530使用的是加强的8051微处理器，但在计算性能上仍有所欠缺。

在实际应用中，应对较短的数据（如秘钥）进行RSA加密解密操作。或在计算能力更强的芯片上运算，然后由cc2530进行数据传输。

加强ZigBee对于非对称加密算法支持程度，引入协处理器，将会称为一种较为可取的解决方案。

参考文献：

[1]黄太波，赵华伟，潘金秋，聂培尧，杨泽军.ZigBee协议栈的安全体系综述[J].山东科学，2012，25（2）：59-66.

[2]谢琦，赵森，仇婷婷. ZigBee消息在应用层的安全机制研究[J].计算机应用与软件，2013，30（8）：311-313.

[3]杨斌.基于AES的ZigBee标准安全机制分析[J].计算机工程与科学，2010，32（7）：42-45.

RSA算法及其安全性研究 篇3

自从1976年Diffie和Hellman两位教授提出公开密钥密码学的新概念后, 由于公开密钥密码学具有优良的密码学特性和广阔的应用前景, 很快吸引了全世界的密码爱好者, 他们提出了各种各样的公开密钥密码算法和应用方案, 密码学进入了一个空前繁荣的阶段然而公开密钥密码学的研究绝非易事, 尽管提出的算法很多, 但是能经得起时间考验的却寥寥无几。

RSA算法是由美国麻省理工学院的学者Ron Rivest, Adi Shamir和Leonard Adleman于1978年提出的公开密钥算法, 该算法已经经受了密码分析家多年深入的分析.该算法基于大数分解的困难性, 其公开密钥和私人密钥是一对大素数的函数, 从一个公开密钥和密文中恢复出明文, 难度等价于分解两个大素数的乘积.该算法具体描述如下:随机选择两个大素数p和q, 计算n=pq及, 随机选取公钥e使得, 用扩展欧几里德算法计算私钥d, 使d满足, 公开n, e, 保密p, q, d.加密消息m时加密算法为c=memodn, 解密算法为m=cdmodn。

2 对RSA的攻击

目前对于RSA算法的攻击主要有以下方式。

2.1 选择明文攻击

RSA的模指数运算能够保持输入的乘法结构, 即Ek (ab) =Ek (a) Ek (b) (modn) , 这一特点使得RSA能够用于消息的隐藏, 适于盲签名但它也影响了RSA算法的安全性。

2.1.1 破译密文

假设A的公钥为 (e, n) , 攻击者B通过窃听得到发给A的密文c=memodn, 为了获得明文, 攻击者随机选取r∈Zn*, 计算y=remodnt=ycmodn, 令k=r-1modn, 则k=y-dmodn, 现在攻击者B让A用他的私钥对t签名, 攻击者就可以得到s=tdmodn, 这样攻击者可以计算ks≡y-dtd≡y-dydcd≡cd≡med≡m (modn) 于是攻击者获得了明文m。

2.1.2 骗取签名

攻击者B想要获得A对一则非法消息m`的签名, 他有多种方法。

方法1:B首先随即选取x∈Zn*, 计算y=xemodn, 然后攻击者计算m=ym`m odn, 并将m发送给A以获得A对无害消息m的有效签名, A向B发送签名, 现在攻击者B计算mdx-1modn=ydm`dx-1modn=xe dm`dx-1modn=m`dmodn, 这样, 攻击者B得到了A对非法消息m`的签名。

方法2:攻击者B首先产生两份消息m1, m2, 满足m`=m1m2modn, 如果攻击者B能获得A对m1, m2的签名, 那么他可以计算mdmodn=m1dm2dmodn, 从而获得A对非法消息m`的签名。

所以, 为了安全起见, 不要对陌生人提交的随机性文件签名, 并且最好先使用单向Hash函数对消息进行散列运算.ISO9796分组格式可用来防止这种攻击。

2.2 公共模数攻击[1]

如果系统中每个人拥有相同的模数n, 即使每个人采用不同的公/私钥对, 系统安全仍然会收到巨大的威胁.设消息为m, 两个加密密钥为分别为e1, e2, 且满足gcd (e1, e2) =1, 两个密文为c1=me1modn, c2=me2modn, 由于, 攻击者很容易由扩展欧几里德算法得到r, s, 满足re1+se2=1, 那么c1rc2smodn=mre1+mse2modn=m。因此, 在一组用户之间共享模数是不安全的。

2.3 低加密指数攻击[2]

在RSA加密和数字签验证中, 如果选取了较低的e值可以加快速度, 但这是不安全的, Hastad证明如果采用不同的模数n, 相同的公钥e, 则对e (e+1) /2个线性相关的消息加密, 系统安全会受到威胁.如果消息比较短, 或者消息不相关, 就不存在这个问题.如果消息相同, 那么只要有个消息就可以攻击系统.一般来讲, 选取16位以上的素数速度比较快, 而且可以阻止该攻击.对于较短的消息, 使用独立随机值填充消息, 可以阻止该攻击, 这也能保证memodn≠me。

2.4 低解密指数攻击

Machael Wiener给出了另外一种攻击[3], 可以成功地计算解密指数d, 前提是满足如下条件:3d

2.5 定时攻击

定时攻击[4]主要针对RSA核心运算是非常耗时间的模乘, 只要能精确监视RSA的解密过程, 获得解密时间, 就可以估算出私有密钥d。模指数运算是通过一位一位来计算的每次迭代执行一次模乘, 并且如果当前位是1则还需要进行一次模乘.对于有些密码, 后一次模乘执行速度会极慢, 攻击者就可以在观测数据解密时, 根据执行时间判断当前位是1还是0, 不过这种方法只是理论上可以考虑, 实际操作很困难.如果在加密前对数据做盲化处理, 再进行加密, 使得加密时间具有随机性, 最后进行去盲, 这样可以抵抗定时攻击, 不过增加了数据处理步骤。

摘要：主要讨论RSA算法的安全性, 描述了当前大数分解的状况及推荐的安全密钥空间, 并在大数分解问题困难性的假设下, 简单讨论了自RSA算法提出以来, 研究者对该算法提出的各种攻击.

关键词：RSA算法,安全性,因子分解

参考文献

[1]G.J.Simmons.A weak privacy pro-tocol using the RSA cryptosystems.Cryptologia[J].1984, 7:180～182.

[2]J.Hastas.On using RSA with lowexponent in a public key network[J].Advancees in Cryptology-CRYPTO’85 Proceedings, Spring-Verlag, 1986:403～408.

[3]M.J.Winner.Cryptanalysis of shortRSA secret exponent, IEEE Transac-tions on Information Theory, vol36 (3) , 1990, 36 (3) :553～558.

RSA算法研究 篇4

1 GSM系统的安全机制及其问题

1.1 GSM系统的鉴权机制[1,2]

在GSM系统中,安全机制主要包括鉴权和加密两个方面。涉及到的参数包括:随机数(RAND)、用户鉴别密钥(Ki)、鉴权算法A3、加密密钥Kc、鉴权符号响应SRES(32bit)、加密算法A 5和A 8,其中随机数R A N D,符号响应SRES,密钥Ki称为加密三参数或鉴权三元组。首先是利用RAND和Ki以及鉴权算法A3进行用户鉴权。然后再对用户数据进行加密。

当用户MS拨打电话时,网络都要对用户进行鉴权,以确定是否为合法用户。这时,移动用户识别卡(SIM卡)和网络同时利用鉴权算法,对鉴权密钥和随机数字RAND进行计算,其过程是鉴权中心AUC产生的随机数RAND送至网络侧的A3算法运算器与鉴权密钥进行加密算法A3运算,计算出网络侧的符号响应SRES,同时AUC将产生的随机数字RAND通过公共控制信道送给移动终端,在SIM卡中与鉴权密钥进行加密算法A3运算,计算出用户侧的符号响应SRES,并传送到VLR中,将网络侧的符号响应SRES与户侧的符号响应SRES在VLR中进行比较,计算结果相同的,SIM卡被承认,用户是合法用户可以入网,否则SIM卡被拒绝,用户是非法用户,不能入网。其过程如图1所示。

1.2 存在的问题

GSM系统的安全机制,特别是用户鉴权体系存在着若干安全漏洞:第一,GSM系统采用单向认证。G S M系统用户鉴权体系可以防止未授权非法用户接人移动通信系统,却因为没有用户对网络的认证,而不能识别服务设备(如基站)的合法性,这样,一个不合法的假基站可以达到欺骗用户,窃取用户信息的非法目的。第二,认证算法A3是不公开的,这样的话,密码算法的安全性得不到数学验证。第三,鉴权密钥是固定不变的,所以对的保密性要求极高,若该密钥Ki泄漏,那么通信中的安全将无从谈起。第四,用户与网络之间缺乏密钥协商机制。

2 RSA算法及其特点[3]

RSA密码被誉为是一种风格优雅的公开密钥密码。由于RSA密码既可以用于加密,又可以用于数字签名,而且安全、易懂,因此RSA密码已成为目前应用最广泛的公开密钥密码。许多国家标准化组织,如ISO、ITU、SWIFT和TCG等都已接收RSA作为标准。Internet的Email保密系统GPG以及国际VISA和MASTER组织的电子商务协议(SET协议)中都将RSA密码作为传送会话密钥和数字签名的标准。

2.1 RSA加解密算法原理

(1)随机地选择两个大素数p和q,而且保密。

(2)计算n=pq,将n公开。

(3)计算φ(n)=(p-)1×(q-)1,对φ(n)保密。

(4)随机地选取一个正整数e,1

(5)根据ed=1 modφ(n),求出d,并对d保密。

(6)加密算法:

解密算法:

由以上算法可知,RSA密码的公开加密钥Ke=,而保密的解密钥Kd=。

RSA算法的安全性等价于求解RSA单向函数的逆的困难性。但是,在实际应用中,很多时候是因为算法实现的细节的漏洞导致攻击,所以在使用RSA算法构造密码系统时,为了保证系统的安全性,必须仔细选择各个参数。RSA的主要参数有三个:模数n,加密密钥e,解密密钥d。

2.2 RSA算法的特点

RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从提出到现在已近20年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。该算法的加密密钥和加密算法分开,使得密钥分配更为方便。它特别符合计算机网络环境。对于网上的大量用户,可以将加密密钥用电话簿的方式印出。如果某用户想与另一用户进行保密通信,只需从公钥簿上查出对方的加密密钥,用它对所传送的信息加密发出即可。对方收到信息后,用仅为自己所知的解密密钥将信息脱密,了解报文的内容。由此可看出,RSA算法解决了大量网络用户密钥管理的难题,这是公钥密码系统相对于对称密码系统最突出的优点。

3 RSA在GSM系统的加解密中的实现

针对GSM系统鉴权机制的缺陷以及RSA算法的特点,我们试着用RSA算法取代原有GSM系统鉴权体制中的A3算法,RSA算法的实现包括了三大模块:大素数的产生,密钥对的生成以及模幂运算的实现。RSA鉴权系统的实现流程图如图2和3所示。

如图2流程产生三参数组,首先产生一个随机数(RAND),用RAND和Ki通过加密算法(A8)、鉴权算法(RSA)分别算出加密密钥(Kc)和符号响应(SRES);RAND、Kc和SRES作为一个三参数组一起发给HLR。

如图3流程进行用户鉴权,当MS发出入网请求时,MSC/VLR就会查询Ki对应存储的唯一指定的值m,产生一个m比特长的随机r加在随机数(RAND)后面形成N发送给移动台(MS),MS在收到N后查询n值,去掉n比特长的尾部得到随机数(RAND),MS使用该随机数(RAND)以及与存储在用户SIM卡中的鉴权密钥和鉴权算法RSA,计算出符号响应(SRES),然后把RSES回送给MSC/VLR,验证其合法性,若相同则接入;若不同则不允许接入。

RSA算法的实现方法如图4所示。

3.1 大素数生成实现

针对RSA算法,素数的p和q的选取应该使得n=p×q的分解不可行。本设计采取的方案如下。

(1)确定大素数p和q的长度:本设计采用1024位的模值,因此p和q的位数大约为512位,考虑到p和q不能太接近,也不能取太小的值,我们取素数p的比特长为500～510之间的值,然后再定素数的长(为模n的长度减去素数P的长度)。

(2)确定搜索空间:得到了大素数p及q的长度,我们就可以在该长度范围内随机搜索大素数p和q,由素数定理知,在比特长为512的自然数中,大约每178个连续的奇自然数,就有一个素数。因而,对我们选取的自然数区域[R A N D,R A N D+t],t=k×1 7 8,R A N D是M S C/V L R发送给M S的随机数,其长为所求素数的长度,即比特长在512左右,该区域基本上会含有素数。为保险起见,可增大自数区域的长度,即增加t的值,这里取k=3。

(3)筛值:先用值小于r的小素数,对自然数区域[RAND,RAND+t]进行筛值,筛去是这些小素数的倍数的合数。考虑到筛值算法的计算量随r的加大增加得并不太多,我们取r为1023。

(4)Miller-Rabin检测:这是目前最实用、效率最高、计算量最小的算法。该算法中,需要选取和待测自然数n互素的随机数a,n属于[N,N+t],a

综合以上方案考虑,本设计采用的方法是先用随机数发生电路产生n bit的串,然后通过小素数在设定的搜索空间筛值,最后在通过Miller_Rabin素数检测来判断是否为素数,产生大素数的流程如图5所示。

产生的两个大素数p和q的值如下(用十六进制表示)。

p=E86C7F16FD24818FFC502409D33A83C2A2A07FDFE971EB52DE97A3DE97A3DE092980279EA29E32F378F5E6B7AB1049BB9E8C5EAE84DBF2847EB94FF14C1E84CF568415

q=D7D9D94071FCC67EDE82084BBEDEAE1AAF765917B6877F3193BBAEB5F9F36007127C9AA98D436A80B3CCE3FCD56D57D4103FB18F1819D5C238A49B0985FE7B49

其中模n值为:

n=C3F8E7F2836DE23254FC66235DD74398BE4A82EC846C0667B7C15D5C9E2B819E433025AA6DFB73B280EC7048AAC42FFBAA1B66AB83107CB9FE11FC026D0B080AB68D380E032D96AE44DA944561777F80C0C71CEEBE6031FFBFBD3DE0EBE31E6600DFA447B5BD15514316E15377CF9F9E436F4038C8A5389B0A6F7C0FD

从实验结果可以看出,p和q都是十进制154位的大素数。由于本设计采用1024位的模n(十进制约为308位),因此其两个素数因子应该为154位左右,且可以通过计算满足n=p×q,证明了设计的正确性。

3.2 加密密钥产生

所谓密钥的产生,即是己知欧拉函数φ(n)=(p-1)(q-)1,求e和加密指数d。其中e是与欧拉函数互素的奇数,加密指数d是e模的逆元。因此,求密钥对,实质上是求模逆元运算。n的欧拉函数值φ(n):

φ(n)=C3F8E7F2836DE23254FC66235DD74398BE4A82EC846C0667B7C15D5C9E2B81F9E433025AA6DF1FB73B280EC7048AAC42FFBAA1B66AB83107CB9FE11FC026D0AEC065107C11BEEAC74C073E8EBB901278C5611F146C78646773AFCD67F8B6FDE00D12AD838D3DE413F05960CDA0623114BE356C629A5B747A6062D02251A2C1A0

为了加快RSA的速度,可以选取小的e,虽然小的加密指数会影响RSA的安全性,但是,只要我们稍作处理,即给待处理信息填充随机数,就可以避免这种攻击。本设计中,e的取值为3,5,7,57其中之一,或者是一个长度不超过32比特的数,而且Ki安全性可以保证。

从以上分析可以知道:得到大素数p,q后,就可以计算e和d了。本设计采用如下的步骤产生密钥对:

第一步:计算φ(n),φ(n)=(p-1)(q-)1;

第二步:求e、d。

(1)随机选取1

(2)求d,满足e×d=1(modφ(n))。

e的产生如下。

从以上的分析流程,得到大素数后,首先计算出欧拉函数φ(n)=(p-1)(q-)1,然后进行e的选取。要选取e,首先必须判断它与是否互素,即看e和φ(n)的公因数是否为1。

3.3 模幂计算

计算模幂运算memodn不能先计算me然后再求模,因为如果m为200位的大数,me的结果会占用巨量的存储空间而无法实现,必须对me的中间结果进行求模运算,使结果二进制位数始终保持在一定范围内。如果将e划分后,取幂可作为一连串乘法,并且每次都进行模运算,可使运算速度加快。

假设用户鉴权键Ki。

Ki=B503BE7137293906649E0AE436E29819EA2D06ABF31E10091A7383349DE84C5B

通过对Ki进行模幂运算得到SRES:

SRES=486A4805B2B00D87FF361C2868B4C6DCD5C08F0901E834237BB8079198A67D4BFD3807D22AA6805010B09C5210B4E436B493788F28A8AE79E5826C017F14008782A1FA9049BF8354B57718099B8C8391EBC14D1B75C04E0CC2989783842B71FFCA094A5AA80600C38B2C5B1D370035A1035383A6BF5D0DD1E0B7FDE1F05AA372

将符号响应SRES送回给M S C/V L R,M S C/V L R中的S R E S:

SRES=486A4805B2B00D87FF361C2868B4C6DCD5C08F0901E834237BB8079198A67D4BFD3807D22AA6805010B09C5210B4E436B493788F28A8AE79E5826C017F14008782A1FA9049BF8354B57718099B8C8391EBC14D1B75C04E0CC2989783842B71FFCA094A5AA80600C38B2C5B1D370035A1035383A6BF5D0DD1E0B7FDE1F05AA372

SRESAUC与SRES MS相同,予以接入。

4 结语

本文分析了GSM系统的安全机制,指出了其鉴权机制的缺陷,并基于RSA算法设计了新的GSM鉴权机制,并对新的机制进行了详细说明。根据RSA本身的特点,可以看出基于RSA的鉴权机制的抗攻击性要好于原有机制,那么在移动通信中使用RSA算法也成为了一种可能。该方法对改进GSM系统的安全机制,乃至第三代移动通信系统的安全机制都提供了参考。

摘要：GSM系统是目前全球拥有最多用户的移动通信系统,如何保障用户通信的安全性是其关键问题之一。本文首先对GSM系统现有的安全机制做了介绍,指出了其存在的问题,提出了将RSA算法用在GSM系统的鉴权机制中,并对其实现过程做了详细的介绍,该方法可以对移动通信的构造新的鉴权机制提供一定参考。

关键词：GSM,RSA,鉴权,安全机制

参考文献

[1]鲁骏.GSM安全性分析[J].移动通信,2009,6.

[2]杨秀清,赵莲清.GSM系统与WCDMA系统用户鉴权体系的比较[J].中国新通信,2008,5.

[3]韩宝乐.DES密码体制及其应用探讨机制[J].中国科技博览,2008,16.

浅析RSA加密算法 篇5

在传输信息过程中,为确保信息的安全性和保密性,信息加密成为一种主要措施。加密算法的种类不胜枚举。从2012年为期5天的RSA大会中,可见RSA已经运用到社会中的各个领域,受到了全世界的关注。这主要基于RSA加密算法不仅易于理解和实现,而且安全性好。

1 RSA加密算法

1.1 算法原理

文献[1]中描述RSA算法是在1977年由Rivest、Scha Mir和Adle Man发明的。RSA算法是一种既用于数据加密也可以数字签名的非对称密码算法,其安全性依赖于因子分解大数问题。

RSA密码算法是利用陷门单向函数的一种可逆模指数运算,它的安全性是基于大数分解的困难性。下面给出RSA体制的算法流程:

1)RSA加解密算法的初始化

第一,加解密系统随机地选取两个非公开的大素数p和q。

第二,计算出公开的模数N和非公开的欧拉函数,N=pq,φ(N)=(p-1)(q-1)。

第三,随机生成一个整数e作为加密秘钥,并使成立。

第四,计算d(私钥),使得)成立,即,为安全起见立即销毁p、q及e。

2 RSA算法存在攻击

尽管对于RSA的密码分析已经研究了三十多年,但它依然是流行和可靠的。可是,在RSA算法实现的细节上存在一些缺陷,这导致了RSA的安全性下降,从而使RSA被攻击者攻破。下面简单地概述一下目前对RSA算法攻击的几种主要方法。

2.1 数学攻击

实质上就是直接对两个素数乘积N的因式分解。这是一种最直接和最困难的的方法。一旦对N进行分解成功,就很容易得到密钥e。大整数因子分解一直是数论和密码学理论研究中的主要课题。根据目前的研究表明,目前最快的因式分解算法的复杂度为。此外,在文献[4]中,作者提出了用于分解强素数乘积构成的RSA模数N的算法,能够进一步提高了运算效率。

2.2 时间攻击

依赖解密算法的运行时间。P.Kocher提出,利用测定RSA解密所进行的模指数的运算时间来估计解密指数d,然后再确定d的值;可以通过将解密运算量与参数d无关来挫败时间攻击;不断强力穷举密钥。

2.3 密文攻击

攻击者非法获取密文通,过对密文反复用公开密钥加密,可以使明文出现。例:如果取RSA参数(N,e)为(35,17),明文M为33,加密明文:c=3317mod 35=3;再次加密:317mod 35=33,从而得到明文。

2.4 RSA的部分明文攻击

另外,攻击者不仅对可以密文进行攻击,也可以通过获取明文消息的部分信息进行破译或恢复整个明文。这也是RSA存在的另一个安全性的重要问题。

2.5 对RSA小指数的攻击

此攻击方法主要针对RSA算法实现中的细节。如果为了加快加密和验证,选较小的e,并且用这些e向多个用户加密同一个消息(N不同),利用中国剩余定理可以联立方程求解明文。

2.6 公用模攻击

如果需要多个密钥对,有一种做法:不再重新寻找p、q,而只是重新选d、e,即若干对密钥使用同一个模N。这时可以不用重新分组,也方便管理。但可能遭到公用模攻击。这样,如果同一信息用两个不同的指数e加密,并且两个指数e是互素的,则不需要任何解密密钥便能恢复出明文。设M是明文,两个互素的加密密钥分别是e1、e2,共同的模数为N,两个密文分别c1=Me1mod N、c2=Me2mod N。由于e1、e2互素,根据扩展Euclid算法可以找到a和b,使其满足ae1+be2=1。假设a是负数(在a、b中,肯定有一个是负数),再次使用Euclid算法可以计算出c1-1故可得到((c1-1)-rc2s)≡M mod N。

3 参数的选择

RSA体制是将安全性基于因子分解的第一个系统。虽然无法证明因子分解等于破解RSA系统,但若能分解因子N,便能破解RSA系统,所以RSA对公开的N的选择是很关键的。对于公开密钥e和解密密钥d也需要加以限制,否则会使RSA不安全。选择参数会影响RSA整个系统的安全,常用的参数选择应注意要求如下:

3.1 p,q的选择

要想提高RSA的效率和安全性,可以从p、q两个参数以下两个方面着手:素数的检测算法和对p、q的破解。

素数的检测算法。在RSA算法中,首先要产生两个大素数。但是要判断一个大整数是否为素数却一直是个难点。素数检测算法有确定性素数检测法和概率性素数检测法两类。目前,在RSA密码的应用中都使用概率性检测法来判断一个大数是否是素数。但是通过概率性监测算法的检测,还是存在伪素数的情况。

对p、q的破解。从RSA算法原理中,我们知道欧拉函数φ(N)和模数N:φ(N)=(p-1)(q-1)和N=pq。那么根据这两个式子可以构造关于p、q的一元二次方程,即χ2-(N-φ(N)+1)χ+N=0。其中p、q满足:

由文献[4]提出的一种强素数的量子算法,可求得φ(N),这样就可以得到p、q的值,即分解了模数N,RSA就被破解了。

总之,为了抗穷举,p、q都要大;p、q的差要大,如果p、q的差不大,可以用N开方估算p、q;p-1、q-1要有大的素因子,p、q要为强素数;p-1、q-1的公因数要小。

3.2 模数N取几个素数乘积

从RSA算法原理,我们知道模数N是由两个素数相乘得到的。那么模数N可以由多个素数相乘得到吗?答案是肯定的。Euler函数φ(N)表示小于N并且与N互素的正整数个数。如果模数N可因式分解为(其中,ai>0,ai互不相同),则φ(N)=∏Piai×(1-1/Pi)即:。文献[1]已经证明了该推断的正确性。

无论取多个素数还是两个素数相乘,一旦计算出模数N的值,就会都被丢掉。所以这多个素数和两个素数的保密性是一样的,RSA的加密和解密过程是相同的。那么在确定N时应尽可能的选择多个素数相乘。但是如果通过量子算法[4]来对多个素数乘积的模数N进行分解的话,那么就不能构成一元二次方程,分解模数N的难度就更大。

3.3 e,d的选择

e不能太小,如果e小,则可能而未取模,这样可以直接对密文开方求出明文;e太小易遭低指数攻击。为了有效防止被攻击,同时有较快的加解密速度,通常加密密钥e选取16位的素数,并且为modφ(N)的阶数,即i要达到(p-1)(q-1)/2。

d不能太小,应该。解密密钥d的值越小,系统签名和解密运算的速度越快,这对于我们常用的智能卡的加密、银行系统的签名特别重要。

4 小结

综上所述,RSA是一种安全性较好的非对称密码算法。它的安全性依赖于对模数N的因式分解。在日常生活中,RSA算法已广泛地运用到各个领域。那么对RSA算法的攻击无时不在。特别地,当选择的参数不当时,RSA很容易被攻击。要确保RSA的效率和保密性,我们应注意以下几点:对素数检测算法进行改进;用量子算法来研究RSA算法。

摘要：RSA算法不但能用于数据加密,也能用于数字签名,还能检测素数的算法,所以它是目前最有影响力的公钥加密算法,能够抵抗到目前为止已知的所有密码攻击。其安全性依赖于大素数因数分解的困难性。文章主要介绍RSA的加密算法原理、加密与解密过程,存在的攻击,以及参数选择。

关键词：非对称密码,RSA算法,加密,素数,参数,量子算法

参考文献

[1]武亚宁.RSA公钥算法的新探讨及改进[J].信息安全与技术,2012(9):27-28.

[2]白洁.RSA大会,安全领袖眼中的世界[J].信息安全与通信保密,2010(4):16-19.

[3]张宏,刘方圆.四素数RSA加密算法的研究与分析[J].2010:29-30.

[4]潘峰,申军伟.一种强素数因式分解的量子算法[J].2010,46(10):73-74.

RSA两种相关算法的改进 篇6

RSA公钥密码体制是由麻省理工学院的Ron Divest, Adi Shamir和Leonard l Adleman于1976年提出, 1978年正式发表的一种可将加密密钥公开的密码体制。RSA密码体制从提出到现在经受住了多年深入的密码分析的考验, 已逐步走向成熟, 被越来越多的人所接受, 它是目前世界上唯一被广泛使用的公开密钥密码体制。

目前, 为保证安全性, RSA算法中用户选择的素数p和q都为100位左右的十进制数, 这样的大整数运算必然造成其加解密速度异常缓慢, 因此探讨RSA算法的某些局部优化, 以加快其运行速度, 是十分必要的。

二、大数存储与运算的改进

1. 大数存储。

RSA算法中用到的大数其十进制位数可达数百位, 而在编程语言提供的各种标准数据类型中, 32位机器上整型数所能表示的最大的正整数也只有232-1, 远远不能满足要求, 因此, 大数的存储不能用通常的方法来表示, 必须用自己定义的数据结构来实现。

最常用的表示大整数的方法是将大整数表示成为一个二进制序列, 该序列用一个数组表示, 则每一个二进制位对应该数组的一位。这种方法的优点是表达直观, 编程容易。但它也有明显的缺点, 首先, 占用的存储空间多。一个十位的十进制数化为二进制数, 是 位, 因此, 一个数百位的十进制数用该方法将占用上千个存储单元, 这是一个很大的浪费。其次, 运行速度慢, RSA算法中明文的表示采用分组形式, 实际应用中都是通过键盘输入, 键盘输入读取的字符都直接表示为ASCII值, 为将其转换成二进制形式, 必须多花费一道转换的过程, 同时, 由于二进制形式的表示使得数组长度很长, 减慢了运算速度。

2. 改进的大数表示。

改进的大数表示, 最常见的是采用万进位法, 它逢万进位, 每个存储单元存储的最大值是9 999, 这种方法的性能比二进位法有了很大的提高, 它的思路是通过增加每个数据单元储存的信息量来减少存储空间和总循环次数, 但还可以在它的基础上对其做更进一步的改进。本文采用了一种特殊的表示方法, 整个大数采用一个数据结构表示, 该数据结构中包含一个用来表示该数值的数组, 每个数组单元都是一个无符号长整型数, 可表示大小在32位CPU上为232-1, 每个数组单元的值是十进制数, 但数组相邻的上一单元与下一单元之间的关系是二进制形式的。举例说明, 设大数占用一个存储单元, 则用十进制表示, 不妨设为93, 即表示为十进制数93, 若大数占用两个存储单元, 不妨仍设第一个单元为93, 第二个单元为1, 注意, 此时表示的数不是1, 000…093, 而是232+93。

该数据结构中, 包括一个指示该数是否为负数的标志, 一个整数指示实际分配的存储单元的大小, 还有一个整数专门用来指示实际使用的存储单元的大小。这样做的好处是由于大数的频繁运算, 它的位数会经常发生改变, 只有当存储空间不满足要求时才会考虑重新分配, 而当由于某些运算后大数实际使用的存储单元减少而不需要重新分配, 只需改变指示实际使用的存储单元的大小的整数值就可以了, 这样就可以避免每次运算后由于参与运算的数据位数的改变而频繁释放和分配内存。

三、递归余数和算法及改进

1. 递归余数和算法。

传统的幂剩余计算采用的是BR (BinaryRePresentations) 算法。即将指数E表示成二进制形式,

然后将幂剩余计算分解成一系列乘同余和平方剩余的迭代:

如果中间结果为A, 则每步迭代进行乘同余AM mod N或平方剩余A 2mod N的计算。

若令X=AM或X=A 2, 将X表示成二进制形式:

式中k为x的二进制长度。AM mod N或A 2mod N可表示成:

由于模运算满足结合律, 则上式可变为:

于是 (6) 中X对N的模运算就变成了一系列余数之和。

由 (5) 得:

(7) 说明第i个余数可由前一个余数迭代而来, 这就是递归余数和的由来。

2. 递归余数和的操作步骤。

首先建立一个余数表, 将预先产生的2的各次幂的余数顺序排列进去, 在进行求模运算时, 只需找出被模数的非零位, 在余数表中查出相应的余数并求和即可。

计算18 mod 7。由于18= (10010) 2, 非零位为

所以18 mod 7=2+2=4

直接计算18mod7, 亦可得到相同的结果。从上面的例子可以看出, 被模数所包含的非零位个数越少, 求和次数就越少, 计算速度就越快。

3. 递归余数和算法的改进。

由上述讨论可知, 递归余数和算法速度取决于被模数非零位个数。据此, 提出一种改进的递归余数和算法。

先将待加密信息M的二进制表示变换成二进制冗余表示。用i代表-l, 当M的二进制表示中有3个以上连“1’, 时, 将最低位“1”变成“i”, 最高位“1”前面增加一个“l”, 中间各位都置为“0”。如111变成100i, 1111变成1000i, 不难证明111=1000-1=100i, 1111=10000-l=1000i, 当M=10111001111101时, 相应的二进制冗余数R (M) =1100i010000i01, 容易证明M=R (M) 。以后每计算一步, 都对中间结果进行同样的变换。用变换后的二进制冗余数进行乘法运算, 其乘积必为二进制冗余数,

并可能出现连“i”的情况。此时将最低位“i”, 置为“1’, 在最高位“i”, 前增加一个“i”, 中间各位均置为“0”。如iii=i001, iiii=i0001。如果。“l”和“i”相邻, 则按如下规则变换:

不难证明这些变换的正确性。

改进后的递归余数和算法仍然是先建立余数表, 然后用二进制冗余数进行乘法运算, 再用递归余数和方法对二进制冗余数求模。求模时, 从高位算起, 遇到为“1”的位就加上相应的余数, 遇到为“i”, 的位就减去相应的余数。如计算7 mod 5:

在幂剩余的BR算法中, 每步迭代都只有两种基本运算:乘法和求模。乘法的快慢取决乘数和被乘数的非零位个数。乘数的非零位个数越多, 乘法运算的移位累加就越多, 累加越多, 进位就越多。当乘数和被乘数很大时, 进位的传播严重制约了乘法速度的提高。当用二进制冗余数代替二进制数时, 由于非零位减少, 移位累加次数减少, 在累加时, 当“1”和“i”相遇时则互相抵消, 这就使进位传播减少, 从而缩短了乘法运算时间。

例如:计算15x15的二进制数乘法为1111*1111=11100001。二进制冗余数乘法结果为:100i00001。两者结果相等, 但二进制冗余数乘法运算步骤明显减少, 进位传播也明显减少。同时, 非零位个数的减少, 也使递归余数和算法的求和次数减少, 使求模速度加快。不同的只是求算术和变成了求代数和。

实现RSA算法应注意的问题 篇7

关键词：公钥密码,RSA,共模攻击

0 引 言

随着Internet的迅速普及,网络给人们带来便利的同时,也带来了一个不容忽视的问题即网络信息的安全保密问题。为了保护网络中传输的数据不被黑客截取、修改、添加、删除,导致密码学、数字签名、和认证技术的产生。RSA[1]是第一个公钥密码的实际实现,在1978年Rivest、Adleman、Shamir提出该算法之后,已广泛应用于各种硬件软件产品平台之上。RSA的安全性基于:计算密文C模合数n的e次根的困难性和整数分解问题的困难性。在公钥加密算法下,公钥是公开的,任何人可以用公钥加密信息,再将密文发送给私钥拥有者;私钥是保密的,用于解密其接收的公钥加密过的信息。文献[2]中对RSA公钥密码体制的安全性进行分析,并给出当RSA在参数选取不当情况下,可能遭受小加密指数攻击、因式分解攻击。本文介绍常见的攻击方法选择密文攻击和共模攻击,以说明安全实现RSA算法应注意的问题。

1 RSA基本算法的描述

1.1 算法参数的构成

① 选取两个大素数p≈q;

② 计算n=pq;

③ 随机选取e,满足gcd(e,φ(n))=1,那么公钥即(e,n);

④ 用Euclid算法计算d,d=e-1mod φ(n),那么私钥即(d,n);

最后销毁p、q、φ(n),其中φ(n)为欧拉函数φ(n)=(p-1)(q-1),保存私钥,公开公钥。

1.2 加解密过程

M为明文,C为密文。

加密 C=En,e(M)=Memod n (1)

解密 Ed,n(C)=Cdmod n=Medmod n=M (2)

2 RSA算法实现应注意的问题

2.1 不要对外来的随机信息解密

假设攻击者截取了一段Alice发给Bob的一段密文C(对应明文为m),攻击者可以不通过大整数分解的方法得到明文。方法如下:

(1) 选择一整数r(r∈RZ*n)且r与n互素;

(2) 计算C1=remod n;

(3) 计算 C′=C1Cmod n;

(4) 把密文C′发送给B解密,解密结果为rm;

(5) 计算f=r-1mod n;

(6) m=frm mod n。

要防止这种攻击的办法就是解密前对消息源进行认证,不要对外来的随机信息解密。

2.2 不同的RSA密钥对不应共模[3]

(1) 多个密钥对共模可能遭受共模攻击

(2) 如果知道其中一个公私钥对e和d,则可攻破整个密码系统。因为:

φ(n)=(p-1)(q-1)=pq-p-q+1

n=pq>>p+q-1

∴ n≈φ(n)

ed=1mod φ(n)⇒ed=k φ(n)+1⇒k φ(n)=ed-1

下面通过其中一对密钥e、d求出φ(n)、p、q,从而可求出其他密钥对。

共模攻击如下:

(1) k=1;

(2) if k不能整除ed-1或(ed-1)/k>n 则k=k+1,重复执行(2);

(3) φ(n)=(ed-1)/k;

(4) p、q是方程x2-(n-φ(n)+1)+n=0的两个根。

文献[3]对RSA从根本上免受共模攻击提出不同密钥对不共模,并对p、q的生成算法进行讨论,这里不再赘述。

2.3 公钥e不可过小

e是一个小数并不降低RSA的安全性。从计算速度考虑,e 越小越好。可是,当明文也是一个很小的数时就会出现问题。例如我们取e=3,而且我们的明文m比n的三次方根要小,那么密文C=memodn就会等于m3,这样只要对密文开三次方就可以得到明文。

3 结束语

网络的开放性以及黑客的攻击是造成网络不安全的主要原因。科学家在设计Internet之初就缺乏对安全性的总体构想和设计,我们所用的TCP/IP 协议是建立在可信的环境之下,而网络互连是缺乏对安全方面的考虑的,只有对网中传输的信息加密方可保证其安全。RSA公钥密码算法可用于加密,也可用于认证和数字签名领域。本文对RSA算法实际实现应注意的事项进行研究,给出实现RSA算法应注意的问题。

参考文献

[1]Rivest R L,Shamir A,Adleman L.Amethod for obtaining digital signa-tures and public-key cryptosystems.Communication of ACM,21(2):120-126.

[2]张淑芬.RSA公钥密码体制的安全性分析及其算法实现.计算机应用与软件,2005(7).

CA系统中的RSA加密算法原理 篇8

随着我国数字电视的推广和普及, 数字化的视频、音频、图像、资讯等播放设备走进普通人的家庭, 但是数字电视的非法复制和侵权行为变得越来越严重。特别是数字电视衍生出来的增值业务, 如视频点播、按次付费、网上游戏、信息点播等应用给原来的数字电视广播系统带来了更大的发展空间, 但是为了确保这些新业务的实现, 一个安全可靠的综合业务平台就显得尤为重要, 其中CAS (Conditional Access System) 就是重要的组成部分之一。

CA系统涉及到信息安全工程学和密码学相关领域。其中密码学中用到了对称算法、非对称算法及哈希函数。对称加密算法的优点是加解密的速度很快, 缺点是无法对传输的密钥进行加密, 所以主要用它来对传输的数据进行加密, 而且哈希函数主要的作用是用来生成数据的指纹, 能保证数据在传输过程中的完整性。非对称算法的优点是加密和解密使用不同的密钥, 所以它能在不安全的信道上传输信息, 缺点是速度特别慢, 所以它适合用来传输加解密的密钥。而在CAS中非对称算法主要用RSA算法, 本文主要介绍RSA的算法原理。

2 RSA算法的数学理论基础

RSA公钥加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在 (美国麻省理工学院) 开发的。RSA取名来自三个开发者的名字。RSA是目前最有影响力的公钥加密算法。现在已知的所有非对称加密算法都是基于已知的数学难题而设计的, 如:背包算法基于数学中解决背包问题的复杂性, DH密钥交换协议基于求离散对数的复杂性, RSA算法也不例外, 其数学原理是求两个大质数的乘积很容易, 而分解两个大质数的乘积很难办到。下面就介绍一下RSA算法的数学原理。

2.1 单向函数和陷门单向函数

RSA的安全性主要取决于构造其加密算法的数学函数的求逆困难性, 这同大多数公钥密码系统一样, 这样的函数我们称为单向函数。单向函数是不能直接用作密码体制的, 因为如果用单向函数进行加密, 那么合法的接收者也不能还原出明文, 因为求单向函数的逆运算很困难。与密码体制关系更为密切的是陷门单向函数, 即函数及其逆函数的计算都存在有效的算法, 而且可以将计算函数的方法公开。单向函数和陷门单向函数的概念是公钥密码学的核心, 它对公钥密码系统的构造非常重要。

定义a:令函数f是集合A到集合B的映射, 以f:A→B表示。若对任意X1≠X2, X1, X2∈A, 有f (X1) ≠f (X2) , 则称f为映射, 或可逆函数。

定义b:一个可逆函数f, 若它满足:

(1) 对所有X∈A, 易于计算f (x) 。

(2) 对“几乎所有”x∈A, 由f (X) 求x“极为困难”, 以至于实际上不可能做到。

则称f为单向函数, 上述定义中的“极为困难”是对现有计算机能力和算法而言的。

2.2 同余及模运算

同余:假定有三个整数a, b, n (n≠O) , 当我们称a在模n时与b同余, 是指当且仅当a与b的差为n的整数倍, 即a-b=kn, 其中k为任一整数。若a与b在模n中同余, 我们可写为a≡b (modn) 。

剩余类:很明显地, 利用同余概念, 所有整数在模n中被分成n个不同的剩余类;被n所整除的数 (即余数为0) 为一剩余类, 被n所除余数为1的数为另一剩余类, 余2的数又为一剩余类, 以此类推。

完全剩余系:若在每一剩余类中取一数为代表, 形成一个集合, 则此集合称为模n的完全剩余系, 以Zn表示。很明显地, 集合{0, 1, 2, …, n-1}为模n的完全剩余系。

从0到n-1的整数组成的集合构成了模n的“完全剩余系”。这意味着, 对每一个整数a, 它的模n剩余是从0到n-1之间的某个整数。

既约剩余系:也叫缩剩余系, 在模n的完全剩余系中, 若将所有与n互素的剩余类形成一个集合, 则称此集合为模n的既约剩余系, 以zn*表示。例如n=10时, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}为模10的完全剩余系;而{1, 3, 7, 9) 为模10的既约剩余系。

2.3 欧拉函数、欧拉定理和费马小定理

欧拉函数Φ (n) :是一个定义在正整数上的函数, 其值等于0, 1, 2, 3, …, n-1中与n互素的数的个数。即Φ (n) 为模n既约剩余系中所有元素的个数。由定义知, 当P是素数时, Φ (n) =P-1。

欧拉小定理:若m, a为正整数, 且GCD (a, m) =1 (注:GCD表示最大公约数) 则aφ (m) ≡1 (mod m) 。其中Φ (m) 为欧拉函数, 它是比m小但与m互素的正整数个数。欧拉定理也有一种等价形式:aφ (m) +1≡1 (mod m) 。

费马小定理:如果p是素数, 且GCD (m, p) =1, 则mp-1≡1m odp, 费尔马定理还存在另一种等价形式:如果P是素数, m是任意正整数, 则mp≡m (mod p) 。对于素数P来说, φ (p) =p-1, 可见费马小定理是欧拉小定理的特殊形式。

推论1:设p和q是两个不同的素数, n=p×q,

则Φ (n) = (p-1) × (q-1) 。

证明:小于n的正整数有n-1个, 其中p、2p、3p, …, (q-1) p一共q-1个数, q、2q、3q...... (p-1) q一共p-1个数与n都不互质,

所以φ (n) =n-1- (p-1) - (q-1) =n-q-p+1=qp-q-p+1= (p-1) × (q-1) 。

推论2:对任意的X∈zn及任意的非负整数k, 有xkφ (n) +1≡xm odn。

2.4 乘法逆元及其求法

乘法逆元的定义:若ab≡1 (m odn) , 则称b为a在模n的乘法逆元, b可表示为a-1。

可利用辗转相除法求乘法逆元:己知a及n且 (a, n) =1, 求aa-1≡1 (m odn) 。

欧几里德算法是古希腊数学家欧几里德给出的求两个自然数的最大公约数的方法, 如果GCD (a, b) =1, 则b一定存在。利用辗转相除法来求两个数的最大公约数和求一个数的逆元的收敛速度是很快的, 这对计算机来说是很容易办到的。细节证明可查阅相关资料。

3 RSA算法的实现

3.1 RSA公钥加密解密概述

3.1.1 密钥的产生

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

(2) 计算模N=p×q (公开) , 以及欧拉函数φ (N ) = (p一1) × (q-1) (保密) , 其中φ (N ) 是N的欧拉函数值。

(3) 随机选取整数e (公开) , 满足1<e<φ (N ) , 且gcd (e, φ (N ) ) =1。

(4) 计算d (保密) , 满足保密d×e≡1 (m odφ (N ) ) , d是e在模下φ (N ) 的乘法逆元。

(5) 以 (e, N) 为公钥, (d, N) 为私钥, 销毁p, q, φ (N ) 。

3.1.2 加密

加密时首先将明文比特串进行分组, 使得每个分组对应得串在数值上小N, 即分组的二进制长度小于log2 N。然后, 对每个明文分组M, 作加密运算:

3.1.3 解密

对密文分组的解密运算为:

整个流程可如图1所示。

3.2 RSA算法举例

3.2.1 设计公私密钥 (e, n) 和 (d, n)

令p=3, q=23, 得出n=p×q=3×23=69 (公开) , φ (N ) = (p-1) (q-1) =2×22=44。

取e=5 (公开) , 注意GCD (5, 44) =1, 则e×d≡1 modφ (N ) , 即5×9=45≡1 mod 44。

利用辗转相除法我们很容易找到这个d, 而且由于GCD (5, 44) =1能保证这个d值一定存在。通过计算我们找到, 当d=9时, e×d≡1 mod f (n) 同余等式成立。因此, 可令d=9。从而我们可以设计出一对公私密钥, 加密密钥 (公钥) 为P= (e, n) = (5, 69) , 解密密钥 (私钥) 为S= (d, n) = (9, 69) 。

3.2.2 英文数字化

我们现在把字母用数字表示, 然后选出我们要加密的信息, 如我们选取单词'YES'作为要加密的文, 则得到分组后的YES的明文信息为:25, 05, 19。

3.2.3 明文加密

用户A用加密密钥公钥 (5, 69) 将数字化明文分组信息加密成密文。由C≡Me (mod n) 得:

C1≡M3e (mod n) =255 (mod69) =55

C2≡M2e (mod n) =055 (mod69) =20

C3≡M1e (mod n) =195 (mod69) =34

因此, 得到相应的密文信息为:55, 20, 34。

3.2.4 密文解密

用户B收到密文, 若将其解密, 只需要计算M≡Cd (modn) , 即:

M1≡C3d (mod n) =559 (mod69) =25

M2≡C2d (mod n) =209 (mod69) =05

M3≡C1d (mod n) =349 (mod69) =19

用户B得到明文信息为:25, 05, 19。根据上面的编码表将其转换为英文, 我们又得到了恢复后的原文“YES”。

3.3 RSA算法分析

因为公钥是大家都知道的而私钥是生成密钥的一方才有, 即使中间有人窃听, 他只能获取e、n和C。而且只根据e和n是没办法推出d的, 除非他能把n分解了, 求出q和p。但是想要分解n, 是一个数学难题, 几乎是不可能的, 所以这就保证了通信的安全性, 实现了在一个不安全的信道上也能安全地传输信息。

4 总结

RSA的安全性依赖于大数分解, 但是否等同于大数分解一直未能得到理论上的证明, 因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法, 就可以求出d的算法, 那RSA算法的安全性就受到了绝对的挑战。不管怎样, 分解n是最显然的攻击方法。现在随着计算机运算速度的提高, 人们已能分解多个十进制位的大素数。因此, 模数n必须选大一些, 要视具体适用情况而定。

由于进行的都是大数计算, 使得RSA的加解密速度非常非常慢, 速度一直是RSA的缺陷。一般来说只用于少量数据加密, 如密钥。这也是为什么CA系统只用它进行加密密钥的原因, 而真正的数据传输还得用对称密钥算法如DES、3DES、AES等速度比较快的加密算法来实现。

摘要：条件接收系统 (CA系统) 是数字电视进行安全传输的关键, 而CA系统中应用到的RSA加密算法又是整个加密体系的重要环节。本文对RSA加密算法的数学原理做了简要的阐述, 并对RSA算法传送密钥进行了分析, 提出了综合运用算法的关键。

关键词：数字电视,CA系统,条件接收,RSA,非对称加密算法

参考文献

[1] 闵嗣鹤, 严士键.初等数论.北京:人民教育出版社, 1957.

[2] 潘承洞, 潘承彪.简明数率.北京:北京大学出版社, 2001.