ĐẠ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
1
prime
digits
who
when
reference
3756801695685·2666669+1 200700 L1921 2011 Twin (p+2)
3
3756801695685·2666669-1 200700 L1921 2011 Twin (p)
2
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
1
nếu a là giá trị thặng dư bậc hai của p
-1
a
=
p
nếu a ≡ 0 (mod p)
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]
t
t
Cho n là một số nguyên dương lẻ có phân tích chuẩn n p1t p2 ... pm ở đâ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
n
hiệu Jacobi được định nghĩa như sau:
a
a
t t
t
n p1 p2 ... pm
1
2
m
t1
t2
a a a
...
p1 p2 pm
tm
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
mod p
a
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
mod n
a
n
a
Trong đó: là ký hiệu Jacobi.
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ì:
a
p 1
2
a
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
a
n 1
2
a
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.
1.2 Tính r a
n 1
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
n
1.4 Tính kí hiệu Jacobi s
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}.
2 .m
Xét dãy số xk a
với k=0,1,2,...,s.
k
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
xs21 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
= 1 và m là số tự nhiên lẻ
.PDF 
100 
162 
91 
