**DC10004 - Editorial**

**PROBLEM**

Link to the Practice Question can be found: https://www.codechef.com/DECI2020/problems/DC10004

**PREREQUISITE**

Cryptography

**DIFFICULTY**

Moderate

**PROBLEM**

Assume Eve has captured a few ciphertexts. You need to write the decryption program such that with given cipher text, eve can recover the plaintext.

**EXPLANATION**

- This cryptography problem is a mixture of Diffie Hellman and RSA algorithm.
- Here the public key is used to encrypt the plaintext and private key helps to decrypt the ciphertext to get back the plaintext.
- Here some public information is given. Now you need to write a program for the given public information (f,g,qn,α,Ya). We also have the private key Xb.
- From the given f, we can easily calculate the
**‘e’**by using the formula: f=(e×3)−1 - Calculate k; as k=Ya^Xb mod qn
- Calculate n by using the following formula; i.e. g=(k−n)
- From the n, find the value of p and q; as n=p*q
- From the value of p,q calculate the value of f(n)= (p−1)*(q−1)
- Now calculate the private key, d such that (e*d) mod f(n)=1
- Find the paint text § by using formula P = c^d mod (k-g); where
**‘c’**is the cipher text. - Convert the plaintext value into its corresponding letter as A=0,B=1,…,Z=25

**Solution:**

**https://drive.google.com/file/d/1WEwBcXfVLIc9xmAsS4xXob3-ReNFWHBX/view?usp=sharing**