System and method for communicating encrypted messages using RSA with modular reduction to provide fast decryption

Description:

The present invention relates to a system for communicating encrypted messages according to an RSA-type method involving key numbers d and e and a modulus number N such that N is the product of two factors p and q which are prime numbers N = pq and that ed = l_{modf (N}) where φ (Ν) is the indicator function of Euler, a system comprising on the one hand at least one encryption device formed:

- splitting means for splitting the message to be encrypted into at least one part of the message to be encrypted,

- exponentiation means for performing, on each part of the message to be encrypted, a modular exponentiation operation of modulus N and with an exponent equal to a first of said key numbers, with a view to providing an encrypted message part and of on the other hand at least one decryption device.

The invention also relates to a method implemented in the system, a user device, microcircuit card type comprising on the same medium an encryption device and a decryption device and a so-called trust server center for processing information between the different user devices.

A method of this kind is described in the article entitled Fast decipherement algorithm for a public-Key Cryptosystem with MM as authors. JJ Quisquater and C. Couvreur, published in the ELECTRONICS LETTERS review of OCTOBER 14, 1982. This process involves the use of the Chinese remainder theorem to obtain a rapid decryption without harming the qualities of the RSA process.

The present invention, also based on the Chinese Remainder Theorem, provides a system for which the decryption process is further improved to a very large extent with regard to the speed of the decryption process.

For this, such a system is remarkable in that it comprises at least one formed decryption device:

- modulus determination means for determining a decryption modulus chosen from among said factors,

- first modular reduction means to make a first modular reduction on the number d with a modulus equal to said decryption modulus reduced by one unit to provide a reduced number,

- second reduction means for making a second modular reduction on each part of the message encrypted with a module equal to said decryption module in order to provide a reduced part of the encrypted message,

second exponentiation means for performing modular exponentiation on each reduced encrypted message part with a modulus equal to said decryption modulus and with an exponent equal to said reduced number in order to restore said message. '

Thus, thanks to the measures recommended by the invention, it is no longer necessary to carry out the operation of combining the residues, see formula (1) of the aforementioned article.

The following description given with reference to the accompanying drawings, all given by way of non-limiting example, will make it clear how the invention can be implemented.

FIG. 1 shows a communication system according to the invention.

FIG. 2 shows an encryption flowchart according to the invention.

FIG. 3 shows a decryption flowchart according to the invention.

Figure 4 shows the schematic of a user device.

FIG. 5 shows a system according to the invention involving a so-called trusted server and a plurality of devices between users.

In Figure 1, reference 1 indicates the encryption device. The latter receives a message M, for example HELLO.

This message is divided into message parts to be encrypted by cutting means 3 These parts are made up of each of the letters that compose it and a series of digital codes is obtained, for example the digital codes in decimal M1 = 66, M2 = 79, M3 = 78, m4 = γ4, M5 = 79, m6 = 85, M7 = 82 which represent the ASCI codes of HELLO. Exponentiation means 5 perform exponentiations on these digital codes by taking parameters e and N according to measurements, the first of which follows directly from the invention:

- We take numbers p and q greater than 255: p = 263 and q = 311 hence N = pq = 81793 ·

- We choose e such that it is prime with p-1 and q-1 that is: e = 17.

- We now determine d: ed = 1_{MOD f (N)}

In the case where p and q are prime <p (N) = (p-1). (Q-1) that is to say:

= l_mod (406l0)

Among the ds which satisfy the above relation, we can take 5 ^ 943 · In principle d is not known at the level of the encryption device 1. The means 5 can then encode the message by performing on each of the aforementioned codes l '' modular exponentiation operation:

^This = ^{Mi 17}mod (N) 1 = 1 - .. 7 hence the coded message comprising the encrypted parts:

Cl = 62302, C2 = 47322, C3 = 74978, C4 = 00285, C5 = 47322, c6 = 09270, C7 = 54110.

According to the invention, to decrypt this message, a decryption device 10 is provided. This device uses a first means for determining the decryption module from among the numbers p and q, one chooses, preferably the smallest, for s. '' save calculations, either:

P (= 263) of the second means perform the modular reduction operation on the number dd_r = 5 ^ 9 ^ 3 mod ₂₆₂ = 185

The encrypted message parts are then reduced, according to the module p.

VS_rl = 62302 mod _2&3= 234 and respectively C_r2 = 245, C_r3 ⁼ 023, 0_r4 = 022, C_r5 = 245, C_r6 = Ο65, C_r7 = 195, hence the decrypted message parts: ^mi = Cr^{1 l85}mod 263 = ⁶⁶ “2 = C_r2 ^l85moa 263 = 79 ^m3 “^ R3 ⁵mod 263 “78“ 4 = cr4 ^l85mod 263 = 74 “5 = c_r5 ^l85mOd 263 = 79 “6 = C_r6 ^l85mod 263 = 85 m₇ = C_r7 ^l85mod 263 = ⁸²

The message m is then restored by concatenation and by »transcription into usual characters by the final reconstitution means 4. If all went well, m = M.

The encryption device 1 and the decryption device 10 are in fact made from processors programmed to execute the flowcharts shown in FIGS. 2 and 3 below.

The flowchart of FIG. 2 explains the operation of the device 1. Box K1 indicates a test carried out on each part of the encrypted message. If this value exceeds that of the chosen decryption module (therefore the smallest among p and q), then, we declare that there is an error in box K2. Otherwise, we go to box K5 where the actual encryption operation is performed, that is to say a modular exponentiation. In this way, parts of encrypted messages Ci are obtained.

The flowchart of FIG. 3 shows the decryption operations performed by the decryption device 10. This flowchart shows in box K10 a preliminary reduction operation on the number d to provide a reduced key number dr. Box K12 is a modular reduction operation according to p performed on the encrypted message parts and box K14 is a modular exponentiation of modulus p and whose exponent is dr on the encrypted message parts.

The encryption and decryption devices can be inserted on the same medium to thus constitute a user device. The devices can then communicate with each other using the encryption method of the invention.

Figure 4 shows the structure of a user device. This device is based on a physically secure microcontroller such as, for example, the 83C852 manufactured by Philips. Such a microcontroller 31 is shown in FIG. 4 and made up from a microprocessor 32, a random access memory 33 and a read only memory 34 which notably contains operating instructions for implementing the invention, in particular the encryption and decryption operations already described. It also includes an EEPROM 35 to contain various data such as the secret key of the card, the public key of a third party with which it exchanges information, etc. It is also composed of a calculation unit 36 ​​to take charge of the operations necessary for carrying out the cryptography functions, of an input / output management unit 37 also connected to an I / O input of the microcontroller. 31 The aforementioned elements of the microcontroller 31 are interconnected by a bus 38

Any additional detail can be found in the instructions for the aforementioned 83C852 microcontroller.

An important example of application of the invention is the transfer of DES key by means of RSA as mentioned in the article Threats of Privacy and Public Keys for protection by Jim Bidzos published in the document PROCEEDINGS OF COMPCON 91, 36th IEEE COMPUTER SOCIETY INTERNATIONAL CONFERENCE - February 25 to March 1, 1991 »San Fransisco NEW YORK (US). The protocol for the exchange of the session key DES between two users A and B via a public channel can be as follows.

Let {n_TO, d_TO} and N_B, d_B} the respective secret keys of users A and B.

For example A wants to transmit the session key K_s to B.

- User A. m = K_s

Encryption is performed using the public key e_B^ ab ^{= m} B and we transfer the cryptogram C_AB via the public channel.

- User B. receipt of cryptogram C_ABdecryption of the cryptogram m = C_AB^dB use of the key K_s

Usually K_s is much less than an RSA key.

K_s may be a DES session key of the order of 56 bits and p and q are of the order of 256 bits.

Many official organizations prohibit encryption of messages in public communications.

The invention is particularly applicable when, to avoid this prohibition, a trusted server SC is used.

This case has been shown in FIG. 5. This figure illustrates the case where a plurality of user devices A, B, .. X can communicate with one another through a trusted server SC. This SC server has all the knowledge to know, in clear, all the messages that the different users exchange.

By way of example, we explain the case where the user A wants to communicate a key DES K_AB to user B. Then, A encrypts the key K_AB using the public key e_B the server SC which itself decrypts it as soon as it is received, then encrypts it with the public key e_B of B. Finally B decrypts the cryptogram in order to find the key initially sent by A.

It can therefore be seen that in this case, the method applies equally well to the level of the decryption of the user B and to that of the server SC. Thus, the invention is used to obtain good availability of the server for a plurality of users. The gain in calculations provided by the invention is particularly appreciated.