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

Description

1 A PSEUDO-RANDOM GENERATOR BASED ON A HASHING FUNCTION FOR CRYPTOGRAPHIC SYSTEMS REQUIRING THE DRAWING OF RANDOM NUMBERS 5 The present invention describes a system making it possible to generate digital signatures or cryptograms requiring the drawing of random numbers (typically DSA, El-Gamal, Fiat-Shamir and Guillou Quisquater for signatures, El-Gamal and McEliece for 10 encryption), by signature or encryption devices (typically microprocessors) lacking hardware or software resources allowing the drawing of random numbers. It also provides an answer, or defence, against 15 certain threats (typically the encryption of short messages and the recent attacks published by Coppersmith et al. at Eurocrypt '96 in the articles "Low Exponent with Related Message" and "Finding a small root of a univariate modular equation") by the 20 low-cost, i.e. inexpensive, generation of a random 2 sequence making it possible to add to the information to be processed. It also allows the generation of obscuring factors, used within the context of blank signature or 5 random disguising mechanisms. Finally it can be used in the Diffie-Hellman type key exchange protocols. Despite a widespread distribution and a good acceptance of the smart card concept on the part of the 10 public, the majority of practical applications appeared only a few years ago, mainly owing to the limitations in computational power of the cards. Advances as regards non-volatile storage capacity for information, security and circuit technology (for example the 15 EEPROM) are promoting the rapid emergence of new generations of cards and of more and more ambitious applications such as the new American digital signature (DSA) standard. A great limitation of smart cards as a medium for 20 implementing public-key algorithms is the necessity (frequently encountered) of having a device generating random numbers on board the card. This is because perfecting such a device, also referred to as a generator, proves complex and often unstable 25 (sensitivity to phenomena external to the card such as ambient temperature or the voltage applied to the card) . Where such cryptographic systems are implemented on a computer, other phenomena, due to the very nature of software random generators, interfere 30 with the quality of the random numbers. Typically, one 3 very popular method of generating random numbers consists of measuring the elapsed time between two presses on the keypad by the user. Recent cases of fraud show that this kind of generator can be biased by 5 simulating the keypad by means of a fraudulent device in which the elapsed time between the various keystrokes is known by the attacker. The present invention proposes a substitute solution allowing the implementation of cryptographic 10 systems requiring the drawing of a good quality random number on software or hardware platforms: 1. not possessing any random number generation means, 2. or generating poor quality random numbers, 15 3. or when the system designer suspects that external elements could compromise the quality of the random numbers by modifying the external and internal operating conditions. The present invention applies to various families 20 of cryptographic algorithms. For a better understanding of the invention and before going over the content of the claims in the description, it is useful to recall the main characteristics of the said families of cryptographic algorithms to which the 25 invention applies, these being six in number. The first application family concerns the El Gamal type signature schemes. The El-Gamal signature algorithm, described in the article entitled "A public-key cryptosystem and a 30 signature scheme based on discrete logarithms" and 4 published in the journal IEEE Transactions on Information Theory, Vol. IT-31, -no. 4, 1985, pp. 469 472, has given rise to a number of known signature algorithms: Schnorr, patented in the United States 5 under the reference 4.995.082, or GOST 34-10 - Russian federal digital signature standard; DSA - American digital signature standard. Once illustrated within the context of the DSA, the application of the present invention to other 10 algorithms of the same family can easily be implemented by persons skilled in the art. Subsequently, it is referred to as the DSA algorithm. The Digital Signature Standard (the DSA, American 15 patent no. 5.231.668 entitled "Digital Signature Algorithm") was proposed by the US National Institute of Standards and Technology in order to provide a suitable basis for applications requiring a digital signature instead of conventional signatures. A DSA 20 signature is a pair of large numbers represented in a computer by strings of binary digits. The digital signature is calculated by means of a series of calculation rules (the DSA) and a set of parameters in a manner making it possible to certify both the 25 identity of the signatory and the integrity of the data. The DSA makes it possible to generate and verify signatures. The signature generation method makes use of a private key (in order to produce a digital signature) . 30 The verification method uses a public key which 5 corresponds to the secret key without however being identical thereto. Each user possesses a pair of keys (public, secret) . It is assumed that the public keys are known to all while the secret keys are never 5 disclosed. Any person has the ability to verify the signature of a user using his public key but signatures cannot be generated other than by using the secret key of the user. The parameters of the DSA are: 10 1. A prime modulus p such that 2 L-1 < < 2 L for 512 L 1024 and L = 64a for any a. 2. A prime modulus q such that 2 59 < q < 210 and p-1 is a multiple of q. 3. A number g, of order q modulo p such that g = 15 h(P-1)/4 mod p, where h is any integer verifying 1 < h < p-1. 4. A number x, generated randomly or pseudo randomly. 5. A number y defined by the relationship: y = g' 20 mod p. 6. A number k generated randomly or pseudo randomly such that 0 < k < q. The integers p, q and g are parameters of the system able to be published and/or shared by a group of 25 users. The secret and public keys of a signatory are respectively x and y. The parameters x and k are used for generating the signature and must be kept secret. The parameter k must be regenerated for each signature.

6 In order to sign a message m (hashed value of an initial file M), the signer ca-lculates the signature (r, s) by: r = gk mod p mod q and s = (m + x r)/k mod 5 q, where the division by k is understood to be modulo q (i.e. 1/k is the number k' such that k k' = 1 mod q). For example, if q = 5 and k = 3 then 1/k = 2 10 since 3 x 2 = 6 = 1 mod 5. After having tested that r and s # 0, as explained in the description of the DSA, the signature (r, s) is sent to the verifier which calculates: 1. w = 1/s mod q 15 2. ui = m w mod q 3. u 2 = r w mod q 4. v= gu yu 2 mod p mod q 5. and compares whether v and r are equal in order to accept or reject the signature. 20 The second family also concerns signature schemes; these are schemes derived from zero-disclosure protocols. A second family of signature algorithms to which the invention applies are those derived from zero 25 disclosure protocols (typically Fiat-Shamir or Guillou Quisquater patented in the United States respectively under the references 4.748.668 and 5.140.634). Also, only one of these protocols will be described. Once applied to the Guillou and Quisquater algorithm, the 30 extension of the invention to other algorithms in this 7 family proves self-evident for persons skilled in the art. The parameters of the Guillou-Quisquater algorithm are: 5 1. Two secret prime numbers p and q equal in size to at least 256 bits; these prime numbers are generated in a particular manner, the detail of which is not essential to the understanding of the present invention but can however be found in the work "Applied 10 Cryptography, Algorithms, Protocols and Source Codes" by Bruce Schneier (Translation by Marc Vauclair), Thomson Publishing; 2. A public modulus n = p q and a string ID representing the identity of the signer; 15 3. A public exponent v and a secret key B such that By ID = 1 mod n; the parameter B must remain secret; 4. In order to sign the message m, the sender draws a random number k, calculates the initial marker 20 T = k' mod n and generates the signature: d = h(T, m) and D = k Bh(T, m) mod n; 5. The verifier makes sure of the authenticity of the signature by verifying that: d = h(T', m) with T' = Dv Idd. 25 The third application family concerns the public key encryption schemes requiring a random number. The first encryption algorithm requiring a random number described subsequently is that of El Gamal. The parameters of this algorithm are: 30 1. A prime modulus p (of at least 512 bits); 8 2. A number g, of order p-1 modulo p (i.e. such that, for any integer number u, 0 < u < p-1, gu 1 mod P; 3. A number x, 1 x p-2, generated randomly or 5 pseudo-randomly; 4. A number y defined by the relationship: y = g' mod p; 5. A number k generated randomly or pseudo randomly such that 0 < k < q. 10 The integers p and g are system parameters able to be published, and/or shared by a group of users. The public encryption key is the number y, and the secret decryption key is the number x. The parameter k is used for generating the 15 cryptogram, and must not be divulged. Furthermore, it must be regenerated at each encryption. The encryption of a message m, 0 m p-1, is the integer pair (r, s), where: r = gk mod p and s = m yk mod q. 20 In order to recover the message m, the receiver of the cryptograms (who possesses x) calculates: s/rX mod p, which is precisely m. A second encryption algorithm' requiring the 25 generation of a random number is the McEliece scheme, based on a code theory problem, more precisely using a particular class of codes known by the name of Goppa codes. The general idea is to disguise a Goppa code as any linear code; this is because there is an efficient 30 algorithm for decoding a Goppa code but on the other 9 hand decoding a general linear code is a difficult problem. The receiver, knowing- the information which made it possible to disguise the code, can therefore decrypt the message by decoding the Goppa code 5 obtained. The parameters of the McEliece algorithm (all the formulae which follow are understood to be in GF(2)) are: 1. Numbers n, k and t, parameters of the system; 10 in the original article describing his encryption scheme, McEliece proposes n = 1024, t = 50 and k = 524; 2. 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 15 corresponding decoding algorithm; * A random invertable matrix S of dimension k x k; e A random permutation matrix P of size n; 3. A corresponding public key composed of: * The generator matrix T - SGP of a code equivalent to 20 G; * The correction rate t; 4. The encryption by the McEliece algorithm of a message m of k bits is performed by calculating: c = mT + e 25 where e is a randomly chosen error vector of Hamming weight equal to t. The decryption of c is performed by calculating: cP m TP 1 + eP~ 1 = mSG + eP 1 . Since e is of weight t, eP~ is also of weight t. 30 The vector cP 1 is therefore correctable by the code G.

10 By decoding, the decrypter obtains mS, and then m since it knows S and S is invertable. The fourth family concerns the cryptographic schemes requiring random padding. 5 It is not uncommon that the data item to be encrypted must first be padded, i.e. added to in order to obtain a data item 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. 10 Shamir and L. Adleman, and then patented under the title "Cryptographic 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 or hexadecimal 15 digits. The cryptogram is calculated by means of a software calculation resource (a program) and/or a hardware calculation resource (an electronic circuit) using a series of calculation rules (the encryption algorithm) which have to be applied at the time of 20 processing a set of parameters accessible to all in order to hide the content of the processed data. In an analogous manner, the cryptogram is decrypted by means of a software or hardware calculation resource using a series of calculation rules (the decryption algorithm) 25 applied (by the receiver of the cryptogram) to a set of secret parameters and the cryptogram. The encryption method makes use of a public key in order to produce the cryptogram. The decryption method uses a private key which corresponds to the 30 secret key without however being identical thereto.

11 Each user possesses a pair of keys (public, secret) and it is assumed that the public -keys are known to all while the secret keys are never disclosed. Any person has the ability to encrypt a message for a user using 5 the public key of the latter but cryptograms cannot be decrypted other than by using the secret key of the user. The parameters of the RSA algorithm are: 1. Two secret prime numbers p and q equal in size 10 to at least 256 bits. These prime numbers are generated in a particular manner, the detail of which is not essential to the understanding of the present invention but can however be found in the work "Applied Cryptography, Algorithms, Protocols and Source Codes", 15 by Bruce Schneier (Translation by Marc Vauclair), Thomson Publishing; 2. A public modulus n = p q; 3. A pair of exponents denoted (e, d) such that: e d = 1 mod (p-1) (q-1). 20 The exponent e, referred to as the "encryption exponent", is accessible to all, whereas the "decryption exponent" d must remain secret. In order to encrypt the message m, the sender calculates the cryptogram c = me mod n and the receiver 25 decrypts c by calculating m = cd mod n. The security of the algorithm, based on the problem of factorization, allows, for a choice of parameters made as well as possible, the provision, in the general case of the encryption of messages of the 30 size of the modulus and not possessing any particular 12 relationships between them, of confidentiality between the sender and the receiver of the encrypted information. On the other hand, recent attacks presented by 5 Coppersmith et al. at Eurocrypt '96 (notably in "Low Exponent with Related Message" and "Finding a small 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 10 polynomial relationships between messages encrypted with one and the same small-sized exponent, which can quite occur within the context of an application where the encrypting device in general uses, for encrypting, a public exponent e = 3 for performance reasons, allows 15 effective attacks revealing the clear text. One possible answer is to pad the message with a random sequence (but taking certain precautions) or to break up any relationship between the messages, which, depending on the application, is not always possible. 20 The following modification will then be introduced in step 4: In order to encrypt the message, the sender generates a sequence Sr having a certain degree of randomness and calculates the cryptogram c = (mlsr)e mod 25 n, the sign I indicating concatenation; the receiver decrypts c by calculating cd mod n and recovers m by removing the padding. The exact methods of padding the messages can vary depending on the standards, the application 30 requirements or the required level as regards security.

13 The fifth family concerns obscuring factors and blank signatures. A basic functionality, referred to as primitive by persons skilled in the art, used in many 5 cryptographic protocols and schemes is the mechanism of blank signing of a given message. This functionality disclosed and patented by Chaum (US patent no. 4.759.063 and European patent no. 0139313) makes it possible to have a message signed without the signer 10 being able to read the message. It requires the generation of an obscuring factor, making it possible to conceal the message, known only to the requester of the signature. The mechanism used applies equally well to signature schemes of the El Gamal type as to those 15 of the RSA. Once illustrated within the context of the RSA, the application of the present invention to other signature algorithms proves self-evident for persons skilled in the art. Only the blank signature mechanism 20 based on the RSA will be described here. Taking again the notation used within the context of the description of the fourth application family of the invention, the RSA signature is defined thus: s = md mod n; 25 the verification naturally being done: se mod n = (md)e mod n = m. The steps of obtaining a blank signature by the sender E of a message m are: 14 1. E generates a random number k, calculates the obscuring factor ke mod n and sends m' = mk" mod n to the receiver or (signer); 2. The receiver calculates s' = m'd mod n which is 5 the signature of m' and sends s' to E; 3. E calculates s'/k = (mke) d/k = mdked/k = md mod n, and therefore obtains the signature s of m. This technique of multiplying by an obscuring factor is also used within the context of random 10 disguising (European patent application EP 91402958.2). The method of random disguising is used for example where a device A wishes to subcontract operations to a device B while not wishing to fully reveal the operands to it. Let for example a modular 15 reduction operation be taken: A can camouflage the number to be reduced modulo n by multiplying it by a random multiple of the modulus. Thus, if A wishes to obtain c = ab mod n, it can generate a random number k, calculate c' = ab + kn (kn masks the product ab) , and 20 send c' to the device B for reduction. The device B calculates c' mod n = ab + kn mod n = C. This technique finally makes it possible to propose an answer to the Kocher attacks described at 25 Crypto '96 ("Timing attacks on Implementation of Diffie-Hellman, RSA, DSS and Other Systems", proceedings of the conference published at Springer Verlag under the reference LNCS 1109) which are based on the measurement of the time required by operations 15 manipulating secret magnitudes in order to guess the values thereof. This is because an effective answer is the multiplication, by an obscuring factor, of the secret 5 magnitudes manipulated in order to decorrelate the calculation time and the magnitude. In the case of the RSA signature for example (persons skilled in the art will know how to extend this result to all algorithms concerned by the attack, notably all those entailing 10 the calculation of a modular exponential with a secret exponent), taking again the notation used within the context of the description of the fourth application family of the invention, it suffices that: 1. the signer generates a random number k and 15 calculates: d' = d + k(p-1) (q-1) 2. he next generates the signature of m by calculating: md' - md+k(p- 1 ) (q-1) md(m(p-1) (q-1) k = md mod n. 20 The sixth family concerns the key exchange schemes based on the Diffie-Hellman method. The Diffie-Hellman key exchange algorithm is the first public-key algorithm described in "New Directions in Cryptography" published in IEEE Transactions on 25 Information Theory, Vol. IT-22, no. 6 and patented in the United States under the reference 4.200.770. The method uses two participants (or appliances) wishing to agree on secret information through a non-secure channel.

16 The parameters of the Diffie-Hellman protocol are as follows: 1. Two public parameters on which the sending appliance (A) and the appliance (B) agree: a prime 5 number p of at least 512 bits and an integer g, a modulo p primitive root. These two parameters can possibly be common to a group of users; The protocol progresses as follows: In order to share secret information, the two 10 appliances carry out the following operations: " the appliance A generates a random number x and calculates the magnitude X = g' mod p; " the appliance B generates a random number y and calculates the magnitude Y = gy mod p; 15 e the two appliances exchange with one another the quantities X and Y; * the appliance A calculates key = Y' mod p; e the appliance B calculates key' = X mod p. The two appliances thus share at the end of the 20 protocol the knowledge of the quantity key' = key = gxY mod p. The two appliances can subsequently use the secret quantity "key" in order to exchange with one another messages through a secure channel by means of a 25 symmetric encryption algorithm taking as parameters the quantity "key" and the message to be encrypted. Following the description of the different application families of the invention, it is desirable to specify the main advantages of the invention.

17 The economic constraints related to the smart card market entail continuous research with a view to improving production costs. This effort often proceeds through the use of the simplest possible products. 5 This established fact results in a constantly growing importance for solutions making it possible to implement public-key algorithms on inexpensive 8-bit microcontrollers, with an 80C51 or 68HC05 for example at their heart. 10 The main advantage of the inventive method compared with the preceding proposals as regards digital signatures or encryption lies in the ability to calculate signatures or perform encryption operations without, for all that, requiring a random number 15 generator on board the signing or encrypting circuit. For the clarity of the description, it is necessary to specify that the generation of the keys and parameters of the various systems presented remains identical. The usual works and patents will therefore 20 be referred to in order to generate, as well as possible, the various elements necessary for the signature, authentication and encryption algorithms presented in the invention. A practical reference work can be "Applied Cryptography, Algorithms, Protocols and 25 Source Codes, by Bruce Schneier (Translation by Marc Vauclair), Thomson Publishing. The present invention concerns a cryptographic system, normally requiring the drawing of a random number k, the random number being an integer; the 30 system is characterised in that it is implemented by 18 replacing the said random number k by the quantity h(mlsecret) where h is a hashing function, m is the message occurring in the said system and "secret" is a secret item unknown to the world external to the 5 cryptographic system. More precisely, the cryptographic system of the invention comprises at least: - a public-key signature system; - a public-key encryption system; 10 - a random padding system; - an obscuring factor generation system; - a key exchange protocol. In the case of a cryptographic system which comprises a public-key signature system of type DSA, 15 Schnorr, El-Gamal, GOST 34.10 or the IEEE ECDSA elliptical curve standard, the random number (k) renewed by the signer at the time of each signature is replaced by the quantity h(mIx), where x is the secret key of the signer. 20 In the case of a cryptographic system comprising a public-key signature system of the Fiat-Shamir or Guillou-Quisquater type, the random number renewed by the signer at the time of each signature is replaced by the quantity h(m B), B being the secret key of the 25 signer and m the message to be signed. In the case of a cryptographic system comprising a public-key encryption system of the El Gamal type, the random number (k) renewed by the encrypter at the time of each sending of an encrypted message is 30 replaced by the quantity h(m).

19 In the case of a cryptographic system comprising a public-key encryption system -of the McEliece type, the random error vector e renewed by the encrypter at each encryption is derived from the quantity h(m), 5 where m is the message to be encrypted. In the case of a cryptographic system comprising a system of random padding occurring in a public-key encryption system, the encrypter possesses a key a unknown to the decrypter and where the padding of the 10 messages is carried out according to the following steps: a. Generate as many ki = h(mlali) as necessary so that the length of the concatenated kis is at least equal to 1/6 of the size of the modulus n (in the case 15 of RSA encryption for example), or generate k = h(mIa) and expand it; b. Form mr such that mr = size(m) |ml (ki); c. Encrypt mr instead of m. In the case of a cryptographic system comprising 20 a system for generating an obscuring factor within the context of a blank signature generation or a random disguising operation, the random number (k) renewed by the sender at the time of each obscuring or disguising operation is replaced by the quantity h(mla). 25 In the case of a cryptographic system comprising a Diffie-Hellman type key exchange protocol, an appliance wishing to send a message m uses, instead of a random secret item, the quantity h(mla) where a is a secret data item.

20 In this same case of this cryptographic system, the said protocol has at least the following steps: a. A first appliance, wishing to send the message m, calculates bi = gh(mia) mod p; 5 b. A second appliance, the receiver, generates a random number a and calculates b 2 = ga mod p; c. The two appliances exchange bi and b 2 , and calculate key = ga h(mla) mod p; d. The first appliance encrypts c = f (m, key) 10 where f is a symmetric encryption mechanism; the first appliance sends c to the second appliance which decrypts it and recovers m. Preferentially, the communicating appliances are smart cards, PCMCIA cards, badges, contactless cards or 15 any other portable appliance. Preferentially, the communication between the said appliances implementing the invention is carried out by means of exchanges of electronic signals, radio waves or infrared signals. 20 Subsequently, the invention is presented in a more detailed manner, taking again the notations used in the description of the application families. As stated previously, the idea of generating a random number by a hashing operation h. For the first 25 two application families of the invention, h will take as parameters a secret data item, namely the secret key of the signer, and a public data item, the message to be signed. For the third family, h will take as a parameter 30 only the message to be signed.

21 Finally, for the other families, h will take as parameters a public data item and a secret data item (denoted a subsequently). More precisely: 5 - for the first family concerning the said El Gamal type signature schemes, the random number k is generated as follows: k = h(mlx) where m is the hash of the message M which has to be signed and x, the secret key of the signatory. The remainder of the generation 10 of the signature (r, s) is performed in a manner identical to the original method. Similarly the verification of the generated signature remains unchanged. - for the second family concerning the said 15 signature schemes derived from zero-disclosure protocols, k is generated as follows: k = h(m|B) with m the hash of the message M which has to be signed and B, the secret key of the signer. The remainder of the generation of the signature (d, D) is performed in a 20 manner identical to the original method. Similarly the verification of the generated signature remains unchanged. - for the third family ~concerning the said encryption schemes requiring a random number, two cases 25 are to be considered: 1. The El Gamal encryption case: - the random number k is generated as follows: k = h(m) with m the message which has to be encrypted. Next the El Gamal algorithm is performed in the manner 22 described previously. The decryption also remains unchanged. 2. The McEliece encryption case: - instead of deriving the error vector e from a 5 random number, it is generated from h (m) , where m is the message to be encrypted. It should be noted that e must be of exactly Hamming weight t. One way of deriving a vector of size n (the size of the code under consideration) and of weight t from h(m) is as follows: 10 - let it be assumed that the vectors of size n and weight t have been ordered. The vector in this list which is in position h(m) (or a position derived from h (m) , since this number can exceed binomial (t, n), depending on t, n, and the hashing function used) 15 can then be chosen as the vector e. The McEliece algorithm is next performed in the manner described previously. The decryption also remains unchanged. Moreover, this method of generating e makes it 20 possible to solve the problem of encrypting one and the same message twice. In fact, in the generic McEliece case, it is unwise to encrypt one and the same message twice (and therefore with two different error vectors), since it is possible to guess part of the error vector 25 medium, and subsequently recover the clear message more easily. With the generation of e of the present invention, one and the same message will always have the same encryption.

23 The invention applies in the following manner to the fourth family, which concerns the cryptographic schemes requiring random padding: - as specified, an advisable security measure is 5 to pad the messages with a random sequence. But there again, if the sequence varies for a number of encryptions of one and the same message, an attack is again possible revealing the clear message. The use of the deterministic method of generating 10 a random number makes it possible to effectively stop this type of phenomenon. This is because, by adding to the message m as many times as necessary (the length of the padding must be at least 1/6 of the size of n, that is between 86 and 171 bits for conventional modulus 15 sizes going from 512 to 1024 bits) the values ki = h(m, a, i) , a being a secret number of at least 128 bits, all the attacks become impossible since there is no longer any relationship between the messages and moreover, one and the same message encrypted a number 20 of times will always be so with the same padding. The encryption of a message m is then performed as follows by the sender: 1. Generate as many ki = h(mlali) as necessary so that the length of the concatenated kis is at least 25 equal to 1/6 of the size of n; it can also be preferred to use a single k = h(m a) , and- then expand k before concatenating it with the message; 2. Form mr such that mr = size(m) m|f{ki); 3. Calculate the cryptogram c = mr* mod n in order 30 that the receiver decrypts c by calculating mr = cd mod 25 In the Diffie-Hellman type key exchange system, the appliance, also referred to as the device, which wishes to send a message m, uses, instead of a random number, the quantity h(mla) where a is a fixed secret 5 data item. Obviously this method can be extended naturally to all the participants in the protocol. The latter has, at least, the following steps: * a first device, wishing to send the message m, calculates X = g (mla) mod p; 10 e a second device, the receiver, generates a random number y and calculates Y = gY mod p; " the two devices exchange X and Y, and calculate key = g y. h(mIa) mod p; " the first device encrypts c = f (m, key) where f is a 15 symmetric encryption mechanism; * the first device sends c to the second device which decrypts it and recovers m. The invention will be easier to understand with the help of Figures 1 to 4. 20 Figure 1 describes the organizational diagram of a signature or decryption appliance implementing the system proposed by the present invention. Figure 2 describes the organizational diagram of a verification or encryption appliance implementing the 25 system proposed by the present invention. Figure 3 depicts the data exchanged by the signature device and the verification device. Figure 4 depicts the data exchanged by the encryption device and the decrypti.on device.

26 According to the proposed invention, each signature/decryption appliance (typically a smart card) is composed of a processing unit (CPU), a communication interface, a random access memory (RAM) and/or a read 5 only memory (ROM) and/or a writable (generally re writable) memory (EPROM or EEPROM). The CPU and/or the ROM of the signature/decryption appliance contain programs or calculation resources corresponding to the steps of the 10 signature/decryption algorithm (rules for calculation and for use of the hashing, multiplication, squaring, addition, modular inverse and modular reduction function). Certain of these operations can be grouped together: for example, the modular reduction can be 15 directly integrated in the multiplication. The RAM contains the message M to which is applied the hashing function or the calculation rules for signature generation or the calculation rules for cryptogram generation. The E(E)PROM contains at least 20 the parameters m, x and k generated and used as specified in the description which follows. The CPU controls, via the address and data buses, the communication interface, and the memory read and write operations. 25 Each signature appliance is protected from the external world by physical protective mechanisms. These protective mechanisms should be sufficient to prevent any unauthorized entity from obtaining the secret key. The techniques most used nowadays in this 30 regard are integration of the chip in a security module 27 and equipping of the chips with devices capable of detecting variations in temperature or light as well as abnormal voltages and clock frequencies. Particular design techniques, such as mixing up of the memory 5 access, are also used. According to the proposed invention, the verification appliance is composed at minimum of a processing unit (CPU) and memory resources. The CPU controls, via the address and data buses, 10 the communication interface, and the memory read and write operations. The CPU and/or the ROM of the authority contain programs or calculation resources making it possible to implement the signature or encryption protocol 15 (calculation rules and hashing, multiplication, exponentiation and modular reduction function). Certain of these operations can be grouped together (for example, the modular reduction can be directly integrated in the multiplication).

Claims (12)

1. A cryptographic system, normally requiring the drawing of a random number k, the random number 5 being an integer, characterised in that it is implemented by replacing the said random number k by the quantity h(mjsecret) where h is a hashing function, m is the message occurring in .the said system and "secret" is a secret item unknown to the world external 10 to the cryptographic system.

2. A cryptographic system according to Claim 1, characterised in that it comprises at least: - a public-key signature system; - a public-key encryption system; 15 - a random padding system; - an obscuring factor generation system; - a key exchange protocol.

3. A cryptographic system comprising a public key signature system of type DSA, Schnorr, El-Gamal, 20 GOST 34.10 or the IEEE ECDSA elliptical curve standard, according to Claim 2, characterised in that the random number (k) renewed by the signer at the time of each signature is replaced by the quantity h(mfx), where x is the secret key of the signer. 25

4. A cryptographic system comprising a public key signature system of the Fiat-Shamir or Guillou Quisquater type, according to Claim 2, characterised in that the random number renewed by the signer at the time of each signature is replaced by the quantity 29 h(m|B), B being the secret key of the signer and m the message to be signed.

5. A cryptographic system comprising a public key encryption system of the El Gamal type, according 5 to Claim 2, characterised in that the random number (k) renewed by the encrypter at the time of each sending of an encrypted message is replaced by the quantity h(m).

6. A cryptographic system comprising a public key encryption system of the McEliece type, according 10 to Claim 2, characterised in that the random error vector e renewed by the encrypter at each encryption is derived from the quantity h(m), where m is the message to be encrypted.

7. A cryptographic system comprising a system of 15 random padding occurring in a public-key encryption system, according to Claim 2, characterised in that the encrypter possesses a key a unknown to the decrypter, and in that the padding of the messages is carried out according to the following steps: 20 a. Generate as many ki = h(miali) as necessary so that the length of the concatenated kis is at least equal to 1/6 of the size of the modulus n (in the case of RSA encryption for example) , or generate k = h (mj a) and expand it; 25 b. Form mr such that mr = size(m) Im l (ki); c. Encrypt mr instead of m.

8. A cryptographic system comprising a system for generating an obscuring factor within the context of a blank signature generation or a random disguising 30 operation, according to Claim 2, characterised in that 30 the random number (k) renewed by the sender at the time of each obscuring or disguising operation is replaced by the quantity h(mla).

9. A cryptographic system comprising a Diffie 5 Hellman type key exchange protocol according to Claim 2, characterised in that an appliance wishing to send a message m uses, instead of a random secret item, the quantity h(mla) where a is a secret data item.

10. A cryptographic system according to Claim 9, 10 characterised in that the said protocol has at least the following steps: a. A first appliance, wishing to send the message m, calculates b 1 = gh(ma) mod p; b. A second appliance, the receiver, generates a 15 random number a and calculates b 2 = ga mod p; c. The two appliances exchange bi and b 2 , and calculate key = ga h(mla) mod p; d. The first appliance encrypts c = f(m, key) where f is a symmetric encryption mechanism; 20 - the first appliance sends c to the second appliance which decrypts it and recovers m.

11. A cryptographic system according to any one of Claims 1 to 10, characterised in that the appliances are communicating appliances are smart cards, PCMCIA 25 cards, badges, contactless cards or any other portable appliance.

12. A cryptographic system according to any one of Claims 1 to 11, characterised in that the communication between the said appliances implementing 31 it is carried out by means of exchanges of electronic signals, radio waves or infrared-signals.