Blog Công Nghệ

Nơi chia sẻ kiến thức

Môn An Toàn Và Bảo Mật Thông Tin

by admin
Lượt xem: 47

1. Phương trình Diophantine (Đi ô phan)

Ví dụ giải phương trình diophan 2740x + 1760 = 80

Ta có:  a = 2740, b = 1760, c = 80

  • r1 = 2740
  • r2 = 1760,
  • q = 1 (thương của r1 và r2)
  • r = 980 (chia dư của r1%r2)
  • s1 = 1 (giá trị mặc định)
  • s2 = 0 (giá trị mặc định)
  • s = s1 – q * s2
  • t1 = 0 (giá trị mặc định)
  • t2 = 1 (giá trị mặc định)
  • t =  t1 – q * t2
q r1 r2 r s1 s2 s t1 t2 t
1 2740 1760 980 1 0 1 0 1 -1

Tiếp theo sẽ dời giá trị:

  • r2 xuống r
  • r xuống r2
  • s2 xuống s1
  • s xuống s2
  • t2 xuống t1
  • t xuống t2

Ta được:

q r1 r2 r s1 s2 s t1 t2 t
1 2740 1760 980 1 0 1 0 1 -1
  1760 980   0 1   1 -1  

Tiếp tục thực hiện:

  • r = r1%r2 = 780
  • q = 1
  • s = s1 – q * s2
  • t =  t1 – q * t2
q r1 r2 r s1 s2 s t1 t2 t
1 2740 1760 980 1 0 1 0 1 -1
1 1760 980 780 0 1 -1 1 -1 2

Tiếp tục cho đến khi r2 = 0

q r1 r2 r s1 s2 s t1 t2 t
1 2740 1760 980 1 0 1 0 1 -1
1 1760 980 780 0 1 -1 1 -1 2
1 980 780 200 1 -1 2 -1 2 -3
3 780 200 180 -1 2 -7 2 -3 11
1 200 180 20 2 -7 9 -3 11 -14
9 180 20 0 -7 9 -88 11 -14 137
  20 0   9 -88   -14 137  

Kết quả ta được:

  • s = 9
  • t = -14
  • d = 20

Ta có: x0 = (c/d)*s = (80/20)*9 = 36

          y0 = (c/d)*t = (80/20)*(-14) = -56

Tổng quát: x = x0 + k(b/d) = 36 + 88k

                  y = y0 – k(a/d) = -56 – 137k

2. Mã hóa Affine

Nội dung bài tập: https://mycourses

Mình ví dụ câu a K=(5,10)  => k1 = 5, k2 = 10

Đầu tiên mình chuyển thông điệp về dạng số thứ tự của nó (số phía trên của chữ)

Kí tự  STT
D 3
A 0
I 8
H 7
O 14
C 2

Tiếp theo  mình sẽ nhân với k1 và cộng với k2 ta được C

Kí tự  STT k1 k2 C
D 3     25
A 0     10
I 8 x 5 + 10 50
H 7     45
O 14     80
C 2     20

Tiếp theo chia dư cho 26(kí tự)

Kí tự  STT k1 k2 C   Kq Mod
D 3     25   25
A 0     10   10
I 8 x 5 + 10 50 mod 26 24
H 7     45   19
O 14     80   2
C 2     20   20

Chuyển kí tự đã mod lại thành kí tự mã hóa => đó là thông điệp mã hóa cần tìm

Kí tự  STT k1 k2 C   Kq Mod Kí tự mã hóa
D 3     25   25 Z
A 0     10   10 K
I 8 x 5 + 10 50 mod 26 24 Y
H 7     45   19 T
O 14     80   2 C
C 2     20   20 U

3. Mã hóa Hill

File bài tập ở phần 2

Đầu tiên chuyển thông điệp thành ma trận P có số cột bằng số dòng của k:

Nếu lẻ thêm kí tự vô nghĩa thường là z vào

Sau đó nhân với ma trận K được ma trận kết quả C

Chuyển các kí tự thành chữ cái ta được kết quả mã hóa: V J U Y S L Y D H K O W V J L G Z I B D

4. Giải mã Hill

Đề bài như phần 3

Đầu tiên bạn hãy tìm nghịch đảo của ma trận k

det(k) = 8*4-3*1 = 29 mod 26 = 3  => nghịch đảo nhân của k = 9 = (det(k))-1

A11 = 9 * (-1)(1+1) x 4 = 10    (Nếu ra ngoài phạm vi thì mod)

A12 = 9 * (-1)(1+2) x 1 = -9 mod 26 = 17

A21 = 9 * (-1)(2+1) x 3 = -1 mod 26 = 25

A22 = 9 * (-1)(1+1) x 8 = 20

Giải thích:

  • Màu xanh dương là theo vị trí dòng mấy cột mấy của A
  • Màu đỏ là xóa cột mấy dòng mấy của A ví dụ A12 là xóa cột 1 dòng 2
  • 8 1   => xóa dòng 1 cột 2   => 1
  • 3 4

Đến đây ta được ma trận nghịch đảo k-1 = 10 17 

                                                                    25 20

Lấy C * K-1 được thông điệp trước khi mã hóa

5. Galo Field

Ví dụ bài tập 1: Lập bảng phép tính nhân trong trường GF(23) với đa thức tối giản x3 + x2 + 1

Giải thích: Bạn thấy GF(23) tức là mình sẽ có 2 giá trị là 0 và 1, và sẽ có 23 = 8 phần tử. Đa thức tối giản là khi bị tràn ra khỏi miền giá trị mình sẽ chia dư cho đa thức này. Miền giá trị ở đây là bậc sẽ phải nhỏ hơn số mũ, ví dụ 2 thì bậc < 2(bao gồm 0, 1) , 3 thì bậc < 3 (bao gồm 0, 1, 2). Với bài này bạn thấy mũ của GF là 3 như vậy bậc cao nhất chỉ là 2 nếu vượt ngưỡng bậc này mình phải mod cho đa thức.

⊗ 000 001 010 011 100 101 110 111
000                
001                
010                
011                
100                
101                
110                
111                

Ở dòng 1, 0 nhân với mấy cũng bằng 0.

⊗ 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001                
010                
011                
100                
101                
110                
111                

Tương tự cột 1, 0 nhân với mấy cũng bằng 0

⊗ 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001 000              
010 000              
011 000              
100 000              
101 000              
110 000              
111 000              

Mình sẽ lấy ví dụ tính 010 ⊗ 110 nha.

010 => 0x2 + 1x1 + 0x0 => x

110 => 1x2 + 1x1 + 0x0 => x2 + x

010 ⊗ 110 = x (x2+x) = x3 + x2 ∉ GF(23) do đó chia cho đa thức tối giản

x3 + x2 x3 + x2 + 1
x3 + x2 + 1 1
———————–  
x  

(* Giải thích) x3 ⊕ x3 = 2x3 mod 2 = 0x3

x2 ⊕ x2 = 2x2 mod 2 = 0x2

x => 010

Vậy 010 ⊗ 110 = x = 010

⊗ 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001 000              
010 000           010  
011 000              
100 000              
101 000              
110 000              
111 000              

Ví dụ khác 100 ⊗ 100 nha.

100 => 1x2 + 0x1 + 0x0 => x2

100 ⊗ 100 = (x2 )(x2) = x4  ∉ GF(23) do đó chia cho đa thức tối giản

x4 x3 + x2 + 1
x4 + x3 + x x + 1
———————–  
x3 + x  
x3 + x2 + 1  
———————–  
x2 + x + 1  

x2 + x + 1 => 111

Vậy 100 ⊗ 100 = x2 + x + 1 = 111

⊗ 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001 000              
010 000           010  
011 000              
100 000       111      
101 000              
110 000              
111 000              

Ví dụ bài tập 2: (x5 + x2 +x) ⊗ (x7 + x4 + x3+ x2 + x) trong GF(28) với đa thức tối giản x8 + x4 + x3 + x + 1

(x5 + x2 +x) ⊗ (x7 + x4 + x3+ x2 + x)

= x12 + x9 + x8 + x7 + x6 + x9+ x6 + x5 + x4+ x3 + x8 + x5 + x4 + x3 + x2

= x12 + 0x9 + 0x8 + x7 + 0x6 + 0x5 + 0x4+ 0x3 + x2 (giải thích bên dưới)

= x12 + x7 + x2 ∉ GF(28)

(*) Tại sao ra 2x9 mà lại viết 0x9. Bởi vì giá trị của GF(28) chỉ có 2 giá trị 0 và 1. Mà ở đây là 2x9 do đó phải mod cho cơ số 2 của GF. 2 mod 2 = 0

x12 + x7 + x2 x8 + x4 + x3 + x + 1
x12 + x8 + x7 + x5 + x4 x4 + 1
———————–  
x8 + x5 + x4 + x2   
x8 + x4 + x3 + x + 1  
———————–  
x5 + x3 + x2 + x + 1  

(* Giải thích) x7 ⊕ x7 = 2x7 mod 2 = 0x7. Tương tự cho những cái khác

x5 + x3 + x2 + x + 1 = 00101111

Vậy (x5 + x2 +x) ⊗ (x7 + x4 + x3+ x2 + x) = x5 + x3 + x2 + x + 1 = 00101111

6. Mã hóa DES (Data Encryption Standard)

Đề bài:

Cho chuỗi bản rõ: P= “VINH”

1. Hãy biểu diễn các ký tự trên thành chuỗi 32 bit với mỗi ký tự trong P là 8 bit, và các ký tự trong P thuộc bảng mã ASCII. (có nghĩa là: A có mã thập phân là 65, B là 66, …, Z là 90

2. Hãy mở rộng chuỗi 32 bits của câu 1 thành chuỗi 48 bits khi đi qua hộp hoán vị mở rộng theo phương pháp mã hóa DES

3. Hãy rút gọn chuỗi 48 bits của câu 2 thành chuỗi 32 bits khi đi qua 8 hộp S-Box của phương pháp mã hóa DES

Giải:

Câu 1)

Đầu tiên bạn chuyển các ký tự mã hóa thành hệ số Dec trong bảng mã ascii:

Ký tự Hệ 10
V 86
I 73
N 78
H 72

Tiếp theo chuyển hệ 10 thành hệ nhị phân

Ký tự Hệ 10 Hệ nhị phân
V 86 0101 0110
I 73 0100 1001
N 78 0100 1110
H 72 0100 1000

Ta được: 0101 0110 0100 1001 0100 1110 0100 1000 (đây là 32bit cần tìm)

Câu 2)

Ở dãy trên mình có các cụm gồm 4 số: Mình sẽ tách thành dãy 6 số như sau:

[bit trước] [cụm] [bit sau]

– cụm 1: 0101 0110 0100 1001 0100 1110 0100 1000

  • bit trước: Không có nên lấy bit cuối cùng của dãy là 0
  • cụm: 0101
  • bit sau: 0
  • => 001010

– cụm 2: 0101 0110 0100 1001 0100 1110 0100 1000

  • bit trước: 1
  • cụm:0110
  • bit sau: 0
  • => 101100

– cụm 3: 0101 0110 0100 1001 0100 1110 0100 1000

  • bit trước: 0
  • cụm:0100
  • bit sau: 1
  • => 001001

Tương tự với các cụm khác:

– cụm 4: 0101 0110 0100 1001 0100 1110 0100 1000

– cụm 5: 0101 0110 0100 1001 0100 1110 0100 1000

– cụm 6: 0101 0110 0100 1001 0100 1110 0100 1000

– cụm 7: 0101 0110 0100 1001 0100 1110 0100 1000

– cụm 8: 0101 0110 0100 1001 0100 1110 0100 1000

  • bit trước: 0
  • cụm:1000
  • bit sau: Không có nên lấy bit đầu tiên của dãy là 0
  • => 010000

Kết quả cuối cùng ta được 48 bit: 001010 101100 001001 010010 101001 011100 001001 010000

Câu 3)

Từ 6 bit của mỗi cụm câu 2. Chúng ta sẽ:

  • Tách bit đầu và cuối
  • Tách 4 bit giữa

– cụm 1: 001010

bit đầu-cuối (R) 00 Chuyển sang hệ 10 0 xét dòng 0 cột 5 của bảng S-box1 15 Chuyển sang hệ nhị phân 1111
4 bit giữa (C) 0101 5

(*): Các bảng S-box bạn xem phía dưới bài giải nhé.

– cụm 2: 101100

bit đầu-cuối (R) 10 Chuyển sang hệ 10 2 xét dòng 2 cột 6 của bảng S-box2 13 Chuyển sang hệ nhị phân 1101
4 bit giữa (C) 0110 6

– cụm 3: 001001

bit đầu-cuối (R) 01 Chuyển sang hệ 10 1 xét dòng 1 cột 4 của bảng S-box3 3 Chuyển sang hệ nhị phân 0011
4 bit giữa (C) 0100 4

– cụm 4: 010010

bit đầu-cuối (R) 00 Chuyển sang hệ 10 0 xét dòng 0 cột 9 của bảng S-box4 2 Chuyển sang hệ nhị phân 0010
4 bit giữa (C) 1001 9

– cụm 5: 101001

bit đầu-cuối (R) 11 Chuyển sang hệ 10 3 xét dòng 3 cột 4 của bảng S-box5 1 Chuyển sang hệ nhị phân 0001
4 bit giữa (C) 0100 4

– cụm 6: 011100

bit đầu-cuối (R) 00 Chuyển sang hệ 10 0 xét dòng 0 cột 14 của bảng S-box6 5 Chuyển sang hệ nhị phân 0101
4 bit giữa (C) 1110 14

– cụm 7: 001001

bit đầu-cuối (R) 01 Chuyển sang hệ 10 1 xét dòng 1 cột 4 của bảng S-box7 4 Chuyển sang hệ nhị phân 0100
4 bit giữa (C) 0100 4

– cụm 8: 010000

bit đầu-cuối (R) 00 Chuyển sang hệ 10 0 xét dòng 0 cột 8 của bảng S-box8 10 Chuyển sang hệ nhị phân 1010
4 bit giữa (C) 1000 8

Như vậy: Kết quả cuối cùng ta được: 1111 1101 0011 0010 0001 0101 0100 1010 

 

7. Các đề kiểm tra

7.1 Đề kiểm tra 2016

7.2 Đề kiểm tra DA17QTM

7.3 Đề kiểm tra DA17TT

Bài giải đề 01

Câu 5: Hình phía dưới sai ở B1 và kết quả cuối cùng sẽ ra A0. Còn những chỗ khác là đúng

Kinh nghiệm

  • Nghịch đảo cộng: 2 số cộng lại mod cho n đồng dư với 0
  • Nghịch đảo nhân: 2 số nhân lại mod cho n đồng dư với 1

Related posts:

  1. Thuật toán khai khoáng dữ liệu – Hiểu Thuật Toán Naive Bayes như thế nào?

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *