CA2288767A1 - Pseudo-random generator based on a hash coding function for cryptographic systems requiring random drawing - Google Patents

Abstract

The invention concerns a cryptographic system, normally requiring the drawing of a random number k, which is a whole number. The system is characterised in that it is operated by replacing said random number k by the value h (m/secret) in which h is a hash coding function, m is the message intervening in said system and "secret" is a secret unknown to the world outside the cryptographic system. The invention is particularly applicable to communicating media such as smart cards, PCMCIA cards, badges, contactless cards or any other portable medium.

Description

GENERATE PSEUDO-RANDOM HASE ON A CHOPPING FUNCTION
FOR CRYPTOGRAPHIC SYSTEMS REQUIRING HAZARD DRAWING
The present invention describes a system for generate digital signatures or cryptograms requiring the drawing of hazards (typ: only DSA, E1-Gamal, Fiat-Shamir, Guillou-Quisquater for the signatures, E1-Gamal and McEliece for encryption), by signature devices or encryption (typically microprocessors) without i0 hardware or software resources allowing the drawing of hazards.
It also provides a defense, or defense, against certain threats (typically message encryption short and the recent attacks published by Coppersmith et al.
to Eurocrypt '96 in the articles ~ Low Exponent wi th Related Message "and ~ Finding a small root of a univariate modular equation ”) by generating inexpensively, ie little expensive, of a random sequence allowing to complete the information to be processed.
It also allows the generation of factors of blindness, used as part of the mechanisms of blank signatures or random makeup.
It can finally be used in protocols to exchange Diffie-Hellman keys.
Despite widespread dissemination and good acceptance of the concept of the smart card on the part of the public, most practical applications only appeared here a few years, mainly due to the limitations of computing power of cards. Progress in 3o non-volatile information storage capacity, security and circuit technology (eg EEPROM) encourage the rapid emergence of new generations of

2 increasingly ambitious maps and applications such as the new American digital signature standard (DSA).
A big limitation of smart cards as support implementation of public key algorithms is the need (frequently encountered), to have a device generating random numbers on board. Indeed, the setting point of such a device, also called generator, turns out complex and often unstable (sensitivity to phenomena outside the map such as room temperature or l0 voltage applied to the card). In the event that such systems cryptographic are implemented on a computer, others phenomena, due to the very nature of random generators software disrupts the quality of hazards. Typically, a very popular hazard generation method is to measure the time between two keys on the keyboard by the user. Recent fraud cases show that this kind of generators can be biased by simulating the keyboard to using a fraudulent device whose time between the various keys is known to the attacker.
The present invention provides a substitution solution allowing the implementation of cryptographic systems requiring the drawing of a good quality hazard on software or hardware platforms.
1. having no means of generating hazards, 2. or generating poor quality hazards,

3. or when the system designer suspects that external elements could compromise the quality of hazards by modification of external conditions and operating interior.
The present invention applies to various families cryptographic algorithms. For better understanding of the invention and before resuming the content of claims in the description it is useful to recall the main characteristics of said families of cryptographic algorithms to which applies ~ 5 The invention, these being six in number.
The first family of applications concerns the diagrams of E1-Gamal signature.
El-Gamal's signature algorithm described in the article entitled "A public-key crypt; osystem and a signature scheme based on discrete logari.thms ”and: published in the IEEE journal Transactions on Information Theory, vol. IT-31, no. 4, 1985, pp. 469-472, gave rise to several algorithms for known signature: Schnorr, patented in the United States under the reference 4.995.082, or GOST 34-10 - Russian federal standard of digital signature; Signature American DSA-Standart digital.
Once illustrated within the framework of the DSA, the application of the present invention to other algorithms of the same family could easily be implemented by those skilled in the art.
2o In the following, it is called The DSA algorithm.
The Digital Signature Standard (DSA, American patent no. 5.231.668 entitled "Digital Signature Algorithm") has been proposed by the US National Institute of Standards and Technology to provide an appropriate basis for applications requiring a digital signature instead of classic signatures. A DSA signature is a pair of large numbers represented in ur ~ computer by strings of binary digits. The digital signature is calculated at using a set of calculation rules (the DSA) and a set parameters in a way to certify both

4 the identity of the signatory and the integrity of the data. The DSA
allows to generate and verify signatures.
The signature generation method makes use of a private key (to produce a digital signature). The verification process uses a public key that matches to the secret key without however being identical to it. Each user has a key pair (public, secret). I1 is assumed that the public keys are known to all then that secret keys are never revealed. Every person 1o has the capacity to verify the signature of a user in using their public key but signatures cannot be generated other than by using the secret key of the user.
The DSA parameters are.
- O A first p module such as 2L1 <p <2L for 512 <_ L <_ 1024 and L = 64 a for any a.
OO A prime module q such that 2lss <q <2lso and p-1 is a multiple of q.
OO A number g, of order q modulo p such that g - hop-1 ~ / q mod p, where h is an integer satisfying 1 <h <p-1.
~ A number x, randomly generated or pseudo randomly.
D A number y defined by the relation. y = g "mod p.
~ A randomly generated or pseudo number k randomly such that 0 <k <q.
The integers p, q and g are parameters of the system can be published and / or shared by a group of users. The keys, secret and public, of a signatory are respectively x and y. The parameters x and k are used for signature generation and must be kept WO 98lS1038 PCT / FR98 / 00901 secrets. The parameter k must be regenerated for each signature.
In order to sign a message m (hashed value of a file initial M), the signer calculates the signature (r, s) by.
k

5 r = g mod p mod q and s = (m + xr) / k mod q, where the division by k means modulo q (ie 1 / k is the number k 'such as kk' - 1 mod q).
For example, if q = 5 and k = 3 then 1 / k = 2 because 3x2 - 6 --- 1 mod 5.
lo After testing that r and s ~ 0, as explained in the description of the DSA, the signature {r, s ~ is sent to checker who calculates.
w = 1 / s mod q ~ ul = mw mod q OO u2 = rw mod q ~ v = gul yua modp mod q ~ And compare if v and r are equal in order to accept or reject signature.
The second family also relates to patterns of signature; these are diagrams derived from protocols to zero disclosure A second family of signature algorithms to which apply the invention are those derived from the protocols to zero disclosure (typically Fiat-Shamir or .Guillou-Quisquater patented in the United States respectively under references 4,748,668 and 5,140,634). Also, it will be described . only one of these protocols. Once applied to the Guillou and Quisquater algorithm, the extension of - the invention to other algorithms of this family turns out obvious to those skilled in the art.

_ 6 The parameters of the _Guillou-Quisquater algorithm are Two secret prime numbers p and q of size at least.
equal to 256 bits; these prime numbers are generated from a particular way in which detail is not essential to the understanding of the present invention but may however be found in the book "Applied Cryptography, Algorithms, Protocols and Source Codes ”, by Bruce Schneier (Translation of Marc Vauclair), Thomson Publishing Editions;
i0 20 A public module n = pq and an ID string representing the identity of the signer;
O A public exponent v and a secret key B such as B "
ID = 1 mod n; parameter B must remain secret;
~ In order to sign the message m, the sender draws a random k, calculates the initial witness T - k "mod n and generates the signature.
d = h (T, m) and D = k Bh ~ T'm) mod n;
OO The verifier verifies the authenticity of the signature by checking that.
d = h (T ', m) with T' = D "Idd.
The third family of applications concerns the diagrams of public key encryption requiring a hazard.
The first encryption algorithm requiring a random described below is that of El Gamal.
The parameters of this algorithm are:
O A first p module (at least 512 bits);
O A number g, of order p-1 modulo p (ie such that, for any integer u, 0 <u <p-1, gu ~ 1 mod p;
OO A number x, 1 <_ x _ <p-2, randomly generated or pseudo randomly;
A number y defined by the relation. y = g "mod p;

_ 7 ~ A number k randomly generated or pseudo randomly such that 0 <k <q.
The integers p and g are system parameters that can be published, and / or shared by a group of users. The . 5 public encryption key is the number y, and the key decryption secret is the number x.
The parameter k is used for the generation of the cryptogram, and does not must not be disclosed. In addition, it must be regenerated each time encryption.
lo The encryption of a message m, 0 <_ m 5 p-1, is the pair of integers (r, s), where:
r = gk mod p and s = m yk mod q.
To find the message m, the receiver of the cryptograms (which has x), calculates:
15 s / r "mod p, which is precisely mr.
A second encryption algorithm requiring the generation of a hazard is the McEliece scheme, based on a problem of code theory, specifically using 20 a particular class of codes known as Coppa. The general idea is to disguise a Coppa code as a code any linear; there is indeed an efficient algorithm to decode a Coppa code but on the other hand to decode a code general linear is a difficult problem. The receiver 25 knowing the information used to disguise the code, will therefore be able to decipher the message by decoding the Coppa code got.
The parameters of the McEliece algorithm (all . The following formulas are heard in GF (2)) are.

_ 8 Numbers n, k and t, parameters of the system; in the original article describing its encryption scheme, McEliece proposes n = 1024, t = 50 and k = 524;
OO A secret key composed of.
~ A generator matrix G of a binary Goppa code of size n and dimension k correcting t errors and the algorithm corresponding decoding;
A random invertible matrix S of dimension kxk;
~ A random permutation matrix P of size n;
OO A corresponding public key composed of.
~ The generator matrix T - SGP of a code equivalent to G;
~ The correction rate t;
~ Encryption by the McEliece algorithm of a message k of k bits is performed by calculating.
c = mT + e where e is a randomly chosen error vector of weight of Hamming equal to t.
The decryption of c is done by calculating.
cP 1 - m TP 1 + eP 1 - mSG + eP 1.
Since e is of weight t, eP-1 is also of weight t. The vector cP 1 is therefore correctable by code G..Decoding, the decipherer gets mS, then m because he knows S and S is reversible.
The fourth family concerns cryptographic schemes requiring random padding.
I1 is not uncommon that the data to be encrypted must first be "padded", that is to say completed to obtain a data of a fixed size. The illustration of this aspect can be given by the example of RSA encryption, published in 1978 by R. Rivest, A. Shamir and L. Adleman then patented under the title Cryptography Communications System and Method ~ and the reference US 4,405,829.
An RSA cryptogram is a large number represented in a computer by strings of binary digits or hexadecimal. The cryptogram is calculated using a software (program) and / or hardware calculation resource (electronic circuit) implementing a series of rules calculation (the encryption algorithm) to be applied When processing a set of parameters accessible to 1o all in order to hide the content of the data processed. In a way analog, the cryptogram is decrypted using a software or hardware computing resource implementing a series of calculation rules (the decryption algorithm) applied (by the cryptogram receiver) on a set secret parameters and the cryptogram.
The encryption process uses a public key in order to produce the cryptogram. The decryption process uses a private key that matches the secret key without however be identical to it. Each user has a key pair (public, secret) and we assume that the keys are known to everyone while secret keys are not are never revealed. Anyone has the ability to encrypt a message for a user using the public key of the latter but cryptograms cannot be decrypted other than using the user's secret key.
The parameters of the RSA algorithm are.
. ~ O Two secret prime numbers p and q of size at least equal to 256 bits. These prime numbers are generated in a way . particular whose detail is not essential to the understanding of the present invention but may however be found in the book "Applied Cryptography, Algorithms, Protocols and Source Codes ”, by Bruce Schneier (Translation of Marc Vauclair), Editions Thomson Publishing;
OO A public module n = pq;
O A pair of exponents noted (e, d) such as.
ed = 1 mod {p-1) (q-1).
The exponent e, called "encryption exponent", is accessible to all while "the deciphering exponent" d must remain secret.
In order to encrypt the message m, the sender calculates the 10 cryptogram c - me mod n and the receiver decrypts c in calculating m = cd mod n.
The security of the algorithm, based on the problem of factorization, allows for a choice of parameters made in the rules of the art to ensure in the general case of encryption of messages the size of the module and not having no special relationships between them confidentiality between the sender and the receiver of the encrypted information.
In contrast, recent attacks presented by Coppersmith et al. at Eurocrypt '96 {notably in "Low Exponent with Related Message "and ~ Finding a srnall root of a univariate modular equation ”published in the proceedings of the conference at Springer-Verlag under the reference LNCS 1070) show that the existence of polynomial relationships between messages encrypted with the same small exponent, this which can very well happen as part of a application where the encryption device generally uses to encrypt a public exhibitor e = 3 for reasons of performance, allows effective attacks revealing the text clear.
A possible parry is to pad the message with a random sequence (but taking certain precautions) or to break any relationship between the messages, which, next applications, is not always possible.
We will then introduce in step ~ the modification next .
In order to encrypt the message, the sender generates a sr sequence with a certain degree of randomness and calculates the cryptogram c = (m ~ sr) ~ mod n, the sign ~ indicating concatenation; the receiver decrypts c by calculating cd mod n and find m by subtracting the padding.
l0 Exact methods of message padding can vary according to standards, application needs or level required for security.
The fifth family concerns the factors of blindness and signatures in white.
Basic functionality, called primitive by man of art, used in many schemes and protocols cryptographic is the blank signing mechanism of a message given. This functionality discovered and patented by Chaum (US patent n ° 4,759,063 and European patent n ° 0139313) allows of 2o have a message signed without the signer being able to take knowledge of the message. It requires the generation of a blindness factor, to hide the message, known only to the person requesting the signature. The mechanism used also applies to signature patterns of the type ~ El Gamal than RSA.
Once illustrated in the context of the RSA, the application of our invention to other signature algorithms turns out obvious to those skilled in the art. I1 will be described here only the blank signing mechanism based on RSA.

_ 12 By using the notation used in the context of the description of the fourth application family of the invention, the RSA signature is thus defined.
s = md mod n;
verification is done naturally.
se mod n = (md} e mod n = m.
The steps to obtain a blank signature by the sender E of a message m are.
E generates a random number k, calculates the factor ke mod n and sends m '= mke mod n to the receiver or (signor);
OO the receiver calculates s' - m'd mod n and which is the signature of m 'and send s' to E;
OO E calculates s' / k - (mke) d / k - mdked / k - md mod n, and therefore obtains the signature s of m.
This factor multiplication technique blindness is also used in the context of make-up random (European patent application EP 91402958.2).
The random makeup method is used for example in the case where a device A wants to subcontract operations to a device B while not wishing to reveal it completely operands. Take for example a reduction operation modular: A can camouflage the number to be reduced modulo n by multiplying by a random multiple of the module. So if A
wishes to obtain c - ab mod n, it can generate a random k, calculate c '- ab + kn {kn mask the product ab), and send c' to device B for reduction.
Device B calculates c 'mod n = ab + kn mod n = c.
This technique finally makes it possible to offer a parade to Kocher's attacks described in Crypto '96 ("Timing attacks on Implementation of Diffie-Hellman, RSA, DSS and Other Systems ”, conference proceedings published at Springer-Verlag under the reference LNCS 1109) which are based on the measurement of time required by operations manipulating quantities secrets to guess the values.
Indeed, an effective display is multiplication, by a factor of blindness, secret magnitudes manipulated in order to decorrelate the calculation time and the magnitude. In the case of the RSA signature for example (the person skilled in the art will know extend this result to all the algorithms concerned by the attack, in particular all those involving the calculation of a modular exponential with a secret exponent), using the notation used in the description of the fourth family of application of the invention, it suffices that.
the signer generates a random number k and calculates.
d '- d + k (p-1) (q-1), D it then generates the signature of m by calculating ma- - ma + xcP-l ~ e-1> - ma (mcP-n tq-1>) x _ ma mod n.
The sixth family concerns key exchange schemes based on the Diffie-Hel: lman method.
Diffie-Hellman's key exchange algorithm is the first public key algorithm described in ~ New Directions in Cryptography ”published in IEEE Transactions on Information Theory, vol. IT-22, No. 6 and patented in the United States under the reference 4.200.770. The method implements two participants (or devices) wishing to agree on secret information to through an insecure channel.
The parameters of the Diffie-Hellman protocol are the following.
O Two public parameters on which the device sender (A) and the device (B) get along. a number first p of at least 512 bits and an integer g, primitive root WO 98/51038 PCTlFR98 / 00901 modulo p. These two parameters can be optionally common to a group of users;
the protocol is as follows.
In order to share secret information, the two devices perform the following operations.
~ device A generates a random number x and calculates the quantity X = g "mod p;
~ device B generates a random number y and calculates the quantity Y = gy mod p;
~ the two devices exchange the quantities X and Y
~ the device A calculates key = Y "mod p;
~ device B calculates key '- XY mod p.
The two devices thus share at the end of the protocol knowledge of the key quantity '- key = g "Y mod p.
Both devices can then use the secret “key” quantity for exchanging messages by a secure channel using symmetric encryption algorithm taking as parameters the quantity "key" and the message to encrypt.
Following the description of the different families application of the invention, it is desirable to specify the main advantages of the invention.
Economic constraints linked to the card market puce, lead to constant research with a view to improving production costs. This effort often involves the use of simplest possible products. This state of affairs induces a constantly growing interest in solutions allowing to implement public key algorithms on micro inexpensive 8-bit controllers, at the heart of 80C51 or 68HC05 for example.

WO 98/51038 pCT / FR9g ~ 0pg01 The main advantage of the inventive process compared to previous proposals for digital signatures or encryption lies in the ability to calculate signatures or perform encryption operations without however requiring a hazard generator on board the circuit signing or encrypting.
For the clarity of the description, it is necessary to specify that the generation of keys and parameters of the various systems presented remains identical. We will therefore refer to patents and usual works in order to generate, in the rules of art, the various elements necessary for the algorithms of signature, authentication and encryption presented in the invention. A practical reference book may be "Applied Cryptography, Algorithms, Protocols and Codes Source ”, by Bruce Schneier (Translation by Marc Vauclair), Editions Thomson Publishing.
The present invention relates to a cryptographic system, normally requiring the drawing of a hazard k, the hazard being a whole; the system is characterized in that it is implemented work by replacing said alea k by the quantity h (m ~ secret) where h is a hash function, m is the intervening message in said system and "secret" is a secret unknown to the world outside the cryptographic system.
More specifically, the cryptographic system of the invention includes at least.
- a public key signature system;
- a public key encryption system;
- a random padding system;
- a factor generation system blindness;
- a key exchange protocol.

_ 16 In the case of a cryptographic system that includes a DSA, Schnorr, E1- type public key signature system Gamal, GOST 34.10 or the IEEE standard for elliptical curves ECDSA, the hazard (k) renewed by the signer at each signature is replaced by quantity h (m ~ x), where x is the key signer's secret.
In the case of a cryptographic system comprising a Fiat-Shamir type public key signature system or Guillou-Quisquater, the hazard renewed by the signer during l0 each signature is replaced by the quantity h (m ~ B), B being the signer's secret key and m the message to sign.
In the case of a cryptographic system comprising a El Gamal type public key encryption system, the hazard (k) renewed by the encryptor each time a message is sent encrypted is replaced by the quantity h (m).
In the case of a cryptographic system comprising a McEliece type public key encryption system random error vector e, renewed by the encryptor at each cipher is derived from the quantity h (m), where m is the message to encrypt.
In the case of a cryptographic system comprising a random ~ c padding system involved in a system of public key encryption, the encryptor has a key unknown to the decryptor and where the messages 'padding' is carried out according to the following steps.
at. Generate as many ki = h (m ~ a ~ i) as necessary so that the length of the concatenated ki is at least equal to 1/6 of the module size n (in the case of RSA encryption for example) or else generate k = h (m ~ a) and expand it;
b. Compose mr such that m = = size (m) ~ m ~ {ki ~;
vs. Encrypt mr in place of m.

In the case of a cryptographic system comprising a system for generating a blindness factor within the framework a blank signature generation or an operation of.
random makeup the hazard (k) renewed by the sender during of each blindness or make-up operation is replaced by the quantity h (m ~ a) In the case of a cryptographic system comprising a Diffie-Hellman type key exchange protocol according to a device wishing to send a message uses it instead lo of a random secret, the quantity h (m ~ a) where a is a given secret.
In this same case of this cryptographic system said protocol includes at least the following steps.
at. A first device, wishing to send the message m, calculate bl = ghcm'a) mod p;
b. A second device, receiver, generates a hazard a and calculate bz = ga mod p;
vs. The two devices exchange bl and b2, and calculate key - ga h (m I a) mOd pi 2o d. The first device numbers c - f (m, key) where f is a symmetric encryption mechanism;
the first device sends c to the second device which sends it decrypts and finds mr.
Preferably, the communicating devices are smart cards, PCMCIA cards, badges, contactless cards or any other portable device.
Preferably, the communication between said apparatuses implementing the invention is realized by the through exchange of electronic signals, radio waves or infrared signals.

WO 98! 51038 PCT / FR98 / 00901 In the following, the invention is presented in a more detailed manner.
detailed by using the notations used in the description of the families of applications.
As said before, the idea of generating a hazard by a hash operation h. For the first two families application of the invention, h will take as a parameter a secret data, namely the signer's secret key, and a public data, the message to sign.
For the third family, h will take as a parameter l0 only the message to sign.
Finally, ~ for the other families, h will take as a parameter public data and secret data (noted a in the after ) .
More precisely .
- for the first family concerning said schemes of signature of type E1-Gamal, the hazard k is generated in the way next . k - h (m'x) where m is the hash of the message M in front be signed and x, the signer's secret key. The rest of the generation of the signature (r, s) is carried out identically to the original process. Likewise the verification of the signature generated remains unchanged.
- for the second family concerning said diagrams of signature derived from zero disclosure protocols, k is generated as follows. k - h (m ~ B) with m the hash of message M to be signed and B, the signer's secret key.
The rest of the generation of the signature (d, D) is carried out from identical to the original process. Likewise the verification of the signature generated remains unchanged.
- for the third family concerning said schemes of encryption requiring a hazard, two cases are to be considered:
O Case of El Gamal encryption.

_ 19 - the hazard k is generated as follows. k = h (m) with m the message to be encrypted. Then we do El Gamal's algorithm as described above. The decryption also remains unchanged.
O Case of Mc Eliece encryption.
- instead of deriving the error vector e from a ala, it is generated from h (m), where m is the message to encrypt. It is recalled that e must be of Hamming weight exactly t. One way to derive a vector of size n (size of the code considered) and of weight t from h (m) is the next one .
- suppose that we ordered the vectors of size n and of weight t. We can then choose the vector from this list which is in position h (m) (or a position derived from h (m), because IS this number can exceed binomial. (T, n), following t, n, and the hash function used) as a vector e.
We then perform the McEliece algorithm, hme as described above. Decryption also remains unchanged.
In addition, this method of generating e solves the problem of encrypting the same message twice. In indeed, in the case of generic McEliece, it is unwise to encrypt the same message twice (so with two vectors error), because we can guess part of the support for error vectors, and consequently find more easily the clear message.
With our generation of e, the same message will always have the same figure.
The invention applies as follows to the fourth family, which concerns cryptographic schemes requiring a random padding.

- as specified, a recommendable security measure is to “pad” messages with a random sequence. But the again, if the sequence varies for several ciphers of one same message, an attack is still possible revealing the clear message.
Use of the deterministic generation method of a hazard makes it possible to effectively curb this type of phenomenon.
Indeed, by adding to the message m as many times as necessary (the padding must be at least 1/6 of the l0 size of n, i.e. between 86 and 171 bits for sizes of conventional modules ranging from 512 to 1024 bits) the values ki =
h (m, a, i), a being a secret of at least 128 bits, the set of attacks becomes impossible because no more relationship exists between messages and moreover, the same encrypted message many times will always be with the same padding. The encryption of a message m is then carried out in the manner next by the sender.
O Generate as many ki = h (m ~ a ~ i) as necessary so that the length of the concatenated ki is at least equal to 1/6 of the size of n; we may also prefer to use a single k =
h (m ~ a) then expand k before concatenating it to the message;
O Compose mr such that mr = size (m) ~ m ~ tki ~;
Calculate the cryptogram c - mre mod n so that the receiver decrypts c by calculating mr = cd mod n. The receiver then simply extract m, knowing its size and therefore significant bits of mr.
For the fifth family concerning the factors of blindness and blank signatures, three cases are â
consider .
0 Signature case in white.

- k is generated as follows. k. = h (m ~ a) with m le message to be signed and has a: secret data. The rest of the blank signature is generated in a way identical to the original procedure. Likewise the extraction of the signature of m remains unchanged;
D Case of random makeup.
- we generate k in the following way. k - h (atb ~ a) with a and b the operands to be multiplied and has a secret datum. The rest of the random makeup operation is performed from identical to the original process. Similarly the reduction . modular c 'by the receiver remains unchanged;
~ Case of protection mechanisms against attacks based on measuring the time of a process.
- in the case of the RSA signature for example, we generate the random multiple k of (p-1) (q-1) as follows. k - h (m ~ a) with m the message to sign, and has a secret data.
The rest of the exhibitor's make-up operation (d '= d + k (p 1) (q-1)) is carried out in the same way as the original process.
The invention applies from the following to the sixth family, which relates to said key exchange schemes based on the Diffie-Hellman method.
In the Diffie-Hellman type key exchange system the device, also called a device, which wishes to send a message m, uses, instead of a hazard the quantity h (m ~ a) where a is fixed secret data. One can obviously so natural extend this method to all participants to the protocol. The latter includes, at least, the steps following.
a first device, wishing to send the message m, cal cule X = gh ~ '°' a ~ mod p;

~ a second device, receiver, generates a hazard y and calculate Y = gY mod p;
~ the two devices exchange X and Y, and calculate key - gY.nc ~ I 6> mod p;
~ the first device numbers c - f (m, key) where f is a symmetric encryption mechanism;
~ the first device sends c to the second device which decrypts it and finds mr.
The invention will be easier to understand using the Figures 1 to 4.
Figure 1 depicts the flow diagram of a signature or decryption implementing the system proposed by the present invention.
Figure 2 depicts the flow diagram of a verification or encryption implementing the system proposed by the present invention.
FIG. 3 represents the data exchanged by the signature device and verification device.
FIG. 4 represents the data exchanged by the encryption device and the decryption device.
According to the proposed invention, each signature / decryption (typically a smart card) is consists of a processing unit (CPU), an interface communication, a random access memory (RAM) and / or a memory writable (ROM) and / or writable memory (usually rewritable) (EPROM or EEPROM).
The device's CPU and / or ROM
signature / decryption contain programs or computing resources corresponding to the steps of the algorithm 3o signature / decryption (rules of calculation and use the hash, multiplication, squaring function, z3 addition, modular inverse and modular reduction). Some of these operations can be grouped together. for example, the modular reduction may be directly integrated into the multiplication.
The RAM contains the message M to which the hash function or calculation rules for generation of signatures or the calculation rules for the generation of cryptograms. The E (E) PROM contains at least the parameters m, x and k generated and used as specified in the description which lo follows.
The CPU controls, via the address and data buses, communication interface, read operations and memory writing.
Every signature device is protected from the world outside by physical protections. These protections should be sufficient to prevent any entity not authorized to obtain the secret key. The most used of our. days in the matter are the integration of the chip in a security module and the chip equipment devices capable of detecting temperature variations, of light as well as clock voltages and frequencies abnormal. Special design techniques, such as that scrambling memory access, are also used.
According to the proposed invention, the verification device is consists of at least one processing unit (CPU) and memory resources.
The CPU controls, via the address and data buses, the communication interface, the read operations and memory writing.

The authority's CPU and / or ROM contain compute programs or resources to implement the signature or encryption protocol (calculation rules.
and hash, multiplication, exponentiation and modular reduction). Some of these operations can be grouped (for example, modular reduction maybe directly integrated into the multiplication).

Claims (12)

Claims 1. Cryptographic system, normally requiring the drawing of a random number k, the random number being an integer, characterized in that that it is implemented by replacing said hazard k by the quantity h(m~secret) where h is a hash function, m is the message intervening in said system and "secret" is a secret unknown to the world outside the cryptographic systems. 2. Cryptographic system according to claim 1 characterized in that it comprises at least.

- a public key signature system;
- a public key encryption system;
- a random “padding” system;
- a factor generation system blindness;
- a key exchange protocol. 3. Cryptographic system comprising a system of DSA, Schnorr, E1-Gamal, GOST type public key signature 34.10 or the IEEE Elliptic Curve ECDSA standard, depending on the claim 2, characterized in that the hazard (k) renewed by the signer during each signature is replaced by the quantity h(m~x), where x is the signer's secret key. 4. Cryptographic system comprising a system of Fiat-Shamir type public key signature or Guillou-Quisquater, according to claim 2, characterized in that the hazard renewed by the signer during each signature is replaced by the quantity h(m~B), B being the secret key of the signer and m the message to be signed. 5. Cryptographic system comprising a system of public key encryption type E1 Gamal, according to the claim 2, characterized in that the hazard (k) renewed by the encryptor each time an encrypted message is sent is replaced by the quantity h(m). 6. Cryptographic system comprising a system of McEliece type public key encryption according to the claim 2, characterized in that the error vector random e, renewed by the encryptor at each encryption is derived from the quantity h(m), where m is the message to encrypt. 7 Cryptographic system comprising a system of random “padding” intervening in a system of public key encryption, according to claim 2, characterized in that the encryptor has an unknown key a of the decryptor and in that the padding of the messages is carried out according to the following steps:
has. Generate as many ki=h(m¦.sigma.¦i) as necessary so that the length of the concatenated ki is at least equal to 1/6 of the modulus size n (in the case of RSA encryption by example), or generate k=h(m¦.sigma.) and expand it;
b. Compose mr such that mr = size(m)¦m¦{ki};
vs. Encrypt mr instead of m. 8. Cryptographic system comprising a system of generation of a blinding factor within the framework of a signature generation in white or a make-up operation random according to claim 2, characterized in that the hazard (k) renewed by the shipper during each operation of blinding or make-up is replaced by the quantity h(m¦.sigma.) 9. Cryptographic system comprising a protocol Diffie-Hellman type key exchange according to claim 2, characterized in that a device wishing to send a message m uses, instead of a random secret, the quantity h(m a) where a is a secret data. 10. Cryptographic system according to claim 9, characterized in that said protocol comprises at least the following steps.

has. A first device, wishing to send the message m, calculate b1 = gh(m~.sigma.) mod p;
b. A second device, receiver, generates a random a and calculate b2 = ga mod p;
vs. The two devices exchange b1 and b2, and calculate key - ga h(m~.sigma.) mod p d. The first device encrypts c = f (m, key) where f is a symmetric encryption mechanism;
- the first device sends c to the second device which decipher and find mr. 11. Cryptographic system according to any of the claims 1 to 10, characterized in that the devices are communicating devices are smart cards, cards PCMCIA, badges, contactless cards or any other portable device. 12. Cryptographic system according to any of the claims 1 to 11, characterized in that the communication between said devices implementing it is carried out by through the exchange of electronic signals, radio waves or infrared signals.