背包公钥密码

2024-07-02

背包公钥密码（精选七篇）

背包公钥密码篇1

自1978年Merkle和Hellman首先提出了一个现在称为M-H背包体制的密码算法之后, 基于背包的密码一直是密码研究者研究的热点, 研究人员设计出许多基于背包问题的密码方案。虽然M-H背包方案以及它的一些改进算法在20世纪80年代初被Shamir等人给破译了, 但随后仍有不少其他改进方案被提出来。既然基于背包的公钥密码体制不安全, 为什么大量的研究人员还在进行研究, 提出改进方案呢?分析其中原因, 发现有三点:第一, 背包密码体制加解密非常迅速, 实用性很强;第二, 背包密码本身是基于背包问题的, 背包问题的NPC (NP完全性) 特性使其完全可以应用到加密体制中去;第三, 现实中有很多资源受限制的应用环境, 比如内存受限, 时间受限等等, 这些都为背包密码提供了很好的实用环境。所以, 背包密码体制的研究者依然层出不穷, 他们都想找到一种相对比较安全的改进算法来实现背包密码算法的安全应用。

1 王氏密码的改进算法

1.1 算法介绍

丁燕艳等人在文献[1]中对王氏密码进行了安全性分析, 说明了仅通过模乘运算与中国剩余定理构造的背包公钥算法都是不安全的, 原因在于不能充分隐藏初始序列的冗余, 存在安全漏洞。他们提出了要引进扩散技术, 以分散初始序列的冗余度, 使破译者难以利用, 从而提出了王氏密码的一种改进算法。

1.2 算法描述

1.2.1 密钥生成算法

(1) 取超递增初始序列:

(2) 选互素的正整数w和m, 满足公式 (1) :

(3) 运用乘数w, 对序列B中的bi进行模乘运算, 将B转换成D序列:

其中di (i=1, 2, …, n) 最大长度可以为n+1位。

(4) 对di进行不对称分组:di的长度以n+1位计 (如高位不足, 以0计) , 左起在第j位分为左右两部分, 形成ui和vi位数分别为j位和n+1-j位, 其中:

(5) 选整数t, 满足:

(6) 选互素的正整数p和q, 满足:

运用中国剩余定理, 生成公钥A (28) (a 1, a 2, …, a n) 。

私钥为:p, q, t, w-1, m。

初始序列B作为固定值嵌入在算法中。

1.2.2 加密算法

二进制明文x= (x 1, x 2, …, xn) , ix为0或1, 被加密为:

1.2.3 解密算法

再运用超递增初始序列B计算得到明文。

2 安全性分析

文献[1]中提到必须猜测到公式 (5) 中的t获得公式 (3) 中的D序列后才能运用格规约攻击, 本文考虑的是在没有得到D序列的情况下, 只通过已知的公钥和密文来构造格, 根据文献[8]的方法进行启发式格规约攻击。

由于这类算法都是基于背包的, 它的密文都是∑ai xi的形式, 明文都是0或1, 所以密文与明文之间的关系总可以模拟出来, 而LLL算法正可以进行这种模拟, 例如构造一个格:

由上面构造的格L的形式, 进行LLL规约后, 如果存在首项为0, 尾项为1的规约基, 必定有 (这里的k1, k 2, …, kk是规约过程中的系数) 。若中间项为1时, 对应行的系数为1;若中间项为-1时, 对应的行的系数为0, 则此时K= (k 1, k 2, …, k k) 就是我们要得到的明文序列。

文献[1]中还提出了一种对何-卢背包公钥密码系统的改进算法, 我们依然可以根据上面的启发式格规约攻击来攻击它, 通过此方案的算法描述得到一组公钥与明文, 从而得到密文, 再构造格, 用LLL算法来直接恢复它的明文。成功的比例比较大, 虽不能百分之百攻破, 但其不安全性也显而易见了。

为了进一步说明文献[1]中的改进算法仍然是不安全的, 下面我们对王氏密码的改进算法进行攻击实验, 以实验数据来证明这一点。

3 格规约攻击方法

3.1 格规约攻击的算法设计

(1) 根据算法描述可以求出一组公钥然后取一随机明文从而得到一组密文

构造格L如下:

(2) 调用LLL算法, 得到格L的规约基B。

(3) 在规约基B中寻找首项为0, 尾项为1, 中间项为1或-1的规约基, 如公式 (15) 所示:

(4) 如果在规约基B中找到这样的向量, 则输出明文X= (x1, x2, …, xk) , 数学表达如公式 (16) :

分析此启发式格规约攻击所需要花费的时间:

调用LLL算法需要的时间为实际的运行时间远远小于这个时间, 而扫描找到需要的那个向量所要花费的时间为O (n2) , 所以此启发式格规约攻击所需要花费的时间在多项式时间内, n=1024的时候大约6个多小时就可以得到结果。

3.2 格规约攻击计算实验

为了进一步说明上述启发式格规约攻击的有效性, 可以利用NTL算法库来进行计算实验验证, 限于文章篇幅, 这里仅通过n=32来进行验证说明。

具体参数值如下:

背包密度表示的是比特长度)

其中对公式 (3) 中D分割的比例按照的是文献[1]中例子的比例,

测试结果如下:

通过寻找算法, 可以找到规约基B中存在这么一个向量, 首项为0, 尾项为1, 中间项为1或-1:

根据公式 (16) 可以恢复出明文X:

通过对照, 恢复出的明文X正好与原明文m一致, 从而说明攻击成功。

以上仅运用一组参数进行了实验, 为表明计算实验的有效性, 表1中列出了选取不同参数时的实验结果, 可以看出文献[1]中的这种改进方案不能抵抗格规约攻击。

通过多次计算实验可以发现, 运用启发式格规约攻击能以不可忽略的概率直接恢复出明文, 即使那些没有完全成功的实验中, 也都可以恢复出大部分明文, 从而说明这样的背包公钥改进算法仍然是不安全的。

4 结束语

本文对文献[1]中两种改进背包公钥方案的安全性进行了分析, 根据不同的参数, 在高背包密度下对其中一种方案进行了启发式的格规约攻击, 攻击时间均在多项式时间内, 通过计算实验验证了格规约攻击的有效性, 从而说明这两种方案都是不安全的, 存在潜在的漏洞与威胁。根据对背包密码本身的特性, 本文作者大胆猜测只要是基于背包的公钥密码算法, 不管怎样隐藏冗余, 都会为攻击者留下一定的信息, 总存在着安全威胁, 总可以通过格规约攻击以不可忽略的概率恢复出全部或部分明文。在接下来的研究中, 将通过理论分析来证明上面的猜测。

参考文献

[1]丁燕艳, 费向东, 潘郁.重新认识背包公钥密码的安全性[J].计算机应用.2012.

[2]Merkle R C, Hellman M H.Hiding information and signaturesin trapdoor knapsacks[J].IEEE Transaction on InformationTheory, 1978.

[3]SHAMIR A.A polynomial-time algorithm for breaking thebasic Merkle-Hellman cryptosystem[J].IEEE Transactions onInformation Theory, 1984.

[4]王保仓, 韦永壮, 胡予璞.基于中国剩余定理的快速公钥加密算法[J].西安电子科技大学学报:自然科版.2008.

[5]何敬民, 卢开澄.背包公钥系统的安全性与设计[J].清华大学学报.自然科学版.1988.

[6]Coster M J, Joux A, LaM acchia B A, etal.Improved low-densitysubset sum algorithms[J], Computational Complexity, 1992.

[7]LENSTRA A K, LENSTRA H W, Jr OVASZ L.Factoringpolynomials with rational coefficients[J].Mathematische Annalen, 1982.

[8]古春生, 于志敏, 景征俊.基于随机背包公钥密码的格攻击[J].计算机应用研究.2012.

公钥密码体制研究综述篇2

密码已有几千年的历史。在很长一段时间里，密码都是作为一种隐蔽通信技术。直到20世纪50年代，1949年，信息论创始人Shannon发表的经典论文“保密通信的信息理论”，将密码学的研究引入了科学的轨道。密码才发展成为一门完整的、成熟的学科。整体而言，安全与秘密通讯的学科包括密码编码学(cryptography)与密码分析学(cryptoanalysis)，统称为密码学(Cryptology)。1976年，著名学者Diffie和Hellman“密码学新方向”的发表，奠定了公钥密码学的基础;Diffie和Hellman描述了几个可能用来实现公钥密码的数学变换，称之为单向陷门函数，简单地理解即是从x计算y=f (x) 是容易的，而从y计算出x是困难的，单向陷门函数的概念使得公钥密码系统成为可能。[1]

随着计算机网络迅猛发展及电子商务应用的需求，网络信息安全保密性要求日益提高，公钥密码体制在数字签名和公开信道密钥建立上的两个重要应用，保证网上数据传输的完整性、有效性和不可否认性，对促进网络安全电子商务的发展也就起到了不可替代的巨大作用。本文结合笔者在密码学基础学习的基础上，对公钥密码体制的基本概念，发展现状、及未来发展的展望做个简单地概述。

2 基础知识

保密是密码学的核心，而加密是获得信息保密的实用工具。现代加密技术主要分为两种体制，一种是称为对称密码体制(又称为单钥密码体制)，另一种也是我们重点介绍的称为非对称密码体制(又称为双钥/公钥密码体制)，我们在此分别对这两个概念做个简单的总结。

2.1 对称密码体制

对称密码体制是一种传统密码体制, 也称为单钥/私钥密码体制。在对称加密系统中, 加密和解密采用相同的密钥，密文发送者必须和密文接收者分享密文的该加密密钥。因为加解密密钥相同, 需要通信的双方必须选择和保存他们共同的密钥, 各方必须信任对方不会将密钥泄密出去, 这样就可以实现数据的机密性和完整性。然而，这需要通信双方在基于对称密码体制进行保密通信以前，必须首先生成它们之间共享的正确密钥，这需要在网络应用中不依赖于物理地传输，即要建立安全的密钥信道保证密钥的保密性和可靠性。这也是对称密码体制的一个不足之处。

2.2 非对称密码体制

非对称密码体制也称为公钥加密技术, 该技术就是针对私钥密码体制的缺陷被提出来的。在公钥加密系统中, 加密和解密是相对独立的, 加密和解密会使用两把不同的密钥, 加密密钥 (公开密钥) 向公众公开, 谁都可以使用, 解密密钥 (秘密密钥) 只有解密人自己知道, 非法使用者根据公开的加密密钥无法推算出解密密钥, 顾其可称为公钥密码体制。

2.3 对称与非对称密码体制比较

采用分组密码、序列密码等对称密码体制时, 加解密双方所用的密钥都是秘密的, 而且需要定期更换, 新的密钥总是要通过某种秘密渠道分配使用方, 在传递的过程中, 稍有不慎, 就容易泄露。公钥密码加密密钥通常是公开的, 而解密密钥是秘密的, 由用户自己保存, 不需要往返交换和传递, 大大减少了密钥泄露的危险性。同时, 在网络通信中使用对称密码体制时, 网络内任何两个用户都需要使用互不相同的密钥, 只有这样, 才能保证不被第三方窃听, 因而N个用户就要使用N (N-1) /2个密钥。

对称密钥技术由于其自身的局限性, 无法提供数字签名的功能。这是因为数字签名是网络应用中表征人或机构的真实性、唯一性和私有性的重要手段, 而对称密钥技术中的密钥至少需要在交互双方之间共享, 不满足惟一性、私有性, 无法用于实现数字签名。相比之下, 公钥密码技术由于存在一对公钥和私钥, 私钥可以表征惟一性和私有性, 而且经私钥加密的数据只能用与之对应的公钥来验证, 其他人无法仿冒, 因此广泛用于实现网络中的数字签名服务。另外，公钥密码体制的一个重要优点就是易于建立两个相距遥远的终端用户间的密钥信道，而不需要他们彼此见面或者使用在线认证服务，这正好克服了传统对称技术的缺点。

3 公钥密码体制的研究现状

近代公钥密码系统的研究中，其安全性都是基于难解的困难问题的。如：(1)大整数因子分解问题;(2)计算有限域的离散对数问题;(3)平方剩余问题; (4) 椭圆曲线的离散对数问题等。基于这些问题, 各种公钥密码体制相继研究出来，主要集中在以下的几个方面：(1) RSA公钥体制的研究;(2)椭圆曲线密码体制ECC的研究;(3)各种公钥密码体制的研究(量子密码，NTRU，基于辫群的密码体制等;(4)数字签名研究。在此，我们对几个主要的密码体制做个介绍。

3.1 RSA密码体制

RSA密码系统是较早提出的一种公开钥密码系统。RSA是建立在“大整数的素因子分解是困难问题”基础上的, RSA算法的安全性基于RSA问题 (开e次方根的问题) , 而RSA问题的困难性又依赖于整数分解的困难性。所以, RSA需要选择合适的安全参数，才能保证RSA有足够的中长期安全，所使用的RSA密钥至少需要|N|=1024bit, 且它的两个素因子p和q的长度要相等。

具体的教科书式的RSA算法可简单描述如下：公钥(N, e), 私钥d (满足ed=1 mod (p-1) (q-1) ) ;加密：c=me (mod N) ;解密：m=cd (mod N) 。两个素数p和q不再需要, 可以舍弃, 但绝不能泄漏。加密消息m时, 首先将它分成若干比N小的数据分组，对每个分组分别实施上述加解密过程，加密后的密文c, 将由相同长度的分组ci组成。

当然，当可证明安全的概念引入后，这种教科书式的加密体制在实际应用中证明是不安全的。目前，作为RSA加密标准的是RSA-OAEP方案。

3.2 基于椭圆曲线离散对数的密码体制[2]

椭圆曲线在代数学和几何学上已有一百五十多年的研究历史, 有着复杂的数学背景, 涉及到数论、群论和射影几何等学科。1985年, N.Koblitz和V.Miller分别提出了椭圆曲线密码体制 (Elliptic Curve Cryptosystem, ECC) , 其安全性依赖于椭圆曲线群上离散对数问题 (ECDLP) 的难解性, 即已知椭圆曲线上的点p和kp计算k的困难程度。不过在当时一直没有像RSA等密码系统一样受到重视。但从现在来看, ECC是目前已知的公钥密码体制中, 对每一比特所提供加密强度最高的一种体制, 它具有安全性高、计算量小、存储空间占用小、带宽要求低等特点, 这些优点使得椭圆曲线公钥密码体制将应用到越来越多的领域。如存储空间小, 这对于加密算法在IC卡上的应用具有特别重要的意义, 带宽要求低使ECC在无线网络领域具有广泛的应用前景。

目前, 求解椭圆曲线离散对数问题 (ECDLP) 的算法主要有小步—大步法、Pollardρ方法、Pohlig-Hellman算法和MOV归约攻击等。在这些算法中, Pollardρ方法是目前求解一般ECDLP的最有效算法, 它的时间复杂度为O (sqrt (πn/2) ) 数级的。Wiene和Zuccherato将该算法时间复杂度改进为O (sqrt (πn) /2) , Pollardρ算法可以并行实现, 使用r个处理器的运行时间大概是O (sqrt (πn) /2r) 。但在使用ECC时, 椭圆曲线的选择上一定要避免超奇异曲线和奇异曲线, 这两种曲线是不宜用于密码体制的椭圆曲线, 它们的ECDLP相对容易, 易遭到特定算法的攻击。另外, ECDLP是否存在亚指数时间算法是有待证明的问题, 因为它关系ECC未来的安全性。

4 公钥密码学体制的应用

公钥密码体制主要服务于以下几个方面：(1)数据加密;(2)数字签名、身份认证与识别;(3)密钥分配。由于公钥密码体制用于数据加密的密钥生成成本较高，其主要用于数字签名和密钥分配。当然, 数字签名和密钥分配都有自己的研究体系, 形成了各自的理论框架。目前数字签名的研究内容非常丰富, 包括普通签名和特殊签名。特殊签名有盲签名、代理签名、群签名、不可否认签名、公平盲签名、门限签名、具有消息恢复功能的签名等, 它与具体应用环境密切相关。显然, 数字签名的应用涉及到法律问题, 美国联邦政府基于有限域上的离散对数问题制定了自己的数字签名标准 (DSS) , 部分州已制定了数字签名法。数字签名涉及的内容非常丰富，也是近年来公钥密码学领域的主要研究热点。

密钥管理中还有一种很重要的技术就是秘密共享技术, 是由安全多方计算技术的引入而发展而来的一种分割秘密的技术, 目的是阻止秘密过于集中, 自从1979年Shamir提出这种思想以来, 秘密共享理论和技术达到了空前的发展和应用, 特别是其应用至今人们仍十分关注。我国学者在这些方面也做了一些跟踪研究, 发表了很多论文, 按照X.509标准实现了一些CA。但没有听说过哪个部门有制定数字签名法的意向。目前人们关注的是数字签名和密钥分配的具体应用以及潜信道的深入研究。

5 结束语

公钥密码体制是非常重要的一种技术，它实现了数字签名的概念，提供了对称密钥协定的切实可行的机制，使安全通信成为可能。密钥对的思想也实现了其他的服务和协议，包括：机密性、数据完整性、安全伪随机数发生器和零知识证明等[3]。

目前，公钥密码的重点研究方向，理论方面[4]：(1)用于设计公钥密码的新的数学模型和陷门单向函数的研究;(2)公钥密码的安全性评估问题, 特别是椭圆曲线公钥密码的安全评估问题。应用方面：(1)针对实际应用环境的快速实现的公钥密码设计;(2)公钥密码在当今热点技术如网络安全、电子商务、PKI、信息及身份认证等中的应用, 这方面还将是持续研究热点。

参考文献

[1]Wenbo Mao著, 王继林等译.现代密码学理论与实践.北京:电子工业出版社, 2004 (7) .

[2]卓泽朋等.公钥密码体制的现状与发展[J].电脑知识与技术, 2006 (12) .

[3]毕仁平.公钥密码体制综述及展望[J].广西轻工业, 2007 (4) :55-57.

公钥密码体制与RSA算法篇3

关键词：公钥密码体制RSA算法,加密体制

0.引言

随着计算机联网的不断发展，全球经济发展正在进入信息经济时代，计算机信息的保密问题显得越来越重要，无论是个人信息通信还是电子商务发展，都迫切需要保证Internet网上信息传输的安全，需要保证信息安全。信息安全技术涉及信息论、计算机科学和密码学等多方面知识，它的主要任务是研究计算机系统和通信网络内信息的保护方法以实现系统内信息的安全、保密、真实和完整。其中，信息安全的核心是密码技术。密码技术是集数学、计算机科学、电子与通信等诸多学科于一身的交叉学科。它不仅能够保证机密性信息的加密，而且能够实现数字签名、身份验证、系统安全等功能。是现代化发展的重要科学之一。本文将对公钥密码系统及该系统中目前最广泛流行的RSA算法做一些简单介绍。

1. 公钥密码系统

20世纪70年代Diffie和Hellman以及Erkle分别提出了公开密钥密码体制的思想, 它同于常规的对称密钥密码体制, 算法的核心是向陷门函数的应用, 加密和解密使用不同的密每个用户保存着一对密钥--公开密钥PK和秘密密钥SK, 二者不能相互推导。用户公开密钥可以发布出去, 只要保障秘密密钥的安全即可。

1.1 公钥密码

公钥密钥加密方法是1976年由Hellman和Diffie首先提出，当时堪称密码学方向的里程碑。其主要思想是:采用两个密钥，一个公开密钥，一个私有密钥。发送方发送信息时用对方的公开密钥加密，收信方用自己的私用密钥进行解密。目前，公认比较安全的公开密钥算法主要有RSA算法及其变种Rabin算法、离散对数算法等。

1.2 公钥密码体制的原理

公钥密码体制的思想并不复杂，而实现它的关键问题是如何确定公钥和私钥及加密、解密的算法。我们假设在这种体制中, PK是公开信息，用作加密密钥，而SK需要由用户自己保密，用作解密密钥。加密算法E和解密算法D也都是公开的。虽然SK与PK是成对出现，但却不能根据PK计算出SK。它们须满足条件：

(1) 加密密钥PK对明文X加密后，再用解密密钥SK解密，即可恢复出明文，或写为：DSK (EPK (X））=X

(2) 加密密钥不能用来解密，即DPK (EPK (X））≠X

(3) 在计算机上可以容易地产生成对的PK和SKㄢ

(4) 从已知的PK实际上不可能推导出SKㄢ

(5) 加密和解密的运算可以对调，即：EPK (DSK (X））=X

从上述条件可看出，公开密钥密码体制下，加密密钥不等于解密密钥。加密密钥可对外公开，而该用户唯一保存的私人密钥是保密的，也只有它能将密文复原、解密。虽然解密密钥理论上可由加密密钥推算出来，但这种算法设计在实际上是不可能的，或者虽然能够推算出，但要花费很长的时间而成为不可行的。所以将加密密钥公开也不会危害密钥的安全。

2、RSA算法

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

该算法基于下面的两个事实, 这些事实保证了RSA算法的安全有效性：

(1) 已有确定一个数是不是质数的快速算法；

(2) 尚未找到确定一个合数的质因子的快速算法。

2.1 RSA算法的工作原理

(1) 任意选取两个不同的大质数p和q，计算乘积r=p*q;

(2) 任意选区一个大整数e, e与 (p-1) * (q-1) 互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的质数都可用；

(3) 确定解密密钥d:d*e=1 mod (p-1）*（q-1）根据e、p和q可以容易地计算出d;

(4) 公开整数r和e，但是不公开d;

(5) 将明文P (假设P是一个小于r的整数) 加密为密文C，计算方法为：C=Pemod r;

(6) 将密文C解密为明文P，计算方法为：P=Cd mod r;

然而只根据r和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。

2.2 RSA算法的优缺点

2.2.1 优点

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

2.2.2 缺点

(1) 产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密。

(2) 安全性, RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价，而且密码学界多数人士倾向于因子分解不是NPC问题。实际上，攻击利用的都是同一个弱点，即存在这样一个事实：乘幂保留了输入的乘法结构： (XM) d=Xd*Md mod nㄢ

这个固有的问题来自于公钥密码系统的最有用的特征--每个人都能使用公钥。但从算法上无法解决这一问题，主要措施有两条：一条是采用好的公钥协议，保证工作过程中实体不对其他实体任意产生的信息解密，不对自己一无所知的信息签名；另一条是决不对陌生人送来的随机文档签名，签名时首先使用One-Way Hash Function对文档作HASH处理，或同时使用不同的签名算法。除了利用公共模数，人们还尝试一些利用解密指数或φ（n）等等攻击。

(3) 速度太慢, 由于RSA的分组长度太大，为保证安全性，n至少也要600 bitx以上，使运算代价很高，尤其是速度较慢，较对称密码算法慢几个数量级；且随着大数分解技术的发展，这个长度还在增加，不利于数据格式的标准化。

3、结论

RSA不仅可以加密，还能够完成签名验证功能。密码系统中，RSA公开密钥密码算法在信息交换过程中使用比较广泛、安全性比较高。

背包公钥密码篇4

随着计算机技术的发展,Internet已经走入百姓生活。网上书店、远程医疗、电子购物已经成为大多数人生活中不可或缺的一部分。随着人们网络生活的频繁,大家对网络技术的安全性和保密性也越来越高。进而信息安全问题成为需要解决的首要问题,密码学作为保护信息的首要手段已经被业内人士高度重视。

传统的加密方式可以保证信息的完整性以及信息的不可修改性,但是对于现在的高性能计算机来说,传统的加密方式很容易就被破解。1976年Diffie和Hellmann创造性的提出了公钥加密的思想,从此开创了公钥加密方法的先河。所谓公钥密码体制就是每个用户有两个密钥:一个用来加密,另一个用来解密,公钥密钥是公开的,被记录在一个特定的地方,而解密密钥保密。通过40多年的发展,基于公钥加密的思想被不断改进更新。主要介绍了其中的一种公钥加密系统即多变元公钥加密系统,具体介绍多变元方程组是如何进行加密和解密的,并且给出实际例子来演示和验证加密和解密的过程。

2 存在问题

公钥密码系统都是基于数学的难题,例如,最具代表性的公钥密码RSA是基于数学上大数分解的困难性,但是随着计算机技术的飞速发展,现有的加密系统都受到量子计算机的威胁。就以目前的RSA为例,如要是想保证RSA加密后的密文绝对安全的话,其密钥长度就必须达到1024位,也就是1024这么大一个数,试想一下如果密钥长度这么大的话,无论是加密还是解密都需要花费很长的时间,作为时间就是金钱的今天,其商业价值也会大打折扣。但即使是这样的加密系统对于量子计算机来说破解起来也是非常容易的,所以对于公钥密码系统必须改变之前传统的想法。

3 优势

多变元公钥密码系统的难度是基于解多变元方程组的困难性,在方程组的数量很大的情况下,解多变元方程组问题(即方程组中变量的个数多于方程的个数)是一个NP完全问题。已经知道即使是量子计算机对于NP完全问题也是束手无策的,至少在NP完全问题被证明是否NP问题之前是这样。而基于多变元方程组问题的公钥密码也很多,例如(HFE)、(MIAi+)、(UOV/)、STS(UOV)等,它们都是基于多变元方程组问题的。

4 关键技术

将方程展开后可以得到密钥方程组:

5 结语

主要介绍了多变元公钥加密系统在数字签名中的应用。可以看出多变元公钥加密系统安全性是和方程组的个数密切相关的。虽然多变公钥加密系统有很多的局限性以及不稳定性,但是多变元公钥加密系统是基于NP完全问题,即使以后的量子计算机出现,也无法攻破NP完全问题,由此可以看出多变元公钥加密系统有好的发展前景。

摘要：介绍了多变元公钥密码系统在密码学中的应用,以及多变元公钥密码是如何实现加密和解密的。

关键词：多变元方程组,公钥密码,加密和解密

参考文献

[1]H W Lenstra.Factoring integers with elliptic curves[J].An-nals of Mathematics,1987,126:649-673.

[2]孙丽娜.基于遍历矩阵的密码学困难问题研究[D].长春:吉林大学计算机学院,2008.

[3]裴士辉.遍历矩阵及其在公钥密码体制中的应用[D].长春:吉林大学博士学位论文,2008.

基于RSA的概率公钥密码的研究篇5

1984年, Goldwasser和Micali提出了概率密码系统 (Probabilistic Encryption, 也有文献称为随机化加密) 的概念[1], 简单解释就是加密体制针对同一明文进行两次加密得到的密文有可能不同。概率公钥密码体制可以达到更严格的安全目标:语义安全 (Semantic Security) 。语义安全, 保证了对于相同明文能够产生随机的不同的密文, 保证了多次重复出现的信息的安全性。由于RSA是应用最广泛的密码体制, 基于RSA的概率公钥密码的研究也取得了许多成果。比如, 文献[2]提出利用随机比特填充明文的方式进行概率加密, 该方案的解密是唯一的, 能抵抗共模攻击, 但密文扩展率比较高。文献[3]提出了一种末位随机填充的概率加密方案, 该方案具有多项式安全性, 能抵抗选择密文攻击, 但该方案还是具有较大的密文扩展率。

1 基于RSA的概率公钥加密算法1

文献[4]描述了一种RSA概率算法, 该算法如下:

(1) 密钥生成

(2) 加密过程

Bob获得接收公钥 (e, n) , 把消息m分组成长度为L (L<log2n) 的消息分组m1, m2, …ms;生成一个与明文块mi等长的随机数r (r>0) 与每个明文块先进行异或运算, 再进行加密运算, 具体过程如下:

将μ, c1, c2, …cs按顺序排起来, 便得到全部的密文c, 即:c=μ, c1, c2, …csμ

(3) 解密过程

Alice在解密前, 将密文按长度L进行分组, 得到μ, c1, c2, …cs;用私钥d对μ和各个密文块ci (i=1, 2, …s) 解密, 还原出随机数r和处理后的消息mi+ (i=1, 2, …s) ;将mi+ (i=1, 2, …s) 同随机数r按位异或, 得到明文消息mi (i=1, 2, …s) , 即:

如果将m1, m2, m3…ms依次排列起来, 便得到全部的明文m, 即:m=μm1, m2, m3…msμ

2 基于算法1的改进算法2

针对算法1存在的效率低的问题, 本节提出一种改进算法, 主要是在不降低安全性的前提下, 加解密效率方面有较大提升。

2.1 算法描述

(1) 密钥生成

(2) 加密过程

Bob获得接收公钥 (e, n) , 把消息分组成长度为L (L<log2n) 的消息分组m1, m2, …ms。;生成一个与明文块mi等长的随机数r (r>0) ;然后使用加密算法计算出密文。将mi同随机数r模乘, 得到密文ci (i=1, 2, …s) , 用公钥e加密, 得到解密参数μ, 即:

将μ, c1, c2, …cs依次排列起来, 便得到全部的密文c, 即:c=μ, c1, c2, …csμ

假设一下, 在加密过程中, 如果某个密文块ci=0, 也即mir=kn, 那么这个密文块就会像一个奇点一样, 无法还原。因此, 在产生随机数r时, 必须保证r不能是n的因子。

(3) 解密过程

Alice在解密前, 将密文按长度L进行分组, 得到μ, c1, c2, …cs;用私钥d对μ和各个密文块ci (i=1, 2, …s) 解密, 还原出随机数r;再将ci (i=1, 2, …s) 乘随机数r模n的逆, 得到明文消息mi (i=1, 2, …s) , 即:

将m1, m2, m3…ms依次排列起来, 便得到全部的明文m, 即:m=μm1, m2, m3…msμ

从上面的解密过程我们可以看出, 需要求出随机数r模n的逆r-1, 根据同余理论, 当且仅当r与n互素的时候才有r-1存在。综合加密与解密过程对r的要求, 我们发现满足条件的r有如下特征:素数且不是n的因子。那么我们在产生随机数r时必须考虑到这一点。

2.2 算法的安全性分析

(1) 抵抗选择明文攻击:由于在对明文进行加密时增加了随机数r, 这使得该公钥密码体制兼具概率加密的特性。而且因为加密时随机数r隐藏在了密文中, 每次加密随着r的选择不同, 密文信息也随之不同, 满足了概率公密码中明文—密文一对多的条件, 达到抵抗选择明文攻击的效果。

(2) 抵抗选择密文攻击:对于算法2, 攻击者不可能用加密随机明文的方法来寻找一个正确密文。例如, 假定攻击者有密文ci。即使他正确地猜到了明文m, 但是当他加密m时, 结果将是完全不同的cj (因为每次的加密使用的随机参数不同) 。他不能比较ci和cj, 所以他也就不可能知道他正确地猜到了明文消息m。这表明, 即使攻击者拥有公开密钥、明文和密文, 但他在没有加密密钥情况下仍不能证明该密文就是明文加密的结果。即使他采用穷举攻击法也只能证明每一个可猜想到的明文都是可能的明文。但是, 如果攻击者能够获得随机参数r, 他就可能利用加密算法来验证其获得的明文消息的正确性。加密前缀密文μ, 对攻击者没有用, 因为解密它将面对求解大数分解的困难性问题。

2.3 算法的效率分析

本算法中, 如果我们把明文分成s等分, 则加密时需要1次模幂运算, s-1次模乘运算, 解密时一样。而对比经典的RSA算法来说, 加密时需要s次模幂运算, 解密时也需要s次模幂运算。我们知道, 模乘运算比模幂运算快得多, 特别是在模数比较大的时候, 因此, 很明显, 本算法能大幅提高运算速度。

另外, 在数据膨胀率方面, 许多概率公钥密码体制都有数据膨胀率过高的问题, 本算法也不例外。因为对于一个长度为s的明文来说, 由于随机数r也需要被加密, 因此密文的长度为s+1。当s较大时, 密文膨胀率1+1/s可以忽略, 而s较小时, 密文膨胀率的问题较为严重, 3种加密体制的效率比较见表1。

3 基于RSA的双模数多密钥算法3

文献[5]描述了一种基于RSA双模数多密钥算法, 描述如下:

(1) 密钥生成

同经典的RSA算法稍异。主要区别在该算法的解密模数n与加密模数N互不相等, 并且N具有随机特性, 即:n=pq, N=rw。其中, p≠q, 同为大素数, r是由Bob临时生成的一个随机整数, g是一个奇素数, w=gn是一个公开的大整数, (p, q) 和 (g, n) 由Alice秘密保存。

(2) 加密过程

Bob在加密前, 生成一个与明文块mi等长的随机数r (r>0) , 计算出N=rw;再将明文转换为比特位数相等的分组m1, m2, …ms, 并且mi (i=1, 2, …s) 的位数都小于n的位数;然后对每个明文块做加密运算, 具体过程如下:

将c1, c2, …cs依次排列起来, 便得到全部的密文c, 即:c=茌c1, c2, …cs茌

(3) 解密过程

Alice在解密前, 将密文按长度L进行分组, 得到c1, c2, …cs;Bob用私钥d对密文块ci (i=1, 2, …s) 逐块解密, 还原为明文块mi, 即:

将m1, m2, m3…ms, 依次排列起来, 便得到全部的明文m, 即:m=茌m1, m2, m3…ms茌

4 基于算法3的改进算法4

4.1 算法描述

(1) 密钥生成

同算法3一样进行预处理。

(2) 加密过程

Bob在加密前, 生成一个与明文块mi等长的随机数r (r>0) , 计算出N=rw;再将明文转换为比特位数相等的分组m1, m2, …ms, 并且mi (i=1, 2, …s) 的位数都小于的位数;用m0对mi (i=1, 2, …s) 进行按位异或运算进行加密, 最后对m0做加密运算, 具体过程如下:

(3) 解密过程

4.2安全性分析

本算法的最大特点是加密模数N和解密模数n不同, 后者是前者的一个因子, 而能实现这一点的理论基础则是同余的性质, 关于这一点, 我们在前面已经证明过了。在本算法中, 加密模数N因为随机数r的不同而不同, 而解密模数n是固定的, n和私钥d都不对外公开, 这无形中增加了d的长度, 提高了抗选择明文攻击能力。

另外, 我们下面证明该算法具有多项式安全性。如果一个算法具有多项式安全, 则在已知明文和多项式时间内, 无法求出明文[6]。为说明这一点, 只需证明对于明文和已知它们所对应的密文c, c', 无法在多项式时间内区分每个明文所对应的密文即可。

我们用反证法证明:假如该体制不是多项式安全的, 则对于明文m, m'和已知它们所对应的密文c, c', 可以在多项式时间内区分每个明文所对应的密文。不失一般性, 我们假设m, m'只有一位不同, 即第i (1≤i≤s) 位, 则有:mi≠m'i。m0和m0'做为密钥种子隐藏在c0=m0emod N和c'0= (m'0) emod N中, 在不知道d的情况下, 根据c0=m0emod N, c'0= (m'0) emod N, 在多项式时间内求出m0和m'0, 这与RSA这一单向陷门函数的定义矛盾。故在多项式时间内无法获得m0和m'0, 进而也无法得到mi ( (1≤i≤s) , 因为, 对于m'0来说有同样结论。因此, 假设不成立, 那么该体制是多项式安全的。

4.3 效率分析

由于加解密模数的不同, 而且每次都需要重新产生随机数以及计算加密模数, 故本算法的时间效率会比经典的RSA算法低。另外一方面, 从以上的过程可以看出, 本算法是一种零数据膨胀的概率公钥密码, 即明文密文长度一样。通过分析, 我们可以发现, 本算法相较于算法3, 在加解密效率方面有比较大的优势, 这个优势与算法2的思想一致, 即:都只进行一次模幂运算。显然, 在安全性相同的情况下, 加解密的速度将大大提高, 有关效率比较见表2。

5 结语

本文先叙述了2种基于RSA的概率公钥算法, 它们各有特点。但是它们都体现了一个思想, 即通过引入随机数来改变明文或者模数来达到增加算法安全性的特点。本文在不降低安全性的基础上, 以提高加解密效率和降低密文膨胀率为目标, 设计并改进了这2种算法, 并对改进前后的算法的正确性, 安全性和效率进行了分析和比较。

我们知道, RSA的安全性是建立在大整数分解的基础上, 而随着现代信息技术的发展以及高速计算机的发明, 对RSA模数的选择提出了越来越大的挑战和威胁, 迫使RSA的模的位数一步步增大。而另一方面, RSA模数增大必然将导致加解密效率的降低[7]。本文通过提出概率公钥算法, 在探索从其他方面增加RSA的安全性方面做了一些研究, 另外, 这些算法在提高安全性的同时也大幅提高了加解密的速度。因此, 本文的研究具有一定的理论和实践价值。

参考文献

[1]S.Goldwasser, S.Micali.Probabilistic Encryption[J].Journal of Computer and System Sciences, 1984 (28) :270-299.

[2]刘花云, 罗静, 胡予濮.基于RSA的概率加密[j].西安电子科技大学学报, 1997, 24 (4) :106-111.

[3]练慧萍, 杨明福.基于RSA的概率加密方案及应用研究[J].计算机工程, 2011, 27 (1) :139-140.

[4]郑明辉.一种基于RSA的概率公钥密码算法设计[J].湖北民族学院学报 (自然科学版) , 2004, 22 (3) :51-54.

[5]刘吉颖.一种基于RSA的概率公钥密码体制[D].暨南大学, 2001.5.

[6]余梅生, 邹惠.一种改进的RSA公钥密码体制[J].大连理工大学学报, 2003 (S1) :57-59.

一种基于组合公钥密码的盲签名篇6

数字签名是对传统文件中的手写签名的一种数字模拟, 在某些场合中能够代替手写签名, 具有保证数据的完整性、机密性、安全性和不可否认性的功用。盲签名是一种特殊的数字签名, 这种签名要求签名人能够在不知道签名文件内容的情况下对文件进行签名, 就像是个里面装有复写纸的信封交给签名人签名, 签名人只用在信封上签字就可以把签名通过复写纸签在信封中的文件上。另外, 即使签名人以后看到被他签名的文件, 也不能判断出这个签名是他何时为何人所签生成的[1]。盲签名在电子投票领域、电子现金系统、电子政务领域中有着广泛的应用。盲签名是1982年由D.chaum首次提出, 随后, 人们根据数字签名的发展, 基于大素数因子分解问题, 离散对数问题, 二次剩余问题等先后提出了各种盲签名方案, 推动了盲签名技术向前发展。1999年, 南湘浩教授提出了组合公钥技术, 2005年公布, 2006年获得国家专利[2]。组合公钥技术是我国自主研发的一种新的认证技术, 与目前正在使用的PKI、IBE等认证技术并称为三大认证技术。组合公钥技术不需要可信第三方的在线认证, 在椭圆曲线的基础上实现了将标识作为公钥的标识认证, 解决了密钥管理规模化的问题。本文将探讨一种基于组合公钥密码技术的盲签名。

2、组合公钥算法原理

组合公钥 (Combined Public Key) 算法是基于椭圆曲线的离散对数难题构建公钥矩阵和私钥矩阵, 将实体标识映射为矩阵的行坐标与列坐标序列, 用以对矩阵元素进行选取与组合, 生成公钥和私钥对。本文采用椭圆曲线离散对数问题构建组合公钥体制, 并以有限域EP (a、b) (p不等于2和3的素数) 上椭圆曲线群说明该密钥管理算法的构建方法和原理[3]。

(1) 初始化:选定椭圆曲线密码参数T= (a, b, G, n, p) , 设私钥矩阵和公钥矩阵为m×h阶矩阵。私钥矩阵SKK中的元素rij与对应椭圆曲线上的点rijG即为公钥矩阵PSK中的对应元素。

(2) 基于标识的组合密钥的生成

CPK基于标识的密钥生成与分发采用了包括对标识的Hash运算, 行映射算法和列置换算法[4]。

设行映射算法生成的行坐标序列为 (i0, i1, i2, …, ih-1) , 它是一个模m的随机数列;设列置换算法生成的列为 (j0, j1, …, jh-1) , 它是一个h元置换。据此, 可得到私钥

3、盲签名的安全性要求

盲签名先由消息拥有者将消息盲化, 再将盲化后的消息发给签名者, 签名者签名后将消息发给消息拥有者。消息拥有者将签了名的盲消息去除盲因子从而得到签名者原消息签名。

设Alice为消息拥有者, Bob为签名者。

(1) Alice将原消息m用一个随机因子盲化得到盲消息m′, 然后将盲消息m′传给Bob。

(2) Bob对盲消息m′用自己的私钥签名, 然后将签名sig (m′) 传给Alice。

(3) Alice将盲签名sig (m′) 去除盲化因子, 得到关于原消息m的签名sig (m) 。

4、一种基于组合公钥密码的盲签名

根据已经公布的椭圆曲线的数字签名和前面所述的组合公钥算法原理, 本文提出一种基于CPK的盲签名方案。

(1) 初始化:设消息拥有者Alice的身份标识为IDA, 签名者Bob的身份标识为IDB, 由注册中心为两个用户分别生成组合密钥对 (dA, PA) , (dB, PB) 通过存储介质发给Alice和Bob。

(2) 盲化:用户Alice先将消息m取Hash值得到Hash (m) 。Alice选择一个随机数或伪随机数δ, 使得0<δ<n, 并计算δG= (x′, y′) , ξ=x′modn。如果ξ=0则重新计算。盲化后消息为m′=H (m) +ξ·G, Alice将盲签名m′发给用户B。

(3) 签名:用户Bob作如下步骤:

①选择一个随机或伪随机数k, 使得0<k<n;

②计算k G= (x1, y1) ;

③计算r=x1modn, 如果r=0则回到第①步;

④计算签名sig (m′) =r (k+dB (H (m) +ξ·G) ) modn;

⑤发送 (r, Sig (m′) ) 给Alice。

(4) 去盲:Alice收到 (r, Sig (m′) ) 后, 计算

(5) 验证:Alice计算r-1Sig (m) G-H (m) PB= (x2, y2) , 计算v=x2modn, 如果v=r则接受签名, 如果v≠r则拒绝接受签名。

验证过程:

5、安全性分析

该方案是基于组合公钥密码技术和椭圆曲线离散对数问题[5]构成的, 具有椭圆曲线密码和组合公钥密码的安全性。

(1) 机密性:攻击者截获盲签名sig (m′) , 因为不知道签名者私钥, 所以不能恢复消息m。

(2) 签名私钥的安全性:攻击者截获数据 (r, sig (m′) ) 后, 试图获取签名者私钥是非常困难的。因为签名方程中含有攻击者未知的消息密钥ξ, k, 如果想从k G= (x1, y1) , δG= (x′, y′) , ξ=x′modn中求出ξ, k, 则会遇到求解椭圆曲线离散对数的难题, 是十分困难的。

(3) 盲性:因为消息拥有者用盲化因子ξ将消息盲化, 所以签名者不知道消息的具体内容。

(4) 不可否认性:由于在盲签名过程中使用了签名者的私钥dB, 而私钥dB只有Bob签名者拥有, 所以签名人不能否认自己产生的签名。

(5) 不可伪造性:盲签名是否由签名者产生, Alice只用计算r-1Sig (m) G-H (m) PB=k G= (x2, y2) , 并计算v=x2modn, 判断v是否等于r, 若相等则可证明是由Bob产生;若不相等, 则说明签名被伪造或篡改, 不可接受。

6、结束语

本文将组合公钥密码技术应用到盲签名中, 采用了组合公钥密码技术是基于椭圆曲线离散对数难题的优势, 提出了一种新的盲签名方案。该方案具有机密性, 盲性, 不可否认性, 不可伪造性, 保障了盲签名的安全性。该方案计算过程不复杂, 可提高签名的效率。

摘要：组合公钥密码技术是我国自主研发的一种新的认证技术, 其核心算法是基于椭圆曲线离散对数求解难题构建而成, 实现了将标识作为公钥的标识认证, 解决了密钥管理规模化的问题。本文将探讨一种基于组合公钥密码技术的盲签名。

关键词：数字签名,组合公钥密码,盲签名

参考文献

[1]杨义先, 钮心忻.应用密码学[M].北京邮电大学出版社, 2006.

[2]李雪.标识认证打开信息安全新天地——走进南相浩教授的CPK世界[J].信息安全与通信保密, 2006 (9) :9-11.

[3]邓文, 邓辉舫, 田文春, 郑东曦.组合公钥标识认证系统的设计及密钥生成的实现[J].计算机应用, 2007 (8) :1939-1941.

[4]陈华平, 关志.关于CPK若干问题的说明[J].信息安全与通信保密, 2007 (9) :47-49.

背包公钥密码篇7

一、RSA算法理论基础

欧拉定理:若n, a为正整数, 有gcd (a, n) =1, 则aφ (n) =1 (modn) 。其中φ (m) 称为欧拉函数, 它是比n小但与n互素的正整数个数。欧拉定理也有一种等价形式:aφ (n) +1=a (modn) 。

费尔马定理:如果n是素数, 且gcd (m, n) =1, 则mn-1=1 (modn) , 费尔马定理还存在另一种等价形式:如果n是素数, m是任意正整数, 则mn=m (modn) 。对于素数n来说, φ (n) =n-1, 所以费尔马定理实际是欧拉定理的一个推论。

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

1、密钥的产生

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

(2) 计算N=pq, φ (N) =n-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, 作加密运算:

C=Ek (M) =Me (mod N)

3、解密

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

M=Dk· (C) =Cd (mod N)

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

二、RSA实现算法研究

1、传统实现算法———二进制算法

最常使用的二进制算法有两种, 一种是硬件资源需求较大的right-to-left二进制法, 该方法实现较快;一种是left-to-right二进制法, 是基于硬件资源的有效利用。前者平方和模乘运算相互独立, 可以进行平行处理;后者模乘运算和平方可不间断执行, 能够在同一个硬件乘法器上执行, 节约面积又不影响运算速度。

算法1

算法2

模幂运算可看做是模乘运算的重复, 可见, 该算法是每一步迭代都对求模, 以控制中间结果数的大小, 每一步迭代最多需要2次乘法和2次求模, 总共需要t次迭代, 显然, 2t次乘法和2t次求模运算是影响算法实现速度的关键。

2、基于乘同余对称特性的SMM算法

基于乘同余对称特性的SMM算法是利用乘同余对称特性来减少RSA加密、解密计算中乘法和求模运算量的一种快速算法。RSA加密是对明文求幂剩余的过程, 传统的RSA算法是将指数表示成t位二进制的形式, 并将幂剩余变成一系列乘同余的迭代, 由传统实现算法的分析可以知道, 仍以a=g emodn为例, 每一步迭代必有运算a=a2 (modn) 和可能有运算a=a*g (modn) 。

SMM算法是在每步迭代计算中对乘数和被乘数进行有条件的代换:如果ai-1表示第 (i-1) 步迭代结果, 则在进行第i步迭代时, 若ai-1≤ (n-1) /2或g≤ (n-1) /2, 则保持原数不变, 但是如果ai-1> (n-1) /2或g> (n-1) /2, 则使用n-ai-1或 (n-g) 来代替ai-1或g。

迭代次数取决于其汉明重量, 即指数二进制化后的非零元素个数及二进制长度。通过迭代, 可使两个相乘数保持在一个较小的范围内, 有利于提高数据的计算效能, 随着迭代次数的增加算法改善的效果将不断提升。

3、滑动窗口法

滑动窗口技术可将一个二进制数转换成具有最少非0数字的编码形式, 再通过预处理提高运算速度。可以这样描述:设定窗口大小为k, 从大整数E的首位1开始, 向右k位记为Wk-1, Wk-1后连续的若干个零 (可能为0个) 记为Ok-1;从Ok-1后的1开始k位记为Wk-2, Wk-2后的连续若干个零记为Ok-2, 如此下去, 最后的1开始的若干位 (可能不足k位) 记为W0, 若W0=k, 且其后还有若干0, 则其后若干0记为O0, 则E可表示成

为了方便的在大整数模乘运算中使用滑动窗口法, 需要创建三个线性表X、T、L用来存储相应中间值。采用滑动窗口技术对乘数B的二进制形式重新编码, 非0元素存入X, 滑动窗口编码码元与另一乘数A的模乘的值存入T, L用以保存X中相邻元素与A相乘的倍乘次数差。最后根据三个线性表中存储的值来计算。

三、算法改进

如果将前文所述算法进行选择性组合, 汲取各自优点, 则可构建一新型适用范围更广运算速度更快的改进算法。 (以a≡g emodn为例)

1、将指数e转换为二进制形式。

即e= (eiei-1…e1e0) 2。

2、利用滑动窗口法, 窗口大小为k, 此时g e可表示为:

取变量x=n/2, 用以基于乘同余对称特性的SMM算法简化过程中乘数的判断。创建三个线性表X、T、L。其中X用以存放其中g重新编码后的非0元素, T用以存放 (g, g3, …, g 2k-1) modn的值, L用以保存X中相邻元素与g相乘的倍乘次数差。最后根据三个线性表中存储的值来计算。

其具体实现步骤如下:

(1) 预计算

(1) g1←g, g2←g2;

(2) 对i从1到2k-1-1, 执行g2i+1←g2i-1g2modn。

(2) s←1, i←t;