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

The present invention relates to a message communication system encrypted using an RSA-type process 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 = 1_{modφ (N)} where φ (N) is the Euler indicator function, the system comprising firstly at least one encryption device formed:<ul><li>cutting means for cutting the message to be encrypted into at least one message part to be encrypted,</li><li>of exponentiation means to perform, on each message part to be encrypted, a modular exponentiation module operation "N" and with an exponent equal to a first of the said key numbers, to provide a portion of encrypted messages and on the other hand at least one decryption device.</li></ul>

The invention also relates to a method implemented in the system, a user device, such microcircuit card comprising on the same support an encryption device and a decryption device and a host of said confidence for processing information between the various user devices.

One such method is described in the article entitled "Fast decipherement algorithm for a Public-Key Cryptosystem" with authors such as MM. JJ Quisquater and C. Couvreur, published in the journal Electronics Letters of 14 October 1982. This process involves the use of the Chinese remainder theorem to get a quick decryption without harming the quality of the RSA method

The present invention, also based on the Chinese remainder theorem, provides a system for which the decryption process is still to a very large extent, improved as regards the speed of the decryption process.

For this purpose, such a system is characterized in that it comprises at least one decryption device formed: <ul><li>module determination means for determining a decryption modulus selected from the said factors,</li><li>first means of modular reduction to a first modular reduction on the number "d" with equal module to said decryption module decreased by one to provide a reduced number,</li><li>second means reduction to a second modular reduction on each encrypted message part with a modulus equal to said decryption module to provide a portion of reduced encrypted message</li><li>of second exponentiation means to perform a modular exponentiation on each reduced encrypted message part with a modulus equal to the said decryption modulus and with an exponent equal to said reduced number in order to restore the said message.</li></ul>

So thanks to the measures recommended by the invention, it is no longer necessary to perform the operation of combination leftover see formula (1) of that Article.

The following description with reference to the accompanying drawings, all given by way of non-limiting example, to understand how the invention can be implemented.<ul><li>1 shows a communication system according to the invention.</li><li>2 shows a flow chart of encryption according to the invention.</li><li>3 shows a flow chart of decryption according to the invention.</li><li>Figure 4 shows the diagram of a user device.</li><li>5 shows a system according to the invention involving a said trust server and a plurality of devices between users.</li></ul>

In Figure 1, reference 1 indicates the encryption device. It receives a message M such as "HELLO". This message is divided into message parts to be encrypted by cutting means 3. These parts are made by each of the letters making up the and obtained a series of digital codes, such as numeric codes in decimal M1 = 66, M2 = 79, = 78 M3, M4 = 74, 79 = M5, M6 = 85 = 82 M7 representing ASCI codes of "HELLO". 5 ways to perform exponentiation exponentiations these numerical codes by taking parameters "e" and "N" according to measures of which the first direct result of the invention:<ul><li>We take numbers p and q greater than 255: p = q = 263 and N = 311 where pk = 81793.</li><li>Is selected "e" such that it is prime to p-1 and q-1 is: e = 17.</li><li>now is determined d: ed = 1_{MOD φ (N)}</li></ul> Where p and q are prime to φ (N) = (p-1) (q-1) is.: ed = 1_{mod (40610)}. Among the "d" that satisfy the above relationship, one can take 54943. In principle "d" is not known at the encryption device 1. The means 5 may then encode the message by performing on each of the codes above the modular exponentiation operation: Ci = Mi ¹⁷_{mod (N)} i = 1 ... 7 hence the encoded message containing the encrypted portions: 62302 C1 = C2 = 47322, 74978 = C3, C4 = 00285, 47322 = C5, C6 = 09270, C7 = 54110.

According to the invention, to decrypt this message, there is provided a decryption device 10. This device utilizes a first determining means decryption module among the numbers "p" and "q" is chosen, preferably more small, to save calculations, including: p (= 263) second means performs the modular reduction operation on the number "d"<dl id="dl0001" compact="compact"><dt>d_r</dt><dd>Mod = 54943 ₂₆₂ = 185</dd></dl> is then reduced, as the "p" module, parts of encrypted messages. <dl id="dl0002" compact="compact"><dt>C_r1</dt><dd>Mod = 62302 ₂₆₃ = 234</dd></dl> respectively and C_r2 = 245, C_r3 = 023, C_r4 = 022, C_r5 = 245, C_r6 = 065, C_r7 = 195, where the decrypted message parts: m₁ = C_r1 ¹⁸⁵_{mod 263} = 66 m₂ = C_r2 ¹⁸⁵_{mod 263} = 79 m₃ = C_r3 ¹⁸⁵_{mod 263} = 78 m₄ = C_r4 ¹⁸⁵_{mod 263} = 74 m₅ = C_r5 ¹⁸⁵_{mod 263} = 79 m₆ = C_r6 ¹⁸⁵_{mod 263} = 85 m₇ = C_r7 ¹⁸⁵_{mod 263} = 82 The message "m" is then returned by concatenation and transcription unusual characters by the final reconstitution means 4. If all went well, m = M

1 the encryption device and the decryption device 10 are actually made from programmed processors to execute the flowcharts shown in Figures 2 and 3 following.

The flowchart in Figure 2 explains the operation of the device 1. Box K1 indicates a test performed on each encrypted message part. If this value exceeds that of the chosen decryption module (thus the smallest among "p" and "q"), then it is declared that there is error in box K2. Otherwise, we go to the box K5 where the actual encryption is done, that is to say, a modular exponentiation. This results in parts of Ci encrypted messages.

The flowchart in Figure 3 shows the decryption operations performed by the decryption device 10. The flowchart shown in box K10 a prior reduction operation on the number to provide a reduced number key "dr". Box K12 is a modular reduction operation by "p" carried out on parts of encrypted messages and box K14 a module modular exponentiation "p" and whose exponent is "dr" on the encrypted message parts.

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

4 shows the structure of a user device. This device is based on a secure microcontroller from a physical point of view as, for example, the 83C852 manufactured by Philips. Such a micro-controller 31 is shown in Figure 4 and compound from a microprocessor 32, a RAM 33 and a ROM 34 which contains particular operating instructions for the implementation of the invention, in particular the encryption and decryption operations already described. It also includes an EEPROM memory to hold 35 different data such as the secret key of the card, the public key of a third party with which it exchanges information ... It is also composed of a calculation unit 36 ​​to take load operations necessary to achieve the cryptographic functions, unit 37 management / O also connected to an input I / O of the microcontroller 31. the above elements of the microcontroller 31 are interconnected by a bus 38.

Further details can be found in the instructions of the microcontroller 83C852 supra.

A significant example of application of the invention is the key transfer DES using RSA as discussed in the article "Threats of Privacy and Public Keys for protection" Jim Bidzos appeared in the document PROCEEDINGS OF COMPCON 91 36th IEEE COMPUTER SOCIETY INTERNATIONAL CONFERENCE - from 25 February to 1 March 1991, San Francisco - NEW YORK (US). The protocol for the exchange of session DES key between two users A and B through a public channel, may be as follows. Let {n_AT, d_AT} and N_B, d_B} The respective secret keys of the users A and B. Eg A wants to transmit the session key K_S B.<ul><li><b>User A.</b>    m = K_S the encryption is performed using the public key e_B    C_AB = m^eB and transferred cryptogram C_AB via the public channel.</li><li><b>B. user</b> reception of the cryptogram C_AB decrypting the ciphertext C m =_AB^dB use of the key K_S. generally K_S is much lower than an RSA key. K_S can be a session key DES in the order of 56 bits and p and q are in the order of 256 bits.</li></ul>

Many government agencies prohibit encrypt messages in public communications. The invention is particularly applicable when to avoid the ban, using a trusted server SC.

this case is shown in Figure 5. This figure illustrates the case where a plurality of user devices A, B, .. X may communicate with one another via a trusted server SC. This server SC has all the knowledge to know, in short, all messages exchanged between different users.

By way of example, explicit the case where the user A wants to communicate a DES key K_AB the user B. Then, A figure key K_AB using the public key e_B SC server that decrypts itself upon receipt, then encrypts it with the public key e_B Finally B. B decrypts the ciphertext to recover the key originally issued by A.

It is thus seen that in this case, the method is equally applicable in the decryption of the user B as the SC server. Thus, the invention is utilized to get a good server uptime for a plurality of users. The gain in calculations provided by the invention is particularly popular.