Patent ID: 8572367

Claim:
A method of computing a public key from an implicit certificate associated with a certificate authority in a cryptographic communication system based on an underlying group of order n; the method being performed by a computing device in the communication system; the device comprising a cryptographic unit; the method comprising: the device operating on the implicit certificate in the cryptographic unit to derive an integer e; the device deriving a pair of integers e 1 and e 2 from the integer e in said cryptographic unit, each of the integers e 1 and e 2 having a bit length less than the bit length of the integer e, and the ratio of the pair of integers e 1 and e 2 corresponding to the integer e; and the device computing the public key by combining the integers e 1 and e 2 with public key contribution data derived from said implicit certificate and a static public key of the certificate authority, wherein the pair of integers e 1 and e 2 are derived using a truncated Extended Euclidean Algorithm.