RSA算法的纯Python实现（源码）

#!/usr/bin/python # -*- coding:utf-8 -*- ################################################################# ## Author: 周骞 # 您可将本库用作任何用途， ## ## Date: 2014-5-21 # 但请保留本段文字，如有BUG ## ## Mail: ylf_zq@126.com # 请邮件告知我，谢谢。欢迎一 ## ## Python: 3.3.5 # 起探讨编程。 ## ################################################################# import ZIntMath import ZPrime import hashlib # 生成两个不相等的随机大质数 # bits表示要生成的大质数的二进制位数 # 两个大质数以元祖形式返回 def _generatePQ(bits): bits >>= 1 p = ZPrime.randomPrimeBits(bits) q = ZPrime.randomPrimeBits(bits) while p == q: q = ZPrime.randomPrimeBits(bits) #print('random prime finished. %d, %d'%(p, q)) return (p, q) # 根据两个大质数P，Q计算出N，E，D # 以元祖形式返回(n, e, d) def _calcNED(p, q): t = (p - 1) * (q - 1) n = p * q e, d = _calcED(t) return (n, e, d) # 计算E,D # 该方式先求E，再求D。E有3个推荐值，若推荐值可用，则用推荐值。 # E和D哪个放入公钥，哪个放入私钥都没关系。简单的理解可以认为： # 把E和D中较大的数放入公钥，则会使加密操作和验证签名操作变慢； # 若把较大者放入私钥，则会使解密操作和签名操作变慢。 # 两者需要自己权衡 def _calcED(t): recommande = (65537, 3, 17) e = 1 # 其实因为t是合数，所以e只要选择任意一个质数都会通过 for i in recommande: if i < t: e = i break # 下面这一行语句其实是永远不会被执行的，但是它阐述了原理。 if e == 1: e = ZPrime.getMinRelativelyPrime(t) d = ZIntMath.modular_linear_equation(e, 1, t)[0] return (e, d) #私钥中的较大，解密和签名操作较慢，默认 #return (d, e) #公钥中的较大，加密和验证签名操作较慢 # 为ZPrime中的常用函数提供调用 randomIntBits = ZPrime.randomIntBits findFactors = ZPrime.findFactors # 因式分解，以破解私钥 isPrime = ZPrime.isPrime ####################################################### # 以下内容摘自 Python3.3.5 document # The byteorder argument determines the byte order used to represent # the integer. If byteorder is "big", the most significant byte is # at the beginning of the byte array. If byteorder is "little", the # most significant byte is at the end of the byte array. To request # the native byte order of the host system, use sys.byteorder as the # byte order value. # The signed argument determines whether two’s complement is used # to represent the integer. If signed is False and a negative integer # is given, an OverflowError is raised. The default value for signed # is False. def _bytesToInt(intBytes): return int.from_bytes(intBytes, 'big', signed=False) # 要转化成bytes的数字num，要转化成的bytes的长度length，以字节为单位 def _intToBytes(num, length): return num.to_bytes(length, 'big', signed=False) # 获取一个整数至少为多少位的整数 def _integerBits(n): count = 0 while n != 0: count += 1 n >>= 1 return count #return n.bit_length() #这个是python内置的函数，结果与我自己写的相同 def bytesToHexStr(bins): return ''.join( [ "%02X" % x for x in bins ] ).strip() def hexStrToBytes(hexStr): return bytes.fromhex(hexStr) # ####################################################### def rsaBits(key): n = 0 if len(key) == 2: n = key[1] if len(key) == 3: n = key[1] * key[2] if n == 0: raise ValueError('key is not either public key nor private key') return _integerBits(n) # 根据指定的bits位数，生成 # 返回一个元祖，分别为公钥和密钥 def generateKey(bits): p, q = _generatePQ(bits) n, e, d = _calcNED(p, q) return ((e,n), (d,p,q)) # 使用指定的p、q生成公钥和密钥 def generateKeyWith(p, q): n, e, d = _calcNED(p, q) return ((e,n), (d,p,q)) # 因为明文不一定刚好能被等分完毕。所以开头用n个字节标记 # 剩下那一段的长度的。 codeTitle = b"zqRsa:" codeLeftLen = 4 # 加密函数，公钥加密 # 返回加密后的数据 def encrypt(data, pubkey): if len(pubkey) != 2: raise ValueError('pubkey error.') n = pubkey[1] if isinstance(data, type(b'')): # 加密时，对于每个分段，密文比明文多1字节 srcSectionLen = (_integerBits(n)-1) >> 3 tgtSectionLen = srcSectionLen + 1 # 求出分段数和多余字节数base lenData = len(data) sectionCount = lenData // srcSectionLen base = lenData % srcSectionLen ret = bytearray() # 加密第一段，仅当明文不能被分成整数份时 if base > 0: a = int.from_bytes(data[0:base], 'big') b = ZIntMath.montgomery(a, pubkey[0], n) ret.extend(codeTitle) ret.extend(_intToBytes(base, codeLeftLen)) ret.extend(_intToBytes(b, tgtSectionLen)) # 写入第一段密文 for i in range(base, lenData, srcSectionLen): sectionData = data[i : i + srcSectionLen] a = int.from_bytes(sectionData, 'big') b = ZIntMath.montgomery(a, pubkey[0], n) ret.extend(_intToBytes(b, tgtSectionLen)) return bytes(ret) else: raise TypeError("data must be 'bytes' type") # 解密函数，私钥解密 # 返回解密后的数据 def decrypt(data, prikey): if len(prikey) != 3: raise ValueError('prikey error.') n = prikey[1] * prikey[2] if isinstance(data, type(b'')): # 解密时，对于每个分段，密文比明文多1字节 tgtSectionLen = (_integerBits(n)-1) >> 3 srcSectionLen = tgtSectionLen + 1 # 求出分段数和多余字节数base lenData = len(data) ret = bytearray() # 解密第一段没有完整长度的密文 pos = 0 if data[0:len(codeTitle)] == codeTitle: pos = len(codeTitle) lena = int.from_bytes(data[pos:pos+codeLeftLen], 'big') pos += codeLeftLen a = int.from_bytes(data[pos:pos + srcSectionLen], 'big') pos += srcSectionLen b = ZIntMath.montgomery(a, prikey[0], n) ret.extend(_intToBytes(b, lena)) # 写入第一段解密后的明文 for i in range(pos, lenData, srcSectionLen): sectionData = data[i : i + srcSectionLen] a = int.from_bytes(sectionData, 'big') b = ZIntMath.montgomery(a, prikey[0], n) ret.extend(_intToBytes(b, tgtSectionLen)) return bytes(ret) else: raise TypeError("data must be 'bytes' type") # 签名函数，私钥签名 # 返回签名结果的字节数组 def sign(data, prikey): if len(prikey) != 3: raise ValueError('prikey error.') n = prikey[1] * prikey[2] sha1calc = hashlib.sha1() sha1calc.update(data) return encrypt(sha1calc.digest(), (prikey[0], n)) # 验证函数，公钥验证 # 验证通过返回True，失败返回False def verify(data, pubkey, signature): if len(pubkey) != 2: raise ValueError('pubkey error.') n = pubkey[1] sha1calc = hashlib.sha1() sha1calc.update(data) m = decrypt(signature, (pubkey[0],n,1)) return sha1calc.digest() == m