RSA in python

modinverse.py

#!/usr/bin/env python3

p = 101149
q = 201829

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

n = p*q
phi = (p-1)*(q-1)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

e = int('10001', 2)
d = modinv(e, phi)

print('P =', p)
# P = 101149
print('Q =', q)
# Q = 201829
print('N =', n)
# N = 20414801521
print('Phi =', phi)
# Phi = 20414498544
print('E =', e)
# E = 17
print('D =', d)
D = 18012792833
print('(E*D)%Phi =', (e*d)%phi)
# congruency test (E*D)%Phi = 1 

print(gcd(e, phi - 1))
# 1
print(e<phi)
# true

print('PK','n =',n,'e =',e,'p =',p,'q =',q,'d =',d)
print('PU','n =',n,'e =',e)

m = "test"
m = int.from_bytes(bytes(m, 'utf8'), 'big')
print(m)
# 1952805748

c = m**e%n
print(c)
# 6028677544

print(m<n)
# true

# t = c**d%n 
# way too slow
# let's apply chinese remainder theorem and garner's formula
dP = modinv(e,p-1)
dQ = modinv(e,q-1)
qInv = modinv(q,p)
m1 = c**dP%p
m2 = c**dQ%q
h = qInv*(m1-m2)%p
mm = m2+h*q

print(mm)
# 1952805748

t = str(mm.to_bytes(mm.bit_length() // 8 + 1, 'big'), 'utf8')
print(t)
# test

# source: https://www.di-mgt.com.au/rsa_theory.html
# disclaimer: code above is not for real cryptography, it's just a toy, don't use it, don't buy drugs with it.