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?