Lý thuết mật mã | Sơ lược về mật mã

[hailoc12]

Mật mã

Các phương pháp đơn giản
Trong số các phương pháp đơn giản nhất ( và xưa nhất ) dùng để bảo mật là mật mã Caesar: nếu một chữ cái trong vản bản thật là kí tự thứ N trong bảng mẫu tự, thì thay nó bằng kí tự thứ (N+K) trong bảng mẫu tự, trong đó K là một số nguyên không đổi nào đó ( Caesar đã dùng K=3). Bảng dưới đây cho thấy làm thế nào một thông điệp được mã hoá bằng cách dùng phương pháp này với K=1
Văn bản thật: ATTACK AT DAWN
Văn bản mã: BUUBDLABUAEBXO
Phương pháp này yếu vì người giải mã chỉ phái đoán giá trị của K; bằng cách thử từng trường hợp một trong số 26 cách chọn, anh ta có thể đảm bảo rằng anh ta sẽ đọc đựơc thông điẹp.
Một phương pháp tốt hơn nhiều là dùng một bảng tổng quát để định nghĩa sự thay thế sẽ đựơc tạo ra: đối với mỗi chữ cái trong văn bản thận, bẳng sẽ cho biết chữ cái nào sẽ được đặt vào trong văn bản mã. Ví dụ, nếu bảng cho sự tương ứng.
ABC DEF GHI JKLMN OPQRSTUVWXYZ
THE QUI CKB ROWNF XJMPDVRLAZYG
thì thông điệp sẽ được mã hoá như sau:
Văn bản thật: ATTACK AT DAWN
Văn bản mã: HVVH OTHVTQHAF
Cách này mạnh hơn nhiều so với mật mã Caesar đơn giản, vì người giải mã sẽ phải thử nhiều bảng hơn ( khoảng 27!>10^28) để đảm bảo đọc đựơc các thông điệp. Tuy nhiên, các bộ mã " thay thế đơn giản" giống như bộ mã này thì dễ dàng bị mở do các tần số chữ cái vốn có trong ngôn ngữ. Ví dụ, vì E là ký tự thông thường nhất trong văn bản tiếng Anh, người giải mã có thể nhận đựơc một điểm khởi đầu tốt khi đọc thông điệp bằng cách tìm chữ cái thường xuất hiện nhất trong văn bản mã và thay nó bằng E. Trong khi điều này có thể không hẳn là một lựa chọn đúng, nhưng nó lại đặc biệt tốt hơn việc thử tất cả 26 chữ cái một cách mò mẫm. Trường hợp tốt hơn nữa ( cho người giải mã ) là khi bắt gặp các tổ hợp hai chữ cái ( digram): các digram cụ thể ( như QJ) không bao giờ xảy ra trong văn bản tiếng Anh trong khi những chữ cái khác ( như ER) lại rất phổ biến. Bằng cách xét các tần số của các chữ cái và các tổ hợp ký tự, một nhà giải mã học có thể mở khoá một bộ mã thay thế đơn giản một cách dễ dàng.
Một cách để khiến cho kiểu tấn công này trở nên khó khăn hơn là dùng nhiều bảng hơn. Một ví dụ đơn giản của điều này là một sự mở rộng cùa bộ mã Caesar đựơc gọi là bộ mã Vigenere: một khoá lặp nhỏ sẽ đựơc dùng để xác định giá trị của K cho mỗi kí tự. Ở mõi bước, chỉ mục của chữ cái khoá được cộng thêm với chỉ mục ký tự văn bản thật để ác định chỉ mục của ký tự văn bản mã. Văn bản mẫu thật của chúng ta, với khoá ABC, đựơc mã như sau:
Khoá: AB CABCABC ABCAB
Văn bản thật: ATTACK AT DAWN
Van bản mã: BVWBENACWAFDXP
Cho ví dụ, chữ cái cuối cùng của văn bản mã là P, là chữ cái thứ 16 của bảng mẫu tự, do ký tự văn bản thật tương ứng là N ( chữ cái thứ 14) và chữ cái khoá tương ứng là B ( chữ cái thứ hai ).
Bộ mã Vigenere hiển nhiên có thể được chế tạo một cách phức tạp hơn bằng cách dùng các bảng tổng quát khác cho mỗi chữ cái của văn bản thật ( thay vì chỉ là các độ dời đơn giản ). Cũng vậy, hiển nhiên là khoá càng dài, thì bộ mã càng tốt hơn. Thực vậy, nếu khoá dài bằng văn bản thật, ta có bộ mã Vernam, được gọi một cách phổ biến hơn là đệm một lần ( one-time pad). Đây là hệ mật mã an toàn tuyệt đối duy nhất được biết, và nó

[hailoc12]

được dùng một cách công khai cho đường dây nóng Washington-Moscow và những ứng dụng trọng yếu khác. Vì mỗi một ký tự khoá đựơc dùng chỉ một lần, người giả mã có thể không còn cách nào tốt hơn là thử mọi chữ cái chìa khoá có thể có, cho mỗi một vị trí trong thông điệp, một trường hợp vô vọng hiển nhiên vì điều này khó ngang với việc thử tất cả các thông điệp có thể có. Tuy nhiên, dùng mỗi một chữ cái khoá chỉ một lần hiển nhiên dẫn tới một bài toán phân phối khoá dịch vụ, và việc đệm - một lần sẽ chỉ hữu ích đối với các hông điệp tương đối ngắn, không thường xuyên được gửi đi.
Nếu thông điệp và khoá được mã trong dạng nhị phân, ,một cơ chế phổ biến hơn để mã hoá từng vị trí một là dùng hàm "hoặc loại trừ " (XOR): để mã văn bản thật , "xor" nó ( từng bit một ) với khoá. Một đặc trưng hấp dẫn của phương pháp này là việc giải mã có cùng thao tác với việc mật mẫ: văn bản thật là sự XOR văn bản mã và khoá sẽ trả về văn bản thật. Chú ý rằng việc XOR của văn bản mã và văn bản thật sẽ là khoá. Điều này thoạt đầu có vẻ là đáng ngạc nhiên, nhưng thực sự nhiều hệ mật mã có tính chất là người giải mã có thể phát hiện ra khoá nếu như anh ta biết được văn bản thật.

Các máy mật mã / giải mã
Nhìêu ứng dụng mật mã ( ví dụ, các hệ thống tiếng nói dùng cho truyền thông quân sự ) có liên quan đến việc truyền đi một lượng lớn dữ liệu, và điều này khiến cho việc đệm một lần là không phù hợp. Những cái mà ta cần là xấp xỉ với đệm một lần trong đó một lượng lớn "chìa khoá giả " có thể được tạo ra từ một lượng nhỏ các khoá thật sé đựơc phân phối.
Cài đặt thông thường trong những trường hợp như vậy là như sau: một máy mật mã được cung cấp một vài biến mật mã ( cryptovariables) (khoá thực) bởi nơi gửi, dùng để tạo ra một dòng bit khoá dài ( khoá giả ). Việc XOR của các bit này và văn bản thật tạo ra văn bản mã. Nợi nhận có một máy tương tự và các biến mật mã, dùng chúng tạo ra cùng dòng khoá để XOR dựa trên văn bản mật mã và để lấy lại được văn bản thật.
Việc tạo khoá trong ngữ cảnh này rất giống với việc băm và phát sinh số ngãu nhiên. và các phương pháp đựơc bàn lậun trong chương 16 và 35 là thích hợp cho việc phát sinh khoá. Thực vậy, một vài cơ chế đựơc bàn luận trong chương 35 đầu tiên đã được phá triển cho việc sử dụng trong các máy mật mã \ giải mã như những cái được mô tả ở đây. Tuy nhiên, bộ phát sinh khoá phỉa là một cái gì đó phức tạp hơn các bộ sinh số ngẫu nhiên, vì có những cách để tấn công các máy đơn giản. Vấn đề là người giải mã có thể dễ dàng nhận dược một văn bản thật nào đó ( ví dụ nghe lén một hệ tiếng nói ), và do đó nhận được một khoá nào đó. Nếu người giải mã biết đủ về máy, thì khoá có thể cung cấp đủ các chi tiết rắc rối để cho phép các giá trị của tất cả các biến mật mã có thể được mô phổng và tất cả khoá được tính toán bắt đầu từ điểm đó.
Các nhà mật mã học có nhiều cách để tránh được những vấn đề như vậy. Có một cách là khiến cho một bô phận kiến trúc của chính máy đó trở thành một biến mật mã. Thông thường ta giải định làn người giải mã biết mọi thứ về kiến trúc của máy ( có thể là một cái máy bị đánh cắp ) ngoại trừ các biến mật mã, nhưng nếu một vài biến mật mã được dùng để "tạo cấu hình " cho máy, thì có thể khoá tìm được các giá trị của chúng. Một phương pháp khác đựơc sử dụng phổ biến để làm rối trí người giải mã là bộ mã sinh ( product cipher), trong đó hai máy khác nhau được tổ hợp lại để sinh ra một dong fkhoá phức tạp ( hay để điều khiển lẫn nhau . Phương pháp khác là thay thế không tuyến tính; ở đây việc dịch giữa văn bản thật và văn bản mã được thực hiện trong những đoạn lớn, không phải là từng bit một. Vấn đề thường thấy đối với các phương pháp phức tạp như vậy là chúng có thể là quá phức tạp ngay cả đối với nhà mật mã học để hiểu đựơc nó, và luôn luôn có khả năng là sự việc có thể trở nne tồi tệ hơn đối với mọt vài sự lựa chọn các biến mật mã nào đó.
Các hệ mật mã khoá - công khai
(Public - key cryptosystems)
Trong các ứng dụng thương mại như chuyển ngân điện tử và thư tín máy tính ( thực sự ) , bài toán phân phối khoá là nặng nề hơn so với các áp

[hailoc12]

dụng mật mã cổ điển. Khuynh hướng cung cấp các khoá dài mà nó phải được thay đổi thường xuyên cho mọi công dân, trong khi vẫn tiếp tục duy trì cả tính an toàn lẫn hiệu quả chi phí, sẽ cản trở rất nhiều đến việc phát triển các hệ thống như vậy. Tuy nhiên, các phương pháp gần đây được phát triển, sé hứa hẹn việc loại bỏ bài toán phân phối khoá mọt cách an toàn. Những hệ thống như vậy, được gọi là các hệ mật mã khoá công khai, rất có thể sẽ được sử dụng rộng rãi trong tương lai gần. Một trong những điểm nổi bật nhất của các hệ thống này là dựa trên một vài thuật toán số học ta đang nghiên cứu, vì vậy ta sẽ xem xét kĩ hơn nó hoạt động như thế nào.
Ý tưởng trong các hệ mật mã khoá công khai là dùng một " danh bạ điện thoại " các khoá mật mã. Khoá mật mã củamỗi người ( kí hiệu bởi P ) là tri thức công cộng: khoá của một người có thể được liệt kê, ví dụ như, nằm kế số điện thoại của anh ta trong cuốn danh bạ điện thoại. Mỗingười cũng có một khoá bí mật được dùng để giải mã; khoá bí mật này ( đựơc kí hiệu bởi S) không được biết bởi bất kì ai khác. Để chuyển đi một thông báo M, người gửi tra ra khoá công khai của người nhận, dùng khoá đó để mã hoá thông điệp, và sau đó gửi thông điệp đi. Ta sẽ ký hiệu thông điệp đã đựơc mã hoá ( văn bản mã ) là C=P(M). Người nhận dùng khoá giải mã riêng để giải mã và đọc thông điệp. Để cho hệ thống này hoạt động, ít nhất các điều kiện sau phải được thoả mã
(i) S(P(M))= M đối với mọi thông điệp M
(ii) Tất cả các cặp (S, P) là phân biệt
(iii) Việc phát sinh S từ P là khoá ngang với việc đọc M
(iv) Cả S lẫn P đều đựơc tính dễ dàng
Điều kiện đầu tiên là một tính chất của mật mã căn bản, ,hai điều kiện sau cung cấp tính an toàn , và cái thứ tự là cho hệ thống trở nên dễ dùng.
Lược đồ tổng quát này đã được tóm lược bởi W.Diffie và M.Hellman vào năm 1976, nhưng họ đã không có phương pháp nào thoả mãn được tất cả các điều kiệnnào. Một phương pháp như vậy đã dược khám phá chẳng bao lâu ngay sau dó bởi R.Rivest, A.Shamir và L.Adleman. Lựơc đồ của họ, ,được biết đến như là hệ mật mã khoá công khai RSA, dựa trên các thuật toán số học được thực hiện trên các số nguyên rất lớn. Khoá mật mã P là cặp số nguyên (N, p) và khoá giải mã S là cặp số nguyên (N, s), trong đó s là bí mật. Các số này dự kiến sẽ là rất lớn ( đặc biệt, N có thể tới tới 200 chữ số và s có thể là 100 chữ số). Các phương pháp mật mã và giải mã thì đơn giản: đầu tiên thông điệp đựơc ngắt thành các số nhỏ hơn N ( ví dụ, bằng cách lấy lgN bits ở từng thời điểm từ chuỗi nhị phân tương ứngvới mã hoá ký tự của thông điệp). Sau đó các số này được nâng lên luỹ thừa một cách độc lập rồi modulo cho N: để mật mã một ( mẩu một ) thông điệp M, ta tính C=P(M)= M^p mod N, và để giải mã một văn bản C ta tính M= S(C)=C^s mod N. Trong chương 36 ta sẽ nghiên cứu làm thế nào để thực hiện phép tính này khi mà việc tính toán với cá số 200 chữ số có thể là gặp trở ngại, tuy nhiên việc ta chỉ cần lấy phần dư sau khi chia cho N hiểu là ta có thể giữ cho các số khôg trở nên lớn, bất chấp sự kiện là chính M^p và C^s là các số lớn không tưởng tượng nổi.
Tính chất 23.1: Trong các hệ mật mã RSA, một thông điệp có thể đựơc mã trong khoảng thời gian tuyến tính.
Đối với các thông điệp dài, độ dài của các số được dùng cho các khoá có thể được coi nhưu là hằng- một chi tiết cho cài đặt. Tương tự, nâng một số lên một lũy thừa thì đựơc thực hiện trong khoảng thời gian hằng, vì các số không được phép dài hơn một độ dài "hằng". Thực ra, tham số này che giấu nhiều chi tiết cài đặt có lịên quan đến việc tính toán các con số dài: chi phí của các phép toán này thực sự là một yếu tố ngăn cản sự phổ biến khả năng ứng dụng của phương pháp.
Điều kiện (iv) ở trên vì vậy được thoả mãn, và điều kiện (ii) có thể dễ dàng bị ép thoả mẫn. Ta vẫn phải tiếp tục bảo đảm rằng các biến mật mã N, p và s có thể được chọn sao cho có thể thoả (i) và (iii). Để các điều kiện này trở nên có sức thuyết phục hơn thì phải cần đến sự trình bày về lý thuyết số mà nó nằm ngoài phạm vi của quyển sách này, nhưng chúng ta có thể

[hailoc12]

tóm lược các ý chính. Đầu tiên, cần tạo ra 3 số nguyên tố "ngãu nhiên " lớn ( xâp xỉ 100 chữ số ): số lớn nhâtsex là s và ta sẽ gọi hai số còn lại là x và y. Sau đó N đựơc chọn sẽ là tích của x và y, và p thì đựơc chọn sao cho ps mod (x-1)(y-1)=1. Có thể chứng minh rằng, với N, p và s được chọn theo cách này, ta có M^ps mod N= M đối với tất cả các thông điệp M.
Ví dụ với việc mã hoá chuẩn của chúng ta, thông điệp ATTACK AT DAWN có thể tương ứng một số nguyên 28 chữ số
0120200103110001200004012314
vì A là chữ cái đầu tiên ( 01) trong bản mẫu tự, T là chữ cái thứ 20(20)...Bây giờ để cho ví dụ là nhỏ, ta bắt đầu với một vài số nguyên tố 2 chữ số ( thay vì 100 chữ số như đã yêu cầu ): lấy x=47, y=79 và s=97. Những giá trị này dẫn tới N= 3713( tích của x và y) và p=37 ( số nguyên duy nhất mà nó cho phần dư là 1 khi được nhân cho 37 và chia cho 3588). Bây giờ để mã hoá thông tin, ta ngắt nó thành ra từng đoạn 4 số và nâng lên luỹ thừa p ( modulo N). Điều này cho ra bản đã được mã hoá.
14042932353600012328422802235
Nghĩa là, 0120^37 đồng dư 1404, 2001^37 đồng dư 2932, 0311^37 đông dư 3536 ( mod 3713)...tiêns trình giải mã cũng giống như vậy, dùng s thay cho p. Vì vậy ta nhận đựơc trở lại thông điệp gốc vì 1404^97đồng dư 0120, 2932^97 đồng dư 2001 (mod3713)...
Phần quan trọgn nhất của các con tính có liên quan dến việc mã hoá thông điệp, như đã bàn trong tính chát 23.1 ở trên. Nhưng sẽ không có hệ mật mã nào hết nếu như không thể tính được các biến chìa khoá. CHo dù điều này có ám chỉ cả lý thuyết số tinh vi lẫn các chương trình tinh xảo để thao tác trên các số lớn, thời gian để tính toán các khoá có lẽ là nhỏ hơn bình phương đồ dài của chúng ( và không tỉ lệ với độ lớn của chúng , mà điều đó là không thể chấp nhận được )
TÍnh chất 23.2 Các khoá cho hệ mật mã RSA có thể được tạo ra mà không phải tính toán quá nhiều.
Một lần nữa, ta lại cần đến một vài phương pháp dựa trên lý thuyết số mà nó nằm ngoài phạm vị của cuốn sách này; mỗi số nguyên tố lớn có thể đạơc phát sinh bằng cách đầu tiên tạo ra một số ngẫu nhiên lớn, sau đó kiểm tra các số kế tiếp bắt đầu từ điểm đó cho tới khi tìm được một số nguyên tố. Một phương pháp đơn giản thực hiện một phép tính trên một con số ngẫu nhiên, mà với xác xuất là 1/2 sẽ "chứng minh " rằng số được kiểm tra là không nguyên tố. Bước cuối cùng là tính p: có lẽ sẽ chỉ cần đến một biến thể của thuật toán Euclid ( xem chương 1).
Nhớ lại là khoá giải mã s ( và các thừa số x và y của N) sẽ được giữ bí mật, và sự thành công của phương pháp tuỳ thuộc vào việc người giải mã không có khả năng để tìm giá trị của s, nếu cho trước N và p. Bây giờ đối với vị dụ nhỏ của chúng ta, dễ phát hiện ra rằng 3713=47*79, nhưng nếu N là một số 200 chữ số, thì có ít hy vọng để tìm ra các thừa số của nó. Nghĩa là, có vẻ khoá tìm ra đựơc s từ tri thức về p ( và N ) mặc dù không ai có thể chứng minh điều đó. Rõ rnàng, tìm p từ s cần tri thức về x và y, và rõ ràng cần phân tích N ra thừa số dể tính x và y. Nhưng việc phân tích N ra thừa số là rất khó: các thuật toán phân tích ra thừa số tốt nhất đã được biết cần hàng triệu năm để phân tích một số 200 chữ số ra thừa số dùng kĩ thuật hiện có.
Một đặc trưng hấp dẫn của hệ RSA là các tính toán phức tạp ám chỉ N, p và s được thực hiện chỉ một lần cho mỗi một người sử udngj có đăng kí với hệ thống, trong khi đó thì rất nhiều thao tác mật mã và giải mã thông thường chỉ ngắt thông điệp và áp dụng thủ tục lũy thừa đơn giản. Sự đơn giản về mặt tính toán này, kết hợp với tát cả các đặc trưng thuận lợi được cung cấp bởi các hệ mật mã khoá công khai, đã khiến cho hệ thống này thật hấp dẫn cho việc truyền thông đơn giản, đặc biệt trên các hệ thống máy tính và mạng máy tính.
Phương pháp RSA có nhựơc điểm của nó: thủ tục lũy thừa thực sự tốn kém bởi các tiêu chuẩn mật mã, và tệ hơn là về lâu về dài, có khẳn năng đọc được các thông điệp đã được mật mã bằng các dùng phương pháp này. Điều này là đúng đối với nhiều hệ mật mã: một phương pháp mật mã phải chống lại được các cuộc tấn công để giải mã một cách nghiêm túc trước khi nó có thể được dùng với sự tin tưởng.
Nhiều phương pháp khác đã được đề nghị để cài đặt các hệ mật mã khoá công khai. Một vài phương pháp thú vị nhất đã được gắn với một lớp bài toán quan trọng mà nó thường được xem là rất khó ( mặc dù điều này không chắc lắm ), mà ta sẽ nghiên cứu trong chương 45. Các hệ mật mã này có một tính chất thú vị là một cuộc tấn công thành công có thể cung cấp một cái nhìn sâu hơn về cách làm thế nào để giải được một vài bài toán khó nổi tiếng chưa giải đựơc ( như việc phân tích ra thừa số đối với phương pháp RSA). Việc liên kết giữa mật mã học với các chủ đề cơ sở trogn nghiên cứu khoa học máy tính, cùng với khả năng sử dụng rộng rãi mã khoá công khai, đã khiến cho lĩnh vực này trở thành một môi trường nghiên cứu rất năng động hiện nay.

Một số thảo luận về Mã hoá trong diễn đàn
http://diendan.congdongcviet.com/sho...p?t=183&page=3
http://diendan.congdongcviet.com/showthread.php?t=1873

[tutinit]

trùi ui !
bạn học chuyên sâu về mật mã sao?