FR2772532A1 - METHOD FOR SECURING THE TRANSMISSION OF A MESSAGE FROM A TRANSMITTING DEVICE TO A RECEIVER DEVICE - Google Patents

Abstract

The invention concerns a method for making secure the transmission of a message (Prgm) from a transmitting device (E) to a receiving device (R), characterised in that: the message (Prgm) is split into n elementary units (I), n being a number not less than 1; a logical property (P) is defined such that, for each elementary unit (I), the logical property (P), applied to an authentic elementary unit (I), gives a true logical value; the message (Prgm) is encrypted by the transmitting device (E) encryption means using an encryption algorithm comprising a key (Kc) so as to obtain a result Kc(Pgrm); The encrypted result Kc(Pgrm) is transmitted by the transmitting device (E) to the receiving device (R); the encrypted result Kc(Pgrm) is decrypted by the receiving device (R) using a decryption algorithm comprising a secret key (Kd) so as to obtain a decrypted result Kd(Kc(Pgrm)); the decrypted result Kd(Kc(Pgrm)) is split into elementary units (I); the logical property (P) is applied to the elementary units (I) so as to obtain, for each unit, a true logical value or a false logical value. The method is particularly applicable to smart cards.

Description

METHOD OF SECURING THE TRANSMISSION OF A
MESSAGE FROM A TRANSMITTING DEVICE TO A DEVICE
RECEIVER
The invention relates to a method for securing the transmission of messages from a transmitting device to a receiving device.

 When information is transmitted from a transmitting device to a receiving device, this information, contained in a message, may be altered during transmission. This alteration can come either from a defect in the transmission, the transmission or the reception of the message or from a fraud of a third party. The message received is not honest.

 For this reason, methods have been developed to verify the integrity of transmitted messages.

 Furthermore, when information is transmitted from a transmitting device to a receiving device, it is sometimes useful to make the message confidential so as to reserve access to said information to a limited number of people, in general the transmitter and the receiver of the message.

 This is why we have developed methods to preserve the confidentiality of a message.

 Finally, when information contained in a message is transmitted to a receiving device, it is often useful to authenticate this message as actually coming from the transmitting device.

 This is why we have developed methods of message authentication.

 The known methods for verifying integrity, preserving confidentiality and authentication, that is to say securing messages, generally consist of encrypting the message and attaching a certificate to it before transmission. The receiving device then decrypts the message, verifies the certificate and, possibly, in the case where said message is a computer program, executes it.

 These procedures are obviously cumbersome, since the decryption and verification of the certificate each impose an operation. This is the case, in particular, when the encryption and decryption operations are long.

 Considering the foregoing, a problem that the invention proposes to solve is to provide a method for securing the transmission of a message from a transmitting device to a receiving device that does not require the implementation of the two aforementioned steps. decryption of the message and verification of the certificate.

In view of the problem posed above, the subject of the invention is a method of securing the transmission of a message from a transmitting device to a receiving device, characterized in that
the message is divided into n elementary units, n being a number greater than or equal to 1;
a logical property is defined so that, for any elementary unit, the logical property, applied to an authentic elementary unit, gives a logical value of the true type;
the message is encrypted by encrypting means of the transmitting device by means of an encryption algorithm comprising a key so as to obtain an encrypted result
the encrypted result is transmitted by the transmitting device to the receiving device;
the encrypted result is decrypted by the receiver device using a decryption algorithm comprising a secret key so as to obtain an decrypted result
- the decrypted result is divided into elementary units
the logical property is applied to the elementary units so as to obtain, for each unit, a logical value of the true type or the false type.

- the message is considered authentic and honest if,
for each unit, the logical values have a value of the type
true.

 The message is then advantageously stored.

It will furthermore be noted that, advantageously, the message Prgm is a computer program that can be executed and / or interpreted by the receiver device R. The elementary units are instructions of the Prgm program. The property
P, applied to an elementary unit I, gives a logic value of true type when the elementary unit I is executable and / or interpretable. The property P, applied to an elementary unit I, gives a false type logical value when the elementary unit I is not executable and / or interpretable. The receiver device R is a portable memory object of the smart card type. The receiver device R comprises a portable memory object of the smart card type. The portable memory object is a subscriber identification module (SIM). The Prgm message is written in a high level interpreted language. The high level language is the Java language. The computer program consists of a set of precompiled instructions. The message Prgm is encrypted in continuous flow or in linked blocks. The message Prgm is encrypted in blocks and that the blocks of the encrypted Prgm message are exchanged. One of the permuted blocks is a start or end block of the Prgm message. The result Kc (Prgm) is decrypted in blocks, each encrypted block being at the origin of an decrypted block taking the place of the encrypted block. The encryption and decryption algorithms involve a hazard, transmitted by the transmitting device E, to the receiver device R. The message Prgm is recorded, after verification, in a non-volatile memory of the receiver device R.

 This invention will be better understood on reading the nonlimiting description which follows.

 According to the invention, the message Prgm is transmitted from a transmitting device E to a receiver device R.

 The Prgm message is for example a computer program that can be executed and / or interpreted.

 The transmitting device E is, for example, a server, a computer, a transmitting station in a telecommunications network or a smart card reader with or without contact, in short, any device capable of encrypting and transmitting a message. Of course, the transmitting device E must be considered in a broad sense to include complex devices formed in particular of physically separated parts, a part ensuring for example the encryption of the message, another, the transmission stricto sensu said message.

 The receiver device R is, for example, a computer possibly equipped with a smart card reader and a card inserted in said reader, a receiving station in a telecommunications network, a mobile phone with or without a module. subscriber identification (SIM) or even a smart card or such a module, in short, any device capable of receiving a message or even to store this message and, advantageously, when the message is a computer program, to interpret and / or to run this program. In the case where the receiving device advantageously comprises a portable memory object of the smart card type, the portable object may be a payment card or an access control card, for example, a computer network.

 In the remainder of the disclosure of the invention, it will be limited to the examples where the message is a computer program Prgm.

 According to the invention, this computer program Prgm is divided into n elementary units I, n being an integer greater than or equal to 1. These are instructions, blocks of instructions or, in the case where the program Prgm is written in an interpretable language of Java type, precompiled instructions of the program (or bytecodes).

 According to the invention, a logic property P is defined so that, for any elementary unit I, this property P, applied to an authentic elementary unit, gives a logical value P (I) of the true type. Nevertheless, we will try to find a property P which, applied to an elementary unit I, gives a logical value P (I) of the false type when said elementary unit I has been modified and corresponds for example to an unrecognizable instruction of the program, in particular not likely to be interpretable and / or executable.

According to the invention, the program Prgm is encrypted by means of encryption of the transmitting device E by means of an encryption algorithm comprising a key Kc known from said device E so as to obtain a result Kc (Prgm). The encryption guarantees the confidentiality of the program Prgm during its transmission and reception, but, above all, during its transmission to the receiver device R. This result Kc (Prgm) is then transmitted by the device
E, to the receiver device R.

 I1 is then decrypted by this device R using an encryption algorithm comprising a secret key Kd, known to the receiving device. A decrypted result Kd (Kc (Prgm)) is then obtained.

 This key Kc may be specific to the device E and known to the device R, or specific to the device R and also known to the device E. An example of the first configuration is the case where the device R is subscribed to a service delivered by the device transmitter.

An example of the second configuration is the case where the receiving device, when requesting a transmission of the program, provides the key Kc, the decryption key Kd remaining known from the single receiving device. Another example of the same configuration is the case where Kc and Kd are identical (private key system), and where this key is sent, in encrypted form, by the receiving device to the transmitting device.

According to the invention, the decrypted result Kd (Kc (Prgm)) is divided or decomposed into n elementary units, images of or corresponding to n elementary units resulting from the division of the program.
Prgm in the transmitter device E.

 The logic property P is then applied to said n elementary units so as to obtain, for each unit, a logical value of the true type or the false type.

In the case where all logical values are true, there is a strong probability that the decrypted program is identical to the encrypted program and that the key used for encryption is the key.
Kc expected. The receiver device R then deduces that the Prgm program is intact and that it was emitted by a transmitter device E having the key Kc, so authentic.

 On the other hand, in the case where at least one logic value is of the false type, the decrypted program is different from Prgm and the receiver device R deduces that the Prgm program has undergone at least one modification to the transmission. , on receipt or during transmission and / or that said Prgm program has encrypted the message with a key other than Kc, an unexpected key. The program is then not honest or not authentic.

 The invention thus makes it possible to guarantee, in a single encryption-decryption operation, both the integrity, the authentication and the confidentiality of the Prgm program.

 Considering, for example, that the instructions of the computer language in which the Prgm program is written are four-byte coded instructions, there are theoretically 232 possible codes for defining an instruction. Of course, some codes, defined by a set of parameters, do not correspond to any understandable instruction. In addition, some parameters of some codes, typically the last three octets, have only certain allowed values. A memory address can not be negative, or be outside the space allocated to the Prgm program. This is why the property P advantageously comprises a parameter test, said test depending on the type of instruction.

If the unit non-detection rate C is defined as the percentage of the possible instructions which are not recognized as false by the application of the property P during decryption and following a specific modification of the program
Prgm, the probability that the receiver device R does not detect the fraud is, when the one-time modification is causing a modification on each instruction of the decrypted result:
prob = (1 - n.

For the following typical values, the following probabilities are obtained:

<tb><SEP> n <SEP> C <SEP> (%) <SEP> prob
<tb> 256 <SEP> 10% <SEP> 1.9E-12
<tb> 128 <SEP> 10% <SEP> 1.4E-06
<tb> 512 <SEP> 5% <SEP> I
<tb> 128 <SEP> 5% <SEP> 1.4E-03
<Tb>
It can be seen that the probability that a particular fraudulent modification will go unnoticed is very low, except in the case of programs with few instructions and whose unit non-detection rate C is very high. This probability is a fortiori very low in the case where the program has been encrypted by a key other than Kc.

 Compared with the usual encryption operations, the application of the property P does not require a too heavy implementation including a calculation time too long. It allows the detection of errors in all types of programs Prgm since the encryption algorithm is of good quality, given the pseudo-random character of any decryption of a series of falsified instructions.

 The encryption algorithm is advantageously of the type in chained blocks or in continuous flow. Thus, a modification of an elementary instruction will result in a modification of other instructions. On the other hand, when the algorithm proceeds only in blocks, the encrypted program can be decomposed into a sequence of, for example, n blocks corresponding approximately to the n elementary units. By modifying a block and observing the behavior of the receiving device, the prob probability that the change is not detected is then equal to 1 - C, therefore very high.

 In order to avoid a directed modification to the head or tail block of the encrypted program, the blocks of the encrypted program are, for example, switched so that said head and tail blocks of the program are at a location which is not not predictable by a fraudster, but nevertheless known devices E and R.

 The confidentiality is furthermore improved when the encryption algorithm involves a hazard generated for example by the receiver device R and communicated to the transmitter device E. It may be, for example, an "exclusive" operation applied to a fixed number of bytes of the program or all before encryption.

 We can finally introduce at the beginning and / or end of the program, before encryption, empty instructions (NOP), which the receiving device will recognize by applying the property P, then eliminate.

 In a first embodiment of the invention, the transmitting device E is a base station of a GSM (Global System for Mobil Communication) telecommunications network or of any other mobile telephone system involving a security module. , the receiver device R is a SIM subscriber identification module associated with a mobile phone. The program Prgm, intended to be downloaded into said SIM module, is coded in the form of precompiled instructions (bytecodes) written for example in the Java language.

 Of course, the invention applies equally to other smart card systems, such as payment or access control systems.

 In this first embodiment of the invention, the program is divided into n elementary units, an elementary unit being a precompiled instruction of a fixed number of bits (fixed or dependent on the type of instruction).

 The logical property P is defined so that it takes a logical value true when the elementary unit to which it is applied is an executable (or interpretable) instruction or corresponds to a NOP instruction.

 The Prgm program is then encrypted by the transmitter device E with an encryption algorithm, for example of the RSA type (Rivest, Shamir and Adelman) as described in US Pat. No. 4,405,829. An encryption result Kc (Prgm), a function of the key Kc, is then obtained.

 This result Kc (Prgm), ultimately the encrypted program, is transmitted by the base station to a transmitting station associated therewith and to receiving means of the mobile phone. It is then loaded into the card where it is stored in a non-volatile memory EEPROM before the decryption operation, given the slowness of this operation implemented on a SIM module.

The result Kc (Prgm) is then decrypted using a decryption algorithm comprising a secret key Kd. Each block of the decrypted result is stored in the non-volatile memory
EEPROM of the SIM module, at the block address of the corresponding encrypted result. Thus, the memory space used for the implementation of decryption according to the invention is minimal. Note that, in an implementation variant of the invention, using at least one free memory space corresponding to a block, it is possible to record the blocks of the decrypted result at memory addresses different from the encrypted blocks to which they correspond. Circular permutation is equally possible, improving the security of the program during the decryption step.

 The application of the property P preferably takes place at the end of the complete decryption of the encrypted result Kc (Prgm), the final result (accepted or rejected program) being given only at the end of all the checks. Thus, the fraudster can not simply detect the elementary unit I recognized as giving a false logic value when applying the property P.

Given the low memory available in the module
SIM, a simple calculation function of the property P is implemented. This is a function implemented by the interpreter himself. Once the encrypted result is decrypted, the interpreter interprets the decrypted result by looking at whether the instructions have meaning or not. In the end, the interpreter carries out the analysis of the program as it would in a normal interpretation, without however that this interpretation is followed by any effect other than the verification that the result decrypted corresponds to a program
Prgm.

In a second embodiment of the invention, the transmitting device E is a server comprising a precompiled and encrypted form Kc (Prgm) of a Prgm program, written for example in the Java language. The receiver device R is a personal computer, which will be usefully provided with a smart card reader in which a card is inserted. The personal computer comprises a hard disk and a safe memory zone, that is to say one that is not likely to be read or written by a third party, for the temporary or permanent storage of decrypted results Kd ( Kc (Prgm)) and keys. The computer further includes a program loading software Prgm called Loader invoked whenever it is necessary to load a precompiled Prgm program, before said Prgm program is used (interpreted or executed). In the present second embodiment of the invention, this software includes a decryption function, which advantageously comprises functional elements necessary for decryption and in particular elements of the decryption algorithm. The program loading software is then overloaded. Of course, other functional elements necessary for decryption can be contained in a non-volatile memory of the smart card. These elements will then be called by the program loading software and the decryption function. Thus, the loading software allows, in association with the card, the decryption of the result Kc (Prgm) and the verification of the decrypted result Kd (Kc (Prgm)) before the interpretation of said decrypted result Kd (Kc (Prgm)), that is, when the property
P has been successfully applied, the program Prgm, and the execution of this program Prgm.

 The constraints of time and memory space that were mentioned during the description of the first embodiment of the method of the invention are, in this second embodiment, less, since the card is here only used as a secure physical medium of one or more keys or elements, tables for example, necessary for decryption. The card can even contain the entire secret decryption algorithm.

 The property P may, therefore, be not only of the type mentioned above, or else be a particular property whose implementation algorithm will be implemented. The verification algorithm verifies in an example the precompiled instructions each time an instruction block (s) of the encrypted result is decrypted.

 The exchange phases between, on the one hand, the personal computer equipped with the interpreter, the loading device and associated with a card reader in which the card is inserted and, on the other hand, the card, can to break down into three phases: an initialization phase, a transfer phase and a decryption / verification phase.

 The initialization phase is in fact a phase of exchange of a public and secret key pair. This phase is started when the decryption process is initialized. The key pairs are not written to the hard disk of the personal computer and can be recalculated at any time. During this phase, a re-initialization order is transmitted by the personal computer to the card. The computer then calculates a public key pair PKc - secret key PKd, then calculates a signature of the public key PKc using the secret key PKd. This signature is transmitted with the public key PKc to the card. It is then verified by the card, using the PKc public key. The card then calculates, using a secret key CKd, a signature of the public key CKc. This signature is transmitted, with the public key CKc, to the personal computer.

The computer verifies the signature, using the public key CKc.

 The transfer phase is a phase of loading secret information from the card into the personal computer. This information allows the computer to decrypt the precompiled and encrypted form of the Prgm program. For this phase, the computer requests the card to transfer the secret decryption key Kd that it has in its memory. The card encrypts this key using the PKc key, and sends it to the computer. This one decrypts this message using his key Kd, and thus has the key Kc.

It is then possible for him to decrypt the program Kc (Prgm), to obtain a program Prgm ', which is none other than the original program Prgm if no attempt of fraud took place.

The computer can at this point break down the program
Prgm 'in elementary units, and apply property P to them, as in the first embodiment. If the result is satisfactory, it archives said program, for example on its hard disk. It can also compute audit information (for example a cheksum or, better, a hashing) and store it in the memory of the card, for subsequent verification of program integrity.

Claims (17)

 A method for securing the transmission of a Prgm message from a transmitting device E to a receiver device R, characterized in that:  the message Prgm is divided into n elementary units I, n being a number greater than 1;  a logical property P is defined in such a way that, for every elementary unit I, the logical property P, applied to an authentic elementary unit I, gives a logical value of the true type;  the message Prgm is encrypted by means of encryption of the sending device E by means of an encryption algorithm comprising a key Kc so as to obtain an encrypted result Kc (Prgm);  the encrypted result Kc (Prgm) is transmitted by the transmitter device E to the receiver device R  the encrypted result Kc (Prgm) is decrypted by the receiver device R by means of a decryption algorithm comprising a secret key Kd so as to obtain an decrypted result Kd (Kc (Prgm));  the decrypted result Kd (Kc (Prgm)) is divided into elementary units I;  the logic property P is applied to the elementary units I so as to obtain, for each unit, a logical value of the true type or the false type;  the message Prgm is considered authentic and integrates if, for each unit, the logical values have a value of the true type.  2. Method according to the preceding claim, characterized in that the Prgm message is a computer program that can be executed and / or be interpreted by the receiver device R.  3. Method according to the preceding claim, characterized in that the elementary units are instructions of the program Prgm.  4. Method according to claim 2 or 3, characterized in that the property P, applied to an elementary unit I, gives a logical value of true type when the elementary unit I is executable and / or interpretable.  5. Method according to one of claims 2, 3 or 4, characterized in that the property P, applied to an elementary unit I, gives a logical value of false type when the elementary unit I is not executable and / or interpretable.  6. Method according to one of the preceding claims, characterized in that the receiver device R is a portable memory object of the smart card type.  7. Method according to one of claims 1 to 5, characterized in that the receiver device R comprises a portable memory object of the smart card type.  8. Method according to claim 6, characterized in that the portable memory object is a subscriber identification module SIM.  9. Method according to one of the preceding claims, characterized in that the Prgm message is written in a high level interpreted language.  10. Method according to claim 9, characterized in that the high level language is the Java language.  11. Method according to one of claims 9 or 10, characterized in that the computer program is formed of a set of precompiled instructions.  12. Method according to one of the preceding claims, characterized in that the Prgm message is encrypted in continuous flow or chained blocks.  13. Method according to one of the preceding claims, characterized in that the Prgm message is encrypted in blocks and in that the blocks of the encrypted Prgm message are permuted.  Method according to claim 13, characterized in that one of the permuted blocks is a start or end block of the message Prgm.  15. Method according to one of claims 1 to 12, characterized in that the result Kc (Prgm) is decrypted in blocks, each encrypted block being at the origin of an decrypted block taking the place of the encrypted block.  16. Method according to one of the preceding claims, characterized in that the encryption and decryption algorithms involve a hazard transmitted by the transmitting device E to the receiver device R.  17. Method according to one of the preceding claims, characterized in that the Prgm message is recorded, after verification, in a non-volatile memory of the receiving device. R.