RSA algorithm as shown below:

a) Key Genration :

• Select p,q…….. p and q both are the prime numbers, p≠q.
• Calculate n=p×q
• Calculate q(n) = (p-1) (q-1)
• Select integer….g(d ( (n), e)) =1 & 1< e < (n)
• Calculate d; d= e-1 mod (n)
• Public Key, PU= {e, n}

• Private Key, PR ={d,n}

  b) Encryption :

• Plaintext : m<n< p="">

• Ciphertext: C

  c) Decryption:

• Ciphertext: C

• Plaintext : M= Cd mod n
• Note 1 : (n) -> Euler’s totient function

• Note 2: Relationship between C and d is expressed as:

  ed (mod (n))=1

  ed = 1 mod (n)

  d = $e^{-1}$ mod (n)

6.Example:

• Key Generation :

  1. Select 2 prime numbers -> p=17 and q=11
  2. Calculate n = p×q =17 ×11=187
  3. Calculate = 16 × 10= 160 Select ‘e’ such that e is relatively prime to (n)=160 and e <

  4. Determine d such that :

     de =1 mod (n)

     d × 7 = 1 mod 160

$\hspace{2.7cm}\downarrow$

$\hspace{2.5cm}161$

$\hspace{2.5cm}d = e^{-1} \ \ mod \ \ (n) [161 /7 = \ \ div. (d) 23 \ \ \text{and remainder (mod) =1} \\ \hspace{2.5cm}d = 23$

1. Then the resulting keys are public key :

   PU = {7, 187 }

   PR = {23, 187 }

   Let M=88 for encryption

   $C= 88^7 mod (187) \\ 88 mod 187 =88 \\ 88^2 mod 187 = 7744 mod 187 =77 \\ 88^4 mod 187 =59969536 mod 187 = 132$

   $88^7 mod 187$ $= (88^4 mod 187) × (88^2 mod 187) × (88 mod 187) mod 187 \\ =(132 × 77 × 88) mod 187 \\ = 894432 mod 187 \\ =11$

$$\text{Figure 5.4 Solution of Above example}$$

• For Decryption :

  $M$ $= C^d mod 187 \ = 11^{23} mod 187$ $\hspace{1cm}11^1 mod 187 =11$ $\hspace{1cm}11^2 mod 187 =121$ $\hspace{1cm}11^4 mod 187 =14641 / 187 =55$ $\hspace{1cm}11^8 mod 187 = 214358881 mod 187 =33$ $\hspace{1cm}11^{23} mod 187$ $= (11^8 mod 187 × 11^8 mod 187 × 11^4 mod 187 × 11^2 mod 187 × 11^1 mod 187) mod 187 \\ =(33 × 33 × 55 × 81 × 11) mod 187 \\ = 79720245 mod 187 \\ =88$

Why the decrypted message is the same as plain text:

1.The Key Distribution Problem

• Private-key systems suffer from the key distribution problem. In order for a secure communication to occur, the key must first be securely sent to the other party. An unsecure channel such as a data network cannot be used.
• Couriers or other secure means are typically used. Public-key systems do not suffer from this problem because of their use of two different keys. Messages are encrypted with a public key and decrypted with a private key. No keys need to be distributed for a secure communication to occur.

2.Public-Key Cryptosystems

• A user wishing to exchange encrypted messages using a public-key cryptosystem would place their public encryption procedure, E, in a public file. The user's corresponding decryption procedure, D, is kept confidential. Rivest, Shamir, and Adleman provide four properties that the encryption and decryption procedures have three important steps:

  1. Deciphering the enciphered form of a message M yields M. That is, D(E(M)) = M

  2. E and D are easy to compute.

  3. Publicly revealing E does not reveal an easy way to compute D. As such, only the user can decrypt messages which were encrypted with E. Likewise, only the user can compute D efficiently.

  4. Deciphering a message M and then enciphering it results in M. That is, E(D(M)) = M

3.As Rivest, Shamir, and Adleman point out, if a procedure satisfying property (3) is used, it is extremely impractical for another user to try to decipher the message by trying all possible messages until they find one such that E(M) = C.

4.A function satisfying properties (1) - (3) is called a "trap-door one-way function". It is called "one-way" because it is easy to compute in one direction but not the other. It is called "trap-door" because the inverse functions are easy to compute once certain private, "trap-door" information is known.

5.The Public-Key Cryptosystem Encryption and Decryption Process

Suppose user A wants to send a private message, M, to user B.

• User A gets User B's public key from some public source.
• User A encrypts message M using B's public key. This produces a ciphertext message, C
• Ciphertext message C is sent over some communication channel
• Upon receipt, user B decrypts message C using their private key. This results in the original message M.