Tài liệu Số nguyên tố và ứng dụng trong phương pháp chứng minh không tiết lộ thông tin

THÁI NGUYÊN - 2016 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG _____________œ ______________ TẠ THỊ HẰNG SỐ NGUYÊN TỐ VÀ ỨNG DỤNG TRONG PHƯƠNG PHÁP CHỨNG MINH KHÔNG TIẾT LỘ THÔNG TIN Chuyên ngành: Khoa học máy tính Mã số: 60 48 0101 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Người hướng dẫn khoa học: TS. Nguyễn Thị Hồng Minh THÁI NGUYÊN - 2016 i Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Lời cam kết Tài liệu được sử dụng trong luận văn được thu thập từ các nguồn kiến thức hợp pháp, có trích dẫn nguồn tài liệu tham khảo. Chương tri ̀nh sử dụng mã nguồn mở, có xuất xứ. Dưới sự giúp đỡ nhiệt tình và chỉ bảo chi tiết của giáo viên hướng dẫn, tôi đã hoàn thành luận văn của mình. Tôi xin cam kết luận văn này là của bản thân tôi làm và nghiên cứu, không hề trùng hay sao chép của bất kỳ ai. ii Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Lời cảm ơn Trước hết tôi xin gửi lời cảm ơn đến TS. Nguyễn Thị Hồng Minh, Phó Chủ nhiệm khoa Sau đại học, Đại học Quốc gia Hà Nội người đã hướng dẫn và giúp đỡ tôi rất nhiều trong suốt quá trình tìm hiểu nghiên cứu và hoàn thành khóa luận này. Sự hướng dẫn nhiệt tình của Tiến sĩ đã giúp tôi quyết tâm hoàn thành luận văn, qua đó bản thân tôi đã mở rộng hiểu biết về vấn đề bảo mật thông tin và các ứng dụng trong thự tế của nó. Tôi cũng xin chân thành cảm ơn quý Thầy, Cô trong trường Đại học Công nghệ Thông tin & Truyền thông - Đại học Thái Nguyên; quý Thầy, Cô trong Viện Công nghệ thông tin đã tận tình truyền đạt kiến thức cho chúng tôi trong 2 năm học tập và nghiên cứu. Với vốn tiếp thu trong khóa học không chỉ là nền tảng cho quá trình nghiên cứu luận văn này mà còn là hành trang quý báu, nền tảng vững chắc để tôi tiếp tục nghiên cứu, hoạt động trong lĩnh vực công nghệ thông tin. Cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã giúp đỡ và động viên tôi trong công việc và học tập cũng như trong quá trình thực hiện luận văn này. Xin chúc mọi người luôn mạnh khoẻ, đạt được nhiều thành tích cao trong công tác, học tập và nghiên cứu khoa học! Trân trọng cảm ơn! Thái Nguyên, ngày 12 tháng 5 năm 2016 Tác giả Tạ Thị Hằng iii Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Danh mục viết tắt Viết tắt Giải thích Đpcm Điều phải chứng minh CMKTTTT Chứng minh không tiết lộ thông tin UCLL Ước chung lớn nhât TTĐT Thanh toán điện tử CT Cử Tri KP Kiểm Phiếu TMĐT Thương mại điện tử GMR Goldwasser, Micali và Rackoff TT Thông tin BKP Ban kiểm phiếu CSDL Cơ sở dữ liệu BDK Bàn Đăng Ký BKP Ban kiểm phiếu iv Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Danh mục các hình và bảng Hình 1.1: Sơ đồ quy trình bỏ lá phiếu điện tử……………………………. 35 Hình 1.2: Sơ đồ giai đoạn đăng ký bỏ phiếu……………………………… 36 Hình 1.3: Sơ đồ giai đoạn bỏ phiếu………………………………………. 38 v Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Lời nói đầu Ngày nay, công nghệ thông tin đang phát triển mạnh mẽ, Internet đã trở thành một phần không thể thiếu trong cuộc sống hàng ngày thì các hoạt động trao đổi thông tin, mua bán,…trên mạng Internet diễn ra thường xuyên và ngày phổ biến hơn. Chính vì vậy mà việc bảo mật, đảm bảo an toàn thông tin đang là nhu cầu cấp thiết. Trước các nhu cầu cấp thiết đó, lý thuyết về mật mã thông tin đã ra đời nhằm đảm bảo tính an toàn dữ liệu tại nơi lưu trữ cũng như khi dữ liệu đang được truyền trên mạng. Mật mã học là một trong những vấn đề quan trọng trong lĩnh vực bảo mật và an toàn thông tin.Trên thế giới mật mã học được ra đời từ thời La Mã cổ đại và ngày càng được nghiên cứu, phát triển đạt những thành tựu to lớn. Trong mật mã học thì vấn đề bảo mật luôn đi đôi với vấn đề xác thực thông tin, đặc biệt trong hệ thống mã hóa khóa công khai vấn đề xác thực là vô cùng quan trọng, để giải quyết vấn đề trên người ta đưa ra một cách giải quyết hiệu quả, đó là phương pháp chứng minh không tiết lộ thông tin. Với sự bùng nổ của mạng Internet hiên nay, mạng máy tính đang ngày càng đóng vai trò thiết yếu trong lĩnh vực hoạt động xã hội, và khi nó trở thành phương tiện điều hành các hệ thống thì nhu cầu bảo mật thông tin được đặt lên hàng đầu. Việc sử dụng phương pháp chứng minh không tiết lộ thông tin là một giải pháp hữu hiệu, ngày càng được ứng dụng nhiều trong thực tế, không chỉ giới hạn trong nghành công nghệ thông tin, mật mã học mà còn được áp dụng nhiều trong lĩnh vực khác như ngân hàng, viễn thông…”Chứng minh không tiết lộ thông tin (zero Knowledge Proofs” là phương pháp chứng minh không có nghĩa là “ không để lộ thông tin” mà là “để lộ thông tin ở mức thấp nhất” về sự vật, sự việc cần chứng minh. Với việc “không để lộ” người xác minh sẽ không có nhiều hiểu biết về sự vật, sự việc, họ chỉ thu được chút ít thông tin (coi như là không) về tính chất của nó nhưng vẫn đảm bảo được nhận thức về tính đúng của đối tượng cần xác minh. vi Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Số nguyên tố, một phát minh kì diệu của con người, được quan tâm không chỉ bởi cộng đồng toán học mà cả cộng đồng tin học do tính chất đặc biệt của nó và cả những ứng dụng thực tế hiệu quả. Ứng dụng chính của số nguyên tố là trong lĩnh vực mã hóa (cryptography), trong đó chúng ta cần tạo ra những số nguyên tố với hàng trăm chữ số. Kiểm tra một số có phải số nguyên tố hay không, làm sao sinh được các số nguyên tố càng lớn càng tốt là những bài toán khá quan trọng trong khoa học máy tính. Trong đề tài này em tập trung nghiên cứu về một số vấn đề liên quan tới số nguyên tố lớn và ứng dụng trong phương pháp chứng minh không tiết lộ thông tin (bỏ lá phiếu điện tử và tiền điện tử). Bố cục luận văn gồm 3 chương. Chương 1 giới thiệu số nguyên tố và các bài toán liên quan và cách phân tích thừa số nguyên tố.Tiếp theo chương 2 trình bày về thuật toán kiểm tra số nguyên tố lớn và ứng dụng trong phương pháp chứng minh không tiết lộ thông tin như bỏ lá phiếu điện tử, tiền điện tử từ đó chúng tôi sẽ có những vị trí đặt trạm làm tiền đề cho chương 3 với thuật toán kiểm tra số nguyên tố lớn để ứng dụng trong bỏ lá phiếu điện tử. Chương 3 sẽ trình bày một số kết quả thực nghiệm để kiểm chứng hiệu quả của thuật toán trên hệ thống máy tính để kiểm tra và sinh số nguyên tố lớn, lồng ghép vào chương trình chứng minh không tiết lộ thông tin trong việc mô tả quá trình bỏ lá phiếu điện tử. vii Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn Chương 1: Số nguyên tố và các bài toán liên quan 1.1. Định nghĩa số nguyên tố Số tự nhiên p, lớn hơn 1 gọi là số nguyên tố nếu như nó chỉ chia hết cho 1 và chính nó. Định lý cơ bản của số học nói rằng, bất kỳ số tự nhiên n, lớn hơn 1 có thể phân tích thành tích các số nguyên tố. Tức là một số tự nhiên n có thể biểu diễn dưới dạng sau: n ở  p1 ... pk , 1 k đây p1  p2  ...  pk - là các số nguyên tố khác nhau, 1,...,k  N . 1.2. Tính chất của số nguyên tố Ký hiệu "b a" nghĩa là b là ước của a, ký hiệu a b nghĩa là a chia hết cho b. Ước tự nhiên khác 1 nhỏ nhất của một số tự nhiên là số nguyên tố.  Chứng minh: Giả sử d a; d nhỏ nhất; d 1. Nếu d không nguyên tố d = d1.d2; d1, d2 > 1 d1|a với d1 < d: mâu thuẫn với d nhỏ nhất. Vậy d là nguyên tố.  Cho p là số nguyên tố; a (a,p) = p (a p) (a,p) = 1 (a p)  Nếu N; a 0. Khi đó tích của nhiều số chia hết cho một số nguyên tố p thì có ít nhất một thừa số chia hết cho p.  Ước số dương bé nhất khác 1 của một hợp số a là một số nguyên tố không vượt quá  2 là số nguyên tố nhỏ nhất và cũng là số nguyên tố chẵn duy nhất  Tập hợp các số nguyên tố là vô hạn. 1 1.3. Sinh số nguyên tố và phân tích thừa số nguyên tố 1.3.1. Sinh số nguyên tố Vậy làm sao chúng ta có thể tìm ra được các số nguyên tố trong số các số nguyên dương (hay số tự nhiên dương)? Trong tập hợp các số tự nhiên, có bao nhiêu số nguyên tố? Cho đến nay, người ta vẫn chưa biết được, bởi vì quy luật của nó rất khó tìm, giống như đứa trẻ bướng bỉnh vậy, nó nấp ở phía đông, chạy ở phía tây, thách thức các nhà toán học. Có lẽ chúng ta cũng đã từng nghe đến phương pháp sàng lọc của nhà toán học Eratosthenes, dùng phương pháp này có thể tìm ra các số nguyên tố rất tiện lợi. Nó giống như là sàng lấy sỏi trong cát, sàng lọc lấy những số nguyên tố trong tập hợp số tự nhiên, bảng các số nguyên tố chính là được làm theo phương pháp này. Thế nhưng, các nhà toán học chưa thỏa mãn với việc dùng phương pháp này để tìm ra số nguyên tố, bởi vì nó có chút mò mẫm nhất định, bạn không thể biết trước được số nguyên sẽ “sàng” ra số nào. Điều mà các nhà toán học muốn là tìm ra quy luật của số nguyên tố để nghiên cứu sâu hơn về nó. Từ trong bảng các số nguyên tố, chúng ta có thể thấy chúng được phân bố như sau: từ 1 đến 1000 có 168 số nguyên tố; từ 1000 đến 2000 có 135 số; từ 2000 đến 3000 có 127 số; từ 3000 đến 4000 có 120 số; từ 4000 đến 5000 có 119 số. Khi số các số tự nhiên càng lớn thì tỉ lệ phân bố các số nguyên tố càng thưa. Số nguyên tố đã "hoá trang" cho mình rồi lẩn khuất trong các số tự nhiên, khiến việc tìm ra chúng trở nên khó khăn hơn. Ví dụ, 101, 401, 601, 701 đều là số nguyên tố, nhưng 301 và 901 thì lại không phải. Có người thử tính như thế này: 12 + 1 + 41 = 43, 22 + 2 + 41 = 47, 32 + 3 + 41 = 53, ..., 392 + 39 + 41 = 1601. Có 39 số từ 43 cho đến 1601 đều là số nguyên tố, thế nhưng tiếp sau đó: 402 +40 +41 =1681 = 41 x 41 thì lại là một hợp số. 2 Nhà toán học người Pháp Ferma từng nghiên cứu lâu dài về số nguyên tố, ông từng đưa ra một suy đoán thế này: số (22n + 1) (với n là số nguyên) thì nhất định là số nguyên tố. Ferma đã thử 5 "số Ferma" đầu thì đều là số nguyên tố, nhưng đến số "ferma" thứ sáu thì lại là hợp số, hơn nữa từ số "Ferma thứ 6" trở đi, không thể phát hiện thấy số nguyên tố nào nữa, toàn là hợp số. Xem ra số nguyên tố đã cố trêu đùa Ferma. Năm 1644, nhà toán học người Pháp Mason đã đưa ra "số Mason", hình thức của nó là (2p - 1). Khi ông còn sống, ông tìm ra 11p để cho (2p - 1) là số nguyên tố, người ta tiến hành kiểm chứng đối với 8p, chúng đều là số nguyên tố. 250 năm sau, năm 1903, các nhà toán học tìm ra số Mason thứ 9 không phải là số nguyên tố mà là hợp số. Mặc dù Mason cũng không thực sự tìm ra quy luật của số nguyên tố, nhưng dùng phương pháp của ông, người ta tìm được nhiều số nguyên tố hơn. Trong đó, số nguyên tố Mason thứ 33 được tìm ra nhờ máy tính điện tử , nó có 378632 là số nguyên tố lớn nhất mà loài người tìm được đến lúc đó. Mersenne, tu sĩ người Pháp sinh năm 1588, đã khám phá ra dạng số nguyên tố 2p-1 Một nhóm các nhà khoa học thuộc Đại học Missouri (Mỹ) đã sử dụng hơn 700 máy tính để tìm ra số nguyên tố lớn nhất cho đến nay, một con số khổng lồ với 9.152.052 con số. Phát hiện này được thực hiện vào ngày 15/12/2005 và đã được xác nhận lại vào ngày 24/12/2005. Sự kiện này đánh dấu lần thứ hai trong năm nay dự án kết hợp máy tính có tên Tìm kiếm số nguyên tố Mersenne trên Internet (GIMPS - Great Internet Mersenne Prime Search) tìm ra số nguyên tố lớn nhất. Nhưng cũng tương tự như phát hiện hồi tháng Hai, con số mới được tìm ra này vẫn chưa đạt được kích thước 10 triệu con số cần thiết để giành được giải thưởng 100.000 USD từ Quỹ điện tử có tên là Electronic Frontier Foundation. Dự án GIMPS khai thác sức mạnh của hơn 200.000 máy tính được cung cấp một cách tình nguyện với nhiệm vụ tìm kiếm tất cả các số nguyên tố Mersene. Một số nguyên tố là một số chỉ có thể chia hết cho 1 và 3 chính nó, và một số nguyên tố Mersenne là một dạng đặc biệt có công thức 2p-1 trong đó p cũng là một số nguyên tố. Ví dụ: 7 cũng là một số nguyên tố Mersenne bởi nó là một số nguyên tố và bằng 2x7 - 1. Đã vài năm nay, những số nguyên tố lớn nhất được phát hiện đều là các số nguyên tố Mersenne. Chúng được đặt tên theo tên của Marin Mersenne, một tu sĩ người Pháp sinh năm 1588, người đã khám phá ra dạng số này. Các số nguyên tố Mersenne trong nhiều trường hợp đã được các cá nhân tìm ra, nhưng lần này thì thành quả lại là của một nhóm tình nguyện viên. Nhóm này tới nay đã cống hiến một năng lực xử lý nhiều hơn bất cứ ai: tương đương với khả năng xử lý của của một máy tính Pentium 90MHz chạy liên tục trong... 67.000 năm. Hai giáo sư Curtis Cooper và Steven Boone là những người phụ trách dự án này. Con số nguyên tố được phát hiện lần này là số nguyên tố Mersenne thứ 43 được tìm ra. 1.3.2. Phân tích ra thừa số nguyên tố Các số có dạng Mq = 2q - 1 (với q là nguyên tố) được gọi là các số Mersenne và đã được nghiên cứu công phu. Vào năm 1640 , Mersenne đã cho rằng M q là số nguyên tố đối với q=13,17,19,31,67,127,257; ông đã nhầm đối với 67 và 257 và đã không đưa 61, 89 và 107 vào danh sách trên. Những số này còn sinh ra các số nguyên tố Mersenne. Phát hiện của ông thực sự đáng kinh ngạc về mặt độ lớn của các số. Một bài toán khá hiển nhiên là: Xét xem một số Mersenne có là số nguyên tố không, và nếu không thì xác định các thừa số của nó ( hay còn gọi là bài toán phân tích ra thừa số). Một kết quả cổ điển do Euler đưa ra năm 1750 và sau đó được Lagrange (1775) và Lucas (1875) chứng minh là: Nếu q là một số nguyên tố đồng dư modul log 4(q(3) (mod 4)) thì Mq chia hết cho 2q + 1 khi và chỉ khi 2q + 1 là nguyên tố; trong trường hợp này, nếu q> 3 thì Mq là hợp số. 4 Thật vậy: Cho n = 2q + 1 là một thừa số của M q Vì 22# 1 (mod n) nên 2q# 1 (mod n), và 22q - 1 = (2q+1)Mqº0 (mod n), từ đó bằng phép thử của Lucas suy ra n là một số nguyên tố. Ngược lại, cho p = 2q + 1 là một số nguyên tố. Vì pº7(mod 8) nên (2/p)=1, do vậy tồn tại m sao cho 2ºm2 (mod p). Điều này chứng tỏ rằng 2qº2(p1)/2 ºmp - 1º1(mod p) Vì vậy Mq chia hết cho p. Hơn nữa, nếu q > 3 thì Mq = 2q-1>29+1=p, vì vậy Mq là hợp số. Vì vậy nếu q =11, 23, 83, 131, 179, 191, 239, 251, thì M q có các ước tương ứng là 23, 47, 167, 263, 350, 383, 479, 503. Còn rất dễ để xác định hình dạng của các thừa số của các số Mersenne: " Nếu Mq chia hết cho n thì nº±1 (mod 8) và nº1 (mod q)" Vậy cho nên ta chỉ cần chỉ ra rằng mọi thừa số nguyên tố p của Mq có dạng trên là đủ. Thật vậy, nếu p là ước của Mq = 2q - 1 thì 2qº1 (mod q); Vì vậy theo bài toán nhỏ của Fermat thì q là ước của p-1, tức là p - 1 = 2kq (vì p#2). Vì 2 vậy: ( p )  2( p1) / 2  2qk  1 (mod p). Do đó pº±1 mod (8). Phương pháp tốt nhất hiện nay dùng để xác định Mq là một số nguyên tố hay là một hợp số được phát triển dựa vào việc tính toán một số đệ qui do Lucas (1878) và Lemer (1930) đưa ra. Tuy nhiên, bằng cách này vẫn không tìm ra được các thừa số cụ thể. Nếu n lẻ, n³3 thì Mn = 2n - 1º7 (mod 12). Đồng thời, nếu Nº7 (mod 12) thì ký hiệu Jacobi: 3 (N )( N 3 )(1) ( N 1) / 2 1 5 Như vậy khi phân tích một số a > 1thành một tích những thừa số nguyên tố, ta có thể gặp cùng một thừa số nhiều lần. Nếu p1,p2,...,pn xuất hiện theo thứ tự α1,...,αn lần thì ta có: a = p1α1 p2α2... pnαn. Đây là dạng phân tích chính tắc tiêu chuẩn của a. Ví dụ: 360 = 23.32.5. Giả sử a = p1α1 p2α2... pnαn là dạng phân tích chính tắc của số tự nhiên a > 1. Khi đó nếu d là một ước dương của a  d = p1β1 p2β2... pnβn với 0 ≤ βi ≤ αi ; i = 1, n Vậy nên nếu cho n sốố tự nhiên lớn hơn 1     a  a 1  p1 n   11 12 p 2 1m ...pm  pm1 pm 2 ...pmn 1 2 m  Khi đó: (a1, ..., an) = p1β1 ... pmβm với βj = min (αij); i = 1, n [a1, ..., an] = p1ƴ1 ... pmƴm, ƴj = max(αij); i= 1, n ; j = ; j = 1, m . 1, m . 1.4. Kết luận chương Như vậy, chương 1 đã tổng quan về số nguyên tố và phân tích thừa số nguyên tố. Đây là kiến thức cơ sở chuẩn bị cho những nghiên cứu tiếp theo của bản luận văn này. Phần đầu nói về định nghĩa và các tính chất của số nguyên tố. Tiếp theo là những vấn đề về sinh số nguyên tố và phân tích số nguyên tố đó ra thừa số. Nội dung chính chương giúp hiểu được số nguyên tố và mô hình hóa lập kế hoạch giải quyết các bài toán về số nguyên tố. Đây là cơ sở quan trọng để tiến hành xây dựng các thuật toán kiểm tra số nguyên tố và sinh số nguyên tố lớn đảm bảo hiệu quả, sẽ trình bày ở các chương tiếp theo. 6 Chương 2: Số nguyên tố lớn và ứng dụng trong chứng minh không tiết lộ thông tin. 2.1. Thuật toán kiểm tra số nguyên tố Bài toán Cho một số nguyên n, kiểm tra xem đó có phải là số nguyên tố hay không? Giải thuật 1: - Nếu n là 1, thì n không là số nguyên tố - Xét tất cả số nguyên i nhỏ hơn (n - 1), kiểm tra xem n có chia hết x không, nếu tất cả không thì n là số nguyên tố. Thuật toán có thể viết dạng giả mã như sau: Giải thuật 1: Kiểm tra số nguyên tố Input: n (lớn hơn 2) Output: 1 nếu n là số nguyên tố, 0 nếu ngược lại Begin for (i=2; i1. Output : Flase nếu n là số nguyên, True nếu n là hợp số. Thuật toán Miller 1. Kiểm tra điều kiện sau có thỏa mãn hay không n  ms , với s, m  N , s  2 . Nếu như thỏa mãn, thì n là hợp số, và thuật toán dừng. 2. Thực hiện các bước nhỏ (i)-(iii) đối với tất cả a  f (n) (i) Kiểm tra điều kiện a|n (ii) Kiểm tra điều kiện an1  (mod n) (iii) Kiểm tra xem có đúng hay không, với một số giá trị của k, 1 k  v2 (n 1) , n1 1  UCLN(a 2k 1(mod n), n)  n Nếu như một trong ba điều kiện (i)-(iii) thỏa mãn thì n là hợp số, và thuật toán dừng. 3. Nếu như chúng ta đi đến được bước này thì n là số nguyên tố. 2.1.3. Kiểm tra tính nguyên tố của số bằng phép kiểm tra xác suất. Các phép kiểm tra tính nguyên tố hay dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a <= p. Nếu n là một số tự nhiên lẻ và mệnh đề Q(n,a) đúng với một a<= n được lấy ngẫu nhiên, khi đó a có khả năng là một số nguyên tố. Ta đưa ra một thuật toán, kết luận rằng n là số nguyên tố. Nó là một thuật toán ngẫu 11