Method of cryptography with public key based on the discrete log

Details Method of cryptography with public key based on the discrete log Method of cryptography with public key based on the discrete log

1997-09-24

1999-08-31

Cangialosi, Salvatore

Cryptography

Particular algorithmic function encoding

Public key

H04L 900

Patent

active

059463970

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

1. Field of the Invention
An object of the present invention is a method of cryptography known as a public key method based on the discrete logarithm, making use of a variable modulo p.
It can be applied in the generation of digital signatures of messages or in a transfer of authentication between two entities.
In such procedures, security is based on the fact that it is extremely difficult to reverse certain functions and more particularly the discrete logarithm.
Given the mathematical relationship y=g.sup.x modulo p which shall hereinafter be written as y=g.sup.x modp (which means that y is the remainder of the division of g.sup.x by p), this problem consists in finding x when p, g and y are known. With the present state of knowledge, this problem is impossible to resolve once the size of p reaches 512 bits or goes beyond it and once the size of x reaches 128 bits or goes beyond it.
In such systems, there is generally an authority that gives the large-sized number p constituting the modulus. The authority also chooses an integer g, called the base, such that the set generated by g, namely the set p-1! is a subset of maximum size, at least 2.sup.128.
The parameters p and g are said to be "public", that is, they are given by the authority to all the users coming under this authority.
According to certain variants, these parameters are chosen individually by each user and, in this case, form an integral part of its public key.
2. Description of the Related Art
A major drawback of the implementation of cryptographic systems lies in the need for relatively large computation and storage means owing to the complex computations that are performed.
Indeed, the computation of the variable g.sup.k modp consists of the performance of modular multiplication operations and this is costly in terms of computation time and memory space. In simple electronic devices that use only standard microprocessors, this type of operation can hardly be performed.
For electronic devices possessing a processor that is specialized for this type of commutation, it is nevertheless desirable to limit the computation time and the memory space needed for the intermediate results.
Indeed, it is in general relatively costly to compute the variable g.sup.k modp by the standard square-multiply or SQM method since it is equivalent on an average to 3/2 Log.sub.2 (p) multiplication operations.
According to this method, a computation is made of all the powers of g, namely when k has a length of n bits, all the squares:
According to the simple "square-multiply" method, g.sup.k requires n/2 multiplication operations and n squares.
A method proposed by E. BRICKELL et al., known as the BGCW method, reduces the number of multiplication operations in the case of the square-multiply method but introduces a need for the storage of numerous precomputed constants and hence the need to have available a quantity of storage memories that is extremely disadvantageous.


OBJECTS AND SUMMARY OF THE INVENTION

It is an object of the present invention to overcome all these drawbacks. It provides for an approach, that is flexible and costs little in terms of computation time and memory space, to the implementation of cryptographic algorithms for all systems of cryptography and especially by portable machines of the microprocessor based chip card type.
According to the invention, two approaches are proposed. Both approaches are based on a common principle in which a data base of random values is formed and these values are combined to determine exponents k used for the exchanges between two entities.
With the two approaches proposed, the computation of an exponent k requires fewer than 30 modular multiplication operations for a memory space that is quite acceptable for carriers such as chip cards.
An object of the invention more particularly is a method of public key cryptography based on the discrete logarithm that makes use of the computation of the variable r=g.sup.k modp where p is a prime number called a modulus, the exponent k is a r

REFERENCES:
patent: 5124117 (1992-06-01), Tatebayashi
patent: 5297206 (1994-03-01), Orton
patent: 5313521 (1994-05-01), Torii
patent: 5521980 (1996-05-01), Brands
patent: 5604805 (1997-02-01), Brands
patent: 5724425 (1998-03-01), Chang et al.
Advances in Cryptology--Europcrypt '92, "Fast Exponentiation With Precomputation", Ernest F. Brinkell et al., May 24-28, 1992, pp. 200-207.
AT&T Technical Journal, "Interactive Identification and Digital Signatures", Ernest F. Brickell et al., Nov.-Dec. 1991, vol. 70, No. 6, pp. 73-86.
Journal of Cryptology, 1991, "Efficient Signature Generation by Smart Cards", C.P. Schnorr, vol. 4, No. 3, pp. 161-174.

Affiliated with

Also associated with

Rating

Method of cryptography with public key based on the discrete log does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of cryptography with public key based on the discrete log, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of cryptography with public key based on the discrete log will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2428225