Đăng ký Đăng nhập
Trang chủ Tiểu luận môn lý thuyết số số học và lý thuyết mã...

Tài liệu Tiểu luận môn lý thuyết số số học và lý thuyết mã

.DOC
8
359
73

Mô tả:

Số học và lý thuyết mật mã ___________________________________________________________________________ LỜI NÓI ĐẦU Khoảng ba thập kỷ gần đây, sự phát triển của Tin học đã làm thay đổi nhiều ngành truyền thống của Lý thuyết số. Một phương hướng mới của số học đã ra đời và phát triển mạnh mẽ: Số học và thuật toán. Nội dung cuốn tiểu luận này đề cập đế những nguyên lý chung của mật mã khóa công khai và hệ mã RSA. Lý do chúng tôi chọn đề tài này vì nó mang tính thời sự sâu sắc. Nội dung cuốn tiểu luận này chia làm hai phần: Phần A: Nguyên lý chung Trình bày những nguyên lý chung của mật mã khóa công khai. Phần B: Hệ mã RSA Trình bày hệ mã RSA và ứng dụng của nó trong đời sống. Vì thời gian và trình độ có hạn nên tiểu luận chắc chắn không tránh khỏi có nhiều sai sót. Rất mong sự góp ý của Thầy giáo hướng dẫn và các bạn để tiểu luận hoàn thiện hơn. Chúng tôi xin chân thành cảm ơn sự hướng dẫn nhiệt tình của GS- TSKH Hà Huy Khoái và những đóng góp ý kiến của các bạn cùng khóa Cao học K9 Trường Đại học Quy Nhơn đã giúp chúng tôi hoàn thành tốt tiểu luận này. 1 Số học và lý thuyết mật mã ___________________________________________________________________________ PHẦN A. NGUYÊN LÝ CHUNG Hệ mật mã mà chúng ta nguyên cứu được lập theo nguyên tắc trong đó việc biết khóa lập mã không cho phép tìm ra khóa giải mã trong một thời gian chấp nhận được. Vì thế mỗi cá thể chỉ cần giữ bí mật khóa giải mã riêng của mình, trong khi khóa lập mã được công bố công khai. Trong trường hợp một trong các cá thể bị lộ khóa giải mã của mình, bí mật của các cá thể còn lại không hề bị ảnh hưởng. Lý do của việc có thể xây dựng những hệ mã như vậy chính là điều khi xét đến các hệ mã mũ: độ phức tạp của thuật toán tìm logarit modulo p là quá lớn. Trước hết, ta nói sơ qua về nguyên tắc của hệ mã khóa công khai. Giả sử trong hệ thống đang xét có n cá thể cùng trao đổi các thông tin mật. Mỗi cá thể chọn cho mình một khóa lập mã k và một công thức mã hóa E(k), được thông báo công khai. Như vậy có n khóa lập mã công khai k 1, k2, …, kn. Khi cá thể thứ i muốn gửi thông báo cho cá thể thứ j, cũng như trước đây, mỗi chữ trong thông báo được chuyển thành số, nhóm thành từng khối có độ dài nào đó. Sau đó, mỗi khối P trong văn bản được mã khóa bằng khóa lập mã E(k j ) của cá thể thế j (đã thông báo công khai), và gửi đi dưới dạng C = E(k j ) (P). Để giải mã thông báo này, cá thể thứ j chỉ cần dùng khóa giải mã (bí mật riêng cho mình) D k j D k j (C) = D k j , E k j (P) = P, bởi vì D k j và E k j là các khóa giải mã và lập mã của cùng cá thể thứ j. Các cá thể trong hệ thống, nếu nhận được văn bản mật, cũng không thể nào giải mã, vì việc biết khóa lập mã E k j không cho phép tìm ra khóa giải mã D k j . 2 Số học và lý thuyết mật mã ___________________________________________________________________________ PHẦN B. HỆ MÃ RSA 1. Hệ mã RSA Hệ RSA được xây dựng trên cơ sở mã mũ, trong đó khoá lập mã là cặp (e, n) gồm số mũ e và số modun n. Số n được dùng ở đây là tích của hai số nguyên tố rất lớn nào đó, n = pq, và e được chọn sao cho (e,  (n))  1 , trong đó  (n) là hàm Euler (trong trường hợp này  (n) = (p – 1)(q – 1). Để mã hoá một thông báo, trước tiên ta mã hoá các chữ cái thành các số tương ứng và nhóm thành các khối với độ dài đủ lớn (tuỳ thuộc khả năng tính toán và không vượt quá số n) với một số chẵn chữ số. Để mã hoá một khối P trong văn bản, ta lập khối C trong văn bản mật bằng công thức: E(P) �C �Pe (mod n), 0 < C < n. Quá trình giải mã đòi hỏi phải biết một nghịch đảo d của e modulo  (n) . Nghịch đảo này tồn tại theo điều kiện (e,  (n) ) = 1. Muốn giải mã một khối C trong văn bản mật, ta tính D(C ) �C d �( P e ) d �P ed �P k ( n ) 1 �( P ( n ) ) k P �P (mod n), trong đó ed = k  (n) + 1 đối với số nguyên k nào đó, vì ed �1(mod  (n) ), và do định lý Euler ta có: P ( n ) �1(mod p ) , khi (P,n) = 1 (chú ý rằng, xác suất để P và n không nguyên tố cùng nhau là hết sức nhỏ, vì điều đó chỉ xảy ra khi P có ước là p hoặc q). Cặp (d,n) được gọi là khoá giải mã. Ví dụ: lấy n = 53.61 = 3233 và e = 17. Ta có (e,  (n))  1 . Giả sử ta cần mã hóa thông báo sau: ĐA GƯI TIÊN Trước tiên ta chuyển các chữ cái trong văn bản thành các số tương ứng và nhóm chúng thành từng khối 4 chữ số. Ta có: 0701 1026 1224 1209 1628 Ta mã khóa các khối nhờ công thức C �P17 (mod 3233) Ta lại dùng công thức bình phương liên tiếp. Chẳng hạn, đối với khối đầu tiên, ta nhận được: (701)17 �140(mod 3233) Mã hóa toàn bộ văn bản, ta được văn bản sau đây: 140 721 1814 1819 361 Khi nhận được văn bản mật này, để giải mã, ta phải tìm một nghịch đảo d của e modulo  (3233) . Ta có  (53.61) = 52. 60 = 3120. Dùng thuật toán Euclid mở rộng, ta tính được d = 2753. Như vậy, để giải mã khối C ta dùng công thức P �C 2753 (mod 3233), 0 �P �3233 . Có thể thử lại C 2743 �( P17 ) 2753 �P( P 3210 )15 �P(mod 3233) , 3 Số học và lý thuyết mật mã ___________________________________________________________________________ Ở đây ta dùng định lý Euler để nhận được P (3233) �P3120 �1(mod 3233) , khi (P,3233) = 1 (điều này đúng cho mọi khối trong văn bản của chúng ta). Bây giờ ta chỉ ra rằng, hệ mã RSA thỏa mãn các nguyên tắc của hệ mã khóa công khai. Trước tiên, ta chú ý rằng, mỗi cá thể phải chọn hai số nguyên tố lớn hơn p và q, cỡ chừng 100 chữ số thập phân. Điều này có thể thực hiện trong ít phút nhờ một máy tính. Khi các số nguyên tố p và q đã được chọn, số mũ dùng để mã hóa e sẽ được lấy sao cho (e,  (qp)) = 1. Nói chung nên chọn e là số nguyên tố tùy ý lớn hơn q và p. Số e được chọn phải nhất thiết thỏa mãn 2e > n = pq. Nếu điều kiện này không được thỏa mãn, ta có C = Pe < n, và như vậy để tìm ra P, ta chỉ việc tính căn bậc e của C. Khi điều kiện 2e > n được thỏa mãn, mọi khối P khác 0 và 1 đều được mã hóa bằng nâng lên lũy thừa và lấy đồng dư theo modulo n. Ta cần phải chứng tỏ rằng, việc biết khóa lập mã (công khai) (e, n) không dẫn đến việc tìm được khóa giải mã (d,n). Chú ý rằng, để tìm nghịch đảo d của e modulo  (n) , trước tiên phải tìm được  (n) . Việc tìm  (n) không dễ hơn so với phân tích n, bởi vì, một khi biết  (n) và n, ta sẽ phân tích được n =pq. Thật vậy, ta có: p + q = n -  (n) +1 p  q  ( p  q )2  4 pq  ( p  q ) 2  4n Từ các công thức đó tìm được q và p. Nếu chọn các số p và q khoảng 100 chữ số thập phân, thì n sẽ có khoảng 200 chữ số thập phân. Để phân tích một số nguyên cỡ lớn như thế, với các thuật toán nhanh nhất hiện nay và với những máy tính hiện đại nhất, ta mất hàng tỷ năm! Có một vài điều cần lưu ý khi chọn các số p và q để tránh rơi vào trường hợp tích pq bị phân tích nhanh nhờ những thuật toán đặc biệt: q và p cần chọn sao cho p – 1 và q – 1 phải có các thừa số nguyên tố lớn, ước chung lớn nhất (p – 1, q – 1) phải nhỏ, q và p phải có số chữ số trong khai triển thập phân khác nhau không nhiều. 2.Xác nhận chủ thể với hệ mã RSA 4 Số học và lý thuyết mật mã ___________________________________________________________________________ Có thể nảy ra câu hỏi: trong một hệ thống nhiều cá thể tham gia, các khóa lập mã đã lại được công khai, làm sao có thể tránh được trường hợp một cá thể này “mạo danh” một cá thể khác để gửi thông báo cho một cá thể thứ ba? Nói cách khác làm sao có thể “kí tên” dưới các thông báo mật? Vấn đề này được giải quyết nếu sử dụng hệ mã RSA. Cách làm đơn giản như sau: Để gửi văn bản P cho ông J, trước tiên ông I dùng khóa công khai Ej ( của ông J) để tính Ej(P), sau đó lại dùng khóa bí mật của mình để tính Di(Ej(P)) = C và gửi đi. Khi nhận được C, ông J sẽ dùng khóa công khai Ei ( của ông I) để tính Ei(C) = Ei(Di(Ej(P))) = Ej(P), rồi sau đó dùng khóa bí mật Dj của mình để tính ra Dj(Ej(P)) = P. Thủ tục này tránh mọi sự mạo danh có thể xảy ra như đã nêu ở trên, nhưng giá phải trả cũng không ít: cần phải thêm một lần mã hóa toàn bộ văn bản. Với tốc độ xử lý chậm của RSA thì điều này chỉ có thể khả thi khi văn bản là nhỏ. Với các văn bản lớn (thí dụ như bộ luật, văn kiện, tập hồ sơ,…) chúng ta cần một “biến thể” tinh tế hơn của giao thức trên, với sự tham gia của hàm băm mật mã. Hàm này có khả năng “chiết xuất” từ văn bản (có độ dài tùy ý) ra một xâu ký tự( có độ dài xác định khoảng vài trăm bít) đại diện cho văn bản đó, để người ta có thể “ ký” lên xâu ký tự đại diện này thay vì “ký” trực tiếp vào văn bản. Để nắm được bản chất của giao thức ký điện tử này, ta cần phải hiểu bản chất của hàm băm mật mã. Định nghĩa: Hàm băm H(x) từ tập các xâu ký tự có độ dài bất kỳ vào tập các xâu ký tự có độ dài xác định k là một hàm có thể tính toán được dễ dàng (tốc độ nhanh) với mọi giá trị của biến x, và đồng thời thỏa mãn các điều kiện sau: 1) Không thể tìm (trong thời gian chấp nhận được) hai giá trị x 1 �x2 mà lại có H(x1) = H(x2)(tính kháng xung đột); 2) Cho y trong tập giá trị của hàm H, không thể tìm được x sao cho H(x) = y (tính kháng tiền ảnh) Tính chất thứ nhất đảm bảo rằng không có hai văn bản nào khác nhau mà lại có giá trị băm như nhau. Tính chất thứ hai cho thấy rằng không thể “mạo” ra một văn bản khác có cùng giá trị băm với một văn bản cho trước. Như vậy giá trị băm của văn bản có thể xem như là đại diện cho văn bản về hai khía cạnh “độc tôn” và “toàn vẹn”: mỗi văn bản có riêng một giá trị băm, nếu văn bản bị thay đổi thì giá trị băm sẽ thay đổi. Như vậy, sự toàn vẹn của văn bản x đồng nghĩa với sự toàn vẹn của giá trị băm H(x). Với hàm băm mật mã, giao thức ký điện tử sẽ được thực hiện một cách hiệu quả hơn hẳn. Thay vì phải mã văn bản x (bằng khóa mật của mình), người gửi I chỉ cần mã giá trị băm H(x), tức là tính S  Di ( H ( x))  ( H ( x)) d mod ni . Trước hết cần lưu ý rằng việc ký văn bản không bao hàm việc bảo mật (trên thực tế nhiều văn bản không cần giữ bí mật, mà chỉ cần bảo đảm sự toàn vẹn và tính xác thực của chủ nhân phát hành văn bản, như các chứng chỉ, văn bằng, thông tư,…). Cho nên , nếu không cần phải bảo mật văn bản x, thì ông I có thể gửi văn bản x cùng với “chữ ký” S đến cho người nhận. Người nhận có i 5 Số học và lý thuyết mật mã ___________________________________________________________________________ thể kiểm tra tính “xác thực” của ông I bằng việc lấy chìa khóa công khai của ông I để giải mã “ chữ ký” S tìm ra H(x), rồi sau đó kiểm tra sự toàn vẹn của văn bản x ( không bị thay đổi trên đường đi) bằng cách cho hàm H băm văn bản x nhận được rồi so sánh giá trị băm này với giá trị nhận được ( do ông I gửi). Nếu hai giá trị khớp nhau thì người nhận biết đích xác là văn bản do ông I gửi và không hề bị thay đổi trên đường đi ( còn người gửi I không thể phủ nhận rằng mình đã “ký” văn bản đó, vì chỉ có ông ta mới có cái khóa bí mật di). Nếu muốn kết hợp việc ký văn bản với bảo mật văn bản thì sau khi tính được chữ ký S, người gửi I cần tiến hành mã hóa toàn bộ văn bản cùng chữ ký S bằng chìa khóa công khai của người nhận J. Còn ông này thì phải thêm một bước giải mã gói tin nhận được ( bằng chìa khóa bí mật của mình) trước khi tiến hành kiểm chữ ký và tính toàn vẹn của văn bản. 6 Số học và lý thuyết mật mã ___________________________________________________________________________ TÀI LIỆU THAM KHẢO  1 Hà Huy Khoái. Bài giảng môn Lý thuyết số.  2 Hà Huy Khoái, Phạm Huy Điển. Số học thuật toán – cơ sở lý thuyết và tính toán thực hành. NXB ĐHQG Hà Nội 2003. 7 Số học và lý thuyết mật mã ___________________________________________________________________________ MỤC LỤC TRANG 1 1 2 2 4 6 1.Phần A. 2.Nguyên lý chung 3.Phần B 3.1 Hệ mã RSA 3.2 Xác nhận chủ thể với hệ RSA 4.Tài liệu tham khảo 8
- Xem thêm -

Tài liệu liên quan