Find the multiplicative inverse of following using extended Euclidean algorithm.

i. $8^{-1}$ mod 77

ii. $7^{-1}$ mod 15

Also explain the use of Euler’s theorem in RSA cryptosystem.

1) Fermat’s Theorem (1M May 2014) :

• It states that , if p is prime and a positive integer not divisible by P then

  $a^{p-1} =1$ (mod p)

  Ex. $a=7 , p=19 \\ (a^{p-1} = 719-1 = 718 )$

  $7^2 =49 = 11 (mod 19) \\ [49/ 19 -\gt div= 2 and rem =11]$

  $7^4 = 7^2 × 7^2 = 11 × 11 = 121 -\gt 7 (mod 19) \\ [121/19 -\gt div =6 and rem =7 ]$

  $7^8 = 7^4 × 7^4 = 7 × 7 =49 -\gt 11( mod 19)$

  $7^{16} = 7^8 × 7^8 = 11 × 11 = 121 -\gt 7 (mod 19 )$

2) Euler’s Theroem (1M May 2014) :

• For every ‘a’ and ‘n’ which are relatively prime

  $a^{f(n)} = 1 (mod n)$

  Ex.

  i. $a =3, n=10, f (10) =4 \\ a^{f(n)} = 3^4 = 01 (mod 10) = 1 (mod n)$

  ii. $a =2 , n=11, f(11) = 10 \\ a^{f(n)} = 2^{10} =1024 = 1 (mod 11) = 1 (mod n)$

1) Comparing with following equation,

$$a^{∅(n)-1} mod \ n= a^{-1} mod \ n$$

We get, a=8, n= 77

$Φ(15)$ $= Φ(11)* Φ(7) \\ =10*6 \hspace{5cm} \text{{as for prime numbers, Φ(n)= n-1}} \\ = 60$

Putting the values in above equation,

$8^{59}mod 77= 8^{-1} mod 77$

We need to find value of left hand side.

Now, dividing 59 into powers of 2,

$7^{59}=7^{32}*7^16*7^8*7^2*7^1 \\ 7^{59} mod 77=(7^{32}*7^16*7^8*7^2*7^1)mod 77$

8 mod 77=8

$8^2 mod 77=64$

$8^8 mod 15$ $=(8^2 mod 15)^3 \ mod \ 77 \\ =64^3 \ mod \ 15 \\ =36$

$8^{16} mod \ 15$ $= (8^8 \ mod 15)^2 mod \ 77 \\ =36 \ mod \ 77 \\ =64$

$8^{32}mod 15$ $=(8^{16} mod 15)^2 mod \ 77 \\ =64^2 \ mod \ 77 \\ =15$

$7^{59} mod 77$ $=(7^{32}*7^16*7^8*7^2*7^1)mod 77 \\ =(8*64*36*64*15)mod 77 \\ =(8*64^2 \ mod 77*36*15) \ mod \ 77 \\ =(8*36*71) mod 77 \\ =43$

2) a=7, n= 15

$Φ(15)$ $= Φ(5)* Φ(3) \\ =4*2 \hspace{3cm} \text{{as for prime numbers, Φ(n)= n-1}} \\ = 8$

Putting the values in above equation,

$7^7 \ mod 15= 7^{-1} \ mod \ 15$

We need to find value of left hand side.

Now,

$7^7=7^4 *7^2*7^1$

$7^7 mod \ 15=(7^4 *7^2*7^1) \ mod \ 15$

7 mod 15=15

$7^2 mod 15=4$

$7^4 mod \ 15$ $=(7^2 \ mod \ 15)^2 mod \ 15 \\ =4^2 mod \ 15 \\ =1$

$7^7 \ mod \ 15$ $=(15*4*1) \ mod \ 15 \\ =60 \ mod 15 \\ =0$

Use of Euler’s theorem in RSA algorithm:

For RSA algorithm to be satisfactory for public-key encryption, the following requirements must be met.

1. It is possible to find values of e, d, n such that Med mod n = M for all M < n.
2. It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n.

3. It is infeasible to determine d given e and n.

   • Now to satisfy first condition, We need to find a relationship of the form

     Med mod n = M

   • The preceding relationship holds if e and d are multiplicative inverses modulo ϕ(n),

     where ϕ(n) is the Euler totient function.

     for p and q prime, ϕ(n) = (p - 1)(q - 1).

   • The relationship between e and d can be expressed as

     ed mod ϕ(n) = 1, which can also be written as

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

   • if e and n are relatively prime then, we can make use of Euler’s theorem to find the value of d.