Các thuật toán phân tích thừa số

- Phân tích modulus của rabin với một chơng trình con giải mã cho trớc..
- wr (mod n), trong đó w là một trong các căn bậc hai không tầm thờng của 1 modulo n.
- Bởi vậy, việc tính UCLN(x 1 +r,n)(hoặc UCLN(x 1 -r, n)) phải dẫn tới hoặc p hoặc q, và nh vậy phép phân tích n đợc hoàn thành..
- Ta sẽ tính xác suất thành công của thuật toán này trên tất cả (n-1) phép chọn ngẫu nhiên r.
- Điều đó cho ta thấy rằng quan hệ ~ là một quan hệ tơng đơng.
- Trong thuật toán đợc trình bày ở hình 4.14, hai giá trị r bất kỳ trong cùng một lớp tơng đơng sẽ dẫn tới cùng một giá trị y.
- y thì thuật toán không thành công.
- trong khi nếu r=± wy thì thuật toán sẽ thành công.
- Ta kết luận rằng xác suất thành công của thuật toán là 1/2..
- Thuật toán ở hình 4.14, phần dùng để chứng minh sự an toàn.
- Trong phơng pháp tấn công bản mã chọn lọc, chơng trình con A đợc thay bằng thuật toán giải mã của Bob..
- Các thuật toán phân tích thừa số..
- Đã có một khối lợng khổng lồ các tìa liệu về các thuật toán phân tích thừa số và việc nghiên cứu kỹ lỡng sẽ đòi hỏi phải có một cuốn sách dày hơn quyển sách này.
- lợc về các thuật toán phân tichs thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế.
- Ba thuật toán hiệu quả.
- nhất trên các số thật lớn là sàng bậc hai, thuật toán đờng cong elliptic và sàng trờng số.
- Các thuật toán nổi tiếng khác (những thuật toán toán có trớc) bao gồm phơng pháp ρ và thuật toán p-1 của Pollard, thuật toán p+1 của Williams, thuật toán liên phân số và dĩ nhiên cả những phép chia thử..
- Trong toàn bộ phần này, xchúng ta cỏìng số nguyên n cần phân tích ra thừa số là một số lẻ.
- 10 12 thì đây là một.
- phơng pháp phân tích thừa số hợp lý một cách hoàn hảo, tuy nhiên với n lớn hơn nói chung ta phải dùng các kỹ thuật tinh tế hơn..
- Phơng pháp p-1.
- Thuật toán p-1 của Pollar (đa ra vào năm 1947) là một thí dụ về một thuật toán đơn giản đơn khi đợc áp dụng với các số nguyên lớn.
- Thuật toán này (trình bày trên hình 4.15) có hai.
- đầu vào: số nguyên lẻ n cần đợc phân tích và một cận B.
- Có thể mô tả thuật toán nh sau:.
- Thuật toán phân tích thừa số p-1..
- d là một thừa số của n else.
- Trong trờng hợp này, phép phân tích sẽ thành công do 135978 chỉ gồm các thừa số nguyên tố nhỏ:.
- Trong thuật toán có (B-1) luỹ thừa theo modulo, mỗi luỹ cần nhiều nhất là 2log 2 B phép nhân modulo dùng thuật toán bình phơng và nhân.
- Việc tính ớc chung lớn nhất có thể thực hiện trong thời gian O((log n) 3 ) bằng thuật toán Euclide.
- Bởi vậy, độ phức tạp của thuật toán là O(B logB (log n) 2 +(log n) 3.
- thuật toán thực sự là thuật toán thời gian đa thức, tuy nhiên với phép chọn B nh vậy, xác suất thành công sẽ rất nhỏ.
- thì thuật toán sẽ thành công nhng nó sẽ không thực hiện nhanh hơn phép chia thử..
- Nh vậy, điểm bất lợi của thuật toán này là nó yêu cầu n phải có ớc nguyên tố p sao cho (p-1) chỉ các thừa số nguyên tố bé.
- modulus n= pq hạn chế đợc việc phân tích theo phơng pháp này.
- Trớc tiên tìm một số nguyên tố lớn p 1 sao cho p= 2p 1 +1 cũng là một số nguyên tố và một số nguyên tố lớn q 1 sao cho q= 2q 1 +1 cũng là một số nguyên tố (nhờ dùng một trong các thuật toán kiểm tra tính nguyên tố Monte-Carlo nêu trong phần 4.5).
- Khi đó modulo của RSA n= pq sẽ chống đợc cách phân tích theo phơng pháp p-1..
- Thuật toán đờng cong elliptic mạnh hơn (đợc Lenstra xây dựng vào những năm 1980) trên thực tế là sự tổng quát hoá của phơng pháp p-1.
- Thuật toán Dixon và sàng bậc hai.
- Thuật toán Dixon đợc xây dựng trên ý tởng đơn giản mà ta đã thấy trong hệ mật Rabin.
- Phơng pháp này sử dụng cơ sở nhân tử là một tập b chứa các số nguyên tố bé.
- Điều này dẫn đến một đồng d thức dạng mong muốn x 2 ≡ y 2 (mod n) mà ta hy vọng sẽ đa đến việc phân tích n..
- Giả sử b .
- UCLN Ta thấy 115759 là một thừa số của n..
- Giả sử B = {p 1.
- .p B }là một cơ sở nhân tử.
- Đây là lý do cho thấy đồng d thức (thiết lập theo tích) sẽ phân tích thành công đợc n..
- B+1 là do không có gì bảo đảm để một đồng d thức cho trớc bất kỳ sẽ tạo đợc phân tích n.
- Khoảng 50% thuật toán cho ra x.
- Hy vọng là ít nhất một trong các đồng d thức kết quả sẽ dẫn đến việc phân tích n..
- Vấn đề còn lại là phải làm thế nào để nhận đợc các số nguyên x j mà các giá trị x j 2 mod n có thể phân tích hoàn toàn trên cơ sở b.
- ở đây) dùng để xác định các x j phân tích đợc trên b..
- ở đây dĩ nhiên là một sự thoả hiệp: nếu B.
- B | là một số lớn thì thích hợp hơn cả là nên phân tích số nguyên x j.
- Sàng trờng số là thuật toán phân tích mới hơn (từ cuối những năm 80) Thuật toán này cũng phân tích n bằng cách.
- 4.8.3.Các thuật toán phân tích trên thực tế..
- Thời gian chạy tiệm cận của các thuật toán sàng bậc hai,.
- thời gian chạy tiệm cận của các thuật toán đờng cong elliptic và sàng bậc hai cơ bản nh nhau.
- đã đợc phân tích bằng phơng pháp đờng cong elliptic là tham số Fermat đợc Brent thực hiện năm 1988).
- Để phân tích các modulo RSA (trong đó n=pq, p và q là các số nguyên tố có cùng kích thớc), sàng bậc hai là một thuật toán thành công nhất hiện nay.
- Sau đây là một số kết quả.
- Vào năm 1983, thuật toán sàng bậc hai đã phân tích thành công một số có 69 chữ số, số này là một thừa số của 2 251 -1 (do Davis, Holdredye và Simmons thực hiện).
- trình này tiếp tục trong những năm 80 và đến năm 1989 đã có thể phân tích đợc các số có tới 106 chữ số theo phơng pháp này( do Lenstra và Manasse thực hiện) nhờ phân bố các phép tính cho hàng trăm trạm làm việc tách biệt (ngời ta gọi phơng pháp này là “phân tích thừa số bằng th điện tử”)..
- đã phân tích đợc một số 129 chữ số (đợc gọi là RSA-129) nhờ sử dụng sàng bậc hai (các số RSA-100, RSA-110,....,RSA-500 là một danh sách các modulo RSA đợc công bố trên internet nh là sự thách đố cho các thuật toán phân tích.
- RSA-d là một số d chữ số, số này là tích của hai số nguyên tố có kích thớc xấp xỉ nhau).
- Việc phân tích số RSA-129 cần hàng trăm tính toán với máy tính 5000 MIPS (triệu lệnh/s) đợc thực hiện bởi 600 nhà nghiên cứu trên toàn thế giới..
- Sàng trờng số là một thuật toán mới nhất trong ba thuật toán toán.
- Nó có vẻ có tiềm năng lớn do thời gian chạy tiệm cận của nó nhanh hơpn cả hai thuật toán trên.
- Thuật toán này hiện vẫn còn trong thời kì nghiên cứu, tuy nhiên ngời ta đã dự đoán là sàng trờng số phải chứng tỏ là nhanh hơn với các số có trên 125-130 chữ số.
- dùng sàng trờng số để phân tích thành ba số nguyên tố có 7, 49 và 99 chữ số..
- là một bài báo tổng quát và mặt mã khoá công khai của Diffie..
- Các cận tối nhất hiện thời về xác suất sai của thuật toán Miller- Rabin có thể tìm thấy trong [DLP 93]..
- Phép phân tích n với số mũ giải mã cho trớc đợc nêu trong [DE 84]: các kết quả về thông tin riêng bị lộ bởi RSA lấy từ [GMT 82]..
- Nh đã nói trên, đã có rất nguồn tài liệu về các thuật toán phân tích.
- Pomerance [Po 90]là tổng quát về phếp phân tích.
- Lenstra và Lenstra [LL 90] là một báo cáo hay là về các thuật toán lý thuyết nói chung.
- Bressoud [Br 89] là một giáo.
- trình sơ cấp về phép phân tích thừa số và phép kiểm tra tính nguyên tố.
- Còn sách của Lenstra và Lenstra [LL 93] là một chuyên thảo tốt về sàng trờng số..
- Hãy dùng thuật toán Euclide mỡ rộng để tính các phần tử nghịch đảo rau:.
- gợi ý: trớc tiên hãy dùng thuật toán Euclide mỡ rông rồi áp dụng.
- a) 97 là một số nguyen tố.
- Hãy chứng minh rằng x ≠ 0 là một căn nguyên thuỷ theo modulo 97 khi và chỉ khi.
- c) Giả sử p là một số nguyên tố và p-1 có phần tích ra các mũ nguyên tố sau.
- ở đây p i là các số nguyên tố khác nhau.
- Hãy chứng minh tỏ rằng x ≠ 0 là một căn nguyên thuỷ theo modulo p khi và chỉ khi.
- Trớc hết hỹ phân tích n (điều này khá dể vì n quá nhỏ).
- Hãy dùng thuật toán bình phơng và nhân để lấy luỹ thừa theo modulo n..
- Giả sử Bob có một hệ mật RSA có modulo n lớn để việc phân tích n không thể thực hiên trong một thời gian chấp nhận đợc.
- b) Minh hoạ cách tấn công qua việc giải mã bản mã sau (bản này đã đợc mã bằng hệ mật RSA với n = 18721 và b = 25) mà không cần phải phân tích n:.
- 4.9 Đây lại là một ví dụ khác về sự trục trặc thủ tục xoay quanh hệ mật RSA.
- Hãy mô tả cách tnhs x của Oscar khi anh ta đã biết y 1 , y 2 , y 3 , mà không cần phải phân tích bất cứ n i nào..
- Giả sử A là một thuật toán tất định có đầu vào là một.
- Giả sử rằng có ε ì n bản mã mà có thể giải, hay chỉ rõ cách dùng A làm một chơng con trong thuật toán giải mã Las Vegas có xác suất không thành công là ε.
- ơng trình không thực hiện việc phân tích thừa số trừ việc phân ra các luỹ thừa bậc hai.
- b) Nếu n là một số hợp số lẻ, chứng minh rằng.
- Giả sử ta có thuật toán Las-Vegas với xác suất sai ε.
- c) Giả sử δ là một số dơng thực nhỏ hơn 1.
- áp dụng dụng thuật toán sác suất để phân tích n theo thông tin đợc biết này.
- Hãy phân tích ra thừa số các số 262063 và 9420457 bằng phơng pháp p-1

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt