In [59]:
from math import sqrt
In [1]:
def exp_mod(a, b, n):
"""
a to the power of b, mod n
>>> exp_mod(2, 3, 6)
2
"""
return (a**b) % n
In [2]:
def gcd(a, b):
"""
Greatest common divisor
>>> gcd(72, 5)
1
"""
if b > a:
return gcd(b, a)
if a % b == 0:
return b
return gcd(b, a % b)
In [3]:
def gcd_qs(a, b):
"""
List of q values from gcd(a, b)
>>> gcd(72, 5)
[14, 2]
"""
if b > a:
a, b = b, a
assert a > b
assert gcd(a, b) == 1
rem = None
while rem != 1:
q = a // b # 72 // 5 = 14 5 // 2 = 2
rem = a - q * b # 72 - 5*14 = 2 5 - 2*2 = 1
a = b # a is now 5 a is now 2
b = rem # b is now 2 b is now 1
yield q
In [4]:
def mod_inv(a, n):
"""
Modular inverse
>>> inv_mod(72, 5)
29
"""
t0, t1 = 0, 1
for q in gcd_qs(a, n):
t = t0 - q * t1
t0, t1 = t1, t # move them all back one space
return t
In [63]:
def is_prime(n):
"""
Check whether a number is prime
>>> is_prime(5)
True
"""
return all(n % i != 0
for i in range(2, int(sqrt(n))))
In [47]:
from random import shuffle
In [68]:
# pick two big prime numbers
p = 101
q = 499
assert is_prime(p)
assert is_prime(q)
n = p * q # first part of public key
phi_n = (p-1)*(q-1)
In [55]:
# pick v, second part of public key
valid_range = list(range(p+1, q))
shuffle(valid_range) # shuffles in place
for v in valid_range: # search for a prime in (p, q)
if not is_prime(v): # need v to be prime
continue
if gcd(v, phi_n) == 1: # found one that fits
break
print(f'v = {v}')
In [56]:
# compute s
s = mod_inv(v, phi_n) # private key
In [57]:
# desired message to send
msg = 321
assert 1 < msg < n
signed_msg = exp_mod(msg, s, n)
print(f'signed message = {signed_msg}')
In [69]:
decrypted = exp_mod(signed_msg, v, n)
print(f'decrypted message = {decrypted}')
print(f'same as original message: {decrypted == msg}')