Chương 1: Tống quan về các hệ mật mã. > Chương này giới thiệu một sé thong tin tổng quan về các hệ mật mã, trình bày các lý thuyết mật mã, mật mã truyền thống, mật mã khóa công khai. Chương 2: Một số phương pháp tấn công hệ mật mã truyền thống. > Chương này giới thiệu một số phương pháp tấn công hệ mật mã truyền thống.
Trên cơ sở đó, học viên đưa ra một số nhược điểm của hệ mật mã truyền thống. Chương 3: Đề xuất thuật toán nhằm nâng cao độ an toàn cho hệ mật mã truyền thống. > Chương này sẽ dựa trên cơ sở đã nghiên cứu ở chương 2 dé đưa ra thuật toán nâng cao độ an toàn. So sánh thuật toán cũ và mới để thấy được độ an toàn bảo mật của văn bản đã được mã hóa? Đề xuất thuật toán, xây dựng thuật toán, cài đặt thuật toán và thử nghiệm.
Đánh giá kết quả, hướng nghiên cứu tiếp và kết luận. CHUONG 1: TONG QUAN VE CAC HE MAT MA 1. Téng quan vé ly thuyét mat ma. Một số khái niệm cơ bản.
q, Các mô hình mã hóa có chung một số thuật ngữ nhw sau: ° Bản rõ: Là nội dung của thông điệp cần gửi đi và cần được bảo vệ an toàn. Nó có thể là xâu các bít, các file văn bản, các file có cấu trúc. ° Mã hoá: Là quá trình biến đổi bản rõ thành những dãy ký tự không đọc được có nghĩa trước khi gửi đến người nhận đích thực. ° Bản mã: Là kết quả thu được khi mã hóa bản rõ theo một thuật toán mã hóa nào đó.
° Giải mã: Là quá trình xử lý ngược, tiến hành giải mã bản mã để thu lại bản rõ. Ví dụ: Mã hóa văn bản có nội dung là “ABC” với luật mã là tịnh tiến vòng 1 đơn vị đối với mã ASCII của mỗi kí tự. Vậy ta có: Bản rõ: “ABC” Mã hóa: Thực hiện mã hóa theo luật mã. Biến đổi các kí tự thành các số theo mã ASCII của kí tự đó.
A ©65,B c©66,C © 67 Thu được các mã mới sau khi tịnh tiến là: 66 — 67 — 68 Biến đổi các mã mới thành kí tự. Giải mã: Thu được bản rõ là “ABC”. Hệ mật mã là một bộ gồm 5 thành phần (P, C, K, E, D),trong đó, P (PlaintexÐ): là tập hợp hữu hạn các bản rõ. C (Ciphertext): la một tập hữu hạn các bản mã.
K (Key): là một tập hữu hạn các khóa có thẻ. E (Encrytion): là tập các hàm lập mã. D (Decrytion): là tập các hàm giải mã. Chúng ta đã biết một thông báo thường được xem là bản rõ.
Người gửi sẽ có nhiệm vụ mã hóa bản rõ đó bằng một thuật toán mã hóa nào đó để cho ra kết quả được gọi là bản mã. Và bản mã này sẽ được gửi đi trên đường truyền không an toàn tới người nhận. Người nhận giải mã bản mã dé tìm hiểu nội dung của bản rõ. Với mỗi ke K, có một hàm lập mã e¿e E, e¿: P->C, và một hàm giải mã d, €D, dk: C>P sao cho: d, (e(x))=x, VxeP c, Những tính năng của hệ mật ma.
° Cung cấp một mức cao về tính bảo mật, toàn vẹn, chống chối bỏ và xác thực. ° Tính bảo mật: Bảo đảm bí mật cho nội dung thông báo và dữ liệu bằng nhờ các kỹ thuật mã hóa. ° Tính toàn vẹn: Bảo đảm với các bên rằng bản tin không bị thay đổi trên đường truyễn tin. ° Chống chối bỏ: Có thể xác nhận rằng tài liệu đã đến từ ai đó, ngay cả khi họ có gắng từ chối nó.
° Tính xác thực: Cung cấp hai dịch vụ: > Nhan dang nguồn gốc của một thông báo, đảm bảo rằng nó là đúng sự thực. > Kiểm tra định danh của người đang đăng nhập hệ thống, tiếp tục kiểm tra đặc điểm của họ trong trường hợp ai đó cô gắng kết nói và giả danh là người sử dụng hợp pháp. Cơ sở toán học của lý thuyết số. a, Tính chia hễt của các số nguyên, thuật toán Euclide [3].
Ta ký hiệu Z là tập hợp các số nguyên, Z = {.}, và Z* là tập hợp các số nguyên không âm, Z*= {0,1,2,. - Tính chia hết của số nguyên Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân, nhưng không đóng kín đối với phép chia: chia một số nguyên cho một số nguyên không phải bao giờ cũng được kết quả là một số nguyên. Vì vậy, trường hợp chia hết, tức khi chia số nguyên z cho số nguyên b được thương là một số nguyên g, a = b. q, có một ý nghĩa đặc biệt.
Khi đó, ta nói ø chia hết cho b, b chia hết bởi a, ø là bội số của b, blà ước số của a, và ký hiệu là b|a. Dễ thấy ngay rằng số 1 là ước số của mọi số nguyên bắt kỳ, số 0 là bội số của mọi số nguyên bất kỳ, mọi số nguyên ø là ước số, đồng thời là bội số, của chính nó. Cho hai số nguyên bất kỳ ø và b, b > 1. Thực hiện phép chia a cho b ta sẽ được hai số q va r sao cho a=b.
Số a được gọi là số thương của phép chia a cho b, ký hiệu ø div b, và số r được gọi là số đư của phép chia a cho b, ký hiệu z mod b. Thi du: 25 div 7 =3 va 25 mod 7 = 4, -25 div 7 = -4 và -25 mod 7 = 3. Một số nguyên đ được gọi là ước số chung của hai số nguyên ø và b nếu d | a vad | b. Số nguyên đ được gọi là ước số chung lớn nhất của ø và b nếu d>0, đlà ước số chung cua a va b, va moi ước sé chung của ø và b đều là bế hơn hay bằng đ.
Ta ký hiệu ước sé chung lớn nhất của ø và b là gced(a, b). Thi dụ gcd(12, 18) = 6, gcd(-18, 27) = 3. Dễ thấy rằng với mọi số nguyên đương z ta có gcd(a, 0) =a, ta cting sé qui ước xem rằng gcd(0, 0) = 0.2: Nếu b #0 và b| a thì gcd(a, b) = b. Một số nguyên rn được gọi là bội số chung cua a vab néua | m vab | m.
Số m được gọi là bội số chung nhỏ nhất của ø và b , và được ký hiệu là lcm(z, b), nếu m la bội số chung của a va b và mọi bội số chung cla a va b đều lớn hơn hoặc bằng m. Thí du lem(14,21) = 42. Với hai số nguyên dương ø và b bất kỳ ta có quan hệ Icm(a, b).2 ta suy ra thuật toán sau đây thực hiện việc tìm ước số chung lớn nhất của hai số nguyên bất kỳ: Thuật toán Euelide tìm ước số chung lớn nhất: INPUT: hai số nguyên không âm z và b, với a>b. OUTPUT: ước số chung lớn nhất của z và b.
Trong khi còn b > 0, thực hiện: 1.datr-amodb, acb,ber. Cho ra két qua (a). Thí dụ: Dùng thuật toán Euclide tìm gcd(18, 12), ta lần lượt được các giá tri gan cho các biên a, b và r như sau: a b r 18 = 1-12 +6 18 12 12=2:6+0 12 6 6 6 0 0 Thuật toán Euclide mở rộng: Thuật toán Euclide mở rộng. Thuật toán nay nhằm xác định 3 số nguyên x, y, đ sao cho: mx + my = đ, trong đó m, n 1a hai số nguyên cho trước với giả thiết m > n.
Nội dung thuật toán như sau: Cho 3 véc - tơ (21, a2, a3), (b1, b2, b3), (c1, c2, c3 ); Các bước tiến hành như sau: 11 Bước!. Nếu 23=0 thì thuật toán dừng và (zl, a2, a3) là đáp số; Bước 3. Đặt ạ = [a3/ b3]; và (c1, c2, c3) — (a1, a2, a3 ) -g(b1, b2, b3 ); (al, a2, a3 ) — (b1, b2, b3); (b1, b2, b3) (c1, c2, c3) và đi đến bước 2. Trong đó [X] là phần nguyên của số X, nghĩa là [X] là số nguyên lớn nhất nhưng không vượt quá X.
Thí dụ: Dùng thuật toán Euclide mở rộng cho các s6 a= 4864 va b= 3458, ta lần lượt được các giá trị sau đây cho các biến a, b, g, , x, y, x¡, x2, y;, y2 (sau mỗi chu trình thực hiện hai lệnh 3.2): a b q r x y xX] x2 yi y2 4864 | 3458 0 1 1 0 3458 | 1406 1 | 1406 1 -1 1 0 -1 1 1406 | 646 2 | 646 -2 3 -2 1 3 -1 646 | 114 2 | 114 5 -7 5 -2 -7 3 114 76 5 76 -27 38 -27 5 38 -7 76 38 1 38 32 -45 32 -27 | -45 38 38 0 2 0 -91 | 128 -91 32 | 128 -45 Ta dé thir lai rang sau mỗi lần thực hiện chu trình gồm hai lệnh 3.2, các giá trị x, y, r thu được luôn thoả mãn 4864-x+ 3458-y = r, và do đó khi kết thúc các vòng lặp (ứng với giá trị b= 0), thực hiện tiếp lệnh 4 ta được kết qua d = 38, x = 32 và y= -45, cặp số (32, -45) thoả: 4864-32 + 3458-(-45) = 38. b, Số nguyên tố và nguyên tố cùng nhau. Số nguyên tố là số nguyên dương chỉ chia hết cho 1 và chính nó. Hệ mật mã thường sử dụng các số nguyên tố ít nhất là lớn hơn 10159, 12 Hai sé m van duoc gọi là nguyên tố cùng nhau, nếu ước số chung lớn nhất của ching bang Ky hiéu: ged (m, n) = 1.
Thi dụ: 9 và 14 là hai số nguyên tố cùng nhau. - Cho a va b là các số nguyên ø là số nguyên dương. Khi đó ø được gọi là đồng dư với b theo modulo n, ky hiéu la a = b (mod n), néu a, b chia cho n có cùng số dư. ø được gọi là modulo của đồng dư.
Kí hiệu: a = b (mod n) Thí dụ: 11 = 5 (mod 3) vi 11 va 5 khi chia cho 3 đều dư số dư là 2. - Tính chất đồng dư Cho 4, ai, b, bị, c€ Z. Ta có các tính chất sau: a = bmod n nếu và chỉ nếu z và b có cùng số đư khi chia cho n Tinh phản xa: a = amodn Tinh đối xứng: Nếu a = b mod ø thì 5= z mod ø Tinh giao hoan: Néu a = b mod n va b= c mod nthia = c mod n Néu a = ai mod ñ, b = bị mod ø thì ø + b = (a, + bị) mođ n vaa - b= (a;"b,) mod n ° Lớp tương đương: Lớp tương đương của số nguyên z là tập hợp các số nguyên đồng dư với a theo modulo n.