Tài liệu Giới thiệu về hệ mật RSA

xe mod n x Zn . Người ta đã coi rằng f là hàm một chiều và chúng ta dễ dàngkiểm tra hàm ngược của f là f-1 được xác định như sau: f-1(x) yd mod n x Zn . như vậy nếu biết được d thì việc tính f-1 sẽ trở nên vấn đề “dễ” vậy giá trị d trên chính là cửa sập của f. Tất nhiên hiện nay người ta cũng chưa tìm được thuật toán hữu hiệu nào cho phép tìm được d mà không cần tìm p,q do vậy có thể ngầm hiểu rằng việc tìm được d cũng tương đương việc tìm được p, q. Tuy nhiên ở phần sau chúng ta sẽ thấy thậm chí việc biết d cũng không giúp ích gì lắm cho việc tìm p và q. Xây dựng mạng thông tin theo hệ mật RSA. Trong hệ mật RSA thì không gian các bản rõ P, không gian xác các bản mã chính là Zn còn không gian khoá K={(e,d,n): ở đây n là tích của hai số nguyên tố p và q với e*d 1 mod (n)} Mạng thông tin theo hệ mật RSA được thiết lập như sau: Mỗi thành viên Mi trong hệ thống chọn cho mình một khoá (ei,di,ni) K. Công bố ei và ni làm thông tin công khai để mọi người mã hoá thông tin muốn gửi cho anh ta theo luật C X ei mod ni và giữ thông tin “cửa sập” di để giải mã các bản mã thông tin gửi cho mình theo luật C X di mod ni. Tính khả thi của thuật mã hoá và giải mã trong hệ RSA Ta thấy rằng để mã hoá hay giải mã một thông báo theo luật RSA chính lf việc thực hiện một phép tính luỹ thừa modulo n. Việc tính toán này chỉ cần thực hiện trong thời gian O(log3 n) với đơn vị tính là thời gian để thực hiện một thao tác cơ sở của máy tính. Với một số công bố gần đây người ta đã chỉ ra rằng thời gian tính đó chỉ còn là O(log2 n) với việc sử dụng biến đổi Furier nhanh. Theo các tài liệu công bố hiện nay thì những thiết bị phần cứng mật mã RSA hiệu quả nhất hiện nay chỉ đạt tốc dộ khoảng 600 Kb/s tức là chậm hơn 1500 lần so với hệ mật DES (1 Gb/s) như vậy việc mã dịch bằng luật RSA vẫn còn bị hạn chế về mặt thờ gian do về mặt thực tế thì hệ mật RSA có lẽ chỉ dùng đẻ thực hiện các tính năng ưu việt của nó như phân phối mầm khoá tự động, xác thực... Độ an toàn của hệ mật RSA. Bài toán phân tích số và việc phá hệ mật RSA. Cách tấn công dẽ thấy nhất đối với hệ mật RSA là người thám mã sẽ cống gắng phân tích n rathừa số nguyên tố n=p*q và khi đó anh ta dễ dàng tính được (n)=(p-1)(q-1) và do đó tìm được thông tin cửa sập D tương ứng với thông tin mã hoá E bằng thuật toán Euclide. Như vậy chúng ta thấy ngay rằng việc phá hệ mật RSA là “dễ hơn” bài toán phân tích số nguyên ra thừa số nguyên tố tuy nhiên cũng chưa có một kết quả nào chỉ ra rằng bài toán phân tích số là thực sự khó hơn cho nên người ta thườn thừa nhận rằng bài toán phá hệ RSA là tương đương với bài toán phân tích số nguyên thành thừa số người. để đảm bảo tính khó phân tích ra thừa số của n=p*q thì yêu cầu đầu tiên là p,q là các số nguyên tố lớn xấp xỉ bằng nhau và là số nguyên tố “mạnh “. Khái niệm “mạnh” ở đây chỉ bắt nguồn từ ý nghĩa khó phân tích do vậy nó sẽ được bổ xung cùng với kết quả có được của khả năng phân tích số. Nói một cách khác là khái niệm “mạnh” bao gồm sự loại trừ các lớp số nguyên tố mà với chúng tồn tại thuật toán phân tích hiệu quả, chúng ta có thể biết đén một khái niệm sơ khai của tính “mạnh” đó là các số nguyên tố p mà p-1 và p+1 có chứa thừa số nguyên tố lớn. Việc tấn công hệ mật RSA khác phương pháp phân tích số. Trong [Stínon] đưa ra chứng minh một kết quả thú vị là một thuật toán bất kỳ để tính số mũ giải mã D đều có thể được dùng như một chương trình con trong thuật toán xác suất kiểu Las Vegas để phân tích n. Như vậy mặc dù rằng nếu D bi lộ thì việc phân tích n cũng không còn ý nghĩa theo quan điểm phá hệ mật tuy nhiên kết quả trên dù sao cũng cho ta một thuật toán phân tích số n khi biết D với xác suất thành công không quá 1/2 của mỗi lần chọn số ngẫu nhiên làm đầu vào cho thuật toán. Các thuật toán phân tích số. Trong phần này em giới thiệu một số thuật toán phân tích số nguyên được coi là “mạnh nhất” theo nghĩa thời gian tính tốt nhất hiện nay. Việc trình bày của chúng tôi dựa trên quan điểm không phải là đưa ra thuật toán chi tiết nhằm mục đích phân tích số nguyên mà chủ yếu nêu ra ý tưởng của thuật toán và quan trọng nhất là đưa ra thông số về thời gian tính của chúng nhằm chứng minh cho kích thước tối thiểu của các modulo được sử dụng trong mật mã theo dạng tích hai số nguyên tố lớn.Các thuật toán được kể đến bao gồm thuật toán sàng bậc hai, thuật toán phân tích trên đường cong Elliptic, thuật toán sàng trường số.... nhưng do hai thuật toán sau đều cần phải có kiến thức bổ trợ khá cồng kềnh về đại số hiện đại vả lại điều kiện về tài liệu lại không đủ chi tiết nên em chỉ trình bày thuật toán sàng bậc hai và cũng dừng ở những nét chính yếu nhất. a. thuật toán sàng bậc hai. Tư tưởng chủ đạo của một loạt khá lớn các thuật toán phân tích số như phương pháp đặc biệt của Euler, phương pháp phân tích các dạng chính phương của Danien Shanks, phương pháp triển khai liên phân số của Morrison và Brillhart, phương pháp sàng bậc hai của Pomerance .. là cố tìm đồng dư thức x2 y2 mod N sao cho x y mod N, còn kỹ thuật tìm cụ thể như thế nào thì chính là nội dung riêng của từng thuật toán. Đối với thuật toán sàng bậc hai của Pomerance được thực hiện như sau: - Chọn k là số nguyên tố đầu tiên và gọi là cơ sở phân tích. - Chọn B là một số nào đó gọi là ngưỡng tìm các thặng dư bậc hai nhỏ. - Tìm k+1 các thặng dư bậc hai nhỏ hơn B và phân tích được hoàn toàn trong tập cơ sở trong lớp các số dạng Q(x) ((m+x)2- N) mod N với k là số phần tử của cơ sở, m = [] còn x=0, 1, 2,.... - Xây dựng đồng dư thức x2 y2 mod N từ k+1 thặng dư bậc hai tìm được trên. Cơ sở thuật toán chủ yếu dựa vào thứ nhất là khả năng tìm được k+1 thặng dư bậc hai và tiếp đến là xây dựng đồng dư thức x2 y2 mod N như thế nào. Trước hết chúng ta cùng xem xét đến vấn để thứ hai. Giả sử thặng dư bậc hai thứ i tìm được ở trên là ri = i2= q11. q22.... qkk. (qj là số nguyên tố thứ j của B), ta đặt tương ứng với véc tơ vi [GF(2)]k như sau ri khác nhau được ứng cùng với véc tơ v nhưng một cách hình thức ta có thể coi có k+1 véc tơ khác nhau thu từ việc ứng k+1 giá trị r có được ở trên. Hiển nhiên trong không gian k chiều GF(2)k thì tập k+1 véc tơ vi (i=1,2,...,k+1) chắc chắn phụ thuộc tuyết tính, giả sử ta có tổ hợp tuyết tính đặc trưng cho phụ thuộc đó là: aivi với là véc tơ không và ai không đồng dư bằng không. khi đó Q(Xi) theo định nghĩa sẽ là x2 mod N, mặt khác do điều kiện đặt ra ở trên là Q(xi) phân tích được hoàn toàn trong tập cơ sở cùng với điều kiện aivi tức là vế phải của tích Q(Xi) chứa toàn các số mũ chẵn đối với các thừa số trong cơ sở do vậy nó cũng là một thặng dư bậc hai y2 nào đó. Nừu xy mod N thì chúng ta sẽ thành công việc phân tích N với các thừa số tương ứng là gcd(xy,N). Người ta chỉ ra rằng khả năng thành công xảy ra với xác xuất là 0.5 do vậy thời gian tính của thuật toán chủ yếu phụ thuộc vào giai đoạn tìm thặng dư bậc hai nhỏ và giai đoạn tìm hệ thức phụ thuộc tuyến tính (thông thường bằng phép khử Gauss). Với việc tìm các thặng dư bậc hai nhỏ thoạt tiên chúng ta nhận thấy rằng do Q(x+rp) [(m+x+rp)2 -N] mod N {[(m+x)2 - N] + rp [2(m+x) + rp]} mod N Q(x) + rp [2(m+x) + rp] mod N nên : Nếu p là ước của Q(x) thì nó cũng là ước của Q(x + rp) với mọi số nguyên r. Từ kết quả trên chúng ta thấy rằng nếu tồn tại giá trị x theo yêu cầu Q(x) phân tích hoàn toàn trong cơ sở và không quá B thì ta có thể tìm được nó chỉ cần trong lân cận B của 0. Ngoài ra còn một số kết quả ( xem [Riesel]) khác cũng không kém phần quan trọng đó là : Điều kiện cần và đủ để x sao cho p là ước của Q(x) là kí hiệu Legendge(N/p) =1. Như vậy không phải toàn bộ các số nguyên tố trong cơ sở đều phải được biểu diễn (đúng hơn là chỉ có khoảng một nửa số nguyên tố trong cơ sở là có mặt trong biểu diễn các Q(x)) do đó để thu được hệ phụ thuộc tuyến tính nêu trong phân tích trên thì thường chỉ cần số phương trình khoảng già nửa số các số nguyên tố trong cơ sở là đủ. Nếu p 3 mod 4 thì giá trị x -m N(p+1)/4 mod p là các giá trị < p thoả mãn p là ước của Q(x). Nếu p 1 mod 4 thì việc tìm các giá trị x tương ứng có thể bằng một thuật toán gần đa thức. Nếu x<p thoả mãn p là ước của Q(x) và p+1 không là ước của Q(x) thì giá trị y< p+1 có p+1 là ước của Q(y) có thể tìm được là y=x+r p với r là nghiệm của phương trình đồng dư bậc nhất sau 2(x+m)- N (chú ý rằng phương trình trên luôn luôn có duy nhất một nghiệm). Với hai kết quả trên rõ ràng chúng ta luôn luôn tìm được toàn bộ giá trị x trong một phạm vi B cho trước nào đó mà với chúng Q(x) có ước lẻ trong tập cơ sở phân tích. Trường hợp p=2 việc thu được kết quả na ná như trên ta có phức tạp hơn, em không có đủ tài liệu để mô tả tường minh việc tìm đó ở đây. Tóm lại quá trình tìm thặng dư bậc hai nhỏ có thể mô tả như sau : - Chọn một ngưỡng B nào đó và sàng để tìm giá trị x nhỏ nhất <B mà với chúng p là ước của Q(x). - Các thặng dư bậc hai nhỏ Q(x) = R2 = q11. q22.... qkk. nếu có thì chỉ cầm tìm theo r= 0, 1, 2,.. tại những giá trị Q(x) với x= x0+ s q11. q22.... qkk, ở đây x0 là giá trị nhỏ nhất để q11. q22.... qkk là ước của Q(x) mà ta có thể phát hiện được ở bước trên. Tất cả các phân tích được nêu ở trên mặc dù chưa đủ chặt chẽ cho sự đảm bảo thành công việc tìm thặng dư bậc hai nhỏ trong lớp Q(x) mà chỉ dừng ở mức độ thể hiện một mô tả bước tìm kiếm này sẽ được thông qua một quá trình “sàng” theo cơ sở của những kết quả nêu trên nhằm loại bỏ các giá trị không thể là ứng cử viên cho các thặng dư bậc hai nhỏ. Một số tài liệu (xem [Dixon], [Lenstra],...) đã phân tích về thời gian tính của thuật toán và số liệu khả quan nhất về vấn đề này của Lenstra là: với O(1) là một hàm tiến tới 0 khi N. b. Thời gian tính của một số thuật toán phân tích khác. Thuật toán phân tích dựa trên đường cong elliptic cũng là một thuật toán có thời gian tính khá tốt. Thuật toán thực sự là mở rộng của thuật toán kiểu phân tích p-1 của Pollard theo ý thay cho sự “phải phân tích được p-1 ra các thừa số” bằng một cái gì đó gần như thế mà cơ sở của nó là sự có cấu trúc của các điểm trên đường cong elliptic. Thời gian tính của thuật toán này được đánh giá là : với p là ước nhỏ nhất của N. Thoạt tiên ta có thể thấy ngay thuật toán này tỏ ra hơn hẳn thuật toán sàng bậc hai nếu hai ước của N chênh lệch nhau nhiều. Tuy nhiên nếu hai ước của N xấp xỉ nhau thì thuật toán sàng bậc hai thường tỏ ra hiệu quả hơn. Thuật toán sàng trường số là thuật toán mới nhất, thuật toán này cũng phân tích số nguyên N bằng cách xây dựng đồng dư thức x2 y2 mod N nhưng việc thực hiện bằng các tính toán trên các vành đại số. Sàng trường số đang trong thời kỳ nghiên cứu tuy nhiên theo dự đoán chung thì nó chứng tỏ nhanh nhất với các số có trên 125 chữ số thập phân. Thời gian tính của thuật toán sàng trường số là: . để phân tích các số RSA thì phương pháp sàng bậc hai là thành công nhất. Vào năm 1983 thuật toán sàng bậc hai đã phân tích thành công các số có 69 chữ số thập phân. Tới năm 1989 số chữ số thập phân của các số phân tích được là 106 chữ số thập phân bởi việc phân bố việc tính toán phân tích trên hàng trăm máy tính làm việc riêng biệt. Gần đây nhất trong tháng 4 năm 1994 Atkin, Graff, Lenstra và Leyland đã phân tích được một số có 129 chữ số thập phân. Việc phân tích con số trên phải thực hiện trong hàng năm tính toán trên máy 5000 MIPS (Triệu lệnh trên một giây) do 600 nhà nghiên cứu trên toàn thế giới thực hiện. II NHỮNG ỨNG DỤNG CỦA HỆ MẬT RSA 1. Sơ đồ chữ ký hệ mật RSA. Chữ ký thông thường trên một tài liệu là phương tiện dùng để xác nhận tài liệu đó clà của người ký nó. Chữ kí điện tử là phương pháp ký một bức điện dưới dạng điện tử được lưu hoặc truyền trên mạng máy tính. Vậy sự khác nhau cơ bản của chữ ký thông thường và chữ ký điện tử là gì ? Trước hết chữ ký thông thường là một phần vật lý của chính văn bản, trong khi chữ ký điện tử không gắn kết theo kiểu vật lý vào bức điện nên thuật ngữ toán được dùng phải “không nhìn thấy” theo một nghĩa nào đó trên bức điện. Thứ hai là vấn đề kiểm tra. Chữ ký thông thường được kiểm tra bằng các so sánh nó với mẫu đã đăng ký trước về nó. Ûong khi chữ ký điện tử phải được kiểm tra công khai bằng một thuật toán mà khi bất cứ ai cũng có thể kiểm tra được đồng thời phải thoả mãn yêu cầu chống trả khả năng giả mạo cao. Một sơ đồ ký gồm hai thành phần: Thuật toán ký và thuật toán kiểm tra chữ ký. Dưới đây là định nghĩa hình thức về chữ ký. định nghĩa 2.1. Một sơ đồ chữ ký là một bộ 5 gồm (P,AS,K,S,V). Trong đó: P là tập hữu hạn các bức điện có thể có. A là tập hữu hạn các chữ ký có thể có. K là tập hữu hạn có thể có thẻ có thoả mãn điều kiện kK tồn tại một thuật toán ký SigK S. và một thuật toán kiểm tra VerK V trong đó SigK : PA và VerK PxA {true/false} là những hàm số sao cho với mỗi bức điện x P và chữ ký y A ta có: VerK (x,y)=true khi và chỉ khi y= SigK(x). Thường thì mỗi K thì VerK , SigK là các hàm thời gian đa thức. VerK sẽ là hàm công khai còn SigK là hàm bí mật. Như Vậy sẽ không thể tính toán để giả mạo chữ ký trên bức điện x được, nghĩa là với x cho trước thì chỉ có chủ nhân của nó mới có thể “ký” trên có theo công thức đã nêu y = SigK(x) để đảm bảo VerK(x,y) =true. Cũng như đối với các hệ mật khoá công khai khác, sơ đồ chữ ký trên không thể an toàn vô điều kiện vì đối với x cho trước “kẻ giả mạo” có thể dùng phương pháp vét cạn để kiểm tra bằng hàm công khai VerK(x,y) cho tất cả các chữ ký y cho đến khy tìm ra y để VerK(x,y)=true. Với mục đích tìm một sơ đồ chữ ký an toànvề mặt tính toán người ta đề xuất sử dụng hệ RSA dùng trong mục đích trên như sau : Với hệ RSA như trình bày ở phần trước thì hàm giải mã được dùng làm hàm ký Sig, chữ ký chính là giá trị y xd mod n hàm kiểm tra Ver(x,y) = true khi va chỉ khi x ye mod n. Hiển nhiên sơ trên thoả mãn yêu cầu về một sơ chữ ký và được gọi là sơ đồ chữ ký RSA. 2/. Tạo dãy số giả ngẫu nhiên RSA. Một ứng dụng ít phổ biến hơn nhưng cũng khá quan trọng là việc tạo ra các xâu bit giả ngẫu nhiên trong mật mã bằng hệ RSA. Trước hết chúng ta dưa ra định nghĩa về việc tạo dãy ngẫu nhiên như sau. Dịnh nghĩa 3.1..cho k,l là các số nguyên dương sao cho l>k+l. Một bộ tạo bit ngẫu nhiên (k,l) là hàm f : Z2k Zl2 tính được trong thời gian đa thức (như một hàm của k ). Giá trị đầu vào S0 Zk2 dược gọi là mầm và giá trị đầu ra F( S0 ) là một xâu các bit ngẫu nhiên. Như chúng ta đã quen thuộc thì để tạo được hệ mật có khoá hoàn thiện thì các dùng phải một lần và là xâu bit ngẫu nhiên cùng độ dài với xâu bit ngẫu nhiên cùng độ dài với xâu bit biểu diễn bản rõ với mã pháp là phép cộng mod 2 các bit tương ứng của rất rõ và xâu khoá. Phương pháp tạo xâu bit ngẫu nhiên có thể giải quyết vấn đề trên trong các sơ đồ mật mã khoá sinh tự động. Trong sơ đồ trên người gửi và người nhận thoả thuận với nhau cùng một bộ sinh khoá giả ngẫu nhiên và thông báo cho nhau về mầm khoá trên một kênh bảo mật. Như vậy mầm khoá có chức năng như khoá mật thông thường và bộ sinh (k,l) có chức năng tạo khoá dùng cho hệ mật dòng quen thuộc. Với mục đích trên người ta đã đề xuất xây dựng một bộ tạo dãy ngẫu nhiên dựa trên cơ sở loại bài toán phân tích số trong hệ mật RSA như sau: p