现在的位置: 首页 > 综合 > 正文

RSA算法优化 RSA算法优化

2017年12月12日 ⁄ 综合 ⁄ 共 6938字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

RSA算法优化

分类： 加解密算法2013-07-10
20:05 81人阅读 评论(0) 收藏 举报
RSA剩余定理孙子定理速度优化python

RSA算法优化

  1. 大数乘法
  2. 模乗优化
  3. 剩余定理（孙子定理）
  4. RSA加解密
  5. python的RSA计算优化

 

[python] view
plaincopy

  1. #-*- coding: utf-8 -*-  
  2. ''''' 
  3. /********************************************************************************* 
  4.   *Copyright(C),2000-2013,KK Studio 
  5.   *FileName:    rsa 
  6.   *Author:      KingKong 
  7.   *Version:     1.0 
  8.   *Date:        20130709 
  9.   *Description: //用于主要说明此程序文件完成的主要功能 
  10.                 //与其他模块或函数的接口、输出值、取值范围、 
  11.                 //含义及参数间的控制、顺序、独立及依赖关系 
  12.   *Others:      //其他内容说明 
  13.   *Function List:      //主要函数列表，每条记录应包含函数名及功能简要说明 
  14.      1.RSA 
  15.      2.RSA CRT 
  16.      3.RSA MulMod     
  17.   *History:            //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介 
  18.      1.20130702: 
  19. **********************************************************************************/ 
  20. '''  
  21.   
  22. # sudo apt-get install python-setuptools  
  23. # sudo easy_install rsa-3.1.1-py2.7.egg  
  24.   
  25. # import binascii  
  26. #print repr(binascii.unhexlify('0123456789abcdef'))   
  27.   
  28. EASYKEY = True  
  29.   
  30. def CRT_SRC(c, n, p, q, d=None, exp1=None, exp2=None):  
  31.     ''''' 
  32.     剩余定理的基础实现 
  33.     c是密文 
  34.     exp1 = d % (p-1) 
  35.     exp2 = d % (q-1) 
  36.     (1)计算d1←d(mod(p-1))与d2←d(mod(q-1)); 
  37.     (2)计算C1←c(modp)与C2←c(modq);  
  38.     (3)计算M1←C1^d1 (modp)与M2←C2^d2(modq); 
  39.     (4)计算B1←q-1(modp)与B2←p-1(modq); 
  40.     (5)计算m←(M1*B1*q+M2*B2*p)(modN) 
  41.     '''  
  42.     c1 = c % p  
  43.     c2 = c % q  
  44.     if d != None:  
  45.         d1 = d % (p-1)  
  46.         d2 = d % (q-1)  
  47.     elif exp1 != None:  
  48.         d1 = exp1  
  49.         d2 = exp2  
  50.     else:  
  51.         return 0  
  52.       
  53.     import rsa  
  54.     y1 = rsa.common.inverse(q, p)  
  55.     y2 = rsa.common.inverse(p, q)  
  56.       
  57.     m1 = pow(c1, d1, p)  
  58.     m2 = pow(c2, d2, q)  
  59.       
  60.     m = (m1*q*y1 + m2*p*y2)%n  
  61.     return m  
  62.   
  63. def CRT_MMRC(c, n, p, q, coef, d=None, exp1=None, exp2=None):  
  64.     ''''' 
  65.     剩余定理的快速实现 
  66.     c是密文 
  67.     exp1 = d % (p-1) 
  68.     exp2 = d % (q-1) 
  69.     self.coef = rsa.common.inverse(q, p)     
  70.     (1)计算d1←d(mod(p-1))与d2←d(mod(q-1)); 
  71.     (2)计算C1←c(mod p)与C2←c(mod q);  
  72.     (3)计算M1←C1^d1 (modp)与M2←C2^d2(modq); 
  73.     (4)计算B←p^-1(modp);  
  74.     (5)计算m←M1+[(M2-M1)*B(modq)]*p 
  75.     '''  
  76.     c1 = c % p  
  77.     c2 = c % q  
  78.     if d != None:  
  79.         d1 = d % (p-1)  
  80.         d2 = d % (q-1)  
  81.     elif exp1 != None:  
  82.         d1 = exp1  
  83.         d2 = exp2  
  84.     else:  
  85.         return 0  
  86.       
  87.     y1 = coef  
  88.       
  89.     m1 = pow(c1, d1, p)  
  90.     m2 = pow(c2, d2, q)  
  91.       
  92.     m = m2 + (((m1-m2)*y1)%p)*q      
  93.     return m  
  94.   
  95.   
  96. def dec2bin(number):  
  97.     ''''' 
  98.     转换数字为二进制字符串 
  99.     :param number: 
  100.     '''  
  101.     m = {'0':'0000', '1':'0001', '2':'0010', '3':'0011',  
  102.           '4':'0100', '5':'0101', '6':'0110', '7':'0111',  
  103.           '8':'1000', '9':'1001', 'a':'1010', 'b':'1011',  
  104.           'c':'1100', 'd':'1101', 'e':'1110', 'f':'1111'}  
  105.     s = hex(number)[2:].rstrip('L')  
  106.     return ''.join(m[x] for x in s).lstrip('0')   
  107.    
  108. #print dec2bin(10), len(dec2bin(10))   
  109.   
  110. def MulMod(m, r, e):  
  111.     ''''' 
  112.     a^m%r 
  113.     343^474%2003=1819 
  114.     '''  
  115.     c = 1L  
  116.     b = dec2bin(e)  
  117.     length = 0;  
  118.     while(length < (len(b))):  
  119.         c = (c*c)%r;  
  120. #         print c, b[length]  
  121.         if (b[length] == "1"):      
  122.             c = (c * m) % r;       
  123.         length = length + 1;     
  124.     return c  
  125.   
  126.   
  127. def RSA_ENC(m, n, e):  
  128.     ''''' 
  129.     RSA加密，处理小数据 
  130.     :param m: 
  131.     :param n: 
  132.     :param e: 
  133.     '''  
  134.     return m**e%n  
  135.   
  136. def RSA_DEC(c, n, d):  
  137.     ''''' 
  138.     RSA解密，处理小数据 
  139.     :param c: 
  140.     :param n: 
  141.     :param d: 
  142.     '''      
  143.     return c**d%n  
  144.   
  145. def RSA_ENC_Fast(m, n, e):  
  146.     ''''' 
  147.     RSA加密，处理大数，加速处理 
  148.     :param m: 
  149.     :param n: 
  150.     :param e: 
  151.     '''  
  152.     return pow(m, e, n)  
  153.   
  154. def RSA_DEC_Fast(c, n, d):  
  155.     ''''' 
  156.     RSA解密，处理大数，加速处理 
  157.     :param c: 
  158.     :param n: 
  159.     :param d: 
  160.     '''  
  161.     return pow(c, d, n)  
  162.   
  163.   
  164. def main():  
  165.     if EASYKEY == True:      
  166.         n = 3727264081  
  167.         d = 3349121513  
  168.         e = 65537  
  169.         p = 65063  
  170.         q = 57287  
  171.         exp1 = 55063  
  172.         exp2 = 10095  
  173.         coef = 50797  
  174.     else:  
  175.         n = 133258714669197804455201327242498072620373933399830946281753432589524373262313529490829857553863402092345114025453326547226675345976454214588491707723768296657213731743431331618394950680996499630699923360897031860272219245284778878593279460078556127568327691304405295451439978360703575209901885763486177804307  
  176.         d = 88839143112798536303467551494998715080249288933220630854502288393016248841542352993886571702575601394896742683635551031484450230650969476392327805149178849037945720743702166302175205762735121467799910708222531056914667451445033725048565810909623712841116051352011118012226070375134490825522121220289982706011  
  177.         e = 3     
  178.         p = 11933806723950669295207846073987787705734940703054957716278358174994444687961839258803748173125990183157845108140695431551588508864566689717312651807708143  
  179.         q = 11166488426677208786957286068049106111694059354243605518996542043073672540329181171939965947432316470456431280477737669321209492974404928986620399396037149  
  180.         exp1 = 7955871149300446196805230715991858470489960468703305144185572116662963125307892839202498782083993455438563405427130287701059005909711126478208434538472095  
  181.         exp2 = 7444325617784805857971524045366070741129372902829070345997694695382448360219454114626643964954877646970954186985158446214139661982936619324413599597358099  
  182.         coef = 9906165481638181059785426924280606820580988396251355030296387570862138753002899617836092623649635665775562393844489153345463178213574659230193241203692517  
  183.       
  184.     m = 9999  
  185.       
  186.     print '********RSA BEGIN********************************************'  
  187.     print 'message:', m  
  188.     c = RSA_ENC(m, n, e)  
  189.     print 'encrypt:', c  
  190.     r = RSA_DEC_Fast(c, n, d)  
  191.     print 'decrypt:', r  
  192.     print '********RSA END**********************************************'  
  193.       
  194.     print '********RSA FAST BEGIN***************************************'  
  195.     print 'message:', m  
  196.     c = RSA_ENC_Fast(m, n, e)  
  197.     print 'encrypt:', c  
  198.     r = RSA_DEC_Fast(c, n, d)  
  199.     print 'decrypt:', r  
  200.     print '********RSA FAST END*****************************************'  
  201.       
  202.     print '********RSA MulMod BEGIN*************************************'  
  203.     print 'message:', m  
  204.     c = MulMod(m, n, e)  
  205.     print 'encrypt:', c  
  206.     r = MulMod(c, n, d)      
  207.     print 'decrypt:', r  
  208.     print '********RSA MulMod END***************************************'  
  209.   
  210.     print '********RSA CRT BEGIN****************************************'  
  211.     print 'message:', m  
  212.     c = RSA_ENC_Fast(m, n, e)  
  213.     print 'encrypt:', c  
  214.     r = CRT_SRC(c, n, p, q, d)  
  215.     print 'decrypt:', r  
  216.     print '********RSA CRT END******************************************'  
  217.   
  218.     print '********RSA CRT FAST BEGIN***********************************'  
  219.     print 'message:', m  
  220.     c = RSA_ENC_Fast(m, n, e)  
  221.     print 'encrypt:', c  
  222.     r = CRT_MMRC(c, n, p, q, coef, d, exp1, exp2)  
  223.     print 'decrypt:', r  
  224.     print '********RSA CRT FAST END*************************************'  
  225.       
  226.   
  227. if __name__ == '__main__':  
  228.     main()  
  229.       
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞