RSAキー
9545 ワード
RSA鍵生成Crycoライブラリから持ち出された鍵の長さは200ビット以上必要であり,鍵ペアを迅速に生成できる.
from Crypto import Random
from Crypto.Math.Numbers import Integer
COMPOSITE = 0
PROBABLY_PRIME = 1
class Rsa(object):
def __init__(self, p,q,n,e,d,u):
self.p=p
self.q=q
self.n=n
self.e=e
self.d=d
self.u=u
def Gcd(_value, term):# ，
r_p, r_n = abs(_value), abs(int(term))
while r_n > 0:
q = r_p // r_n
r_p, r_n = r_n, r_p - q * r_n
return r_p
def Lcm(_value, term):# ，
term = int(term)
if _value == 0 or term == 0:
return 0
return abs((_value * term) // Gcd(_value, term))
def Inverse( _value, modulus):# ，
modulus = int(modulus)
if modulus == 0:
raise ZeroDivisionError("modulus 0")
if modulus < 0:
raise ValueError("modulus ")
r_p, r_n = _value, modulus
s_p, s_n = 1, 0
while r_n > 0:
q = r_p // r_n
r_p, r_n = r_n, r_p - q * r_n
s_p, s_n = s_n, s_p - q * s_n
if r_p != 1:
raise ValueError(" " + str(r_p))
while s_p < 0:
s_p += modulus
_value = s_p
return _value
def miller_rabin_test(candidate, iterations, randfunc=None):
if not isinstance(candidate, Integer):
candidate = Integer(candidate)
if candidate in (1, 2, 3, 5):
return PROBABLY_PRIME
if candidate.is_even():
return COMPOSITE
one = Integer(1)
minus_one = Integer(candidate - 1)
if randfunc is None:
randfunc = Random.new().read
# Step 1 and 2
m = Integer(minus_one)
a = 0
while m.is_even():
m >>= 1
a += 1
# Skip step 3
# Step 4
for i in range(iterations):
# Step 4.1-2
base = 1
while base in (one, minus_one):
base = Integer.random_range(min_inclusive=2,
max_inclusive=candidate - 2)
assert (2 <= base <= candidate - 2)
# Step 4.3-4.4
z = pow(base, m, candidate)
if z in (one, minus_one):
continue
# Step 4.5
for j in range(1, a):
z = pow(z, 2, candidate)
if z == minus_one:
break
if z == one:
return COMPOSITE
else:
return COMPOSITE
# Step 5
return PROBABLY_PRIME
def lucas_test(candidate):
if not isinstance(candidate, Integer):
candidate = Integer(candidate)
# Step 1
if candidate in (1, 2, 3, 5):
return PROBABLY_PRIME
if candidate.is_even() or candidate.is_perfect_square():
return COMPOSITE
# Step 2
def alternate():
value = 5
while True:
yield value
if value > 0:
value += 2
else:
value -= 2
value = -value
for D in alternate():
if candidate in (D, -D):
continue
js = Integer.jacobi_symbol(D, candidate)
if js == 0:
return COMPOSITE
if js == -1:
break
# Found D. P=1 and Q=(1-D)/4 (note that Q is guaranteed to be an integer)
# Step 3
# This is \delta(n) = n - jacobi(D/n)
K = candidate + 1
# Step 4
r = K.size_in_bits() - 1
# Step 5
# U_1=1 and V_1=P
U_i = Integer(1)
V_i = Integer(1)
U_temp = Integer(0)
V_temp = Integer(0)
# Step 6
for i in range(r - 1, -1, -1):
# Square
# U_temp = U_i * V_i % candidate
U_temp.set(U_i)
U_temp *= V_i
U_temp %= candidate
# V_temp = (((V_i ** 2 + (U_i ** 2 * D)) * K) >> 1) % candidate
V_temp.set(U_i)
V_temp *= U_i
V_temp *= D
V_temp.multiply_accumulate(V_i, V_i)
if V_temp.is_odd():
V_temp += candidate
V_temp >>= 1
V_temp %= candidate
# Multiply
if K.get_bit(i):
# U_i = (((U_temp + V_temp) * K) >> 1) % candidate
U_i.set(U_temp)
U_i += V_temp
if U_i.is_odd():
U_i += candidate
U_i >>= 1
U_i %= candidate
# V_i = (((V_temp + U_temp * D) * K) >> 1) % candidate
V_i.set(V_temp)
V_i.multiply_accumulate(U_temp, D)
if V_i.is_odd():
V_i += candidate
V_i >>= 1
V_i %= candidate
else:
U_i.set(U_temp)
V_i.set(V_temp)
# Step 7
if U_i == 0:
return PROBABLY_PRIME
return COMPOSITE
from Crypto.Util.number import sieve_base as _sieve_base_large
## The optimal number of small primes to use for the sieve
## is probably dependent on the platform and the candidate size
_sieve_base = set(_sieve_base_large[:100])
def test_probable_prime(candidate, randfunc=None):#Miller-Rabin
if randfunc is None:
randfunc = Random.new().read
if not isinstance(candidate, Integer):
candidate = Integer(candidate)
# First, check trial division by the smallest primes
if int(candidate) in _sieve_base:
return PROBABLY_PRIME
try:
map(candidate.fail_if_divisible_by, _sieve_base)
except ValueError:
return COMPOSITE
mr_ranges = ((220, 30), (280, 20), (390, 15), (512, 10),
(620, 7), (740, 6), (890, 5), (1200, 4),
(1700, 3), (3700, 2))
bit_size = candidate.size_in_bits()
try:
mr_iterations = list(filter(lambda x: bit_size < x[0],
mr_ranges))[0][1]
except IndexError:
mr_iterations = 1
if miller_rabin_test(candidate, mr_iterations,
randfunc=randfunc) == COMPOSITE:
return COMPOSITE
if lucas_test(candidate) == COMPOSITE:
return COMPOSITE
return PROBABLY_PRIME
def generate_probable_prime(**kwargs):
exact_bits = kwargs.pop("exact_bits", None)
randfunc = kwargs.pop("randfunc", None)
prime_filter = kwargs.pop("prime_filter", lambda x: True)
if kwargs:
raise ValueError("Unknown parameters: " + kwargs.keys())
if exact_bits is None:
raise ValueError("Missing exact_bits parameter")
#if exact_bits < 160:
# raise ValueError("Prime number is not big enough.")
if randfunc is None:
randfunc = Random.new().read
result = COMPOSITE
while result == COMPOSITE:
##Integer.random()create
candidate = Integer.random(exact_bits=exact_bits,randfunc=randfunc) | 1
if not prime_filter(candidate):
continue
result = test_probable_prime(candidate, randfunc)
return candidate
def generate(bits, randfunc=None, e=65537):
"""Create a new RSA key pair.
"""
p = q = 0
#if bits < 1024:
# raise ValueError("RSA modulus length must be >= 1024")
if e % 2 == 0 or e < 3:
raise ValueError(
"RSA public exponent must be a positive, odd integer larger than 2.")
if randfunc is None:
randfunc = Random.get_random_bytes
# ， n byte string from os import urandom
# Random.get_random_bytes=urandom
d = n = Integer(1)
#A fast, arbitrary precision integer 、
e = Integer(e)
while n.size_in_bits() != bits and d < (1 << (bits // 2)):
size_q = bits // 2
size_p = bits - size_q
min_p = min_q = (Integer(1) << (2 * size_q - 1)).sqrt(modulus=None)
if size_q != size_p:
min_p = (Integer(1) << (2 * size_p - 1)).sqrt(modulus=None)
def filter_p(candidate):
return candidate > min_p and (candidate - 1).gcd(e) == 1
p = generate_probable_prime(exact_bits=size_p,randfunc=randfunc,prime_filter=filter_p)
min_distance = Integer(1) << (bits // 2 - 100)
def filter_q(candidate):
return (candidate > min_q and(candidate - 1).gcd(e) == 1 and abs(candidate - p) > min_distance)
q = generate_probable_prime(exact_bits=size_q,randfunc=randfunc,prime_filter=filter_q)
n = p * q
lcm=Integer((p - 1)).lcm(q - 1)
d = Integer(e).inverse(lcm)
if p > q:
p, q = q, p
u = Integer(p).inverse(q)
return Rsa(n=n, e=e, d=d, p=p, q=q, u=u)
def Encode(text,key,n):
return pow(text,key,n)
def Decode(text, key,n):
return pow(text, key, n)
if __name__ == '__main__':
import time
while True:
print(" ， 200")
length=input(" ：
")
timestart = time.time()
R=generate(bits=int(length))
timeend = time.time()
print("*q*: ",R.q)
print("*p*: ",R.p)
print("*n*: ",R.n)
print("*e*: ",R.e)
print("*d*: ",R.d)
print(" ：",timeend-timestart)
text=int(input(" （ ）：
"))
timestart = time.time()
m=Encode(text,int(R.e),int(R.n))
h=Decode(int(m),int(R.d),int(R.n))
timeend = time.time()
print(" ",text)
print(" ",m)
print(" ",h)
print(" ：", timeend - timestart)
print("*"*200+"
")