Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
1999-08-24
2002-10-01
Smithers, Matthew (Department: 2132)
Cryptography
Particular algorithmic function encoding
Public key
Reexamination Certificate
active
06459791
ABSTRACT:
The object of the present invention is a cryptography method of the so-called public key type based on the discrete logarithm using the calculation of a modulo p quantity.
It finds an application in the generation of digital message signatures, in an authentication session between two entities or in the encoding of data.
In such procedures, security is based on the extreme difficulty that there is in reversing certain functions and particularly the discrete logarithm.
This problem consists, given the mathematical relationship y=g
x
modulo p, which will be denoted hereinafter y=g
x
modp (which means y is the remainder of the division of g
x
by p), of finding x when p, g and y are known. This problem is impossible to resolve, in the current state of knowledge, as soon as the size of p reaches or exceeds 512 bits and the size of x reaches or exceeds 128 bits.
In such systems, there is in general an authority which supplies the number p of large size, constituting the modulus. The authority also chooses an integer g, referred to as the base, such that the set generated by g, i.e. the set formed by the numbers g
x
modp) for x belonging to the interval [0, p-1], is a subset of maximum size, at least 2
128
.
The parameters p and g are said to be “public”, i.e. they are supplied by the authority to all the users attached to 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.
A major drawback of the use of cryptographic systems lies in the need to have relatively large calculation and storage means because of the complex calculations which are performed.
This is because the calculation of the quantity g
k
modp consists in performing modular multiplications and this is expensive in calculation time and memory space. In simple electronic devices using only standard microprocessors, this type of operation can scarcely be performed.
For electronic devices having a specialised processor for this type of calculation, it is in spite of everything desirable to limit the calculation time and memory space necessary for the intermediate results.
This is because calculating the quantity g
k
modp is in general relatively expensive using the conventional method of “square-multiply”, known by the English abbreviation SQM, since it is equivalent on average to 3/2 Log
2
(p) multiplications.
According to this method all the powers of g are calculated, i.e. all the squares: g
0
, g
1
, g
2
. . . g
n
, when k is n bits long, since the required multiplications between these powers are performed (for example g
17
=g
1
·g
16
)
According to the simple “square-multiply” method, g
k
requires n/2 multiplications and n squares.
Where N signatures are to be supplied on a single occasion, Ng
k
is produced, and then a parallel calculation is performed.
The parallel “square-multiply” method requires N×n/2 multiplications and n squares.
A method proposed by E. BRICKEL et al, referred to by the abbreviation BGKW, makes it possible to reduce the number of multiplications in the case of the square-multiply method but introduces a requirement to store numerous precalculated constants and therefore the need to have a highly disadvantageous quantity of storage memories.
Introducing a parallel calculation of N values into this method entails the use of numerous registers for keeping the intermediate results.
This method therefore becomes much more constraining when there is a situation where it is a case of generating a large number of signatures in a very short time since in this case parallel calculation is introduced.
The object of the present invention is to remedy all these drawbacks. It affords a solution, flexible and inexpensive in calculation time and memory space, to the implementation of cryptographic algorithms for all cryptography systems and in particular by means of portable appliances of the microprocessor chip card type.
According to a first object of the invention, the proposed cryptography method reduces the number of modular multiplications so that savings in calculation times are obtained of 15 to 40% and more depending on the cryptography schemes used (Schnorr or El Gamal).
According to the invention, two solutions are proposed in order to reduce the number of multiplications, one consisting of generating “hollow” exponents k with few bits at 1, but of sufficient length to keep all the security for the system, and the other consisting in performing the calculations of the powers of g in parallel whilst combining the exponents with each other so as not to perform the same power calculation twice for a given exponent.
An object of the invention is more particularly a public key cryptography method based on the discrete logarithm using the calculation of the quantity q
k
modp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which this quantity acts, characterised in that it includes the following steps for the entity:
generating a random exponent k of length N bits, N being equal to n+b bits,
calculating the Hamming weighting C of this exponent and comparing it with a value h fixed in advance,
checking whether the random value k fulfils the condition C≧h
rejecting the random value k where the Hamming weighting is less than h and recommencing the generation of new exponents until an exponent satisfying this condition is obtained,
or keeping this value in the contrary case,
calculating the expression gkmodp from the kept value,
using this expression in an exchange of electronic signals with the other entity.
Another object of the invention is a public-key cryptography method based on the discrete logarithm using the calculation of the quantity g
k
modp where p is a prime number referred to as the modulus, k a random number normally of length n bits and g an integer referred to as the base, in which an entity E performs authentication and/or signature and/or encoding operations, comprising exchanges of signals with another entity in which several quantities of this type act, characterised in that it includes the following steps for the entity:
generating a set of random exponents k
j
of n bits of weighting a
i
expressed by the expression:
k
j
=&Sgr;a
i
2
i
calculating in parallel the powers of
g
2
i
whilst combining the exponents so that the powers of g already calculated for an exponent serve for other exponents in which they act,
for each given k
j
, calculating the powers of g not yet calculated and grouping together all these powers in order to obtain the required expression g
kj
modp,
using these expressions in an exchange of signals with the other entity.
According to a first embodiment, these steps of calculating in parallel and grouping together include the following operations:
combining the exponents in pairs in order to obtain exponents k
c
which are a reflection of their common parts and reiterating the combinations on the combination result obtained,
calculating quantities G
kc
for each value of k
c
such that:
G
kc
=g
kc
mod
p
combining an exponent k
j
with the exponent k
c
obtained for the combination to which this exponent belongs so as to eliminate the common parts and keep only the different parts,
defining exponents k′
j
which are a reflection of the different parts between a given exponent k
j
and a given exponent k
c
,
calculating quantities G
k′j
such that:
G
k′j
=g
k′j
mod
p
determining the expressions G
kj
modp by performing multiplications between the quantities G
kc
obtained at each iteration.
In a second embodiment, the steps of calculating in parallel and grouping together include the following operations:
combining the exponents together so as to form all the subsets of possible combinations of exponents having common parts,
defi
M'Raihi David
Naccache David
Gemplus
Plottel Roland
Smithers Matthew
LandOfFree
Public key cryptography method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Public key cryptography method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Public key cryptography method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2987989