[Back] With RSA, we create two random prime numbers (\(p\) and \(q\)), and determine the modulus (\(N=pq\)). We encrypt a message with \(C=M^e \pmod{N}\) and decrypt with \(M=C^d \pmod{N}\), and where \((e,N)\) is the encryption key and \((d,N)\) is the decryption key.

## RSA with varying prime number sizes |

## RSA

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

\(N=pq\)

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:

\(\textrm{PHI}=(p-1)(q-1)\)

We then pick \(e\) so that it does not share a factor with PHI:

\( \textrm{GCD} (e,PHI)=1 \)

and where GCD is the greatest common denominator. In practice \(e\) typically has a value of 65,537 (and which is a prime number, so is safe). The encryption key is now \((e.N)\). Bob and then send this to Alice for her to encrypt a message using this public key.

We determine the decryption value (\(d\)) with:

\(d \times e \pmod {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 \pmod N\)

and to decrypt:

\(M=C^d \pmod N\)

## Coding

The coding is here:

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:

Message: Hello Prime number size: 20 bits p=994831, q=1008701 Encryption key (e,N)= (65537, 1003487024531) Decryption key (d,N)= (418821822473, 1003487024531) Cipher: 70586842916 Decrypted: Hello