Chuẩn mã DỮ liệU

CHUẨN MÃ DỮ LIỆU

1. 
   MỞ ĐẦU.
   

2. 
   MÔ TẢ DES
   

Mô tả đầy đủ của DES được nêu trong Công bố số 46 về các chuẩn xử lý thông tin Liên bang (Mỹ) vào 15.1.1977. DES mã hoá một xâu bít x của bẳn rõ độ dài 64 bằng một khoá 54 bít. Bản mã nhậ được cũng là một xâu bít có độ dài 48. Trước hết ta mô tả ở mức cao của hệ thống.

1.Với bản rõ cho trước x, một xâu bít x₀ sẽ được xây dựng bằng cách hoán vị các bít của x theo phép hoán vị cố định ban đầu IP. Ta viết:x₀= IP(X) = L₀R₀, trong đó L₀ gồm 32 bít đầu và R₀ là 32 bít cuối.

2. Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính L_iR_i, 1  i 16 theo quy tắc sau:

L_i = R_i-1

R_i = L_i-1  f(R_i-1,K_i)

trong đó  kí hiệu phép hoặc loại trừ của hai xâu bít (cộng theo modulo 2). f là một hàm mà ta sẽ mô tả ở sau, còn K₁,K₂, . . . ,K₁₆ là các xâu bít độ dài 48 được tính như hàm của khoá K. ( trên thực tế mỗi K_i là một phép chọn hoán vị bít trong K). K₁, . . ., K₁₆ sẽ tạo thành bảng khoá. Một vòng của phép mã hoá được mô tả trên hình 3.1.

3. Áp dụng phép hoán vị ngược IP ^-1 cho xâu bít R₁₆L₁₆, ta thu được bản mã y. Tức là y=IP ^-1 (R₁₆L₁₆). Hãy chú ý thứ tự đã đảo của L₁₆ và R₁₆.
Hình 3.1. Một vong của DES

Hàm f có hai biến vào: biến thứ nhất A là xâu bít độ dài 32, biến thứ hai J là một xâu bít độ dài 48. Đầu ra của f là một xâu bít độ dài 32. Các bước sau được thực hiện:

1. Biến thứ nhất A được mở rộng thành một xâu bít độ dài 48 theo một hàm mở rộng cố định E. E(A) gồm 32 bít của A (được hoán vị theo cách cố định) với 16 bít xuất hiện hai lần.

2. Tính E(A)  J và viết kết quả thành một chuỗi 8 xâu 6 bít = B₁B₂B₃B₄B₅B₆B₇B₈.

3.Bước tiếp theo dùng 8 bảng S₁, S₂, ... ,S₈ ( được gọi là các hộp S ). Với mỗi S_i là một bảng 416 cố định có các hàng là các số nguyên từ 0 đến 15. Với xâu bít có độ dài 6 (Kí hiệu B_i = b₁b₂b₃b₄b₅b₆), ta tính S_j(B_j) như sau: Hai bít b₁b₆ xác định biểu diễn nhị phân của hàng r của S_j ( 0  r  3) và bốn bít (b₂b₃b₄b₅) xác định biểu diễn nhị phân của cột c của S_j ( 0  c  15 ). Khi đó S_j(B_j) sẽ xác định phần tử S_j(r,c); phần tử này viết dưới dạng nhị phân là một xâu bít có độ dài 4. ( Bởi vậy, mỗi S_j có thể được coi là một hàm mã mà đầu vào là một xâu bít có độ dài 2 và một xâu bít có độ dài 4, còn đầu ra là một xâu bít có độ dài 4). Bằng cách tương tự tính các C_j = S_j(B_j), 1  j  8.

4. Xâu bít C = C₁C₂... C₈ có độ dài 32 được hoán vị theo phép hoán vị cố định P. Xâu kết quả là P(C) được xác định là f(A,J).

Hàm f được mô tả trong hình 3.2. Chủ yếu nó gômg một phép thế ( sử dụng hộp S ), tiếp sau đó là phép hoán vị P. 16 phép lặp của f sẽ tạo nên một hệ mật tích nêu như ở phần 2.5.
Hình 3.2. Hàm f của DES

Trong phần còn lại của mục này, ta sẽ mô tả hàm cụ thể được dùng trong DES. Phép hoán vị ban đầu IP như sau:

IP

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 31 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

Bảng này có nghĩa là bít thứ 58 của x là bít đầu tiên của IP(x); bít thứ 50 của x là bít thứ hai của IP(x), .v.v . . .

IP -1

40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

Hàm mở rộng E được xác đinh theo bảng sau:

Bảng chọn E bít

32 1 2 3 4 5 4 5 6 7 8 9 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 25 26 27 28 29 28 29 30 31 32 1

Tám hộp S là:

Và phép hoán vị P có dạng:

P

16 7 20 29 12 28 1 15 23 5 18 31 32 27 3 19 13 30 22 11 4

Cuối cung ta cần mô tả việc tính toán bảng khoá từ khoá K. Trên thực tế, K là một xâu bít độ dài 64, trong đó 56 bít là khoá và 8 bít để kiểm tra tính chẵn lẻ nhằm phát hiện sai. Các bít ở các vị trí 8,16, . . ., 64 được xác định sao cho mỗi byte chứa một số lẻ các số "1". Bởi vậy một sai sót đơn lẻ có thể phát hiện được trong mỗi nhóm 8 bít. Các bít kiểm tra bị bỏ qua trong quá trình tính toán bảng khoá.

1. 
   Với một khoá K 64 bít cho trước, ta loại bỏ các bít kiểm tra tính chẵn lẻ và hoán vị các bít còn lại của K theo phép hoán vị cố định PC-1. Ta viết:
   

PC-1(K) = C₀D₀

2. 
   Với i thay đổi từ 1 đến 16:
   
3. 
   
   

D_i = LS_i(Di-1)

PC-1

57 49 41 33 25 17 1 58 50 42 34 26 10 2 59 51 43 35 19 11 3 60 52 44 63 55 47 39 31 23 7 62 54 46 38 30 14 6 61 53 45 37 21 13 5 28 20 12

PC-2

14 17 11 24 1 5 3 28 15 6 21 10 23 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

Bây giờ ta sẽ đưa ra bảng khoá kết quả. Như đã nói ở trên, mỗi vòng sử dụng một khoá 48 bít gồm 48 bít nằm trong K. Các phần tử trong các bảng dưới đây biểu thị các bít trong K trong các vòng khoá khác nhau.

Vòng 1

10 51 34 60 49 17 35 57 2 9 19 42 3 35 26 25 44 58 59 1 36 27 18 41 22 28 39 54 37 4 47 30 5 53 23 29 61 21 38 63 15 20 45 14 13 62 55 31

Vòng 2

2 43 26 52 41 9 25 49 59 1 11 34 60 27 18 17 36 50 51 58 57 19 10 33 14 20 31 46 29 63 39 22 28 45 15 21 53 13 30 55 7 12 37 6 5 54 47 23

Vòng 3

51 27 10 36 25 58 9 33 43 50 60 18 44 11 2 1 49 34 35 42 41 3 59 17 61 4 15 30 13 47 23 6 12 29 62 5 37 28 14 39 54 63 21 53 20 38 31 7

Vòng 4

35 11 59 49 9 42 58 17 27 34 44 2 57 60 51 50 33 18 19 26 25 52 43 1 45 55 62 14 28 31 7 53 63 13 46 20 21 12 61 23 38 47 5 37 4 22 15 54

Vòng 5

19 60 43 33 58 26 42 1 11 18 57 51 41 44 35 34 17 2 3 10 9 36 27 50 29 39 46 61 12 15 54 37 47 28 30 4 .5 63 45 7 22 31 20 21 55 6 62 38

Vòng 6

3 44 27 17 42 10 26 50 60 2 41 35 25 57 19 18 1 51 52 59 58 49 11 34 13 23 30 45 63 62 38 21 31 12 14 55 20 47 29 54 6 15 4 5 39 53 46 22

Vòng 7

52 57 11 1 26 59 10 34 44 51 25 19 9 41 3 2 50 35 36 43 42 33 60 18 28 7 14 29 47 46 22 5 15 63 61 39 4 31 13 38 53 62 55 20 23 38 30 6

Vòng 8

36 41 60 50 10 43 59 18 57 35 9 3 58 25 5251 34 19 49 27 26 17 44 2 12 54 61 13 31 30 6 20 62 47 45 23 55 15 28 22 37 46 39 4 721 14 53

Vòng 9

57 33 52 42 2 35 51 10 49 27 1 60 50 17 44 43 26 11 41 19 18 9 36 59 4 46 53 5 23 22 61 12 54 39 37 15 47 7 20 14 29 38 31 63 62 13 6 45

Vòng 10

41 17 36 26 51 19 35 59 33 11 50 44 34 1 57 27 10 60 25 3 2 58 49 43 55 30 37 20 7 6 45 63 38 23 21 62 31 54 4 61 13 22 15 47 46 28 53 29

Vòng 11

25 1 49 10 35 3 19 43 17 60 34 57 18 50 41 11 59 44 9 52 51 42 33 27 39 14 21 4 54 53 29 47 22 7 5 46 15 38 55 45 28 6 62 31 30 12 37 13

Vòng 12

9 50 33 59 19 52 3 27 1 44 18 41 2 34 25 60 43 57 58 36 35 26 17 11 23 61 5 55 38 37 13 31 6 54 20 30 62 22 39 29 12 53 46 15 14 63 21 28

Vòng 13

58 34 17 43 3 36 52 11 50 57 2 25 51 18 9 44 27 41 42 49 19 10 1 60 7 45 20 39 22 21 28 15 53 38 4 14 46 6 23 13 63 37 30 62 61 47 5 12

Vòng 14

42 18 1 27 52 49 36 60 34 41 51 9 35 2 58 57 11 25 26 33 3 59 50 44 54 29 4 23 6 5 12 62 37 22 55 61 30 53 7 28 47 21 14 46 45 31 20 63

Vòng 15

26 2 50 11 36 33 49 44 18 25 35 58 19 51 42 41 60 9 10 17 52 43 34 57 38 13 55 7 53 20 63 46 21 6 39 45 14 37 54 12 31 5 61 30 29 15 4 47

Vòng 16

18 59 42 3 57 25 41 36 10 17 27 50 11 43 34 33 52 1 2 9 44 35 26 49 30 5 47 62 45 12 55 58 13 61 31 37 6 27 46 4 23 28 53 22 21 7 62 39

Phép giải mã được thực hiện nhờ dùng cùng thuật toán như phép mã nếu đầu vào là y nhưng dùng bảng khoá theo thứ tự ngược lại K₁₆,...K₁. Đầu ra của thuật toán sẽ là bản rõ x.

Sau đây là một ví dụ về phép mã DES. Giả sử ta mã bản rõ (ở dạng mã hexa - hệ đếm 16):

0 1 2 3 4 5 6 7 8 9 A B C D E F

Bằng cách dùng khoá

1 2 3 4 5 7 7 9 9 B B C D F F 1

Khoá ở dạng nhị phân ( không chứa các bít kiểm tra) là:

L0 = 1100110000000000110010011111111 L1 =R0 = 11110000101010101111000010101010

Sau đó thực hiện 16 vòng của phép mã như sau:

E(R0) = 011110100001010101010101011110100001010101010101 K1 = 000110110000001011101111111111000111000001110010 E(R0)  K1 = 011000010001011110111010100001100110010100100111 S-box outputs 01011100100000101011010110010111 f(R0,K1) = 00100011010010101010100110111011 L2 = R1 = 11101111010010100110010101000100

E(R1) = 011101011110101001010100001100001010101000001001 K2 = 011110011010111011011001110110111100100111100101 E(R1) K2 = 000011000100010010001101111010110110001111101100 S-box outputs 11111000110100000011101010101110 f(R1,K2) = 00111100101010111000011110100011 L3 = R2 = 11001100000000010111011100001001

E(R2) = 111001011000000000000010101110101110100001010011 K3 = 010101011111110010001010010000101100111110011001 E(R2) K3 = 101100000111110010001000111110000010011111001010 S-box outputs 00100111000100001110000101101111 f(R2,K3) = 01001101000101100110111010110000 L4 =R3 = 10100010010111000000101111110100

E(R3) =01010000010000101111100000000101011111111010100 K4 = 011100101010110111010110110110110011010100011101 E(R3) K4 = 001000101110111100101110110111100100101010110100 S-box outputs 00100001111011011001111100111010 f(R3,K4) = 10111011001000110111011101001100 L5 = R4 = 01110111001000100000000001000101

E(R4) = 101110101110100100000100000000000000001000001010 K5 = 011111001110110000000111111010110101001110101000 E(R4)  K5 = 110001100000010100000011111010110101000110100010 S-box outputs 01010000110010000011000111101011 f(R4,K5) = 00101000000100111010110111000011 L6 = R5 = 10001010010011111010011000110111

E(R5) = 110001010100001001011111110100001100000110101111 K6 = 011000111010010100111110010100000111101100101111 E(R5)  K6 =101001101110011101100001100000001011101010000000 S-box outputs 01000001111100110100110000111101 f(R5,K6) = 10011110010001011100110100101100 L7 = R6 = 11101001011001111100110101101001

E(R6) = 111101010010101100001111111001011010101101010011 K7 = 111011001000010010110111111101100001100010111100 E(R6)  K7 = 000110011010111110111000000100111011001111101111 S- box outputs 00010000011101010100000010101101 f(R6,K7) = 10001100000001010001110000100111 L8 = R7 = 00000110010010101011101000010000

E(R7) = 000000001100001001010101010111110100000010100000 K8 = 111101111000101000111010110000010011101111111011 E(R7)  K8 = 111101110100100001101111100111100111101101011011 S-box outputs 01101100000110000111110010101110 f(R7,K8) = 00111100000011101000011011111001 L9 = R8 = 11010101011010010100101110010000

E(R8) = 011010101010101101010010101001010111110010100001 K9 = 111000001101101111101011111011011110011110000001 E(R8)  K9 = 100010100111000010111001010010001001101100100000 S-box outputs 00010001000011000101011101110111 f(R8,K9) = 00100010001101100111110001101010 L10 = R9 = 00100100011111001100011001111010

E(R9) = 000100001000001111111001011000001100001111110100 K10 = 101100011111001101000111101110100100011001001111 E(R9)  K10 = 101000010111000010111110110110101000010110111011 S-box outputs 11011010000001000101001001110101 f(R9,K10) = 01100010101111001001110000100010 L11 = R10 = 10110111110101011101011110110010

E(R10) = 010110101111111010101011111010101111110110100101 K11 = 001000010101111111010011110111101101001110000110 E(R10)  K11 = 011110111010000101111000001101000010111000100011 S-box outputs 01110011000001011101000100000001 f(R10,K11) = 11100001000001001111101000000010 L12 = R11 = 11000101011110000011110001111000

E(R11) = 011000001010101111110000000111111000001111110001 K12 = 011101010111000111110101100101000110011111101001 E(R11)  K12 = 000101011101101000000101100010111110010000011000 S-box outputs 01110011000001011101000100000001 f(R11,K12) = 11000010011010001100111111101010 L13 = R12 = 01110101101111010001100001011000

E(R12) = 001110101011110111111010100011110000001011110000 K13 = 100101111100010111010001111110101011101001000001 E(R12)  K13 = 101011010111100000101011011101011011100010110001 Sbox outputs 10011010110100011000101101001111 f(R12,K13) = 11011101101110110010100100100010 L14 = R13 = 00011000110000110001010101011010

E(R13) = 000011110001011000000110100010101010101011110100 K13 = 010111110100001110110111111100101110011100111010 E(R13)  K14 = 010100000101010110110001011110000100110111001110 S-box outputs 01100100011110011001101011110001 f(R13,K14) = 10110111001100011000111001010101 L15 = R14 = 11000010100011001001011000001101

E(R14) = 111000000101010001011001010010101100000001011011 K15 = 101111111001000110001101001111010011111100001010 E(R14)  K15 = 010111111100010111010100011101111111111101010001 S-box outputs 10110010111010001000110100111100 f(R14,K15) = 01011011100000010010011101101110 R15 = 01000011010000100011001000110100

E(R15) = 001000000110101000000100000110100100000110101000 K16 = 110010110011110110001011000011100001011111110101 E(R15)  K16 = 111010110101011110001111000101000101011001011101 S-box outputs 10100111100000110010010000101001 f(R15,K16) = 11001000110000000100111110011000 R16 = 00001010010011001101100110010101

Cuối cùng áp dụng IP^-1 vào L₁₆,R₁₆ ta nhận được bản mã hexa là:

3. 
   
   Каталог: files -> FileMonHoc
   FileMonHoc -> NGÂn hàng câu hỏi lập trình cơ BẢn nhóm câu hỏI 2 ĐIỂM
   FileMonHoc -> CHƯƠng 2 giới thiệu về LÝ thuyết số
   FileMonHoc -> CÁc hệ MẬt khoá CÔng khai kháC
   FileMonHoc -> BỘ MÔn duyệt chủ nhiệm Bộ môn
   FileMonHoc -> Khoa công nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
   FileMonHoc -> Chủ nhiệm Bộ môn Ngô Thành Long ĐỀ CƯƠng chi tiết bài giảNG
   FileMonHoc -> Chủ nhiệm Bộ môn Phan Nguyên Hải ĐỀ CƯƠng chi tiết bài giảNG
   FileMonHoc -> Khoa: CÔng nghệ thông tin cộng hòa xã HỘi chủ nghĩa việt nam
   FileMonHoc -> MẬt mã khóA ĐỐi xứng lý thuyết cơ bản của Shannon
   FileMonHoc -> Khoa công nghệ thông tin bài giảng LẬp trình cơ BẢn biên soạn
   
   
   
   tải về 0.52 Mb.
   
   Chia sẻ với bạn bè của bạn: