HỆ MẬT MÃ KHÓA ĐỐI XỨNG

Chia sẻ: ngoisaotrongdem

Mã khóa đối xứng được dùng để chỉ các hệ mã mà trong đó, khi biết khóa lập mã ta có thể tìm được khóa giải mã một cách dễ dàng (vì vậy người ta thường coi chúng là một), đồng thời việc giải mã cũng đòi hỏi thời gian như việc lập mã. Các hệ mã thuộc loại này có thời gian lập mã và giải mã tương đối nhanh vì thế các hệ mã đối xứng thường được sử dụng để mã hóa những dữ liệu lớn. Nhưng các hệ mã đối xứng yêu cầu phải giữ bí...

Bạn đang xem 10 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: HỆ MẬT MÃ KHÓA ĐỐI XỨNG

 

  1. Chương HỆ MẬT MÃ KHÓA ĐỐI XỨNG (SYMMETRIC-KEY CRYPTOGRAPHY) Mã khóa đối xứng được dùng để chỉ các hệ mã mà trong đó, khi biết khóa lập mã ta có thể tìm được khóa giải mã một cách dễ dàng (vì vậy người ta thường coi chúng là một), đồng thời việc giải mã cũng đòi hỏi thời gian như việc lập mã. Các hệ mã thuộc loại này có thời gian lập mã và giải mã tương đối nhanh vì thế các hệ mã đối xứng thường được sử dụng để mã hóa những dữ liệu lớn. Nhưng các hệ mã đối xứng yêu cầu phải giữ bí mật hoàn toàn về khóa lập mã. Nội dung chính I. Các hệ mật mã cổ điển (Classical ciphers). II. Thám mã đối với hệ mật mã cổ điển. III. Mã dòng (Stream Cipher). IV. Mã khối (Block cipher)
  2. Trường Đại học Dân lập Hải Phòng Hiện nay tin học đã được áp dụng vào hầu hết các lĩnh vực trong cuộc sống và có một ảnh hưởng rất lớn đối với sự tồn tại và phát triển của các ngành khoa học khác. Trong mọi hệ thống tin học, thông tin luôn là thành phần cơ bản nhất và quan trọng nhất. Chúng ta không ai mà không gặp phải những trường hợp khi máy tính bị mất hết những thông tin quan trọng do nhiều nguyên nhân khác nhau như bị virus, bị hư hỏng thiết bị, do không biết sử dụng, bị đánh cắp hay xoá thông tin… Nói chung vấn đề an toàn và bảo mật thông tin rất đa dạng và phụ thuộc vào nhiều yếu tố chủ quan và khách quan khác nhau như: con người, môi trường, công nghệ… Hiện nay có rất nhiều công cụ và phần mềm hỗ trợ an toàn cho hệ thống máy tính. Tuy nhiên vấn đề đánh giá và chọn lựa một hệ thống an toàn rất phức tạp và chỉ mang tính tương đối bởi vì một hệ thống được đánh giá là rất an toàn hôm nay có thể không còn an toàn nữa vào ngày mai. Nếu chúng ta thường xuyên theo dõi các thông tin bảo mật trên Internet, chúng ta có thể thấy thông tin về những lỗ hổng bảo mật của các hệ điều hành, các phần mềm bảo mật, các dịch vụ… Vì vậy an toàn và bảo mật thông tin là một trong những thành phần quan trọng nhất cần được quan tâm trong việc duy trì và phát triển của hệ thống. Lê Thụy 2
  3. Chương 2 - Lý thuyết Mật mã và An toàn thông tin Mật mã và vấn đề an toàn thông tin ? Mật mã (Cipher) đã xuất hiện cách đây khoảng 4000 năm tại Ai cập. Khi mà các cuộc chiến tranh xẩy ra giữa các đế chế. Thông tin của bên A dưới dạng chữ cái (letter), chữ số (number) hay loại nào đó trước khi được gửi đi sẽ được mã hoá. Bên B nhận được thông tin mã hoá này thực hiện việc giải mã để hiểu được nội dung. Một người lấy được bản mã cũng khó có thể hiểu được nội dung của thông tin vì chỉ có A và B mới có cách giải mã. Thời kì này các thông tin được bảo mật bằng các phương pháp khác nhau, hay còn gọi là các hệ mật mã cổ điển. Các hệ mật mã sớm nhất được biết đến như mật mã Ceazar - mã dich chuyển (Shift Cipher), mã thế (Substitution Cipher)… Các hệ mật mã này được sử dụng trong một thời gian dài. Cho đến khi toán học phát triển. Các hệ mã mới được xây dựng trên các lý thuyết về toán học hiện đại. Một thế hệ mật mã được xây dựng dựa trên độ phức tạp tính toán, các hệ mật mã này được gọi là các hệ mã hiện đại. Các ứng dụng của các hệ mật mã ngày càng được áp dụng trong nhiều lĩnh vực xã hội. Giúp giải quết hàng loạt các vấn đề về an toàn thông tin trên các kênh thông tin không bảo mật. Mật mã cung cấp một giải pháp nhằm mục đích thực hiện biến một thông tin cụ thể dễ hiểu thành một dạng khác (khó hiểu) có quan hệ chặt chẽ với thông tin gốc. Giờ đây ta gọi thông tin chưa mã hoá (tường minh) là “bản rõ”, và thông tin sau khi được mã hoá là “bản mã”. Vậy mật mã là gì ? Tại sao nó lại bảo vệ đươc bí mật thông tin ? Cơ sở của nó là gì ? Định nghĩa : Mật mã học là sự nghiên cứu các phương pháp toán học liên quan đến một số khía cạnh của thông tin như sự an toàn, sự toàn vẹn dữ liệu, sự xác nhận tồn tại và sự xác nhận tính nguyên bản của thông tin. Lê Thụy 3
  4. Trường Đại học Dân lập Hải Phòng I. Các hệ mật mã cổ điển (Classical ciphers). 1. Mở đầu: - Mong muốn được trao đổi thông tin một cách bí mật là một trong những đòi hỏi của con người xuất hiện từ rất sớm trong lịch sử. Vì thế lịch sử của việc trao đổi thông tin mật rất phong phú và bao gồm những phát minh độc đáo mang đầy tính giai thoại. Ngành học nghiên cứu cách thức che dấu thông tin đối với những đối tượng không mong muốn được gọi là mật mã học (cryptography) - Mật mã (cipher) được dùng để bảo vệ bí mật của thông tin khi thông tin được truyền trên các kênh thông tin không bảo mật như thư tín, điện thoại, mạng truyền thông máy tính… - A muốn gửi cho B một văn bản bằng tiếng Việt (gọi là “bản rõ” - plaintext), muốn được bảo mật thì A phải lập mật mã cho “bản rõ” đó (gọi là “bản mã” - ciphertext) và gửi “bản mã” cho B. A và B có một khoá mật mã chung, vừa để A lập “bản mã”, vừa để B giải “bản mã” thành “bản rõ”. Một người khác không có khoá đó, thì dù có lấy được “bản mã” từ kênh truyền tin cũng không thể biến thành “bản rõ” để hiểu được nội dung thông báo mà A gửi cho B. M’ Phân tích mật mã C Bản tin Các bản tin Bản tin gốc (M) mật mã gốc (M) Bộ mã hoá Kênh công cộng Bộ giải mã A☺ B☺ Kênh an toàn - Các hệ mật mã cổ điển thực hiện việc bảo mật đó đều dùng một khoá chung cho việc lập mã và giải mã, các bản rõ và bản mã thường dùng cơ sở là bảng chữ trong ngôn ngữ tự nhiên. Trong phần này, để tiện trình bầy ta dùng bảng chữ cái tiếng Anh làm ví dụ, và dùng các số liệu thống kê của tiếng Anh để minh hoạ. Lê Thụy 4
  5. Chương 2 - Lý thuyết Mật mã và An toàn thông tin - Dưới đây là một số định nghĩa toán học về hệ thống mật mã: Định nghĩa 1.1: Một hệ mật mã là một bộ năm (P, C, K, E, D) thoả mãn các điều kiện sau đây: + P là một tập hữu hạn các bản rõ. + C là một tập hưu hạn các bản mã. + K là một tập hưu hạn các khoá. + Với mỗi k ∈ K, có một hàm lập mã ek ∈ E, ek: P → C, và một hàm giải mã dk ∈ D, dk: C → P sao cho dk(ek(x)) = x với mọi x ∈ P. Trong thực tế, P và C thường là bảng chữ cái (hoặc tập các dãy chữ cái có độ dài cố định) Nếu bản rõ là (một xâu chữ cái): x = x1x2x3…xn (xi ∈ P ), và khoá là k ∈ K thì bản mã sẽ là: y = y1y2y3…yn (yi ∈ C ) Trong đó yi = ek(xi) (1 ≤ i ≤ n). Nhận được bản mã y, biết khoá k, sẽ tìm được bản rõ x, vì xi = dk(yi) Sau đây thay cho bảng chữ cái A, B, C,…,X, Y, Z ta sẽ dùng các con số 0, 1, 2,…, 24, 25 và dùng các phép toán số học theo modulo 26 để diễn tả các phép biến đổi trên bảng chữ cái. A B C D E F G H I J K L M N 0 1 2 3 4 5 6 7 8 9 10 11 12 13 O P Q R S T U V W X Y Z 14 15 16 17 18 19 20 21 22 23 24 25 2. Mã dịch chuyển (Shift Cipher). Kí hiệu m là tập các số nguyên từ 0 đến (m-1), ký hiệu đó cũng dùng cho vành các số nguyên từ 0 đến (m-1) với các phép cộng Lê Thụy 5
  6. Trường Đại học Dân lập Hải Phòng và nhân với modulo m. Như vậy, bảng chữ cái tiếng Anh có thể xem là một vành 26 với sự tương ứng kể trên. Định nghĩa Mã dịch chuyển: (P, C, K, E, D) P=C=K= 26 với k ∈ K, định nghĩa ek(x) = (x + k) mod 26 dk(y) = (y – k) mod 26 (x, y ∈ 26) Ví dụ: Dùng khoá k = 9 để mã hoá dòng thư: “hentoithubay” dòng thư đó tương ứng với dòng số: h e n t o i t h u b a y 7 4 13 19 14 8 19 7 20 1 0 24 qua phép mã hoá e9 sẽ được: 16 13 22 2 23 17 2 16 3 10 9 7 q n w c x r c q d k j h bản mã sẽ là: “qnwcxrcqdkjh” Nhận được bản mã đó, dùng d9 để nhận được bản rõ. Cách đây 2000 năm mã dịch chuyển đã được Julius Ceasar sử dụng, với khoá k=3 mã địch chuyển được gọi là mã Ceasar. Tập khoá phụ thuộc vào m với m là số khoá có thể. Trong tiếng Anh tập khoá chỉ có 26 khoá có thể, việc thám mã có thể được thực hiện bằng cách duyệt tuần tự 26 khoá đó, vì vậy độ an toàn của mã dịch chuyển rất thấp. Lê Thụy 6
  7. Chương 2 - Lý thuyết Mật mã và An toàn thông tin 3. Mã thay thế (Substitution Cipher). Khoá của mã thay thế là một hoán vị của bảng chữ cái. Gọi S(E) là tập hợp tất cả các phép hoán vị các phần tử của E. Định nghĩa Mã thay thế: (P, C, K, E, D) P=C= 26, K=S( 26) Với mỗi л ∈ K, tức là một hoán vị trên 26, ta xác định eл(x) = л(x) dл(y) = л-1(y) với x, y ∈ 26, л-1 là nghịch đảo của л Ví dụ: л được cho bởi (ở đây ta viết chữ cái thay cho các con số thuộc 26): a b c d e f g h i j k l m n x n y a h p o g z q w b t s o p q r s t u v w x y z f l r c v m u e k j d i bản rõ: “hentoithubay” sẽ được mã hoá thành bản mã (với khoá л): “ghsmfzmgunxd” Dễ xác định được л-1, và do đó từ bản mã ta tìm được bản rõ. Mã thay thế có tập hợp khoá khá lớn - bằng số các hoán vị trên 26 bảng chữ cái, tức số các hoán vị trên 26, hay là 26!, lớn hơn 4.10 . Việc duyệt toàn bộ các hoán vị để thám mã là rất khó, ngay cả đối với máy tính. Tuy nhiên, ta sẽ thấy có những phương pháp thám mã khác dễ dàng thực hiện, và do đó mã thay thế cũng không thể được xem là an toàn. Lê Thụy 7
  8. Trường Đại học Dân lập Hải Phòng 4. Mã Apphin (Apphin Cipher). Phép lập mã được cho bởi một hàm Apphin dạng: e(x) = ax + b mod 26 trong đó a, b ∈ 26 (chú ý: nếu a = 1 ta có mã dịch chuyển) Để có được phép giải mã tương ứng, tức để cho phương trình ax + b = y mod 26 có nghiệm x duy nhất (với bất kỳ y ∈ 26 cho trước), hay nói cách khác hàm Apphin phải là đơn ánh. Theo một định lý số học, điều kiện cần và đủ là a nguyên tố với 26, tức là (a, 26) = 1. Ở đây (a, 26) ký hiệu cho ước số chung lớn nhất của a và 26. Khi (a, 26) = 1 thì có số a-1 ∈ 26 sao cho a.a-1 = a-1.a = 1 mod 26, và do đó, Nếu: y = ax + b mod 26 ax = y – b mod 26 a-1.ax = a-1.(y – b) mod 26 (a-1.a)x = a-1.(y – b) mod 26 x = a-1.(y – b) mod 26 ⇒ d(x) = a-1.(y – b) mod 26 Định nghĩa Mã Apphin: (P, C, K, E, D) P=C= 26, K = { (a, b) ∈ 26 x 26 : (a, 26) = 1 } với mỗi k = (a, b) ∈ K ta định nghĩa: ek(x) = ax + b mod 26 dk(y) = a-1(y – b) mod 26 trong đó x, y ∈ 26 Lê Thụy 8
  9. Chương 2 - Lý thuyết Mật mã và An toàn thông tin Có những thuật toán để thử tính chất (a, m) = 1, và tính a-1 mod m khi (a, m) = 1, ta sẽ trình bầy trong phần sau. Tuy nhiên, với m = 26, ta dễ thử rằng các số a sao cho (a, 26) = 1 là: 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 Ví dụ: Lấy k = (5, 6). Bản rõ: “hentoithubay” h e n t o i t h u b a y x 7 4 13 19 14 8 19 7 20 1 0 24 y = 5x + 6 mod 26 y 15 0 19 23 24 20 23 15 2 11 6 22 p a t x y u x p c l g w Bản mã: “patxyuxpclgw” Thuật toán giải mã trong trường hợp này có dạng: dk(y) = 21(y − 6) mod 26 Với mã Apphin, số các khoá có thể có bằng (số các số ≤ 26 và nguyên tố với 26) × 26, tức là 12 × 26 = 312. Việc thử tất cả các khoá để thám mã trong trường hợp này tuy khá mất thì giờ nếu tính bằng Lê Thụy 9
  10. Trường Đại học Dân lập Hải Phòng tay, nhưng không khó khăn gì nếu dùng máy tính. Do vậy, mã Apphin cũng không phải là mã an toàn. 5. Mã Vigenēre (Vigenēre Cipher). Mã lấy tên của Blaise de Vigenēre, sống vào thế kỷ 16. Khác với các mã trước, mã Vigenēre không thực hiện trên từng ký tự một, mà được thực hiện trên từng bộ m ký tự (m là số nguyên dương). Định nghĩa Mã Vigenēre: (P, C, K, E, D) Cho m là số nguyên dương. m P=C=K= 26 với mỗi khoá k = (k1, k2,…,km) ∈ K có: ek(x1, x2,…, xm) = (x1 + k1, x2 + k2,…, xm + km) dk(y1, y2,…, ym) = (y1 – k1, y2 – k2,…, ym – km) các phép cộng phép trừ điều lấy theo modulo 26 Ví dụ: Giả sử m = 6 và khoá k là từ CIPHER - tức k=(2, 8, 15, 7, 4, 17). Bản rõ: “hentoithubay” h e n t o i t h u b a y x 7 4 13 19 14 8 19 7 20 1 0 24 k 2 8 15 7 4 17 2 8 15 7 4 17 y 9 12 2 0 18 25 21 15 9 8 4 15 j m c a s z v p j i e p Bản mã: Lê Thụy 10
  11. Chương 2 - Lý thuyết Mật mã và An toàn thông tin “jmcaszvpjiep” Từ bản mã đó, dùng phép giải mã dk tương ứng, ta lại thu được bản rõ. Chú ý: Mã Vigenēre với m = 1 sẽ trở thành mã Dịch chuyển. Tập hợp các khoá trong mã Vigenēre mới m ≥ 1 có tất cả là 26m khoá có thể có. Với m = 6, số khoá đó là 308.915.776, duyệt toàn bộ chừng ấy khoá để thám mã bằng tính tay thì khó, nhưng với máy tính thì vẫn là điều dễ dàng. 6. Mã Hill (Hill Cipher). Mã này được đề xuất bởi Lester S.Hill năm 1929. Mã cũng được thực hiện trên từng bộ m ký tự, mỗi ký tự trong bản mã là một tổ hợp tuyến tính (trên vành 26) của m ký tự trong bản rõ. Như vậy, khoá sẽ được cho bởi một ma trận cấp m, tức là một phần tử của m×m m×m 26 . Để phép biến đổi tuyến tính xác định bởi ma trận k ∈ 26 có phép nghịch đảo, ma trận k cũng phải có phần tử nghịch đảo k-1 ∈ m×m 26 . Điều kiện cần và đủ để ma trận k có ma trận nghịch đảo là định thức của nó - ký hiệu det(k),- nguyên tố với m. Định nghĩa Mã Hill: (P, C, K, E, D) Cho m là số nguyên dương. m P=C= 26 m×m K={k∈ 26 : (det(k), 26) = 1 } với mỗi k ∈ K định nghĩa: ek(x1, x2,…, xm) = (x1, x2,…, xm).k dk(y1, y2,…, ym) = (y1, y2,…,ym).k-1 Lê Thụy 11
  12. Trường Đại học Dân lập Hải Phòng ⎛ 11 8 ⎞ Ví dụ: Lấy m = 2, và k = ⎜ ⎟ ⎝ 3 7⎠ Với bộ 2 ký tự (x1, x2), ta có mã là (y1, y2) = (x1, x2). k được tính bởi y1 = 11.x1 + 3.x2 y2 = 8.x1 + 7.x2 Giả sử ta có bản rõ: “tudo”, tách thành từng bộ 2 ký tự, và viết dưới dạng số ta được 19 20 | 03 14 , lập bản mã theo quy tắc trên, ta được bản mã dưới dạng số là: 09 06 | 23 18, và dưới dạng chữ là “fgxs”. Chú ý: Để đơn giản cho việc tính toán, thông thường chọn ma trận vuông 2×2. Khi đó có thể tính ma trận nghịch đảo theo cách sau : −1 ⎛a b⎞ ⎛a b ⎞ Giả sử: k = ⎜ ⎟ ta có ma trận nghịch đảo k −1 = ⎜ ⎟ ⎝c d⎠ ⎝c d⎠ ⎛ d −b ⎞ ⎛a b⎞ ⎜ ad − bc −1 ad − bc ⎟ được tính : ⎜ ⎟ =⎜ ⎟ ⎝c d⎠ ⎜ −c a ⎟ ⎜ ⎟ ⎝ ad − bc ad − bc ⎠ Một chú ý là để phép chia luôn thực hiện được trên tập 26 thì nhất thiết định thức của k : det(k) = (ad – bc) phải có phần tử nghịch đảo trên 26, nghĩa là (ad – bc) phải là một trong các giá trị : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, hoặc 25. Đây cũng là điều kiện để ma trận k tồn tại ma trận nghịch đảo. Khi đó: k-1.k = I là ma trận đơn vị (đường chéo chính bằng 1) ⎛ d −b ⎞ ⎛ a b ⎞ ⎛ a b ⎞ ⎜ ad − bc ad − bc ⎟ ⎛ a b ⎞ ⎛ 1 0 ⎞ −1 ⎜ c d ⎟ ⎜ c d ⎟ = ⎜ −c ⎟⎜ ⎟= a ⎟⎝ c d ⎠ ⎜ 0 1⎟ ⎝ ⎠ ⎝ ⎠ ⎜ ⎝ ⎠ ⎜ ⎟ ⎝ ad − bc ad − bc ⎠ Ví dụ: Lê Thụy 12
  13. Chương 2 - Lý thuyết Mật mã và An toàn thông tin ⎛ 11 8 ⎞ Định thức của ⎜ ⎟ là 11 × 7 – 8 × 3 = 1 ≡ 1 mod 26 ⎝ 3 7⎠ −1 ⎛ 11 8 ⎞ ⎛ 7 −8 ⎞ ⎛ 7 18 ⎞ Khi đó : ⎜ ⎟ = ⎜ −3 11 ⎟ ≡ ⎜ 23 11 ⎟ mod 26 ⎝ 3 7⎠ ⎝ ⎠ ⎝ ⎠ Trên đây là một ví dụ đặc biệt vì ma trận có định thức bằng 1, chúng ta sẽ xem xét một ví dụ tìm nghịch đảo của ma trận 2×2 khác. Ví dụ: ⎛9 4⎞ Định thức của ⎜ ⎟ là 9 × 7 – 4 × 5 = 43 ≡ 17 mod 26 ⎝5 7 ⎠ ⎛ 7 −4 ⎞ ⎛9 4⎞ ⎜ 17 −1 17 ⎟ Khi đó : ⎜ ⎟ =⎜ ⎟ mod 26 ⎝5 7 ⎠ ⎜ −5 9 ⎟ ⎜ ⎟ ⎝ 17 17 ⎠ Theo một tính chất toán học ta có: phép chia cho 17 mod 26 sẽ tương đương với phép nhân với phần tử nghịch đảo của 17 mod 26. Với thuật toán trình bầy trong chương một ta có thể tính được phần tử nghịch đảo của 17 trong 26 là 23. Do đó : ⎛ 7 −4 ⎞ ⎜ 17 17 ⎟ ⎛ 7 × 23 −4 × 23 ⎞ ⎜ ⎟ mod 26 ≡ ⎜ ⎟ mod 26 ⎜ −5 9 ⎟ ⎝ −5 × 23 9 × 23 ⎠ ⎜ ⎟ ⎝ 17 17 ⎠ ⎛ 161 −92 ⎞ ⎛ 5 12 ⎞ ≡⎜ mod 26 ≡ ⎜ 15 25 ⎟ mod 26 ⎝ −115 207 ⎟ ⎠ ⎝ ⎠ −1 ⎛9 4⎞ ⎛ 5 12 ⎞ Kết quả : ⎜ ⎟ =⎜ ⎟ ⎝5 7 ⎠ ⎝ 15 25 ⎠ Lê Thụy 13
  14. Trường Đại học Dân lập Hải Phòng Ta không có công thức để đánh giá số khoá k có thể có với m cho trước. Trong mục sau ta sẽ xét một phương pháp thám mã đối với mã Hill. 7. Mã hoán vị (Permutation Cipher). Khác với các mã trước, mã hoán vị không thay đổi các ký tự trong bản rõ mà chỉ thay đổi vị trí các ký tự trong từng bộ m các ký tự của bản rõ. Ta ký hiệu Sm là tập hợp tất cả các phép hoán vị của {1, 2,…, m}. Định nghĩa Mã hoán vị: (P, C, K, E, D) Cho m là số nguyên dương. m P=C= 26 , K = Sm với mỗi k = π ∈ Sm , ta có ek(x1, x2,…, xm) = (xπ(1), xπ(2),…, xπ(m)) dk(y1, y2,…, ym) = ( yπ -1 (1) , yπ -1 (2) ,..., yπ -1 (m) ) trong đó π-1 là hoán vị nghịch đảo của π Ví dụ: Giả sử m = 6, và khoá k được cho bởi phép hoán vị π 1 2 3 4 5 6 3 5 1 6 4 2 Khi đó phép hoán vị nghịch đảo π-1 là: 1 2 3 4 5 6 3 6 1 5 2 4 Bản rõ: “hentoithubay” Lê Thụy 14
  15. Chương 2 - Lý thuyết Mật mã và An toàn thông tin h e n t o i t h u b a y vt 1 2 3 4 5 6 1 2 3 4 5 6 π 1→3 2→5 3→1 4→6 5→4 6→2 1→3 2→5 3→1 4→6 5→4 6→2 vt 3 5 1 6 4 2 3 5 1 6 4 2 n o h i t e u a t y b h Bản mã: “nohiteuatybh” Dùng hoán vị nghịch đảo, từ bản mật mã ta lại thu được bản rõ. Chú ý: Mã hoán vị là một trường hợp riêng của mã Hill. Thực vậy, cho phép hoán vị π của {1, 2,…, m}, ta có thể xác định ma trận Kπ=(kij), với ⎧1 nÕu i = π (j ) kij = ⎨ ⎩0 nÕu ng−îc l¹i thì dễ thấy rằng mã Hill với khoá Kπ trùng với mã hoán vị với khoá π. Với m cho trước, số các khoá có thể có của mã hoán vị là m! Dễ nhận thấy với m = 26 ta có số khóa 26! (mã Thay thế) Lê Thụy 15
  16. Trường Đại học Dân lập Hải Phòng II. Thám mã đối với hệ mật mã cổ điển. Như chúng ta đã biết, hệ mã cổ điển là những hệ mã được sử dụng từ rất lâu, lúc mà khả năng tính toán của các hệ thống chưa phát triển vì thế các quy tắc được áp dụng trong các hệ mã là rất đơn giản. Chủ yếu dựa trên hai phương pháp dịch chuyển và thay thế. Độ an toàn của các hệ mã này không chỉ phụ thuộc vào khoá mà còn phụ thuộc cả vào sơ đồ mã hoá được sử dụng (dó đó cần giữ bí mật cả sơ đồ mã hoá và khoá lập mã). Với sáu loại mã cổ điển chúng ta đã xét, thấy rằng miền giá trị khoá có thể của các hệ mã đó bị giới hạn, khi đó với khả năng tính toán của các máy tính hiện nay, miền giá trị khoá có thể được vét cạn trong một khoảng thời gian rất ngắn. Nhưng phương pháp này không tối ưu trong nhiều trương hợp vì phải duyệt tất cả các bộ khoá trong miền khoá. Một phương pháp được dùng nhiều trong kỹ thuật thám mã đó là phương pháp sắc xuất thống kê (xác định tần suất xuất hiện của các ký tự trong bản mã). Trong hầu hết các ngôn ngữ tự nhiên, các văn bản được trình bầy dưới dạng các chữ cái với tần suất xuất hiện khác nhau. Ví dụ: trong tiếng Anh tần suất xuất hiện của chữ E là cao nhất với sắc xuất xuất hiện là 0,127. 0.14 0.12 0.1 Xắc suất 0.08 0.06 0.04 0.02 0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Bảng xắc suất xuất hiện của các k ý tự trong tiếng Anh Từ bảng trên có thể phân 26 chữ cái thành 5 nhóm như sau: Lê Thụy 16
  17. Chương 2 - Lý thuyết Mật mã và An toàn thông tin E: có xác suất khoảng 0,127 T, A, O, I, N, S, H, R: có xác suất khoảng 0,06 đến 0,09 D, L: mỗi ký tự có xác suất chừng 0,04 C, U, M, W, F, G, Y, P, B: có xác suất khoảng 0,015 đến 0,023 V, K, J, X, Q, Z: mỗi ký tự có xác suất nhỏ hơn 0,01 Việc xem xét các dãy gồm 2 hoặc 3 ký tự liên tiếp (được gọi là bộ đôi - Diagrams và bộ ba - Trigrams) cũng rất hữu ích. Có 30 bộ đôi thông dụng nhất (theo hứ tự giảm dần) là: TH, HE, IN, ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS, OR, TI, IS, ET, IT, AR, TE, SE, HI và OF. Có 12 bộ ba thông dụng nhất (theo thứ tự giảm dần) là: THE, ING, AND, HER, ERE, ENT, THA, NTH, WAS, ETH, FOR và DTH. Tuy nhiên việc thám mã nói chung đều thực hiện qua 4 bước: - Xác định ngôn ngữ được sử dụng. (bản rõ – bản mã). - Xác định hệ thống nói chung được sử dụng. - Xây dựng lại khoá của mật mã sử dụng trong hệ thống. - Xây dựng lại bản gốc. (bản rõ) Các hình thức tấn công vào hệ mã: - Chỉ biết bản mã: Kẻ thám mã chỉ có trong tay bản mã. - Biết bản rõ: Kẻ thám mã biết được một mẫu của bản rõ và phần mã tương ứng của bản rõ đó. - Chọn bản rõ: Kẻ thám mã có thể tạm thời tước quyền điều khiển hệ thống, rồi chọn bản rõ và xây dựng bản mã tương ứng. - Chọn bản mã: Kẻ thám mã tạm thời điều khiển hệ thống, rồi chọn bản mã và xây dựng lại bản rõ tương ứng. Lê Thụy 17
  18. Trường Đại học Dân lập Hải Phòng III. Mã dòng (Stream Cipher). Trong các hệ mật mã được xét cho đến nay, ta dùng cùng một khoá k để mã hoá các ký tự (hay các bộ m ký tự) trong bản rõ. Điều khác cơ bản của mã dòng là sinh ra một dòng khoá z = z1z2… và dùng chúng để mã hoá các ký tự ở các vị trí khác nhau trong bản rõ x = x1x2… cụ thể là bản mã được xác định bởi: y = y1y2… = ez1(x1)ez2(x2)… Một cách tổng quát, mã dòng được định nghĩa như sau: Định nghĩa 1.2: Một hệ mã dòng là một bộ (P, C, K, L, F, E, D) thoả mãn các điều kiện sau đây: + P là một tập hữu hạn các bản rõ. + C là một tập hữu hạn các bản mã. + K là một tập hữu hạn các khoá chính. + L là một tập hữu hạn các khoá dòng. i-1 i-1 + F = {f1, f2, …} là bộ sinh khoá dòng; fi = K × L ×P → L + Với mỗi z ∈ L có một hàm lập mã ez ∈ E: P → C và một hàm giải mã dz ∈ D : C → P sao cho dz(ez(x)) = x với mọi x ∈ P Nếu bộ sinh dòng khoá không phụ thuộc vào bản rõ, thì ta gọi mã dòng đó là đồng bộ, trong trường hợp đó, K như là hạt giống để sinh ra dòng khoá z1, z2, …. Nếu zi+d = zi thì mã dòng được gọi là tuần hoàn chu kỳ d. Trong thực tế, mã dòng thường được dùng với các văn bản nhị phân, tức là: P=C= 2 = {0, 1}, các phép lập mã và giải mã là: ez(x) = x + z mod 2 dz(y) = y + z mod 2 Lê Thụy 18
  19. Chương 2 - Lý thuyết Mật mã và An toàn thông tin Ví dụ: Một loại mã dòng thường được sử dụng khi dòng khoá được sinh ra bởi một hệ thức truy toán. Trong trường hợp này, k = (k1, m k2,…, km) ∈ Z 2 , và dòng khoá được xác định bởi: zi = ki (1 ≤ i ≤ m) zi = c1zi-m + … + cmzi-1 mod 2 (i > m) Nếu khéo chọn, ta có thể thu được dòng khoá tuần hoàn với chu kỳ lớn nhất là 2m – 1. Chẳng hạn, với m = 4 và dòng khoá sinh ra bởi luật: zi = zi-4 + zi-3 mod 2 ( i > 4) ta sẽ được, với mọi k = (z1, z2, z3, z4) ≠ (0, 0, 0, 0) là khoá chính, một dòng khoá có chu kỳ 15. Với k = (1, 0, 0, 0) ta sẽ được dòng khoá: 100010011010111100010… Mã dòng sinh ra bởi hệ thức truy toán có thể được thực hiện bằng phần cứng khi dùng một thanh ghi chuyển dịch liên hệ ngược tuyến tính. Thanh ghi tương ứng với hệ mã cụ thể nói trên có sơ đồ là: + k1 k2 k3 k4 Chú ý: Mã Vigenēre với độ dài khoá m có thể được coi là mã dòng, có chu kỳ m với cách lập mã và giải mã theo mã dịch chuyển. Ví dụ: Một ví dụ đơn giản của mã dòng không đồng bộ là mã Autokey, cho bởi: Định nghĩa Mã Autokey: (P, C, K, L, F, E, D) P=C=K=L= 26 Dòng khoá sinh bởi: Lê Thụy 19
  20. Trường Đại học Dân lập Hải Phòng z1 = k, zi = xi-1 (i ≥ 2), xi là ký tự thứ i của bản rõ. Các hàm lập mã và giải mã là: ez(x) = x + z mod 26 dz(y) = y – z mod 26 Với khoá k = 8 và bản rõ là: “rendezvous” r e n d e z v o u s x 17 4 13 3 4 25 21 14 20 18 Ta có dòng khoá tương ứng là: 8 17 4 13 3 4 25 21 14 20 18 Do đó bản mã dưới dạng số là: y 25 21 17 16 7 3 20 9 8 12 z v r q h d u j i m Khi giải mã ta sẽ giải từng ký tự, và tìm lần lượt z1 = k, x1 = y1 + z1 z2 = x1, x2 = y2 + z2 z3 = x2, x3 = y3 + z3 … Ta sẽ có lại được bản rõ. Lê Thụy 20
Theo dõi chúng tôi
Đồng bộ tài khoản