80910213143536#!/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
