RSA加密体制

关键词： 单向 函数 构造 密码

RSA加密体制（精选七篇）

RSA加密体制 篇1

一、RSA算法理论基础

R SA算法采用下述加密/解密变换:

1、密钥的产生

(1)选择两个保密的大素数p和q。

(2)计算N=pq,φ(N)=(p-1)(q-1),其中φ(N)是N的欧拉函数值。

(3)选择一个整数e,满足1<e<φ(N),且gcd(φ(N),e)≡1。

(4)计算私钥d(解密密钥),满足ed≡1(modφ(N)),d是e在模φ(N)下的乘法逆元,因e与φ(N)互素,由模运算可知,它的乘法逆元一定存在。

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

2、加密

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

3、解密

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

由欧拉定理可以证明解密运算能恢复明文M。

二、几种针对RSA的攻击方法

密码学所讨论的系统,其安全性是最高的评价准则。再好的密码系统,若安全性不足则一文不值,同时,密码系统的安全性很难用理论证明(事实上证明其为安全很难,但若此系统不安全,则证明其为不安全很容易)。R SA算法从提出到现在已经有二十多年的时间了,广泛的应用证明R SA体制的安全性是相当可靠的。但是在特定的条件下,R SA的实现细节的漏洞会导致对R SA算法的攻击。

对R SA算法的攻击主要有以下几种:

1、对分解模数N的攻击

分解模数N是最直接也是最困难的攻击目标。如果N=pq被因式分解,则攻击者通过p、q便可计算出φ(N)=(p-1)(q-1),进而ed≡1(modφ(N))而得到解密密钥d,大整数分解研究一直是数论与密码理论研究的重要课题。

2、对R SA的选择密文攻击

选择密文攻击是攻击者对R SA等公钥算法最常用的攻击,也是最有效的攻击手段之一。选择密文攻击通常是由R SA加密变换的性质诱发的,常见的对R SA的选择密文攻击有三种:

(1)明文破译。攻击者获得某用户U使用公钥e加密的密文y≡xe(modn),并试图恢复出消息x。随机选取r<n,计算y1≡re(modn),这意味r≡y1d(modn)。计算y2≡(y y1)(modn)。令t≡r-1(modn),则t≡y1-d(modn),现在攻击者请U对消息y2进行签名(不使用H ash函数,仅使用解密密钥),得到s≡y2d(modn)。攻击者计算t1=ts≡(y1-dy2d)(modn)≡(y1-dy1dy d)(modn)=y d(modn)=x,得到明文。

(2)骗取仲裁签名。在有仲裁情况下,若某用户U有一个文件要求仲裁,可先将其送给仲裁T,T使用R SA的解密密钥进行签名后送给U(未使用H ash函数,仅以解密密钥对消息进行签名)。攻击者有一个消息想要T签名,因为由于可能有伪造的时戳或来自非法使用者的消息,T并不签名。但攻击者可用下述方法获得T的签名。令攻击者的消息为x,首先任选一个数N,计算y≡N e(modn)(e是T的公钥),然后计算M=y x,送给T,T将签名结果M dmodn送给攻击方,则有:

攻击者成功骗取T对x的签名。

(3)伪造合法签名。攻击者利用自己伪造的两个消息x1和x2来拼凑所需要的x3≡(x1x2)(modn)。攻击者如果得到用户U对x1和x2的签名x1d(modn)和x2d(modn),就可以计算x3的签名,x3d≡(x1d(modn))(x2d(modn))(modn)。

3、对R SA小指数攻击

这类攻击专门针对R SA算法实现的细节。采用小的e、d可以加快加密和验证签名的速度,而且所需的存储空间小,但是如果e、d太小,则容易受到小指数攻击,包括低加密指数攻击和低解密指数攻击。

通过独立随即数字对明文消息x进行填充,这样使得xe≡(modn)≠xe,可以有效地抗击小指数攻击。

4、对R SA共模攻击

在R SA公钥密码的实现中,为简化问题,可能会采用给每个人相同的n值,但不同的指数值e和d。这样做的问题是,如果同一信息用两个不同的指数加密,这两个指数是互素的,则不需要任何解密密钥就能恢复明文。

设m是明文,两个加密密钥分别为e1,e2,共同的模数为n,两个密文为:

由于e1,e2是互素的,有扩展的E culidean算法可以找到r和s,使之满足

假设r是负数(其中必有一个为负数),再次使用E culidean算法可以计算出c1-1,故可以得到

即密码分析者知道n,e1,e2,c1和c2,则可以恢复出明文m。

5、关于R SA算法的明文部分信息安全性

攻击者通过获取明文消息的部分信息,进而可以破译或恢复整个明文信息。这就是R SA安全性的另一个重要方面,可以称之为比特安全性,即R SA算法中密文所泄漏的有关明文二进制表示的某些有效位的部分安全性。

关于R SA体制部分信息安全性的最好结果是由W.Aiexi等人得出的。W.Aiexi等人证明了任何由密文E(x)(E为加密函数)以不小于1/2+1/ploy(log N)的正确概率猜对最末有效位的算法F,都可诱导出一种由密文E(x)破译出x的相对于算法F的非确定多项式算法,即所谓的最末有效位1/2+1/ploy(log N)安全性。

三、提高RSA安全性的必须手段——正确选择参数

在使用R SA算法构造密码系统时,为了保证R SA体制的安全,在大素数生成的基础上,还必须仔细选择各参数。R SA的主要参数有三个:模数n,加密密钥e,解密密钥d。

1、模数n的确定

选择合适的n是实现R SA算法的重要环节。一般地,模数n的确定可以遵循以下几个原则[18]:

(1)p和q之差要大。

当二者差距很小时,当已知n的情况下,可预先估计p和q的平均值为即n被分解。

(2)p-1和q-1的最大公因子应很小。

(3)p和q必须为强素数。

(4)p和q应大到使得因子分解n为计算上不可能。

由于若能因子分解n,则R SA即能被破译,因此必须足够大,使得因子分解n在计算上是不可行的。因子分解问题为密码学最基本的难题之一,如今,因子分解的算法已有长足的进步,但仍不足以说明R SA可破解。基于安全性考虑,实际应用中所选择的素数p和q至少应该为100位以上的二进制数,相应的模数n将是200位的二进制数。

模数n一般性原则:临时性384位(二进制),经过努力可以破解;商用512位(二进制),专业组织可以破译;军用1024位(二进制),十年内难以破译。电子邮件安全协议PG D使用了最大长度的R SA密钥,2047位(二进制)。随着计算能力的提高和分布式运算的发展,安全密钥的长度将是动态增长的。

2、e的选取原则

在R SA算法中,e和φ(n)互质的条件容易满足,如果e的选择过小,加/解密的速度快,也便于存储,但是会导致安全性问题。

一般地,e的选取有如下原则:

(1)e不可过小。一般选择e为16位的素数,可以有效防止攻击,又有较快速度。

(2)e应选择使其在modφ(n)的阶为最大,即存在i,使得ei≡1(modφ(n)),i≥(p-1)×(q-1)/2,可以有效抗击攻击。

3、d的选取原则

一般地,d要大于。在许多应用场合,常希望使用位数较短的密钥以降低解密或签名的时间。例如IC卡应用中,IC卡CPU的计算能力远低于计算机主机,长度较短的d可以减少IC卡的解密或签名时间,而让较复杂的加密或验证预算(e长度较长)由快速的计算机主机运行。一个直接的问题就是:解密密钥d的长度减少是否会造成安全性的降低?很明显地,若d的长度太小,则可以利用已知明文M加密后得C=M e(m odn),在直接猜测d,求出Cd(modn)是否等于M。若是,则猜测正确,否则继续猜测。若d的长度过小,则猜测的空间变小,猜中的可能性加大,已有证明当时,可以由连分式算法在多项式时间内求出d值。因此其长度不能过小。

结束语

依上所述,R SA的安全性依赖于大数分解的难度,那么因素分解技术、计算机能力的日益提高以及计算机并行技术的进一步发展将使得针对R SA的攻击变得更加的有效。鉴于类似分析,如何进一步提高R SA算法的加解密效率,以保证能够在用户可以接受的时间内提供用户更长更难破译的密钥进而保证用户信息安全将是今后较长一段时间内重要的研究方向。

参考文献

[1]王育民,刘建伟.通信网的安全.西安:西安电子科技大学出版社.1999,50-213

[2]赖溪松,韩亮,张真诚.计算机密码学及其应用.北京:国防工业出版社.2001,2-79

[3]杨子青.近世代数.北京:高等教育出版社.2003,1-177

[4]胡冠章.应用近世代数.北京:清华大学出版社.1999,1-213

[5]卢开澄.计算机密码学一计算机网络中的数据保密与安全.北京:清华大学出版社.2003,15-231

[6]Taher E lg amal.A Public Key Cryptosystemand a Sig nature Scheme Based on Discrete Log arithms.IE E E Transactions on InformationTheory,1985,IT31(4):469-472

RSA加密体制 篇2

引言

当今互联网经过多年发展丰富,已经深入社会生活的各个角落,逐渐提供了包括娱乐,资源共享,云存储,电子商务,远程教育等等服务,但是有一个功能是从互联网诞生之初,直到现在都是互联网服务的关键组成部分,那就是收发电子邮件,而且随着网络的普及,电子邮件由于其快捷、便利,易于管理等特点,愈发在工作和日常生活中发挥重要作用。但是,由于电子邮件本身不提供加密保护的服务,使其安全性受到较大威胁。

随着加密技术和网络安全意识的发展,现在可以利用RSA公钥加密体系的作为基础,适用PGP软件对电子邮件进行加密,来解决这一安全隐患。

RSA加密体系

RSA公开密钥密码体制。公开密钥密码体制就是使用不同的一对密钥,分别作为加密密钥和解密密钥,而用其中任何一个密钥推导出另一个密钥都是不可行的

在这个密钥体制中,加密密钥是公开信息,而解密密钥是需要保密的。此外,加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的,但却不能根据PK计算出SK。

正是基于这种理论,1978年出现了著名的RSA算法,它通常是先生成一对RSA密钥,其中之一是保密密钥,由用户保存;另一个为公开密钥,可对外公开,甚至可在网络服务器中注册。为提高保密强度,RSA密钥至少为500位长,一般推荐使用1024位。这就使加密的计算量很大。为减少计算量,在传送信息时,常采用传统加密方法与公开密钥加密方法相结合的方式,即信息采用改进的DES或IDEA对话密钥加密,然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后,用不同的密钥解密并可核对信息摘要。

RSA算法是第一个能同时用于加密和数字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从提出到现今的三十多年里,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。

但是,RSA算法毕竟只是一种算法理论,将其用于实际应用,还需要借助于相关的应用软件,而PGP软件正是一个基于RSA公钥加密体系的加密软件。可以提供包括数据加密、数字签名、电子邮件加密等功能,而且简便易用,安全性高,广泛的用于重要文件、电子邮件等内容的加密传输。通过使用PGP可以完善的保证信息传输的安全要求,即机密性、完整性、真实性和不可否认性。

本文就是探讨,在RSA算法的理论指导下,具体使用PGP软件,来实现电子邮件的数字签名,从而防止邮件内容被篡改。

数字签名,和生活中的个人签名类似,但是相比真实的签名,数字签名具有更高的安全性和不可伪造性。数字签名技术是非对称密钥加密技术的应用,在使用过程中,发送方以要发送的数据为基础,生成一个消息摘要,该消息摘要包括了数据的时间、发布者等关键信息,然后发送方用自己的私钥加密该摘要,这样就形成了数字签名,再将该数字签名与数据发送出去,接收方收到数据以及数字签名文件后,用发送方的公钥对数字签名解密,得到新的消息摘要,将该摘要与数字签名里的消息摘要对比,就可以验证出此消息的真实性,最终达到对原始数据的验证,辨明真伪的目的。

实现过程

1PGP软件的安装

1.1正常安装PGP,按提示重启

1.2重启后,按照提示向导进行注册,此步为以后生成密钥做准备

1.3注册成功后,按照邮件帐户创建密钥对,该密钥对可在PGPKeys中查看到

2导出签名公钥

此步的目的是在两台主机之间互换公钥,建立信任关系后再相互通信

2.1导出公钥

在刚生成的密钥上右击,选择Export选项,可将其导出到指定目录,然后将其用电子邮件发送给对方

2.2导入对方公钥

接收方收到对方公钥后,双击添加进自己的密钥环中,并用自己的私钥对该公钥签名后,就可以用来加密邮件,进行通信了

3使用PGP和电子邮件客户端发送加密邮件,此处以Outlook Express为例

3.1发送加密并签名的邮件

使用Outlook Express编辑完邮件内容后,选择加密图标加密邮件正文,并对内容签名。注意此时用来加密的公钥是接收方的,而用来签名的私钥是发送方的。然后点击“发送”按钮。

3.2接收方验证邮件

接收方通过邮件客户端收到对方的邮件后,内容是加密的密文,此时需要惦记Decrypt&Verifu按钮解密,要注意解密所用的私钥是接收方的。

解密成功后,才能看到邮件正文内容。

总结

浅论基于RSA的加密算法 篇3

1 RSA的研究意义

产生网络信息安全问题的根源可以从三个方面分析:自身缺陷, 开放性和人的因素。

首先, 网络自身的安全缺陷主要体现在协议和业务的不安全上, 而协议的不安全主要原因是:一方面互联网起源的出忠是进行学术交流和信息的沟通, 并非商业目的而导致缺乏安全的总体构想和设计。另一方面是协议本身的泄漏。然而业务上的不安全表现在错误信息或业务本身的不完善。

其次, 网络的开放性体现在业务是基于公开的协议等原因。

最后, 人的因素才是最主要的因素, 表现为三方面:人为的无意失误, 黑客攻击, 管理不善。

随着这些问题不断的出现, 网络信息安全的意义也就体现出来了:从大的方面说, 网络信息安全关系到国家主权的安全、社会的稳定、民族文化的继承和发扬等。从小的发面说, 网络信息安全关系到公私财产和个人隐私的安全。因此, 密码学在网络信息安全中发挥的重要性也体现了出来。密码技术是实现网络信息安全的核心技术, 是保护数据最重要的工具之一。最常用的技术有:数据加密标准DES、高级加密标准AES、RSA算法、椭圆曲线密码算法ECC、IDEA算法、PGP系统等。

2 RSA的国内外发展趋势

2012年2月27日到3月2日在美国旧金山举办的RSA信息安全大会上, 网络安全, 云安全仍然是时下最为热点的话题。而其中云安全仍是2010、2011和2012年度最耀眼的新星, 围绕着云安全与网络安全提出了许多问题以及解决的方法, 比如:云安全需要急迫解决的安全隐患;云计算是转变安全交付方式的机会;云安全将成为2010安全领域趋势;安全专家看RSA大会焦点:云安全准备出发;RSA大会三大主题:网络计犯罪, 云计算, IT消费;安全风向标:品味RSA 2012信息安全大会;RSA2012主题揭秘:伟大的密码比剑更有力;新的安全威胁面前需要新的安全架构。

另外, 前人针对RSA所做的一些研究, 比如:RSA算法的改进;基于AES与RSA混合加密策略的硬盘分区加密技术;一种基于RSA的加密算法;RSA密码算法的研究与改进实现;RSA加密算法的研究及应用等等。

3 RSA公钥密码

3.1 RSA算法简介

公开密码算法与其他密码学完全不同, 它是基于数学函数而不是基于替换或置换。与使用一个密钥的对称算法不同, 公开密钥算法是非对称的, 并且它使用的是两个密钥, 包括用于加密的公钥和用于解密的私钥。公开密钥算法有RSA、Elgamal等。

RSA公钥密码算法是由美国麻省理工学院 (MIT) 的Rivest, Shamir和Adleman在1978年提出来的, 并以他们的名字的有字母命名的。RSA是是第一个安全、实用的公钥密码算法, 已经成为公钥密码的国际标准, 是目前应用广泛的公钥密码体制。

RSA的基础是数论的Euler定理, 其安全性基于大整数因子分解问题的困难性, 公私钥是一对大素数的函数。并且该算法已经经受住了多年深入的密码分析, 虽然密码分析者既不能证明也不能否地RSA的安全性, 但这不恰恰说明该算法有其一定的可信度。

3.2 加解密算法描述

3.2.1 RSA利用了单向陷门函数

如图1所示。

3.2.2 RSA密钥对生成与加解密

3.2.2. 1 RSA密钥对的生成

首先, 选取两个互异的大素数, 令其为q和p (保密) , 并且为获得最大程度的安全性, 要让q与p相同长度。然后计算乘积 (公开) :

其次, 随机选取加密密钥e, 使其与j) (n互素, 即ne j1) ) (, gcd (=, 然后用扩展的Euclid算法计算密钥d:

即

注意, e和n可以公开, 两素数p与q不再需要, 可销毁, 但不能泄露。

3.2.2. 2 RSA加解密算法

1) 加密过程

首先, 将明文比特分组, 使其每个分组对应的十进制数小于n, 即分组长度小于log2n, 后对每个明文分组mi做加密运算, 其具体步骤如下:

获得其接收方公钥 (e, n) ;

把消息M分组为长度L (L

3) 利用加密算法计算出密文C=c1c2....ct (公式如下) ; (公式如下) ;

将密文C发送给对方。

2) 解密过程

(1) 接收方收到密文C并把密文按照长度为L分组得C=c1c2....ct ;

(2) 利用私钥d和解密算法计算mi (公式如下) ;

(3) 得到明文消息M=m 1m2....mt。

3.2.3 加解密流程

如图2示。

3.3 RSA设计流程

如图3所示。

4 RSA的安全性

从理论上讲RSA的安全性完全依赖于分解大数的难度。但从技术上讲这是不正确的, 这只是一种推测。从数学上从未证明需要分解n才能从c和e中计算出m。用这种完全不同的方法来对RSA进行密码分析这还只是一种假想。而我并不认为这种新方法能让密码分析者推算出d。

当然, 也可通过猜测 (p-1) (q-1) 的值来攻击RSA, 但这种攻击没有分解n容易。

对那些仍持极端怀疑态度的人来说, 有些RSA的变型已经被证明和大数分解同样困难, 可参见, 它给出了从RSA加密的密文中恢复某一位与恢复出整个文本同样困难这一结论。

可以看出分解n是最显而易见的攻击方法。敌方手中有公开密钥e和模数n, 所以要找到解密密钥d, 就必须分解n。目前, 129为十进制数字的模数是能分解的临界数。所以, n应该大于这个数。

对于密码分析者而言, 他有可能尝试每一种可能的d, 直到获得正确的一个。这种穷举攻击并没有试图分解n更有效。

随着时间的推移, 人们声称已经找到了破译RSA的简单方法, 但是直到现在这些宣称还是站不住脚的。举例来说, 1993年Willian Payne的论文草案中提到了一种基于费尔马小定理的方法。很不幸, 它的速度仍然比分解模数要慢很多。

5 结束语

随着现代信息快速发展和网络的普及, 人们可以不用出门而了解世界大事和一些重要的信息。人们在这快速发展的今天再也没有属于自己的秘密, 因此我们要保护好自己的个人信息或者公司信息等等, 使隐私不被泄漏。所以信息的加密对我们来说非常的重要, 文件的加密可以用到各个领域, 它将要影响我们未来的生活。

摘要：信息是一种资源, 也是一种财富。在现代社会中, 信息处理和通信技术日益发展, 保护信息的安全, 特别是保护重要信息的安全, 已成为国际社会普遍关注的重大问题。该文对密码学、信息安全做了些简要的介绍, 并且简明扼要的介绍了信息安全的发展趋势, 重点阐述了RSA加解密算法。

关键词：计算机,密码,RSA算法

参考文献

[1]梁玲, 孔令德.RSA加密算法及一般攻击方法[J].太原大学学报, 2006 (2) .

[2]郑勇明, 杨亚新, 彭凤梅.RSA加密算法实现过程中数据溢出问题的一种解决方法[J].电脑知识与技术, 2006 (32) .

[3]王刚.RSA加密算法初探[J].科技信息:学术研究, 2007 (17) .

[4]柴井坤.RSA加密算法的实现及其细节问题的研究[J].黑龙江科技信息, 2007 (12) .

[5]步山岳.RSA加密算法分析与实现[J].信息安全与通信保密, 2007 (10) .

RSA数据加密算法分析与改进 篇4

关键词：RSA算法,CUDA,算法改进,模幂运算

随着工业4.0的迈入,中国制造2025[1]与之不谋而合,应运而生。人们正在全面进入“互联网+”时代,中国制造2025“互联网+工业”是“互联网+”的重要组成部分之一。现阶段通过大规模定制和网络协同配置的各方面资源、数据越来越多,制造业企业的实时数据安全处理、传输和储存的要求也会越来越高,保障数据的实时安全传输是这个时代迫切需要的。可以说加密技术无疑是保障数据安全传输的重要措施之一。RSA公钥密码是1978年Ron Rivest,Adi Shamirh和Len Adleman提出来的,源于三个作者的首字母,该算法是公钥加密的行业标准[2]。RSA加密算法理论基础是两个大素数相乘,然而计算机技术的进步使得比较短的RSA密钥可以被攻破。所以,RSA的密钥在不断的加长。我国山东大学的研究人员季凯和他的破解团队成员刘强等人宣布找到了这样的一种快速素因子分解算法,并且公布了算法,但是并没有得到最终的证实。现在国内外在RSA算法的研究上主要集中在算法的优化和程序的优化上,在算法优化方面主要集中在模幂和模乘的快速算法上,最传统的方法。就是把乘方后求模的运算改为一边乘方一边求模的运算,这种方法最大化避免大数的乘方运算。在一定程度上提高RSA的效率[3][4]。

现阶段应用最为广泛的加密算法有MD5算法、DES算法及RSA算法[6]-[8]。MD5是将任意长度的“字节串”变换成一个128bit的大整数,并且它是一个不可逆的字符串变换算法。DES算法把64位的明文输入块变为64位的密文输出块。而RSA算法是第一个既能用于数据加密也能用于数字签名的算法,RSA的安全性一直未能得到理论上的证明,但是它经历了各种攻击,至今未被完全攻破。较之MD5、DES算法,RSA算法的安全性更高,它的安全性基于数论中的大素数分解,该体制是采用足够大的整数作模数。但是大整数分解问题运用了大量的模乘和幂运算时间都比较长,所以RSA密码体制有显著的缺点就是运算效率低下,运算时间过长等缺点。那么提高RSA的算法效率是研究RSA密码体制的重点。

在1976年,W.Diffie和M.E.Hellmam发表了具有划时代意义的“密码学的新方向”一文,提出了公钥密码体制思想,为近代密码学的发展指明了方向。它的出现是密码学研究领域中的一项重大突破,也是现代密码学诞生的标志之一[9]。本文针对物联制造数据的安全快速传输问题,提出了对RSA算法的改进。首先对非对称加密算法RSA进行了原理分析,进而提出了算法的改进和实现。

1公开RSA加密算法

RAS算法是现今普遍使用的一种公开秘钥算法,其本质上是一种基于因数分解的非对称加密算法,其核心原理就是利用两个素数[10]。包含:一个是公钥以及一个是私钥,公钥是唯一解密通过私钥加密的密文,同时,私钥也是唯一解密通过公钥加密的密文,那么这就解决了数据的在传输过程中由于密钥的丢失,导致安全性受到威胁的问题。其加密算法流程如下:

从上述流程中不难看出中不难看出传统的RSA算法采用的公钥是n=p*q;并通过指数e二进制化后迭代,然后求模运算。

2 RAS算法的优化

2.1 RSA算法优化原则

由于传统的RSA的安全性依靠于算法过程中的大素数的因子分解的难度,也就造成了该算法采用的幂指剩余计算太耗时(在加密解密过程要计算大整数模幂乘)[11]。优化原则:(1)提高安全性,最大素数p和q至少应该是在100位以上的十进制数;(2)e的适当减小会加快解密速度,但是太小会威胁安全性。

2.2优化RSA算法

2.2.1多因子优化

利用多个素数因子对算法进行加速,此处选取三个素数因子,可以降低素数选取需要的时间,通过中国剩余定理[12]得出适当的减少素数的位数,可以降低计算量。那么基本算法描述如下:

首先选择三个保密大素数:p、q及r。计算n=p*q*r,φ(n)=(p-1)(q-1)(r-1),φ(n)为欧拉函数,选择整数e,有gcd(φ(n),e)=1,计算d*e=1 modφ(n),以{e,n}为公开钥,{p,q,r}为密钥,与传统RSA相比较,若明文m大于n,则需将m分块使得每一块数据都小于n-1,进而进行c=m^emod n。

2.2.2幂指运算优化

传统的RAS算法指数e的比特序列长度很大,需要在计算过程中多次迭代,因此找出最短的指数序列减少迭代次数是加速该算法的手段之一。那么,采用将指数e进行2^k进制化的方式达到加速算法的目的。

对于指数e可以用(2)等式表示出来:

那么在余数运算中,形如g^emod(m)可以如下表示:

(6)式中n为e被2k进制后的序列,其中)m表示取模运算。计算geimod(m)时,需从ge0mod(m)到ge2k-1mod(m)的所有值,伪代码算法描述如下:

上述共完成了2^k次迭代运算,接下来要进行幂剩余和乘通余运算,此步需完成n次迭代次数,其伪代码如下:1.C=1,i=n-1,

改进后算法流程图如下:

3改进RSA算法实现

3.1改进RSA模幂单元分析

首先输入明文M,然后通过C=m^e modn计算密文C,计算密文向量X=(x1,1….,x1,k,x2,1,…,x2,k,x3,1,…,x3,k),其中Xi,j=Cei,jmodn(0<i<4,0<j<k+1)。

进而通过中国剩余定理解密,计算

其中d1,j值已知,d2,j,d3,j在密码生成算法中可以得出。在计算d=e-1modφ(N)的同时计算Wp=(qr)p-1mod n,Wq=(pr)q-1mod n,Wr=(pq)r-1mod n,可以计算出明文M=(MPWp+MqWq+MrWr)mod n。故可以将大数模幂运算分解成多个小的模幂运算,然后基于GPU模式加速算法。其流程如下:

3.2 基于CUDA的算法实现

采用CUDA[13][14](Compute Unified Device Architecture)对改进RSA算法的实现,CUDA是一种由NVIDIA推出的通用并行计算架构,这一编程模型基于GPU,GPU相对于CPU而言有计算密度高、低耗能的优势,并且适用于大规模数据并行的通用计算。GPU提供了健全的储存器系统,合理的分配决定了算法和应用性能,所以将大素数p、q、r及密文C作为整个运算中的输入参数,这些参数是整个运算过程中的重要参数,在运算中需要将其置于全局储存器中,并将模幂单元与其集成。以下是基于CUDA框架的RSA改进算法的线程组织结构图:

3.3 具体实现方法

基于CUDA模式,采用NVIDIA Ge Force GTX960测试改进算法性能,并与传统BR算法和2K进制算法进行比对,GTX960包含1024个流处理器单元,核心频率是1051MHz,显存频率是7012MHz,支持2048M GDDR5显存,其显存宽带为232GB/s。在改进的RSA算法中,将关键操作步骤大整数模幂运算转移到GPU上实现计算,首先求出各个线程块内数值,然后保存在数组W[y-1][0]中,我们定义W[y-1][z],(1≤z≤2)为模幂运算单元乘积,那么有Mp=W[0][0]*N[1][0]*…N[y-1][0],Mq=W[0][1]*N[1][1]*…N[y-1][1],Mr=W[0][2]*W[1][2]…W[y-1][2]。各个独立的模乘单元运算可以参考文献[15]基于montgomery算法实现。

具体内核定义的代码如下:

4数据的验证分析

基于物联制造实验室,运用由NVIDIA公司开发的Ge Force GTX960对采集的数据进行验证,首先对改进算法的加密过程进行了数据分析如下:

基于CUDA对RSA算法加密进行数据验证。最下方的曲线为所求曲线,从图中可以得出最下方的在加密过程中完全优于另外曲线。所以在采用三因子素数及幂指优化算法可以在很大程度上提高加密效率。

下面将基于CUDA模式下对大整数模幂的运算性能对三种算法分别进行对1024和2048位从运算次数进行解密分析:

改进RSA算法的解密过程基于CUDA完。在CUDA模式下,令yy=={{22,,112288,,551122,,11002244,,22004488……}}为运算次数。yy值的增加会使并行的线程块增加,运算的速度会越来越快。这里达到2200448位运算依然流畅进行,但是随着位数的时候会由于GGPPUU本身的最大计算能力而下降。因为线程块越多意味着对储存器的访问次数越多,从而降低计算能力。但是从2张比较图可以看出改进后的RRSSAA算法(最下方曲线)的解密效率同样很高。

5结束语

高效加密预计算RSA算法实现方法 篇5

1978年MIT(Massachusetts Institute of Technology)三位年青数学家R.L.Rivest,A.Shamir和L.Adleman用数论构造双钥密码的方法,称为RSA体制[1]。它既可用于加密、又可用于数字签名,易懂且易于实现,是目前仍然安全并且逐步被广泛应用的一种体制[2,3]。国际上一些标准化组织ISO、ITU、及SWIFT等均已接受RSA体制作为标准,Internet采用的PGP(Pretty Good Privacy)也将RSA作为传送会话密钥和数字签名的标准算法[4,5]。在现实应用中,密码体制一方面需要保证安全性,另一方面需要保证运算速度[6,7]。本文提出一种随机预先计算RSA算法,通过参数选择、加密、解密三个步骤,并在解密过程中预先计算,不仅可以保证算法安全,同时比原始RSA算法加密速度要快的多。

2 原始RSA算法原理

2.1 原始RSA算法实现方法

RSA算法可通过如下三个步骤实现:

⑴、参数选择:独立地选取两大素数p1和p2(各512bit的数),计算n=p1×p2,其欧拉函数值ϕ(n)=(p1-1)(p2-1),随机选一整数e,1≤e<ϕ(n),(ϕ(n),e)=1(因而在模ϕ(n)下e有逆元),d=e-1 modϕ(n),公钥为n,e;私钥为d,(p1,p2不再需要,可以销毁);

⑵、加密:将明文分组,各组长1024比特;明文集Az={m:1≤m加密得到密文c=memod n=""> 加密得到密文c=memod>

⑶、解密:m=yd mod n,通过上式得到解密结果。

2.2 原始RSA加解密时间复杂度分析

在RSA体制使用过程中,通常情况下选择

加密算法用16次模n平方运算和1次模n乘法运算。解密算法用一次模n指数幂运算。

3 随机预计算RSA

3.1 预计算RSA算法实现方法

预计算RSA算法可通过如下三个步骤实现:

⑴、参数选择:独立地选取两大素数p1和p2(各512bit的数),计算n=p1×p2,其欧拉函数值ϕ(n)=(p1-1)(p2-1),随机选一整数e,1≤e<ϕ(n),(ϕ(n),e)=1(因而在模ϕ(n)下e有逆元),d=e-1 modϕ(n),k1=2,k2=3,k3,k4,k5,k6:,公钥为n,k1,k2,k3,k4,k5,k6;私钥为d,(p1,p2不再需要,可以销毁);

⑵、加密:将明文分组,各组长1024比特;明文集Az={m:1≤m加密得到密文c=(c1,c2,c3);其中,< p=""> 加密得到密文c=(c1,c2,c3);其中,<>

,因此

⑶、解密:当解密者接收到密文c=(c1,c2,c3),可能过公式m=cd mod n得到解密结果。

通过分析可知,随机的k3,k4,k5,k6组成了原始密码的公钥e,其它的参量和原始的相同,因此没有改变原始密码的安全性。

3.2 预计算RSA加解密时间复杂度分析

加密过程同样选择,其中e16=e0=1;本方案可以预先计算,因此在线加密只需计算c1=m2⋅R1modn,c2=m3⋅R2modn,此加密算法只用4次模n平方运算就可以完成整个加密。

解密过程中可以预先计算,由文献8可知,三次模n指数幂运算可以转化成一次模n指数幂运算。

3.3 计算复杂度比较结果

由表1可知,虽然预计算RSA和原始RSA的解密时间复杂度相当,但是预计算RSA的加密只需4次模n乘法运算,比原始RSA算法的17次模n乘法运算少的多,这样在加密过程很大程度上提高了加密速度。

4 结论

在RSA算法的现实应用中,由于加密算法的效率不高,本文提出了一种预计算RSA算法,把公钥拆成随机的4个分量,通过分析,它不仅不会影响安全性,同时很大程度上提高了加密速度,有利于实践应用。

参考文献

[1]Rivest,R.;A.Shamir;L.Adleman."A Method for Obtaining Digital Signatures and Public-Key Cryptosyst-ems".Communications of the ACM21(2):120–126

[2]Smart,Nigel P.Errors matter:Breaking RSA-based PIN encryption with thirty ciphertext validity queries[C].Lecture Notes in Computer Science(including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),2010,5985:15-25

[3]Sarkar Santanu,Maitra Subhamoy.Cryptanalysis of RSA with more than one decryption exponent[C].Information Processing Letters,110(8-9):336-340

[4]张亚玲,张璟,王晓峰.一个高效的基于身份和RSA的紧致多重数字签名方案[J].电子与信息学报,2008,30(9):2246-2249

[5]姚国祥,林良超.RSA密钥对高效生成算法[J].计算机工程,2007,33(20):148-152

[6]张宝华,殷新春.RSA密码算法的安全及有效实现[J].中山大学学报(自然科学版),2008,47(6):22-26

[7]徐文华,贺前华,李韬.基于强RSA假设的数字签名方案[J].华中科技大学学报(自然科学版),2008,36(12):24-26

RSA加密算法中MPI的应用 篇6

MPI(消息传递接口Message Passing Interface),MPI是一个库,而不是一门语言,具有巨大的数值计算和数据处理能力,提供高性能并行计算,即通过把一个大的计算问题分解成许多彼此独立且有相关的子问题,然后把他们散列到各个节点机上并行执行从而最终解决问题的一种方法。并行计算的提示有效地改进了RSA加密算法的缺点。本文以RSA加密算法为出发点,通过MPI的应用,通过实验有效地证明了在RSA加密算法中MPI能够提升加密速度、降低容量需求,提高数据的安全性。

1 RSA加密算法

RSA(Ronald Rivist、Adi Shamir和Len Adlemar三人的名字共同命名)是一种应用较为广泛的公钥算法,也是他们开发出的第一个公钥密码体制,并在未来的20 多年时间内得到了充分肯定。RSA是以分组的方式对明文进行加密,RSA密钥产生过程如下:

1它随机地选择两个大质数p和q(需保密);

2p*q=n;

3在任找一个数m,要求满足m<n且可与(q-1)*(p-1)互质;

4计算得到d=m-1mod[(p-1)*(q-1)];这里d是私密指数,m代表公开指数;

5获得公匙(n,m),私匙(n,d);

6删除p和q;

加密算法实现原理就是将明文数据分解成比n小的数据块用公开指数作乘方取模运算:c=memod n(其中m代表明文块,c代表密文块);解密过程恰恰相反:即把密文数据块依托私密指数进行乘方取模运算:m=cdmod n。网络攻击者有公匙:e和n,为了获得私匙d,则会对n行因数分解来获得p、q,最终算出d是最好的RSA攻击方法。若采用推断(p-1)(q-1)或直接穷举d则会慢很多。因此实现RSA加密算法的运行速度而且尽可能少耗费资源一直是待解决的问题。

2 并行计算环境MPI

MPI(Message Passing Interface)是一个消息传递编程标准,它是一个全球性质的参考标准。MPI的制定整合了几乎所有消息传递系统的优点,并在相关方面做了较大的改进和发展,最终获得一个为并行程序的开发使用的平台。MPI系统是一个由所有具有标准接口说明的消息传递函数所构成的函数库,MPI标准中定义了一组函数接口用于进程间的消息传递,通信的性能对基于消息传递的应用来说至关重要,若不全力实现MPI,造成通信开销会十分昂贵,程序并行将豪无放逐意义。MPI标准的制定仅解决了并行程序的可移性问题,而最为关键的问题是在为MPI实现的高效与否。

针对网络中已经确定带宽上限和延迟下限,不同的协议和API向用户提供的功能和性能不同。根据API、协议,可将带宽、延迟空间划分为以下五类:

①高延迟/窄带宽(存在较多拷贝和缓冲的标准TCP/IP协议栈)

②高延迟中等带宽改进的协议栈

③中等延迟中等带宽建立在相对较慢的驱动之上,采用无拷贝TCP/IP协议栈的MPI实现,如MPICH)

④ 低延迟/宽带宽(有硬件支持的优化了的MPI实现)

⑤超低延迟/窄带宽(主动消息,远程put/get)

在TCP/IP协议之上无法建立高速的MPI,为了实现MPI的高效,put/get协议往往会被人们所选择。

3 RSA加密算法中MPI的应用

由于RSA加密算法在实现时有一定的困难,结合并行计算环境MPI在并行处理方面的优点,提出对RSA加密算法进行改进,采用基于MPI的消息传递系统,实现算法运行的速度以及其安全性的提高。具体改进后的RSA算法实现如下:

RSA算法在实现过程中后继操作基本上都依赖于前一步的运算结果,因此在实现数据交换和通信过程中如果全部采用并行计算,往往导致系统开销消耗增大,实现起来相对较难,最终影响系统效率。鉴于以上问题在实现过程中建议采用更加实际的局部并行处理方法。即主要对随机产生质数过程、计算逆元的过程、欧拉函数的计算以及加密时的大数取模过程采用并行处理。RSA加密中有两个关键问题:

1)选定互质P和Q

判定素数,一般定义是:素数是除了能被1 和它本身整除而不能被其他任何数整除的数。用2到n-1这些数去除n,如果所有数除不尽,即判定n是素数,否则只要其中有一个数能整除,即判定n不是素数。该办法适用范围较小,对于判定大素数来说,则结果不可取,故对于大数(超过百位以上的整数)p和整数q(q<p),计算qp- 1mod p,如结果不等于1,p一定不是素数;若结果为1,则p不为素数的概率大约只有10-13。

2)计算逆元

逆元算法:如果ab≡1(modm), 则称b是a的模m逆,记作a的模m逆是方程ax≡1(modm)的解,两个数互质一定有逆元。求逆元可以使用辗转相除法,但是只有两个数都是质数的时候才有逆元。逆元计算相对困难,本文计算逆元以欧几里得算法为例。

分析发现,有4 个调用单元在系统中被确定,通过单元模块的有效组合来实现系统。建立系统时,为了让消息传递及计算简便,每一位数据存放都采用数组,每个整型数组的一位都存放一个需要计算的数的每一位。以系统模块中2 个随机大素数的乘积为例:

在实现大数相乘时,通过MPI消息传递的方式将乘数和被乘数发送给每1个进程上,接着设置1个步长,用于每台机器在并行计算时计算相应位。以ABCD×EFGH为例。

第一阶段:初始化

经过消息发送,使得每个进程中都存放了乘数和被乘数ABCD及EFGH。

第二阶段:计算

设定MPI步长,步长等于乘数的位数/开设的进程数所得的商。本例为4 除以2 得2,即步长为2. 具体计算过程是:用第个进程与2求模余1的位数上的数,第2个进程计算与2求模余0的位数上的数,单个进程单独计算后得到各自的结果。

第三阶段:汇总

通过MPI消息将单个进程的结果发送至1 号进程完成汇总,接着进行进位的调整,得到最终结果。

以下为MPI主要代码:

其他几个功能函数的设计思想与上述类似,就是充分利用MPI在多台机器或多个进程中的消息传递机制,将本来需要在台机器上或1 个进程上完成的作业,分发到多台机器或多个进程中,提高整体加密速度。如图1所示算法流程图。

4 结论

在现实的工作中,往往需要处理较多的保密数据,在网络上进行传输时必须充分考虑其安全性。MPI在为运行并行程序和用户构造时提供了便利的程序开发平台,特别是其采用的消息传递机制,适应于各种同构或异构网络平台。通过在RSA加密算法中MPI的应用,不仅达到了高效、准确、安全的数据传输、数据加密等要求,而且对于MPI的数据传送的快速、资源利用率的提高等优点也充分得到体现。

摘要：RSA加密算法在进行复杂判断和大数运算时,计算时间往往花费较多,对计算机的运行速度、存储容量等方面具有较高的要求。MPI能够提供较快的数值计算和数据处理能力,提供高性能并行计算。该文通过在RSA加密算法中MPI的应用,通过实践证明MPI并行计算可以改进RSA算法,提高加密速度、减少容量需求等。

RSA加密体制 篇7

这些图像加密技术都是对数字图像的所有数据进行处理,相当来说是需要很慢的。为了解决这个问题,本文提出一种基于RSA和图像关键信息的加密技术算法,该算法只对数字图像的极少部分数据(图像关键信息)进行处理,先对要加密的数字图像进行关键信息提取,然后利用加密性能优秀的RSA对图像关键信息进行加密处理,解决了对数字图像全部数据进行处理而速度慢的问题。实验结果显示该算法对现有几乎所有的数字图像格式都是有效的且速度快,较好地解决了数字图像实时加密速度慢的问题。

1 RSA加密算法

RSA加密算法[5]是一种公钥加密体制,也是一种非对称加密体制,即加密密钥和解密密钥不同,要实现RSA加密算法,首先必须产生密钥,其实现过程如下:

1)随机生成两个大的素数p,q。并计算出n=pq和∮(n)=(p-1)(q-1)。

2)产生一个随机整数E,使得1

3)根据αβ≡(1 mod∮(n))原理求整数D,使得1

4)加密,取明文M,计算M E(mod∮(n)),得到密文C,即C=ME(mod∮(n))。

5)解密,为加密的一个逆过程,即M=CD(mod∮(n))。

在算法实现过程中,(E,∮(n))为公钥,(p,q,β,n)为私钥,关键的是随机素数的产生不仅要保证p,q两个素数足够大且要求差值p-q不宜太小,这样才能确保加密算法的安全性。

2 图像关键信息

图像文件的存储结构通常称为图像文件结构(File structure of images),一般的图像文件结构主要都由文件头、文件体和文件尾三个部分组成。文件头的主要内容包括产生或编辑该图像文件的软件的信息以及图像本身的参数。这些参数必须完整地描述图像数据的所有特征,因此是图像文件中的关键数据,在文中称之为图像关键信息。当然,根据不同格式的图像文件,有的参数是可选的,如压缩算法,有的文件无压缩,有的文件可选择多种方法压缩;有的参数是必选的,如图像文件格式标识。文件体主要包括图像数据以及颜色变换查找表或调色板数据,在文中也把这些数据称之为图像关键信息。这部分是文件的主体,对文件容量的大小起决定作用。如果是真彩色图像,则无颜色变换查找表或调色板数据,对于256色的调色板,每种颜色值用24 bit表示,则调色板的数据长度为256×3(Byte)。文件尾一般包含一些用户信息。文件尾是可选项,大部分的文件格式不包括这部分内容。由于文件体数据量较之文件头与文件尾要大得多,而文件体中颜色变换表或调色板所占用的空间一般也比图像数据小得多,因此图像文件的容量一般能够表示图像数据的容量(压缩或无压缩)。

3 基于RSA和图像关键信息的加密技术

3.1 加密技术的加密算法

基于RSA和图像关键信息的加密技术的加密算法具体描述如下:

步骤1:输入要加密的图像D;

步骤2:从图像D中提取图像关键信息M;

步骤3:输入加密的密钥K,通过RSA加密算法对图像关键信息M进行加密,得到图像关键信息密文C;

步骤4:把图像关键信息密文C写入到要加密的图像D中,得到加密后的图像W;

步骤5:保存加密后的图像到文件,以便发布和传输。

3.2 加密技术的检测和解密算法

步骤1:打开需要解密的图像文件,得到需要解密的图像W;

步骤2:从加密的图像W中提取加密后的图像关键信息C;

步骤3:输入解密的密钥P,通过RSA解密算法对加密后的图像关键信息C进行加密,得到图像原始的关键信息M;

步骤4:把图像原始的关键信息M写入到要解密的图像W中,得到加密后的图像D;

步骤5:保存解密后的图像D到文件,以便查看和浏览;

4 算法的性能分析

算法测试在P4 2.9GHz×2,DDRAM 1024M,Windows XP Professional 5.1环境中进行,实验速度和效果都很好。

虽然RSA加密和解密算法在进行数据加密时速度都不快,但由于该算法只对图像的关键信息进行RSA加密,要处理的数据相当图像数据来说是很少的,因此加解密速度很快,且图像的关键信息是图像显示的必备数据,不能有任何错误,否则是不能显示图像,算法通过少量的图像关键信息的加密,修改了图像显示的必备数据,从而达到不能正常显示图像而实现图像加密的目的,且实验结果符合预期目标。理论上分析,根据图像格式的不同,其图像关键信息数据有差异,但差距不到,一般都是在32~80个字节,而实际图像的数据却很大,一般都是几十、几百、几千个字节甚至更大,因此算法需要处理的数据相对图像数据本身来说是很少的,大约在千分之一甚至更少,因此理论分析该算法比普通的图像加密算法速度要提高上千倍或更高。

5 结论

在现在的网络年代理,为了解决图像的快速实时的传递和重要图像的版权保护,普通的图像加密算法虽然很成熟,但都是对数字图像的所有数据进行处理,速度都不快,或实时性不好。为了解决这个问题,本文提出一种基于RSA和图像关键信息的加密技术算法,该算法只对数字图像的极少部分数据即图像关键信息进行处理,先对要加密的数字图像进行关键信息提取,然后利用加密性能优秀的RSA对图像关键信息进行加密处理,解决了对数字图像全部数据进行处理而速度慢的问题。实验结果显示该算法对现有几乎所有的数字图像格式都是有效的且速度快,较好地解决了数字图像实时加密速度慢的问题,且从理论分析和实验验证,算法速度都是很好的,完全符合预期目的,该算法在有实时要求且需要版权保护的应用中是值得推广的。

摘要：针对数字图像的版权保护问题和现有加密技术速度慢和实时性不高的特点,提出了一种基于RSA和图像关键信息的加密技术算法。该算法先对要加密的数字图像进行关键信息提取,然后利用加密性能优秀的RSA对图像关键信息进行加密处理,解决了对数字图像全部数据进行处理而速度慢的问题。实验结果显示该算法对现有几乎所有的数字图像格式都是有效的且速度快,较好地解决了数字图像实时加密速度慢的问题。

关键词：图像关键信息,RSA,加密技术,数字图像

参考文献

[1]邓新文,王国才,李娟.一种安全图像小波域密写方案[J].计算机工程与应用,2007,43(36):1526-1529.

[2]齐东旭.矩阵变换及其在图像信息隐藏中的应用[J].北方工业大学学报,1999,11(1):24-28.

[3]B Schneier.应用密码学——协议、算法与C源程序[M].北京:机械工业出版社,2000:104-158.

[4]盛苏英,吴新华.一种混沌图像加密算法的研究与改进[J].微电子学与计算机,2010,27(10):61-64.