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


Compute three certificates CertA, CertB and CertC.
Verify all three certificates.
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$.