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:

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