WO1998038767A1

WO1998038767A1 - Method and arrangement for computer assisted formation of a permutation to permute digital signals and method and arrangement to encrypt digital signals

Info

Publication number: WO1998038767A1
Application number: PCT/DE1998/000537
Authority: WO
Inventors: Franz Pichler; Josef Scharinger; Dieter SCHÜTT
Original assignee: Siemens Aktiengesellschaft
Priority date: 1997-02-26
Filing date: 1998-02-23
Publication date: 1998-09-03
Also published as: EP0963634A1; JP2001513213A

Abstract

The invention relates to a method for generating permutations, wherein a pre-definable key is used to form a permutation in order to break down a pre-definable matrix into several sub-matrices (Spj). The individual lines or columns of the sub-matrices are imaged clearly with their results representing sub-permutations. The sub-permutations are combined with the permutation. According to the inventive method, the sub-permutations are used to form a permutation, said sub-permutations being formed by taking a pre-definable key, preferably a secret key, into consideration when a symmetrical encryption method is involved. Cryptographic security of the encryption method is thus improved in such a way that crypto analysis using conventional methods is much more complicated or even impossible.

Description

description

Method and arrangement for computer-aided formation of a permutation for the permutation of digital signals and method and arrangement for the encryption of digital signals

In cryptography, the permutation of input signals to a permuted output signal plays an important role.

The so-called Data Encryption Standard (DES) is known from [1] and [6]. As part of the DES, the input signals are subjected to both permutations and substitutions. The method is carried out in several iterations with the aim of encrypting the text, i.e. to find the result of the application of the DES method to the input signals, which is so complex that it cannot be broken by a computer of today's computing power.

The so-called P-Boxes of the DES method, with which the permutation of the input signals to intermediate signals is carried out, is fixed in each case.

This means that, for example, a so-called differential crypto analysis method is suitable for increasing the chances of unauthorized decryption, i.e. to prevent unauthorized breaking of the encrypted text.

Basics of so-called Walsh matrices are described in [2].

Fundamentals of what is known as boot algebra are known from document [3]. Further basics about permutations and their applications in cryptography are described in the document [4].

An arrangement for generating Walsh matrices is described in document [5].

The invention is based on the problem of specifying a method for the computer-assisted formation of a permutation and a method for encrypting digital signals and arrangements for carrying out the method with which the cryptographic security of permutations and thus also the cryptographic security of encryption methods in which permutations are used , is significantly increased.

The problem is solved by the method according to claim 1, by the method according to claim 2 and by the arrangement according to claim 12.

In the method according to claim 1, a predeterminable matrix is divided into several depending on a predefinable key

Disassembled partial matrices. Rows or columns of the partial matrices are subjected to a clear mapping, the result of the mapping representing partial permutations. The partial permutations are linked to the permutation.

In the method according to claim 2 for the encryption of digital signals, at least one permutation is used in the context of the encryption, which is formed according to the following regulation. A predeterminable matrix is broken down into several sub-matrices depending on a predefinable key. Rows or columns of the submatrices are subjected to a clear mapping, the results of which represent partial permutations. The partial permutations are linked to the permutation. The digital signals are encrypted at least using permutation. The arrangement according to claim 12 is designed such that the method steps are carried out according to claim 1 and claim 2. For this purpose, an arithmetic unit is provided for carrying out the individual method steps.

The procedure described above clearly means that a permutation is formed taking into account a predefinable key. This additional degree of flexibility enables a significant cryptographic security gain for the permutation formed and thus an increased degree of security of the encrypted data when the method is used in cryptography.

Advantageous developments of the invention result from the dependent claims.

In order to further increase the cryptographic security, it is advantageous to use a matrix as a starting point for the decomposition, which matrix has approximately the same number of elements with values of a first binary value and elements with values of a second binary value.

This above-mentioned effect of increasing the cryptographic security is further increased by using a Walsh matrix.

In order to simplify the method, it is further provided in a further development to realize the unambiguous mapping simply by sorting the rows or columns according to the increasing or decreasing order of values which result from a binary number of the respective row or column.

Even if in the further exemplary embodiment only the matrix is broken down into sub-matrices according to columns of the matrix. follows, however, a breakdown of the matrix into rows is also easily possible.

The use of a Walsh matrix as a matrix described below is also in no way to be understood as restricting. In general, any matrix can be used in this context.

The size of the matrix is also basically arbitrary.

The arrangement can be both a common computer, i.e. be a conventional data processing system, which is designed by programming such that the above-described methods can be carried out. The arrangement can also be implemented by a digital electronic circuit.

In the figures, an embodiment of the invention is shown, which is explained in more detail below.

Show it

Figure 1 shows a Walsh matrix with an indicated decomposition of the Walsh matrix into 4 sub-matrices;

Figure 2 is a sketch of two computer units with which the

Procedures are carried out; Figures 3a to 3e individual partial permutations Pi and the

Permutation P;

FIGS. 4a to 4e the inverse partial permutations Pj; " ¹ to the partial permutations Pi and the inverse permutation P"¹;

Figure 5 is a sketch of a realization of the arrangement with a digital electronic circuit.

2 shows a first computer unit C1 with a processor unit P and a second computer unit C2 also with a processor unit P. The two computer units are connected to one another via a transmission medium UM in such a way that data can be exchanged between the computer units C1, C2. In the first computer unit C1, digital data D to be encrypted is encrypted using at least one permutation, which is determined in a manner described below. The encrypted data VD are transmitted via the transmission medium UM to the second computer unit C2 and there decrypted the original data D using at least one of the permutations inverse to the permutation described below.

When using a symmetrical encryption method, it is further provided that the secret key is exchanged before the encrypted data is transmitted. Any method for exchanging cryptographic keys can be used for this.

As described above, the encryption is carried out using at least one permutation, which is formed in the following way.

The Walsh matrix WM of size 16x16 in dyadic order shown in FIG. 1 is used as the starting point for forming the permutation. The Walsh matrix WM only has elements that have either a first binary value "1" or a second binary value "0".

Furthermore, a predefinable key S, preferably the secret key, is used for encrypting the data in a symmetrical encryption method in the course of the further method.

In this case, the key S has the following structure:

S = (3, 4, 7, 2).

The key S, which is also referred to below as a boot decomposition, is used as a permutation key. In this case, the key S is used to define a breakdown of the specified matrix into four tracks Spl, Sp2, Sp3, Sp4 (TracesT. A track Spl, Sp2, Sp3, Sp4 is to be understood as a set of columns of the Walsh matrix WM, whereby the number of columns in a track Spl, Sp2, Sp3, Sp4 is determined by a value of the key S in each case.

For the Walsh matrix WM shown in FIG. 2, the use of the key S means that a first track Spl has the first three columns, a first column S1, a second column S2, and a third column S3 of the Walsh matrix WM .

A second track Sp2 has four columns, a fourth column S4, a fifth column S5, a sixth column S6 and a seventh column S7 of the Walsh matrix WM.

A third track Sp3 contains, according to the key S, seven columns, an eighth column S8, a ninth column S9, a tenth column S10, an eleventh column S11, a twelfth column S12, a 13th column S13 and a 14th column S14 of the Walsh - Matrix WM.

A fourth column Sp4 contains two columns, a 15th column S15 and a 16th column S16 of the Walsh matrix WM.

Each track Spl, Sp2, Sp3, Sp4 corresponds to a partial permutation Pi, a concatenation of the four partial permutations PI, P2, P3, P4 in this case results in the permutation P, which is clearly determined by the specified boot decomposition taking into account the key S.

In Fig. 1, the individual lines of the Walsh matrix WM are clearly identified by a growing numerical value from 1 to 16.

Each track Spj, where j is an index to designate the respective track, the respective line number is always assigned a numerical value, whereby the most significant digit is assumed on the left. The numerical value is derived from ^{^} representing binary numbers of the respective elements of the corresponding row in the track Spj.

If the line numbers are sorted according to these numerical values, a reordering is associated with this, which determines the corresponding partial permutation Pi for each track Spj. Since it can happen that different line numbers of a track Spj are assigned the same numerical value, these conflicts are preferably alternated according to a FIFO strategy (Eirst-In-Eirst-o.ut) or LIFO strategy (ast-In- £ irst -Q_ut), resolved.

The individual partial permutations Pi and the permutation P are shown in FIGS. 3a to 3e.

3a shows a two-line table with 16 columns, which represent the individual lines of the Walsh matrix WM or the resulting line specification for the respective track Spj.

The top line of the table shows the individual line numbers of the Walsh matrix WM for the first partial permutation PI, which results from the first track Spl, successively from 1 to 16.

In the second line of the table, the respective line number of the track SPj is given, which results from the re-sorting of the lines within the first track Spl according to falling numerical values.

In this case, the FIFO principle is used to resolve the conflicts of the same numerical values for different line numbers, i.e. the line number that was previously a lower value than the one in conflict with its line

Line number remains in front of the other line number. For the first partial permutation PI, a 1: 1 mapping results, which results from the dyadic order of the Walsh matrix WM and the FIFO strategy used, since the first three-digit binary values are in any case arranged in order of decreasing order. The first partial permutation PI thus results as an identical image of the first track SP1.

However, this changes in a second partial permutation P2, which is shown in FIG. 3b.

The second partial permutation P2 is formed taking into account the second track Sp2 (cf. FIG. 3b).

The second line of FIG. 3b again shows the new line numbers which result from the rearrangement within the second track Sp2, but this time using the LIFO principle. In this context, the LIFO principle means that the order of conflicting lines is simply reversed. This is already evident in lines 1 and 2, which are reversed by using the LIFO strategy. For example, the first line 1 and the second line 2 of the second track SP2 of the Walsh Matrix WM both have the binary value “1111”. However, the LIFO strategy makes the order of the first line 1 and the second line 2 in the second partial permutation P2 vice versa, which is shown in Figure 3. The 13th line 13 and the 14th line 14 of the second track SP2 of the Walsh Matrix WM both have the binary value "1100". As a result, these lines are re-sorted to the new, permuted "position" 11 or 12.

Here, too, the LIFO principle becomes clear again, since the 14th line 14 is sorted to position 11 and the 13th line 13 to position 12.

The third partial permutation P3 results, taking into account the third track Sp3, again in the manner described above (cf. FIG. 3c). The fourth partial permutation P4 again takes into account the ^{^} fourth track Sp4 in the manner described above (cf. FIG. 3d).

The individual partial permutations are linked to form the permutation P. The permutation P is shown in Fig. 3e. In this context, concatenation means that the value of the new line number of the respective partial mutation PI, P2, P3 is selected as the initial value of the line number in the next partial permutation P2, P3, P4.

Furthermore, the resulting permuted line number for two line numbers is explained based on the specified starting line number.

Line number 9 is retained after the first partial permutation PI has been carried out. In the second partial permutation P2, a new line number 12 results for the line number 9. For the new line number 12, the permuted line number 6 results in the third partial permutation P3. For the line number 6, the value of the line number results in the fourth partial permutation P4 2. The overall result of the concatenation is shown in FIG. 3e, that is to say the tuple of the initial line number 9 and the associated permuted line number 2.

For the initial value 4, the value 4 results again after the first partial permutation PI. After the second partial permutation P2, the value for line number 4 results in the new one

Line number 7. For the third partial permutation P3, a new value of the line number 2 results for the value of the line number 7. In the fourth partial permutation P4, a new line number 16 results for the value of the line number 2. This is again shown in FIG. 3e the pair of values (2, 16) of the second column of the table in Fig. 3e. In this way, the permutation P is formed, which has increased cryptographic security compared to known permutations, since in this case the dynamic, preferably secret, key S is used to form the respective permutation P.

Inverting each partial permutation Pi gives inverse partial permutations Pi ^"1 .

If one links these partial permutations Pi ^-1 , of course in reverse order, an inverse permutation P ^"1 to the permutation P is determined.

The individual inverse partial permutations P ^_1 and the inverse permutation P ^-1 are shown in FIGS. 4a to 4e.

In Fig. ^{4a, "the} fourth permutation P4 ¹ simply the inverse fourth Teilpermutation P4 by rearranging and ^re-sorting" is for a fourth inverse Teilpermutation P4 ¹ shown.

In FIG. 4b, the third is for the in Fig. 3c shown Teilpermutation P3 inverse Teilpermutation P3 shown ^-1.

4c shows the inverse second partial permutation P2 ^{"" 1} resulting from the second partial permutation P2.

FIG. 4d describes an inverse first partial permutation Pi ^"1 resulting from the first partial permutation PI.

In Fig. 4e, the resulting inverse permutation P ^{-1 is shown} in a value table that summarizes a concatenation of the four inverse partial permutations.

For the concrete cases described above of the original line number with the value 9 and the resulting permuted line number with the value 2, the value of the line number 2 results in the fourth inverse partial permutation P4 ^"1 for the value of the line number 2 the value 4 resulting from the fourth inverse partial permutation P4 ^"1 results in the value 12 in the third inverse partial permutation P3" ^1. The value 12 results in the value 12 in the second inverse partial permutation P2 ^-1 . In the first inverse partial permutation Pi ^"1 , which also represents a 1: 1 mapping when it is inverted, results in the value of the line number 9 for the line number 9. Thus, for the inverse permutation P" ^1, a mapping of an original permuted value 2 again results in the original Value of line number 9. This is indicated in Figure 4e in the pair of values (2,9).

For the example of the permuted value 16, the following new line number results after the individual partial permutations:

- After the fourth inverse partial permutation P4 ^"1 for the value 16, the new value 2;

- after the third inverse partial permutation P3 ^"1 for the value 2 the new value 7; - after the second partial permutation P2 ^-1 for the value 7 the new value 4;

- after the first inverse partial permutation Pi ^-1 for the value 4, the new value 4.

This is shown in Fig. 4e in the tupple of the last column of the value table (16, 4).

If the matrix WM used is known both in the first computer unit C1 and in the second computer unit C2 and the type of unambiguous mapping used in each case, then it is only necessary to send the key S used to form the permutation P from the first computer unit C1 to transmit the second computer unit C2.

The method can be arranged, for example, by a computer unit, for example the first computer unit C1 and / or the second computer unit C2 can be implemented. With conventional computers, it is only necessary to implement the above-described regulations for forming the permutation in a computer program with which the steps of constructing the permutation P are implemented.

Furthermore, it is also possible to implement the arrangement by means of a digital electronic circuit, as shown in FIG. 5.

A possible arrangement for generating Walsh matrices WM is described in document [5].

Individual tracks Spj can be masked out by setting the binary counter accordingly in a start or stop position. The order of the binary numbers thus obtained, i.e. the numerical values assigned to the individual lines of the tracks Spj are provided by a specially designed switching mechanism SW which outputs the corresponding numerical value in binary form.

A generator G for generating Walsh matrices WM is shown in FIG. 5. A number i to be permuted as well as the number of columns of the respective track Spj are fed to the generator G in each case. The generator G is connected to the switching mechanism SW, with which the permutation P of the number i is carried out. A permuted number P (i) is output from the arrangement.

Some variants of the exemplary embodiment described above are explained below.

It is not necessary to carry out the individual lines of a track Spj according to falling or increasing binary values which are assigned to the individual lines. Any unique mapping can be used within the scope of this invention. Any matrix can also be used in this process.

Furthermore, it is provided to provide a symmetrical encryption method for the encryption method, with the symmetrical encryption method not only using permutations but also, for example, so-called substitutions.

The invention can clearly be seen in the fact that it is proposed to use permutations which are formed as a function of a predefinable key.

The following publications have been cited in this document:

[1] A. S. Tannenbaum, Computer Networks, Wolframs Fachverlag, 2nd edition, ISBN 3-925328-79-3, pp. 610-618, 1992

[2] F. Pichler, Analog Scrambling by a general fast Fourier Transform, Springer Lecture Notes in Computer Science, No. 149, Berlin, ISBN 0-387-11993-0, 1982, pp. 173 - 178

[3] D. Schutt et al, Boot AIgebras, Int. Computer Science Institute, TR-92-039, pp. 1-32, June 1992

[4] N. Sloane, Encrypting by Random Rotations, Mathematics and Statistics Research Center, Bell Laboratories, Springer Lecture Notes in Computer Science, No. 149, Berlin, ISBN 0-387-11993-0, 1982, pp. 71 - 128

[5] F. Pichler, Mathematical Systems Theory, Berlin, ISBN 3 110 039095, p. 191, 1975

[6] US 5,008,935

Claims

claims

1. Method for computer-aided formation of a permutation for the permutation of digital signals, a) in which a predeterminable matrix (WM) is broken down into a plurality of sub-matrices (Spj) depending on a predefinable key (S), b) in the rows or columns of the sub-matrices ( Spj) are subjected to a clear mapping, the results of which represent partial permutations (Pi), and c) in which the partial permutations (Pi) are linked to form the permutation (P).

2. Method for encrypting digital signals, a) in which a permutation (P) is formed according to the following rule:

- a predefinable matrix (WM) is broken down into several sub-matrices (Spj) depending on a predefinable key (S), - rows or columns of the sub-matrices (Spj) are subjected to a clear mapping, the results of which represent partial permutations (Pi),

- The partial permutations (Pi) will be linked to the permutation (P), and b) in which the encryption of the digital signals takes place at least using the permutation (P).

3. The method of claim 1 or 2, wherein the matrix has only binary values.

4. The method of claim 3, wherein the matrix has approximately the same number of elements with a first binary value and elements with a second binary value.

5. The method according to claim 4, in which a Walsh matrix is used as the matrix.

6. The method according to any one of claims 1 to 5, wherein the matrix is disassembled after boot disassembly.

7. The method according to any one of claims 1 to 6, in which as an illustration the rows or columns are sorted according to the increasing or decreasing order of numerical values that result from a binary number that is assigned to a set of rows or columns.

8. The method according to any one of claims 1 to 7, wherein the linkage of the partial permutations (Pi) takes place in the form of a concatenation of the partial permutations (Pi).

9. The method according to any one of claims 2 to 8, in which a symmetrical encryption method is used for encrypting data.

10. The method according to claim 9, wherein the key (S) is the secret key of the symmetric encryption method.

11. The method according to any one of claims 2 to 10, in which additional encryption methods substitutions of the digital signals are carried out.

12. Arrangement for forming a permutation for the permutation of digital signals, with a processor unit which is set up in such a way that a) a predeterminable matrix (WM) is broken down into a plurality of sub-matrices (Spj) depending on a predefinable key (S), b) lines or columns of the partial matrices (Spj) are subjected to a clear mapping, the results of which represent partial permutations (Pi), and c) the partial permutations (Pi) are linked to form the permutation (P).

13. arrangement for encryption of digital signals, with a processor unit which is set up in such a way that a) a permutation (P) is formed according to the following rule:

- A predefinable matrix (WM) is broken down into several sub-matrices (Spj) depending on a predefinable key (S), - Rows or columns of the sub-matrices (Spj) are subjected to a clear mapping, the results of which represent partial permutations (Pi) ,

- The partial permutations (Pi) will be linked to the permutation (P), and b) the encryption of the digital signals takes place at least using the permutation (P).

14. Arrangement according to claim 12 or 13, in which the processor unit is set up in such a way that the matrix has only binary values.

15. The arrangement according to claim 14, wherein the processor unit is set up such that the matrix has approximately the same number of elements with a first binary value and elements with a second binary value.

16. The arrangement according to claim 15, wherein the processor unit is set up such that a Walsh matrix is used as the matrix.

17. Arrangement according to one of claims 12 to 16, in which the processor unit is set up in such a way that the matrix is disassembled after boot disassembly.

18. Arrangement according to one of claims 12 to 17, in which the processor unit is set up in such a way that the rows or columns are sorted as an image according to the increasing or decreasing order of numerical values which result from a binary number representing a set of rows or columns.

19. Arrangement according to one of claims 12 to 18, in which the processor unit is set up in such a way that the partial permutations (Pi) are linked in the form of a concatenation of the partial permutations (Pi).

20. Arrangement according to one of claims 13 to 19, in which the processor unit is set up in such a way that a symmetrical encryption method is used for encrypting data.

21. The arrangement as claimed in claim 20, in which the processor unit is set up in such a way that the key (S) is the secret key of the symmetrical encryption method.

22. Arrangement according to one of claims 13 to 21, in which the processor unit is set up in such a way that additional encryption methods are used to substitute the digital signals.