Mat Ma Pho Thong - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (28 trang)

Trang chủ

Y - Dược

Ngoại khoa

Mat ma pho thong

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.5 MB, 28 trang )

(1)Mật mã Phổ thông Biên soạn : PHẠM HUY ĐIỂN. NỘI DUNG 1. LỊCH SỬ MẬT MÃ VỚI SỰ THÂM NHẬP CỦA PHƯƠNG PHÁP TOÁN HỌC ........................................2 1.1. Sơ lược về lịch sử mật mã thời cổ ₫ại ................................ 2 Các phép mã chuyển vị: ................................................................................................................. 2 Phép mã thay thế .......................................................................................................................... 2. 1.2. Mật mã thời trung ₫ại và cận ₫ại ....................................... 4 Mật mã thay thế kép- Hệ mã PLAYFAIR .......................................................................................... 4 Mật mã De Vigenere ...................................................................................................................... 5 Máy mã Enigma ............................................................................................................................. 6. 1.3. Mã hóa thông tin thời hiện ₫ại ......................................... 11 Vấn ₫ề nan giải ngàn năm của các hệ mã ₫ối xứng .......................................................................11 Những ₫òi hỏi mới từ thực tiễn hiện tại ........................................................................................11. 2. SỐ HỌC VÀ MỘT SỐ BÀI TOÁN KHÓ ...................11 2.1. Số nguyên tố và bài toán phân tích ra thừa số .................. 11 Số nguyên tố ................................................................................................................................11 Thuật toán tìm các số nguyên tố nhỏ hơn hoặc bằng số n ............................................................11 Định lí cơ bản của số học..............................................................................................................12 Bài toán phân tích ra thừa số nguyên tố .......................................................................................13. 2.2. Tính toán ₫ồng dư và bài toán tính logarit rời rạc............. 13 Khái niệm ₫ồng dư và ₫ịnh lí nhỏ của Phéc-ma..............................................................................13 Tính toán ₫ồng dư với lũy thừa lớn và phương pháp bình phương liên tiếp......................................15 Bài toán tính logarit rời rạc và “khai căn” rời rạc.........................................................................15. 2.3. Ước chung của hai số và những vấn ₫ề liên quan............ 16 Ước chung lớn nhất của hai số......................................................................................................16 Thuật toán Ơ-cơ-lit ......................................................................................................................16 Thuật toán Ơ-cơ-lit mở rộng .........................................................................................................17 Bội chung nhỏ nhất của hai số......................................................................................................18 Nghịch ₫ảo theo modulo m .........................................................................................................19. (2) 3. MỘT SỐ HỆ MÃ DỰA TRÊN NHỮNG BÀI TOÁN KHÓ ............................................................................19 3.1. Thuật toán mã mũ Pohlig — Hellman................................ 19 Nguyên lý thực hiện .....................................................................................................................19 Ví dụ: ...........................................................................................................................................20 Nhận xét ......................................................................................................................................21. 3.2. Thuật toán mã hóa khóa công khai RSA........................... 21 Các hệ mật mã truyền thống và một vấn ₫ề nan giải của chúng....................................................21 Hệ mã khóa công khai RSA ...........................................................................................................21 Ví dụ : ..........................................................................................................................................22 Độ an toàn của hệ mã RSA ............................................................................................................23 Phía sau trang sử về RSA ..............................................................................................................23. 3.3 Thuật toán mã hóa El Gamal............................................. 26 Nguyên lý thực hiện .....................................................................................................................26 Nhận xét: .....................................................................................................................................27. 3.4. Thay cho lời kết ............................................................... 27. 1. (3) 1. LỊCH SỬ MẬT MÃ VỚI SỰ THÂM NHẬP CỦA PHƯƠNG PHÁP TOÁN HỌC 1.1. Sơ lược về lịch sử mật mã thời cổ ₫ại Các phép mã chuyển vị: Phép mã chuyển vị làm dịch chuyển vị trí của các từ trong văn bản. Reilfence cipher. Scytale Được sử dụng trong quân đội Spartan từ thế kỷ thứ 4 trước công nguyên (năm 404, BC). Phép mã thay thế (Thay mỗi chữ cái bằng một chữ cái khác, hay một ký hiệu khác). 2. (4) Mã Kama-Sutra (Sách dạy các môn “nữ công gia chánh” cho thiếu nữ trước khi lấy chồng. Trong sách này, ngoài các môn “cầm, kỳ, thi, họa, làm nước hoa, nấu ăn,... còn có môn “mật mã”, giúp họ dấu diếm những bí mật riêng tư). Hệ mã này được viết ra vào thế kỷ thứ 4 sau công nguyên, nhưng dựa trên tài liệu có từ thế kỷ thứ 4 trước công nguyên. Nguyên lý thực hiện rất đơn giản: chỉ việc chia tập 26 chữ cái ra thành 2 bảng và cho tương ứng với nhau (1-1).. Atbash cipher Nguyên lý: cho tương ứng mỗi ký tự với một ký hiệu bất kỳ Dưới đây là phép tương ứng đơn giản nhất, dùng chính bảng chữ cái alphabet nhưng với thứ tự ngược lại. Phép mã Caesar Nguyên lý: Thay thế mỗi chữ cái trong bảng alphabet bằng một chữ khác đứng sau nó k vị trí (trong chính bảng chữ cái này). Ví dụ, lấy k=3. 3. (5) Tuy nhiên, những người lính của Caesar có thể không biết làm tính, cho nên người ta thường triển khai dưới dạng “máy mã ăn liền”, kiểu cái đĩa với các vòng tròn đồng tâm, gọi là đĩa Caesar. Giáo sư Hà Huy Khoái và chiếc đĩa Caesar trong một bảo tàng mật mã ở Châu Âu. Phép mã Caesar có thể xem là khởi đầu của sự thâm nhập của Toán học. Nếu cho tương ứng mỗi chữ cái trong bảng alphabet với một số nguyên (từ 0 đến 25) thì phép mã này có thể biểu diễn bằng một công thức toán học. Nhận xét: Các phép mã thay thế đơn chữ (thay một chữ này bằng một ký hiệu khác) nói trên bị rơi vào khủng hoảng sau khi người ta phát hiện ra cách bẻ khóa bằng phép phân tích tần số xuất hiện của từng chữ trong ngôn ngữ thường dùng. Vì vậy, cho đến trước thế kỷ thứ 16, các nhà làm mật mã vẫn bị bất lực trước những người bẻ khóa. Các nhà làm mật mã chỉ dành lại được vị thế của mình bằng một loạt phép mã mới thời kỳ trung đại.. 1.2. Mật mã thời trung ₫ại và cận ₫ại Mật mã thay thế kép- Hệ mã PLAYFAIR Hệ mã được phát minh bởi Charles Wheatstone, nhưng được quảng bá rộng rãi bởi Lyon Playfair. Đây là một trong những hệ mã sử dụng phép thay thế cặp hai chữ cái (digraph), nhưng lại khá đơn giản, và vì vậy được sử dụng khá phổ biến. 4. (6) Phép mã này thay thế cặp hai chữ (hoành độ, tung độ) bằng cặp hai chữ có sẵn trong bảng ca-rô. Quy trình mã hóa triển khai như sau: • Chọn chìa khóa mã là một bộ k chữ cái sao cho không có chữ nào được lặp lại, thí dụ là: CHARLES. • Lập mảng carô hình vuông 5x5, và viết các chữ cái vào từng ô (theo thứ tự từ trái qua phải và từ trên xuống dưới). Các chữ cái trong chìa khóa mã được viết trước tiên (theo thứ tự đã chọn), sau đó là những chữ cái còn lại (viết theo thứ tự trước sau như trong bảng alphabet, riêng hai chữ i và j được viết chung trong một ô). • Ghép các chữ cái trong văn bản nguồn thành từng cặp hai chữ. Nếu lẻ ra một chữ thì cho thêm chữ X vào cuối cho đủ cặp. Hai chữ cùng hàng (hay cùng cột) được ứng với hai chữ nằm kế tiếp (theo thứ tự xoay vòng). Hai chữ không cùng hàng và không cùng cột (xác định ra một hình chữ nhật) được ứng với cặp hai chữ là hai đỉnh còn lại của hình chữ nhật. Nhận xét: Điểm mạnh của hệ mã này cũng là ở chỗ có thể xóa nhòa mọi dấu vết về tần số xuất hiện của các chữ cái trong văn bản gốc, khiến người bẻ khóa khó đường lần mò. Tuy nhiên, quá trình mã và giải mã rất tốn kém thời gian, cho nên rất ít được dùng. Mật mã De Vigenere Hệ mã này được khởi nguồn từ Leon Alberti (nhà họa sĩ, nhạc sĩ, nhà thơ, nhà triết học người Ý, sinh năm 1404, và là một trong những nhân vật tiêu biểu của thời kỳ Phục hưng). Nói một cách đơn giản, ý tưởng của Alberti là sử dụng luân phiên hai phép mã Caesar (với 2 chìa khóa mã khác nhau). Cụ thể hơn, ông mã từ đầu tiên trong văn bản mã bằng một phép mã Caesar với chìa khóa k1 rồi mã từ tiếp theo lại bằng phép mã Caesar với khóa k2. Quy trình cứ thế lặp lại cho đến khi mã xong văn bản. Ý tưởng này sau đó được phát triển bởi một số người khác, và người hoàn thiện nó sau cùng là nhà ngoại giao Blair de Vigenere (người Pháp, sinh năm 5. (7) 1523). Sau một thời gian tiếp xúc với hệ mã Alberti (do nhu cầu công việc) ông đã say mê nó và, ở tuổi 39, sau khi thấy mình đã kiếm đủ tiền để có thể theo đuổi công việc của đời mình ông quyết định bỏ nghề ngoại giao và dồn sức cho phát triển hệ mã này. Nguyên lý làm việc của nó như sau: • Chọn từ khóa là một bộ gồm m ký tự, trong đó không có hai ký tự nào trùng nhau (thí dụ là: dibanme, với m=7). • Lập bảng ca-rô, với hàng đầu (hàng thứ 0) là các chữ cái trong bảng alphabet (bắt đầu từ chữ a), còn các hàng tiếp theo cũng là các chữ cái này, nhưng bắt đầu bằng các chữ có trong từ khóa (với thứ tự được xoay vòng trên từng hàng). • Phép mã Vigenere chính là phép mã luân phiên của m phép mã Caesar. Cụ thể, chữ cái thứ nhất (trong văn bản nguồn) được mã bằng phép mã Caesar với khóa là chữ cái đầu tiên trong từ khóa; chữ cái thứ hai được mã bằng phép mã Caesar với chìa khóa là chữ cái thứ hai trong từ khóa. Quy trình cứ thế lặp lại và, một cách tổng quát, chữ cái thứ i được ứng với chữ cái cùng cột với nó trong bảng ca-rô, tại hàng thứ i theo modulo m.. Điểm mạnh của hệ mã là ở chỗ nó xóa nhòa mọi dấu vết về tần số xuất hiện của các chữ cái (trong văn bản gốc). Có thể triển khai dưới dạng đĩa Caesar với nhiều đĩa. Máy mã Enigma Một phát minh độc đáo được ghi nhận vào đầu thế kỷ XX thuộc về Arthur Scherbius (kỹ sư người Đức), máy mã Enigma, được đăng ký phát minh vào năm 1918. Nguyên lý hoạt động như sau:. 6. (8) Ở đây, để cho đơn giản, ta chỉ vẽ bàn phím gồm 6 chữ cái (trên thức tế gồm đủ cả 26 chữ cái). Tuy nhiên, nếu chỉ có một Rotor như trên thì phép mã sẽ lập lại sau 26 bước. Người phát minh đã sử dụng tới 3 vòng Rotor làm cho phép mã trở nên rất phức tạp. Sau khi mã xong mỗi chữ cái, Rotor thứ nhất được quay một nấc, sau đó chữ cái tiếp theo mới được mã. Quy trình tiếp diễn cho tới khi Rotor thứ nhất quay trọn một vòng (26 nấc) thì Rotor thứ hai quay đi một nấc,... và khi Rotor thứ hai quay trọn được một vòng thì Rotor thứ ba quay một nấc. Như vậy, cùng một chữ cái ở các vị trí khác nhau sẽ được mã thành những chữ khác nhau. Khả năng “mã lặp” một chữ cái nào đó chỉ có thể xảy ra nếu chữ đó xuất hiện lại ở đúng vị trí chữ thứ 7. (9) 17576 trong văn bản nguồn (một điều gần như không thể đối với các bản tin thông thường). Vì vậy, việc tấn công bằng tần suất là vô hiệu lực. Ngoài ra, người ta lại sử dụng cơ chế “phản xạ”, cho tín hiệu (sau khi xuyên qua 3 vòng Rotor) được quay ngược trở lại (tiếp tục xuyên qua 3 vòng Rotor) theo một con đường khác.. Hệ thống cấu trúc tổng thể của Enigma có thể được mô phỏng như sau. Trong thực tế, người ta sử dụng rất nhiều dạng biến thể của Enigma. Có loại dùng 3 Rotor, có loại dùng 5 Rotor, có loại không dùng Plugboard,... Một chiếc máy Enigma thật sự, đã từng được sử dụng, là như sau. 8. (10) Một chiếc máy như vậy cho phép sử dụng tới 100 nghìn tỷ tỷ (100000.1018) chìa khóa khác nhau. Khi mới đi vào sử dụng, từ năm 1920, Enigma làm cho thiên hạ choáng ngợp với con số chìa khóa khổng lồ, khiến không ai hy vọng có thể bẻ được nó. Tuy nhiên, một nhóm thám mã Balan (đứng đầu là Marian Reijewski) lại không đầu hàng và có một số ý tưởng độc đáo. Một tuần trước khi Thủ đô Varszawa bị xâm lấn, nhóm thám mã này đã kịp đến với người Anh và tham gia đội thám mã tại Bletchley Park (phía bắc Luân đôn). Những ý tưởng của nhóm thám mã Balan đã được xem là khởi nguồn cho phát kiến chói lọi của Alan Turing trong việc công phá hệ mã Enigma.. Marian Reijewski. Alan Turing. 9. (11) Một số máy mã khác trong Thế chiến thứ II. 10. (12) 1.3. Mã hóa thông tin thời hiện ₫ại Vấn đề nan giải ngàn năm của các hệ mã đối xứng. Chuyển chìa khóa cho người giải mã (Về nguyên tắc: nếu có con đường an toàn để chuyển được chìa thì cũng chuyển được tin, hà tất cần đến mật mã!!!) Những đòi hỏi mới từ thực tiễn hiện tại Điểm khác biệt then chốt của các hệ mã hiện đại so với các hệ mã trước đây là xuất phát từ yêu cầu mới của thực tiễn hiện tại, đó là tính công khai, đại chúng và đơn giản trong sử dụng. Những yêu cầu này vốn không thể chấp nhận được đối với các hệ mã cũ (vì nó chỉ dành cho các đối tượng có nghiệp vụ đặc biệt), nhưng lại là không tránh khỏi trước các yêu cầu của thời hiện đại (vì nó là công cụ của tất cả mọi người). Chính các yêu cầu trớ trêu này buộc người ta phải tìm đến với các phương pháp mới và là cơ hội cho Toán học thể hiện vai trò của mình.. 2. SỐ HỌC VÀ MỘT SỐ BÀI TOÁN KHÓ Trước hết ta nhắc lại một số khái niệm quen thuộc trong số học.. 2.1. Số nguyên tố và bài toán phân tích ra thừa số Số nguyên tố Ðịnh nghĩa. Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số tự nhiên nào. ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải là số nguyên tố được gọi là hợp số. Ðịnh lí sau đây cho một thuật toán đơn giản để xác định các số nguyên tố. Ðịnh lí. Hợp số n phải có ước nguyên tố không lớn hơn. n.. Thật vậy, khi n là một hợp số thì ta có thể viết n = ab , trong đó a và b là các số nguyên thỏa mãn 1 < a ≤ b < n . Rõ ràng ta phải có a hoặc b không vượt quá n (vì trong trường hợp ngược lại thì ab > n ). Giả sử số không lớn hơn n là a , khi đó ước nguyên tố của a không thể lớn hơn n và rõ ràng cũng là ước nguyên tố của n . Từ định lí trên, ta có thuật toán sau đây. Thuật toán tìm các số nguyên tố nhỏ hơn hoặc bằng số n Ta viết dãy các số tự nhiên từ 1 đến n . Trước hết, ta gạch đi số 1, vì nó không phải là số nguyên tố. Số nguyên tố đầu tiên của dãy là 2. Tiếp theo đó ta gạch khỏi dãy tất cả những số lớn hơn 2 nhưng chia hết cho 2 (cũng tức là gạch đi toàn bộ số chẵn 11. (13) lớn hơn 2). Số đầu tiên trong các số còn lại (không chia hết cho 2) là 3: đó chính là số nguyên tố. Giữ lại số 3, ta lại gạch khỏi dãy còn lại những số nào chia hết cho 3 nhưng đứng sau số 3, số đầu tiên trong các số còn lại là số 5 : cũng chính là số nguyên tố. Giữ lại số 5, ta lại gạch đi khỏi dãy những số đứng sau số 5 và chia hết cho 5. Số đầu tiên trong các số còn lại cũng sẽ là một số nguyên tố. Tiếp tục quá trình trên, ta gạch đi khỏi dãy những số lớn hơn số này lại mà chia hết cho nó. Quá trình này tiếp diễn cho tới khi số đầu tiên còn lại (sau một lần gạch nào đó) là một số nguyên tố không nhỏ hơn n . Khi ấy, tất cả những số còn lại của dãy đều là nhỏ hơn hay bằng n và không có ước nguyên tố vượt quá n . Theo định lí trên, những số còn lại này không thể là hợp số, hay nói cách khác, chúng đều là các số nguyên tố. Rõ ràng, định lí này giúp ta giảm được khối lượng công việc một cách đáng kể. Ví dụ, với n = 100 ta chỉ cần tiến hành công việc cho tới gạch hết những số là bội của 7 (vì số đầu tiên còn lại sau lần gạch này đã là 11 > 10 = 100 ); với n = 10000 ta chỉ cần tiến hành công việc cho tới khi gạch xong các các số là bội của 97 (vì số đầu tiên còn lại sau lần gạch này đã là 101 > 100 = 10000 ); Quy trình trên còn có tên gọi là sàng Ơ-ra-tô-xten (Eratosthenes). Tuy rất mạch lạc và đơn giản về ý tưởng, nhưng khi làm việc với các số lớn thì quy trình này rất ít được sử dụng trong việc tìm các số nguyên tố cũng như xác định xem một số đã cho có phải là số nguyên tố hay không. Lí do là số lượng phép tính trong quy trình này quá lớn, khi n là một số lớn. Ví dụ, khi n có khoảng 100 chữ số thập phân thì, với những máy tính thực hiện một triệu phép tính trong một giây, thời gian cần thiết sẽ vào khoảng 3,1.1036 năm! Định lí cơ bản của số học Ðịnh lí. Mọi số nguyên lớn hơn 1 đều phân tích được một cách duy nhất thành tích. các số nguyên tố. Chứng minh. Bằng phản chứng, giả sử tồn tại những số nguyên lớn hơn 1 mà không viết được thành tích các số nguyên tố. Dĩ nhiên những số như vậy phải là những hợp số. Gọi n là số bé nhất trong các số đó. Vì n là hợp số nên nó có dạng n = ab , với a, b là những số tự nhiên bé hơn n . Do định nghĩa số n , mọi số bé hơn n phải phân tích được thành tích các số nguyên tố, cho nên các số a và b phân tích được thành tích các số nguyên tố, tức là a = p1p2 pr , b = q1q2 qs , trong đó pi , i ∈ {1, 2, …, r } , q j , j ∈ {1, 2,..., s } , là những số nguyên tố. Từ đây suy ra n = p1p2 prq1q2 qs , và như vậy n cũng phân tích được thành tích các số nguyên tố. Điều này mâu thuẫn với giả thiết là n không thể phân tích được. Mâu thuẫn này cho thấy rằng giả thiết phản chứng là không thể xảy ra, qua đó khẳng định tính phân tích được của mọi số nguyên lớn hơn 1. Để chứng minh phân tích là duy nhất, ta lại dùng phương pháp phản chứng và giả sử n có hai dạng phân tích khác nhau, tức là n = a1a2 ...am = b1b2 ...bk , trong đó ai , i ∈ {1, 2,..., m } , bj , j ∈ {1, 2,..., k } , là những số nguyên tố. Sau khi giản ước những số nguyên tố bằng nhau có mặt trong hai vế, ta được đẳng thức 12. (14) ai 1ai 2 ...aiu = bj 1bj 2 ...bjv ,. trong đó không có số nguyên tố nào có mặt cả hai vế. Như vậy, vế trái chia hết cho bj 1 , và do đó phải tồn tại một thừa số của tích bên trái chia hết cho bj 1 . Điều này là không thể, vì đây là tích các số nguyên tố khác với bj 1 . Mâu thuẫn này cho thấy giả thiết phản chứng là không thể xảy ra, tức là n không thể có hai dạng phân tích khác nhau. Định lí đã được chứng minh đầy đủ. Bài toán phân tích ra thừa số nguyên tố Phân tích như trên của các số nguyên được gọi là phân tích ra thừa số nguyên tố. Có một quy trình khá đơn giản về mặt ý tưởng để thực hiện việc này : chỉ việc lấy số n đem chia cho các số nguyên tố nhỏ hơn n (có trong sàng Ơ-ra-tô-xten). Tuy nhiên, khi n là một số lớn thì cách phân tích này là không khả thi. Nói chung, bài toán phân tích một số ra các thừa số nguyên tố cho đến hiện nay vẫn là một bài toán hết sức khó khăn. Ðể hình dung được phần nào tính phức tạp của vấn đề, ta xem bảng dưới đây để biết khoảng thời gian cần thiết cho việc phân tích một số nguyên n ra thừa số nguyên tố bằng thuật toán nhanh nhất được biết hiện nay (ta xem rằng máy tính sử dụng vào việc này có tốc độ 1 triệu phép tính trong 1 giây) Số chữ số thập phân Thời gian 75 104 ngày 100 74 năm 200 3,8 tỉ năm Tuy nhiên, một điều kì diệu là chính sự "hóc búa" của bài toán này lại mang đến một giải pháp độc đáo trong ứng dụng của số học vào mã hóa thông tin hiện đại, được xem như là cuộc cách mạng trong lịch sử công nghệ mật mã (xem phần cuối).. 2.2. Tính toán ₫ồng dư và bài toán tính logarit rời rạc Khái niệm đồng dư và định lí nhỏ của Phéc-ma Đồng dư là một trong những quan hệ cơ bản của số học, được sử dụng thường xuyên trong các ứng dụng thực tiễn. Khái niệm này được định nghĩa như sau. Giả sử m là một số nguyên dương. Ta nói hai số nguyên a và b là đồng dư với nhau theo modulo m nếu như m chia hết hiệu a − b , và khi ấy ta kí hiệu a ≡ b(mod m ) . Như vậy a ≡ b (mod m ) khi và chỉ khi tồn tại số nguyên k sao cho b = a + km . Ví dụ 1. 1 ≡ 17(mod 4) , vì 17 − 1 = 16 chia hết cho 4 ; 113 ≡ 413(mod100) , vì 413 − 113 = 300 chia hết cho 100 ; 200 ≡ 215(mod 5) , vì 215 − 200 = 15 chia hết cho 5 .. 13. (15) Khi a là số dư trong phép chia b cho m thì ta cũng có a ≡ b(mod m ) và trong trường hợp này người ta nói a là rút gọn của b theo modulo m . Khi ấy, để cho đơn giản, người ta dùng cách viết a = b mod m . Ví dụ 2. 3 = 11 mod 4 , vì 11 chia cho 4 dư 3; 13 = 313 mod100 , vì 313 chia cho 100 dư 13; 5 = 2005 mod 1000 , vì 2005 chia cho 1000 dư 5. Từ định nghĩa ta có cách tính rút gọn theo modulo của tổng và tích như sau. Mệnh ₫ề. Với a, b ∈. (tập các số nguyên) và m ∈. (tập các số tự nhiên), ta. luôn có: (i).. (a + b) mod m = (a mod m + b mod m ) mod m ;. (ii).. (a ⋅ b) mod m = [(a mod m ) ⋅ (b mod m )] mod m .. Chứng minh. Ta viết a, b dưới dạng a = k1m + r1 , b = k2m + r2 , trong đó r1 = a mod m , r2 = b mod m , còn k1, k2 là những số nguyên. Rõ ràng (a + b) mod m = ((k1 + k2 )m + r1 + r2 ) mod m = (r1 + r2 ) mod m ,. cho nên ta có đẳng thức (i) trong mệnh đề trên. Đẳng thức còn lại được chứng minh tương tự. Ví dụ 3. Ta áp dụng mệnh đề trên để tính 1234562 mod111 . Lưu ý rằng nếu thực hiện phép tính bình phương rồi mới tính modulo thì ta sẽ gặp khó khăn về “tràn bộ nhớ”. Nếu áp dụng đẳng thức (ii) của mệnh đề trên thì ta có 1234562 mod111 = [(123456 mod111) ⋅ (123456 mod111)] mod111 = = [24 ⋅ 24 ] mod111 = 576 mod111 = 21 .. Một định lí quan trọng gắn liền với khái niệm đồng dư là định lí nhỏ của Phécma (Fermat). Định lí. Nếu p là một số nguyên tố và a là một số nguyên không chia hết cho p. thì a p −1 ≡ 1 (mod p ) . Định lí này mặc dù mang tên là "nhỏ" nhưng vai trò của nó thì hoàn toàn không nhỏ. Trong Mục 4 chúng ta sẽ đề cập tới một ứng dụng đặc biệt của nó trong lĩnh vực mã hóa thông tin hiện đại. Để có được ứng dụng đó, người ta đã sử dụng một kết quả của định lí Ơ-le (Euler) - một mở rộng định lí Phéc-ma nêu trên. Kết quả này được phát biểu như sau. Mệnh ₫ề. Nếu n = p ⋅ q , trong đó p, q là những số nguyên tố, còn a là số tự. nhiên không chia hết cho p và q , thì a (p −1)(q −1) ≡ 1 (mod n ) . Trong khuôn khổ giáo trình này chúng ta không có điều kiện trình bày chứng minh cho các kết quả nêu trên. Bạn đọc quan tâm có thể tham khảo trong các tài liệu về Số học (ví dụ như cuốn “Số học Thuật toán” của Hà Huy Khoái và Phạm Huy Điển, do Nhà xuất bản ĐHQG ấn hành năm 2002). 14. (16) Tính toán đồng dư với lũy thừa lớn và phương pháp bình phương liên tiếp Các tính toán lũy thừa với số mũ lớn thường đưa đến những con số vượt quá tầm kiểm soát của bộ nhớ máy tính. Tuy nhiên, trong nhiều ứng dụng thực tế (như sẽ thấy ở phần mã hóa sau này) người ta lại thường phải thực hiện các tính toán đồng dư với lũy thừa bậc rất lớn. Một trong những giải pháp khắc phục khó khăn này là phương pháp bình phương liên tiếp mà bản chất là quy việc tính đồng dư lũy thừa bậc cao về việc tính liên tiếp nhiều đồng dư của lũy thừa bậc thấp (bình phương). Để hiểu rõ bản chất của phương pháp này, ta chỉ cần xem xét một ví dụ minh họa sau đây. Ví dụ 4. Tính 87 43 mod103 . Nếu thực hiện xong phép tính luỹ thừa rồi mới tính đồng dư thì sẽ gặp số rất lớn gây ra "tràn bộ nhớ". Muốn tránh điều này, trước hết người ta tiến hành khai triển số mũ dưới dạng cơ số 2, tức là 43 = 32 + 8 + 2 + 1 = 25 + 23 + 21 + 20. rồi tính liên tiếp các đồng dư bình phương, như sau đây. 87 mod103 = 87 , 872 mod103 = 7569 mod103 = 50 , 2. 872 mod103 = (872 ) mod103 = 502 mod103 = 28 , 2. 3. ( ) mod103 = 28 mod103 = 63 , mod103 = (87 ) mod103 = 63 mod103 = 55 , mod103 = (87 ) mod 103 = 55 mod103 = 38 . 2 2. 872 mod103 = 872. 872. 4. 5. 872. 23. 2. 24. 2. 2. 2. 2. Từ đây, áp dụng công thức rút gọn theo modulo 103 của một tích, ta có 5. 3. 87 43 mod103 = 872 mod 103 ⋅ 872 mod103 ⋅ 872 mod103 ⋅ 87 mod103 ,. và từ kết quả tính toán ở trên ta có 87 43 mod103 = 38.63.50.87 mod103 = 85 . Theo cách này, ta chỉ cần làm việc với những số vừa và nhỏ, không những nhanh mà còn có thể làm việc chỉ trên máy tính bỏ túi. Phương pháp bình phương liên tiếp tuy đơn giản nhưng rất hiệu quả trong thực tiễn triển khai, đặc biệt là khi phải tính toán với các số nguyên lớn (cỡ hàng trăm chữ số thập phân). Khá nhiều phát kiến lớn trong lĩnh vực toán học tính toán được hình thành trên cơ sở ý tưởng của phương pháp này. Bạn nào có điều kiện đi sâu vào lĩnh vực Tính toán khoa học trong tương lai sẽ được tự mình kiểm nghiệm điều đó. Bài toán tính logarit rời rạc và “khai căn” rời rạc Như trên ta thấy, với a, m là những số tự nhiên cho trước (cho dù có thể lớn) việc tính k = a n mod m , (*) đối với mỗi số tự nhiên n , là khả thi và cũng tương đối nhanh (bằng những thuật toán thích hợp). Tuy nhiên bài toán ngược lại, cho trước số tự nhiên k , cần tìm số 15. (17) tự nhiên n thỏa mãn (*) thì lại là một bài toán vô cùng khó. Bài toán này có tên gọi là tính logarit rời rạc và đang là đối tượng được quan tâm nghiên cứu hiện nay. Ta biết rằng việc tính logarit thông thường (với số thực) thì không ai xem là khó (và luôn khả thi với ngay cả máy tính cầm tay), nhưng việc tính logrit rời rạc thì hoàn toàn khác hẳn. Một trong những nguyên nhân làm nên tính khó giải của bài toán này là ở chỗ "hàm logarit rời rạc" biến thiên rất "thất thường", theo nghĩa: khi biết được giá trị của hàm tại một điểm nào đó thì ta chẳng thể nói gì về giá trị của hàm tại những điểm xung quanh. Ví dụ, khi biết rằng log7 5(mod 41) = 18 ta cũng rất khó mà đoán ra được rằng log7 4(mod 41) = 28 và log7 6(mod 41) = 39 . Cho đến nay, chưa có thuật toán tính logarit rời rạc nào được xem là khả thi đối với những số có độ dài cỡ trăm chữ số (cho dù máy tính có tốc độ siêu phàm, gấp cả trăm lần tốc độ máy tính nhanh nhất hiện nay). Chính sự khó khăn này đang được xem là chỗ dựa cho một số giải pháp quan trọng trong mã hóa thông tin hiện đại. Tương tự như vậy, khi biết trước các số tự nhiên k , n thì việc tìm số a thỏa mãn (*) cũng là một bài toán vô cùng khó, và được gọi là bài toán “khai căn” rời rạc.. 2.3. Ước chung của hai số và những vấn ₫ề liên quan Ước chung lớn nhất của hai số Ước chung lớn nhất của hai số tự nhiên a và b , kí hiệu (a, b) , là số tự nhiên lớn nhất trong các số chia hết cả a và b . Ta nói hai số a, b là nguyên tố cùng nhau nếu như (a, b) = 1 . Hiện nay sách giáo khoa vẫn còn đưa ra quy trình tìm ước chung lớn nhất của hai số thông qua việc phân tích từng số ra các thừa số nguyên tố rồi lấy tích của các thừa số chung với số mũ nhỏ hơn. Như đã chỉ ra ở trên, quy trình này là không khả thi với các số lớn, vì việc phân tích là không thực hiện được. Một quy trình thực sự khả thi lại chính là một trong những thuật toán cơ bản và lâu đời nhất của toán học, đó là thuật toán Ơ-cơ-lit. Thuật toán đó cho phép xác định ước chung lớn nhất của hai số nguyên có kích cỡ vài trăm chữ số một cách nhanh chóng. Thuật toán Ơ-cơ-lit Thuật toán Ơ-cơ-lit được dựa trên nhận xét đơn giản sau đây: Với a, b là các số tự nhiên ( a > b ), và r là số dư trong phép chia của a cho b , thì d là ước chung của a và b khi và chỉ khi d là ước chung của b và r . Từ nhận xét trên ta suy ra ước chung lớn nhất của a và b thì cũng là ước chung lớn nhất của b và r , tức là (a, b) = (b, r ) . Như vậy, ta có thể quy việc tính ước chung lớn nhất của hai số tự nhiên lớn ( a và b ) về việc tính ước chung lớn nhất của hai số nhỏ hơn ( a và r ), và đó chính là ý tưởng chủ đạo của thuật toán Ơ-cơlit. Hãy xét ví dụ sau. 16. (18) Ví dụ 1. Tính d = (123456789,121212). Dễ thấy rằng, với máy tính bỏ túi thông thường, quy trình phân tích hai số nêu trên ra thừa số nguyên tố để rồi lấy tích các thừa số chung là một việc vô cùng gian nan. Tuy nhiên, cũng bằng máy tính này, với thuật toán Ơ-cơ-lit ta có kết quả tính toán đơn giản sau đây. Trước hết ta lấy số lớn (là 123456789) chia cho số bé (là 121212) được số dư là 62973. Theo nhận xét trên ta có d = (123456789,121212) = (121212,62973).. Tiếp theo, ta lại lấy số lớn hơn (121212) chia cho số bé hơn (62973) được số dư là 58293, và lại theolập luận trên ta lại có d = (121212,62973) = (62973,58239). Cứ như thế tiếp tục quá trình này ta có kết quả tính toán như sau d = (58239, 4734) = (4734,1431) = (1431,441) = (441,108) = (108,9) = 9. Thuật toán Ơ-cơ-lit, mặc dù đã ra đời hàng nghìn năm, cho đến nay vẫn là thuật toán tốt nhất để tìm ước chung lớn nhất của hai số nguyên cho trước! Thuật toán này được ghi đơn giản như sau. Thuật toán Ơ-cơ-lit Bước 1. [Kết thúc?] Nếu b = 0 , cho ra a và kết thúc thuật toán. Bước 2. [Chia Ơ-cơ-lit] Ðặt r ← a mod b ,a ← b ,b ← r , và quay về Bước 1. Thuật toán Ơ-cơ-lit mở rộng Thuật toán Ơ-cơ-lit nêu trên không chỉ cho phép ta tìm được ước chung lớn nhất của hai số a, b là một số d , mà còn cho phép tìm ra hai số nguyên u, v thỏa mãn d = au + bv ,. tức là cho phép biểu diễn d dưới dạng tổ hợp tuyến tính của a và b (với các hệ số nguyên u, v ). Thật vậy, không làm mất tổng quát, ta có thể giả sử a > b và thuật toán Ơ-cơ-lit dừng sau n bước với kết quả cho ra là (a, b) = d . Theo thuật toán này, với a = r0 ,b = r1 , các bước tiếp sau sẽ là:. r0 = r1q1 + r2 ,. 0 ≤ r2 < r1 ,. (1). r1 = r2q2 + r3 ,. 0 ≤ r3 < r2 ,. (2). ............................. ............... rn −3 = rn −2qn −2 + rn −1 ,. 0 ≤ rn < rn −1 ,. (n-2). rn −2 = rn −1qn −1 + rn ,. 0 ≤ rn < rn −1 ,. (n-1). rn −1 = rnqn ,. ......... (n) 17. (19) trong đó rn = d . Theo bước thứ n − 1 ta thấy d = rn −2 − rn −1qn −1 , tức là d biểu diễn qua rn −1, rn −2 dưới dạng tổ hợp tuyến tính. Tiếp theo, do bước thứ n − 2 ta thấy rn −1 biểu diễn được qua rn −2 , rn −3 (dưới dạng tổ hợp tuyến tính) và điều này kéo theo d biểu diễn được qua rn −2, rn −3 (dưới dạng tổ hợp tuyến tính). Cứ tiếp tục như vậy, truy ngược về bước đầu tiên, ta suy ra d được biểu diễn dưới dạng tổ hợp tuyến tính qua r1, r0 (cũng tức là a, b ) và ta có điều khẳng định trên. Ví dụ 2. Với a = 123456789, b = 121212 , ta có (a, b) = 9 và, theo quy trình trên ta tìm ra được u = 1101, v = −1121390 .. Bội chung nhỏ nhất của hai số Bội chung nhỏ nhất của hai số tự nhiên a và b là số tự nhiên bé nhất trong các số tự nhiên chia hết cho cả a và b . Với hai số tự nhiên a, b bất kỳ, ta kí hiệu d = (a, b) và luôn có các phân tích sau đây a = dk1, b = dk2 , trong đó k1, k2 là hai số tự nhiên không có ước chung. Ta đặt m(a, b) := dk1k2 và dễ thấy rằng nó là một bội chung của a và b . Ta sẽ chỉ ra rằng nó là bội chung nhỏ nhất, tức là mọi bội chung khác của a và b đều phải chia hết cho m(a, b) . Thật vậy, giả sử số tự nhiên n là một bội chung nào đó của a và b , ta có n = ah = dk1h , với một số tự nhiên h nào đó. Do n chia hết cho b = dk2 ta suy ra k1h chia hết cho k2 . Vì k1 không có ước chung với k2 cho nên h phải chia hết cho k2 . Điều này kéo theo n chia hết cho dk1k2 và điều khẳng định đã được chứng minh. Từ đây ta có công thức tính m(a, b) = dk1k2 =. dk1dk2 ab ab = = . d d (a, b). Như vậy, thuật toán Ơ-cơ-lit cũng mang lại một giải pháp khả thi cho việc tính bội chung nhỏ nhất của hai số. Rõ ràng, với các số lớn, giải pháp này khả thi hơn nhiều so với quy tắc nêu trong một số sách trước đây nói rằng cần phải phân tích các số a và b ra thừa số nguyên tố rồi sau đó lấy tích của các thừa số riêng và chung với số mũ lớn hơn. Lưu ý rằng, để tránh gặp phải số lớn, khi áp dụng công thức trên ta nên tính (a, b) và thực hiện phép chia a cho (a, b) trước khi nhân với b . Ví dụ 3. Tính bội chung nhỏ nhất của hai số 1313 và 3131. Theo thuật toán Ơ-cơlit ta tính được ước chung lớn nhất của chúng là (1313, 3131) = 101 , cho nên bội chung nhỏ nhất của chúng được tính như sau m(1313, 3131) =. 1313 × 3131 1313 × 3131 = = 13 × 3131 = 40703 . (1313, 3131) 101 18. (20) Nghịch đảo theo modulo m Với số tự nhiên a cho trước, nếu tồn tại số tự nhiên b thỏa mãn điều kiện ab ≡ 1(mod m ) thì người ta gọi số b là nghịch đảo của số a theo modulo m (và viết b = a −1 mod m hay a = b −1 mod m ). Từ thuật toán Ơ-cơ-lit mở rộng, trong trường hợp riêng khi hai số a, b là nguyên tố cùng nhau (tức là (a, b) = 1 ), ta tìm được hai số u, v thỏa mãn au + bv = 1 , và điều này có nghĩa là u = a −1 mod b , v = b −1 mod a . Tóm lại, việc tìm nghịch đảo theo modulo là hoàn toàn khả thi nhờ thuật toán Ơ-cơ-lit mở rộng.. Trong trường hợp đặc biệt, khi m là một số nguyên tố, thì mọi số không phải là bội của m đều là nguyên tố cùng nhau với m và do đó cũng có nghịch đảo theo modulo m (nói riêng, mọi số tự nhiên nhỏ hơn m đều có nghịch đảo theo modulo m ). Ví dụ 4. Với m = 17 , ta có 2 = 9−1 mod17, 3 = 6−1 mod17, 4 = 13−1 mod17, 5 = 7−1 mod17, …. 3. MỘT SỐ HỆ MÃ DỰA TRÊN NHỮNG BÀI TOÁN KHÓ Như đã nói, một điều kì diệu là chính sự "hóc búa" của các bài toán số học lại là chỗ dựa cho mã hóa thông tin hiện đại, góp phần làm nên cuộc cách mạng trong lịch sử công nghệ mật mã.. 3.1. Thuật toán mã mũ Pohlig — Hellman Nguyên lý thực hiện Giả sử p là một số nguyên tố không nhỏ, và giả sử khoá lập mã e là một số tự nhiên sao cho e và (p - 1) là nguyên tố cùng nhau, tức là (e, p - 1) = 1 . Để có thể mã hoá các khối dữ liệu có độ dài m thì số nguyên tố p cần phải không bé hơn bất cứ khối nào, tức là phải chọn p sao cho độ dài của nó lớn hơn độ dài của m. Nếu như số đã p đã cho trước thì số m (độ dài khối) cần phải được chọn sao cho thoả mã điều kiện trên. Ta mã hoá một khối N (gồm m chữ) thành một khối C trong văn bản mã theo công thức sau: C ≡ N e (mod p) .. Đương nhiên, khối C cũng là một chữ số nhỏ hơn p. Để cho C không thể là chính N e thì số e phải được chọn không nhỏ quá, sao cho luôn có được N e > p . Giải mã. 19. (21) Như ta biết, việc “khai căn” rời rạc là vô cùng khó, nên muốn giải mã văn bản mật ta phải làm cách khác. Trước hết ta tính số d thoả mãn de ≡ 1 (mod p − 1) , có nghĩa d là một nghịch đảo của e modulo (p - 1) . Nghịch đảo này tồn tại do giả thiết ban đầu (e, p − 1) = 1 . Khi ấy de = k (p - 1) + 1 , với một số nguyên k nào đó, cho nên để giải mã khối văn bản mã C, ta áp dụng định lý Fermat (bé) và thực hiện phép nâng nó lên luỹ thừa bậc d rồi rút gọn theo modulo p , vì rằng k. C d = (N e )d = N de = N k (p -1)+1 = ( N p −1 ) ⋅ N .. và do vậy C d mod p = (N p −1 mod p)k .N mod p ≡ 1k ⋅ N (mod p) = N (lưu ý rằng do giả thiết ban đầu N < p ). Ví dụ: Lấy p = 3137 , e = 131 . Cho tương ứng mỗi chữ cái với một con số theo bảng sau đây A. B. C. D. Đ. E. G. .. ............. .. R. S. T. U. V. X. Y. 01. 02. 03. 04. 05. 06. 07. .. ............. .. 17. 18. 19. 20. 21. 22. 23. Thực hiện phép mã hóa văn bản bằng cách chia nó thành các khối 2 chữ cái và cho tương ứng mỗi khối với một số có 4 chữ số (ví dụ khối NA tương ứng với số 1301), sau đó áp dụng phép biến đổi nêu trên cho từng số này để thu được những số cũng có 4 chữ số (nếu số thu được nhỏ hơn 1000 thì thêm số 0 ở đằng trước). Dãy số thu được gọi là "văn bản mã". a) Mã hóa cụm chữ HANOIMOI theo nguyên tắc nêu trên. Lưu ý rằng e = 257 = 28 + 1 nên phép tính modulo của lũy thừa mũ 257 là thực hiện dễ dàng bằng phương pháp bình phương liên tiếp. Chia khối cụm chữ HANOIMOI thành ra HA NO IM OI rồi cho ứng với các số như quy định, ta được các số 0801, 1314, 0912 và 1409. Sau khi thực hiện các phép biến đổi theo quy định đối với từng số này ta được các số 0228, 0235, 0556, 2220. Như vậy "văn bản mã" là 0228 0235 0556 2220. b) Biết rằng 0228 1393 1076 là một "văn bản mã" trong phép mã nêu trên, hãy cho biết nội dung của văn bản trước khi mã. Dùng thuật toán Euclid mở rộng ta tính được số d thỏa mãn điều kiện ed ≡ 1 mod p là 1025. Dễ thấy d = 210 + 1 nên phép tính modulo của lũy thừa mũ 1025 là thực hiện dễ dàng bằng phương pháp bình phương liên tiếp. Áp dụng phép biến tính modulo lũy thừa 1025 đối với các số trong văn bản mã 0228 1393 1076 ta thu được các số 0801 0514 1307. Sau khi cho tương ứng trở lại với các chữ (theo bảng nêu trên) và viết liền nhau ta được cụm chữ HAĐONG.. 20. (22) Nhận xét Trong hệ mã nêu trên, số nguyên tố p có thể được cho công khai, nhưng các số e và d đều phải cùng được giữ bí mật (vì biết số này thì dễ dàng tìm ra số kia). Do vậy, hệ mã này thuộc vào loại mã bí mật (hay mã đối xứng). Tuy nhiên, ý tưởng về việc sử dụng định lý Fermat để thay thế phép tính "khai căn" rời rạc (của việc giải mã) bằng một phép tính luỹ thừa thì quả là tuyệt vời. Ta sẽ được thấy lại ý tưởng này trong hệ mã công khai (hay mã phi đối xứng) RSA.. 3.2. Thuật toán mã hóa khóa công khai RSA Các hệ mật mã truyền thống và một vấn đề nan giải của chúng Trong các hệ mã truyền thống, một nguyên tắc chung được thừa nhận là bản tin được lập mã bằng chìa khóa nào thì chỉ có thể được giải mã bằng chính chìa khóa đó. Vì vậy, một trong những vấn đề nan giải của những người sử dụng các hệ mã theo nguyên tắc này là việc chuyển giao chìa khoá từ người lập mã đến cho người giải mã. Càng ngày vấn đề càng trở nên nghiêm trọng, khi khả năng nắm bắt các luồng thông tin trên mọi môi trường trở nên dễ dàng (các kênh thông tin bí mật về phương diện "vật lý" hầu như không còn chỗ đứng). Điều này đã khiến cho những người làm mật mã cuối thế kỉ XX ước mơ có được một mô hình hệ mật mã với hai chìa khóa riêng biệt cho hai việc lập mã và giải mã. Mỗi cá thể tham gia vào hệ thống như vậy sẽ được cấp riêng một bộ 2 chìa khóa. Chìa khóa lập mã (còn gọi là chìa công khai) có thể được công bố công khai cho mọi người biết (để có thể mã hóa văn bản trước khi gửi tin mật cho cá thể này), còn chìa khóa giải mã (còn gọi là chìa bí mật) thì chỉ một minh cá thể đó được biết (nghĩa là, chỉ một mình cá thể này có thể giải mã các văn bản mật được mã hóa bằng chìa công khai của mình). Hệ mật mã như vậy gọi là hệ mã khóa công khai. Với hệ mã đó, vấn đề chuyển chìa khóa không còn được đặt ra. Thật vậy, khi cá thể A muốn gửi tin mật cho cá thể B thì chỉ cần lấy chìa lập mã của B (đã được công bố công khai) để mã hóa văn bản trước khi gửi đi cho B. Văn bản mã này có thể lưu hành công khai nhưng không ai, ngoài B, có thể giải mã được (vì chỉ B mới có chìa giải mã văn bản này). Mơ ước nói trên cuối cùng đã trở thành hiện thực vào những năm cuối của thập kỉ bảy mươi thế kỷ trước, nhờ sự thâm nhập của số học vào công nghệ mã. Hệ mã khóa công khai RSA Hệ mã này lần đầu tiên được công bố vào năm 1978 bởi ba nhà khoa học của Học viện Công nghệ Massachuset (Hoa Kỳ) là R. Rivest, A. Shamir và L. Adleman. Để xây dựng hệ mã, người ta chọn hai số nguyên tố p và q đủ lớn (có độ dài vào cỡ 150 chữ số thập phân), rồi tính n = p.q ,. φ = (p − 1).(q − 1) ,. 21. (23) và sau đó chọn số tự nhiên e sao cho (e, φ) = 1 , cùng số tự nhiên d = e −1 mod φ (bằng thuật toán Ơ-cơ-lit mở rộng). Văn bản nguồn trước hết được chuyển sang dạng số (nhờ một quy tắc đơn giản nào đó, không nhất thiết phải là bí mật). Tiếp theo, ta phân chia văn bản dạng số thành các khối số P (có số chữ số như nhau và nhỏ hơn số n ). Việc mã hóa văn bản sẽ được thực hiện một cách độc lập trên từng khối số như vậy. Với chìa khóa công khai là bộ số (e, n ) , việc mã hoá mỗi khối văn bản nguồn P được thực hiện bằng việc tính theo công thức C = P e mod n ,. và số C được gọi là khối văn bản mã tương ứng với P . Theo lẽ thường, khi biết C mà muốn tìm ra P thì người ta phải “khai căn rời rạc" bậc e (theo mod n ) của số C . Tuy nhiên, cũng như bài toán logarit rời rạc, khi số n là lớn thì bài toán này là không thể giải được (trong vòng cả trăm năm, với máy tính mạnh nhất hiện nay). Cho nên, để giải mã khối văn bản mã C , người ta áp dụng mệnh đề mở rộng định lí nhỏ của Phéc-ma. Trước hết, từ mệnh đề này ta có P φ mod n bằng 1 nên suy ra, với mọi số nguyên k bất kỳ, ta luôn có P k φ mod n bằng 1. Mặt khác, do d và e là nghịch đảo của nhau theo modulo φ , ta có de = 1 + k φ , với một số nguyên k nào đó, và như vậy C d mod n = (P e )d mod n = P 1+k φ mod n = P mod n ⋅ P k φ mod n = P ,. do P nhỏ hơn n . Tóm lại, có thể tính được P từ C bằng chính phép toán tương tự như trong quy trình lập mã, chỉ khác là thay số mũ e bởi số mũ d . Như đã biết, quy trình này là khả thi và khá nhanh. Như vậy, điểm mấu chốt của quy trình giải mã là phải biết được số d thỏa mãn điều kiện (e, φ) = 1 . Vì vậy, người ta gọi cặp hai số d và n là chìa khoá giải mã (hay chìa bí mật). Rõ ràng, từ e muốn tính ra d thì phải biết được φ và, người ta chứng minh được, điều này tương đương với việc phân tích số n thành tích p.q , một điều mà các máy tính mạnh nhất hiện nay cũng không thể làm được trong vòng hàng ngàn năm khi số n có chiều dài khoảng 300 chữ số thập phân. Ví dụ : Cho tương ứng mỗi chữ cái với một con số theo bảng đã biết ở trên, rồi thực hiện chia văn bản thành các khối 2 chữ cái và cho tương ứng mỗi khối với một số có 4 chữ số (tương tự như đã làm với hệ mã Pohlig-Hellman). Chọn p = 53 , q = 67 , e = 131 , rồi áp dụng phép biến đổi RSA nêu trên. a. Tính văn bản mã của cụm chữ NAMMOI. b. Biết rằng 1265 2266 1953 là một "văn bản mã" trong phép mã nêu trên, hãy tìm nội dung của văn bản trước khi mã. 22. (24) GIẢI a) Lưu ý rằng 131 = 27 + 2 + 1 , cho nên phép tính đồng dư của lũy thừa 131 có thể thực hiện dễ dàng bằng phương pháp bình phương liên tiếp. Theo phép tương ứng đã nêu, ta có NA MM OI = 1301 1212 1409 Áp dụng biến đổi RSA cho từng số trên, với n = 53 ⋅ 67 = 3551 , K = 52 ⋅ 66 = 3432 và e = 131 , ta thu được văn bản mã là: 0347 1530 2513. b) Vì 3432 − 131 ⋅ 26 = 26 và 131 − 26 ⋅ 5 = 1 nên 131 − 5 ( 3432 − 131.26 ) = 1 , hay 131 ⋅ (1 + 5 ⋅ 26) − 5 ⋅ 3432 = 1 ,. suy ra 131 ⋅ 131 = 1 mod 3432 , tức là ta có d = 131 = e (ăn may!!!). Áp dụng phép biến đổi RSA với số mũ d vừa tìm được cho từng số trong bản mã là 1265, 2266, 1953 ta thu được các số 1901, 1312, 0114. Chuyển về dạng chữ, theo bảng tương ứng giữa các chữ và các số nói ở trên, rồi viết liền nhau ta được cụm chữ TANMAO. Độ an toàn của hệ mã RSA Sau khi Rivest, Shamir và Adleman công bố phát minh về hệ mã đã nêu, trên tạp chí Nhà khoa học Mỹ có đưa ra lời thách thức người đọc bẻ khoá một mẩu tin nhỏ đã được mã hoá với: n=11438162575788886766923577997614661201021829672124236256256184 29357069352457338978305971235639587050589890751475992900268795 43541 e = 9007 . Một mẩu tin ngắn (chưa đầy nửa dòng) chỉ được giải mã sau 6 năm, bằng một cố gắng tổng lực mang tính quốc tế (qua internet) với việc sử dụng 1600 máy tính cực mạnh tấn công trong 8 tháng liên tục để phân tích số nêu trên ra thừa số nguyên tố. Qua đó ta thấy được rằng thuật toán RSA là rất an toàn, vì trên thực tế hệ mã chuẩn RSA sử dụng số n có độ dài lớn hơn hai lần như vậy và, với năng lực tính toán như trên, việc phân tích đòi hỏi thời gian thực hiện phải kéo dài trong nhiều ngàn năm. Phía sau trang sử về RSA Thiên hạ ngày nay đều biết hệ mã RSA được phát minh ra vào năm 1978 bởi 3 nhà khoa học của học viện MIT (Hoa Kỳ) là Rivest, Shamir, và Adleman.. 23. (25) . Rivest, Shamir, và Adleman (theo thứ tự từ trái qua phải) Thế nhưng năm 1997, Tổng hành dinh Thông tin Chính phủ Anh Quốc (GCHQ) mới tiết lộ sự thật về việc các chuyên gia mật mã của họ đã phát minh ra nguyên lý mã phi đối xứng từ năm 1969 (bởi James Ellis, nhà thám mã tài ba của nước Anh), thuật toán mã hóa phi đối xứng như RSA vào năm 1972 (bởi Clifford Cocks) và giao thức chuyển chìa khóa kiểu Diffie-Hellman-Merkle vào năm 1975 (bởi Malcolm Williamson). Họ là ai và sự thật đã diễn ra như thế nào? Người ta biết rằng vấn đề chuyển chìa khóa giải mã ngày càng trở nên nan giải, khi khả năng nắm bắt các luồng thông tin trên mọi môi trường trở nên dễ dàng (các kênh thông tin bí mật về phương diện "vật lý" hầu như không còn chỗ đứng). Đầu năm 1969, quân đội Anh đã đặt vấn đề tìm giải pháp cho vấn đề này với James Ellis, một trong những chuyên gia thám mã lỗi lạc của Tổng hành dinh Cơ quan truyền thông Chính phủ Anh quốc (Government Communications Headquarters GCHQ) tại Cheltenham. Ông đã dành nhiều công sức cho việc nghiên cứu đề tài này và phát hiện ra rằng có những giải pháp truyền tin mật mà không đòi hỏi người gửi tin phải "gửi chìa khoá". Một mô hình "vật lý" được ông phát hiện qua một công trình của Claude Shannon (và cộng sự), được hình dung như sau: người nhận tin (theo một kênh truyền nào đó) có thể tự mình làm nhiễu đường truyền (bằng một nhiễu nào đó có bản chất mà chỉ riêng mình được biết), còn người gửi cứ việc thả thông tin vào kênh truyền nhiễu đó. Người nhận tin (qua đường truyền nhiễu) dễ dàng lọc được nhiễu do chính mình tạo ra, còn kẻ "nghe trộm" trên đường truyền thì chịu chết! Đến cuối năm 1969 thì James Ellis đã coi như đến được với nguyên lý cần tìm, khi ông nảy ra ý tưởng “toán học hóa” mô hình vật lý nêu trên bằng hàm một chiều có 24. (26) bẫy. Hàm một chiều có thể được ví như "cái hom giỏ": người ta chỉ có thể tính được "đầu ra" từ các thông tin "đầu vào", mà không thể tính ngược để tìm ra "đầu vào" trên cơ sở các thông tin về "đầu ra". Với hàm một chiều có "bẫy" thì việc "tính ngược" là thực hiện được khi biết một thông tin đặc biệt nào đó (cái bẫy). Tiếc rằng James Ellis không phải là nhà toán học, cho nên khi ấy (1969) cái hàm một chiều có bẫy mà ông hình dung ra đã không đến với ông. Ông đem tâm sự với một đồng nghiệp ở GCHQ là Patterson.. Đến tháng 9 năm 1973, một "tân binh" mới gia nhập vào nhóm, đó là Clifford Cocks - một sinh viên mới tốt nghiệp Đại học Cambridge, ngành toán, với chuyên ngành sâu về lĩnh vực Lý thuyết số (trước đó 5 năm, 1968, anh đã từng tham dự Kỳ thi Olympic Toán Quốc tế của học sinh phổ thông, tổ chức tại Moscow, Liên Xô cũ). Người hướng dẫn công tác của tân binh này, ông Patterson, nói cho Cocks về ý tưởng độc đáo của James Ellis như một câu chuyện để biết (chứ không hy vọng để có thể giải quyết được gì). Tuy nhiên, Cocks đã suy nghĩ nghiêm túc về vấn đề này, vì anh là người làm về lý thuyết số và hàm một chiều đối với anh không phải là xa lạ. Số nguyên tố và vấn đề phân tích ra thừa số được Cocks chọn làm "ứng cử viên" đầu tiên. Chỉ trong vòng khoảng nửa giờ, mô hình trọn vẹn về hàm một chiều có bẫy đã đến với Cocks khá dễ dàng (đến mức bản thân Cocks không tự cảm nhận được đầy đủ ý nghĩa của kết quả mình đạt được). Đương nhiên, ngay từ năm 1973, các đồng nghiệp trong GCHQ hiểu rõ tầm quan trọng của vấn đề mà Cocks đã giải quyết. Kết quả của Cocks đã được giữ tuyệt mật. Nó có sức thuyết phục lớn trong nội bộ GCHQ, nhưng nó cũng chịu cái "bất hạnh" của việc "đi trước thời gian". Phương tiện tính toán nghèo nàn và yếu ớt thời đó tại Anh Quốc đã không cho phép triển khai ngay được thuật toán, và vì vậy GCHQ chưa khai thác được mật mã với khoá công khai. Năm sau, 1974, Cocks đem vấn đề triển khai thuật toán "phàn nàn" với anh bạn “cố tri” là Malcolm Williamson, người cùng học phổ thông, cùng tốt nghiệp Đại học Cambridge, cùng đi thi toán Quốc tế tại Moscow, và bây giờ cũng lại vừa mới đến gia nhập GCHQ. 25. (27) Williamson không tin ngay được kết quả của Cocks, và cố gắng tìm xem Cocks mắc sai lầm ở đâu. Sau một thời gian nghiên cứu, Williamson không tìm được sai lầm nào, nhưng lại tìm ra giải pháp mới cho vấn đề "chuyển chìa" mà các nhà quân sự đang ao ước, đó cũng chính là giao thức trao đổi chìa "Diffie-Hellman-Merkle" mà các nhà khoa học Hoa Kỳ phát minh ra (gần như cùng thời gian đó). Tóm lại, cho đến 1975, James Ellis, Clifford Cocks và Malcolm Williamson đã phát minh ra toàn bộ nền tảng cơ sở của mật mã với khoá công khai, nhưng đã để trong im lặng, và ngồi dõi theo các nhà khoa học Mỹ "phát minh lại" các kết quả ấy trong 3 năm sau. Chỉ có điều hơi ngược về trình tự, ở Anh người ta tìm ra hệ mã công khai trước khi tìm ra giao thức chuyển chìa khoá, còn ở Mỹ thì ngược lại.. Clifford Cocks và Malcolm Williamson đều là thành viên đội tuyển Anh đi thi toán quốc tế ở Moscow năm 1968 (một người giải bạc và một người giải vàng), sau đó họ đều tốt nghiệp Đại học Cambridge về chuyên ngành Lý thuyết số.. 3.3 Thuật toán mã hóa El Gamal Nguyên lý thực hiện Giả sử rằng những người tham gia vào hệ thống sử dụng hệ mã (ký hiệu là: A,B,C,... ) cùng nhau thống nhất chọn một số nguyên tố p (công bố công khai). Người ta dễ dàng tìm được một (trong số rất nhiều) số g < p sao cho mọi số tự nhiên nhỏ hơn p đều có thể biểu diễn dưới dạng lũy thừa của g theo mod p (số g này cũng được công bố công khai, và được gọi là phần tử cơ sở). Mỗi người chọn riêng cho mình một con số làm chìa khoá bí mật, thường được ký hiệu tương ứng là kA, kB , kC ,... Những giá trị g kA , g kB , g kC ,... được công bố công 26. (28) khai (cũng được xem là chìa khoá công khai). Ta biết rằng từ các số này không thể tính ra được các chìa khoá bí mật của từng người, khi p được chọn đủ lớn. Giả sử A muốn chuyển cho B một thông báo mật M (đã chuyển sang dạng số hoá và nằm trong khoảng giữa 0 và p). Khi ấy, A cần chọn ngẫu nhiên một số s trong khoảng từ 1 đến p − 1 và tính cặp số ( g s , Mg s .kB ) để gửi cho B. Cặp số này A tính được dễ dàng nhờ đã biết trước phần tử cơ sở g và khoá công khai g kB của B. Khi nhận được cặp số này, B có thể tính ra được M bằng thủ tục gồm 2 bước: 1. Lấy số thứ nhất (trong cặp số) nâng lên luỹ thừa với bậc bằng khoá bí mật của mình, tức là nhận được ( g s )kB = g s .kB . 2. Lấy nghịch đảo của số vừa nhận được (theo mod p ) bằng thuật toán Euclid, rồi đem nhân với số thứ hai (trong cặp số đã nói), tức là có −1 −1 ( g skB ) .M .g skB = ( g skB ) .g skB .M = M . Rõ ràng ngoài B ra không ai có thể thực hiện được điều này, và do đó hệ mã này là rất an toàn. Tuy nhiên, A cần phải thận trọng khi lấy số ngẫu nhiên s để không ai có thể đoán ra được nó (mỗi lần nên dùng một số khác nhau). Nếu như kẻ gian biết trước được s thì nó có thể lấy chìa khoá công khai của B để nâng lên luỹ thừa bậc s và giải mã ra M như là B đã làm ở bước thứ hai. Nhận xét: Hệ mã ElGamal khai thác triệt để tính một chiều của hàm mũ. Lược đồ mã kiểu này không chỉ áp dụng được cho hệ mã sử dụng hàm mũ mà có thể áp dụng được rất nhiều loại hàm một chiều khác. Một điều đáng lưu ý là tính "không bình đẳng" giữa 2 chìa khoá cũng như giữa 2 quá trình lập mã và giải mã đã làm cho thuật toán ElGamal không có được vẻ đơn giản và những ứng dụng độc đáo như RSA mà ta đã thấy ở trên. Tuy nhiên, sự tham gia của số ngẫu nhiên s lại làm cho phép mã mạnh thêm rất nhiều, vì rằng cùng một văn bản nhưng đem mã vào những thời điểm khác nhau thì ra những văn bản mã khác nhau. Điều này làm cho công việc thám mã trở nên khó khăn gấp bội.. 3.4. Thay cho lời kết Trên đây chỉ là một số nét “chấm phá” về bức tranh mã hóa thông tin thời hiện đại mà chúng ta có thể cảm nhận được từ góc nhìn của toán phổ thông. Trên thực tế, đây là một lĩnh vực mênh mông của các ứng dụng Toán cao cấp: Lý thuyết nhóm, Đại số Bul, Lý thuyết số và Hình học Đại số, Xác suất thống kê, Toán học rời rạc,... Để năm bắt được chúng, xin hãy bước vào thế giới Toán cao cấp.. 27. (29)

Tài liệu liên quan

Lý thuyết về mật mã hóa thông tin, xây dựng server tạo khóa cho user trong vấn đề bảo mật dữ liệu
- 97
- 1
- 6
KỲ THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG NĂM 2007 Môn thi: TIẾNG ANH - Phân ban - Mã đề thi 147
- 26
- 517
- 0
KỲ THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG NĂM 2007 Môn thi: HOÁ HỌC - Phân ban - Mã đề thi 138
- 26
- 463
- 0
KỲ THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG NĂM 2007 Môn thi: VẬT LÍ - Phân ban - Mã đề thi 214
- 42
- 286
- 0
KỲ THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG NĂM 2007 Môn thi: TIẾNG NGA - Phân ban - Mã đề thi 143
- 34
- 388
- 0
KỲ THI TỐT NGHIỆP TRUNG HỌC PHỔ THÔNG NĂM 2007 Môn thi: TIẾNG PHÁP - Phân ban-Mã đề thi 153
- 26
- 468
- 3
Tài liệu Đề thi - Đáp án môn Vật lí - Tốt nghiệp THPT Giáo dục trung học phổ thông ( 2013 ) Mã đề 872 pptx
- 6
- 561
- 0
Tài liệu Đề thi - Đáp án môn Vật lí - Tốt nghiệp THPT Giáo dục trung học phổ thông ( 2013 ) Mã đề 916 pot
- 6
- 496
- 0
đề thi tốt nghiệp trung học phổ thông năm 2012 môn hóa học - mã đề859
- 4
- 298
- 0
đề thi tốt nghiệp trung học phổ thông năm 2012 môn hóa học - mã đề748
- 4
- 308
- 0