Luận văn Thạc sĩ Công nghệ thông tin: Xác thực điện tử và ứng dụng trong giao dịch hành chính

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

Thêm vào BST

Báo xấu

33
lượt xem 4
download

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

Nội dung của luận văn bao gồm: Chương 1: Trình bày cơ sở toán học của xác thực điện tử, số nguyên tố, số học modulo, các phương pháp kiểm tra số nguyên tố. Chương 2: Phân tích các hệ mật mã được sử dụng trong xác thực điện tử: hệ mật RSA và các biến thể, hệ mật AES, hàm băm SHA-1, SHA-2, SHA-3. Chương 3: Trình bày các vấn đề về xác thực điện tử. Xác thực dữ liệu, xác thực thực thể và xác thực hai yếu tố. Chương 4: Trình bày các vấn đề về giao dịch hành chính điện tử. Phân tích, thiết kế và thử nghiệm chương trình ứng dụng chữ ký số RSA và mã hóa AES trong việc quản lý, gửi và nhận văn bản tại trường Cao đẳng nghề cơ khí nông nghiệp.

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ĩ Công nghệ thông tin: Xác thực điện tử và ứng dụng trong giao dịch hành chính

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN XUÂN PHƯƠNG XÁC THỰC ĐIỆN TỬ VÀ ỨNG DỤNG TRONG GIAO DỊCH HÀNH CHÍNH LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội - 2015
ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN XUÂN PHƯƠNG XÁC THỰC ĐIỆN TỬ VÀ ỨNG DỤNG TRONG GIAO DỊCH HÀNH CHÍNH Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60.48.01.03 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ PHÊ ĐÔ Hà Nội - 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
i LỜI CẢM ƠN Luận văn Thạc sĩ này được thực hiện tại Đại học Công nghệ - Đại học Quốc gia Hà Nội dưới sự hướng dẫn của TS. Lê Phê Đô. Xin được gửi lời cảm ơn sâu sắc đến thầy về định hướng khoa học, liên tục quan tâm, tạo điều kiện thuận lợi trong suốt quá trình nghiên cứu hoàn thành luận văn này. Tôi xin được gửi lời cảm ơn đến các thầy, cô trong Bộ môn Công nghệ phần mềm cũng như Khoa Công nghệ Thông tin đã mang lại cho tôi những kiến thức vô cùng quý giá và bổ ích trong quá trình theo học tại trường. Tôi cũng xin chân thành cảm ơn đến gia đình, bạn bè đã quan tâm và động viên giúp tôi có thêm nghị lực, cố gắng để hoàn thành luận văn này. Do thời gian và kiến thức có hạn nên luận văn chắc chắn không tránh khỏi những thiếu sót nhất định. Tôi rất mong nhận được những sự góp ý quý báu của thầy cô, đồng nghiệp và bạn bè. Hà Nội, tháng 10 năm 2015 Trần Xuân Phương
ii LỜI CAM ĐOAN Tôi xin cam đoan luận văn “Xác thực điện tử và ứng dụng trong giao dịch hành chính” là công trình nghiên cứu của cá nhân tôi dưới sự hướng dẫn của TS. Lê Phê Đô, trung thực và không sao chép của tác giả khác. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp. Tôi xin chịu mọi trách nhiệm cho lời cam đoan này. Hà Nội, tháng 10 năm 2015 Trần Xuân Phương
iii MỤC LỤC LỜI CẢM ƠN ...................................................................................................................i LỜI CAM ĐOAN ........................................................................................................... ii MỤC LỤC ..................................................................................................................... iii DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT ................................................. vii DANH MỤC BẢNG BIỀU ......................................................................................... viii DANH MỤC HÌNH VẼ .............................................................................................. viii MỞ ĐẦU .........................................................................................................................1 Chương 1: CƠ SỞ TOÁN HỌC CỦA XÁC THỰC ĐIỆN TỬ......................................2 1.1. Số nguyên tố .........................................................................................................2 1.2. Hai số nguyên tố cùng nhau ..................................................................................5 1.3. Số học modulo ......................................................................................................5 1.3.1 Hàm Euler .......................................................................................................5 1.3.2. Không gian Zn, Zn* .........................................................................................5 1.3.3. Đồng dư thức ..................................................................................................5 1.3.4. Giá trị thặng dư bậc hai – Ký hiệu Legendre .................................................6 1.3.5. Ký hiệu Jacobi ................................................................................................6 1.4. Các tiêu chuẩn và phương pháp kiểm tra số nguyên tố ........................................6 1.4.1. Tiêu chuẩn Euler và số giả nguyên tố Euler ..................................................6 1.4.2. Định lý nhỏ Fermat và số giả nguyên tố Fermat ............................................7 1.4.3. Số nguyên tố Mersenne ..................................................................................7 1.4.4. Một số phương pháp kiểm tra số nguyên tố ...................................................8 1.4.4.1. Thuật toán Soloway - Strassen ................................................................8 1.4.4.2. Thuật toán Miler-Rabin ...........................................................................9 1.4.4.3. Thuật toán AKS .....................................................................................10 1.5. Hàm một chiều ....................................................................................................12 1.6. Phép chứng minh không tiết lộ tri thức (thông tin) ............................................12 Kết luận chương 1 ......................................................................................................12 CHƯƠNG 2: CƠ SỞ MẬT MÃ CỦA XÁC THỰC ĐIỆN TỬ ...................................13 2.1. Hệ mã hóa khóa công khai ..................................................................................13
iv 2.2. Hệ mật RSA ........................................................................................................14 2.2.1. Giới thiệu hệ mật RSA .................................................................................14 2.2.2. Độ an toàn của hệ mật RSA .........................................................................15 2.2.3. Một số phương pháp RSA cải tiến ...............................................................16 2.2.3.1. RSA với số mũ giải mã lớn ...................................................................16 2.2.3.2. HE-RSA .................................................................................................17 2.2.3.3. Biến thể RSA của Seema Verman, Deepar Garg ..................................18 2.3. Hệ mật AES ........................................................................................................20 2.3.1. Giới thiệu......................................................................................................20 2.3.2. Một số khái niệm, tham số và hàm trong AES ............................................20 2.3.2.1. Input và Output ......................................................................................20 2.3.2.2. Trạng thái (State) ...................................................................................20 2.3.2.3. Khóa ......................................................................................................21 2.3.2.4. Phép cộng ..............................................................................................21 2.3.2.5. Phép nhân với x .....................................................................................22 2.3.3. Chu trình tạo khóa con AES ........................................................................23 2.3.4. Quá trình mã hóa AES .................................................................................24 2.3.4.1. Bước SubBytes ......................................................................................25 2.3.4.2. Bước ShiftRows ....................................................................................26 2.3.4.3. Bước MixColumns ................................................................................27 2.3.4.4. Bước AddRoundKey .............................................................................27 2.3.5. Quá trình giải mã ..........................................................................................27 2.3.5.1. Bước InvSubBytes .................................................................................28 2.3.5.2. Bước InvShiftRows ...............................................................................29 2.3.5.3. Bước InvMixColumns ...........................................................................29 2.3.6. Một ví dụ về giải thuật AES.........................................................................29 2.3.7. Đánh giá giải thuật AES ...............................................................................34 2.4. Hàm băm .............................................................................................................35 2.4.1. Hàm băm MD5 .............................................................................................36 2.4.2. Chuẩn an toàn SHS ......................................................................................36
v 2.4.3. Hàm băm SHA-3 ..........................................................................................36 Kết luận chương 2 ......................................................................................................38 Chương 3: XÁC THỰC ĐIỆN TỬ ...............................................................................39 3.1. Nguồn gốc, lịch sử ra đời ....................................................................................39 3.2. Các khái niệm cơ bản ..........................................................................................40 3.2.1. Xác thực .......................................................................................................40 3.2.2. Xác thực điện tử ...........................................................................................40 3.2.3. Hệ xác thực ..................................................................................................40 3.3. Xác thực thông điệp ............................................................................................40 3.3.1. Khái niệm .....................................................................................................40 3.3.2. Xác thực thông điệp bằng thuật toán mã hóa ...............................................41 3.3.3. Xác thực thông điệp bằng chữ ký số ............................................................42 3.3.3.1. Sơ đồ chữ ký RSA .................................................................................44 3.3.3.2. Sơ đồ chữ ký Elgamal ...........................................................................46 3.3.4. Xác thực thông điệp bằng mã xác thực (MAC - Message Authentication Code) ......................................................................................................................48 3.3.5. Xác thực thông điệp bằng hàm băm .............................................................49 3.4. Xác thực thực thể ................................................................................................50 3.4.1. Khái niệm .....................................................................................................50 3.4.2. Xác thực dựa vào những cái mà thực thể sở hữu bẩm sinh (xác thực bằng sinh trắc học) ..........................................................................................................50 3.4.2.1. Nhận dạng sinh trắc học ........................................................................51 3.4.2.2. Mật mã sinh trắc học .............................................................................52 3.4.2.3. Ứng dụng của sinh trắc học trong xác thực ...........................................55 3.4.3. Xác thực dựa vào những cái thực thể (đối tượng) có ...................................56 3.4.4. Xác thực dựa vào những cái thực thể (đối tượng) biết ................................56 3.5. Xác thực 2 yếu tố (Two Factor Authentication - 2FA) ......................................57 3.5.1. Đặc điểm của xác thực hai yếu tố ................................................................58 3.5.2. Một số công nghệ sử dụng cho xác thực hai yếu tố .....................................58 3.5.2.1. Mật khẩu một lần (One Time Password - OTP)....................................58 3.5.2.2. Xác thực bằng cuộc gọi .........................................................................61
vi 3.5.2.3. Xác thực qua địa điểm ...........................................................................62 3.5.2.4. Yếu tố sinh trắc học ...............................................................................62 3.5.2.5. Các loại thẻ thông minh (smart card) ....................................................62 Kết luận chương 3 ......................................................................................................62 Chương 4: ỨNG DỤNG XÁC THỰC ĐIỆN TỬ TRONG GIAO DỊCH HÀNH CHÍNH...........................................................................................................................63 4.1. Hành chính điện tử ..............................................................................................63 4.1.1. Lịch sử phát triển của hành chính điện tử ....................................................63 4.1.2. Chính phủ điện tử và giao dịch điện tử ........................................................63 4.1.2.1. Chính phủ điện tử ..................................................................................63 4.1.2.2. Giao dịch điện tử ...................................................................................64 4.1.3. Hành chính điện tử trên thế giới ..................................................................64 4.1.4. Hành chính điện tử ở Việt Nam ...................................................................66 4.2. Xác thực điện tử trong các giao dịch hành chính điện tử ...................................67 4.3. Ứng dụng xác thực điện tử trong quản lý, gửi nhận văn bản trường cao đẳng nghề Cơ khí nông nghiệp ...........................................................................................68 4.3.1. Thực trạng quản lý văn bản tại trường cao đẳng nghề Cơ khí nông nghiệp 68 4.3.2. Hệ thống quản lý gửi nhận văn bản trường CĐN Cơ khí nông nghiệp .......69 4.3.2.1. Đặc tả hệ thống ......................................................................................69 4.3.2.2. Các yêu cầu của hệ thống ......................................................................71 4.3.2.3. Phân tích hệ thống .................................................................................71 4.3.2.4. Vấn đề ký số và mã hóa trong hệ thống ................................................77 4.3.2.5. Triển khai hệ thống................................................................................79 Kết luận chương 4 ......................................................................................................81 KẾT LUẬN ...................................................................................................................82 TÀI LIỆU THAM KHẢO .............................................................................................83 PHỤ LỤC ......................................................................................................................84
vii DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT STT Từ viết tắt Ý nghĩa 1 CNTT Công nghệ thông tin 2 DES Data Encryption Standard 3 NIST National Institute of Standards and Technology 4 NBS National Bureau of Standards 5 RSA Ron Rivest, Adi Shamir, Len Adleman 6 Sigk Thao tác ký số 7 Verk Thao tác kiểm tra chữ ký 8 SHS Secure Hash Standard 9 SHA Secure Hash Algorithm 10 MD5 Message-Digest Algorithm 5 11 AES Advanced Encryption Standard 12 OTP One Time Password 13 DSA Digital Signature Algorithm 14  Phép toán XOR 15  Phép nhân hai đa thức 16  Phép nhân trên trường hữu hạn
viii DANH MỤC BẢNG BIỀU [ Bảng 1.1. Bảng 10 số nguyên tố lớn nhất .......................................................................2 Bảng 1.2. Bảng 10 số nguyên tố sinh đôi lớn nhất .........................................................2 Bảng 1.3. Bảng 10 số nguyên tố dạng p#  1 ..................................................................3 Bảng 1.4. Bảng 10 số nguyên tố lớn nhất dạng n! + 1 ....................................................4 Bảng 1.5. Bảng 10 số nguyên tố dạng Sophie German lớn nhất ....................................4 Bảng 2.1. Bảng hằng số mở rộng Rcon của AES - 128 ................................................23 Bảng 2.2. Bảng khóa mở rộng AES – 128 ....................................................................23 Bảng 2.3. Mối liên hệ giữa Nk, Nb và Nr .....................................................................24 Bảng 2.4. Bảng thay thế S-box ......................................................................................25 Bảng 2.5. Bảng giá trị Shift(r, Nb) ................................................................................26 Bảng 2.6. Bảng thay thế S-box-1 ....................................................................................28 Bảng 3.1. Mật khẩu OTP cho các phiên làm việc .........................................................60 Bảng 4.1. Xếp hạng chính phủ điện tử năm 2015 .........................................................65 DANH MỤC HÌNH VẼ Hình 2.1. Sơ đồ hệ mã hóa khóa công khai ...................................................................14 Hình 2.2. Biểu diễn ma trận đầu vào và ma trận đầu ra ................................................20 Hình 2.3. Biểu diễn quá trình biến đối từ input  state -> output ................................21 Hình 2.4. Biểu diễn khóa K = 128 bit ...........................................................................21 Hình 2.5. Quy trình mã hóa AES ..................................................................................25 Hình 2.6. Quá trình biến đổi SubByte ...........................................................................26 Hình 2.7. Quy trình giải mã AES ..................................................................................28 Hình 2.8. Sơ đồ hàm băm ..............................................................................................35 Hình 2.9. Input và output của SHA-3 ............................................................................37 Hình 2.10. Cấu trúc Sponge ..........................................................................................37 Hình 2.11. Hàm lặp f của SHA – 3 ................................................................................38 Hình 3.1. Xác thực thông điệp bằng mật mã .................................................................42 Hình 3.2. Sơ đồ tạo chữ ký số .......................................................................................43 Hình 3.3. Sơ đồ xác thực chữ ký số ...............................................................................44 Hình 3.4. Xác thực thông điệp bằng mã xác thực (MAC) ............................................48 Hình 3.5. Xác thực thông điệp bằng hàm băm ..............................................................49
ix Hình 3.6. Các đặc trưng sinh trắc phổ biến ...................................................................50 Hình 3.7. Quá trình lấy mẫu của mật mã sinh trắc học .................................................53 Hình 3.8. Quá trình xác thực của mật mã sinh trắc học ................................................54 Hình 3.9. Sơ đồ mật mã sinh trắc học ...........................................................................54 Hình 3.10. Sử dụng OTP trong giao dịch ngân hàng ....................................................59 Hình 3.11. Thiết bị OTP - Token ..................................................................................61 Hình 3.12. Phần mềm OTP............................................................................................61 Hình 4.1. Mối quan hệ giữa cơ sở hạ tầng và các dịch vụ trực tuyến [4] .......................65 Hình 4.2. Mô hình xác thực hai yếu tố của hệ thống SingPass .....................................67 Hình 4.3. Ứng dụng hệ mật RSA, AES trong giao dịch hành chính .............................68 Hình 4.4. Quá trình nhận văn bản thủ công ...................................................................69 Hình 4.5. Quá trình gửi văn bản nội bộ thủ công ..........................................................69 Hình 4.6. Sơ đồ hoạt động hệ thống gửi nhận văn bản .................................................70 Hình 4.7. Quá trình xử lý văn bản đến ..........................................................................70 Hình 4.8. Quá trình xử lý văn bản nội bộ ......................................................................70 Hình 4.9. Quá trình nhận văn bản..................................................................................71 Hình 4.10. Sơ đồ ca sử dụng tổng quát .........................................................................71 Hình 4.11. Sơ đồ ca sử dụng của tác nhân Quan_Tri_He_Thong .................................72 Hình 4.12. Sơ đồ ca sử dụng của tác nhân Nguoi_Dung ..............................................72 Hình 4.13. Biểu đồ tuần tự chức năng gửi văn bản .......................................................76 Hình 4.14. Biểu đồ tuần tự chức năng ký văn bản ........................................................76 Hình 4.15. Biểu đồ tuần tự chức năng nhận văn bản ....................................................77 Hình 4.16. Lưu đồ hoạt động chức năng gửi văn bản ...................................................78 Hình 4.17. Lưu đồ hoạt động chức năng nhận văn bản .................................................78 Hình 4.18. Cửa sổ gửi văn bản ......................................................................................79 Hình 4.19. Cửa sổ ký và mã hóa văn bản. .....................................................................80 Hình 4.20. Cửa sổ hiển thị thông tin chi tiết của văn bản .............................................80 Hình 4.21. Cửa sổ xác thực văn bản ..............................................................................81 Hình 4.22. Cửa sổ tạo mới người dùng .........................................................................81
1 MỞ ĐẦU Hành chính điện tử đang phát triển mạnh mẽ ở nhiều quốc gia trên thế giới trong đó có Việt Nam. Với hành chính điện tử, người dân và các doanh nghiệp dễ dàng tiếp cận, trao đổi công việc với các cơ quan nhà nước. Đồng thời thúc đẩy công cuộc cải cách hành chính nhằm giảm thiểu sự cồng kềnh của bộ máy tổ chức, nâng cao hiệu quả làm việc, đáp ứng nhu cầu công khai và minh bạch trong công tác quản lý cũng như giảm thiểu số lượng và thời gian cho các hoạt động thủ tục hành chính. Trên thế giới, hành chính điện tử được nhiều quốc gia bắt tay xây dựng từ sớm và đạt được những thành quả nhất định như: Singapore, Anh, Hàn Quốc… Đặc biệt, tại Singapore hàng ngàn dịch vụ công được cung cấp đến người dân và doanh nghiệp thông mạng internet, máy tính và các thiết bị di động. Người dân có thể truy cập tất cả các dịch vụ công thông qua một cổng thông tin quốc gia duy nhất. Tại Việt Nam, nền hành chính điện tử cũng từng bước phát triển và đạt được nhiều thành tựu. Nhiều cơ quan nhà nước, các tỉnh thành đã triển khai các dịch vụ công trực tuyến. Có thể kể đến như tổng cục Hải quan, tổng cục thuế, thành phố Đà Nẵng… được người dân và các doanh nghiệp đánh giá cao. Trong nền hành chính điện tử, vấn đề chứng minh tính hợp pháp của người dùng, đảm bảo an toàn, xác thực nguồn gốc và tính nguyên vẹn của thông tin trong các giao dịch hành chính là một việc hết sức quan trọng và cần thiết. Trên thế giới và tại Việt Nam đã áp dụng nhiều phương pháp bảo mật và xác thực như sử dụng một mật khẩu chung duy nhất cho các dịch vụ, sử dụng mã xác thực OTP, các thuật toán mã hóa và chữ ký số… Trong luận văn này, tôi sẽ tìm hiểu, nghiên cứu một số thuật toán nền tảng trong xác thực điện tử, nghiên cứu về các phương pháp xác thực phổ biến hiện nay, đồng thời ứng dụng chữ ký số RSA và thuật toán mã hóa AES, xây dựng ứng dụng hỗ trợ gửi và nhận văn bản tại trường Cao đẳng nghề Cơ khí nông nghiệp. Nội dung của luận văn gồm các chương sau: Chương 1. Trình bày cơ sở toán học của xác thực điện tử, số nguyên tố, số học modulo, các phương pháp kiểm tra số nguyên tố. Chương 2. Phân tích các hệ mật mã được sử dụng trong xác thực điện tử: hệ mật RSA và các biến thể, hệ mật AES, hàm băm SHA-1, SHA-2, SHA-3 Chương 3. Trình bày các vấn đề về xác thực điện tử. Xác thực dữ liệu, xác thực thực thể và xác thực hai yếu tố. Chương 4. Trình bày các vấn đề về giao dịch hành chính điện tử. Phân tích, thiết kế và thử nghiệm chương trình ứng dụng chữ ký số RSA và mã hóa AES trong việc quản lý, gửi và nhận văn bản tại trường Cao đẳng nghề cơ khí nông nghiệp. Kết luận và hướng phát triển: Rút ra kết luận và hướng phát triển của luận văn.
2 Chương 1: CƠ SỞ TOÁN HỌC CỦA XÁC THỰC ĐIỆN TỬ Trong chương này, tác giả trình bày các cơ sở toán học của xác thực điện tử. Đầu tiên, tác giả trình bày về số nguyên tố, một số dạng số nguyên tố đặc biệt được ứng dụng phổ biến trong các hệ mật mã. Tiếp theo, tác giả trình bày một số lý thuyết về số học modulo và các tiêu chuẩn và phương pháp kiểm tra số nguyên tố. 1.1. Số nguyên tố Trong tập các số nguyên Z = {…, - 2, -1, 0, 1, 2, …}, chúng ta xét các số nguyên dương mà chỉ chia hết cho 1 và chính nó. Tập các số như vậy được gọi là tập các số nguyên tố. Ví dụ các số nguyên tố: 2, 3, 5, 7, 11, …, 1299827, … Số nguyên tố lớn nhất được tìm ra cho đến nay là 257885161 – 1 bao gồm 17425170 chữ số. Theo https://primes.utm.edu/largest.html ta có các kết quả sau: Bảng 10 số nguyên tố lớn nhất được phát hiện ra cho tới thời điểm này: Bảng 1.1. Bảng 10 số nguyên tố lớn nhất [18] rank prime digits who when reference 1 257885161-1 17425170 G13 2013 Mersenne 48?? 2 243112609-1 12978189 G10 2008 Mersenne 47?? 3 242643801-1 12837064 G12 2009 Mersenne 46?? 4 237156667-1 11185272 G11 2008 Mersenne 45? 5 232582657-1 9808358 G9 2006 Mersenne 44 6 230402457-1 9152052 G9 2005 Mersenne 43 7 225964951-1 7816230 G8 2005 Mersenne 42 8 224036583-1 7235733 G7 2004 Mersenne 41 9 220996011-1 6320430 G6 2003 Mersenne 40 10 213466917-1 4053946 G5 2001 Mersenne 39 Mười số nguyên tố sinh đôi lớn nhất được tìm thấy là: Bảng 1.2. Bảng 10 số nguyên tố sinh đôi lớn nhất [18] rank prime digits who when reference 1 3756801695685·2666669+1 200700 L1921 2011 Twin (p+2)
3 2 3756801695685·2666669-1 200700 L1921 2011 Twin (p) 3 65516468355·2333333+1 100355 L923 2009 Twin (p+2) 4 65516468355·2333333-1 100355 L923 2009 Twin (p) 5 4884940623·2198800+1 59855 L4166 2015 Twin (p+2) 6 4884940623·2198800-1 59855 L4166 2015 Twin (p) 7 2003663613·2195000+1 58711 L202 2007 Twin (p+2) 8 2003663613·2195000-1 58711 L202 2007 Twin (p) 9 38529154785·2173250+1 52165 L3494 2014 Twin (p+2) 10 38529154785·2173250-1 52165 L3494 2014 Twin (p) Cho đến nay, mười số nguyên tố dạng Mersener lớn nhất tìm được cũng chính là mười số nguyên tố lớn nhất ở thời điểm này. Người ta còn nghiên cứu các số nguyên tố dạng p#±1 (tích của các số nguyên tố nhỏ hơn hoặc bằng p cộng trừ 1). Số nguyên tố lớn nhất dạng p#±1 là số 1.098.133#-1 gồm 476.311 chữ số, được phát hiện ra vào tháng 3 năm 2012. Mười số nguyên tố lớn nhất dạng p#±1: Bảng 1.3. Bảng 10 số nguyên tố dạng p#  1 [18] rank Prime digits who when Reference 1 1098133#-1 476311 p346 2012 Primorial 2 843301#-1 365851 p302 2010 Primorial 3 392113#+1 169966 p16 2001 Primorial 4 366439#+1 158936 p16 2001 Primorial 5 145823#+1 63142 p21 2000 Primorial 6 42209#+1 18241 p8 1999 Primorial 7 24029#+1 10387 C 1993 Primorial 8 23801#+1 10273 C 1993 Primorial 9 18523#+1 8002 D 1989 Primorial 10 15877#-1 6845 CD 1992 Primorial Số nguyên tố lớn nhất dạng n!+1 là số 150.209!+1 gồm 712.355 chữ số, được chứng minh vào tháng 10 năm 2011. Mười số nguyên tố lớn nhất dạng n!+1
4 Bảng 1.4. Bảng 10 số nguyên tố lớn nhất dạng n! + 1 [18] rank prime digits Who When reference 1 150209!+1 712355 p3 2011 Factorial 2 147855!-1 700177 p362 2013 Factorial 3 110059!+1 507082 p312 2011 Factorial 4 103040!-1 471794 p301 2010 Factorial 5 94550!-1 429390 p290 2010 Factorial 6 34790!-1 142891 p85 2002 Factorial 7 26951!+1 107707 p65 2002 Factorial 8 21480!-1 83727 p65 2001 Factorial 9 6917!-1 23560 g1 1998 Factorial 10 6380!+1 21507 g1 1998 Factorial Số nguyên tố p được gọi là số nguyên tố dạng Sophie German nếu 2p+1 cũng là số nguyên tố. Số nguyên tố dạng Sophie Germain có ứng dụng nhiều trong mật mã. Chẳng hạn, hệ mật ElGamal sẽ có độ mật cao nếu số nguyên tố ta chọn có dạng 2p+1, nghĩa là p là số nguyên tố Sophie Germain. Những số nguyên tố dạng Spophie Germain đầu tiên là: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511,1559 Mười số nguyên tố dạng Sophie German lớn nhất là: Bảng 1.5. Bảng 10 số nguyên tố dạng Sophie German lớn nhất [18] rank Prime digits who when reference 1 18543637900515·2666667-1 200701 L2429 2012 Sophie Germain (p) 2 183027·2265440-1 79911 L983 2010 Sophie Germain (p) 3 648621027630345·2253824-1 76424 x24 2009 Sophie Germain (p) 4 620366307356565·2253824-1 76424 x24 2009 Sophie Germain (p) 5 607095·2176311-1 53081 L983 2009 Sophie Germain (p) 6 48047305725·2172403-1 51910 L99 2007 Sophie Germain (p) 7 137211941292195·2171960-1 51780 x24 2006 Sophie Germain (p)
5 8 31737014565·2140003-1 42156 L95 2010 Sophie Germain (p) 9 14962863771·2140001-1 42155 L95 2010 Sophie Germain (p) 10 33759183·2123458-1 37173 L527 2009 Sophie Germain (p) 1.2. Hai số nguyên tố cùng nhau Hai số m và n được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1. Ký hiệu gcd(m,n) = 1 Ví dụ: 9 và 14 là nguyên tố cùng nhau vì gcd(9,14) = 1. 1.3. Số học modulo 1.3.1 Hàm Euler Hàm Euler: Cho số nguyên dương n, số lượng các số nguyên dương bé hơn n và nguyên tố cùng nhau với n ký hiệu  (n) được gọi là hàm Euler. Nhận xét: Nếu p là số nguyên tố thì  ( p)  p  1 . Định lý về hàm Euler: Nếu n là tích của hai số nguyên tố n = p.q, thì:  (n)   ( p). (q)  ( p  1)(q  1) 1.3.2. Không gian Zn, Zn* Không gian Zn: là tập các số nguyên {0, 1, 2, ..., n - 1}. Các phép toán trong Zn như cộng, trừ, nhân, chia đều được thực hiện theo modulo n. Ví dụ: Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8} Các phép toán trong Z9 được thực hiện theo modulo 9: 7 + 8 = 6 vì 7 + 8 = 15 mod 9 = 6. Không gian Zn*: là tập các số nguyên a  Zn, nguyên tố cùng nhau với n. Ký hiệu: Zn* = {a  Zn | gdc(n,a)=1}; Số phần tử của Zn* là  (n) Nếu n là một số nguyên tố thì: Zn* = {a  Zn | 1  a  n - 1} Ví dụ: Z5 = {0, 1, 2, 3, 4} thì Z5* = {1, 2, 3, 4} 1.3.3. Đồng dư thức Cho số nguyên dương n, hai số nguyên a, b được gọi là đồng dư theo modulo n nếu n|(a-b). Ký hiệu là:
6 a ≡ b (mod n) * Phần tử nghịch đảo: Cho hai số nguyên dương n và a ∈ Zn* . Số x  {0,1,2...,n-1) sao cho: ax  1 (mod n) được gọi là phần tử nghịch đảo của a theo modulo n. Ký hiệu là: x = a-1 (mod n). 1.3.4. Giá trị thặng dư bậc hai – Ký hiệu Legendre[5] Cho n là một số nguyên, y thuộc Zn được gọi là thặng dư bậc hai modulo n nếu tồn tại x Zn sao cho y  x2 (modulo n). a Nếu p là số nguyên tố lẻ và a là một số tự nhiên thì kí hiệu Legendre   được xác  p định như sau: 0 nếu a ≡ 0 (mod p) a   = 1 nếu a là giá trị thặng dư bậc hai của p  p -1 nếu a không phải là giá trị thặng dư bậc hai của p. 1.3.5. Ký hiệu Jacobi[5] Cho n là một số nguyên dương lẻ có phân tích chuẩn n  p1t p2t ... pmt ở đây 1 2 m pi , i  1, 2,..., m là các số nguyên tố. Khi a là một số nguyên tố cùng nhau với n thì ký a hiệu Jacobi   được định nghĩa như sau: n t1 t2 tm a  a  a  a   a    t t       ...   n   p1 p2 ... pm t   p1   p2   pm  1 2 m Ví dụ:  14   14  14   2  4             1.1  1  15   3  5   3  5  1.4. Các tiêu chuẩn và phương pháp kiểm tra số nguyên tố 1.4.1. Tiêu chuẩn Euler và số giả nguyên tố Euler Euler chứng minh rằng với mọi số nguyên tố p và số a, 1  a  p thì: a ( p 1)/2  a mod p   p Ví dụ: a = 6, p = 7 (6/7) – Ký hiệu Legendre = -1
7 6(7-1)/2 (mod 7) = 6 Số giả nguyên tố Euler: Hợp số n được gọi là số giả nguyên tố Euler cơ sở a (1 < a < n) nếu: a ( n 1)/2  a mod n   n Trong đó:   là ký hiệu Jacobi. a   n 1.4.2. Định lý nhỏ Fermat và số giả nguyên tố Fermat Định lý Fermat: Nếu p là số nguyên tố, a là số nguyên thì a p  a (mod p) . Một cách phát biểu khác của định lý như sau: Nếu p là số nguyên tố và a là số nguyên tố cùng nhau với p thì ap-1 - 1 sẽ chia hết cho p, nghĩa là: ap-1  1 (mod p) Ví dụ: 47  4 (mod 7); 47-1  1 (mod 7). Số nguyên tố Fermat: Là một số nguyên dương có dạng: Fn  22  1 n Rất nhiều số Fermat là số nguyên tố nên một thời người ta cho rằng tất cả các số có dạng đó đều là số nguyên tố. Với n là số không âm. Các số Fermat đầu tiên bao gồm: F0 = 21 + 1 = 3 F1 = 2 2 + 1 = 5 F2 = 24 + 1 = 17 F3 = 28 + 1 = 257 F4 = 216 + 1 = 65.537 F5 = 232 + 1 = 4.294.967.297 F6 = 264 + 1 = 18.446.744.073.709.551.617 F7 = 2128 + 1 = 340.282.366.920.938.463.463.374.607.431.768.211.457 F8 = 2256 + 1 = 115.792.089.237.316.195.423.570.985.008.687.907.853.269.984.665.640.564.039.457 .584.007.913.129.639.937 1.4.3. Số nguyên tố Mersenne Số nguyên tố Mersenne là một số Mersenne có dạng lũy thừa của 2 trừ 1: 2n − 1. Một số định nghĩa yêu cầu lũy thừa n phải là số nguyên tố. Điều kiện cần để Mn là số nguyên tố là n là số nguyên tố nhưng ngược lại không đúng.
8 Ví dụ: 31 = (25 - 1) là một số nguyên tố 15 = (24 -1) là hợp số vì 4 là hợp số. Số Mersenne 2047 = 211 − 1 với 11 là số nguyên tố nhưng 2027 không phải số nguyên tố vì nó chia hết cho 89 và 23. 1.4.4. Một số phương pháp kiểm tra số nguyên tố 1.4.4.1. Thuật toán Soloway - Strassen Giả sử p là số nguyên tố lẻ và a là số nguyên không chia hết cho p. Khi đó theo chuẩn Euler thì: p 1 a a 2     mod p  .  p Như vậy, để kiểm tra tính nguyên tố của một số nguyên dương lẻ n, ta có thể lấy một số nguyên a nguyên tố cùng nhau với n và kiểm tra đồng dư thức n 1 a a 2     mod n  , n Trong đó, vế phải của đồng dư thức là ký hiệu Jacobi. Nếu việc kiểm tra này không đúng thì n chắc chắn là hợp số. Ngược lại, ta chưa kết luận được chính xác n là số nguyên tố, nhưng nhiều khả năng n là số nguyên tố. Thuật toán Solovay - Strassen: Input: Số nguyên dương lẻ n và tham số k. Output: Kết luận n là nguyên tố hay hợp số. 1. Khi i chạy từ 1 đến k thì tiến hành làm 1.1 Chọn ngẫu nhiên số nguyên a, 1 < a < n – 1. n 1 1.2 Tính r  a 2 mod n bằng phương pháp bình phương liên tiếp. 1.3 Nếu r ≠ 1 và r ≠ n – 1 thì RETURN (hợp số). a 1.4 Tính kí hiệu Jacobi s    n 1.5 Nếu r ≠ s (mod n) thì RETURN (hợp số) 2. RETURN (nguyên tố). Độ phức tạp của thuật toán: O (n2)
9 1.4.4.2. Thuật toán Miler-Rabin * Tiêu chuẩn Miler – Rabin: Giả sử p là một số nguyên tố lẻ, khi đó p - 1 là số chẵn và ta có thể viết p − 1 dưới dạng: p – 1 = 2s . m, trong đó s là một số tự nhiên >=1 và m là số lẻ. - Điều này nghĩa là ta rút hết các thừa số 2 khỏi p − 1. Lấy số a bất kỳ trong tập {1,2,..,p-1}. Xét dãy số xk  a k 2 .m với k=0,1,2,...,s. Khi đó xk  ( xk 1 )2 , với k=1,2,...,s và xs  a p 1 Từ định lý Fermat nhỏ: a p 1  1(mod p) hay xs  1(mod p) hay xs21  1(mod p) Do đó, hoặc xs 1  1(mod p) hoặc xs 1  1(mod p) . Nếu xs 1  1(mod p) ta dừng lại, Ngược lại ta tiếp tục với xs  2 . Sau một số hữu hạn bước: - hoặc ta có một chỉ số k, 0  k  s 1 sao cho xk  1(mod p) , - hoặc tới k=0 ta vẫn có xk  1(mod p) . => Ta có mệnh đề Q(p,a) như sau: Nếu p là số nguyên tố lẻ và p - 1 = 2s.m thì với mọi a: 0