Luận văn Thạc sĩ Toán học: Một số thuật toán phân tích số nguyên hiện đại và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:34

Thêm vào BST

Báo xấu

21
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn "Một số thuật toán phân tích số nguyên hiện đại và ứng dụng" có mục đích tìm hiểu sơ lược về cơ sở toán học của Lý thuyết mật mã, đồng thời phân tích sâu hơn các thuật toán phân tích số tự nhiên để làm cơ sở toán học cho ứng dụng. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một số thuật toán phân tích số nguyên hiện đại và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ BÌNH MỘT SỐ THUẬT TOÁN PHÂN TÍCH SỐ NGUYÊN HIỆN ĐẠI VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ BÌNH MỘT SỐ THUẬT TOÁN PHÂN TÍCH SỐ NGUYÊN HIỆN ĐẠI VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. HÀ HUY KHOÁI THÁI NGUYÊN - 2017
3 Mục lục Danh sách kí hiệu 5 MỞ ĐẦU 6 Chương 1. Thám mã và một số thuật toán phân tích số nguyên cổ điển 8 1.1 Thám mã và phân tích số nguyên . . . . . . . . . . . . . . . . . . 8 1.2 Phân tích Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Phân tích Pollard p − 1 . . . . . . . . . . . . . . . . . . . . . . . 17 Chương 2. Một số thuật toán hiện đại phân tích số nguyên 20 2.1 Sự kiểm tra ước . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Thuật toán phân tích ρ của Pollard . . . . . . . . . . . . . . . . . 21 2.3 Phương pháp phân tích Brent . . . . . . . . . . . . . . . . . . . . 24 2.4 Phương pháp phân tích dùng đường cong elliptic . . . . . . . . . . 26 2.5 Phương pháp phân tích bằng sàng trường số . . . . . . . . . . . . 28 2.6 Khả năng phân tích số bằng các “chip” chuyên dụng . . . . . . . . 30 KẾT LUẬN VÀ KIẾN NGHỊ 32 TÀI LIỆU THAM KHẢO 33
4 Lời cảm ơn Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành với sự hướng dẫn của GS.TSKH. Hà Huy Khoái (Trường Đại học Thăng Long, Hà Nội). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình đã dành nhiều công sức hướng dẫn để tác giả hoàn thành luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán-Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu. Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể Lớp B, cao học Toán khóa 9 (2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình học tập. Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Nguyễn Đức Cảnh, Huyện Kiến Thụy, Thành phố Hải Phòng đã tạo điều kiện cho tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình. Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến bố mẹ và đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả hoàn thành tốt luận văn này.
5 Danh sách kí hiệu Z vành các số nguyên Q trường các số hữu tỷ Fp trường có p phần tử K[X] vành đa thức với hệ số trên trường K dxe trần của số x deg P(X) bậc của đa thức P(X) mod p modulo p gcd(P(X), Q(X)) ước chung lớn nhất của P(X) và Q(X) exp(·) hàm số mũ gcd(a, b) ước chung lớn nhất của a và b a|b a là ước của b bNc sàn của số N F[α] trường mở rộng của trường F
6 Mở đầu Trước những năm 70 của thế kỷ XX, Số học thường được xem là một trong những ngành toán học thuần tuý, chỉ có ý nghĩa lý thuyết. Đối tượng nghiên cứu của Số học là các quy luật trong tập hợp số nguyên; các giả thuyết lớn tồn tại trong Số học thường là các giả thuyết về số nguyên tố. Thậm chí, có những nhà toán học cho rằng, vẻ đẹp của số học có được nhờ sự xa rời thực tiễn của nó. Ngày nay, những ứng dụng lớn lao và bất ngờ của Số học vào mật mã cho ta thấy rằng quan niệm trên đã hoàn toàn thay đổi. Vẻ đẹp của Số học không chỉ thể hiện trong ý nghĩa “thuần tuý” của nó, mà cả trong những ứng dụng bất ngờ vào thực tiễn. Cách đây khoảng 30 năm, khó có thể hình dung được rằng, một số kết quả lý thuyết trong Số học lại làm nên một cuộc cách mạng trong bảo mật thông tin trong Lý thuyết mật mã. Cơ sở của những ứng dụng đó chính là Số học thuật toán, lĩnh vực nghiên cứu các thuật toán trong Số học. Trong lĩnh vực Lý thuyết mật mã, mật mã khóa công khai là một dạng mật mã cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật). Cơ sở toán học của vấn đề này là việc phân tích các số tự nhiên và một số vấn đề liên
7 quan đến chúng. Luận văn này có mục đích tìm hiểu sơ lược về cơ sở toán học của Lý thuyết mật mã, đồng thời phân tích sâu hơn các thuật toán phân tích số tự nhiên để làm cơ sở toán học cho ứng dụng. Ngoài các phần Mở đầu, Kết luận, Tài liệu tham khảo, nội dung của luận văn được trình bày trong hai chương: • Chương 1. Thám mã và một số thuật toán cổ điển phân tích số nguyên. Trong chương này chúng tôi trình bày các kiến thức cơ sở về thám mã và sau đó là một số thuật toán cổ điển phân tích số nguyên, làm cơ sở so sánh và phát triển cho chương tiếp theo. • Chương 2. Một số thuật toán hiện đại phân tích số nguyên. Đây là nội dung chính của luận văn. Chúng tôi sẽ trình bày một số thuật toán hiện đại phân tích số nguyên như thuật toán phân tích Pollard, phân tích dùng đường cong elliptic hoặc sàng trường số. Thái Nguyên, ngày 10 tháng 7 năm 2017 Tác giả Nguyễn Thị Bình
8 Chương 1 Thám mã và một số thuật toán cổ điển phân tích số nguyên 1.1 Thám mã và phân tích số nguyên Phần này em sẽ trình bày về thám mã. Thám mã là một vấn đề phức tạp nên trong luận văn này em xin phép chỉ đề cập những vấn đề đơn giản nhất. Phần đầu trong trình bày chúng tôi dựa vào [2]. Thám mã (hay phân tích mã - cryptanalysis) là việc nghiên cứu các phương pháp “phá vỡ” bức màn ngụy trang văn bản (do việc mã hóa tạo nên) để có thể hiểu được nội dung văn bản. Hiện nay, trên quan điểm thám mã, người ta phân các hệ mã thành ba loại: • Loại đã bị phá; • Loại chưa được nghiên cứu phân tích (vì còn mới, hoặc vì chưa được dùng rộng rãi);
9 • Loại đã được nghiên cứu nhưng chưa bị phá (RSA, IDEA, các hệ mã sử dụng logarit rời rạc, đường cong elliptic, . . . ). Có ba cách thông dụng trong việc chuyển hóa văn bản mã thành văn bản gốc: • Ăn trộm, hối lộ, hoặc mua (với giá rất cao) để có được chìa khóa; • Khai thác tính cẩu thả hoặc lỏng lẻo của người dùng khóa (ví dụ : có người hay dùng tên người thân để làm mật khẩu hoặc chìa khóa); • Phân tích mã (tức là thám mã). Bây giờ, ta sẽ thảo luận về một số phương pháp thám mã. Thực tế, thám mã sẽ phức tạp hơn nếu người ta không biết hệ mật mã đã được sử dụng. chúng ta giả sử người thám mã đã biết rõ hệ mật mã được sử dụng khi tiến hành phân tích mã. Mục đích là thiết kế được một hệ mật mã an toàn bảo mật. Dưới đây ta sẽ liệt kê các loại tấn công vào hệ mật mã. Mức độ tấn công sẽ phụ thuộc vào hiểu biết của người thám mã đối với hệ mật mã được sử dụng : • Tấn công chỉ biết bản mã (ciphertext-only): người thám mã chỉ có bản tin mã hóa. • Tấn công biết bản tin rõ (known plaintext): người thám mã có bản tin rõ và bản mã.
10 • Tấn công chọn bản tin rõ (chosen plaintext): người thám mã tạm thời có quyền truy xuất tới bộ mã hóa, do đó người thám mã có khả năng chọn bản tin rõ và xây dựng bản mã tương ứng. • Tấn công chọn bản mã (chosen ciphertext): người thám mã tạm thời có quyền truy xuất tới bộ giải mã, do đó anh ta có khả năng chọn bản mã và xây dựng lại bản tin rõ tương ứng. Bây giờ ta sẽ liệt kê các phương pháp thám mã 1. Thám mã tích cực là việc thám mã sau đó tìm cách làm sai lạc các dữ liệu truyền, nhận hoặc các dữ liệu lưu trữ phục vụ mục đích của người thám mã. 2. Thám mã thụ động là việc thám mã để có được thông tin về bản tin rõ phục vụ mục đích của người thám mã. 3. Thám mã affine. Trong mật mã affine, đầu tiên bảng chữ cái của thông điệp cần mã hóa có kích thước m sẽ được chuyển thành các con số tự nhiên từ 0, . . . , m − 1. Sau đó dùng một hàm modulo để mã hóa và chuyển thành bản mã. Hàm mã hóa cho một ký tự như sau: e(x) = (ax + b) (mod m) với m là kích thước của bảng chữ cái, a và b là khóa mã. Giá trị a được chọn sao cho a và m là nguyên tố cùng nhau. Giả sử Trudy đã lấy được bản mã sau đây:
11 FMXVEDKAPHFERBNDKRXRSREFMORUD SDKDVSHVUFEDKAPRKDLYEVLRHHRH Trudy thống kê tần suất xuất hiện của 26 chữ cái như trong bảng sau: A 2 N 1 B 1 O 1 C 0 P 3 D 6 Q 0 E 5 R 8 F 4 S 3 G 0 T 0 H 5 U 2 I 0 V 4 J 0 W 0 K 5 X 2 L 2 Y 1 M 2 Z 0 Các chữ cái trong bản mã xuất hiện tổng là 57 lần, nhưng phương pháp này tỏ ra hiệu quả để thám mã affine. Ta thấy tần suất xuất hiện các chữ cái theo thứ tự là: R là 8, D là 6, E, H, K là 5 và F, S, V là 4. Vì vậy dự đoán đầu tiên của ta có thể là R là mã của e, D là mã của t. Theo đó, eK (4) = 17 và eK (19) = 3. Mà ta có eK (x) = ax + b. Để tìm
12 K = (a, b) ta giải hệ phương trình:   4a + b ≡ 17 (mod 26)   19a + b ≡ 3 (mod 26) .  Giải hệ phương trình này ta được a = 6, b = 19. Đây không phải là khóa vì gcd(a, 26) = 2 > 1. Ta lại tiếp tục phỏng đoán rằng R là mã của e, E là mã của t. Ta nhận được a = 13, chưa thỏa mãn. Tiếp tục với H, ta có a = 8. Cuối cùng, với K ta tìm được K = (3, 5). Sử dụng khóa mã này ta có được bản tin rõ là algorithmsrequiregeneraldefinitionsofarithmeticprocesses (algorithms require general definitions of arithmetic processes) 1.2 Phân tích Fermat Trước khi thảo luận về các thuật toán phân tích số nguyên, ta sẽ giới thiệu một số quy ước về thuật ngữ và khái niệm cơ sở. Ta sẽ bắt đầu với các thuật ngữ của sẽ được dùng trong trình bày: • Kí hiệu O lớn (big O notation). Hàm f (x) là O(g(x)) khi x → ∞ nếu và chỉ nếu có các số dương c và k sao cho với mọi x > k, ta có 0 < f (n) ≤ cg(n). Ta xét ví dụ f (x) = 2x2 + x + 1 là O(x2 ) khi x → ∞ với c = 2, k = 0.
13 Kí hiệu O lớn được áp dụng trong thời gian chạy (running time) hoặc trong yêu cầu lưu trữ (storage requirements) của một thuật toán. Trong trình bày, để ngắn gọn ta cũng có thể chỉ cần viết O(g(x)), và được giả thiết là ta xét với x → ∞. Khi ta xét hàm nhiều biến, thì biến mà dần tới vô hạn sẽ được chỉ ra. Như một phần trong định nghĩa của O(g(x)), tất cả các sự kiện xảy ra sẽ được xét với x → ∞. • Phân tích tầm thường (trivial factor). Phân tích tầm thường là phân tích mà nhân tử là s = 1 hoặc s = N. • Phân tích không tầm thường (nontrivial factor). Phân tích không tầm thường là phân tích một số nguyên mà trong phép phân tích có nhân tử s thỏa mãn 1 < s < N. • Số nguyên tố (prime number). Một số nguyên dương lớn hơn 1 được gọi là nguyên tố nếu nó chỉ chia hết cho 1 và chính nó. Với các khái niệm trên, ta có Định lý cơ bản của số học đó là : Mọi số tự nhiên lớn hơn 1 có thể viết một cách duy nhất (không kể sự sai khác về thứ tự các thừa số) thành tích các thừa số nguyên tố. Luận văn này có mục đích trình bày về thuật toán phân tích số nguyên. Ta hãy xem xét một lý do dẫn đến việc làm này. Định lý cơ bản của số học kéo theo nhận xét rằng mọi số nguyên đều có thể được phân tích thành tích .
14 Xét số N = 25195908475657893494027183240048398571429282126204 03202777713783604366202070759555626401852588078440 69182906412495150821892985591491761845028084891200 72844992687392807287776735971418347270261896375014 97182469116507761337985909570009733045974880842840 17974291006424586918171951187461215151726546322822 16869987549182422433637259085141865462043576798423 38718477444792073993423658482382428119816381501067 48104516603773060562016196762561338441436038339044 14952634432190114657544454178424020924616515723350 77870774981712577246796292638635637328991215483143 81678998850404453640235273819513786365643912120103 97122822120720357. Số nguyên này được biết như là RSA-2048. Vào tháng 3/1991, Phòng thí nghiệm RSA (RSA Laboratories) đã thông báo giải thưởng USD 200.000 cho sự phân tích thành công số nguyên này. Tính đến tháng 11/2004, số này vẫn chưa được phân tích. Nếu biết trước hai số nguyên tố lớn thì ta sẽ có một thuật toán nhanh để nhân chúng với nhau. Tuy nhiên, trong tình huống ngược lại, nếu cho tích của hai số nguyên tố, rất khó phân tích ngược lại để tìm ra hai số như vậy. Thuật toán nhanh nhất được biết đến hiện nay có tên gọi Sàng trường
15 số tổng quát (General Number Field Sieve (GNFS)), mà nếu lấy trung bình thì sẽ cần " #! 1/3 64 S = O exp n (log n)2/3 9 bước để phân tích một số nguyên với n chữ số thập phân. Thời gian chạy thuật toán bị chặn dưới bởi hàm đa thức, và bị chặn trên bởi hàm mũ theo n. Chính sự khó khăn của việc phân tích các số nguyên lớn sẽ là cơ sở cho một số thuật toán mật mã hiện đại. Bây giờ ta sẽ trình bày về phân tích Fermat. Thuật toán này được phát minh bởi nhà toán học Pierre de Fermat trong những năm 1600 (xem Weis- stein E.W. [5]). Để làm phân tích Fermat, ta viết một hợp số N thành hiệu của hai bình phương, N = x2 − y2 . Hiệu này của các bình phương dẫn đến sự phân tích của N N = (x + y)(x − y). Giả sử rằng s và t là các nhân tử không tầm thường lẻ của N thỏa mãn st = N và s ≤ t. Ta tìm x và y sao cho s = (x − y) và t = (x + y). Giải phương trình này, ta tìm x = (s + t)/2 và y = (t − s)/2. Ở đây, x và y là các số tự nhiên, do hiệu số giữa hai số lẻ là chẵn, và một số chẵn là bội của 2. Do s > 1 và t ≥ s, ta tìm x ≥ 1 và y ≥ 0. Trong trường hợp riêng, các số x, y p √ thỏa mãn s = (x − y) và t = (x + y), vì vậy x = N + y2 , và do đó x ≥ N. Cũng vậy, x = (s + t)/2 ≤ 2t/2 ≤ N. √ Đối với thuật toán này, ta chọn x1 = N, và xi+1 = xi + 1. Với mỗi i, ta
16 q kiểm tra khi nào thì yi = xi2 − N là một số nguyên và khi nào thì (xi + yi ), (xi − yi ) là các nhân tử không tầm thường N. Nếu cả hai điều kiện đó xảy ra, ta có được một phân tích không tầm thường. Nếu không, ta tiếp tục với i tiếp theo. Dưới đây là thuật toán. function fermatFactor(N) for x from ceil(sqrt(N)) to N ySquared := x * x - N if isSquare(ySquared) then y := sqrt(ySquared) s := (x - y) t := (x + y) if s 1 and s N then return s, t end if end if end for end function trong đó hàm isSquare(z) đúng nếu z là một số chính phương và sai nếu ngược lại.
17 1.3 Phân tích Pollard p − 1 Phương pháp phân tích Pollard p − 1 được giới thiệu bởi Pollard J.M. năm 1974 (xem Weisstein E.W. [8]). Nó dựa trên Định lí Fermat nhỏ được phát biểu như sau: Định lí 1.3.1 (Định lí Fermat nhỏ). Nếu p là một số nguyên tố, a là một số tự nhiên và p 6 | a thì a p−1 ≡ 1 (mod p). Giả sử chúng ta có một số nguyên dương k ≥ 1 và một số nguyên tố p > 2 sao cho (p − 1) | k!. Bây giờ ta áp dụng Định lí Fermat nhỏ với a = 2, 2 p−1 ≡ 1 (mod p). Nhưng do (p − 1) | k! nên ta có thể viết k! = (p − 1)q với một số nguyên dương q nào đó. Ta có 2k! ≡ (2 p−1 )q ≡ 1q ≡ 1 (mod p). Do vậy p | 2k! − 1. Nếu N là một số nguyên có nhân tử nguyên tố không tầm thường p, thì p là ước của 2k! − 1 + Nt với mọi số nguyên t. Ta có thể tính xk ≡ 2k! − 1 (mod N) với k = 1, 2, 3, . . . , và với mỗi xk kiểm tra xem có tồn tại một số nguyên rk = gcd(xk , N) mà là ước của cả xk và N. Nếu (p − 1) | k! thì p | xk và do đó rk là một nhân tử không tầm thường của N. Nếu rk không phải là một nhân tử không tầm thường của N, thì nó là một nhân tử tầm thường của N, tức là rk = 1 hoặc rk = N. Thuật toán như sau: • Tính rk = gcd(2k! − 1, N) với k = 1, 2, 3 . . .. Nếu rk ∈ / {1, N} thì rk là một nhân tử không tầm thường và ta hoàn thành công việc cần làm.
18 • Ta có thể viết 2k! ≡ (2(k−1)! )k (mod n), sao cho nếu 2(k−1)! là đã biết theo (mod n), thì 2k! có thể tính được chỉ với một phép toán lũy thừa modulo một số. Ta trình bày thuật toán. function pollard_p1(N) # Initial value 2^(k!) for k = 0. two_k_fact := 1 for k from 1 to infinity # Calculate 2^(k!) (mod N) from 2^((k-1)!). two_k_fact := modPow(two_k_fact, k, N) rk := gcd(two_k_fact - 1, N) if rk 1 and rk N then return rk, N/rk end if end for end function Trong đó modPow(a, b, m) lại là số nguyên nhỏ nhất không âm sao cho ab ≡ y (mod m). Hàm này được gọi là “số mũ modular”. Ta trình bày thuật toán hiệu quả đối với số mũ modular. Ta viết b trong hệ nhị phân dưới dạng b = b0 20 + b1 21 + . . . + bn−1 2n−1
19 và thấy rằng ab có thể viết lại dưới dạng 0 b0 1 b1 n−1 bn−1 b0 20 b1 21 bn−1 2n−1 b a =a a ...2 = a2 a2 . . . a2 . k bk k Chú ý với mỗi k, a2 là 1 nếu bk = 0 và a2 nếu ngược lại. Do đó ta có n−1 k b a = ∏ a2 . k=0, bk 6=0 k+1 k k 2 Chú ý rằng a2 = a2·2 = a2 . Bằng phương pháp bình phương liên tiếp, ta có thể thiết kế một thuật toán tìm kiếm số tự nhiên nhỏ nhất sao cho ab ≡ y (mod m). function modPow(a, b, m): ans := 1 a := a % m for k from 0 to infinity if 2^k>b then return ans end if if (bit k of b is nonzero) then ans := (ans * a) % m a := (a * a) % m end for end function
20 Chương 2 Một số thuật toán hiện đại phân tích số nguyên Trong Chương 2 này, chúng tôi sẽ thảo luận về một số thuật toán hiện đại phân tích số nguyên. 2.1 Sự kiểm tra ước Sự kiểm tra ước là thuật toán đơn giản nhất để phân tích số nguyên. Giả sử rằng s và t là các nhân tử không tầm thường của N sao cho st = N và s ≤ t. Để thực hiện thuật toán kiểm tra ước, một cách đơn giản là kiểm tra √ xem s | N với s = 2, . . . , N . Khi một nhân tử như vậy s được tìm thấy thì t = N/s cũng là một nhân tử, và một phép phân tích đã được tìm thấy cho N. Ràng buộc trên s ≤ bNc được cung cấp bởi định lí sau đây: Định lí 2.1.1. Nếu N có nhân tử không tầm thường s, t với st = N và s ≤ t, √ thì s ≤ N. √ Chứng minh. Do s là nhân tử của N nên ta có s > N. Khi đó t ≥ s > N,