Ví dụ giải phương trình diophan 2740x + 1760 = 80
Ta có: a = 2740, b = 1760, c = 80
qr1r2rs1s2st1t2t12740176098010101-1
Tiếp theo sẽ dời giá trị:
Ta được:
qr1r2rs1s2st1t2t12740176098010101-1 1760980 01 1-1
Tiếp tục thực hiện:
qr1r2rs1s2st1t2t12740176098010101-11176098078001-11-12
Tiếp tục cho đến khi r2 = 0
qr1r2rs1s2st1t2t12740176098010101-11176098078001-11-1219807802001-12-12-33780200180-12-72-3111200180202-79-311-149180200-79-8811-14137 200 9-88 -14137
Kết quả ta được:
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
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ự STTD3A0I8H7O14C2
Tiếp theo mình sẽ nhân với k1 và cộng với k2 ta được C
Kí tự STTk1k2CD3 25A0 10I8x 5+ 1050H7 45O14 80C2 20
Tiếp theo chia dư cho 26(kí tự)
Kí tự STTk1k2C Kq ModD3 25 25A0 10 10I8x 5+ 1050mod 2624H7 45 19O14 80 2C2 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ự STTk1k2C Kq ModKí tự mã hóaD3 25 25ZA0 10 10KI8x 5+ 1050mod 2624YH7 45 19TO14 80 2CC2 20 20U
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
Đề 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:
Đế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
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.
⊗000001010011100101110111000 001 010 011 100 101 110 111
Ở dòng 1, 0 nhân với mấy cũng bằng 0.
⊗000001010011100101110111000000000000000000000000000001 010 011 100 101 110 111
Tương tự cột 1, 0 nhân với mấy cũng bằng 0
⊗000001010011100101110111000000000000000000000000000001000 010000 011000 100000 101000 110000 111000
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 + x2x3 + x2 + 1x3 + x2 + 11———————– 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
⊗000001010011100101110111000000000000000000000000000001000 010000 010 011000 100000 101000 110000 111000
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
x4x3 + x2 + 1x4 + x3 + xx + 1———————– x3 + x x3 + x2 + 1 ———————– x2 + x + 1
x2 + x + 1 => 111
Vậy 100 ⊗ 100 = x2 + x + 1 = 111
⊗000001010011100101110111000000000000000000000000000001000 010000 010 011000 100000 111 101000 110000 111000 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 + x2x8 + x4 + x3 + x + 1x12 + x8 + x7 + x5 + x4x4 + 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
Đề 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
Ví dụ giảiGiả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ệ 10V86I73N78H72
Tiếp theo chuyển hệ 10 thành hệ nhị phân
Ký tựHệ 10Hệ nhị phânV860101 0110I730100 1001N780100 1110H720100 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
– cụm 2: 0101 0110 0100 1001 0100 1110 0100 1000
– cụm 3: 0101 0110 0100 1001 0100 1110 0100 1000
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
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ẽ:
– cụm 1: 001010
bit đầu-cuối (R)00Chuyển sang hệ 100xét dòng 0 cột 5 của bảng S-box115Chuyển sang hệ nhị phân11114 bit giữa (C)01015
(*): 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)10Chuyển sang hệ 102xét dòng 2 cột 6 của bảng S-box213Chuyển sang hệ nhị phân11014 bit giữa (C)01106
– cụm 3: 001001
bit đầu-cuối (R)01Chuyển sang hệ 101xét dòng 1 cột 4 của bảng S-box33Chuyển sang hệ nhị phân00114 bit giữa (C)01004
– cụm 4: 010010
bit đầu-cuối (R)00Chuyển sang hệ 100xét dòng 0 cột 9 của bảng S-box42Chuyển sang hệ nhị phân00104 bit giữa (C)10019
– cụm 5: 101001
bit đầu-cuối (R)11Chuyển sang hệ 103xét dòng 3 cột 4 của bảng S-box51Chuyển sang hệ nhị phân00014 bit giữa (C)01004
– cụm 6: 011100
bit đầu-cuối (R)00Chuyển sang hệ 100xét dòng 0 cột 14 của bảng S-box65Chuyển sang hệ nhị phân01014 bit giữa (C)111014
– cụm 7: 001001
bit đầu-cuối (R)01Chuyển sang hệ 101xét dòng 1 cột 4 của bảng S-box74Chuyển sang hệ nhị phân01004 bit giữa (C)01004
– cụm 8: 010000
bit đầu-cuối (R)00Chuyển sang hệ 100xét dòng 0 cột 8 của bảng S-box810Chuyển sang hệ nhị phân10104 bit giữa (C)10008
Như vậy: Kết quả cuối cùng ta được: 1111 1101 0011 0010 0001 0101 0100 1010
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
