From the Beauty of Stockholm to the Beauty of RSA

From the Beauty of Stockholm to the Beauty of RSA

I was so proud to give a talk at Crypto Club in the beautiful and enterprising city of Stockholm last week (thank you to Thales for the invite). In fact, the presentation was in the hotel that once hosted the hostage incident, that derived the term “Stockholm Syndrome”.

It is my second Crypto Club talk, after giving one in my equally beautiful home city (Edinburgh). A key message of the event is that the knowledge of encryption in the industry is very poor — both from executives and technical professionals— and that things need to change. One of my slides shows that the CEOs of Equifax and Talk Talk — when reporting their data breaches — had no idea if encryption was being used on their data:

So let’s dive in and do a bit of crypto and Python.

The method

There was the time before I understood RSA, and there was the time after it. For a method that has existed for over 40 years, it is still going strong. It is as beautiful in its maths as any work of art. As a teacher, I love it when a student finally sees the method, and its simplicity.

We start by generating two prime numbers (p,q) and then calculate the modulus (N):

N=p q

It is this modulus (N) that provides the core of the security of RSA, and it must be difficult to determine the prime numbers for a given modulus value. Our prime numbers must thus be of a size that makes it difficult to factorize, and they must be randomly generated. Next we calculate PHI, which is:

PHI=(p−1)(q−1)

Nect we pick e so that it does not share a factor with PHI:

GCD(e,PHI)=1

and where GCD is the greatest common denomiator. In practice e typically has a value of 65,537 (and which is a prime number, so will never share any factors with PHI, unless PHI is 65,537, of course). The encryption key is now (e.N). Bob and then send this to Alice for her to encrypt a message.

We determine the decryption value (d) with:

d×e (mod PHI)=1

For this we use an inverse mod function to determine d. In the code below, we use:

d=libnum.invmod(e,PHI)

To encrypt a message (M), we use:

C=M^e (mod N)

and to decrypt a cipher (C):

M=C^d (mod N)

Isn’t that beautiful it is simpicity and strength?

The primes

And so the strength is in the lenght of the prime numbers. If these are two small, it will be easy to factorize N. Typically they are now 1,024-bit prime numbers, and which creates a 2,048-bit modulus. At the core of many methods is the (mod p) operation, and which is the remainder of an integer divide with p. The amazing thing about this is that our mathematical calculations all work, and that our numbers are constrained between 0 and p-1. The larger the value of p, the strong the encryption typically becomes.

So let’s generate some prime numbers with a given number of bits. The coding is here [code]:

import sys
import libnum

bitsize=40

if (len(sys.argv)>1):
        bitsize=int(sys.argv[1])

r=libnum.randint_bits(bitsize)

print ("Random: %d Length: %d" % (r,libnum.len_in_bits(r)))

p=libnum.generate_prime(bitsize)

print ("\nPrime (p): %d. Length: %d bits, Digits: %d" % (p,libnum.len_in_bits(p), len(str(p)) ))  

q=libnum.generate_prime(bitsize)
print ("\nPrime (q): %d. Length: %d bits, Digits: %d" % (q,libnum.len_in_bits(q), len(str(q)) ))

N=p*q
print ("\nPrime (N): %d. Length: %d bits, Digits: %d" % (N,libnum.len_in_bits(N), len(str(N)) ))

A sample run [code]:

Random: 1030183127192836844195769 Length: 80

Prime (p): 864304872207118774292573. Length: 80 bits, Digits: 24

Prime (q): 1021474090220744263000943. Length: 80 bits, Digits: 25

Prime (N): 882865033011123283515906055612738686262856896339. Length: 160 bits, Digits: 48

The calculation

We can now use the method above to generate prime numbers of a given size, and then implement RSA. The coding is here [code]:

import sys
import random
import libnum
from Crypto.Util.number import *

msg="Hello"
bitsize=60

if (len(sys.argv)>1):
        msg=(sys.argv[1])
if (len(sys.argv)>2):
        bitsize=int(sys.argv[2])

e=65537

M=  bytes_to_long(msg.encode('utf-8'))

p=libnum.generate_prime(bitsize)
q=libnum.generate_prime(bitsize)
N=p*q

PHI=(p-1)*(q-1)

print ("Message: %s" % (msg))
print ("Prime size: %d bits" % (bitsize))

if (libnum.has_invmod(e,PHI)):
	d=libnum.invmod(e,PHI)
	c=pow(M,e,N)
	plain=pow(c,d,N)
	print ("\nEncryption key (e,N)= (%d, %d)" % (e,N))
	print ("\nDecryption key (d,N)= (%d, %d)" % (d,N))
	print ("\nCipher: %s" % c)
	print ("\nDecrypted: %s" % long_to_bytes(plain) )

A sample run [code]:

Message: Hello
Prime size: 20 bits

Encryption key (e,N)= (65537, 506086466779)

Decryption key (d,N)= (383573496577, 506086466779)

Cipher: 154315550846

Decrypted: Hello

Conclusions

There you go … beautiful and simple.