1. Introduction to RSA
RSA, named after its inventors Rivest, Shamir, and Adleman, is a popular encryption algorithm that ensures secure online communication. It relies on the difficulty of factoring large composite numbers into their prime factors.
2. Note on phi
phi(n) for a positive integer n is defined as the number of positive integers less than n, relatively prime to n (do not share any common factors other than 1).
For a prime p, this can be easily defined as phi(p)=p-1 since all numbers from 1 though p-1 are relatively prime to p. For two primes p and q, phi(pq)=(p-1)(q-1).
3. Encryption & Decryption Process
RSA implementation makes heavy use of modular arithmetic as well as advanced number theory properties including Euler’s Totient function, phi.
The implementation is quite easy to perform with a computer given its only requiring multiplication.
Alice needs to send a message to Bob. Bob, the receiver, chooses two large prime numbers p and q. The product n=pq will comprise half of the PUBLIC KEY.
Bob calculates phi(pq)=(p-1)(q-1) and chooses some number e relatively prime to phi(pq). Usually e=2^16+1=65537 but it can be as small as 3. e will comprise the other half of the PUBLIC KEY.
Bob then calculates the modular inverse, d, of e modulo phi(pq). Then means that de is congruent to 1 modulo phi(pq). (The remainder when de is divided by phi(pq) is 1)
Bob will distribute both parts n and e of the PUBLIC KEY, while d, the PRIVATE KEY, will be kept secret.
Alice, the sender, will convert her message into a number m, using the ASCII alphabet, converting each character one by one. She then calculates c, which is congruent to m^e, modulo n. This is the final encrypted message. If the message were to be sent over a connection, the only information an attacker would be able to glean would be this and the public key (originally made available to everyone).
Bob receives the message c (ciphertext), and computes c^d modulo n to retreive the original message as a string of numbers, at which point he can convert back into letters using ASCII.
Note that this is quite secure as long as Bob does not expose his PRIVATE KEY, d. d is the only way that anyone will be able to decrypt the message. Without it, anyone who intercepts the message will have a lot of brute forcing to do. Sophisticated computers can take upwards of days to crack a message sent with RSA. Very secure!
4. Practice Problems & Check for Understanding
It may be too difficult to crack messages sent using RSA, but it’s great to know how the steps of the encryption method work.
1. If p=11 and q=13, find phi(n), for n=pq.
2. Alice wants to send a message to Bob. If the first word she wants to send is "POOPYPANTS", find m, the ASCII-converted number.
3. Given the answer from problem 2, find c, the message sent over the connection, if the value of e is 3 and the value of n is the same as in problem 1.