Bài giảng Lý thuyết mật mã và an toàn thông tin - 1

MẬT MÃ CỔ ĐIỂN 1.1 MỘT SỐ HỆ MẬT MÃ ĐƠN GIẢN 1.1.1 MẬT MÃ DỊCH CHUYỂN - SHIFT CIPHER 1.1.2 MẬT MÃ THAY THẾ - SUBSTITUTION CIPHER 1.1.3 MẬT MÃ TUYẾN TÍNH - AFFINE CIPHER 1.1.4 MẬT MÃ VIGENÈRE 1.1.5 MẬT MÃ HILL 1.1.6 MẬT MÃ HOÁN VỊ 1.1.7 MẬT MÃ DÒNG Mục đích cơ bản của hệ mật mã cho phép hai người, Alice và Bob, truyền thông tin qua một kênh không được bảo mật theo cách sao cho đối thủ, Oscar, không thể hiểu được thông tin gì đang được nhắc đến. Kênh đó có thể là đường điện thoại hoặc có thể là mạng máy tính. Thông điệp mà Alice muốn gửi tới Bob, chúng ta gọi là “ văn bản gốc ” hoặc “ bản rõ ” ( “ Plaintext ”), được xây dựng hoàn toàn tuỳ ý, có thể là các ký tự tiếng Anh, dữ liệu số MỞ ĐẦU: Sơ đồ minh hoạ Alice Tập các khoá Bob Giải mã Mã hoá x y K x K Mô tả hình thức bằng ký hiệu toán học 1.1.1 Hệ mã dịch chuyển Hệ mã dựa trên cơ sở của phép biến đổi một ký tự trong văn bản gốc thành một ký tự khác trong bản mã Trong trường hợp K=3 , hệ mật mã trên được gọi là mật mã Caesar , được thừa nhận là của Julius Caesar. Trong hệ mật mã Caesar , mỗi ký tự được thay thế bởi ký tự đứng sau nó ba vị trí trong bảng chữ cái Alphabet) Để thực hiện theo phương pháp này, trước hết ta cần định nghĩa một bảng mã để số hoá văn bản gốc: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Xét ví dụ Giả sử khoá K = 11, và văn bản gốc ban đầu là wewillmeetatmidnight Đầu tiên ta biến đổi văn bản gốc thành một dãy các số nguyên , kết quả nhận được như sau: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 Tiếp theo, ta cộng 11 vào mỗi giá trị , sau đó quy các giá trị đó sang modulo 26 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuối cùng, ta biến đổi dãy số nguyên sang các ký tự Aphabet tương ứng như trên , nhận được bản mã HPHTWWXPPELEXTOYTRSE Để giải mã bản mã , Bob đầu tiên biến đổi tương ứng bản mã sang dãy của các số nguyên , rồi trừ từng giá trị trong dãy cho 11 ( sau đó quy đổi sang modulo 26), và cuối cùng biến đổi dãy số nguyên vừa nhận được sang các ký tự Alphabe.Ta thu được văn bản gốc ban đầu Wewillmeetatmidnight Nhận xét: Ta đã sử dụng ký tự hoa cho bản mã và ký tự thường cho văn bản gốc . NHẬN XÉT Ta nhận xét rằng hệ mã dịch chuyển tính bảo mật không cao , chỉ với 26 khoá, rất dễ dàng để thử các quy tắc giải mã dK cho đến khi nhận được văn bản có “ ý nghĩa ”. Xem minh hoạ dưới đây : Ví dụ 1.2 Cho văn bản dưới dạng mật mã là xâu sau đây : JBCRCLQRWCRVNBJENBWRWN 9 1 2 17 2 11 16 17 22 2 17 21 13 1 9 4 13 1 22 17 22 13 Ta lần lượt thử các hàm giải mã d0 ,d1, . Kết quả nhận được dưới đây : jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk fxynyhmnsynrjxfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvdyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwftojof a stitch in times saves nine k cdsdmr .. Cuối cùng thử hết tới K=26, ta xác định được văn bản gốc và dừng lại. Khoá K= 9. K=0 K=1 K=2 K=3 K=4 K=5 K=6 K=7 K=9 K=8 K=10 1.1.2 The Substitution Cipher ( Hệ mã thay thế ) Ví dụ : Cho hoán vị “ ngẫu nhiên ” sau :  a b c d e f g h i j k l m X N Y A H P O G Z Q W B T n o p q r s t u v w x y z S F L R C V M U E K J D I Do đó , Hàm giải mã là hoán vị nghịch đảo. Hãy mã hóa bản rõ: thisciphertextcannotbedecrypted ( ) , ( ) ,...e a X e b N   A B C D E F G H I J K L M d l r y v o h e z x w p t N O P Q R S T U V W X Y Z b g f j q n m u s k a c i Do đó , Ví dụ giải mã đoạn bản mã sau : MGZVYZLGHCMHJMYXSSFMNHAHYCDLMHA Ta thu được thisciphertextcannotbedecrypted ( ) , ( ) ,...d A d d B l   Chương 2.4, 2.5 Kenneth H. Rosen Xuân 2008 Đại học FPT Discrete Mathematics I phép chia division Số nguyên Integer Số nguyên GIỚI THIỆU Integer INTRODUCTION Giới thiệu Chúng ta sẽ học: Số nguyên •Phép chia hết: thương, số dư •Biểu diễn số nguyên theo cơ số: 10, 2, 8, 16 •Thuật toán cho các phép tính số nguyên •Số nguyên tố, hợp số •Ước chung lớn nhất, bội chung nhỏ nhất •Hàm Euler •Thuật toán Euclid Số nguyên PHÉP CHIA Integer DIVISION Định nghĩa Definition Cho hai số nguyên a, b với a ≠ 0, ta nói b chia hết cho a nếu tồn tại một số nguyên c sao cho b = a.c. Khi b chia hết cho a ta nói a là ước của b và b là bội của a và kí hiệu là a|b, nếu trái lại b không chia hết cho a thì ta kí hiệu a|b. a|b  cZ, (a.c =b) Định lí Theorem Cho 3 số nguyên a, b, c. Khi đó Nếu a|b và a|c thì a|(b + c). Nếu a|b thì a|bc, với mọi số nguyên c. Nếu a|b và b|c thì a|c. Phép chia Số nguyên PHÉP CHIA Integer DIVISION Ví dụ Example 21 chia hết cho 3 vì tồn tại 7 để 21 = 3.7 Tập tất cả các bội của 2 là tập các số chẵn Tập tất cả các ước của 2 là {1, -1, 2, -2} Phép chia Số nguyên PHÉP CHIA Integer DIVISION Định lí & định nghĩa Theorem & definition Cho a là một số nguyên và d là một số nguyên dương. Khi đó tồn tại duy nhất các số q và r, với 0  r < d sao cho a = qd + r. Với các kí hiệu như trên ta nói d là số chia, a là số bị chia, q được gọi là thương (q = a div d) và r được gọi là số dư (r = a mod d). Nhận xét: a chia hết cho d khi và chỉ khi số dư của phép chia a cho d bằng 0. Div, mod Số nguyên PHÉP CHIA Integer DIVISION Thuật toán Algorithm procedure Chia(a  Z, d  N*) q: = 0 r: = |a| while r  d begin r: = r – d q: = q + 1 end if (a 0) then begin r: = d – r q: = –(q + 1) end Div, mod Số nguyên PHÉP CHIA Integer DIVISION Ví dụ Example Xác định thương và số dư khi chia 11 cho 3 q = 0 & r = 11 11  3 r = 11 – 3 = 8 q = 0 + 1 = 1 8 8 – 3 = 5 1 2 5 2 5 2 3 2 Xác định thương và số dư khi chia -11 cho 3 -11 0 q = -(3 + 1) = -4 r = 3 – 2 = 1 thương số dư Div, mod Số nguyên SỐ NGUYÊN TỐ Integer PRIME Định nghĩa Definition Số nguyên dương p > 1 được gọi là số nguyên tố nếu nó chỉ có các ước số dương là 1 và p. Các số nguyên dương > 1 và không phải là số nguyên tố được gọi là hợp số. Chú ý: n  N* là hợp số  (a, 1< a < n, a|n). Định lí Theorem Nếu n là một hợp số thì n có ước nguyên tố ≤ n1/2 Số nguyên tố Số nguyên SỐ NGUYÊN TỐ Integer PRIME Định nghĩa Definition Để tìm tất cả các số nguyên tố ≤ n ta sử dụng sàng Erathosthenes. Thủ tục này được mô tả như sau: 1. Liệt kê tất cả các số nguyên từ 2 đến n. Gọi là danh sách A. 2. Lấy ra số 2 là số đầu tiên của danh sách A và cũng là số nguyên tố đầu tiên. Gọi là danh sách B. 3. Xóa bỏ 2 và các bội của nó ra khỏi danh sách A. 4. Số x đầu tiên trong danh sách A mới là số nguyên tố và viết vào B. 5. Xóa x và các bội ( x2) của x ra khỏi A. 6. Lặp lại bước 4 và 5 cho đến khi A không còn phần tử nào. Chú ý là khi phần tử đều tiên của danh sách còn lại > (phần tử lớn nhất)1/2 thì tất cả các phần tử còn lại đều là số nguyên tố. Số nguyên tố Số nguyên SỐ NGUYÊN TỐ Integer PRIME Ví dụ Example Tìm tất cả các số nguyên tố ≤ 120 Số nguyên tố Định lí Theorem Với mọi n > 1, dạng phân tích của n! là ở đó, v(pi) = [n/pi] + [n/pi 2] + + [n/pi s] + Số nguyên SỐ NGUYÊN TỐ Integer PRIME Định lí cơ bản của số học Theorem Mọi số nguyên dương n > 1 đều có thể được viết duy nhất dưới dạng tích của các số nguyên tố, trong đó các số nguyên tố được viết theo thứ tự tăng dần, sự phân tích này gọi là phân tích tiêu chuẩn của n. ....,.... 2121 21 r v r vv ppppppn r  Số nguyên tố )()( 2 )( 1 ....! 21 rpv r pvpv pppn  Số nguyên SỐ NGUYÊN TỐ Integer PRIME Ví dụ Example Tìm dạng phân tích tiêu chuẩn của 10! 10! = 2v(2).3v(3).5v(5).7v(7) v(2) = [10/2] + [10/22] + [10/23] + [10/24] + = 8 v(3) = [10/3] + [10/32] + [10/33] + = 4 v(5) = [10/5] + [10/52] + = 2 v(7) = [10/7] + [10/72] + = 1 10! = 28.34.52.71 Bài tập: viết thuật toán xác định dạng phân tích tiêu chuẩn của n! Số nguyên tố Số nguyên SỐ NGUYÊN TỐ Integer PRIME Định lí Euclid Theorem Tồn tại vô số số nguyên tố. Chứng minh: Giả sử chỉ có một số hữu hạn số nguyên tố: p1, p2, , pn. Đặt Q = p1.p2 pn + 1 > 1 Theo Định lí cơ bản của số học: pj, 1≤ j ≤ n, pj|Q. pj|Q  pj|(Q – p1.p2 pn) = 1 (vô lí)  ĐPCM Gọi (x) là số số nguyên tố ≤ x. Định lí Euclid: limx→(x) = . VD: (10) = 4 Hãy mô tả độ tăng của (x)? Xem trang bên → Số nguyên tố Số nguyên ƯCLN Integer GCD Định nghĩa Definition •Cho a và b hai số nguyên khác 0, số nguyên d lớn nhất sao cho d|a và d|b được gọi là ước chung lớn nhất của a và b, kí hiệu là ƯCLN(a, b). •Bội chung nhỏ nhất của hai số nguyên dương a và b là số nguyên dương nhỏ nhất chia hết cho cả a lẫn b, kí hiệu là BCNN(a, b). Ước chung Số nguyên ƯCLN Integer GCD Định lí Theorem Cho 2 số nguyên dương a, b có dạng phân tích tiêu chuẩn như sau: ở đó, ai, bj  0 (có thể bằng 0). Khi đó Hơn nữa: a.b = ƯCLN(a, b). BCNN(a, b) ra r aa pppa .... 21 21 rb r bb pppb .... 21 21 ),min(),min( 2 ),min( 1 ....),UCLN( 2211 rr ba r baba pppba  ),max(),max( 2 ),max( 1 ....),BCNN( 2211 rr ba r baba pppba  Ước chung Ví dụ Example Cho hai số a = 300, b = 315 tìm ƯCLN và BCNN của a và b. Số nguyên ƯCLN Integer GCD 300 = 22.31.52 315 = 32.51.71 = 22.31.52.70 = 20.32.51.71 ƯCLN(300, 315) = 2min(2, 0).3min(1, 2).5min(2, 1).7min(0, 1) = 20.31.51.70 = 15 BCNN(300, 315) = 2max(2, 0).3max(1, 2).5max(2, 1).7max(0, 1) = 22.32.52.71 = 6300 300*315 = 94500 = ƯCLN(300, 315)*BCNN(300, 315) Ước chung Số nguyên ƯCLN Integer GCD Định nghĩa Definition •Hai số nguyên a và b được gọi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng bằng 1. •Các số nguyên a1, a2, , an được gọi là đôi một nguyên tố cùng nhau nếu hai số bất kì trong chúng ai, aj (1  i < j  n) nguyên tố cùng nhau. Chú ý: Cho p là số nguyên tố, thì p nguyên tố cùng nhau với tất cả các số nguyên a không chia hết cho p. Hàm Euler Số nguyên ƯCLN Integer GCD Để tìm ước chung lớn nhất của hai số nguyên a và b ta thường áp dụng thuật toán Euclid cơ sở toán học của thuật toán này như sau Bổ đề Lemma Cho a = q.b + r, trong đó a, b, q, r là các số nguyên. Khi đó ƯCLN(a, b) = ƯCLN (b, r) T.T Euclid Số nguyên ƯCLN Integer GCD Thuật toán Euclid Algorithm procedure ƯCLN (a, b nguyên dương) x: = a y: = b while y ≠ 0 begin r: = x mod y x: = y y: = r end {ƯCLN(a, b) = x} Dạng đệ quy procedure: ƯCLN (a, b  N, a < b) if a = 0 then ƯCLN(a, b): = b else ƯCLN(a, b): = ƯCLN(b mod a, a) T.T Euclid Số nguyên ƯCLN Integer GCD Ví dụ Example Tìm ước chung lớn nhất của 123 và 456 456 = 3.123 + 87 123 = 1.87 + 36 87 = 2.36 + 15 36 = 2.15 + 6 15 = 2.6 + 3 6 = 2.3 + 0 ƯCLN(123, 456) = 3 T.T Euclid Số nguyên ƯCLN Integer GCD Ví dụ Example Tìm ước chung lớn nhất của 123 và 456 ƯCLN(123, 456) = 3 = ƯCLN(456 mod 123, 123) 87, 123) = ƯCLN(123 mod 87, 87) 36, 87) = ƯCLN(87 mod 36, 36) 15, 36) = ƯCLN(36 mod 15, 15) 6, 15) = ƯCLN(15 mod 6, 6) 3, 6) = ƯCLN(6 mod 3, 3) 0, 3) T.T Euclid Số nguyên ƯCLN Integer GCD Định lí Theorem Cho hai số nguyên dương a và b, với a  b. Khi đó độ phức tạp của thuật toán Euclid theo số phép chia là O(logb). T.T Euclid Đồng dư ĐỊNH NGHĨA Congruence DEFINITION Định nghĩa Definition Cho a và b là hai số nguyên và m là một số nguyên dương. Ta nói a đồng dư với b theo môđun m và kí hiệu là a  b (mod m) nếu a – b chia hết cho m, nếu trái lại thì kí hiệu là a  b (mod m). Như vậy: a  b (mod m)  m|a – b  a mod m = b mod m Đồng dư Tập tất cả các số nguyên sẽ thu gọn về m “số” mới theo mod m mỗi “số” này là một lớp đồng dư. Đồng dư ĐỊNH NGHĨA Congruence DEFINITION Định nghĩa Definition Tập hợp gồm m số nguyên đôi một không đồng dư theo mod m gọi là một hệ thặng dư đầy đủ theo mod m. Một số nguyên bất kì sẽ đồng dư với một và chỉ một số trong một hệ thặng dư đầy đủ. Ví dụ Example {0, 1, 2, 3, 4, 5, 6} là một hệ thặng dư đầy đủ theo mod 7 {1, 2, 3, 5, 8, 13, 21} không là một hệ thặng dư đầy đủ theo mod 7 vì 1  8 (mod 7) {20, 21, 22, 23, 24, 25, 26} có là một hệ thặng dư đầy đủ theo mod 7 không? Không Đồng dư Đồng dư ĐỊNH NGHĨA Congruence DEFINITION Định lí Theorem Cho m là số nguyên dương. Khi đó • a  b (mod m)  k, a = b + km. • Nếu a  b (mod m) và c  d (mod m) thì a + c  b +d (mod m); a.c  b.d (mod m) Đồng dư Có một mối liên hệ giữa các phép tính số học thông thường và các phép tính số học theo môđun m dấu bằng “=” liên hệ với dấu đồng dư “” +, –, *, / liên hệ với +, –, *, / rồi lấy đồng dư Đồng dư ĐỊNH NGHĨA Congruence DEFINITION Vẫn có những tính chất đúng trong số học nhưng không còn đúng trong số học đồng dư nữa. a.b = 0  a = 0 hoặc b = 0 nhưng a.b  0 (mod m)  a  0 hoặc b  0 Ví dụ Example 4.3  0 (mod 6) nhưng 4  0 (mod 6) 3  0 (mod 6) Đồng dư Đồng dư NGHỊCH ĐẢO Congruence INVERSE Hệ quả lemma Cho hai số a và m nguyên tố cùng nhau và m > 1 thì tồn tại số nguyên s (duy nhất theo mod m) để sa  1 (mod m). Định nghĩa Definition Cho hai số a và m nguyên tố cùng nhau và m > 1 thì a gọi là khả nghịch theo mod m, nghịch đảo s của a thỏa mãn sa  1 (mod m) duy nhất (theo mod m). Tập con của một hệ thặng dư đầy đủ mod m gồm tất cả các phần tử khả nghịch mod m gọi là một hệ thặng dư thu gọn mod m. Nghịch đảo Chú ý: nếu a là phần tử khả nghịch theo mod m thì a.b  0 (mod m) khi và chỉ khi b  0 (mod m) Đồng dư NGHỊCH ĐẢO Congruence INVERSE Ví dụ Example Một hệ thăng dư đầy đủ mod 12 là 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 Một hệ thăng dư thu gọn mod 12 là 1, 5, 7, 11 Cho p là một số nguyên tố, một hệ thăng dư thu gọn mod p là {1, 2, , p–1} Định lí Theorem Số phần tử của mọi hệ thặng dư thu gọn mod m là như nhau và bằng (m), hàm Euler của m. Nghịch đảo 1.1.3. Hệ mã tuyến tính Vì gcd(a,26)=1 nên a chỉ có thể nhận các giá trị sau đây: a= 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 a 1 3 5 7 9 11 15 17 19 21 23 25 a-1 1 9 21 15 3 19 7 23 11 5 17 25 Ta xem xét ví dụ sau đây : Giả sử K= ( 7,3). Hàm mã hoá là = 7x+3mod 26 Mã hoá văn bản P - hot . Số hóa h, o, t được 7,14,19 . e(h) = 7.7+3 mod 26 = 0 , e(o) = 7.14+3 mod 26 = 23 , và e(t) = 7.19+3 mod 26 = 6 , Bản mã là xâu ký tự “AXG”. )(xeK Để giải mã bản mã , ta sử dụng hàm giải mã = (y-b) mod 26 . Trong ví dụ trên với K = ( 7,3) ta có a= 7 nên =15 Do đó = (15y-19) mod 26 Khi ta giải mã, thu được các số 7, 14, 19. Các số này tương ứng với các ký tự h, o, t. Do đó ta có văn bản gốc là hot Lưu ý: Có 12 x 26 = 312 chìa khóa có thể, có thể duyệt toàn bộ để thám mã. 1a )(ydK )(ydK 1a 1.1.4 Hệ mã Vigenère Cả hai hệ mật mã Shift Cipher và Substitution Cipher, khi đã chọn khoá K, mỗi ký tự Alphabe ánh xạ đến một ký tự Alphabe duy nhất. Vì lý do này , các hệ mật mã đó được gọi là đơn ký tự ( monoalphabetic ). Đến đây , ta giới thiệu một hệ mật mã không phải là monoalphabetic , được biết đến là Vigenère Cipher, mang tên của Blaise de Vigenère, thế kỷ 16. Sử dụng tương ứng , ta có thể kết hợp với mỗi khoá K vào xâu ký tự Alphabe có độ dài m, gọi là từ khoá. Mật mã Vigenère Cipher mã hoá theo từng khối m ký tự của văn bản gốc. Ví dụ : Giả sử m = 6 và từ khoá là C I P H E R . Tương ứng với nó là các số K = ( 2, 8,15,7,4,17 ). Giả sử văn bản gốc :thiscryptosystemisnotsecure Ta biến đổi các phần tử của văn bản gốc quy đổi sang modulo 26 , và viết chúng thành một nhóm của sáu số , và cộng thêm vào từ khoá ( modulo 26 ) , giống như sau đây : 0, 1, 2,..., 25A B C Z    19 7 8 18 2 17 24 15 19 14 18 24 18 19 2 8 15 7 4 17 2 8 15 7 4 17 2 8 21 15 23 25 6 8 0 23 8 21 22 15 20 1 4 12 8 18 13 14 19 18 4 2 20 17 4 15 7 4 17 2 8 15 7 4 17 2 8 15 19 19 12 9 15 22 8 25 8 19 22 25 19 Bản mã hoá là một xâu VPXZGIAXIVWPUBTTMJPWIZITWZT Để giải mã , ta cần sử dụng từ khoá tương tự , nhưng chúng ta phải trừ đi khoá trong modulo 26.