I have this question which gives me q=71(my prime number) , a=7(generator), Yb=3(public key), m=30(message), c1=59(first cipher text) and he wants me to find c2 (second cipher text) I know that c2 = rM (r:one time key) , which means I have to find r=Y^k or r=c1^x but I dont have k nor x. The only solution is to solve the DLP is there any solution beside this?

  • $\begingroup$ could you please reformat the question? I don't understand what your variables represent. Like, what is your generator? Is it q? Because q is usually used to represent the order for group G with generator g. I understand that x is the private key but what is the public key? $\endgroup$ Apr 6, 2018 at 3:57
  • $\begingroup$ oh okay, q=71 is my prime number and a=7 is the generator while Yb=3 is the public key, m is the message and c1 is the first cipher text $\endgroup$ Apr 6, 2018 at 4:22

1 Answer 1


Ok, so now the question makes more sense to me.

Yes you are correct. Sadly, you cannot solve the problem without solving the DLP. This is simply because in the problem he didn't share his secret x or y. If he had shared y. You could have solved it. But your space is quite small, so it's not too hard to solve.

Public key = g^x = 7^x = 3 (mod 71)
Private key = x = 26 (since this is 7^26 == 3 mod 71) (DONT KNOW THIS)

C1 is :

C1 = g^y = 7^y = 59 (mod 71)
Private key = y = 3 (since this is 7^3 == 59 mod 71) (DONT KNOW THIS)

Message is mapped to:

m' = m mod 71
m' == 30 mod 71

Thus to find c2 you need:

c2 = m' * g^(xy)

But since you know neither x nor y you can't solve it. (of course the sample space was small so I could find it).

First find g^xy

g^(xy) = (g^x)^y = (3)^3 = 27

Your solution should thus be:

c2 == 30 * 27 (mod 71) 
c2 == 29 (mod 71)

Hope that helps!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.