[EN] [Crypto] The RSA Algorithm

17 Jun, 2024

For those who know me, you're well aware of my love for this field.
And after long enough avoidance, I've finally decided to put pen to paper and share some thoughts on cryptography, starting with the most known to muggles, The RSA Algorithm.

The RSA algorithm, named after its creators Rivest, Shamir, and Adleman, is (approximately) the first and most widely used public key crypto system. It's method employs two distinct keys for encryption and decryption, also known as asymmetric cryptography.

In public-key cryptography, one key can be publicly shared while the other remains a closely guarded secret.

The Alorithm

Here's a simplified breakdown of how the RSA algorithm works:

Key Generation: Two large prime numbers, $p$ and $q$ , are chosen.
- These numbers are multiplied together to create $n = p * q$ , also known as the modulus.
- Then, we'll calculate the Euler's totient of $p$ and $q$ using $φ (n) = (p - 1) (q - 1)$
- A first number $e$ is chosen such that $gcd (φ (n), e) = 1$ and $1 < e < φ (n)$
- Finally, a number $d$ is calculated such that $e * d \mod f (n) = 1$ .
The pair $s k = {d, n}$ forms the private key, while $p k = {e, n}$ is the public key.
Encryption: To encrypt a message $M$ , the sender uses the public key $\pk \ = e, n}$ of the receiver. The ciphertext $C$ is then calculated as $C = M^{e} \mod n$ .
Decryption: Conversely, the receiver uses hes private key $\sk = {d, n}$ to decrypt the message. The original message M is calculated as $M = C^{d} \mod n$ .

Example

Let's illustrate this with an example. Suppose we have calculated our keys as follows:

let use $p = 7$ $q = 13$ both prime numbers (IRL both $p$ and $q$ needs to be very long)
Calculate $n = 7 * 13 = 91$
Calculate $φ (n) = (p - 1) (q - 1) = 6 * 12 = 72$
Select $e$ such as $g c d (φ (n), e) = 1$ and $1 < e < φ (n)$
Following our example, select $e$ such as $g c d (72, e) = 1$ and $1 < e < 72$ , Thus choosing any number within $[1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71]$ .
I'll choose $47$
Calculate $d$ such as $d * e \mod φ (n) = 1$ ,
I'll choose, $d = 23$ , $23 * 47 \mod 72 = 1$

So my keys are $p k = {47, 91}$ , $s k = {23, 91}$

Whenever I need to send a message $M$ I'd need to:

Encode the message into usable numbers. Note that any symbol can be converted to a number. For example, here $M = 21$
The ciphertext C would be calculated as $C = M^{e} \mod n \to C = 21^{47} \mod 91 = 70$ .
The message M can be recalculated using $M = C^{d} \mod n \to C = 70^{23} \mod 91 = 21$ , which gives us back our original message.

Yay ! You finally encrypted your message !
That all you need to know about The RSA Algorithm. Hope it was fun to read and easy to work with.

Now is your turn to make it work by Rolling your own RSA

Spoiler (example)

# Here is a sample short implementation of RSA Algorithm, from
# Prof Bill's website https://asecuritysite.com/encryption/rsa12

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

bits=60
msg="Hello"

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

p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)

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

e=65537
d=libnum.invmod(e,PHI)
## d=(gmpy2.invert(e, PHI))

m=bytes_to_long(msg.encode('utf-8'))
c=pow(m,e, n)
res=pow(c,d ,n)

print ("Message=%s\np=%s\nq=%s\n\nd=%d\ne=%d\nN=%s\n\nPrivate key (d,n)\nPublic key (e,n)\n\ncipher=%s\ndecipher=%s" % (msg,p,q,d,e,n,c,(long_to_bytes(res))))

A sample run,

Message=hello
p=242648958288128614541925147518101769011
q=299356840913214192252590475232148200447
N=72638625604016464006874651287120524699932001616388639276131104258310920947917
cipher=5847803746095553957863305890801268831081138920772806292673259864173015661385
decipher=hello

https://asecuritysite.com/rsa/rsa12

#cryptography #rsa