The other thing I don't know is why identical blocks don't result in identically encrypted output. The code here is at least short.
Code: Select all
#!/usr/bin/python
# Shows the limit of what I know about RSA key exchange
# released under the AGPLv3 license https://opensource.org/license/agpl-v3/
# Copyright (C) 2023 John Harris
# created: 2023-08-27 by j@s8r.uk
# amended: ---------- by (...please interpolate as desired)
#
# This does actually appear to work. For RSA key exchange you need to be able to make a big number as the product of just two primes.
# Then you make its totient - see https://www.doc.ic.ac.uk/~mrh/330tutor/ch05s02.html - as the product of one less than each of those two primes.
# From that you can create two smaller numbers for an encode and decode step. Surprise: python handles arbitrary length arithmetic by default.
#
import sys, gmpy2, secrets
from sympy import isprime
sys.set_int_max_str_digits(0) # there's a limit (around 4400 digits), to prevent DoS attacks through a python interface, which this line removes
def primer(length): # a function which creates guaranteed primes of a specified magnitude
random_string = ""
for _ in range(length-1):
random_digit = secrets.randbelow(10) # Generates a cryptographic-secure random integer between 0 and 9
random_string += str(random_digit) # Convert the generated integer to a string and append it
random_string += "3" # This forces the generated number to be odd. The eventual prime will be no more likely to end in a 3 than 1 7 or 9.
random_counter=0 # how many failed prime tests we reject before we hit the next prime
random_digits = int(random_string)
while not isprime(random_digits):
random_counter+=1
random_digits+=2
print(f"jumps:: {random_counter}")
return random_digits
def modinv(e, phi): # taken from https://crypto.stackexchange.com/questions/5889/calculating-rsa-private-exponent-when-given-public-exponent-and-the-modulus-fact
# this finds the inverse of e - you might need to look up the modular arithmetic meaning of inverse
d_old = 0; r_old = phi
d_new = 1; r_new = e
while r_new > 0:
a = r_old // r_new
(d_old, d_new) = (d_new, d_old - a * d_new)
(r_old, r_new) = (r_new, r_old - a * r_new)
return d_old % phi if r_old == 1 else None
length=320 # how long we want the generated prime to be
e=65537 # e is chosen because it's 2^16+1 (0b 1 0000 0000 0000 0001), it only has two set bits so it results in fewer operations in the modinv function
g=0 # When g=1, we have found a coprime pair for e and phi - they have no common divisor greater than 1.
while g != 1:
p=primer(length) # make a prime p
q=primer(length+3) # make another prime q with 3 more digits length than p. The 3 is arbitrary, but both primes should be roughly large but widely separated.
n=p*q # n is the product
phi=(p-1)*(q-1) # phi is the totient
g=gmpy2.gcd(e,phi) # check that e is coprime with phi
print(f"gcd:: {g}")
d = modinv(e,phi) # This finds the inverse of e for a given phi
# report some of the results for checking
print(f"Random prime: {n}")
print(f"totient phi: {phi}")
print(f"preset e: {e}")
print(f"decrypt d: {d}")
print(len(str(n)))
====================
results of one run:
(base) john@a285:~/python$ time python gmp4.py
jumps:: 138
jumps:: 497
gcd:: 1
Random prime: 229059832011762748591042069363694703227288839908150136688407117976523823662560482186330886393345532284203426267597087679947889397311287291626478510542101354530859940271279756539183707650327641986444667600049608387883767568986217491608905609073368317516294432573419634182166851331656320448143901513780767897395757591085563827254890877689550498140557992099210557255400459771771836124894083877272961498305489649083451959458289851403501542189330599765254093399067065361310948264216039645419802051807769454595962771834657156157716332530686608796583939375617155972403424598302576389798743596161023285042897082638837356647674596480085321886225516813473
totient phi: 229059832011762748591042069363694703227288839908150136688407117976523823662560482186330886393345532284203426267597087679947889397311287291626478510542101354530859940271279756539183707650327641986444667600049608387883767568986217491608905609073368317516294432573419634182166851331656320448143901513780767897395757591085562857488221530175405193158050608734342959528930344650140205892437713145184890572438822043967721408057898435496250819068260314916578631658628799380521926436877492220577545006736911312974952181328459447493006063674753860131612033411063675055796397027440602151047537616903287392932093860883692513261721931713719684366094628312708
preset e: 65537
decrypt d: 166007825214194962690216597777856894871393839039281734627603840312052001960734168826833057830305518209603889977143581084494024790638787440535618807928623343090960138289286580043969186295796451034227419274601465578212541132858360501685279913852598913240939265818388274787530386464129884680798493830966402685850836905927811450663259807722984275438728195722341388051720472097406188248975602503270621900897610977346153527297953857985037843558374050957363554448477838231482215236772666554782361951035034814415846067970121280766213116351981080834813567159395324383556791882636469175706927295879509915041818546933682397766025399249378882895713819078821
645
real 0m0.501s
user 0m0.470s
sys 0m0.024s