Module 3 - SLP

Public-Key Cryptosystems

The RSA Algorithm

The pioneering paper by Diffie and Hellman introduced a new approach to cryptography and, in effect, challenged cryptologists to come up with a cryptographic algorithm that met the requirements for public-key systems. A number of algorithms have been proposed for public-key cryptography. Some of these, though initially promising, turned out to be breakable.

One of the first successful responses to the challenge was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT and first published in 1978. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption.

The RSA scheme is a cipher in which the plaintext and ciphertext are integers between 0 and n - 1 for some n. A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than 2¹⁰²⁴. We examine RSA in this section in some detail, beginning with an explanation of the algorithm. Then we examine some of the computational and cryptanalytical implications of RSA.

Description of the Algorithm

RSA makes use of an expression with exponentials. Plaintext is encrypted in blocks, with each block having a binary value less than some number n. That is, the block size must be less than or equal to log₂(n)  +  1; in practice, the block size is i bits, where  encryption and decryption are of the following form, for some plaintext block M and ciphertext block C.

C = M^e mod n

M = C ^dmod n = (M^e)^d mod n = M^ed mod n

(mod means to find the remainder. For example 10 mod 5 = 0 because 10 divided by 5 and remainder is 0, while 10 mod 3 = 1 because 10 divided by 3 and the remainder is 1)

Both sender and receiver must know the value of n. The sender knows the value of e, and only the receiver knows the value of d. Thus, this is a public-key encryption algorithm with a public key of PU  =   {e, n} and a private key of PR   =  {d, n}.For this algorithm to be satisfactory for public-key encryption, the following requirements must be met.

1. It is possible to find values of e, d, and n such that M^ed mod n  =  M for all M <  n.
2. It is relatively easy to calculate M^e mod n and C^d mod n for all values of M  <  n.
3. It is infeasible to determine d given e and n.

For now, we focus on the first requirement and consider the other questions later. We need to find a relationship of the form

 M^ed mod n = M

The preceding relationship holds if e and d are multiplicative inverses modulo ϕ(n). For two prime numbers p, q, ϕ(pq)   =   (p  -  1)(q  -  1). The relationship between e and d can be expressed as

ed mod Ï•(n) = 1

This is equivalent to saying

ed≡ 1 mod ϕ(n)

d≡ e^-1 mod ϕ(n)

 

Figure 4 summarizes the RSA algorithm.

 

Figure 4. The RSA Algorithm

An RSA example

For this example, the keys were generated as follows.

1. Select two prime numbers, p  =  17 and q  =  11.
2. Calculate n  =  pq  =  17  *  11  =  187.
3. Calculate ϕ(n)  =  (p  -  1)(q  -  1)  =  16  *  10  =  160.
4. Select e such that e is relatively prime to ϕ(n)  =   160 and less than ϕ(n); we choose e  =   7. (the greatest common divider (gcd) between e and ϕ(n)  is 1)
5. Determine d such that de  ≡  1 (mod 160) and d  <  160. The correct value is d  =   23, because 23  *  7  =   161  =   (1  *  160)  +  1;

The resulting keys are public key PU  =   {7, 187} and private key PR  =   {23, 187}.

The example shows the use of these keys for a plaintext input of M  =   88. For encryption, we need to calculate C  =   88⁷ mod 187. Exploiting the properties of  modular arithmetic, we can do this as follows.

88⁷ mod 187 = [(88⁴ mod 187) * (88² mod 187) * (88¹ mod 187)] mod 187

88¹ mod 187 = 88

88² mod 187 = 7744 mod 187 = 77

88⁴ mod 187 = 59,969,536 mod 187 = 132

88⁷ mod 187 = (88 * 77 * 132) mod 187 = 894,432 mod 187 = 11

 

For decryption, we calculate M   =   11²³ mod 187:

 

11²³ mod 187 = [(11¹ mod 187) * (11² mod 187) * (11⁴ mod 187)

       * (11⁸ mod 187) * (11⁸ mod 187)] mod 187

11¹ mod 187 = 11

11² mod 187 = 121

11⁴ mod 187 = 14,641 mod 187 = 55

11⁸ mod 187 = 214,358,881 mod 187 = 33

11²³ mod 187 = (11 * 121 * 55 * 33 * 33) mod 187

      = 79,720,245 mod 187 = 88

 

 

Figure 5. An example of the RSA algorithm

 

The Security of RSA

Five possible approaches to attacking the RSA algorithm are

• Brute force: This involves trying all possible private keys.
• Mathematical attacks: There are several approaches, all equivalent in effort to factoring the product of two primes.
• Timing attacks: These depend on the running time of the decryption algorithm.
• Hardware fault-based attack: This involves inducing hardware faults in the processor that is generating digital signatures.
• Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.

The defense against the brute-force approach is the same for RSA as for other cryptosystems, namely, to use a large key space. Thus, the larger the number of bits in d, the better. However, because the calculations involved, both in key generation and in encryption/decryption, are complex, the larger the size of the key, the slower the system will run.

To learn more about RSA, check the following sites:

RSA Encryption - Tutorial
http://www.woodmann.com/crackz/Tutorials/Rsa.htm

Number theory and RSA
http://www.sagemath.org/doc/thematic_tutorials/numtheory_rsa.html

RSA concept and example
https://www.youtube.com/watch?v=ADozzYA8sTs

RSA Encryption tutorial
http://www.eng.utoledo.edu/eecs/faculty_web/hledgard/discrete/upload/index.php?action=downloadfile&filename=Chap4%20RSA%20Tutorial.pdf&directory=Lecture%20Notes/CH04b%20Cryptography&PHPSESSID=eogbva1idanns4sijjihgkf2o4 rsa encryption tutorial

SLP Assignment

Perform encryption and decryption using the RSA algorithm, for the following:

 p = 3; q = 11, e = 7; M = 5

What is the public key PU? What is the private key PR? What is the cipertext C? How does the decryption to covert the ciphertext back to the plaintext M?

SLP Assignment Expectations

Use information from the modular background readings as well as the given resources. Also, you could use any good quality resource you can find. Please cite all sources and provide a reference list at the end of your paper.

The following items will be assessed in particular:

1. Your ability to consolidate ideas from reading materials and your understanding of the materials.
2. Your ability to write a report with strong argument.
3. Some in-text references to modular background readings.