 # DC10004 - Editorial

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: