RSA key exchange

[spot]

I idly coded a bit yesterday around RSA key generation - not the encrypt or decrypt phases, I don't know how to chop raw text into blocks yet.
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

[spot]

So, what else I know about RSA key exchange.

There's hardware encryption built into the great majority of hardware, from phones to Raspberry Pi to laptops and such. It's invariably an implementation of AES. It's lots faster than RSA, like perhaps 10 times faster. In practice, every bulk data transfer uses AES. This uses a 256-bit key (or two 256-bit keys in XTS mode), and you can select how to mangle each block so matching text doesn't carry a pattern from one block to the next (a variant of CBC, the currently-preferred choice being XTS). If you run an encryption speed-check on your hardware it's apparent that hardware-enabled AES is very much the fast option. The reason it matters is that you're encrypting and decrypting every read and write to your storage device because you invariably want encryption-at-rest, if the hardware is physically accessible to third parties, and that's a huge amount of conversion - you don't want to pay the extra time or electricity bill so you do it the most efficient way.

When you transfer an encrypted message to an authorized recipient you need key exchange, and AES doesn't have that, so you use RSA which does. But because of the efficiency factor you still use AES for the majority of the conversion. You use RSA to encrypt just the AES key, which is a short preamble to the transmission, and the decrypted AES key is then used to decrypt the bulk of the message it travelled with.

[spot]

I went back and did a bit more. This version generates exactly 2048-bit RSA keys in roughly half a second. The exact bit-length appears to be a standard requirement whether you're going for 1024, 2048 or 4096. It took a little juggling to make that happen when multiplying two primes together to make the key. First catch your primes, but until the product is the right bit-length keep doing it. I expect mathematicians do it differently.

Code: Select all

import sys, gmpy2, secrets, math
from sympy import isprime
sys.set_int_max_str_digits(0) # there's a limit which you can remove with this line, to prevent DoS attacks through a python interface with base10 numberlengths > 4400

def primer(bitlength): # a function which creates guaranteed primes of a specified magnitude

	random_digits = 3
	while math.floor(math.log2(random_digits)) != bitlength:
		random_string = ""
		random_digits = 3
		while math.floor(math.log2(random_digits)) < bitlength:
			random_digit = secrets.randbelow(10)     # Generates a random integer between 0 and 9
			random_string += str(random_digit)       # Convert the generated integer to a string and append it
			random_digits = int(random_string+"3")

	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)
#	print(f"bitlength:: {math.floor(math.log2(random_digits))}")
	while not isprime(random_digits):
		random_counter+=1
		random_digits+=2
#	print(f"bitlength:: {math.floor(math.log2(random_digits))}")
	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

bitlength=1024  # the bitlength of p and q. n will be 2x bitlength.
#length=616      # how long we want the generated prime to be
e=65537         # e is chosen because it's 2^16-1, 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 - they have no common divisor greater than 1.

while g != 1:
	n=3
	while math.floor(math.log2(n)) != bitlength*2:
		p=primer(bitlength-1)      # make a prime p
		q=primer(bitlength)        # make another prime q with one more bit then p. Both primes will consequenttly be 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

        # reports some of the results, for checking
print(f"RSA key pair generation")
print(f"decimal string length of n : {len(str(n))}")
print(f"bitlength of n             : {math.floor(math.log2(n))}")
print(f"Created p                  : {p}")
print(f"Created q                  : {q}")
print(f"Created n                  : {n}")
print(f"totient phi    (Public key): {phi}")
print(f"preset  e (Public exponent): {e}")
print(f"decrypt d     (Private key): {d}")


(base) john@a285:~/python$ time python gmp5.py 
jumps:: 15
jumps:: 144
jumps:: 23
jumps:: 25
gcd:: 1
RSA key pair generation
decimal string length of n : 617
bitlength of n             : 2048
Created p                  : 124464204136241097090018662503995396252807090089648683571705174850595901359482609803698193085003762522170071627226010673792242206242444127422591901941402913524724478248780907110424728325824707930146040338384752918680610767513795690561648914034105453107465557440151850557870420567746736334246778556225340732379
Created q                  : 316809928959301847116259045032565622503590459464099654743408985979384406103472992592916077264939829903470205621823882019993746888081989543035308490907235991679187549153613992440213240574707864902700918069707697159458647687467758873255738145236327026736922890512525126368533980266391646301871582114495885073303
Created n                  : 39431495670378585087481035575926003528284211065399641419909427816925977319336643442967955678619358153545515118638360442688923907680616326452389418157823609863884666133332767378516552698917916852932660069784551394343425307317852065808071204764160497075516447112221303477262160727462970302946289583353077642067963163596346654454753624536272922725877332398059995599248047429194812667964638567308661142042932953969383436264828652722464170347841272676182728965669190940710920199828612298691675815314867728016175756965783072740308934644857023179007654157499399638818134115477453730016095529486593909621608665267912120577837
totient phi    (Public key): 39431495670378585087481035575926003528284211065399641419909427816925977319336643442967955678619358153545515118638360442688923907680616326452389418157823609863884666133332767378516552698917916852932660069784551394343425307317852065808071204764160497075516447112221303477262160727462970302946289583353077642067521889463251111510547346828736361707120934848506247260932933268364832360501682964912046871692989361543743159015778760028678181253516839005724828572820552035507008172426217399141037846414335155183328798557690622662169676189875468615190267098228967158973745667524776753089691128652455526985490304597190894772156
preset  e (Public exponent): 65537
decrypt d     (Private key): 18108392590313628566732025080925964389440619809196835494682607519508386703390069086210942857613360732826637907222770865978127513457489808462968465420999087325836348881012501331937877635218770214118959826057122592055694820854561448107565482853761058340812342779445573809529872460052382886121953668769970822486629023409302664191722896951408796226547122635083884276245456651631541870302564233867248648814317115741978391700839118979860646980897757046482142386074738767606915558623554100156366877695534509751020749350608277313018916707915863999136082958563822338276589153539118451222064389567007247748329976920848594838909

real	0m0.438s
user	0m0.406s
sys	0m0.032s