RSA算法的Python实现（模幂运算——原始算法）

参考文章： RSA基本原基本原理，可以详细检查，主要介绍使用python来计算RSA算法

设p、q为质数 n = p*q fn = (p-1)*(q-1) 要满足: 1 < e < fn ， 且 e 与 fn 互质 满足: e*d%fn = 1 (d>1)  e 为公钥 ， d 为私钥 把e 和 n 发给 客户端 m 为明文  c = m^e%n c 为密文 在把 c 发给服务器 m = c^d%n 最后得到 m  

# coding=utf-8 import random  num_list = list()  #判断x是否为素数是返回True def isPNs(x):     for j in range(2,x):         if (x % j == 0):             return False     return True  #将1万以内的素数放入列表中 def isPN():     for i in range(3,10001):         if (isPNs(i)):             num_list.append(i)     print ("10000以内质数运算(1/6)已完成")  def returnED(fn):     fnPn = list()       #将fnPn列表中的所有因素     for i in range(2,
      
       int
       (fn
       /
       2
       )
       +
       1
       )
       : 
       if
       (fn
       %i
       ==
       0
       )
       : fnPn
       .append
       (i
       ) fnPn
       .append
       (fn
       /
       2
       ) 
       print 
       (
       "已完成fn所有因子运算(2/6)"
       ,
       'leng='
       ,
       len
       (fnPn
       )
       ) 
       for i 
       in 
       range
       (random
       .randint
       (
       0
       ,fn
       -
       1
       )
       ,
       1
       ,
       -
       1
       )
       : 
       #for i in range(fn - 1, 1, -1): #此算法直接取离fn最近的互质的数作为e flag 
       = 
       True 
       #判断j和fn的所有质因子是否互质，否则标志为False 
       for j 
       in 
       range
       (
       len
       (fnPn
       )
       )
       : 
       if
       (i
       %fnPn
       [j
       ] 
       == 
       0
       )
       : flag 
       = 
       False 
       break 
       if
       (flag
       )
       : 
       print 
       (
       "已完成e运算(3/6), i="
       ,i
       ) j 
       = 
       1 
       while 
       True
       : 
       if
       (i
       *j
       %fn 
       == 
       1
       )
       : 
       print 
       (
       "已完成d运算(4/6), j="
       ,j
       ) 
       return i
       ,j j 
       += 
       1 
       def 
       disp
       (
       )
       : isPN
       (
       ) num1 
       = 
       len
       (num_list
       )
       /
       2
       -
       1 p 
       = num_list
       [random
       .randint
       (
       0
       ,
       int
       (
       (
       len
       (num_list
       )
       )
       /
       2
       -
       1
       )
       )
       ] q 
       = num_list
       [random
       .randint
       (
       0
       ,
       int
       (
       (
       len
       (num_list
       )
       )
       /
       2
       -
       1
       )
       ) 
       + 
       int
       (
       len
       (num_list
       )
       /
       2
       )
       ] n 
       = p
       *q fn 
       = 
       (p
       -
       1
       )
       *
       (q
       -
       1
       ) e
       ,d 
       = returnED
       (fn
       ) m 
       = 
       int
       (
       input
       (
       '请输入你要加密传输的数字：'
       )
       ) 
       # 明文 c 
       = m
       **e
       %n 
       # 密文,m的e次方幂 
       print 
       (
       "已完成c运算(5/6), c="
       ,c
       ) m 
       = c
       **d
       %n 
       # 通过c解出来的 明文 
       print 
       (
       "已完成m运算(6/6)"
       ) 
       print 
       (
       "p ="
       ,p
       ,
       ",q ="
       ,q
       ,
       ",n ="
       ,n
       ,
       ",fn ="
       ,fn
       ,
       ",e ="
       ,e
       ,
       ",d ="
       ,d
       ,
       ",c ="
       ,c
       ,
       ",m ="
       ,m
       ) 
       def 
       main
       (
       )
       : disp
       (
       ) 
       if __name__ 
       == 
       '__main__'
       : main
       (
       ) 
      

RSA算法原理 Python实现RSA加密算法