# How to compute certificates using Diffie-Hellman key exchange with certificates and Elgamal signature scheme

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?

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$$.