To calculate d, we have to 1st calculate Ф(n)



Student ID: 102566527

Name: Mohammad omair alam

|Character |ASCII Value in Dec |

|M |77 |

|o |111 |

|h |104 |

|a |97 |

|m |109 |

|m |109 |

|a |97 |

|d |100 |

|o |111 |

|m |109 |

|a |97 |

|i |105 |

|r |114 |

|a |97 |

|l |108 |

|a |97 |

|m |109 |

|Total |1751 |

“ASCII values Reference: ”

There are 23 questions in Chapter 9. Public-Key and RSA in the book (Cryptography and Network Security Principles and Practices, Fourth edition by William Stallings)

Therefore,

Total mod (number of questions)

1751 mod 23 = 3

The question number I have to solve is the result + 1, i.e. Question number 3

Q) In an RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user?

Solution:

The private key can be written as {d, n}

To calculate d, we have to 1st calculate Ф(n)

Where Ф(n) is the number of prime factors of n

e = 31, n = 3599

It means that e is relatively prime to Ф(n), i.e. gcd (Ф(n), e) = 1

To find Ф(n), we have to first check whether n is prime or not, and if it is not, what are the prime factors of n.

Step1: To find prime factors of n

By using trial and error we find that n is not prime and the prime factors of n are

n = 3599 = 61 * 59

Thus p = 61 and q = 59 are both prime numbers.

Step 2: To calculate Ф(n)

Here we find the Euler’s totient function written as Ф(n), where Ф(n) is the number of positive integers less than n and relatively prime to n.

It is clear that for a prime number p,

Ф(p) = p-1

Now since we have two prime numbers p and q, with p ≠ q, Then for n= pq,

Ф(n) = Ф(pq) = Ф(p) * Ф(q) = (p-1) * (q-1)

Therefore

Ф(3599) = Ф(61) * Ф(59) = 60 * 58

= 3480

Step 3: Calculate d

We know that if gcd (Ф(n), e) = 1, then e has a multiplicative inverse modulo Ф(n)

Therefore

d ≡ e-1modФ(n)

i.e. d is multiplicative inverse of e mod Ф(n)

So now we use the extended Euclid’s algorithm to find the multiplicative inverse of e.

EXTENDED EUCLID (Ф(n), e)

1. (A1, A2, A3) ← (1, 0, m); (B1, B2, B3) ← (0, 1, b)

2. if B3 = 0 return A3 = gcd(Ф(n), e); no inverse

3. if B3 = 1 return B3 = gcd(Ф(n), e); B2 = e-1 mod m

4. Q = [A3/B3]

5. (T1, T2, T3) ← (A1 - QB1, A2 - QB2, A3 - QB3)

6. (A1, A2, A3) ← (B1, B2, B3)

7. (B1, B2, B3) ← (T1, T2, T3)

8. goto 2

Throughout the computation, the following relationships hold:

Ф(n)T1 + eT2 = T3

Ф(n)A1 + eA2 = A3

Ф(n)B1 + eB2 = B3

Now we construct a multiplication table

|Q |A1 |A2 |A3 |B1 |B2 |B3 |

| | | | | | | |

|- |1 |0 |3480 |0 |1 |31 |

| | | | | | | |

|112 |0 |1 |31 |1 |-112 |8 |

| | | | | | | |

|3 |1 |-112 |8 |-3 |337 |7 |

| | | | | | | |

|1 |-3 |337 |7 |4 |-449 |1 |

Now we need to check whether -449 is multiplicative inverse of 31 modulo 3480

Therefore

-449 * 31 = -13919

-13919 mod 3480 = -3479 mod 3480 = 1 mod 3480

Hence it is proved that d = -449 is multiplicative inverse of e = 31 mod Ф(n)

So the private key of this user will be {-449, 3599}

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download