Method and apparatus for computing a shared secret key

#1. Field of the Invention

#The present invention relates to cryptographic systems, and more particularly to a method for computing a shared secret key.

#2. Description of the Prior Art

#These and other features of the preferred embodiments of the invention will become more apparent in the following detailed description in which reference is made to the appended drawings wherein:

#FIG. 1 is a schematic representation of a cryptographic system.

#FIG. 2 is a flowchart showing a method performed by the correspondents in FIG. 1.

#Referring to FIG. 1, a cryptographic system is shown generally by the numeral 10. A pair of correspondents 12, 14, referred to as Alice and Bob, communicate over a network 16. Each correspondent has an arithmetic logic unit (ALU) 18, 20. The ALU can be a general-purpose computer, with a cryptographic unit, which implements cryptographic protocols from instructions provided by software. The software may be provided on a data carrier or in memory. Each correspondent has a long-term private key a, b and a corresponding long-term public key YA, YB. Each correspondent has access to an authentic copy of the other correspondent's long-term public key.

#It is desired to share a key between the correspondents using the MQV protocol. It is recognized that the MQV equations can be reorganized to provide efficient computations without necessarily using the truncation operation The reorganization proceeds as follows.

#The formula K=(RB(YB)RB)sA that is used to determine he key can be rearranged as K=(RB(YB)RB)sA=RBsAYBsARB, using the notation above. This rearrangement allows the key to be computed by using a technique known as simultaneous multiple exponentiation, which uses only one set of squares.