IDEA algorithm for finding high-scoring C# version

Basic concepts of 1 and IDEA

2. Conceptual design principles

3, the idea of encryption process

4.IDEA decryption process

three

Idea (international data encryption algorithm) is an encryption algorithm proposed by James Massey, Xuejia Lai and others in Switzerland, which belongs to a kind of block cipher in cryptography.

IDEA uses a key with the length of 128bit, and the data block size is 64bit. Theoretically speaking, IDEA is a "strong" encryption algorithm, so far there is no effective attack algorithm against this algorithm.

The basic concept of 1 idea

four

As early as 1990, Xue Jialai and others put forward the proposed encryption standard (PES) at EuroCrypt'90. At EuroCrypt'9 1 Annual Meeting, Lai Xuejia and others put forward the revised version of PES (IPES). At present, IPES has been commercialized and renamed IDEA. IDEA has been patented by Ascom, Switzerland, and you must apply for permission to use the IDEA algorithm for commercial purposes.

Basic concepts of ideas

five

IDEA is a block cipher algorithm with a block length of 64 bits and a key length of 128 bits (stronger than DES). The same algorithm can be used for encryption and decryption.

IDEA can resist differential analysis and correlation analysis;

IDEA seems to have no weak bond in the sense of DES;

IDEA's "confusion" and "diffusion" design principles come from three kinds of operations, which are easy to realize (fast encryption) in software and hardware.

Basic concepts of ideas

six

XOR operation ()

Integer module 2 16 plus (+)

Integer modulo 2 16+ 1 degree () (the idea of S-box)

Diffusion is provided by the basic building block of an algorithm called MA structure.

Second generation

F 1

G 1

G2 Esports e-sports club

Conceptual operation

seven

Matters needing attention in implementation

Use subpackage: 16bit subpackage;

Use simple operations (easy to add, shift, etc. )

The encryption and decryption processes are similar;

Rule structure (for VLSI implementation).

Conceptual operation

eight

2. Conceptual design principles

1 the strength of the password: it is mainly achieved through confusion and diffusion.

Confusion implementation method:

(1) Bitwise XOR. expressed as

(2) Modular integer addition, expressed as, whose input and output are

16 unsigned integer processing.

Modular integer multiplication, expressed as, whose input and output are divided by 16.

All zeros are treated as 16 unsigned integers.

nine

take for example

0000000000000000⊙ 1000000000000000

= 100000000000000 1

This is because 216× 215mod (216+1) = 215+1.

Conceptual design principle

Table 3.6 shows the operation tables of three operations when the operand is 2 bits long. These three operations are incompatible in the following sense:

① Any two of the three operations do not satisfy the distribution law, such as a+(b⊙c)≦(a+b)⊙(a+c).

② Any two of the three operations do not satisfy the associative law, such as a +(b? c)?(a+b)？ c

Conceptual design principle

1 1

The combination of three operations can provide complex transformation for the input of the algorithm, which makes the cryptanalysis of IDEA more difficult than DES which only uses XOR operation.

Diffusion in the algorithm is realized by a basic unit called multiply/add (MA) structure (see Figure 4. 14).

The input of this structure is two 16 bit sub-segments and two 16 bit sub-keys, and the output is also two 16 bit sub-segments. This structure has been repeatedly used in the algorithm for 8 times, and a very effective diffusion effect has been obtained.

Conceptual design principle

The diffusion of IDEA algorithm is mainly realized by multiplying and adding the basic units of the structure.

Conceptual structure

Overall scheme of ideological encryption

Second cycle

Eighth cycle

Loop 1

Output conversion

64-bit ciphertext

64-bit plaintext

Z 1

Z 12

Z43

Z48

Z49

Z52

Subkey generator

128-bit key

Z 1

Z52

IDEA encryption overall scheme diagram

Idea encryption process

Round 1

64-bit plaintext

X 1

Second round

W 1 1

W 12

W 13

W 14

Round 8

W7 1

W72

W73

W74

W2 1

W22

W23

W24

W8 1

W82

W83

W84

Output conversion

Y 1

ciphertext

…

Z 1

…

Z 12

…

Z43

Z48

…

Z49

Z52

Keyword generator

128-bit key

Z 1

Z52

The encryption process (as shown in Figure 4. 15) consists of eight consecutive iterations and one output conversion. The algorithm divides the 64-bit plaintext into four 16 sub-segments, and each iteration takes four 16 sub-segments as input, and the output is also four 16 sub-segments. The final output conversion also produces four sub-segments of 16 bits, which are concatenated to form a 64-bit ciphertext packet. Each iteration needs 6 subkeys with 16 bits, and the final output conversion needs 4 subkeys with 16 bits, so the total number of subkeys is 52. Figure 4. The right half of15 shows the sub-key generator that generates 52 sub-keys from the initial 128-bit key.

3. Idea encryption process

Fig. 4. 16 is the schematic diagram of the structure of 1 wheel of IDEA, and the subsequent rounds are also of this structure, except that the subkeys and wheel inputs used are different. As can be seen from the structure diagram, IDEA is not the traditional Feistel cipher structure. At the beginning of each round, there is a change. The input of the transformation is four sub-segments and four sub-keys. The operations in the conversion are twice multiplication and twice addition. The four output sub-segments are XOR-operated to form two sub-segments with 16 bits as the input of MA structure. The MA structure also has two input subkeys, and the output is two 16 subsegments.

Concept wheel structure

Wheel structure of IDEA wheel 1

Y 1

1 wheel structure

Finally, the four output subsections of the transformation are XOR-operated with two output subsections of MA structure to generate four output subsections of this round. Note that W 12 and W 13 are formed after the output subsection generated by X2 and the output subsection generated by X3 are exchanged, in order to further increase the confusion effect and make the algorithm more resistant to differential cryptanalysis.

Idea encryption process

2 1

In each round, the order of execution is as follows:

1.X 1 times the first subitem.

2. X2 and the second subkey are added.

3. X3 and the third subkey are added.

4.X4 and the fourth subkey are multiplied.

5. Distinguish the results of step 1 and step 3.

6. Compare the results of step 2 and step 4.

IDEA, the encryption order of each round.

7. Multiply the result of step 5 by the fifth subkey.

8. Add the results of steps 6 and 7.

9. Multiply the result of step 8 by the sixth subkey.

10. Add the results of steps 7 and 9.

1 1. Differentiate the result of step 1 and step 9 or.

12. Compare the results of step 3 and step 9.

13. Distinguish the results of step 2 and step 10 or.

14. Differentiate the results of step 4 and step 10 or.

IDEA, the encryption order of each round.

The ninth step of the algorithm is output conversion, as shown in Figure 4. 17. Its structure is the same as the transformation structure at the beginning of each round, but the difference is that the second and third inputs of the output transformation have been switched first, so as to cancel the exchange of two subsections in the eighth round of output. It should also be noted that only 4 subkeys are needed in step 9, and 6 subkeys are needed in each of the first 8 rounds.

IDEA, the encryption order of each round.

The output transformation of ideas

In the encryption process, 52 subkeys of 16 bits are generated from the encryption key of 128 bits, as follows: the first 8 subkeys Z 1, Z2, ..., and Z8 are directly taken from the encryption key, that is, Z 1kloc-0/6 bits (most significant bit). Then the encryption key is circularly shifted to the left by 25 bits, and then the next eight subkeys Z9, Z 10, …, Z 16 are taken, which are the same as Z 1, Z2, …, Z8. Repeat this process until all 52 subkeys are generated.

Generation of IDEA subitem

The method of generating subkeys. The algorithm uses 52 subkeys (6 subkeys in each of 8 rounds, and the other 4 subkeys are used for output conversion). First, the 128-bit key is divided into eight 16-bit keys. These are the first batch of 8 subkeys of the algorithm (6 in the first round and 2 in the second round). Then, the key moves 25 bits to the left ring to generate another 8 subkeys, and so on until the end of the algorithm.

4. Decryption process of ideas

Encryption and decryption are essentially the same, but different keys are used;

The decryption key is obtained from the encryption subkey in the following ways:

The first four subkeys of decryption cycle I are derived from the first four subkeys of encryption cycle 10-I; The 1 and the fourth subkey of the decryption key correspond to the multiplication inverse of the 1 and the fourth encryption subkey; 2,3 corresponds to the addition inverse of 2,3;

For the first eight cycles, the last two subkeys of cycle I are equal to the last two subkeys of encryption cycle 9-I;

Decryption and encryption processes are basically the same, but the keys used are different. The decryption key is generated as follows.

(1)I(I = 1, 2, ... 9) rounds of decryption are obtained from the first four subkeys of (10-i) rounds of encryption. 1 and the fourth decryption subkey are used as the modular multiplication inverse keys corresponding to the first and fourth encryption subkeys. When the number of rounds is I = 2, the second and third subkeys are the modulo addition and inversion of the corresponding third and second encryption subkeys, ..., 8, and when i= 1 and 9, they are the modulo addition and inversion of the corresponding second and third encryption subkeys.

Decryption process of thought

3 1

(2) The last two subkeys of the i(i= 1, …, 8) round decryption are equal to the last two subkeys of the (9-i) round encryption process.

Decryption process of thought

Encryption process

change

X 1

Z 1..Z4

Zijiami

I 1 1

I 12

I 13

I 14

Z5 Z6

change

W 1 1

W 12

W 13

W 14

Z7..Z 10

Zijiami

I2 1

I22

I23

I24

Z 1 1 Z6 12

W2 1

W22

W23

W24

change

W7 1

W72

W73

W74

Z43..Z46

Zijiami

I8 1

I82

I83

I84

Z47 Z48

change

W8 1

W82

W83

W84

Z49..Z52

Y 1

Round 1

Second round

Round 8

………… ..

change

X 1

U49..U52

Zijiami

V8 1

V82

V83

V84

U47U48

change

J8 1

J82

J83

J84

U43…U46

Zijiami

V7 1

V72

V73

V74

U 1 1U 12

V2 1

V22

V23

V24

change

J2 1

J22

J23

J24

U7…U 10

Zijiami

V 1 1

V 12

V 13

V 14

U5U6

change

J 1 1

J 12

J 13

J 14

U 1…U4

Y 1

Round 8

Second round

Round 1

translate

Round 9

………… ..

Decryption process

Table 3.7 summarizes the above relationship. Where the inverse of Zj's modular multiplication 2 16+ 1 is Z- 1j, which satisfies (see Table 3.7 on page 58).

ZJ⊙Z- 1j = 1 mod(2 16+ 1)

Since 2 16+ 1 is a prime number, every nonzero integer not greater than 2 16 has a unique modular multiplication inverse 2 16+ 1. The addition inverse of the modulo 2 16 of Zj is -Zj, which satisfies:

-Zj + Zj=0 mod (2 16)

Decryption process of thought

The following verification and decryption process can really get the correct result. In Figure 4. 18, the encryption process is on the left, from top to bottom, and the decryption process is on the right, from bottom to top. Each round is further divided into two steps, 1 step is transformation, and the rest is the second step, which is called sub-encryption.

Decryption process of thought

IDEA encryption and decryption block diagram

Now think from the bottom up. For the last output transformation in the encryption process, the following relationship holds:

y 1 = w 8 1⊙Z49 Y2 = W83+Z50

Y3=W82 + Z5 1 Y4=W84⊙Z52

The step 1 round in the decryption process 1 produces the following relationship:

j 1 1 = y 1⊙u 1j 12 = Y2+U2

J 13=Y3 + U3 J 14=Y4⊙U4

Decryption process of thought

The decryption subkey is represented by the encryption subkey, and Y 1, Y2, Y3 and Y4 are substituted into the following relationships, including

j 1 1 = y 1⊙Z- 149 = w 8 1⊙Z49⊙Z- 149 = w 8 1

j 12 = Y2+-Z50 = W83+Z50+-Z50 = W83

j 13 = Y3+-z 5 1 = W82+z 5 1+-z 5 1 = W82

j 14 = Y4⊙Z- 152 = W84⊙Z52⊙Z- 152 = W84

Decryption process of thought

It can be seen that the output of step 1 in the 1 round of the decryption process is equal to the value exchanged between the second subsection and the third subsection in the last step of the encryption process. From Figure 4. 16, the following relationship can be obtained:

W8 1=I8 1？ MAR(I8 1？ I83，I82？ I84)

W82=I83？ MAR(I8 1？ I83，I82？ I84)

W83=I82？ MAL(I8 1？ I83，I82？ I84)

W84=I84？ MAL(I8 1？ I83，I82？ I84)

Decryption process of thought

Among them, when the inputs of MA structure are X and Y, MAR(X, Y) is the right output and MAL(X, Y) is the left output. rule

v 1 1 = j 1 1？ MAR(J 1 1？ J 13，J 12？ J 14)

=W8 1？ MAR(W8 1？ W82，W83？ W84)

=I8 1？ MAR(I8 1？ I83，I82？ I84) MAR [I8 1？ MAR(I8 1？ I83，I82？ I84)？ I83？

MAR(I8 1？ I83，I82？ I84)，I82？

MAL(I8 1？ I83，I82？ I84)？ I84

? MAL(I8 1？ I83，I82？ I84)]

=I8 1？ MAR(I8 1？ I83，I82？ I84)

MAR(I8 1？ I83，I82？ I84) =I8 1

Decryption process of thought

4 1

Similarly, there can be v12 = i83v13 = i82v14 = i84.

Therefore, the output of the second step of the 1 round of the decryption process is equal to the value exchanged between the second subsection and the third subsection in the penultimate input of the encryption process.

In the same way, it can be proved that each step in Figure 4. 18 has the above-mentioned similar relationship, and this relationship has been until.

v 8 1 = I 1 1v 82 = I 13v 83 = I 12v 84 = I 14

That is, the output transformation of the decryption process is exactly the same as the transformation of 1 step 1 of the encryption process, except that the positions of the second subsection and the third subsection are exchanged.

Decryption process of thought

Forty two.

Therefore, the output transformation of the decryption process is exactly the same as the transformation of 1 step 1 of the encryption process, except that the positions of the second segment and the third segment are exchanged.

So we can finally know that the output of the whole decryption process is equal to the input of the whole encryption process.

Decryption process of thought

Characteristics of IDEA block cipher

Variable key length

Mixed management

Cyclic shift of related data

Key correlation cyclic shift

Slave s box

Lengthy key scheduling algorithm

Variable f function and variable plaintext/ciphertext length

Variable period number

Operate on two halves of data in each cycle.

Forty-four

The idea can be easily realized by software and hardware.

① The software adopts 16 bit segmentation processing, and three operations of the algorithm can be realized by using easy-to-program operations such as addition and shift.

(2) Hardware encryption and decryption are similar, the only difference is the use of keys, so they can be realized by the same device. In addition, the regular module structure in the algorithm is beneficial to the implementation of VLSI.

Characteristics of IDEA block cipher

It's over!

idea