Khóa luận Phân tích hệ thám mã vigenere

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trịnh Thị Dịu PHÂN TÍCH HỆ THÁM MÃ VIGENERE KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin HÀ NỘI - 2009 ii ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Trịnh Thị Dịu PHÂN TÍCH HỆ THÁM MÃ VIGENERE KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn:Tiến sĩ.Hồ Văn Canh HÀ NỘI - 2009 iii LỜI CẢM ƠN Sau thời gian học tập tại trường bằng sự nỗ lực của bản thân cùng với sự chỉ bảo dạy dỗ tận tình của các thầy cô trong trường Đại học công nghệ nói chung và các thầy cô trong Khoa nói riêng em đã tích luỹ được nhiều kiến thức bổ ích trang bị cho công việc của một cử nhân tương lai. Luận văn tốt nghiệp là kết quả của sự cố gắng trong suốt 4 năm học tập và tìm hiểu kiến thức tại trường , đó là sự đánh giá tổng kết công tác học tập trong suốt thời gian qua của mỗi sinh viên. Trong thời gian luận văn tốt nghiệp này em đã được sự giúp đỡ nhiệt tình của các thầy cô giáo trong bộ môn. Em xin gửi lời cảm ơn sâu sắc tới các thầy cô những người đã trang bị cho chúng em hành trang kiến thức, đặc biệt thầy: Hồ Văn Canh đã tận tình giúp em hoàn thành luận văn. Do thời gian tiến hành làm luận văn và trình độ lý thuyết cũng như các kinh nghiệm thực tế còn có hạn nên trong luận văn này chắc chắn sẽ không tránh khỏi những thiếu sót . Em xin kính mong các thầy cô chỉ bảo để em có thể hoàn thiện hơn luận văn cũng như kiến thức chuyên môn của mình. Em xin chân thành cảm ơn ! Hà Nội, tháng 05 năm 2009. Sinh viên : Trịnh Thị Dịu. iv TÓM TẮT NỘI DUNG Nội dung của khóa luận là tìm hiểu về hệ mã hóa Vigenere nổi tiếng, nó được phát minh vào thế kỷ thứ 16 và được viết đầu tiên bởi nhà ngoại giao Pháp Blaise de Vigenère. Trước hết ta đi tìm hiểu về một vài hệ mã hóa cổ điển như hệ mã hóa truyền thống mã thay thế, mã dịch chuyển, mã affine, mã caesar, (hay chúng còn được gọi là hệ mã hóa đơn biểu). Đặc biệt đi sâu vào tìm hiểu hệ mã hóa Vigenere (hệ mã hóa đa biểu) để làm rõ hơn độ an toàn của hệ mật mã này so với các hệ mật mã trên. Đồng thời, làm rõ thêm tính chất của hệ mã hóa Vigenere và cách thức mã hóa và thám mã khi có khóa cho trước. Trong đó, đi nghiên cứu về tần số đơn, tần số đôi, tần số ba và cả sự trùng lặp trong bản rõ và bản mã. Đó cũng là một cách thám mã hiệu quả. Cách phá mã khi không có khóa cho trước, khi đó ta cần thực hiện 2 bước: đầu tiên là tìm chu kỳ khóa, sau đó thám mã, trong đó sử dụng hai cách là thám mã nổi tiếng là của Kasiski và dùng chỉ số trùng khớp. Cuối cùng là chương trình mô tả về toàn bộ cách mã hóa, thám mã khi có khóa và khi không có khóa.( Là chương trình đính kèm theo Vigenere.c). v MỤC LỤC Lời mở đầu................................................................................................................1 Chương 1: Hệ mật mã truyền thống ......................................................................4 1.1 Mở đầu – một số hệ mã hóa đơn giản .............................................................................. 4 1.1.1 Định nghĩa về hệ mật mã ....................................................................................4 1.1.2.Một số loại mã hóa truyền thống như ..................................................................5 1.2. Mã Vigenere và các đặc tính của nó ............................................................................. 11 1.2.1 Định nghĩa..........................................................................................................11 1.2.2 Tính chất.............................................................................................................12 1.3.Phương pháp mã hóa và giải mã Vigenere(khi có khóa cho trước) ........................... 13 1.3.1 Mã hóa................................................................................................................13 1.3.2 Giải mã ...............................................................................................................15 1.3.3 Chương trình mã hóa .................................................................................................... 15 1.3.4 Kết luận........................................................................................................................... 16 Chương 2: Phân tích trong trường hợp không có khóa cho trước ...................17 2.1 Những đặc trưng thống kê của bản rõ: Tần số đơn, bộ đôi, trùng lặp ....................... 17 2.1.1 Tần suất của 1 ký tự ...........................................................................................17 2.1.2 Tần suất bộ đôi phổ biến nhất xuất hiện trong tiếng Anh..................................18 2.1.3 Những bộ ba phổ biến nhất ................................................................................19 2.2 Những đặc trưng thống kê của bản mã: Tần số đơn, bộ đôi, trùng lặp...................... 20 2.3. Thống kê của bản mã được mã bởi khóa giả ngẫu nhiên, không có chu kỳ ............ 27 2.3.1 Lý thuyết trùng khớp(coincident theory) ...........................................................27 vi 2.4 Mô tả 2 cách thám mã Vigenere .................................................................................... 31 2.4.1 Phép thử Kasiski ................................................................................................31 2.4.2 Việc xác minh tiếp cho giá trị của m có thể nhận được bằng chỉ số trùng hợp.33 Chương 3: Thực hành phân tích một bản mã Vigenere.....................................34 3.1 Thử với phép thử Kasiski ................................................................................................ 34 3.2 Tính theo chỉ số trùng hợp............................................................................................... 34 Chương 4 Kết Luận và mô tả chương trình nguồn ............................................40 4.1 Mô tả chương trình ........................................................................................................... 40 4.2 Kết luận.............................................................................................................................. 40 Các thuật ngữ ..........................................................................................................41 Danh sách tham khảo .............................................................................................42 1 Lời mở đầu Ngày nay, với sự phát triển mạnh mẽ của công nghệ thông tin việc ứng dụng các công nghệ mạng máy tính trở nên vô cùng phổ cập và cần thiết. Sự ra đời và tiến bộ vượt bậc của nó là bước ngoặt trong lịch sử phát triển của xã hội, đưa thế giới từ kỷ nguyên công nghiệp sang kỷ nguyên thông tin và phát triển kinh tế tri thức. Công nghệ mạng máy tính đã mang lại những lợi ích to lớn. Chúng được áp dụng trong hầu hết các công việc trong mọi lĩnh vực như : chính trị, quân sự, quốc phòng… Sự xuất hiện mạng Internet cho phép mọi người có thể truy cập, chia sẽ và khai thác thông tin một cách dễ dàng và hiệu quả. Các công nghệ E-mail cho phép mọi người có thể gửi thư cho người khác cũng như nhận thư ngay trên máy tính của mình. Gần đây có công nghệ E-business cho phép thực hiện các hoạt động thương mại trên mạng máy tính. Việc ứng dụng các mạng cục bộ trong các tổ chức, công ty hay trong một quốc gia là rất phong phú. Các hệ thống chuyển tiền của các ngân hàng hàng ngày có thể chuyển hàng tỷ đôla qua hệ thống của mình. Các thông tin về kinh tế, chính trị, khoa học xã hội được trao đổi rông rãi. Tuy nhiên lại nảy sinh vấn đề về an toàn thông tin. Đó cùng là một quá trình tiến triển hợp logic: khi những vui thích ban đầu về một siêu xa lộ thông tin, bạn nhất định nhận thấy rằng không chỉ cho phép bạn truy nhập vào nhiều nơi trên thế giới, Internet còn cho phép nhiều người không mời mà tự ý ghé thăm máy tính của bạn. Thực vậy, Internet có những kỹ thuật tuyệt vời cho phép mọi người truy nhập, khai thác, chia sẻ thông tin. Những nó cũng là nguy cơ chính dẫn đến thông tin của bạn bị hư hỏng hoặc phá huỷ hoàn toàn. Có những thông tin vô cùng quan trọng mà việc bị mất hay bị làm sai lệch có thể ảnh hưởng đến các tổ chức, các công ty hay cả một quốc gia. Các thông tin về an ninh quốc gia, bí mật kinh doanh hay các thông tin tài chính là mục tiêu của các tổ chức tình báo nước ngoài về chính trị hay công nghiệp hoặc kẻ cắp nói chung. Bọn chúng có thể làm mọi việc có thể để có được những thông tin quý giá này. Thử tưởng tượng nếu có kẻ xâm nhập được vào hệ thống chuyển tiền của các ngân hàng thì ngân hàng đó sẽ chịu 2 những thiệt hại to lớn như mất tiền có thể dẫn tới bị phá sản. Chưa kể nếu hệ thông thông tin an ninh quốc gia bị đe doạ thì hậu quả không thể lường trước được. [9]Theo số liệu của CERT(Computer Emegency Response Team - “Đội cấp cứu máy tính”), số lượng các vụ tấn công trên Internet được thông báo cho tổ chức này là ít hơn 200 vào năm 1989, khoảng 400 vào năm 1991, 1400 vào năm 1993, và 2241 vào năm 1994. Những vụ tấn công này nhằm vào tất cả các máy tính có mặt trên Internet, các máy tính của tất cả các công ty lớn như AT&T, IBM, các trường đại học, các cơ quan nhà nước, các tổ chức quân sự, nhà băng... Một số vụ tấn công có quy mô khổng lồ (có tới 100.000 máy tính bị tấn công). Hơn nữa, những con số này chỉ là phần nổi của tảng băng. Một phần rất lớn các vụ tấn công không được thông báo, vì nhiều lý do, trong đó có thể kể đến nỗi lo bị mất uy tín, hoặc đơn giản những người quản trị hệ thống không hề hay biết những cuộc tấn công nhằm vào hệ thống của họ. Không chỉ số lượng các cuộc tấn công tăng lên nhanh chóng, mà các phương pháp tấn công cũng liên tục được hoàn thiện. Điều đó một phần do các nhân viên quản trị hệ thống được kết nối với Internet ngày càng đề cao cảnh giác. Cũng theo CERT, những cuộc tấn công thời kỳ 1988-1989 chủ yếu đoán tên người sử dụng-mật khẩu (UserID- password) hoặc sử dụng một số lỗi của các chương trình và hệ điều hành (security hole) làm vô hiệu hệ thống bảo vệ, tuy nhiên các cuộc tấn công vào thời gian gần đây bao gồm cả các thao tác như giả mạo địa chỉ IP, theo dõi thông tin truyền qua mạng, chiếm các phiên làm việc từ xa (telnet hoặc rlogin). Để vừa bảo đảm tính bảo mật của thông tin lại không làm giảm sự phát triển của việc trao đổi thông tin quảng bá trên toàn cầu thì một giải pháp tốt nhất là mã hoá thông tin. Có thể hiểu sơ lược mã hoá thông tin là che đi thông tin của mình làm cho kẻ tấn công nếu chặn được thông báo trên đường truyền thì cũng không thể đọc được và phải có một giao thức giữa người gửi và người nhận để có thể trao đổi thông tin, đó là các cơ chế mã và giải mã thông tin. Ngày nay thì việc mã hoá đã trở nên phổ cập. Các công ty phần mềm lớn trên thế giới đều có nghiên cứu và xây dựng các công cụ, thuật toán mã hoá để áp dụng cho thực tế. Mỗi quốc gia hay tổ chức đều có những cơ chế mã hoá riêng để bảo vệ hệ thống thông tin của mình. Một số vấn đề an toàn đối với nhiều mạng hiện nay: 3 Một người dùng chuyển một thông báo điện tử cho một người sử dụng khác. Một bên thứ ba trên cùng mạng LAN này sử dụng một thiết bị nghe trộm gói để lấy thông báo và đọc các thông tin trong đó. Cũng trong tình huống trên bên thứ ba chặn thông báo, thay đổi các thành phần của nó và sau đó lại gửi cho người nhận. Người nhận không hề nghi ngờ gì trừ khi nhận ra thông báo đó là vô lý, và có thể thực hiện vài hành động dựa trên các thành phần sai này đem lại lợi ích cho bên thứ ba. Người dùng log vào một server mà không sử dụng mật khẩu được mã hoá. Một người khác đang nge trộm trên đường truyền và bắt được mật khẩu logon của người dùng, sau đó có thể truy nhập thông tin trên server như người sử dụng. Một người quản trị hệ thống không hiểu về khía cạnh an toàn và yêu cầu của hệ thống và vô tình cho phép người dùng khác truy nhập vào thư mục chứa các thông tin hệ thống. Người dùng phát hiện ra họ có thể có được các thông tin hệ thống và có thể dùng nó phục vụ cho lợi ích của mình. Thật tai hại nếu các vấn đề trên xảy ra, nó có thể ảnh hưởng không chỉ lợi ích cá nhân mà còn ảnh hưởng tới lợi ích của tập đoàn, có khi là quốc gia. Vậy nên vấn đề bảo mật thông tin ngày càng trở lên cần thiết và được sử dụng rất nhiều trong các công ty, tập đoàn, ban bộ…Vì đó các hệ mã hóa mang lại lợi ích rất lớn và đóng vai trò không thể thiếu trong đời sống công nghệ thông tin. Trong tài liệu này, tôi xin giới thiệu với các bạn một số hệ mã hóa như: Caesar, mã thay thế, mã dịch vòng…và đặc biệt hệ về hệ mã hóa Vigenere nổi tiếng. Hệ mã hóa này được phát minh vào thế kỷ thứ 16 và được viết đầu tiên bởi nhà ngoại giao Pháp Blaise de Vigenère và là một kiểu của mã hóa thay thế được xem xét là chưa từng bị phá vỡ trong suốt 4 thế kỷ và nó được sử dụng phổ biến rộng rãi cho việc mã hóa những dữ liệu được truyền qua hệ thống điện tín trong suốt thế kỷ 19. 4 Chương 1: Hệ mật mã truyền thống 1.1 Mở đầu – một số hệ mã hóa đơn giản: Trong thực tế, giả sử bên A muốn liên lạc với B thương lượng một vấn đề bí mật nào đó( ví dụ như: hợp đồng, bầu cử, thông điệp bí mật …) trên một kênh mật an toàn sao cho C(kẻ trộm) không thể hiểu được thông tin được truyền đi giữa hai người là gì, để tránh tình trạng nghe nén và ăn trộm thông tin quan trọng. Kênh liên lạc này có thể là một đường dây điện thoại hay một mạng máy tính. Đối tượng cơ bản của mật mã chính là khả năng tạo ra các kênh liên lạc đó. Thông tin mà bên A và B muốn gửi cho nhau có thể là những tài liệu liên quan đến bất kỳ một vấn đề gì được thể hiện bằng một văn bản tiếng Anh, các dữ liệu bằng số hay bất cứ tài liệu nào có cấu trúc tùy ý. A sẽ tìm cách làm thế nào đó để gửi an toàn cho bên B một cách an toàn nhất, vậy nên, bên A sẽ mã hóa tài liệu đó (bản rõ) bằng một khóa được xác định trước và gửi bản mã kết quả trên kênh. Bên C có bản mã thu trộm được trên kênh song không thể xác định nội dung của bản rõ, nhưng B( người đã biết khóa mã) có thể giải mã và thu được bản rõ. Đó là mục đích của mật mã- đảm bảo an toàn thông tin. 1.1.1 Định nghĩa về hệ mật mã [1]: Hệ mật mã là một bộ gồm 5 thành phần(P,C,K,E,D) thỏa mãn các điều kiện sau: - P là một tập hữu hạn các bản rõ có thể - C là một tập hữu hạn các bản mã có thể - K là tập hữu hạn các khóa có thể(không gian khóa) - Đối với mỗi k thuộc K có một quy tắc mã ek : P->C và một quy tắc giải mã tương ứng dk thuộc D, dk : C->P và ek :P->C, là hàm mà: dk(ek(x))=x với mọi bản rõ x ∈P. Khi bên A muốn gửi một tài liệu (bản rõ x) đến cho bên B, bên A sẽ mã hóa bản rõ đó bằng ek : P->C và gửi đi trên đường truyền qua cho bên B, bên B nhận được sau đó sẽ giải mã bằng dk : C->P để thu lại bản rõ ban đầu. Bên A và B sẽ áp dụng thủ tục sau dùng hệ mật khóa riêng. Trước tiên họ chọn một khóa ngẫu nhiên K ∈ K . Điều này được thực hiện khi họ ở cùng một chỗ và không bị bên C theo dõi hoặc họ có một kênh mật trong 5 trường hợp họ ở xa nhau. Sau đó giả sử bên A muốn gửi một thông báo cho B trên một kênh không mật và ta xem thông báo này là một chuỗi: x = x1,x2 ,. . .,xn với số nguyên b ≥ 1 nào đó. Ở đây mỗi kí hiệu của mỗi bản rõ xi ∈ P , 1 ≤ i ≤ n . Mỗi xi sẽ được mã hóa bằng quy tắc mã ek với khóa K xác định trước đó. Bởi vậy bên A sẽ tính yi = ek(xi), 1 ≤ i ≤ n và chuỗi bản mã nhận được y = y1,y2 ,. . .,y sẽ được gửi trên kênh. Khi bên B nhận được y = y1,y2 ,. . .,y anh ta sẽ giải mã bằng hàm giải mã dk và thu được bản rõ gốc x = x1,x2 ,. . .,xn 1.1.2.Một số loại mã hóa truyền thống như: 1.1.2.1 Mã dịch chuyển vòng( shift cipher): Nhận xét: Trong trường hợp K=3, hệ mật thường được gọi là mã Caeser. Ta sẽ sử dụng mã dịch vòng(với modulo 26) để mã hóa một văn bản tiếng Anh thông thường bằng cách thiết lập sự tương ứng giữa các kí tự và các thặng dư theo modulo 26 như sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25. 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 Định nghĩa[2]: Giả sử P = C = K = Z26 với 0 ≤ k ≤ 25 , định nghĩa: eK(x) = x +K mod 26 và dK(x) = y -K mod 26 (x,y ∈ Z26) 6 Ví dụ: Giả sử khóa cho mã dịch vòng là K=11 Bản rõ: “wewillmeetatmidnight” Trước tiên biến đổi bản rõ thành dãy các số nguyên ta có: Bản rõ số: 22 4 22 8 11 11 12 4 4 19 0 9 12 8 3 13 8 6 7 19 Sau đó cộng 11 vào mỗi giá trị rồi rút gọn tổng theo modulo 26, ta được: Bản mã số: 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuối cùng biến đổi dãy số nguyên này thành các kí tự thu được bản mã: Bản mã chữ: “HPHTWWXPPELEXTOYTRSE” Tương tự, khi bên B muốn xem bản mã này, trước tiên bên B sẽ biến đổi bản mã thành dãy các số nguyên rồi trừ đi giá trị cho 11 (rút gọn theo modulo 26) và cuối cùng lại biến đổi dãy này thành các ký tự. Kết luận: Mã dịch vòng là không an toàn vì nó có thể bị thám theo phương pháp vét cạn. Do chỉ có 26 khóa nên dễ dàng thử mọi khóa dk có thể cho tới khi nhận được bản rõ có ý nghĩa. 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 7 1.1.2.2 Mã thay thế: Hệ mã hoá thay thế là hệ mã hoá trong đó mỗi ký tự của bản rõ được thay thế bằng ký tự khác trong bản mã (có thể là một chữ cái, một số hoặc một ký hiệu). Có 4 kỹ thuật thay thế sau đây: 1. Thay thế đơn (A simple substitution cipher): Là hệ trong đó một ký tự của bản rõ được thay bằng một ký tự tương ứng trong bản mã. Một ánh xạ 1-1 từ bản rõ tới bản mã được sử dụng để mã hoá toàn bộ thông điệp. 2. Thay thế đồng âm (A homophonic substitution cipher): Giống như hệ thống mã hoá thay thế đơn, ngoại trừ một ký tự của bản rõ có thể được ánh xạ tới một trong số một vài ký tự của bản mã: sơ đồ ánh xạ 1-n (one-to-many). Ví dụ, “A” có thể tương ứng với 5, 13, 25, hoặc 56, “B” có thể tương ứng với 7, 19, 31, hoặc 42, v.v. 3. Thay thế đa mẫu tự (A polyalphbetic substitution cipher): Được tạo nên từ nhiều thuật toán mã hoá thay thế đơn. ánh xạ 1-1 như trong trường hợp thay thế đơn, nhưng có thể thay đổi trong phạm vi một thông điệp. Ví dụ, có thể có năm thuật toán mã hoá đơn khác nhau được sử dụng; đặc biệt thuật toán mã hoá đơn được Định nghĩa[2]: Cho P =C = Z26 . K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . . ,25 Với mỗi phép hoán vị π ∈K , ta định nghĩa: eπ(x) = π(x) và dπ(y) = π -1(y) Trong đó π -1 là hoán vị ngược π. 8 sử dụng thay đổi theo vị trí của mỗi ký tự trong bản rõ. 4. Thay thế đa sơ đồ (A polygram substitution cipher): Là thuật toán trong đó các khối ký tự được mã hoá theo nhóm. Đây là thuật toán tổng quát nhất, cho phép thay thế các nhóm ký tự của văn bản gốc. Ví dụ, “ABA” có thể tương ứng với “RTQ”, “ABB” có thể tương ứng với “SLL”, v.v. Ta xét ví dụ về phép hoán vị ngẫu nhiên Π tạo nên một hàm mã hóa( các kí hiệu của bản rõ được viết bằng chữ thường còn các kí hiệu của bản mã là chữ in hoa). Ví dụ: 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 Như vậy, eπ (a) = X, eπ (b) = N,. . . .. Hàm giải mã là phép hoán vị ngược. Điều này được thực hiện bằng cách viết hàng thứ 2 lên trước rồi sắp xếp theo thứ tự chữ cái. Ta nhận được: 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 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 Bởi vậy, dπ (A) = d, dπ(B) = 1, . . . 9 Kết luận: Mỗi khóa của mã thay thế là một phép hoán vị của 26 ký tự. Số các hoán vị này là 26! Là một số rất lớn. Bởi vậy phép tìm khóa vét cạn không thể thực hiện được, thậm chí bằng máy tính. Tuy nhiên, sau này sẽ thầy rằng mã thay thế có thể dễ dàng bị thám bằng các phương pháp khác. 1.1.2.3 Hệ mã hoá CAESAR: Hệ mã hoá CAESAR là một hệ mã hóa thay thế đơn làm việc trên bảng chữ cái tiếng Anh 26 ký tự (A, B, …, Z). Trong hệ Caesar và các hệ tương tự còn lại ta sử dụng các số tự nhiên thay cho các ký tự - đánh số các ký tự trong bảng chữ cái theo thứ tự: A B C D E F …. X Y Z 0 1 2 3 4 5 …. 23 24 25 Các phép toán số học thực hiện theo modul 26. Có nghĩa là 26 đồng nhất với 0, 27 đồng nhất với 1, …. Hệ Caesar sử dụng thuật toán mã hóa trong đó mỗi ký tự được thay thế bởi một ký tự khác được xác định bằng cách dịch ký tự cần mã hóa sang phải k bước theo modulo 26: Ek(α ) = (α + k)mod 26. Trong đó α là một ký tự, 0≤ k ≤ 26 Thuật toán giải mã tương ứng Dk là lùi lại k bước trong bảng chữ cái theo modul 26: Dk(α ) = (α - k)mod 26 Không gian khóa của hệ Caesar bao gồm 26 số Ví dụ : Mã Hóa Plaint: “TRICH” Bản rõ số: 19 17 8 2 7 Khóa: k=3 Bản mã số: 22 20 11 5 10 10 Bản mã chữ là : “WULFK” Giải mã: Lùi lại với k=3 ta thu được bản rõ: “TRICH” Nhận xét: hệ mã hóa Caesar là hệ mã hóa cũ và không an toàn vì không gian khóa của nó rất nhỏ, do đó có thể thám mã theo phương pháp vét cạn. Khóa giải mã có thể tính ngay đươc từ khóa mã hóa. Do chỉ có 26 khóa nên ta có thể thử lần lượt các khóa cho đến khi tìm được khóa đúng. 1.1.2.4. Mã Affine: Ví dụ: giả sử K=(7,3). Áp dụng công thức của hàm mã hóa: Ek(x) = 7x+3 Và hàm giải mã tương ứng là: dk(x)=15(y-3)=15y-19 Bản rõ là: “Iwillwin” Bản số: 8 22 8 11 11 22 8 13 Ta có: 7 × 8 +3 mod 26 = 59 mod 26 = 7 7 × 22 + 3 mod 26 = 157 mod 26 =1 Định nghĩa[2]: Cho P = C = Z26 và giả sử: P = { (a,b) ∈ Z26 × Z26 : UCLN(a,26) =1 } Với K = (a,b) ∈K , ta định nghĩa: eK(x) = ax +b mod 26 và dK(y) = a-1(y-b) mod 26, x,y ∈ Z26 11 7 × 8 +3 mod 26 = 59 mod 26 = 7 7 × 11 +3 mod 26 = 80 mod 26 = 2 7 × 11 + 3 mod 26 = 80 mod 26 =2 7 × 22 +3 mod 26 = 157 mod 26 = 1 7 × 8 +3 mod 26 = 59 mod 26 = 7 7 × 13 +3 mod 26 = 94 mod 26 = 16 Bản mã số thu được là: 7 1 7 2 2 1 7 16 Bản mã chữ thu được là: “HBHCCBHQ” Việc giải mã chỉ việc áp dụng dK(y) = a-1(y-b) mod 26, 1.2. Mã Vigenere và các đặc tính của nó: 1.2.1 Định nghĩa: Trong cả hai hệ mã dịch vòng và mã thay thế( một khi khóa đã được chọn) mỗi ký tự được ánh xạ vào một ký tự duy nhất. Vì đó mà các hệ mật còn được gọi là hệ thay thế đơn biểu. Bây giờ ta sẽ trình bày một hệ mật không phải là bộ chữ đơn, đó là hệ mã Vigenere nổi tiếng. Nó được gọi là hệ mã hóa đa biểu Giống như Caesar nhưng ở đây khóa được thay đổi theo từng bước. Định nghĩa[2]: Cho m là một số nguyên dương cố định nào đó. Định nghĩa P=C=K=(Z26)m Với khóa K = (k1,k2, …,km) ta xác định: ek (x1,x2,…,xm) =(x1+k1, x2+k2,….,xm+km) dk(y1,y2,…ym) = (y1-k1, y2-k2,….,ym-km). Trong đó tất cả các phép toán được thực hiện trong Z26. Ta sẽ biến đổi các phần tử của bản rõ theo thặng dư 26, viết chúng thành các nhóm 6 rồi cộng với từ khóa theo modulo 26. 12 Ví dụ: giả sử m=5 và từ khóa là “TRICH”. Từ khóa này tương ứng với dãy số K=(19,17,8,2,7). Giả sử bản rõ là xâu: Bản rõ: “CHIPHEO” Ta sẽ biến đổi các phần tử của bản rõ thành các số từ 0-25, ta được: Bản rõ số: C H I P H E O 2 7 8 15 7 4 14 viết chúng thành các nhóm 5 rồi cộng với từ khóa theo modulo 26 ta được: Bản rõ : C H I P H E O Bản rõ số: 2 7 8 15 7 4 14 Khóa số viết lặp lại: 19 17 8 2 7 19 17 =>> Bản mã số: 21 24 16 17 14 23 5 Bởi vậy, dãy ký tự tương ứng của xâu bản mã sẽ là: “VYQROXF” Để giải mã ta có thể dùng cùng từ khóa nhưng thay cho cộng, ta trừ cho nó theo modulo 26. 1.2.2 Tính chất: Ta thấy, khóa có độ dài là m, nên các khóa có thể là 26m , bởi vậy phương pháp tìm kiếm vét cạn cũng yêu cầu thời gian khá lớn.Việc thám mã là rất phức tạp. Thứ hai, từ khóa có độ dài m, mỗi ký tự có thể được ánh xạ vào trong m ký tự có thể có, như trong ví dụ xét trên có đến 2 ký tự H nhưng khi mã hóa ký tự H được mã hóa thành Y và O. Đó là 13 một đặc điểm khác so với các hệ mã hóa đơn biểu. Một hệ như vậy được gọi là hệ mật thay thế đa biểu. Việc thám mã đa biểu khó khăn hơn nhiều so với việc thám mã hệ đơn biểu. Đó là một tiến bộ hơn so với các phép mã hóa cổ điển ta xét bên trên. 1.3.Phương pháp mã hóa và giải mã Vigenere(khi có khóa cho trước): Chúng ta xét một ví dụ sau: Ví dụ: Bản rõ: “Now is the time for all good men” Keywords là: TABLE Ta viết theo hàng của bản rõ và sự lặp lại của từ khóa phía dưới bản rõ, ta được: Bản rõ: n o w i s t h e t i m e f o r a l l g o o d m e n Lặp khóa: T A B L E T A B L E T A B L E T A B L E T A B L E 1.3.1 Mã hóa: Chúng ta nhìn vào hình A polyalphabetic tableau ứng với mỗi ký tự của bản rõ là một ký tự trên hàng của bảng đa biểu, và ứng với mỗi ký tự từ khóa là một ký tự trên cột của bảng đa biểu, khi đó tìm được ký tự mà là giao của cột ký tự khóa với hàng ký tự của bản rõ, ta được: n o w i s t h e t i m e f o r a l l g o o d m e n T A B L E T A B L E T A B L E T A B L E T A B L E G O X T W M H F E M F E G Z V T L M R S H D N P R Vậy nên, ta thu được bản mã là: “GOXTWMHFEMFEGZVTLMRSHDNPR” 14 Chúng ta xem xét một vài đặc điểm. Trong từ “all” của bản rõ, xuất hiên 2 chữ ‘l’ nhưng khi được mã hóa chúng thành L và M, chữ ‘t’ ở trong “the” và “time” được mã hóa thành M và E…Vì vậy, những ký tự giống nhau của bản rõ có thể mã hóa thành những ký tự mã khác nhau, và những ký tự giống nhau của bản mã lại có thể được tạo nên bởi các ký tự khác nhau của bản rõ. Hình1 : A polyalphabetic tableau 15 1.3.2 Giải mã: Sự giải mã là quá trình ngược lại của mã hóa. Chúng ta viết dưới bản mã với keyword được lặp lại, sau đó nhìn theo cột của keyword khi nào thấy ký tự mã hóa, chiếu sang hàng ngang ta sẽ tìm ra ký tự rõ tương ứng. Ví dụ, ký tự mã là G, ký tự khóa là T, ta nhìn dọc theo cột T khi nào tìm thấy G, chiếu sang hàng ngang thì hàng đó là của ký tự N, vậy nên bản rõ là N. Tương tự lần lượt như vậy ta tìm ra được bản rõ. Ví dụ: Ciphertext: G O X T W M H F E M F E G Z V T L M R S H D N P R Keyword: T A B L E T A B L E T A B L E T A B L E T A B L E Paintext: n o w i s t h e t i m e f o r a l l g o o d m e n Trong hệ mã hóa này, có sử dụng sự quay vòng một số trong hệ mã hóa Caesar. Trong mỗi cột, đại diện một phép mã hóa Caesar đơn giản với một phép dịch chuyển. 1.3.3 Chương trình mã hóa: Chúng ta nhìn vào hàng đầu tiên trong tableau. Trong mỗi cột,A được miêu tả bởi một ký tự khóa, B sẽ được miêu tả ký tự khóa cộng thêm 1, ngoại trừ cột cuối cùng, nơi nó sẽ được thay thế bởi lý tự A. C sẽ được miêu tả bởi ký tự khóa cộng với 2, ngoại trừ 2 cột cuối cùng. Paintext :P Ciphertext: C Keyword: K Do đó, ta có: C= [P+K-1]mod 26 Ví dụ: Ta xét hàng đầu tiên P=13(M), K= 20(T) ,chúng ta sẽ có: C=[13+20-1]mod 26 =6 (F). Theo như trên, cột T và hàng M giao nhau tại F. Nếu bản rõ là vector T% và khóa là vector K%, khi đó bản rõ sẽ được xác định theo công thức: 16 C%(X)=T%(I)+K%(KP)-1 IF C%(X)>26 THEN C%(X)=C%(X)-26 Quá trình giải mã là sự ngược lại của giải mã, khi đó thay công thức trên thành: C%(I)=T%(K)-K%(L)+1 IF C%(I)<0 THEN C%(I)=C%(I)+26 1.3.4 Kết luận: Việc mã hóa và giải mã của hệ mã hóa Vigenere khi có khóa cho trước là một việc không phải phức tạp, chỉ cần viết khóa lặp lại dưới bản rõ(mã) khi mã (giải) hóa, rồi tìm giao của chúng trên bảng đa biểu ta sẽ được bản mã (rõ) tương ứng. 17 Chương 2: Phân tích trong trường hợp không có khóa cho trước 2.1 Những đặc trưng thống kê của bản rõ: Tần số đơn, bộ đôi, trùng lặp: Giả sử ta xét bản rõ: Có 3 cách phân tích mang lại hiểu quả nhất là: theo tần suất các ký tự đơn(letter frequences) và tần suất của các cặp ký tự đôi(digram frequences), và bộ ba(trigram). 2.1.1 Tần suất của 1 ký tự: Bảng 1. Bảng tần suất các ký tự trong Tiếng Anh của Robert Edward Lewand Letter Frequency Letter Frequency a 0.08167 n 0.06749 b 0.01492 o 0.07507 c 0.02782 p 0.01929 d 0.04253 q 0.00095 e 0.12702 r 0.05987 f 0.02228 s 0.06327 g 0.02015 t 0.09056 h 0.06094 u 0.02758 18 i 0.06966 v 0.00978 j 0.00153 w 0.02360 k 0.00772 x 0.00150 l 0.04025 y 0.01974 m 0.02406 z 0.00074 2.1.2 Tần suất bộ đôi phổ biến nhất xuất hiện trong tiếng Anh th, he, in, en, nt, re, er, an, ti, es, on, at, se, nd, or, ar, al, te, co, de, to, ra, et, ed, it, sa, em, ro. Chúng ta hãy nhìn vào bảng sau, ký tự đầu sẽ nằm bên cột ngoài cùng của bảng, ký tự thứ 2 tương ứng sẽ là hàng đầu tiên của bảng. Khi đó, con số trong mỗi ô đó chính là tuần suất xuất hiện của cặp ký tự đó trong tiếng Anh. Ví dụ: tần suất của ‘TH’ là 315, tần suất của “HT” là 22. Bảng 2: Bảng tần số đôi 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 A 1 32 39 15 10 18 16 10 77 18 172 2 31 1 101 67 124 12 24 7 27 1 B 8 58 6 2 21 1 11 6 5 25 19 C 44 12 55 1 46 15 8 16 59 1 7 1 38 16 1 D 45 18 4 10 39 12 2 3 57 1 7 9 5 37 7 1 10 32 39 8 4 9 6 E 131 11 64 107 39 23 20 15 40 1 2 46 43 120 46 32 14 154 145 80 7 16 41 17 17 F 21 2 9 1 25 14 1 6 21 1 10 3 2 38 3 4 8 42 11 1 4 1 19 G 11 2 1 1 32 3 1 16 10 4 1 3 23 1 21 7 13 8 2 1 H 84 1 2 1 251 2 5 72 3 1 2 46 1 8 3 22 2 7 1 I 18 7 55 16 37 27 10 8 39 32 169 63 3 21 106 88 14 1 1 4 J 2 4 4 K 28 8 3 3 2 1 3 3 L 34 7 8 28 72 5 1 57 1 3 55 4 1 28 2 2 2 12 19 8 2 5 47 M 56 9 1 2 48 1 26 5 3 28 16 6 6 13 2 3 N 54 7 31 118 64 8 75 9 37 3 3 10 7 9 65 7 5 51 110 12 4 15 1 14 O 9 18 18 16 3 94 3 3 13 5 17 44 145 23 29 113 37 53 96 13 36 4 2 P 21 1 40 7 8 29 28 26 42 3 14 7 1 2 Q 20 R 57 4 14 16 148 6 6 3 77 1 11 12 15 12 54 8 18 39 63 6 5 10 17 S 75 13 21 6 84 13 6 30 42 2 6 14 19 71 24 2 6 41 121 30 2 27 4 T 56 14 6 9 94 5 1 315 128 12 14 8 111 8 30 32 53 22 4 16 21 U 18 5 17 11 11 1 12 2 5 28 9 33 2 17 49 42 45 1 1 1 V 15 53 19 6 W 32 3 4 30 1 48 37 4 1 10 17 2 1 3 6 1 1 2 X 3 5 1 4 1 4 1 1 Y 11 11 10 4 12 3 5 5 18 6 4 3 28 7 5 17 21 1 3 14 Z 5 2 1 1 2.1.3 Những bộ ba phổ biến nhất: the, and, tha, ent, ing, ion, tio, for, nde, has, nce, edt, tis, oft, sth, men 20 Sau đây là ví dụ về tần số đơn của các ký tự trong bản rõ: “Our latest shipment of one hundred bales is now loaded. Leave haror police will not interfere. We can sail anytime this we Please advise conditions at your end.” Từ đó ta có bảng tần số đơn của từng kí tự là: Plaint E: 28 H: 4 N: 12 W: 4 A: 11 P: 3 I: 11 U: 3 O: 11 B: 2 L: 10 F: 2 S: 9 M: 2 T: 9 Y: 2 D: 7 K: 1 R: 7 V: 1 C: 4 Không có G, J, Q, X và Z 2.2 Những đặc trưng thống kê của bản mã: Tần số đơn, bộ đôi, trùng lặp 21 Ta xét 1 ví dụ thám mã sử dụng tần suất đơn( letter frequencies),bộ đôi( digram frequencies) và bộ ba(trigram frequencies). Cho bản mã sau: “CKPKH GVGCK UGZQA GCKUG CLGPQ FJZIG PQQAF QQLHG FJZEF QGKEF CCQAG LOULJ QFRGM OGPQA FUGZO SJBQA GLOTS MFOKS JZKOQ VKIGE KOGFJ ZKJGI XKJGT OGMQP LCGJQ CXQKO GPQYD” Bước 1 : Chúng ta tính được tần suất xuất hiện của các ký tự trong bản mã. Và bên phải là bảng tần suất của các ký tự trong tiếng Anh. Cryptogram English(based on 135 letters) G ............. 21 e ............... 17 Q ............. 16 t ............... 13 K .......... …12 a, o............ 11 F,J,O ...... .. 9 n, i............. 10 C .......... …8 s ............... 9 L,P,Z ...... ..6 r ............... 8 A .......... …5 h ............... 7 U .......... …4 l, d............. 5 E,I,M,S .... .3 c, u............. 4 22 H,T,V,X .... 2 p,f,m,w....... 3 B,D,R,Y .... 1 y,b,g .......... 2 v,k .............. 1 Và tần suất xuất hiện của bộ đôi và bộ 3 trong bản mã là: Digrams in Cryptogram English Digrams QA ...................... ………5 th ......................... 4 GP,JZ,OG,PQ .................4 he ….................... 3 KO,FJ,CK,AG,UG ..........3 an,in,er,re,es ........ 2 GC,GZ,GF,GL,GM,QF on,ea,ti,at,st QQ,KU,KJ,FQ,JQ,JG en,nd,or,to,nt LO,ZK,AF,EF,IG,SJ ...... 2 ed,is,ar,ou,te of,it,ha,se,et …...... 1 Trigrams in Cryptogram English Trigrams (in order of frequency) GPQ ................................. 4 the QAG, FJZ ......................... 3 and QAF,JZK,OGP,KOG tha CKU,AGL,UGZ,GFJ ent GLO,KUG,KJG ................ 2 ion 23 Bước 2: Chúng ta nhận thấy rằng: - Ký tự G có tần suất cao nhất, vì vậy chúng ta thừa nhận nó là ‘A’. - “the” là bộ đôi có tần suất xuất hiện cao nhất trong tiếng Anh, vì vậy chúng ta nhìn trong bộ 3 những bộ mà kết thúc là G, có: QAG, KOG, KJG - ‘t’ cũng là ký tự có tần suất cao, ‘h’ tần suất trung bình. ‘QA’ là bộ đôi tần suất cao nhất trong bản mã, nên QAG là một lựa chọn chính xác và được thay thế cho ‘the’. Khi đó ta có: e e e th e e e t e tth tt e CKPKH GVGCK UGZQA GCKUG CLGPQ FJZIG PQQAF QQLHG te the t e e th e th FJZEF QGKEF CCQAG LOULJ QFRGM OGPQA FUGZO SJBQA e t e e e e e t GLOTS MFOKS JZKOQ VKIGE KOGFJ ZKJGI XKJGT OGMQP e t t e t LCGJQ CXQKO GPQYD Bước 3: Chúng ta nhìn lại bản cryptogram, nhận thấy: - F( ở khối thứ 7) phải là một nguyên âm và có 1 tần suất cao giống ‘a’ hoặc ‘o’. ‘tha’ là bộ ba có tần suất cao nên F đại diện cho ‘a’ - ‘an’ là bộ đôi và ‘and’ là bộ ba có tần suất cao, chúng ta nhận thấy FJ và FJZ là phù hợp, vì vậy J được thay thế cho ‘n’ và Z cho ‘d’. 24 Nên ta có bản cryptogram mới: e e ed th e e e t and e ttha tt e CKPKH GVGCK UGZQA GCKUG CLGPQ FJZIG PQQAF QQLHG and a t e a the n ta e e th a ed n th FJZEF QGKEF CCQAG LOULJ QFRGM OGPQA FUGZO SJBQA e a nd t e e an d ne ne e t GLOTS MFOKS JZKOQ VKIGE KOGFJ ZKJGI XKJGT OGMQP en t t e t LCGJQ CXQKO GPQYD Bước 4: Nhìn lại bản cryptgram ở bước 3, ta nhận thấy: - e,t,a,o,n là những ký tự có tần suất cao nhất và chúng ta đã tìm thấy 4 ký tự. K kết hợp với o. -‘he’ và ‘re’ , O kết hợp với r Ta có: o o e e o ed th e o e e t and e ttha tt e CKPKH GVGCK UGZQA GCKUG CLGPQ FJZIG PQQAF QQLHG and a teo a the r n ta e re th a edr n th FJZEF QGKEF CCQAG LOULJ QFRGM OGPQA FUGZO SJBQA e r aro ndort o e or ean d one one re t GLOTS MFOKS JZKOQ VKIGE KOGFJ ZKJGI XKJGT OGMQP ent tor e t 25 LCGJQ CXQKO GPQYD Bước 5: Chúng ta hãy nhìn khối thứ 21 và 22, chúng ta thấy xuất hiện cụm từ “…oreandone…one…” đó là “and one …one…”, ta sẽ tìm được một cụm phù hợp thụ thuộc vào IX. Chúng ta thay thế P sẽ là s, Y là z, N là q. Ta có: o s o e e o edth e o e est andbe st th a tt e CKPKH GVGCK UGZQA GCKUG CLGPQ FJZIG PQQAF QQLHG and a t e o a the r n ta e res th a edr n th FJZEF QGKEF CCQAG LOULJ QFRGM OGPQA FUGZO SJBQA e r aro ndort obe orean doneb yon e re ts GLOTS MFOKS JZKOQ VKIGE KOGFJ ZKJGI XKJGT OGMQP ent ytor estz LCGJQ CXQKO GPQYD Bước 6: Chúng ta xét các khối xem chúng có nghĩa không, khi đó tìm ký tự phù hợp: • L được thay thế bởi i • C bởi l • U bởi v • H bởi m 26 • E bởi f • R bởi g • T bởi c losom e e lo vedth elove liest andbe sttha ttime CKPKH GVGCK UGZQA GCKUG CLGPQ FJZIG PQQAF QQLHG andfa teofa llthe irvin tagep resth avedr n th FJZEF QGKEF CCQAG LOULJ QFRGM OGPQA FUGZO SJBQA eirc paro ndort obef orean doneb yonec repts GLOTS MFOKS JZKOQ VKIGE KOGFJ ZKJGI XKJGT OGMQP ilent ytor estz LCGJQ CXQKO GPQYD Bước 7: Lần cuối kiểm tra lại tất cả các ký tự chưa được thay thế: • j bởi D • k bởi B • u bởi S • w bởi V • x bởi W Ta xác định được từ khóa: “FITZGERALD” Ta có bản rõ tìm được là 27 “Lo! some we loved, the lovliest and best That Time and Fate of all their Vintage prest, Have drunk their Cup a Round or two before And one by one crept silently to rest. “ 2.3. Thống kê của bản mã được mã bởi khóa giả ngẫu nhiên, không có chu kỳ Trước tiên chúng ta đi tìm hiểu về một số khái niệm: 2.3.1 Lý thuyết trùng khớp(coincident theory): Giả sử X0, X1 là 2 vecto ngẫu nhiên cùng phân bố, nhận giá trị trên bảng chữ cái A={a,b,…,z} X0=(X00,X01,…,X0,n-1) X1=(X10,X11,…,X1,n-1) Ta có xác suất Pj(t)=P{XiJ = t}= P(t), i=0,n-1 , j=0,1, t € A (do cùng phân bố) Bây giờ ta hãy viết thành hàng ngang: X0 : X00, X01, X02, …., X0,n-1 X1 : X10, X11, X12, …., X1,n-1 Nếu có i sao cho X0i = X1i thì ta nói rằng 2 vecto X0 , X1 có một sự trùng khớp ở vị trí i (i=0,n-1). Ta có công thức tính chỉ số trùng khớp mà hiện nay người ta gọi là “hệ số tự tương quan”: ∑ ∑ = = − =Φ 26 1 2 26 1 )( )1( i i i ii C CC Trong đó : Ci là số lần xuất hiện chữ cái i trong cột của bảng tần số định kỳ. 28 Vấn đề đặt ra là: Vậy có bao nhiêu sự trùng khớp như vậy? Rõ ràng sự trùng khớp này phụ thuộc vào tính ngẫu nhiên của 2 vecto X0, X1 . Có 2 trường hợp cơ bản được đặt ra là: + TH1: X0, X1 là 2 bản rõ tùy ý thuộc vào ngôn ngữ tự nhiên nào đó (chẳng hạn như tiếng Anh). + TH2: Ít nhất 1 trong 2 vecto đó là hoàn toàn ngẫu nhiên có phân bố đều trên A. + Ta xét TH1: kí hiệu θ(X0, X1) là số lượng những trùng khớp giữa X0, X1. Ta đặt ra ΧX0,i (X1, i)= 1 nếu X0,i = X1,i 0 nếu trái lại Với i=(0,n-1) Rõ ràng rằng: θ(X0, X1) = ∑ − = 1 0 ,1 )(,0 n i iX XX i Ta nhận được bổ đề sau: Bổ Đề: Ta có xác suất: P{X0,i = X1,i} =S2 Trong đó: S2 = ∑Α∈t tP )(2 Chứng minh: Thật vậy, biến cố {X0,i = X1,i} là hợp của m biến cố (m là lực lượng của A) độc lập, tức là {X0,i = X1,i} = mt π Υ ≤0 {X0,i = X1,i = t}. Do đó xác suất P{X0,i = X1,i} = P{ mt π Υ ≤0 {X0,i = X1,i = t} } 29 = ∑≤ ==mt ii tXtXPπ0 ,1,0 },{ = ∑≤ mt tPπ0 2 )( = S2 (đpcm) ≈ 0,0678 Như vậy, trong trường hợp X0 và X1 là 2 bản rõ độ dài n bằng nhau và được lấy từ cùng một ngôn ngữ thì số trung bình của sự trùng khớp là n.S2 (1). + TH2: Giả sử X0 là mẫu ngẫu nhiên độc lập, phân phối đều, có mật độ xác suất P0 = (P0,0, P0,1, P0,2……..P0,m-1). Còn X1 là mẫu ngẫu nhiên tùy ý với mật độ xác suất P1 = (P1,0, P1,1, P1,2……..P1,m-1). Đặt Y = X0 + X1 Khi đó phân phối xác suất của Y với hàm mật độ PY(y) y∈ A có dạng : PY(y) = ∑−= − 1 0 01 )()( m x xPxyP Vì P0(x) = m 1 x ∈ A nên có: PY(y) = m 1 ∑− = − 1 0 1 )( m x xyP = m 1 = V2 = 0.0385 Vậy giá trị trung bình của những trùng khớp trong trường hợp này sẽ là nV2 Chý ý rằng, nếu 2 bản mã Y0, Y1 được mã cùng một loạn số tùy ý (K1, K2,……..,Kr) và các bản rõ tương ứng là X0, X1. Khi đó nếu lấy X0 trừ đi X1 (theo modulo 26) thì ta có: Y0 – Y1 = (X0 + K)- (X1 + K) = X0 – X1 Vì vậy số các trùng khớp của Y0 , Y1 bằng số các trùng khớp của X0 , X1 Trên cơ sở đó, chúng ta đưa ra 2 giả thuyết: H0: Y0, Y1 được mã bởi cùng một phép thay thế ∏ ∈ E 30 H1: Y0, Y1 được mã hóa bởi 2 phép thế độc lập ∏0 , ∏1 ∈ E Khi đó xác suất của biến cố: {Y0,i = Y1,i} theo lần lượt từng giả thiết H0 , H1 là: P{Y0,i = Y1,i / H0 } = ∑≤ mt tPπ0 2 )( = S2 và P{Y0,i = Y1,i / H1 } = ∑∈ΠΠ ΠΠE PP10 )()( 10 = ∑≤ ΠΠmt tPtPπ0 )()( 10 =V2 Do đó, số trùng khớp kỳ vọng có thể theo giả thuyết H0, H1 với mẫu độ dài n sẽ là: E{θ(Y0, Y1) / H0 } = n.S2 E{θ(Y0, Y1) / H1 } = n.V2 Nếu X0 , X1đều thuộc ngôn ngữ tiếng Anh thì ta có: S2 = ∑ = 25 0 2 )( t tP ≈ 0,076355 Và nếu khóa là dãy hoàn toàn ngẫu nhiên không chu kỳ thì V2 ≈ 0,038462 + Xác định chiều dài khóa Vigenere: Một cách lý thuyết: giả sử X= (X0, …, Xn-1) là n biến ngẫu nhiên (không nhất thiết độc lập) và cho khóa Π = ( 0Π , …, rΠ ) với r ≤ n, là r biến ngẫu nhiên độc lập. Ta ký hiệu: Prõ{Xi = t} = P(t) với t ∈ {a,z} (hoặc t ∈ {0,25}), 0≤ i <n Và Pkhóa {Π i = Π } = q(Π ) với i = 0,….,r-1 Nếu Y = (Y0, Y1, …. ,Yn-1) là bản mã nhận được từ bản rõ X và khóa Π bằng hệ mã Vigenere, Trong đó, Yi = )(mod iri xΠ với i = 0,1,….,n-1 31 Thì số khả năng trùng khớp θ(Y, Y-S) giữa dãy Y và dãy Y-S = (Ys, Ys+1, ….,Yn-s, Y0, Ys-1) là bằng s2 nếu Y, Y-S được mã cùng một phép thay thế đơn và bằng V2 nếu được mã hóa bởi 2 phép thế độc lập ∏0 , ∏1 ∈ E Tức là ta có bổ đề sau: kỳ vọng, E{ θ(Y, Y-S) } = nV2 nếu s ≠ o mod r nS2 nếu s ≡ o mod r Trong thực hành ta lấy S2 = 4 3 = 0,75, còn V2 = 0,0385. Độ dài n càng lớn càng tốt. Điều này có nghĩa: Nếu i mod r = (i+s) mod r => s là chiều dài khóa Nếu i mod r ≠ (i+s)mod r => s không phải là chiều dài khóa. Sau khi xác định được chiều dài khóa ta viết bản mã thành chu kỳ độ dài chu kỳ đó. Rồi tìm từng phần tử khóa bằng cách thám mã từng cột như thám mã Caser. 2.4 Mô tả 2 cách thám mã Vigenere: phép thử Kasiski và phép thử sử dụng chỉ số trùng hợp: Mô tả một số phương pháp thám hệ mã Vigenere. Bước đầu tiên là ta phải xác định độ dài từ khóa mà ta ký hiệu là m. Dùng 2 kỹ thuật: phép thử Kasiski và sử dụng chỉ số trùng hợp. 2.4.1 Phép thử Kasiski: Được mô tả vào năm 1863 của nhà thám mã Kasiski Friendrich. Kỹ thuật này được xây dựng trên nhận xét là: hai đoạn giống nhau của bản rõ sẽ được mã hóa thành cùng một bản mã khi chúng xuất hiện trong bản rõ cách nhau x vị trí, trong đó x ≡ o md m. Ngược lại, nếu ta thấy hai đoạn giống nhau của bản mã (mỗi đoạn có ít nhất là 3) thì đó là một dấu hiệu tốt để nói rằng chúng tương ứng với các đoạn bản rõ giống nhau. + Phép thử Kasiski như sau. Ta tìm trong bản mã các cặp trùng mã bộ ba bộ bốn v.v. và ghi lại khoảng cách giữa các vị trí bắt đầu của hai đoạn. Chúng ta thu được các giá trị d1,d2,….Ta hy vọng rằng m sẽ chia hết cho ước chung của các di . 32 Ví dụ: Cho bản mã sau: VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT ATOUT GLPKO FHNSO KBHMW XKTWX SX Chúng ta đi tìm các bộ 3 lặp lại và tìm khoảng cách xuất hiện của chúng, sau đó phân tích ra các thừa số. Ta có: HNS: xuất hiện 3 lần tại vị trí 16, 94, 256 Khoảng cách tương ứng là: 78, 240, 162 UHR: xuất hiện 2 lần tại 45, 201 Khoảng cách là: 156 WEO: xuất hiện 2 lần tại 53, 77 Khoảng cách là: 24 EOB: xuất hiện 2 lần tại 54, 78 Khoảng cách là: 24 QRV: xuất hiện 2 lần tại 59, 161 Khoảng cách: 102 KTU: xuất hiện 2 lần tại 91, 151 Khoảng cách là: 60 TUH: xuất hiện 3 lần tại 92, 152, 200 Khoảng cách: 60, 108, 48 33 TBD: 2 lần tại 122, 176 Khoảng cách: 54 BDR: xuất hiện 2 lần tại 123, 177 Khoảng cách: 54 BAY: 2 lần tại 166, 220 Khoảng cách là: 54 Ta liệt kê các khoảng cách là: 78, 240, 162, 156, 24, 24, 102, 60, 60, 108, 48, 54, 54, 54. Tất cả đều là bội số của 2 và 6- đó là một dấu hiệu tốt cho việc chiều dài khóa là 2 hoặc 6. Nhưng độ dài khóa là 6 thì sẽ hợp lý. Vậy m=6 2.4.2 Việc xác minh tiếp cho giá trị của m có thể nhận được bằng chỉ số trùng hợp: Giả sử x = x1x2 . . . xn là một xâu ký tự. Chỉ số trùng khớp của x (ký hiệu là Ic(x)) được định nghĩa là xác suất để hai phần tử ngẫu nhiên của x là đồng nhất. Nếu kí hiệu các tần suất của A, B, C,….,Z trong x tương ứng là F0,F1 ,. . . F25 , Ta có công thức ước lượng chỉ số trùng khớp là: Ic(x) = ∑ ∑ = = − 26 1 26 1 )1( i i i ii C CC Trong đó Ci là số lần xuất hiện chữ cái I trong một cột của bảng tần số định kỳ. Hoặc : IC = )1(* ))1(*( 1...0 − −∑ −= NN FF ni ii Trong đó Fi là xác suất xuất hiện của ký tự thứ i. N là chiều dài của bản mã. Hai giá trị 0,065 và 0,038 đủ cách xa nhau để có thể xác định được độ dài từ khóa đúng( hoặc xác nhận giả thuyết đã được làm theo phép thử Kasiski). Hai kỹ thuật này sẽ được minh họa qua ví dụ chương 3 sau. 34 Chương 3: Thực hành phân tích một bản mã Vigenere Giả sử có bản mã nhận được từ mật mã Vigenere: “CHEEVOAHMAERATBTAXXWTNXBEEOPHBSBQMQEQERBW RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX VRVPRTULHDNQWTWDTYGBPHXTFEALJHASVBFXNGLLCHR ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT AMRVLCRRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI PEEWEVKAKOEWADREMXMTBHHCHRTKDNVRZCHRCLQOHP WQAIIWXNRMGWOIIFKEE “ 3.1 Thử với phép thử Kasiski: Ta xét xâu CHR xuất hiện ở bốn vị trí trong bản mã, bắt đầu các vị trí 1, 166, 236 và 286. Khoảng cách từ lần xuất hiện đầu tiên tới 3 lần xuất hiện còn lại tương ứng là: 165, 235, 285. UCLN của 3 số nguyên này là 5, bởi vậy giá trị này rất có thể là độ dài từ khóa. 3.2 Tính theo chỉ số trùng hợp : Với m=1 chỉ số trùng hợp là 0,045 . Với m=2, có 2 chỉ số trùng hợp là 0,046 và 0,041. Với m=3 ta có 3 chỉ số là 0.043; 0,050; 0,047. Với m=4 có 4 chỉ số là: 0,042; 0,039; 0,046; 0,040. Với m=5 ta có các giá trị 0,063; 0,068; 0,069; 0,061 và 0,072. Điều này càng chứng tỏ rằng độ dài từ khóa là 5. Vậy với giả thiết như trên, làm thế nào để xác đinh được khóa? Ta sẽ sử dụng khái niệm chỉ số trùng khớp tương hỗ của hai xâu sau: 35 Với các giá trị m đã xác định, các xâu con yi thu được bằng mã dịch vòng bản rõ. Giả sử K= (k1,k2,. . .,km) là từ khóa. Ta sẽ xem xét có thể đánh giá MIc(yi,yj) như thế nào. Xét một kí tự ngẫu nhiên trong yi và một kí tự ngẫu nhiên trong yj. Xác suất để cả hai kí tự là A là bằng p-ki p-kj , xác suất để cả 2 là B bằng p1-ki p1-kj,. . .(Cần chú ý rằng tất cả các chỉ số dưới đều được rút gọn theo modulo26). Bởi vậy có thể ước lượng rằng: MIc(yi, yj) ≈ kjh h kih pp − = −∑25 0 = kjkih h h pp −+ = ∑25 0 Ta thấy rằng, giá trị ước lượng này chỉ phụ thuộc vào kí hiệu Ki - Kj mod 26 (được gọi là độ dịch tương đối của yi và yj ). Cũng vậy, ta thấy rằng: 1 25 0 + = ∑ h h h pp = 1 25 0 − = ∑ h h h pp Bởi vậy độ dịch tương đối l sẽ dẫn đến cùng một ước lượng MIc như độ dịch tương đối 26-l. Ta lập bảng các ước lượng cho độ dịch tương đối trong phạm vi từ 0 đến 13. Định nghĩa: Giả sử x = x1x2. . .xn và y = y1y2. . .yn' là các xâu có n và n' kí tự anphabet tương ứng. Chỉ số trùng khớp tương hỗ của x và y (ký hiệu là MIc(x,y)) được xác định là xác suất để một phần tử ngẫu nhiên của x giống với một phần tử ngẫu nhiên của y. Nếu ta ký hiệu các tần suất của A,B,…,Z trong x và y tương ứng là f0,f1,. . .,f25 thì MIc(x,y) sẽ được tính bằng: )1(* ))1(*( ' 1...0 ' − −∑ −= nn ff ni ii 36 Bảng 3: Các chỉ số trùng hợp tương hỗ tính được Độ dịch tương đối Giá trị tính được MIc 0 0.065 1 0,039 2 0,032 3 0,034 4 0,044 5 0,033 6 0,036 7 0,039 8 0,034 9 0,034 10 0,038 11 0,045 12 0,039 13 0,043 Xét thấy rằng, nếu độ dịch tương đối khác 0 thì các ước lượng này thay đổi trong khoảng từ 0,031 đến 0,045; ngược lại nếu độ dịch chuyển tương đối bằng 0 thì ước lượng bằng 0,065. Có thể dùng nhận xét này để tạo nên một phỏng đoán thích hợp cho l=ki – kj (độ dịch tương đối của yi và yj) như sau: Giả sử cố định yi và xét việc mã hóa yj bảng 37 e0,e1,e2. . .Ta kí hiệu các kết quả bằng yj0,yj1,. . .Dễ dàng dùng chỉ số MIc(yi,yjg), 0 ≤ g ≤ 25 theo công thức sau: MIc( x, yg ) = '. ' 25 0 nn ff i gii∑ = − Khi g = l thì MIc phải gần với giá trị 0,065 vì độ dịch tương đối của yi và yj bằng 0. Tuy nhiên, với các giá trị g # l thì MIc sẽ thay đổi giữa 0,031 và 0,045. Bằng kỹ thuật này, có thể thu được các độ dịch tương đối của hai xâu con yi bất kỳ. Vấn đề còn lại chỉ là 26 từ khóa có thể và điều này dễ dàng tìm được bằng phương pháp vét cạn Trở lại ví dụ: Ở trên ta đã giả định rằng, độ dài khóa là 5. Bây giờ ta thử tính các độ dịch tương đối. Nhờ máy tính, dễ dàng tính 260 giá trị MIc(yi, yjg) , trong đó 51 ≤≤≤ ji ; 250 ≤≤ g . Các giá trị này được biểu diễn trong bảng sau: Bảng4: Các chỉ số trùng hợp tương hỗ quan sát được i j Giá trị của MIc(yj,yjg) 1 2 0,028 0,027 0,028 0,034 0,039 0,037 0,026 0,025 0,052 0,068 0,044 0,026 0,037 0,043 0,037 0,043 0,037 0,028 0,041 0,041 0,041 0,034 0,037 0,051 0,045 0,042 0,036 1 3 0,039 0,033 0,040 0,034 0,028 0,053 0,048 0,033 0,029 0,056 0,050 0,045 0,039 0,040 0,036 0,037 0,032 0,027 0,037 0,047 0,032 0,027 0,039 0,037 0,039 0,035 1 4 0,034 0,043 0,025 0,027 0,038 0,049 0,040 0,032 0,029 0,034 0,039 0,044 0,044 0,034 0,039 0,045 0,044 0,037 38 0,055 0,047 0,032 0,027 0,039 0,037 0,039 0,035 1 5 0,043 0,033 0,028 0,046 0,043 0,044 0,039 0,031 0,026 0,030 0,036 0,040 0,041 0,024 0,019 0,048 0,070 0,044 0,028 0,038 0,044 0,043 0,047 0,033 0,026 2 3 0,046 0,048 0,041 0,032 0,036 0,035 0,036 0,020 0,024 0,039 0,034 0,029 0,040 0,067 0,061 0,033 0,037 0,045 0,033 0,033 0,027 0,033 0,045 0,052 0,042 0,030 2 4 0,046 0,034 0,043 0,044 0,034 0,031 0,040 0,045 0,040 0,048 0,044 0,033 0,024 0,028 0,042 0,039 0,026 0,034 0,050 0,035 0,032 0,040 0,056 0,043 0,028 0,028 2 5 0,033 0,033 0,036 0,046 0,026 0,018 0,043 0,080 0,050 0,029 0,031 0,045 0,039 0,037 0,027 0,026 0,031 0,039 0,040 0,037 0,041 0,046 0,045 0,043 0,035 0,030 3 4 0,038 0,036 0,040 0,033 0,036 0,060 0,035 0,041 0,029 0,058 0,035 0,035 0,034 0,053 0,030 0,032 0,035 0,036 0,036 0,028 0,043 0,032 0,051 0,032 0,034 0,030 3 5 0,035 0,038 0,034 0,036 0,030 0,043 0,043 0,050 0,025 0,041 0,051 0,050 0,035 0,032 0,033 0,033 0,052 0,031 0,027 0,030 0,072 0,035 0,034 0,032 0,043 0,027 4 5 0,052 0,038 0,033 0,038 0,041 0,043 0,037 0,048 0,028 0,028 0,036 0,061 0,033 0,033 0,032 0,052 0,034 0,027 0,039 0,043 0,033 0,027 0,030 0,039 0,048 0,035 39 Với mỗi cặp (i, j) , ta tìm các giá trị của MIc(yi , yjg) nào gần với 0,065. Nếu có một giá trị duy nhất như vậy (Đối với mỗi cặp (i,j) cho trước), thì có thể phán đoán đó chính là giá trị độ dịch tương đối. Trong bảng trên có 6 giá trị được đóng khung. Chúng chứng tỏ khá rõ ràng là độ dịch tương đối của y1 và y2 là 9; độ dịch tương đối của y2 và y3 là 13, độ dịch tương đối của y2 và y5 là 7; độ dịch tương đối của y3 và y5 bằng 20; của y4 và y5 bằng 11. Từ đây ta có phương trình theo 5 ẩn số K1, K2, K3, K4, K5 như sau: K1 - K2 = 9 K1 - K2 = 16 K2 - K3 = 13 K2 - K5 = 17 K3 - K5 = 20 K4 - K5 = 11 Điều này cho phép biểu thị các Ki theo K1 ; K2 = K1 + 17 K3 = K1 + 4 K4 = K1 + 21 K5 = K1 + 10 Như vậy khóa có khả năng là ( K1, K1+17, K1+4, K1+21, K1+10) với giá trị K1 nào đó ∈ Z26. Từ đây ta hy vọng rằng, từ khóa là một dịch vòng nào đó của AREVK. Bây giờ , không tốn nhiều công sức lắm cũng có thể xác định được từ khóa là JANET. Giải mã bản mã theo khóa này, ta thu được bản rõ sau: The almond tree was in tentative blossom. The days were longer often ending with magnificient evenings of corrugated pink skies. The hunting seasun was over, with hounds and guns put away for six months. The vineyards were busy again as the well-organized farmers treated their vinesand the more lackadaisical neighbors hurried to do the pruning they have done in November. 40 Chương 4 Kết Luận và mô tả chương trình nguồn 4.1 Mô tả chương trình: Chương trình nguồn được viết bởi ngôn ngữ C, gồm 1 file Vigenere.c. Gồm có 4 phần: Phần 1: Mã hóa một bản rõ khi có khóa cho trước Phần 2: Thám mã một bản mã khi có khóa cho trước Phần 3: Thám mã khi chưa biết khóa Phần 4: Thoát khỏi chương trình. 4.2 Kết luận: Như vậy các chữ mã khác nhau có thể cho cùng một chữ của bản rõ. Suy ra tần suất của các chữ cái là phẳng, nghĩa là tần suất xuất hiện các chữ trên bản mã tương đối đều nhau. Tuy nhiên chưa mất hoàn toàn, do độ dài của khoá có hạn, nên có thể tạo nên chu kỳ vòng lặp. Kẻ thám mã bắt đầu từ tần suất của chữ để xem có phải đây là mã đơn chữ cái hay không. Giả sử đây là mã đa chữ vần chữ cái, khi đó ta xác định số chữ cái trong từ khoá và lần tìm từng chữ. Như vậy cần tăng độ dài từ khoá để tăng số chữ cái dùng khi mã để “là” tần suất của các chữ. Rõ ràng rằng, nếu độ dài của khóa mã mà bằng độ dài của bản thông báo cần mã thì mã pháp trở nên bền vững, thêm vào đó nếu khóa mã không phải là một dãy các từ khóa có quy luật mà là một dãy giả ngẫu nhiên thì người ta đã chứng minh được loại mã pháp này cho đến nay được đánh giá là mã pháp không thể phá vở. Vì vậy, hệ mã hóa Vigenere vẫn được sử dụng phổ biến rộng rãi cho việc mã hóa những dữ liệu được truyền qua hệ thống điện tín. 41 Các thuật ngữ 1. Hệ mật mã là tập hợp các thuật toán và các thủ tục kết hợp để che dấu thông tin cũng như làm rõ nó. 2. Mật mã học nghiên cứu mật mã bởi các nhà mật mã học, người viết mật mã và các nhà phân tích mã. 3. Mã hóa là quá trình chuyển thông tin có thể đọc gọi là bản rõ thành thông tin không thể đọc được gọi là bản mã. 4. Giải mã là quá trình chuyển ngược lại thông tin được mã hóa thành bản rõ ( khi cho trước khóa mã). 5. Thuật toán mã hóa là các thủ tục tính toán sử dụng để che dấu và làm rõ thông tin, Thuât toán càng phức tạp thì bản mã càng an toàn. 6.Một Khóa là một giá trị làm cho thuật toán mã hóa chạy theo cách riêng biệt và sinh ra bản rõ riêng biệt tùy theo khóa. Khóa càng lớn thì bản mã kết quả càng an toàn. Kích thước của khóa được đo bằng bit. Phạm vi các giá trị có thể có của khóa được gọi là không gian khóa. 7. Phân tích mã là quá trình hay nghệ thuật phân tích hệ mật mã khi không cho trước bất kỳ một thông tin gì về khóa mã, thậm chí kể cả thuật toán mã hóa cũng không cho trước. 8. Kẻ tấn công là một người hay một hệ thống thực hiện phân tích mã để làm hại hệ thống. Những kẻ tấn công là những kẻ thọc mũi vào chuyện của người khác, các tay hacker, những kẻ nghe trộm hay những tên đáng ngờ khác và họ làm những việc gọi là cracking. 42 Danh sách tham khảo 1] Nguyễn Hoàng Cường, Lý thuyết mật mã và ứng dụng, tr.15- tr.16 [2] PGS.TS. Trịnh Nhật Tiến, An toàn dữ liệu, tr.53- tr.56 [3] Alfred J. Menezes, Paul C.vanOorschot, Scott A.Vanstone: Handbook of APPLIED CRYPTOGRAPHY, chapter 1. [4] Douglas R. Stinson, Cryptography: Theory and Practice, “Chapter 1: Classical Cryptography”. [5] Friedman, W.F. and Callimahos, L.D. (1985) [1956]. Military Cryptanalytics, Part I – Volume 2. Reprinted by Aegean Park Press. ISBN 0-89412-074-3. [6] Friedman, W.F.. The index of coincidence and its applications in cryptology. Department of Ciphers. Publ 22. Geneva, Illinois, USA: Riverbank Laboratories. OCLC 55786052. The original application ignored normalization. [7] Kahn, David (1996) [1967]. The Codebreakers - The Story of Secret Writing. New York: Macmillan. ISBN 0-684-83130-9 [8] Mark Stamp, Richard M. Low: APPLIED CRYPTANALYSIS- Breaking Ciphers in the Real World ( Wiley-interscience publication 2007) [9] ,”nhu cầu bảo vệ thông tin” [10] [11] [12]