CN100448193C - Multi-module encryption method - Google Patents

Abstract

When using an encryption/decryption module, there are many ways to determine the key or keys used by the module by analyzing the data entering or leaving the module. In order to alleviate the disadvantages of these methods, a multi-module approach is proposed in that the downstream encryption/decryption module starts its encryption/decryption operation once the upstream encryption/decryption module has sent its partial calculation results.

Description

Multi-module encryption method

The present invention relates to the field of encryption or decryption of data, in particular data kept inaccessible to unauthorized persons or devices within the framework of pay-per-view television systems. In such systems, data is encrypted in a secure environment that provides considerable computing power and is called an encoding subsystem. The data are then sent by known methods to at least one decentralized subsystem, in which the data are generally decrypted with the help of an IRD (Integrated Receiver Decoder) and with the aid of a chip card. A potential unauthorized person can have unrestricted access to the chip card and the decentralized subsystems cooperating with the chip card.

It is known practice to chain many different encryption/decryption methods in one encryption/decryption system. In the following description, the term encryption/decryption is used to denote a specific encryption method used in a larger encryption/decryption system.

Attempts have long been made to optimize the operation of these systems from the standpoint of speed, storage space occupied and security. Speed is understood here to mean the time required to decrypt received data.

Encryption/decryption systems with symmetric keys are known. Their inherent secrecy can be estimated as a function of several criteria.

The first criterion, that of physical secrecy, has to do with the ease of investigation by extracting certain components, which can then be replaced by others. These replacement elements intended to inform an unauthorized person of the nature and manner of operation of the encryption/decryption system are chosen by him/her in such a way that it cannot be detected, or as far as possible, by other parts of the system.

The second criterion is that of system security, within the framework of which the attack is not intuitive from a physical point of view but requires analysis of a mathematical type. Typically, these attacks will be carried out by computers with high computing power attempting to decipher algorithms and encryption codes.

An encryption/decryption method with a symmetric key is, for example, a system called DES (Data Encryption Standard, Data Encryption Standard). These relatively ancient methods now only provide complete relative system and physical secrecy. For this reason in particular, DES, whose key length is too short to satisfy the conditions of system secrecy, is increasingly being replaced by new encryption/decryption methods or with longer keys. Typically, these methods with symmetric keys require algorithms that include cryptospheres.

Other attack strategies are called single power analysis and timing analysis. In single power analysis we take advantage of the fact that a microprocessor used to encrypt or decrypt data is connected to a voltage source (typically 5 volts). When it is unloaded, a fixed current of size i flows through it. When it is working, the instantaneous value i is not only related to the input data but also to the encryption algorithm. Single power analysis consists in measuring the current i as a function of time. The type of algorithm implemented by the microprocessor can be deduced from it.

In the same way, the timing analysis method consists in measuring the duration of the computation as a function of the samples supplied to the decryption module. In this way, the relationship between the samples provided and the time used to compute the result makes it possible to recover secret parameters of the decryption module such as keys. Such a system is described, for example, in the document "Timing Attacks on Implememtations of Diffie-Hellman, RSA, DSS, and Other Systems" published by Paul Kocher, Cryptography Research, 870 Market St, Suite 1088, San Francisco, Ca-USA.

To improve the secrecy of encryption systems, algorithms with asymmetric keys have been proposed, such as the so-called RAS (Rivest, Shamir and Adleman) system. These systems involve generating a pair of matching keys, one of which is a so-called public key for encryption and the other a so-called private key for decryption. These algorithms show a high level of security, both systematic and physical. On the other hand, they are slower than traditional systems, especially at the encryption stage.

Recent attack techniques call for the so-called DPA concept that stands for Differential Power Analysis. The basis of these methods is the conjecture, which can be proved after a large number of experiments, about the existence of a 0 or a 1 at a given position of the encryption key. They are nearly non-destructive, which makes them largely undetectable, and requires both a physical intrusion component and a mathematical analysis component. The way they work reminds us of the technology used to detect oil fields, where a blast of known power is created on the surface of the earth, and earphones and probes are placed at known distances from the blast, without much digging, using Shock waves reflected by the boundaries of the subsurface sedimentary bed enable assumptions to be made about the stratigraphic composition of the subsurface. In section 2.1 of the document "A Cautionary Note Regarding Evaluationl of AES Candidates on Smart-Cards" by Suresh Chari, Charanjit Jutla, Josyula R. Rao and Pankaj Rohatgi, IBM T.J. Watson Research Center, Yorktown Heights, NY, published February 1, 1999 DPA attacks are specifically described in Section .

The requirement that DPA attacks must be prevented forces the use of so-called "whitening" jamming systems either in the input information or on the output of the encryption/decryption algorithm. Whitening techniques are described in Section 3.5 of the same document mentioned above.

However, the fact that computational power is limited in the decentralized subsystems of pay-per-view television systems, to implement a sufficient degree of linking as described above, creates a problem that has never been satisfactorily solved.

The purpose of the present invention is to make available encryption/decryption methods against modern investigative methods as described above.

The object of the present invention is achieved by the method of encryption and decryption using at least three encryption/decryption modules connected in series, characterized in that each of the intermediate and last encryption/decryption modules Once part of the information is available before the module ends the encryption/decryption operation, the encryption/decryption operation starts.

The peculiarity of this method lies in the fact that intermediate modules do not start working when results from previous (or upstream) modules have terminated, but start working as soon as partial information is already available. Therefore, for an external observer, it is not possible to establish input or output conditions for this module.

Because in a decentralized subsystem cooperating with the chip card, which offers only relatively limited computing power compared with the encoding subsystem, the decryption takes place, for example with a public Asymmetric keys are beneficial. This makes it possible, on the one hand, to preserve the indestructible character of the system during the detachment process, and on the other hand to concentrate in the encoding subsystem, with the help of private keys, essentially encryption-related computing power.

We have found that additional security is provided due to the possibility of two mutually chronologically following encryption/decryption methods being chained or partially interleaved. We understand chaining or partial interleaving to mean that the process consists in starting the work of the 2nd encryption/decryption method on these same data while the 1st encryption/decryption method has not finished its work on these same data. This makes it possible to mask the data as if they were due to the work of the 1st module and before being acted upon by the 2nd module.

The linking can start as soon as the calculated data portion at the output of the first module is available for processing by the second module.

The invention makes it possible to protect against the above-mentioned attacks by combining many different encryption/decryption methods in one encryption/decryption system and possibly by combining chaining or partial interleaving with sequences in which these methods follow each other.

In a specific embodiment of the invention, the encryption/decryption system includes an encoding subsystem that sequentially uses three algorithms:

a) An asymmetric algorithm A1 with a private key d1. This algorithm A1 adds a signature to the plaintext data represented by the message m, this operation conveys the first secret message c1 through a mathematical operation generally expressed by the following formula: c1=m exponent d1, modulo n1. In this formula, n1 forms part of the public key of the asymmetric algorithm A1, the modulus represents a well-known mathematical congruence operator within the set of related integers, and d1 is the private key of the algorithm A1.

b) A symmetric algorithm S using a secret key K. This algorithm transforms the secret message c1 into the secret message c2.

c) An asymmetric algorithm A2 with a private key d2. This algorithm A2 transforms the secret message c2 into a secret message c3 using the mathematical operation described above by the following formula: c3 = c2 exponent d2, modulo n2, where n2 forms part of the public key of the asymmetric algorithm A2, d2 is the private key for Algorithm A2.

In a method known per se, the tip c3 leaves the encoding subsystem and reaches the decentralizing subsystem. In the case of pay-per-view television systems, this may equally involve video data or messages.

The decentralized subsystem uses the three algorithms A1', S' and A2' in the reverse order of the above. These 3 algorithms form part of 3 encryption/decryption methods A1-A1', S-S' and A2-A2' distributed between the encoding subsystem and the decentralized subsystem and represent the encryption/decryption system.

d) Algorithm A2' implements a mathematical operation on c3 to restore to c2, and is expressed as: c2=c3 exponent e2 modulo n2. In this formula, the group consisting of e2 and n2 is the public key of the asymmetric algorithm A2-A2'.

e) The symmetric algorithm S' uses the secret key K to recover the secret message c1.

f) The asymmetric algorithm A1' with the public keys e1, n1 recovers m by implementing the mathematical operation shown below: m=c1 exponent e1 modulo n1.

In the decentralized subsystem, the chaining consists in starting the decoding step e) when c2 has not been fully recovered by the preceding step d), and starting the decoding step f) when c1 has not been fully recovered by step e). The advantage is that it is possible to prevent an attack on e.g. first extracting the secret message c1 in the decentralized subsystem at the end of step e) in order to compare it with the plaintext data m, and then attacking the algorithm A1' with c1 and m, and then gradually reshaping to the code Link.

Links are not required in coded subsystems installed in secure physical environments. On the other hand it is useful in decentralized subsystems. In the case of pay-per-view television, the IRD is in fact installed at the subscriber's premises and may be the target of an attack of the type described above. It is preferable to make the combined attack of the 3 chained decoding algorithms A1', S' and A2' have much less success than if the secret messages c1 and c2 were fully reconstructed between each step d), e) and f) Chance. However, the fact of using algorithms A1' and A2' with public keys e1, n1 and e2, n2 means that the calculations required in the decentralized subsystem are much reduced when compared to those in the encoding subsystem.

Using the example and the fixed case, the steps a) and c), that is to say the encryption step with the private key are 20 times longer than the decryption steps d) and f) with the public key.

In a particular embodiment of the invention derived from the above embodiment, algorithms A1 and A2 are identical to their counterparts A1' and A2'.

In a particular embodiment of the invention, also derived from the above embodiment, in step c) the public key e2, n2 of the asymmetric algorithm A2 is used, and in step d) the secret message c3 is paired with the private key d2 of this algorithm to decrypt. This embodiment constitutes a possible variant when the resources of decentralized subsystems are far from available in terms of computing power.

Although chip cards are primarily used to decrypt data, there are also chip cards that have the capabilities required to perform cryptographic operations. In this case, the above-mentioned attack will also be related to these encrypted cards working away from a protected location, such as a management center. This is why the method according to the invention is also applicable to continuous encryption operations, ie the downstream module starts its encryption work as soon as a part of the information delivered by the upstream module is available. The advantage of this process is that many different encryption modules can be interleaved, so not all results from upstream modules are available at a given time. However, downstream modules do not start their work with complete but partial results, making it impractical to specify how a module works for a known input state or output state.

We will understand the invention in more detail with the following drawings, taken by way of non-limiting example, in which:

Figure 1 shows the encryption operation.

Figure 2 shows the decryption operation.

Figure 3 shows another possible encryption method.

In Fig. 1, the data set m is introduced into the encryption chain. The first element A1 is encrypted with a so-called private key consisting of exponent d1 and modulo n1. The result of this operation is denoted by C1. According to the working mode of the present invention, the next module starts working as soon as a part of the result C1 is available. This next module S performs its encryption operations with a secret key. As soon as it is partially available, the result C2 is transmitted to the module A2 in order to carry out a third encryption operation with a so-called private key consisting of exponent d2 and modulo n2. This final result, referred to here as C3, is ready to be transmitted via known paths such as radio waves or cables.

Figure 2 shows a decryption system consisting of 3 decryption modules A1', S', A2' similar to those used for encryption but in reverse order. Thus, we start first with module A2', which performs its decryption operation on the basis of a so-called public key composed of exponent d2 and modulo n2. In the same way as for encryption, as soon as part of the result C2 from module A2' is available, it is transferred to module S' for the second decryption operation. To complete the decryption, the module A1' carries out its operations according to the so-called public key composed of the exponent e1 and the modulus n1.

In a particular embodiment of the invention, the keys of the two modules A1 and A2 are the same, that is to say d1=d2 and n1=n2 when encrypting. Similarly, when decrypting, e1=e2 and n1=n2. In this case we speak of a private key d,n and a public key e,n.

In another embodiment of the invention, shown in FIGS. 3 and 4, the module A2 uses a so-called public key instead of a so-called private key. When encrypting, the module A2 operates with the public key e2, n2 (see Fig. 3) and when decrypting (see Fig. 4), the module A2' operates with the private key d2, n2. Although this configuration shows a general working for the decryption group, the use of a private key enhances the security provided by module A2.

The examples shown in FIGS. 3 and 4 do not limit other combinations. For example, module A1 may be configured to use a public key for encryption operations and a private key for decryption operations.

It is also possible to replace the encryption/decryption module with the secret key S by a module of the type with an asymmetric key of the same type as the modules A1 and A2.

Claims (10)

1. utilize the encryption and decryption method of the encrypting-decrypting module of at least three series connection, it is characterized in that in a single day each module in the middle and last encrypting-decrypting module can obtain partial information before next-door neighbour's previous encrypting-decrypting module finishes the encrypt/decrypt computing, just begin to carry out the encrypt/decrypt computing.

2. according to the method for claim 1, it is characterized in that each module in the middle and last deciphering module, just begin to be decrypted computing in case can obtain partial information from next-door neighbour's previous deciphering module.

3. according to the method for claim 1, it is characterized in that each module in the middle and last encrypting module, just begin to carry out cryptographic calculation in case can obtain partial information from next-door neighbour's previous encrypting module.

4. according to the method for one of claim 1 to 3, (A2), central module (S) is for using the type of secret symmetric key (k) for A1, S with 3 modules to it is characterized in that it.

5. according to the method for claim 4, it is characterized in that, the 1st module (A1) for encryption and last module (A2), and the 1st module (A2) for deciphering and last module (A1) are the RSA type of a private key and a public-key cryptography for using unsymmetrical key.

6. according to the method for claim 5, (A1 is A2) for encrypting with so-called private key (d, n to it is characterized in that described two modules; D1, n1; D2, n2), for deciphering with so-called public-key cryptography (e, n; E1, n1; E2, n2).

7. according to the method for claim 6, it is characterized in that described two modules (A1, A2) with identical private key (d, n) and public-key cryptography (e, n) group.

8. according to the method for claim 6, (A1 is A2) with different private keys (d1, n1 to it is characterized in that described two modules; D2, n2) and public-key cryptography (e1, n1; E2, n2) group.

9. according to the method for claim 5, it is characterized in that when encrypting, last module (A2) with so-called public-key cryptography (e2, n2), when deciphering, the 1st module (A2) with so-called private key (d2, n2).

10. according to the method for one of claim 1 to 3, it is characterized in that it with 3 encrypting-decrypting modules that use unsymmetrical key (A1, A, A2).

Images