RSA Public Key Encryption

Background

Public key encryption system has three parts:

1. Key Generation: The recipient of a secret message generates a public key which is shared, and a private key which is kept secret. The keys are generated in a way that conceals their construction, and makes it difficult to find the private key by only knowing the public key.
2. Encryption: A secret message to any person can be encrypted with their public key.
3. Decryption: Only the person being addressed can easily decrypt the secret message using the private key.

Objectives

• Demonstrate how a public key encryption system works using the RSA algorithm with small prime numbers.

Steps

1. Generate public and private keys.

A private key and a public key will be generated from two prime numbers.

• Choose two different prime numbers
  p = 5 11 17 23 31     q = 7 13 19 29 37    
  

  n =	n = p x q
  φ =	φ = φ(n) = (p - 1) x (q - 1)
  e =	arbitrary, but less than n and relatively prime to φ
  d =	inverse of e modulo φ such that (e x d) % φ = 1

  The public key is the pair of e and n.

  The private key is the pair of d and n.

  Only the public key, composed of e and n, are published. The other numbers p, q, φ and d must be kept secret.

  The larger the numbers involved the more time consuming it is to figure out the value of d because:

  • It is difficult to calculate d without knowing the value of φ.
  • It is difficult to factorize n into p times q, which is needed to compute the value of φ.
    • The larger p and q are, the longer the factorization process.
2. RSA Encryption

First, we need the public key of the person to whom we want to send the message.

• (e,n) = ( , )    

  Next we need the message. For simplicity, use just one letter.

  In secure applications letters are never encrypted individually, but in whole blocks.

• Select a letter to cipher: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

• Now encode the letter by its index in the alphabet.
      m =

• Encryption is simple. Use the formula m' = m^e % n
  m' =

  The value of m' is the encrypted message and is sent to the recipient.

3. RSA Decryption

First we need the private key of the recipient of the encrypted message.

• (d,n) = ( , )    

• Next we need the encrypted message:
  m' =    

• is simple. m = (m = m'^d % n)

• The should match with the above chosen letter: _ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Bonus

4. Greatest Common Divisor (GCD)

Two numbers are said to be relatively prime when they have no divisor in common. In other words, their greatest common divisor (GCD) is 1.

The greatest common divisor can be efficiently computed via the Euclidean Algorithm.

• m =    n =   

  GCD(m,n) =

5. Cofactors (Extended GCD)

The greatest common divisor d of two numbers, m and n can be written as

d = c₁ x m + c₂ x n where c₁ and c₂ are cofactors. They can be computed via a simple extension of the Euclidean Algorithm.

The computation of the cofactors is useful for finding the multiplicative inverse of a number n with respect to a module m.

Given two relatively prime numbers, m and n, such that the value of their GCD is 1 the cofactors are

1 = c₁ x m + c₂ x n

And therefore     c₂ x n % m = 1

Thus c₂ is the multiplicative inverse of n % m

• m =    n =   

  GCD(m,n) =    c₂ =

6. Power Modulo

Both encryption and decryption need a power reduced modulo of module m. It is inefficient to compute the whole power before starting the modulo computation as it involves large numbers. Thus, a more efficient method is reducing the intermediate powers of modulo m.

• n =    e =    m =   

  n^e % m =

Congratulations! You have successfully investigated and witnessed how RSA public key cryptosystem works.