Detailed explanation and code of Go-Des and 3Des algorithmsYou can check the warehouse Readme document or Go-package management (management tool comparison and use of go mod) to install

table of Contents

Des

Development history

Design Ideas of Block Cipher Algorithm

Des overview

Initial replacement and inverse replacement

Feistel structure

Round function F

E extension

Key plus

S box replacement

P permutation

Key arrangement

3Des

Pros and cons

Grouping mode

CBC

CFB

OFB

Des' Go implementation

Plaintext padding

encryption

Decrypt

Screenshot of the result

reference


Des

Development history

  • In May 1973, the U.S. Federal Government put forward a proposal for soliciting cryptographic algorithms to protect computer data during data transmission and storage ;
  • In March 1975, the National Bureau of Standards (NBS) announced for the first time the Lucifer algorithm proposed by IBM;
  • In January 1977, NBS officially announced to the public that it adopted the solution designed by IBM as the Data Encryption Standard for non-confidential data . DES officially became the US federal government information processing standard, namely the FIPS-46 standard, which began in July of the same year. Take effect.
  • Since then, the National Security Agency (NSA) of the United States will make a new assessment of DES every five years and re-examine whether it will continue to be a federal encryption standard.

Design Ideas of Block Cipher Algorithm

  1. If the cryptosystem is not idempotent (F2+F), then multiple iterations may improve the security of the cryptosystem.
  2. The advantages of using an iterative structure: software and hardware implementation saves code (hardware) resources.
  3. Confusion: The relationship between plaintext/key and ciphertext is complicated.
  4. Diffusion: Every bit of the plaintext/key affects every bit of the ciphertext.

Des overview

  • Plaintext and ciphertext packet length is 64 bits
  • The algorithm consists of two parts: iterative encryption and decryption and key arrangement
  • Feistel structure (similar to encryption and decryption): encryption and decryption are identical except for the key arrangement
  • Key length: 56 bits (the key space of DES:
2^{56}

), after every 7 bits, there is a parity bit (the 8th bit), a total of 64 bits

  • The round function uses a combination of chaos and diffusion , a total of 16 rounds

the whole frame

The initial permutation (IP) of the plaintext is performed, the key is split into 16 keys through the key arrangement algorithm, 16 rounds of iteration are performed, and the ciphertext is finally obtained through inverse permutation.

Initial replacement and inverse replacement

The input 64-bit data block is recombined bit by bit, and the output is divided into two parts, L0 and R0, each part is 32 bits long.

58

50

42

34

26

18

10

2

60

52

44

36

28

20

12

4

62

54

46

38

30

twenty two

14

6

64

56

48

40

32

twenty four

16

8

57

49

41

33

25

17

9

1

59

51

43

35

27

19

11

3

61

53

45

37

29

twenty one

13

5

63

55

47

39

31

twenty three

15

7

The number in the table represents the position of the data at this position in the new data in the original data , that is, the 58th digit of the original data block is placed in the first digit of the new data, the 50th digit is placed in the second digit, and so on. The data after replacement is divided into two parts, L0 and R0.

Inverse permutation is to return to the original position. For example, if the 1 position is at the 40 position, then the first inverse permutation is 40, so I won’t draw them one by one.

40...
......

Since the initial replacement is public, it has no cryptographic meaning. Many DES implementations have been removed, and some people think it was to better put it in the DES chip at that time.

Feistel structure

One round of iteration

Perform 16 iterations according to the following rules, 1≤i≤16

L_i=R_i
R_i=L_{i-1}\bigoplus f(R_{i-1},K_i)

Round function F

F(

R_{i-1}

,

K_i

) takes a 32-bit string

R_{i-1}

as the first input and a 48-bit string

K_i

as the second input to generate an output with a length of 32 bits .

E extension

32

1

2

3

4

5

4

5

6

7

8

9

8

9

10

11

12

13

12

13

14

15

16

17

16

17

18

19

20

twenty one

20

twenty one

twenty two

twenty three

twenty four

25

twenty four

25

26

27

28

29

28

29

30

31

32

1

Will be

R_{i-1}

expanded to 48 bits , the left and right columns of data are expanded data, and the expanded data is one bit taken from the adjacent position, which can be understood as a circular queue. The bit close to 32 bits is 1, the bit close to 1 bit is 32, and the rest is the beginning of the next line or the end of the previous line.

Key plus

The

R_{i-1}

E-expansion and

K_i

XOR

S box replacement

Using 8 S boxes S1...S8, each Si is a fixed 4*16 order matrix , and its elements are integers between 0-15.
Given a bit string of length 6, such as Bj=b1b2b3b4b5b6 , Sj(Bj) is calculated as follows:

  1. The two bits b1b6 determine the binary representation of row r of Sj (0≤r≤3),
  2. The four bits b2b3b4b5 determine the binary representation of column c of Sj (0≤c≤15),
  3. Sj (Bj) is defined as a length of four values of the bit string of Sj (R & lt, C) . From this, it can be calculated that Cj=Sj(Bj) , 1≤j≤8.

S box 1 is as follows:

14

4

13

1

2

15

11

8

3

10

6

12

5

9

0

7

0

15

7

4

14

2

13

1

10

6

12

11

9

5

3

8

4

1

14

8

13

6

2

11

15

12

9

7

3

10

5

0

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

I will not paste the others, they are all public and can be found on the Internet. This is just to give an example.

Suppose, the input Bj of S1 is 110011

  1. b1b6 is 11, r=3
  2. b2b3b4b5 is 1001, c=9
  3. S1(3,9) is 11, binary is 1011, Cj is 11, that is, 11011 is replaced by 1011.

P permutation

The P box is as follows:

16

7

20

twenty one

29

12

28

17

1

15

twenty three

26

5

18

31

10

2

8

twenty four

14

32

27

3

9

19

13

30

6

twenty two

11

4

25

The length is a 32-bit string C=C1C2C3C4C5C6C7C8. Replace according to the above. The principle is the same as the previous IP. It is to put the original data in the P box according to how many bits, the first one is the 16th bit of C, and so on, and the last combination is That's it, no more examples.

Key arrangement

The previous is iterative encryption and decryption. Next, let’s talk about the key arrangement. The key arrangement is to obtain the key ki of each round through the key K. The process is as follows

Given a 64-bit key K, process K according to the fixed permutation PC-1 to obtain PC-1(K)=C0D0, where C0 and D0 are composed of the first and last 28 bits, respectively . The following is PC-1. Note that it does not include 8, 16, 24, 32, 40, 48, 56 and 64. As mentioned earlier, these are check digits.

57

49

41

33

25

17

9

1

58

50

42

34

26

18

10

2

59

51

43

35

27

19

11

3

60

52

44

36

63

55

47

39

31

twenty three

15

7

62

54

46

38

30

twenty two

14

6

61

53

45

37

29

twenty one

13

5

28

20

12

4

Calculate Ci=LSi(Ci-1) and Di=LS(Di-1), and Ki=PC-2(CiDi), LSi means to rotate two or one position to the left, specifically, if i=1, 2, 9, 16, move one position , otherwise, move two positions. PC-2 is another fixed replacement. Below is PC-2

14

17

11

twenty four

1

5

3

28

15

6

twenty one

10

twenty three

19

12

4

26

8

16

7

27

20

13

2

41

52

31

37

47

55

30

40

51

45

33

48

44

49

39

56

34

53

46

42

50

36

29

32

The above is the process of obtaining Ki in one round. Each round selects different 48 bits of the key K for PC-2 replacement. It is also 16 matrices with the same length and width as PC-2, so I won’t paste it here, otherwise the article is too Long.

3Des

3DES, as the name suggests, uses the triple DES algorithm and has two modes.

DES-EEE3 mode: use P->DES encryption->DES encryption->DES encryption->C for encryption, use C->DES decryption->DES decryption->DES decryption->P for decryption.

DES-EDE3 mode: use P->DES encryption->DES decryption->DES encryption->C for encryption, use C->DES decryption->DES encryption->DES decryption->P for decryption.

Pros and cons

advantage:

  • The key length is increased to 112 or 168 bits, which overcomes the exhaustive attacks faced by DES.
  • Compared with DES, the algorithm complexity is enhanced and the security is improved.
  • Since DES has been used on a large scale, upgrading to 3DES is much less expensive than updating the new algorithm.
  • The analysis time of DES is much longer than any other encryption algorithm. Accordingly, 3DES has stronger anti-analysis ability.

insufficient:

  • The speed of 3DES is slower.
  • Although the length of the key has increased, the length of the plaintext block has not changed, which does not match the increase in the length of the key.

Grouping mode

When the block cipher is encrypted, the length of the plaintext block is fixed, but the data volume of the message to be encrypted in practical applications is uncertain, and the data format is various. In order to be able to use DES in various applications, the United States defines 4 operating modes of DES in FIPS PUS 74 and 81:
ECB, CBC, CFB, OFB. The block cipher mode describes how to repeatedly encrypt multiple long data. Piece.

ECB and CBC are block modes, and CFB and OFB are stream modes. The security of ECB is relatively poor, so I won't learn it first, and it's not in the Go package.

CBC

In CBC (Cipher Block Chaining, cipher block chaining) mode, each block must be XORed with the encrypted data of the previous block , and then encrypted .

encryption:

C_i=E(P_i\oplus C_{i-1},K)

Decryption:

P_i=D(C_i,K) \oplus C_{i-1}
  • IV: initialization vector, initial vector,
  • Divide the long message into blocks, if the last block is less than the packet length, it needs to be filled
  • Encryption and decryption process call encryption algorithm and decryption algorithm respectively
  • Existence of ciphertext expansion (expansion brought by plaintext filling and expansion of IV transmission )
  • Ciphertext block for an order one by one to decrypt
  • There is error propagation (only the next piece of ciphertext is propagated)
  • Suitable for long data encryption larger than one packet length

CFB

The CFB (Cipher Feedback) mode is similar to the CBC mode. The ciphertext of the previous group is encrypted and the plaintext of the current group is XORed to generate the ciphertext of the current group.

encryption:

C_i=E(C_{i-1},K)\oplus P_i

Decryption:

P_i=E(C_{i-1},K) \oplus C_i

Note that the decryption function is consistent with the encryption function .

  • The message is encrypted as a bit stream without packet padding
  • Only the encryption algorithm is called during the encryption and decryption process
  • Existence of ciphertext extension (extension of IV transmission )
  • The ciphertext blocks need to be decrypted one by one in order
  • There is error propagation (only the next few blocks are propagated)
  • Suitable for long data encryption larger than one packet length
  • Can be used for self-synchronizing serial ciphers

OFB

The OFB (Output Feedback) mode is similar to the CFB mode, except that the cipher sequence of the previous block is used to encrypt the cipher sequence of the current block.

to sum up

  • ECB is the fastest and simplest block cipher mode, but its security is the weakest. It is generally not recommended to use ECB to encrypt messages, but if it is to encrypt random data, such as keys, ECB is the best choice.
  • CBC is suitable for file encryption and will not cause synchronization failure when there are a few errors. It is the best choice for software encryption.
  • CFB is usually the mode selected for the encrypted packet sequence, it can also tolerate a small amount of error expansion, and has a synchronization recovery function. It is recommended to use CTR mode instead.
  • OFB is a mode selected in an extremely error-prone environment, but requires a high-speed synchronization mechanism. It is recommended to use CTR mode instead.

Let's talk about CTR mode when learning AES.

Well, none of the above is useful, because DES has been cracked! ! ! (The little friends who see this sentence are almost crying) However, the enhanced version can still be used, and then let's talk about 3DES.

Des' Go implementation

We are not using the Go language to implement Des, it has been written by a great god, and we will call it.

des bag

func NewCipher(key []byte) (cipher.Block, error)

Create and return a cipher.Block interface that uses the DES algorithm.

cipher package

func NewCBCEncrypter(b Block, iv []byte) BlockMode

Return a BlockMode interface in cipher block chaining mode with the bottom layer encrypted with b. The length of the initial vector iv must be equal to the block size of b.

BlockMode method

CryptBlocks(dst, src []byte)

Encrypt or decrypt consecutive data blocks, the size of src must be an integer multiple of the block size, src and dst can point to the same memory address

func NewCBCDecrypter(b Block, iv []byte) BlockMode

Return a BlockMode interface in cipher block link mode and decrypted by b at the bottom layer. The initial vector iv must be the same as the iv used during encryption.

Plaintext padding

CBC mode needs padding. After decryption, we also need to remove the padding. Since there is no requirement for padding, we will pad the missing length so that it is easy to slice when the padding is removed.

func PaddingLastGroup(plainText []byte,blockSize int) []byte{	padNum := blockSize - len(plainText)%blockSize	char := []byte{byte(padNum)}	newPlain := bytes.Repeat(char,padNum)	plainText = append(plainText,newPlain...)	return plainText}
func UnpaddingLastGroup(plainText []byte) []byte {	length := len(plainText)	number := int(plainText[length-1])	return plainText[:length-number]}

encryption

  • Use des.NewCipher to get the block
  • Fill in plaintext
  • Use cipher.NewCBCEncrypter to generate CBC mode blocks
  • Use the CryptBlocks of the mode block for encryption. Since it can point to the same memory address, we still use the same variable to save memory
func DesEncrypt(plainText,iv, key []byte) ([]byte,error) {	if len(iv) != 8{		_, file, line, _ := runtime.Caller(0)		return nil,util.Error(file,line+1,errors.IvError)	}	block, err :=des.NewCipher(key)	if err != nil{		_, file, line, _ := runtime.Caller(0)		return nil,util.Error(file,line+1,errors.DesKeyError)	}	// padding plainText	newText := util.PaddingLastGroup(plainText,des.BlockSize)	// Create a CBC interface	blockMode := cipher.NewCBCEncrypter(block,iv)	// use same one to save space	blockMode.CryptBlocks(newText,newText)	return newText,nil}

Decrypt

  • Use des.NewCipher to get the block
  • Use cipher.NewCBCDecrypter to generate CBC mode blocks
  • Use CryptBlocks of the mode block for decryption
  • Remove plaintext padding
func DesDecrypt(cipherText,iv,key []byte) ([]byte,error) {	if len(iv) != 8{		_, file, line, _ := runtime.Caller(0)		return nil,util.Error(file,line+1,errors.IvError)	}	block, err :=des.NewCipher(key)	if err != nil{		_, file, line, _ := runtime.Caller(0)		return nil,util.Error(file,line+1,errors.DesKeyError)	}	// Create a CBC interface	blockMode := cipher.NewCBCDecrypter(block,iv)	plainText := make([]byte,len(cipherText))	blockMode.CryptBlocks(plainText,cipherText)	return util.UnpaddingLastGroup(plainText),nil}

Part of the test code

        iv := []byte("12345678")	key := []byte("ladykill")	plainText := []byte("hellocrypto")	cipherText,err := DesEncrypt(plainText,iv,key)	if err != nil{		fmt.Println(err)		os.Exit(0)	}	fmt.Printf("加密后:%s\n",string(cipherText))	decryText,_ := DesDecrypt(cipherText,iv,key)	fmt.Printf("解密后:%s\n",string(decryText))

Screenshot of the result

3Des only needs to use des.NewTripleDESCipher(key) when creating it.

I put the code on gitee: https://gitee.com/frankyu365/gocrypto

You can check the warehouse Readme document or Go-package management (management tool comparison and use of go mod) to install

reference

"Modern Cryptography Tutorial Gu Lize, Yang Yixian, etc."

Go standard library-crypto/des

Go standard library-crypto/cipher

More Go related content: Go-Golang study summary notes

If you have any questions, please comment below, please indicate the source for reprinting, and attach a link to the original text, thank you! If there is any infringement, please contact in time. If you feel that you have gained something and volunteer to give a reward, you can choose Alipay 18833895206 (less than). Your support is my motivation for constant updates.