RSA is a cryptosystem and used in secure data transmission. It is based on the difficulty of factoring the product of two large prime numbers.
If we already have calculated the private ”d” and the public key ”e” and a public modulus ”n”, we can jump forward to encrypting and decrypting messages (if you haven’t calculated them, please scroll downfurther this blog post).
To encrypt a message one needs a public key ”e” and ”n”, which we take a look on how to calculate further, and a message ”m”.
Equation for encrypting the message
m^e mod n = c
”c” is the ciphertext, an result of encryption using cypher algorithm, such as the encryption algorithm demonstrated.
To decrypt the message, one needs the ciphertext created ”c”, the public modulus ”n” and the own private key.
Equation to decrypt the message
c^d mod n = m
The equation results in message which was previously encrypted.
Let’s assume that we have successfully generated the numbers e, d and n. If Alice would want to send Jack a message, she would need to know Jacks public key, which can be publicly available.
Alice is sending a message to Jack m = 42
(m is integer representation of the actual message, could be anything like ”hello world”. How the conversion is done, is up to other algorithm)
Jacks public key consist of number e = 17 and n = 3233.
Alice uses the encryption equation to encrypt the message:
m^e mod n = c
42^17 mod 3233 = 2557
Now Alice has the message encrypted with Jacks public key.
Alice send the ”c”, ciphertext to Jack.
Jack receives the message. He has private key ”d” = 2753. He uses it and public key component n to decrypt the message:
c^d mod n = m
2557^2753 mod 3233 = 42
Jack has successfully decrypted the message 42!
How to choose the e, d, n???
Here is the step by step explanation on how to calculate the private and the public key components.
1. Choose two very large prime numbers which are distinct from one another. Calculate the RSA modulus by multiplying them.
– For demonstration purposes I am going to use small numbers. Why to choose large prime numbers is explained pretty well in this stack overflow answer.
Our primes: p = 11, q = 5
RSA Modulus: n = 11*5 = 55
2. Calculate the phi φ (Euler’s totient function)
Euler’s totient function:
φ(n) = (p-1)(q-1)
φ(n) = (11-1) * (5-1) = 10*4 = 40
3. Select, e, that is relatively prime to the φ and is 1 < e < φ
A prime is relatively prime to some number, if they do not have any common divisor expect for 1. For checking that a number is relative to your φ, you can use Euclidean algorithm or just use your brains (:D I know. check this out http://easymathsteps.jimdo.com/number-system/relatively-prime-number/).
For number 40, our phi φ, relative primes can be 3, 5, 7, 9…
Select one of the relative primes, e. I am going to pick e = 7.
4. Find the inverse of e with respect of φ. That way we can find d.
The equation can be put out like this:
e*d mod φ(n) = 1
We need to solve d:
d is going to be solved by using the extended Euclidean algorithm.
For the love of mathematics in WordPress editor and because of the laziness, I am not going to explain the extended Euclidean algorithm here, please refer this video.
By calculating like in the video, we come to conclusion that the magic number d = 23.
5. To find out if our equation works (e*d mod φ(n) = 1)
we can use the calculated numbers to test it out:
e = 7, d = 23, φ(n)=40
7*23 mod 40 = 1 <-- IT WORKS :)
Private and Public key
After calculating e, d and n, we have successfully calculated the public and private key components.
Private key: d = 23 (your private information!), n = 55 (RSA public modulus) .
Public key: e = 7, n = 55
These posts are done in a purpose of being my personal notes for Information Security course exam. Might contain some inaccurate information.
Sources and check these out:
– Aalto materials
– Euclidean Algorithm
– The extended Euclidean algorithm
– How the RSA algorithm works, including how to select d, e, n, p, q, and φ (phi)
– Paper and Pencil RSA (starring the extended Euclidean algorithm)
– Relatively prime numbers