RSA Encryption

Having written these four programs for the fx-50F:-

1. Multiplicative inverses in Zn
2. Is it prime?
3. gcd by subtraction
4. Exponentiation mod n

I am now in a position to be able to demonstrate one of the most widely used encryption methods on the web, RSA. The RSA cryptosystem was first described by Ron Rivest, Adi Shamir and Leonard Adleman in 1978. The complexity of decrypting, i.e. reading an encrypted message using RSA relies heavily on the difficulty of finding the prime factors of very large numbers. For example, if p₁ and p₂ are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p₁p₂=209365018607 but it would be relatively difficult to find their original factors if only the product was known. In the actual implementation of this system prime numbers of typically hundreds of decimal digits are used.

Here is a prescription for using RSA.

1. Choose two prime numbers p₁ and p₂
2. Calculate n=p₁p₂ and φ(n)=(p₁-1)(p₂-1)
3. Choose a positive integer encryption exponent e such that e is less than φ(n) and the gcd(e,φ(n))=1
4. Calculate the decryption exponent d which is the inverse of e modulo φ(n), that is ed≡1 (mod φ(n))
5. To encrypt a positive integer message m calculate m' where m'≡m^e (mod n)
6. To decrypt message m' calculate m≡(m')^d (mod n)

φ(n) is Euler's phi function and is the number of positive integers less than n that are coprime to n. If we have some plaintext message such as 'all aliens are friendly' then one method for encryption using RSA is to take each letter at a time, and encrypt it's numeric position in the alphabet (where 1=a, 2=b, etc). A space ' ' could be given designation 27.

This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p₁ and p₂ (and hence φ(n) and d) private. By doing so anyone can send an encrypted message to the receiver but only the receiver (hopefully) can decrypt the messages.