NL1011544C1 - Encryption system for digital data, uses secondary key to mask primary key, is more difficult to decrypt by Brute Force Attack than data encrypted with conventional single key - Google Patents

Abstract

The unencrypted data (X) is fed to a cryptographic processor (P) where is encrypted by a primary key (K) to produce the encrypted output (Y). The processor is of the 'Data Encryption Standard type. In the present system, the primary key (K) is produced by another processor (P-asterisk) which is itself fed with a secondary key (K-asterisk) and an ancillary key (K').

Description

Short designation: Method and device for cryptographic processing of data.

BACKGROUND OF THE INVENTION

The invention relates to a method for cryptographically processing data, comprising supplying values, namely the data and a key, to a cryptographic process and executing the process 5 to form cryptographically processed data. Such a method is known in practice.

In practice, generally known processes are often used for cryptographic processing of data. Examples of such cryptographic processes (algorithms) are DES and RSA, which are described, for example, in the book "Applied Cryptography" by B. Schneier (2nd edition), New York, 1996.

These processes are published because it was assumed that, with a sufficiently large key length, it would be impossible to retrieve the original data and / or the key from the processed data, even if the cryptographic process was known.

However, attacks based on knowledge of the cryptographic process have recently been discovered. In other words, because the behavior of the process is known, with certain attacks it becomes considerably easier to trace the key used and / or the original data. It will be clear that this is undesirable.

25 SUMMARY OF THE INVENTION

The object of the invention is to solve the above-mentioned problem by indicating a method and circuit for performing a cryptographic process which makes the retrieval of the key considerably difficult or even impracticable when using a known (i.e. public) cryptographic process. According to the invention, a method of the type mentioned in the preamble of 1011544 2 is for this purpose characterized by supplying auxiliary values to the process in order to mask the values used in the process.

5 Masking the data and / or key (s) makes it considerably more difficult to trace these values based on the behavior of the process. The result of the process, ie the set of processed data, can be unchanged, if the auxiliary values are selected appropriately, that is, identical to the result of the process if no auxiliary values are added. In this context, an "auxiliary value" is understood to mean a value (data or key), which is supplied to the process 15 in addition to the corresponding data and key.

The invention is therefore based on the insight that the conversion of the values used in a cryptographic process is considerably complicated if these values are masked by means of auxiliary values. The invention is partly based on the further insight that the use of auxiliary values does not necessarily influence the result of the process.

In a first embodiment of the invention, an auxiliary value comprises an additional key that is supplied to an additional process to form the key.

By using a combination of a known process and an additional process, a new, per se unknown cryptographic process is formed, even if the additional process is also known per se.

By deriving the key (primary key) used for the known process from an additional key (secondary key) by means of an additional process, it is achieved that not the (primary) key of the known process but the additional (secondary) key is offered to the combination of processes. In other words, externally the additional (secondary) 1Π1 1 R4 4 3 key is used and not the actual (primary) key of the actual process. Deriving the key from the original data and the edited data has therefore become impossible. It is also very difficult to derive the additional key, because the combination of the original process and the additional process is unknown.

This embodiment of the invention is therefore based, inter alia, on the insight that the knowledge of a cryptographic process is undesirable, contrary to what has hitherto been assumed. This embodiment is also based on the further understanding that attacks that build on knowledge of the process become considerably more difficult if the process is unknown. Preferably, the additional process comprises a cryptographic process. This makes it easier to trace the additional key. In principle, for example, simple coding can be used as an additional process. An auxiliary key is preferably used in a cryptographic process.

The additional process is advantageously an invertible process. This makes it possible to apply the method according to the invention to existing equipment with minimal changes. For example, if a first device issues an (additional) key which is used in a second device according to the invention, in the first device the inverse of the additional process can be used to derive the additional key from the original key. . In other words, although the original (primary) key is used internally in both the first and second devices, the additional (secondary) key is exchanged between the devices. However, the interception of the additional key does not lead to knowledge of the original key.

It may be advantageous if the additional process is performed only if the data 1011544 4 have predetermined properties. In this way, cryptographic editing can be performed only for certain, selected data, while it is blocked for all other data. In this way, additional protection is achieved.

Optimal security is offered if the process and the additional process each consist of a number of steps, and in which steps of the process and the additional process are alternated. This further obscures the properties of the known process, making it even more difficult to trace the keys.

In a second embodiment of the invention, the process comprises a number of stages, each with a crypto-15 graphical operation for processing the data derived right data and a combining operation for combining the processed right data with data derived left data in order to to form modified data in which the right hand data, prior to operation F, is combined with a primary auxiliary value. Therefore, it is possible to mask the data used in the cryptographic operation.

Preferably, the edited right hand data is always combined with a secondary auxiliary value. This makes it possible, among other things, to mask the modified left data.

Advantageously, the secondary auxiliary value of a stage is formed from the combination of the primary auxiliary value of the previous stage and the primary auxiliary value of the next stage. This makes it possible to compensate the auxiliary value in the subsequent stage, so that this auxiliary value will not affect the end result of the process. A further masking of all data, in particular in the first stage, is achieved if the primary auxiliary value of the first stage is also combined with the left data.

It is possible to carry out the method according to the invention 1011544 5 such that all primary auxiliary values are equal. This makes a very simple practical realization possible. However, the use of different auxiliary values, which are preferably random numbers and regenerated for each time the process is run, provides greater cryptographic security.

A further simplification of this embodiment can be obtained if the primary auxiliary values and / or secondary auxiliary values are each previously combined with the respective operation. That is, combining with auxiliary values is processed in the respective operation (for example, a substitution), so that the result of the respective operation is equal to that of the original operation plus one or two combination operations with auxiliary values. By including the combination operations in the machining in advance, a simpler and faster practical realization is possible.

The said combination operations are preferably performed by means of an exclusive or operation. However, other combination operations, such as binary addition, are also possible in principle.

The invention further provides a circuit for performing: a method of cryptographically processing data. The invention also provides a payment card and a payment terminal which are provided with such a circuit.

The invention will be explained in more detail below with reference to illustrative embodiments shown in the figures.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 schematically shows a prior art cryptographic process.

Fig. 2 schematically shows a first cryptographic process according to a first embodiment of the invention.

1011544 6

Fig. 3 schematically shows a second cryptographic process according to a first embodiment of the invention.

Fig. 4 schematically shows a way in which the processes of FIG. 1 and 2 can be performed.

Fig. 5 schematically shows a first cryptographic process according to a second embodiment of the invention.

Fig. 6 schematically shows a second cryptographic process according to a second embodiment of the invention.

Fig. 7 schematically shows a third cryptographic process according to a third embodiment of the invention.

FIG. 8 schematically shows a circuit in which the invention is applied.

Fig. 9 schematically shows a payment system in which the invention is applied.

PREFERRED EMBODIMENTS

A (cryptographic) process P according to the prior art is schematically shown in figure 1. Input data X and a key K are applied to the process P. Using the key K, the process P converts the input data X into (cryptographically) processed output data Y: Y = PK (X). Process P can be a known cryptographic process, such as DES (Data Encryption Standard), triple DES, or RSA (Rivest, Shamir & Adleman).

If the input data X and the output data Y are known, it is in principle possible to retrieve the key K30 used. With a key of sufficiently long length (i.e., a sufficiently large number of bits), it has hitherto been considered impossible to retrieve this key, even if the process P was known. Impossible in this case means that in theory it is possible, for example by trying all possible keys, to find out the key used, but that this requires an unusually long computing time. Such a brute force attack ("brute force attack") is therefore hardly a threat to cryptographic security.

However, recently discovered attacks use knowledge of the process, which can drastically reduce the number of possible keys. The conversion of the used key K and / or the input data X from the output data Y is thereby possible within acceptable calculation times.

The principle of the invention, which aims at making such attacks considerably more difficult and time-consuming, is schematically shown in Fig. 2. As in Fig. 1, a (known) process P input data X and 15 is supplied a (secret) key K to generate output data Y.

In contrast to the situation of Fig. 1, in the situation of Fig. 2, the key K is supplied from an additional process P * to the process P. The additional process P * has an additional (secondary) key K * as input data to produce, under the influence of an auxiliary key K ', the (primary) key K as output data. The key K is thus not supplied, as in the situation of Fig. 1, from an external source (for example a memory) to the process P, but is generated by the process P * from the additional (secondary) key K *: K = P * K. (K)

Thus, it is the secondary key K * instead of the primary key K which is predetermined and is stored, for example, in a key memory (not shown). In accordance with the invention, the primary key K supplied to the process P is not predetermined.

The auxiliary key K 'may be a permanently stored predetermined key. It is also possible to use an additional process P * in which no auxiliary key K '1011544 8 is used.

The combination of the processes P and P * forms a new process, which is schematically indicated as Q. The process Q, which is unknown per se because of the additional process P *, becomes the input data X and the (secondary) key K * supplied to produce the output data Y. The relationship between the secondary key K * and the primary key K is obscured by the additional process P *.

The complementary process P * is preferably the inverse of another invertible process R. That is, P * = R-1.

This makes it possible to generate the secondary key K * with the aid of R and the auxiliary key K 'from the primary key K: K * = RK. (K), as will be further explained with reference to Figure 5. Optionally, the new process Q can be extended with the process R, so that the primary key K is supplied to the process Q instead of the secondary key K *. In that case, the primary key K is derived in the process Q from: K = P * K. (K *) = P * K. (RK. (K)).

This makes it possible to use the same (primary) key as in the prior art.

The cryptographic process according to the invention schematically shown in Fig. 3 also comprises a process P with a primary key K and an additional process P * with an auxiliary key K ', wherein the primary key K is extracted from the additional key K * is derived. In addition to the process of Fig. 1, in this case the input data X is also supplied to the additional process P *, so that the primary key K is determined partly in dependence on the input data X: K = P * K, ( K *, X)

This provides additional cryptographic protection. In addition, this offers the possibility to execute the additional process P * only if certain input data are offered. That is, the additional process P * may include a test of the 5 input data X and the execution of the additional process P * may depend on the result of that test. For example, the additional process P * can only be performed if the last two bits of the input data X are equal to zero. The effect of such an input data-dependent operation is that the correct primary key K will be produced only for certain input data X, so that only those input data yield the desired output data Y. It will be clear that this further enhances cryptographic security.

Fig. 4 schematically shows the manner in which sub-steps of processes P and P * can be performed alternately ("interleaving") in order to further increase the protection against attacks. The sub-steps 20 can comprise so-called "rounds", as is the case, for example, with DES. Preferably, however, the sub-steps comprise only one or a few instructions from a program with which the processes are executed.

In a first step 101, a first sub-step Pj ^ 25 of the process P is performed. Then, in a second step 102, the first sub-step Px * of the additional process P * is performed. Likewise, in a third step 103, the second sub-step P2 of the process P is carried out, etc. This continues until, in step 110, the last sub-step Pn * of 30, the additional process P * is performed, assuming for the example that the processes P and P * comprise the same number of sub-steps. If not, the last corresponding sub-step is performed in step 110, and the remaining sub-steps are performed in further steps.

By alternating the sub-steps of the process P known per se and the process P * (possibly also known per se) a series of sub-steps can be obtained which does not correspond to that of a known process. This makes the nature of the process more difficult to recognize.

The cryptographic process schematically shown in Fig. 5 comprises a number of steps S (Sx, S2, .....). In each stage S, (right) data RD is applied to a cryptographic operation F. This cryptographic operation may itself comprise a number of sub-steps, such as an expansion, a combination with a key, a substitution and a permutation. The cryptographic operation F provides processed data RD ', which in a combination operation CC (CCX, CC2, ...., the index always indicates the relevant stage S) with left data LD are combined into modified (left) data LD ', which, like the original right hand data RD, are passed to the next stage.

As shown in Fig. 5, at the end of each stage S, the modified left data LD 'and the right data RD change position to form the right data RD and the left data LD of the next stage, respectively.

The left data LD and the right data RD are derived from input data X in a preliminary operation PP and may undergo a preliminary permutation.

The final stage output data constitutes the processed data Y of the method, optionally after it has undergone final processing, such as an output permutation PP'1.

In accordance with the invention, the data present in and between the stages are masked with auxiliary values. Thus, in each stage, for example the stage S2, there is an additional combination operation AC which combines the right hand data RD with an (primary) auxiliary value A before this data is supplied to the cryptographic operation F. A further combination operation BC is inserted between the cryptographic operation F and the combination operation CC for the purpose of combining the processed (right) data RD 'with a further (secondary) auxiliary value B with 1011544 11. Preferably, all combination operations are exclusive-of-operations.

Combining the data LD and RD with auxiliary values A and B results in the modified data LD 'being masked, making it considerably more difficult to retrieve the original data LD and RD from the masked data LD'.

In accordance with a further aspect of the invention, the auxiliary values A and B are related. The second auxiliary value B is preferably formed by means of an exclusive-or-operation from the first auxiliary value A of the previous stage and the auxiliary value A of the following stage:

Bi = Aw Θ Ai + ,.

As a result, each auxiliary value A which is combined with the right-hand data RD by means of a further additional combination operation BC as part of the further auxiliary value B, is each time compensated before the data are subjected to the operation F. The auxiliary value A does, however, work through in the modified data LD ', so that these remain masked between two stages.

Advantageously, the first stage S precedes preparatory combination operations EC and DC, which respectively form the right data RD, and the left data LD, of the first stage S, with reference to the primary auxiliary value A, respectively. the first stage and a primary auxiliary value A0. These combination operations are preferably also exclusive or operations. In that case, the combination operation AC has the effect of removing the auxiliary value A from the right hand data RD before it is presented to the operation F. In the right data RD, which will form the left data LD2 as a result of the crossover in the second stage S2, the auxiliary value A, and thus the masking of the data, is retained.

The second data SD, of the first stage S, are masked with the additional auxiliary value A0. By combining 1011544 12 with the auxiliary value Bx = A0 Θ A2, the initial auxiliary value A0 is removed (due to A0 ® A0 = 0), but the auxiliary value A2 and the masking achieved therewith are retained. The auxiliary value A0 is preferably chosen equal to Ax in this embodiment.

In order to remove the auxiliary values before the final operation (PP "1), final combination operations FC and GC are provided, which modify the modified left data LD'n of the last stage Sn with an auxiliary value 10A -1 + the right data RDn, respectively. with an auxiliary value A '. This makes it possible to carry out the method such that, despite the use of the auxiliary values A, the end dates Y are equal to those which would have been obtained with the conventional method.

Although preferably all auxiliary values Ai are chosen differently, with the exception of A0 = Alf, it is possible to choose all auxiliary values A ± equally. In that case, all secondary auxiliary values in the illustrated embodiment are equal to zero, so that the further combination operations BC can be omitted.

In the process of Fig. 6, which largely corresponds to that of Fig. 5, the combining operations AC and BC and the cryptographic operation F are integrated into a combined operation F '. Integration of the combination operations is possible, for example, by appropriately adjusting a substitution table of the operation F. Therefore, the additional combination operations AC and BC can be omitted. In principle, for each stage Si, a different combined operation Fi is required, in which different auxiliary values Aa are integrated (see Fig. 5). Only if the auxiliary values Ai are chosen equal, i.e. Ax = A2 = .... = A „, the combined operations FA can be the same.

The embodiment of fig. 7 largely corresponds to that of fig. 6. In addition to Fig. 6, in each stage S, with the exception of the last stage Sn, a combination operation HC is included which contains the right hand data RD

1011544 13 with a tertiary auxiliary value W. Preferably the teriary auxiliary value is equal to the exclusive or combination of the auxiliary values A0 and Ax: W = A0 Θ Ax.

The result is that the operation HC always adds the auxiliary value A0 and compensates the auxiliary value Ax. This allows all cryptographic operations F to be essentially identical, which requires a much smaller processing and / or storage capacity of a processor system with which the method is performed. It will be understood that in the embodiment of FIG. 7 the operations F "are adjustments of the original operations F such that they are corrected for the auxiliary value Ax and additionally combine the auxiliary value A0 15 with their result. In other words, if RD Θ Ax is applied to F", the result is equal to F "(RD) 0 W. ___________

Fig. 8 schematically shows a circuit 10 for carrying out the method according to the invention. The circuit 10 comprises a first memory 11, a second memory 12 and a processor 13, the memories 11 and 12 and the processor 13 being coupled by means of a data bus 14. By providing two memories, it is possible in each case to perform a sub-step of one of the processes P and P * (see Fig. 4), to store the result of that sub-step in, for example, the first memory 11, and from the second memory 12 to transfer a previous intermediate result of the other process to the processor 13. In this way it is possible to efficiently perform alternating calculation of sub-steps of two different processes.

The payment system schematically shown in Fig. 9 comprises an electronic payment means 1 and a payment station 2. The electronic payment means 1 is, for example, a so-called "smart card", ie a card which is an integrated circuit for storing and processing payment data to provide. The payment station 2 comprises a card reader 21 and a processor circuit 22. The processor circuit 22 may correspond to the circuit 10 of Fig. 5.

At the beginning of a transaction, the payment means 1 transfers an identification (card identification) ID to the payment station 2. On the basis of this identification, the payment station 2 determines a key that will be used for this transaction. This identification ID can be applied as input data X (see Figures 1-3) to a cryptographic process which produces an identification-dependent transaction key KID as output data Y on the basis of a master key MK. According to the invention, the process shown in Figs. 2 and 3 is used for this purpose, in which the master key MK has previously been converted into an additional master key MK * by means of a process R. This additional master key MK * is now fed, preferably together with the identification ID according to FIG. 3, to the additional process P * in order to reproduce the original master key MK and derive the transaction key KID from the identification ID.

Although a single additional process P * is always shown in Figures 2 and 3, multiple processes P *, P **, P ***, ... can be used in series and / or parallel 25 to convert the primary key K to distract.

It will be clear to those skilled in the art that many modifications and additions are possible without departing from the scope of the invention.

1011544

Claims (20)

Method for cryptographically processing data, comprising supplying values, i.e. the data (X) and a key (K), to a cryptographic process (P), and executing the process (P) to cryptographically form processed data (Y), characterized by adding auxiliary values (K *; A, B) to the process (P) to mask the values (K; D) used in the process (P). ....._ The method of claim 1, wherein an auxiliary value 10 includes an additional key (K *) that is supplied to an additional process (P *) to form the key (K). Method according to claim 2, wherein the additional process (P *) comprises a cryptographic process to which an auxiliary key (K ') is applied. The method of claim 2 or 3, wherein the additional process (P *) is an invertible process. A method according to claim 2, 3 or 4, wherein the data (X) is also supplied to the additional process (P *). The method of claim 5, wherein the additional process (P *) is performed only if the data (X) has predetermined properties. A method according to any one of claims 2-6, wherein the process (P) and the additional process (P *) are each composed of a number of steps, and in which steps of the process (P) and the additional process (P) alternate *) are carried out. Method according to any of the preceding claims, wherein the process (P) comprises a number of stages (S), each with a cryptographic operation (F) for processing the right-hand data (RD) derived from the data (X) and a combination operation (C) for combining the processed 1011544 right data (RD ') with left data (LD) also derived from data 35 (X) to form modified left data (LD'), and wherein the right data (RD) , prior to operation F, are combined with a primary auxiliary value (A). The method of claim 8, wherein the processed right data (RD ') following processing F is combined with a secondary auxiliary value (B). 10. Method according to claims 8 and 9, wherein the secondary auxiliary value (B) of a stage is formed from the combination of the primary auxiliary value (A) of the previous stage and the primary auxiliary value (A) of the next stage. The method of claim 8 or 10, wherein, prior to the first stage (S1), the right data (RD) with the primary auxiliary value (Ax) of the first stage (SJ and the left data (LD) with an additional auxiliary value (A0) is combined. 12. A method according to claim 11, wherein, immediately after the last stage (Sn), the right data (RDn) with the primary auxiliary value (A ') of the last stage and the modified left data (LD') with a further additional auxiliary value (A ^) are combined. A method according to any of claims 8-12, wherein all primary auxiliary values (A) are equal. A method according to any one of claims 9-13, wherein the primary auxiliary values (A) and / or secondary auxiliary values (B) are each pre-combined with the respective operation (F). 15. A method according to any one of claims 8-14, wherein the combining is performed by an exclusive-or-operation. The method according to any of the preceding claims, wherein the data (X) comprises identification data of a payment means (1) and the processed data (Y) forms a diversified key. A method according to any preceding claim, wherein the process comprises (P) DES, preferably triple DES. 1011544 Circuit (10) for performing the method according to any of the preceding claims. Payment card (1), provided with a circuit (10) according to claim 17. Payment terminal (2), provided with a circuit according to claim 18. 1011544