1.Most widely accepted and implemented general purpose approach to public key encryption developed by Rivest-Shamir and Adleman (RSA) at MIT university.

2.RSA scheme is block cipher in which the plaintext and ciphertext are integers between 0 and n-1 for same n.

3.Typical size of n is 1024 bits. i.e n<2.

4.Description of Algorithm:

• The scheme developed by Rivest, Shamir and Adleman makes use of an expression with exponentials.
• Plaintext is encrypted in block having a binary value than same number n.

• Block Size $≤ \log_2 (n)$

  If block size=1 bits then, $2^1 ≤ n ≤ 2^i+1$

• Encryption and decryption are of following form for same plaintext M and ciphertext C.

  $C=M^e mod n$

  $M= C^d mod n$

  $M = (M^e)^d mod n$

  $M = M^{ed} mod n$

• 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= {c, n} and private key of PR= {d, n}.

5.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$

$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$

• For Decryption :

  $M = C^d mod 187 \\ \hspace{0.5cm}= 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$

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