第9期 贺毅朝等：Rabin密码算法的快速实现研究 -51· Rabin密码算法的快速实现研究 贺毅朝 ，刘坤起 (1．石家庄经济学院信息工程系，河北石家庄050031；2．中国地质大学计算机学院，湖北武汉430074) 摘要：首先分析了利用MRC方法改进Rabin密码的解密算法，然后结合素性测试的优化策略和运算数与Vi— sual C++6．0的特性，提出一种基于递归技术的快速素性测试方法。 关键词：Rabin解密算法；MRC方法；素性测试算法 中图法分类号：TP309 文献标识码：A 文章编号：1001—3695(2006)09—0051·03 Research on Fast Implementation of Rabin Algorithm HE Yi．chao ．LIU Kun—qi · (1．Dept．ofInformationEngineering，Shijiazhuang University ofEconomics，ShijiazhuangHebei050031，China；2．CollegeofComputer，Chi- University of Geosciences．Wuhan肌 6ei 430074．China) Abstract：This paper first improves the decryption algorithm of Rabin using the MRC method，then puts forward a fast pri- mality testing optimization algorithm which combines the characters of the optimization strategy operation number and Visual C++6．0 based on recursion techniques． Key words：Rabin Decryption Algorithm；MRC Method；Primality Testing Algorithm 1976年，著名学者Diffie和Hellman在其经典论文《New Directions in Cryptography))…中首次提出公开密钥密码体制 (Public—Key Cryptosystem，PKC)，标志着密码学的研究与实现 自此由传统走向现代。此后，基于背包问题(Knapsack Prob· lem)、离散对数问题(Discrete Logarithms Problem)和因子分解 问题(Factorization Problem)等三大疑难问题 提出了大量 PKC算法，其中比较著名的有Chor．Rivest算法、RSA算法、 Rabin算法、E1Gamal算法和ECC算法。Rabin算法是M．O． Rabin在他的论文 中提出的一种独具特色的PKC算法。该 算法具有两个突出的特点：①从密文恢复明文是不确定的，有 四个不同选择的可能性；②该算法的安全性是确定的，即在理 论上可以证明破译Rabin密码算法的计算复杂性等同于因子 分解问题 ’ 。此外，Rabin密码算法的加密速度较RSA算法 更快 J，且易实现。 制约Rabin密码速度的关键是安全大素数的快速生成、模 幂的计算速度和解密运算的加速实现。由于利用著名的 Montgomery算法可以有效地提高模幂的计算速度，因此本文重 点讨论利用MRC方法对Rabin解密算法的改进，并且结合素 性测试优化策略及运算数和Visual C++的特性，提出了一种 基于递归技术的快速素性测试方法。 1 Rabin解密算法的优化分析 1．1 Rabin解密算法简述 选取满足p=-q=-3(mod 4)的两个大随机素数P和q，计算 N=pq，贝0PK=(Ⅳ)，SK=(p，q)。力Ⅱ密函数：c：Ep (m)=m (modⅣ)，m∈M；解密函数：m=D (c)= (modⅣ)，c∈C，其 收稿日期：2005．07—31；修返日期：2005—09—08 基金项目：国家自然科学基金项目资助(60473081) 中M=C：[0，N一1]，初步建立了Rabin密码系统。需要指出 的是：对于密文e，有四个不同的明文m，一m，wm，一wm。如果 明文是英文文本，解密后容易根据内容正确选择；但若明文是 一个随机位流(如数字签名等)，就无法确定。常用解决方法 是在加密明文之前需先加上一个时戳。 解密函数D (c)= 只是一种形式上的表示，实际计算往 往涉及到欧拉判别法(Euler Criterion)、中国剩余定理(Chinese Remainder Theorem，CRT)和平方剩余(Quadratic Residue)等数 论知识，对此在文献[9]中有详细的论述。下面仅给出Rabin 密码的解密算法： 算法1 Rabin解密算法 (1)计算 】=c(P )／4(mod P)， 2=P— l， 3=c‘ (mod q)， x4 q一 ； (2)计算A=q×(q一。rood JD)和B=JD x(JD一。rood g)； (3)计算ml=(A x戈1+B x 3)(mod^，)，m2=(A x l+B x x4) (modⅣ)，m3=(A x 2+B x )(roodⅣ)，m4=(A x 2+B x z4)(mod Ⅳ)，则m r，m2，m3和m4是四个待定的明文； (4)利用时戳确定m (1≤f≤4)中的明文。 1．2 Rabin解密算法改进 定理1(中国剩余定理) 设p (1≤i≤t)是两两互素的 正整数，对于任意整数d．，d ，…，d ，同余方程组 ；d (mod P )，1≤i≤t有唯一的解 ： t t = diPfP。 (mod P)，其中P=rIP ，P =P／P ，P P 一 1(rood P )，1≤ ≤￡ 上述计算同余方程组 ---d (mod P )的方法称为单个基数 转换法(Single．Radix Conversion，SRC)。除此之外，H．L．Garner 给出了求解中国剩余定理中唯一解的另一种有效方法，即混合 基数转换方法(Mixed—Radix Conversion，MRC)。 定理2(MRC方法) 设P (1≤ ≤￡)是两两互素的正整 数，则对于任意整数d (1≤ ≤￡)，同余方程组 d (modP )， 维普资讯 http://www.cqvip.com 

·52· 计算机应用研究 2006焦 (1≤i≤￡)有唯一的解 。并且，若设 vI=dl，v2=(dE一 1)pl2(mod P2)，’。。， f=(…((dl一 1)pl￡一 2) p2l一…一 (￡一1)1)p(t—1)￡(mod P￡) 其中p 满足PimPf 1(modPj)，(1≤ < ≤￡)，则唯一解 为 =vtPt一1Pt一2…P2Pl+…+v3P2Pl+v2pl+uI 由中国剩余定理及条件N=pq，计算D (c)等价于解方程组： m c m。d p) m c(rood q) 对于m ；c(rood P)，由P---3(mod 4)可知(P+1)／4必是 一正整数，又因c是模P的平方剩余，根据欧拉判别法 必有 c Pl ’ ；1(modP)成立，故得 (c‘P ) ) ；c‘p一 ) c；c(mod P)且(P—c(p )“) P 一 2pc(p ) +c(p ’) §c‘p ’) ------c(mod p) 由此可求得方程m ~---c(modP)的两个解 ，和 为 I=c‘ ’／4(mod P)，x2=(p—c‘p ／4(mod P))(mod P)=P— c‘ ’“(mod p) p— l 同理，可求得方程m ；c(mod q)的两个解 和 为 =c‘ ’／4(mod q)， 4=(q—c q )／4(mod q))(mod q)=q— c(q )“(mod q)=q一如 于是方程组(1)就等价地转换成如下四个方程组： rm= 。(mod N) lm= (modN) (其中，i=1，2且 =3，4) ‘。 根据定理2求解式(2)中四个方程组，得到四个不同的解 (即对应于密文c的明文)为 mod mod mod rood ×p ×p (3) xp ×p 其中c=p (mod q)。于是利用式(3)，Rabin解密算法可改 进为 算法2基于MRC的Rabin解密算法 (1)计算 I=c‘ )／4(mod p)， 2=p一 l，x3=c(q+I]／4(rood q)， x4 q—x3： (2)计算c=P (mod q)； (3){_卜算，扎l= l+[(x3一 1)xC m0d q]xp，m2= l+[( 4一 1)xc mod q]xp，m3= 2+[( 3一 2)xCmod q]xp，m4= 2+[( 4一 2)× C mod q]xp，则ml，m2，m3和m4即是四个待定的明文； (4)利用时戳确定m (1≤i≤4)中的明文。 对于合法的接收者而言，由于P和q是已知的。因此无论 算法1还是算法2中的步骤(2)都可以预先利用扩展Euclide— an算法 ‘ 计算出。这样，算法1与算法2的实质区别是步骤 (3)的不同。从表面上看，尽管算法2中的步骤(3)比算法l 的多四次乘法运算，但是由于P，q，C<1— 10 =9．999 999 999 999)，没有理由不认为Ⅳ是素数。 2．2快速素性测试算法 加快素性测试一个好的解决方法是采取试除的优化策略： 即先利用较小素数3，5，7，11，…去试除Ⅳ，若能整除，显然Ⅳ 不是素数，被排除掉；若不能整除，Ⅳ是否为素数有待进一步确 定，此时雷利用算法3对其测试。试验表明，随着小素数的增 大，被排除掉的非素数奇数就越多(试验结果如表1所示)。 从表1中可以看出，最大小素数选择397比较适宜。 表1 测试到的最大小素数与被排除的非素数的奇数比例的关系 巨 堕鱼塑些 I ：! 《 ： I ： I ：! I!： l ： I ： I ： f 由于这些小素数都很小，远远小于大奇数N(155位以上)， 如果采用大数除法算法(如基本算法、恢复余数法 等)，不仅 浪费存储空间，而且速度也慢，虽然比直接利用算法3测试已经 快很多。但仍然可以进一步地改进。考虑到Visual C++6．0【io] 中特殊整型数据(一int64)的最大值9 223 372 036 854 775 808 是l9位十进制整数，而作为除数的最大小素数397是三位。并 且余数小于397这一事实，可得到下面的分析，设 X=xn10 一 + n—l1O 一 + 一21O 一 +…+ 310 + 21O + 。 其中 。∈{0，1，2，3，4，5，6，7，8，9}， ≠0， l为奇数，n≥155。 为了表示上的方便，以下将采用X=XnX… ··X3 ： 的形式 表示(3)中的 。 利用Homer规则 ，将 从最高位 到个位 ．按下述 规则分解成s个十进制整数： l，(s)= B n—l… n—l7 即Y(s)为一个18位的十进制整数。 l，(s一1)= 一l8 一I9… n一32，l，(s一2)= 一33 一34… 一47，…， l，(2) ￡+i5 …4… ￡+j C C C C × × × × ； ， 1 2 一 一 一 一 3 4 3 4 ，{，L + + + + l = = lI lI 2 3 4 m m m ，●，●●●』、●●●【 维普资讯 http://www.cqvip.com 

第9期 贺毅朝等：Rabin密码算法的快速实现研究 ·53· 即Y(i)为s一2个15位的十进制整数，其中s=[(n一18)／15]+ 2，t=n一18一[(n一18)／15]×15，i=s一1，s一2，…，2，[ ]表 示不超过 的最大整数。 y(1)=XtXI—l… l 即Y(1)为一个t位的十进制整数(显然t<15)。 又设D[77]=t 3，5，7，11，…，389，397}，这里假定数组D 的下标由1开始，即D[1]=3。 于是，R=X(rnod D[ ])可进行如下递归计算： R(s+1)=0 ( )=[ (i+1)×10 +y( )]／o[j] i=s，s一1，…，2， =1，2，…，77 R= (1)=[ (2)×10 +y(1)]／D[j] t～n 18[(n一18)／15]×15 这样，快速素性测试算法可描述为 算法4快速素性测试算法 FastPrimalityTest(Ⅳ1 (1)fori=1 to 40； (2)forj=1 to 77； (3) R=0； (4) for k=s down to 2 (5)L=y( )+R×10”； (6) R=L(mod D[ ])； (7)L=y(1)+R×10 ； (8) R=L(mod D[ ])； (9) if(R=0)Output(Yes)； (10)LehmannTest(Ⅳ)。 在用Visual C++实现时，￡定义为一int64型变量， 及数 组D定义为int型。此外，计算步骤(5)时，避免使用C++库 函数，而采用Homer规则计算。下面以计算L=Y(s一2)+ R×10 为例加以说明： 设R=R[s一1，3]×10 +R[s一1，2]×10+R[s一1，1]，贝0 ￡为 L=(…((((R[s一1，3]×10+R[s一1，2])×10+R[s一1，1])× 10+ 一∞)×10+ 一34)×10+…+ 一46)×10+ 一47 由于利用算法4编程避开了大数的除法计算，完全采用 C++基本运算，使得计算速度极大地提高。测试表明，利用算 法4与利用大数除法进行试除优化策略的素性测试相比，可使 运行时间平均缩短约31．7％左右。 3结束语 众所周知，计算机密码学是一个理论与实践紧密结合的学 科，特别是在信息安全领域有着极为广阔的应用。如果一个好 的密码算法没有一个快速的实现方法，其价值也无法体现。正 是基于这样的考虑，本文从实用的角度讨论了Rabin解密算法 的改进与快速素性测试的实现，并利用文中算法和Visual C++6．0高速、有效地实现了Rabin密码算法。 参考文献： [1]W Diffie，M E Hellman．New Directions in Cryptography[J]．IEEE Transactions oo Information Theory，1976．IT-22(6)：644-654． [2]M O Rabin．Digitalized Signatures and Public-Key Functions As In- tractable As Factorization[R]．Cambridge，Mass：MIT／LCS／TR-212， MIT Lab．for Computer Science，1979．1-16． [3]D E Knuth．The Art of Computer Programming：Seminumerieal Algo- rithms(3rd edition)[M]．Addison-Wesley，1998．284-294． [4]D J Lehmman．On Primality Tests[J]．SIAM Journal on Computing， 1982．11(2)：374-375． [5]潘承洞，潘承彪．初等数论[M]．北京：北京大学出版社，1994． 133—188． [6]冯登国，裴定一．密码学导引[M]．北京：科学出版社，2001．150— 167． [7]B Schneier．应用密码学——协议、算法与C源程序[M]．昊世忠， 祝世雄，等．北京：机械工业出版社，2000．330-360． [8]卿斯汉．密码学与计算机网络安全[M]．北京：清华大学出版社， 20o1．57．60． [9]贺毅朝，沈春璞，等．Rabin密码系统的分析与实现[J]．河北省科 学院学报，2002，(4)：217-220． 作者简介： 贺毅朝(1969-)，男，河北晋州人，讲师，硕士，主要研究方向为计算机 密码学与信息安全、计算理论；刘坤起(1966-)，男，河北无极人，副教 授，在读博士研究生，主要研究方向为演化密码学、算法设计与分析。 (z*i-g 50页)是增强的依据是否可靠，只有在得到清晰指纹 的情况下观察模糊指纹处理后的效果才会知道。如果增强的 特征可靠且未出现错误特征，则该实验方法是可信的；反之，则 该实验方法是失败的。另外，同一种实验方法对待不同的指纹 处理效果也是不同的，因此需要一种广泛适用的处理方法以适 合指纹不同的变化情况，在保持指纹所有特征(包括脱皮、伤 疤、褶皱等)不变的基础上，能准确地提取特征，只有这样的方 法才具有普遍意义。 参考文献： [1]黎妹红，张其善．用迭代法求指纹图像中的闽值[EB／OL]．ht- tp：／／21ic．eom／news／n1941c72．aspx．2004-12—08／2005·05-20． [2]上海科技．几种主要的识别技术[EB／OL]．http：／／www．stcsm． gov．cn／leaming／lesson／gaoxin／20050117／Iesson-2．asp，2005·01·17． [3]张伟伟．在线指纹识别系统研究[D]．中国科学院自动化研究 所．2003． 『4]王曙光．指纹识别技术的若干问题研究[D]．中国科学院自动化 研究所，2003． [5]Hong L，Jain A，Pankanti S，et a1．Fingerprint Enhancement[C]． [6] [7] [8] [9] [10] [11] Proceedings of the 3rd IEEE Workshop．Applications of Computer Vi· sion，1996．202-207． 董日荣．指纹识别系统核心算法的研究[D]．广州：华南师范大 学，2004． 毛幼菊，马军．指纹图自动识别的数字图像处理[J]．半导体光电， l995，16(4)：360． 乔治宏，昊晴，乔雨峰．基于方向滤波的指纹图像增强算法研究 [J]．计算机工程与应用，2004，40(35)：87．89． Randolph T R．Smith M J．Fingerprint Image Enhancement Using a Binary Angular Representation[C]．IEEE 200 1 International Confe— fence on Acoustics，Speech，and Signal Processing，2001．156l- 1564． 刘少聪．新指纹学[M]．合肥：安徽人民出版社，1984． 罗剑，张维新．基于脊线跟踪的指纹角度特征的提取方法及应用 [J]．上海大学学报，2002，8(2)：105-110． 作者简介： 郭雷(1956-)，男，山东人，教授，博导，主要研究方向为神经计算、视觉 计算、图像和视频处理、模式识别；陈大海(1970-)，男，河南人，博士研 究生，主要研究方向为图像分类、指纹识别。 维普资讯 http://www.cqvip.com