We consider the Diffie–Hellman key exchange scheme with certificates. We have a system with the three users Alice, Bob and Charley. The Diffie–Hellman algorithm uses p = 61 and α = 18. The three secret keys are a = 11, b = 22 and c = 33. The three IDs are ID(A)=1, ID(B)=2 and ID(C)=3.

For signature generation, the Elgamal signature scheme is used. We apply the system parameters p= 467, d= 127, α= 2 and β. The CA uses the ephemeral keys kE = 213, 215 and 217 for Alice’s, Bob’s and Charley’s signatures, respectively.

To obtain the certificates, the CA computes xi = 4*bi +ID(i) and uses this value as input for the signature algorithm. (Given xi, ID(i) follows then from ID(i) ≡ xi mod 4.)

  1. Compute three certificates CertA, CertB and CertC.

  2. Verify all three certificates.

  3. Compute the three session keys kAB, kAC and kBC.

I am confused on how to solve for this problem. The book does not really clarify how to do it well. In particular I have no idea what the 'bi' used to solve for xi in the signature is.

For Example: to get certificate A I know that I need to find CertA = [(kA,IDA),sig(kA,IDA)]

To find kA(the public key), I do α^a mod p (which I found to be 10)

To find the signature, I do Sa = (x-d*r)*kE^(-1) mod p-1, where r= α^(ke)mod p The question says that xi = 4*bi +ID(i), which would be the x, but I don't know what the bi is referring to, so I don't know how to solve for the signature.

And for the verification step, it says ver_subK_subpub,CA(CertB), but it does not say what the verification function is anywhere. How do I verify if it does not say how to?


1 Answer 1


I am currently working through this myself. I believe that the variable $b$ refers to the public key, which you will find using the $\alpha^a \bmod p$ equation you mentioned. Given that, you have all the information you need to find $x$.


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.