An toàn bảo mật thông tin - Chương 2: Hệ mật mã khóa đối xứng

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) 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 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 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. Bộ mã hoá Bộ giải mã Phân tích mật mã Kênh công cộng Kênh an toàn Bản tin gốc (M) Bản tin gốc (M) Các bản tin mật mã M’ A☺ B☺ C / - 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 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 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 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 bảng chữ cái, tức số các hoán vị trên ] 26, hay là 26!, lớn hơn 4.1026. 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 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 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 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. P = C = K = ] 26m 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 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 ] 26m m× . Để phép biến đổi tuyến tính xác định bởi ma trận k ∈ ] 26m m× có phép nghịch đảo, ma trận k cũng phải có phần tử nghịch đảo k-1 ∈ ] 26m m× . Đ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. P = C = ] 26m K = { k ∈ ] 26m m× : (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 Trường Đại học Dân lập Hải Phòng Ví dụ: Lấy m = 2, và 11 8k 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 : Giả sử: ta có ma trận nghịch đảo a b k c d ⎛= ⎜⎝ ⎠ ⎞⎟ 1 1 a bk c d − − ⎛ ⎞= ⎜ ⎟⎝ ⎠ được tính : 1 d b a b ad bc ad bc 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) 1 d b a b a b a b 1 0ad bc ad bc c d c d c a c d 0 1 ad bc ad bc − −⎛ ⎞⎜ ⎟⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛− −= =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜−⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝⎜ ⎟⎜ ⎟− −⎝ ⎠ ⎞⎟⎠ Ví dụ: Lê Thụy 12 Chương 2 - Lý thuyết Mật mã và An toàn thông tin Định thức của là 11 11 8 3 7 ⎛⎜⎝ ⎠ ⎞⎟ ×7 – 8×3 = 1 ≡ 1 mod 26 Khi đó : 111 8 3 7 −⎛ ⎞⎜ ⎟⎝ ⎠ = 7 8 3 11 −⎛ ⎞⎜ ⎟−⎝ ⎠ ≡ mod 26 7 18 23 11 ⎛ ⎞⎜⎝ ⎠⎟ 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ụ: Định thức của là 9 9 4 5 7 ⎛ ⎞⎜ ⎟⎝ ⎠ ×7 – 4×5 = 43 ≡ 17 mod 26 Khi đó : = 19 4 5 7 −⎛ ⎞⎜ ⎟⎝ ⎠ 7 4 17 17 5 9 17 17 −⎛ ⎞⎜ ⎟⎜ −⎜ ⎟⎜ ⎟⎝ ⎠ ⎟ mod 26 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 5 9 17 17 −⎛ ⎞⎜ ⎟⎜ −⎜ ⎟⎜ ⎟⎝ ⎠ ⎟ mod 26 ≡ 7 23 4 23 5 23 9 23 × − ×⎛ ⎞⎜ ⎟− × ×⎝ ⎠ mod 26 ≡ mod 26 ≡ mod 26 161 92 115 207 −⎛ ⎞⎜ ⎟−⎝ ⎠ 5 12 15 25 ⎛⎜⎝ ⎠ ⎞⎟ Kết quả : 19 4 5 7 −⎛ ⎞⎜ ⎟⎝ ⎠ = 5 12 15 25 ⎛ ⎞⎜ ⎟⎝ ⎠ Lê Thụy 13 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. P = C = ] , K = S26m m với mỗi k = π ∈ Sm , ta có ek(x1, x2,…, xm) = (xπ(1), xπ(2),…, xπ(m)) dk(y1, y2,…, ym) = π π π-1 -1 -1( 1 ) ( 2 ) ( m )( y , y ,..., y ) 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 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 ( ) ij 1 i k 0 jπ=⎧= ⎨⎩ nÕu 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 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. Bảng xắc suất xuất hiện của các ký tự trong tiếng Anh 0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 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 Xắ c su ất Từ bảng trên có thể phân 26 chữ cái thành 5 nhóm như sau: Lê Thụy 16 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 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. + F = {f1, f2, …} là bộ sinh khoá dòng; fi = K × L i-1 × P i-1 → 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 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, k2,…, km) ∈ Z , và dòng khoá được xác định bởi: 2m 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 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 Chương 2 - Lý thuyết Mật mã và An toàn thông tin IV. Mã khối (Block cipher) Mật mã khối được cấu trúc trên nguyên tắc là bản tin được chia thành các khối có độ dài bằng nhau và việc mã hoá tiến hành theo từng khối độc lập nhau. Trong môi trường máy tính độ dài của khối được tính bằng bit. Độ bảo mật của mã trong trường hợp này phụ thuộc vào độ dài của khối và độ phức tạp của thuật toán mã. Nếu kích cỡ của khối quá bé thì việc giải mã không mấy khó khăn do dò tìm được đặc tính cấu trúc thống kê của bản tin rõ. Nếu tăng kích thước khối thì mức độ cấu trúc thống kê cũng tăng theo số mũ và nếu kích cỡ khối tiến đến đoạn tin thì tác dụng mã khối sẽ giảm. Các phương pháp ứng dụng của mật mã khối Mật mã khối xử lý các khối dữ liệu có độ dài cố định và độ dài bản tin có thể bất kỳ. Có bốn phương pháp ứng dụng mã khối thường gặp trong hệ thống truyền tin và số liệu truyền tin: • Phương pháp dùng từ điển điện tử, còn gọi là mật mã ECB (Electronic CodeBook) • Phương pháp móc xích các khối đã được mã hoá, còn gọi là mật mã CBC (Cipher Block Chaining) • Phương pháp phản hồi bản tin đã mã hoá, còn gọi là mật mã CFC (Cipher feedblack) • Phương pháp phản hồi đầu ra, còn gọi là OFC (Output Feedblack) Các phương pháp ứng dụng của mật mã khối trên được phát triển mạnh sau khi xuất hiện mã DES. Trên thưc tế có thể có những phương pháp khác, nhưng bốn phương pháp trên được ứng dụng phổ biến và cũng khá đầy đủ. 1. Mã hóa DES (Data Encryptiton Standard) Lê Thụy 21 Trường Đại học Dân lập Hải Phòng Hệ mật mã chuẩn DES được xây dựng tại Mỹ trong những năm 70, theo yêu cầu của văn phòng quốc gia về chuẩn (NBS) và được sự thẩm định của cục an ninh quốc gia Mỹ (NASA). Ngày 15/05/1973, NBS công bố một yêu cầu công khai về một thuật toán mật mã chuẩn, mà các đòi hỏi chính là: - Thuật toán phải có độ an toàn cao. - Thuật toán phải được định nghĩa đầy đủ và hoàn toàn dễ hiểu. - Độ an toàn phải nằm ở khoá, độ an toàn phải không phụ thuộc vào sự bí mật của thuật toán. - Thuật toán phải sẵn sàng cung cấp cho mọi người dùng. - Thuật toán phải thích nghi được với việc dùng cho các ứng dụng khác nhau. - Thuật toán phải cài đặt được một cách tiết kiệm trong các thiết bị điện tử. - Thuật toán phải được sử dụng được có hiệu quả. - Thuật toán phải có khả năng được hợp thức hoá. - Thuật toán phải xuất khẩu được. Hồi đó, không có cơ quan nào đáp ứng được yêu cầu đó. Năm sau, ngày 27/04/1974 yêu cầu đó lại được nhắc lại. Và lần này, IBM chấp nhận dự tuyển với sản phẩm sẽ được đệ trình dựa trên một thuật toán mà IBM đã phát triển trước đó là LUCIPHER. DES được công bố lần đầu tiên vào 17/03/1975. Sau nhiều tranh luận, DES được chấp nhận như một chuẩn liên bang vào 23/11/1976 và được công bố ngày 15/01/1977. Sau đó, vào năm 1980 công bố “Các cách dùng DES”. DES được cài đặt cả với tư cách như một thiết bị cứng, cả với tư cách như một phần mềm, và được sử dụng rộng rãi trong khu vực hành chính, kinh tế, đặc biệt trong các hệ thống ngân hàng. NBS về nguyên tắc cứ khoảng 5 năm lại xét lại hệ mã một lần, do vậy các hệ mã chuẩn của Mỹ luôn được nâng cấp. Lê Thụy 22 Chương 2 - Lý thuyết Mật mã và An toàn thông tin DES là một hệ mật mã khóa đối xứng được sử dụng rộng rãi nhất do tính an toàn cao của nó. Như đã biết hệ mật mã khóa đối xứng là hệ mã mà quá trình tạo mã và giải mã đều sử dụng chung một khoá. Thuật toán DES là sự kết hợp được lựa chọn cẩn thận của hai quá trình cơ bản của mật mã là thay thế và hoán vị. Mô tả thuật toán DES. Thuật toán được thiết kết để lập mã và giải mã một khối dữ liệu nhị phân 64 bits với sự kết hợp của một khóa 64 bits. Quá trình giải mã thực hiện theo một sơ đồ như quá trình lập mã, chỉ có khác là trật tự khóa được đảo lại so với quá trình lập mã. Một khối dữ liệu 64 bits được mã hóa bằng việc cho qua một bảng hoán vị ban đầu (IP – Initial Permutation) sau đó qua một quá trình tính toán phức tạp có sự tham gia của khóa k được thực hiện, và cuối cùng bản mã nhận được sau khi qua một bảng hoán vị nghịch đảo (IP-1 – Inverse of the Initial Permutation). Lê Thụy 23 Trường Đại học Dân lập Hải Phòng Lê Thụy 24 Chương 2 - Lý thuyết Mật mã và An toàn thông tin Quá trình mã hóa: 64 bits của khối dữ liệu đầu vào được hoán vị bằng bảng IP. Trong đó bit thứ 58 của khối dữ liệu vào là bit đầu tiên, bit thứ 50 của khối dữ liệu vào là bit thứ 2,… và bit cuối cùng của khối dữ liệu sau khi hoán vị là bit thứ 7 của khối dữ liệu vào. Kết quả của phép hoán vị ban đầu sẽ được chia thành 2 nửa L0R0 (L0 = 32 bits là nửa trái, R0 = 32 bits là nửa phải) sau đó thực hiện 16 lần lặp liên tiếp theo phương pháp: Li = Ri-1 Ri = Li-1 ⊕ ƒ(Ri-1 , Ki) và nhận được L16R16 . Trong đó ƒ được gọi là hàm mật mã. Hàm ƒ có hai đối là hai khối bits, một là Ri-1 32 bits, hai là Ki 48 bits. Ki nhận được từ sơ đồ tạo khóa sẽ được trình bầy dưới đây. Li-1 Ri-1 (32 bit) (32 bit) Kết quả của 16 lần lặp liên tiếp là một khối 64 bits (R16L16) được gọi là dữ liệu tiền kết quả (preoutput), khối 64 bits này được cho qua một hoán vị nghịch đảo IP-1. Trong đó bit thứ 40 của khối dữ liệu tiền kết quả là bit đầu tiên, bit thứ 8 của khối dữ liệu tiền kết quả là bit thứ 2,… và bit cuối cùng sau khi hoán vị là bit thứ 25 của khối dữ liệu tiền kết quả trên. Cuối cùng sau phép hoán vị nghịch đảo ta nhận được bản mã. ƒ Ri (32 bit) Li Ki (48 bit) (32 bit) Lê Thụy 25 Trường Đại học Dân lập Hải Phòng Hàm mật mã ƒ (the cipher function ƒ) Hàm ƒ được tính như sau: ƒ(Ri-1, Ki) = P(S(E(Ri-1) ⊕Ki)) Hàm E là một hoán vị mở rộng. Hàm E thực hiện chức năng mở rộng khối 32 bits thành một khối 48 bits. E(R) có ba bits đầu lần lượt là các bit thứ 32, 1 và 2 của R,… 2 bits cuối của E(R) là bit 32 và bit 1 của R. Lê Thụy 26 Chương 2 - Lý thuyết Mật mã và An toàn thông tin Sau đó tính E(R) ⊕K với K là khóa 48 bits. Kết quả của phép cộng modulo 2 này sẽ được viết thành 8 nhóm, mỗi nhóm 6 bits dạng B = B1BB2B3B BB4B5B BB6B7B BB8. Mỗi nhóm Br B 6 bits (1 ≤ r ≤ 8) đó được đưa qua một hộp đen Sr (S1 S2 … S8) để nhận được Sr(Br) 4 bits đầu ra. Mỗi hộp Sr là một ma trận 4 x 16 trong đó mỗi phần tử của Sr là một số nguyên nằm trong khoảng 0 → 15 (có thể biểu diễn tối đa bởi 4 bit nhị phân). Với mỗi BBr = b1b2b3b4b5b6 là các bit của Br B , ta tính Sr(Br) như sau: b1b6 là biểu diễn nhị phân của số hiệu hàng i trong Sr , b2b3b4b5 là biểu diễn nhị phân của số hiệu cột j trong Sr . Cr = Sr(Br) là phần tử tại hàng i và cột j của Sr . Ví dụ ta tính S1(B) với B = 011011(2) thì hàng i = 01(b) = 1(d), cột j = 1011(b) = 13(d) . Xác định tại hộp S1 giá trị tại hàng 1, cột 13 có giá trị là 5 do đó C = 5(d) = 0101(b). C = C1C2C3C4C5C6C7C8 (32 bits) được cho qua một hoán vị P và nhận được kết quả của hàm ƒ: ƒ = P(C) Lê Thụy 27 Trường Đại học Dân lập Hải Phòng Lê Thụy 28 Chương 2 - Lý thuyết Mật mã và An toàn thông tin Sơ đồ tính khóa (Computation of Key Schedule) K PC1 C0 D0 LeftShift K1 Ki K16 C1 D1 Ci Di C16 D16 LeftShift PC2 LeftShifts LeftShifts PC2 PC2 LeftShifts LeftShifts Lê Thụy 29 Trường Đại học Dân lập Hải Phòng 2. Mã TDEA (Triple Data Encryption Algorithm) Cho DESk(I) và DES-1k(I) tương ứng là hàm lập mã và hàm giả mã của I theo thuật toán DES với khóa k tách biệt. Mỗi quá trình Mã hóa/Giải mã TDEA (Triple Data Encryption Algorithm) là hợp của các phép mã hóa và giải mã DES. Phép mã hóa TDEA : Chuyển bản rõ I 64 bits, thành bản mã O 64 bits tương ứng được định nghĩa như sau : O = DESk3( DES-1k2( DESk1( I ))) Phép giải mã TDEA : Chuyển bản mã O 64 bits, thành bản rõ I 64 bits tương ứng được định nghĩa như sau : I = DES-1k1( DESk2( DES-1k3(O))) DES-1DES DES Xác định bộ khóa (k1, k2, k3) có thể có các lựa chọn sau: • Lựa chọn 1: khóa k1, k2 và k3 là các khóa độc lập. • Lựa chọn 2: khóa k1, k2 độc lập và k3 = k1. • Lựa chọn 3: k1 = k2 = k3 3. Mã AES (Advanced Encryption Standard). Chuẩn này xác định thuật toán Rijnbaen, là một trong những mã khối đối xứng để xử lý một khối dữ liệu 128 bits, có sử dụng khóa mật mã có độ dài 128, 192 và 256 bits DES DES-1DES-1 I O k1 k2 k3 Lê Thụy 30