TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2
KHOA TOÁN
———————o0o——————–

KHÓA LUẬN TỐT NGHIỆP

PHÂN TÍCH THỪA SỐ NGUYÊN TỐ VÀ ỨNG
DỤNG TRONG MẬT MÃ
Chuyên ngành: TOÁN ỨNG DỤNG

Giảng viên hướng dẫn:
Sinh viên:

Trần Vĩnh Đức
Đặng Kiều Trang

Lớp: K37-sp Toán

HÀ NỘI, 5/2015


LỜI CẢM ƠN

Bài khóa luận này được hoàn thành dưới sự hướng dẫn nhiệt tình của thầy giáo T.S
Trần Vĩnh Đức. Qua đây em xin gửi lời cảm ơn sâu sắc tới các thầy cô trong tổ Toán ứng
dụng và các thầy cô trong khoa Toán trường ĐHSP Hà Nội 2 đã giúp đỡ em trong quá
trình học tập để thuận lợi cho việc nghiên cứu. Đặc biệt, em xin gửi lời cảm ơn chân thành
tới thầy giáo T.S Trần Vĩnh Đức người đã dành cho em sự hướng dẫn nhiệt tình, chu đáo
và chỉ bảo cho em trong suốt quá trình học tập nghiên cứu và thực hiện khóa luận.
Dù đã hết sức cố gắng, nhưng do đây là lần đầu tiên làm quen với việc nghiên cứu khoa
học và do năng lực còn hạn chế nên khó tránh khỏi những sai sót. Em mong muốn nhận

2

1 Phân tích thừa số nguyên tố và ứng dụng trong mật mã
1.1 Công thức Euler . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Hệ mật mã khóa công khai RSA . . . . . . . . . . . . . . .
1.3 Kiểm tra tính nguyên tố . . . . . . . . . . . . . . . . . . .
1.4 Thuật toán phép nhân tử hóa Pollard p-1 . . . . . . . . .
1.5 Phân tích thừa số qua hiệu của các bình phương . . . . . .
2 Số
2.1
2.2
2.3

trơn, sàng và xây
Số trơn . . . . . .
Sàng bậc hai . . .
Sàng trường số .

Tài liệu tham khảo

dựng quan hệ cho
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . . .

phép nhân
. . . . . . .
. . . . . . .
. . . . . . .


33
33
34
41

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.


trong các ứng dụng mã hóa.
Ta bắt đầu với một ví dụ. Với lũy thừa modun 15 sẽ làm như thế nào? Nếu
ta thực hiện bảng của lũy thừa bậc 2 và bậc 3 mod 15, chúng trông không thật
thú vị, nhưng nhiều lũy thừa bậc 4 đồng dư với 1 mod 15. Cụ thể, ta thấy rằng

a4 ≡ 1 (mod 15) với a = 1, 2, 4, 7, 8, 11, 13 và 14;

a4 ≡ 1 (mod 15) với a = 3, 5, 6, 9, 10 và 12.

Vậy sự khác nhau giữa dãy các số 1, 2, 4, 7, 8, 11, 13, 14 với dãy các số 3, 5, 6, 9, 10, 12, 15
là gì? Ta thấy, mỗi số 3, 5, 6, 9, 10, 12, 15 đều có một bội chung 15, còn các số
4


1, 2, 4, 7, 8, 11, 13, 14 là các số nguyên tố cùng nhau với 15. Điều này cho thấy
rằng một số phiên bản của Định lý nhỏ Fermat cũng đúng nếu số a là số nguyên
tố cùng nhau với modun m, nhưng số mũ không nhất thiết phải là m − 1.
Cho m = 15 ta thấy số mũ đúng là 4. Tại sao là 4? Ta có thể dễ dàng kiểm
tra với mỗi giá trị của a, nhưng có một thuật toán cụ thể sẽ tốt hơn. Để chứng
minh a4 ≡ 1 (mod 15) ta cần kiểm tra 2 đồng dư thức
Từ (1.1) ta thấy

a4 ≡ 1 (mod 3) và a4 ≡ 1 (mod 5).

(1.1)

.
.
a4 − 1 .. 3 và a4 − 1 .. 5

≡ 1 (mod p) vì 1 lũy thừa luôn bằng 1!
5


Tương tự, thay đổi vai trò của p và q, ta có

a(p−1)(q−1)/g ≡ 1 (mod q).
Như vậy a(p−1)(q−1)/g − 1 chia hết cho cả p và q, do đó nó chia hết cho pq. Ta
được điều phải chứng minh.
Phương pháp thay đổi khóa Diffie-Hellman và hệ thống mật mã khóa công
khai ElGamal phụ thuộc vào những khó khăn khi giải phương trình dạng

ax ≡ b (mod p).
Trong đó a, b và p là các số đã biết, p là số nguyên tố, và x là ẩn. Hệ thống
mật mã khóa công khai RSA mà chúng ta nghiên cứu trong phần tiếp theo phụ
thuộc vào độ khó của việc giải phường trình dạng

xe ≡ c (mod N),
Với e, c và N là các số đã biết và x là ẩn. Nói cách khác, việc bảo mật của RSA
dựa trên giả thiết là nó rất khó để tính căn bậc e modun N.
Đây có phải là một giả thuyết hợp lý? Nếu modun N là số nguyên tố thì sẽ
tương đối dễ dàng trong việc để tính căn bậc e modun N, như được trình bày
trong các mệnh đề dưới đây.
Mệnh đề 1.1.2. Cho p là một số nguyên tố và e ≥ 1 là một số nguyên thỏa
mãn UCLN(e, p − 1) = 1. Ta thấy rằng e có modun nghịch đảo p − 1, ta nói

de ≡ 1 (mod p − 1).
Khi đó đồng dư thức

xe ≡ c (mod p).


x1 ≡ x1 de ≡ (x1e )d ≡ cd ≡ (x2e)d ≡ x2de ≡ x2 (mod p).
Vậy Mệnh đề 1.1.2 có nghiệm duy nhất.
Ví dụ 1.1.3. Giải đồng dư thức sau

x1583 ≡ 4714 (mod 7919),
Với modun p = 7919 là số nguyên tố. Theo Mệnh đề 1.1.2, đầu tiên ta cần giải
đồng dư thức 1583d ≡ 1 (mod 7918).
Để tìm d ta sử dụng thuật toán Euclide mở rộng, ta tìm được d ≡ 5277 (mod 7981).
Từ Mệnh đề 1.1.2 ta thấy

x ≡ 47145277 ≡ 6059 (mod 7919)
là nghiệm của x1583 ≡ 4714 (mod 7919).
Mệnh đề 1.1.2 cho thấy rằng rất dễ để tính nghệm nếu modun p là một số
nguyên tố. Trong trường hợp cho modun N là một hợp số thì sẽ có một sự
khác biệt rất quan trọng. Nếu chúng ta biết phân tích N thì lại dễ dàng để tính
nghiệm. Các mệnh đề sau đây trình bày phương pháp làm trong trường hợp
N = pq là tích của hai số nguyên tố. Các trường hợp tổng quát được để lại xem
như Bài tập.

7


Mệnh đề 1.1.4. Cho p và q là các số nguyên tố khác nhau và e ≥ 1 thỏa mãn

UCLN(e, (p − 1)(q − 1)) = 1.
Ta thấy e có modun nghịch đảo là (p − 1)(q − 1), ta nói

de ≡ 1 (mod (p − 1)(q − 1)).
Khi đó đồng dư thức


u ≡ ude−k(p−1)(q−1) vì de = 1 + k(p − 1)(q − 1).
≡ (ue)d .(u(p−1)(q−1))−k
≡ (ue)d .1−k (mod pq) sử dụng công thức Euler (Định lý 1.1.1)
≡ cd (mod pq) vì u là nghiệm của (1.2)
Do đó, tất cả nghiệm của (1.2) đều đồng dư với cd (mod pq), như vậy đó là
nghiệm duy nhất.
8


Nhận xét 1.1.5. Mệnh đề 1.1.4 đưa ra một thuật toán để giải xe ≡ c(mod pq).

Đầu tiên là giải de = 1(mod (p − 1)(q − 1)), rồi tính cd (mod pq). Ta có thể
làm cho các tính toán nhanh hơn bằng cách sử dụng một giá trị nhỏ hơn d. Cho
g = UCLN(p − 1, q − 1) và giả sử ta giải đồng dư thức sau với d :

de ≡ 1

mod

(p − 1)(q − 1)
.
g

Từ công thức Euler (Định lý 1.1.1) ta có a(p−1)(q−1)/g ≡ 1 (mod pq). Do đó như

trong chứng minh của Mệnh đề 1.1.4, nếu ta viết de = 1 + k(p − 1)(q − 1)/g,
thì
(cd )e = cd e = c1+k(p−1)(q−1)/g = c.(c(p−1)(q−1))k ≡ c (mod pq).
Vì vậy sử dụng giá trị nhỏ hơn này của d, ta vẫn thấy rằng cd mod pq là nghiệm

lên lùy thừa 5629th, trong khi sử dụng Mệnh đề 1.1.4 yêu cầu trực tiếp ta nâng
43927 lên lũy thừa 53509th. Cách làm này tiết kiệm thời gian, mặc dù không
phải là nhiều.
Bob

Plice
Tạo khóa

Chọn số nguyên tố bí mật p và q.
Chọn số mũ mã hóa e với

UCLN(e, (p − 1)(q − 1)) = 1.
Cho biết N = pq và e.
Mã hóa
Chọn bản rõ m.
Sử dụng khóa công khai của Bob (N,e)
để tính c ≡ me (mod N).
Gửi bản mã cho Bob.
Giải mã
Tính d thỏa mãn
ed ≡ 1 (mod (p − 1)(q − 1)).
Tính m′ ≡ cd (mod N)
khi đó m′ là bản rõ m.

Bảng 1.1: Thành lập khóa RSA, mã hóa và giải mã

1.2

Hệ mật mã khóa công khai RSA



tích thừa số N = pq. Mặt khác, Eve có thể chặn được bản mã c nếu cô ấy biết
phân tích N, cô có lẽ đã gặp khó khăn khi giải xe ≡ c (mod N).
Ví dụ 1.2.1. Có thể minh họa hệ mật khóa công khai RSA với một ví dụ bằng
số nhỏ. Tất nhiên, ví dụ này là không an toàn, vì con số này là quá nhỏ nên
Eve sẽ dễ phân tích được N.
Việc triển khai an toàn của RSA sử dụng modun N với hàng trăm chữ số.
Sự Thành Lập Khóa K
11


• Bob chọn hai số nguyên tố bí mật p = 1223 và q = 1987. Bob tính modun
chung của chúng
N = p.q = 1223.1987 = 2430101.
• Bob chọn một số mũ mã hóa công khai e = 948.047 với tính chất
UCLN(e, (p − 1), (q − 1)) = UCLN(94807, 2426892) = 1.
Mã Hóa RSA
• Alice chuyển đổi bản rõ cô thành một số nguyên

m = 1070777 thỏa mãn 1 ≤ m < N.
• Alice sử dụng khóa công khai của Bob (N, e) = (2430101, 948047) để tính
c ≡ me (mod N), c ≡ 107077794807 ≡ 1473513 (mod 2430101).
• Alice gửi bản mã c = 1473513 đến Bob.
Giải Mã RSA
Bob có (p − 1)(q − 1) = 1222.1986 = 2426892, giải
ed ≡ 1 (mod (p − 1)(q − 1)), 94807 ≡ 1 (mod 2426892),
với d và thấy rằng d = 1051235.
Bob lấy bản mã c = 1473513 và tính

cd (mod N), 14735131051235 ≡ 1070777 (mod 2430101).

nguyên tố bí mật p và q. Mệnh đề 1.1.4 cho biết nếu Eve biết giá trị (p−1)(q−1),
thì bà có thể giải xe ≡ c (mod N), và dó đó có thể mã hóa những thông tin
được gửi cho Bob.
Khai triển hệ thức (p − 1)(q − 1) ta được

(p − 1)(q − 1) = pq − p − q + 1 = N − (p − q) + 1.

(1.4)

Bob đã công bố giá trị N, vì vậy Eve bây giờ đã biết N. Do đó, nếu Eve có thể
xác định giá trị của tổng p + q thì (1.4) sẽ cho bà biết giá trị (p − 1)(q − 1) có
thể giúp bà mã hóa những thông tin.
Thực tế, nếu Eve biết các giá trị p + q và pq, thì sẽ rất dễ để tính giá trị của
p và q. Bà chỉ cần sử dụng công thức bậc hai để tìm ra những nghiệm của đa
thức

X 2 − (p − q)X + pq,

vì phân tích đa thức thành nhân tử bằng (X − p)(X − q), nên các nghiệm của
nó là p và q. Do đó, khi Bob đưa ra giá trị N = pq thì sẽ chẳng dễ dàng cho
Eve khi tìm ra giá trị của (p − 1)(q − 1) hơn là khi tìm p và q.
Chúng ta minh họa bằng ví dụ sau. Giả sử Eve biết rằng:

N = pq = 66240912547 và (p − 1)(q − 1) = 66240396760.
Đầu tiên bà sử dụng (1.4) để tính

p + q = N + 1 − (p − 1)(q − 1) = 515788.
13



cách làm này, thì ông có thể chọn ngẫu nhiên những số cho tới khi ông thấy nó
là số nguyên tố. Chúng ta sẽ thảo luận về vấn đề khả năng số được chọn ngẫu
nhiên là số nguyên tố sau này, nhưng bây giờ thì ông đã có cơ hội tốt để thành
công. Do đó, những gì Bob thực sự cần là một cách hiệu quả để xác định một
số rất lớn là số nguyên tố.

14


Ví dụ, giả sử như Bob chọn số lớn có giá trị:

n = 31987937737479355332620068643713101490952335301
và ông muốn biết số n có là số nguyên tố hay không. Đầu tiên Bob tìm những
phép phân tích nhỏ nhưng ông lại thấy n không chia hết cho bất kì số nguyên
tố nào nhỏ hơn 1000000. Vì vậy, ông bắt đầu nghi ngờ liệu n là số nguyên tố
hay không. Tiếp theo, ông tính 2n−1 mod n và ông thấy rằng

2n−1 ≡ 1281265953551359064133601216247151836053160074 (mod n). (1.5)
Đồng dư thức (1.5) cho Bob biết rằng n là hợp số dù cho nó không cho ông bất
kỳ dấu hiệu nào về cách phân tích n. Tại sao? Xem lại định lý Fermat, nếu p
là số nguyên tố thì ap−1 ≡ 1 (mod p) (trừ trương hợp a chia hết cho p). Do đó,
nếu n là số nguyên tố, thì vế phải của (1.5) có thể đồng dư với 1, vì nếu không
đồng dư với 1 thì Bob kết luận n không là số nguyên tố.
Trước khi tiếp tục phần trước đây liên quan đến sự tìm kiếm của Bob về
những số nguyên tố lớn, chúng ta phát biểu phiên bản thuận tiện của Định lý
Fermat nhỏ, mà không có điều kiện nào ở a.
Định lí 1.3.1 (Đinh lý Fermat, phiên bản 2). Cho p là số nguyên tố. Khi đó

ap ≡ a (mod p) với mọi số nguyên a.


(cho tính hợp số) của n nếu

an ≡ a (mod n).

Mệnh đề 1.3.3. Cho p là số nguyên tố lẻ và viết:

p − 1 = 2k q với q lẻ.
Cho a là số bất kì không chia hết cho p, khi đó một trong hai điều kiện sau đây
là đúng:
(i) aq đồng dư với 1 modun p.
(ii) Một trong những aq , a2q , a4q , ..., a2

k−1

q

, đồng dư với 1 modun p.

Chứng minh. Định lý Fermat nhỏ cho ta biết rằng ap−1 ≡ 1 (mod p). Quan sát
dãy số:
k−1
k
aq , a2q , a4q , ..., a2 q , a2 q ,
ta biết rằng số cuối cùng trong dãy số là ap−1 , đồng dư với 1 modun p. Hơn nữa,
mỗi số trong dãy trên là bình phương của số trước. Do đó, một trong những
khả năng sau đây buộc phải xảy ra:
(i) Số đầu tiên trong dãy đồng dư với 1 modun p.
(ii) Vài số trong dãy không đồng dư với 1 modun p nhưng khi nó được bình
phương, nó sẽ đồng dư với 1 modun p. Nhưng số duy nhất thỏa mãn cả hai
điều kiện:

không? Để làm điều này, ông đã làm phương pháp kiểm tra Miller-Rabin sử
dụng một loạt những giá trị được lựa chọn ngẫu nhiên của a. Tại sao điều này
lại tốt hơn việc dùng phương pháp kiểm tra định lí Fermat nhỏ? Câu trả lời là
không có số nào giống như Carmichael cho phương pháp kiểm tra Miller-Rabin
và thực tế mỗi hợp số đều có rất nhiều chứng thực Miller-Rabin như được trình
bày ở mệnh đề sau đây.
17


Mệnh đề 1.3.5. Cho n là hợp số lẻ. Khi đó ít nhất 75% những số giữa 1 và

n − 1 là chứng thực cho n.
Chứng minh. Việc chứng minh này không khó, chúng ta sẽ không chứng minh
ở đây.
Bây giờ hãy xem xét những tìm kiếm của Bob để tìm những số nguyên tố
lớn. Ông lấy số nguyên tố n và thực hiện phương pháp kiểm tra Miller-Rabin
cho n với 10 giá trị khác nhau của a. Nếu bất kỳ giá trị a nào là phương pháp
chứng minh Miller-Rabin với n thì Bob suy ra n là hợp số. Mệnh đề 1.3.5 cho
thấy nếu n là hợp số thì mỗi lẫn Bob thử một giá trị cho a, ít nhất ông đã có
75% cơ hội chứng minh được nó. Vì Bob không tìm được chứng minh nào trong
10 lần thử đó, nên hợp lý khi kết luận rằng xác suất n là hợp số có ít nhất
(25%)10, xấp xỉ với 10−6. Và nếu không đủ thì Bob có thể sử dụng 100 giá trị
khác nhau của a và nếu không giá trị nào chứng minh n là hợp số thì xác suất

n là hợp số sẽ ít hơn (25%)100 ≈ 10−60.
Ví dụ 1.3.6. Chúng ta minh họa phương pháp kiểm tra Miller-Rabin với a = 2
và n = 561 trong đó, bạn có thể nhớ lại định nghĩa về số Carmichael.Ta phân
tích

n − 1 = 560 = 24.35


2321618441 ≡ 40063806 (mod 172947529),
2321618441 ≡ 2257065 (mod 172947529),
2321618441 ≡ 1 (mod 172947529).

Do đó, 23 là witness Miller-rabin và n thực sự là hợp số.

1.4

Thuật toán phép nhân tử hóa Pollard p-1

Chúng ta đã thấy là tương đối dễ để kiểm tra một số lớn liệu có phải là số
nguyên tố không. Điều này là tốt vì hệ thống mã hóa RSA cần những số nguyên
tố lớn để thực hiện.
Ngược lại, tính bảo mật của RSA dựa trên độ khó rõ ràng trong việc tính
toán với những số lớn. Nghiên cứu về phép nhân tử hóa đã có từ thời kỳ Hy
Lạp cổ đại nhưng nó chỉ dành cho máy tính khi mà mọi người bắt đầu phát
triển những thuật toán có khả năng phân tích những số lớn. Nghịch lý RSA là
để khiến RSA hoạt động hiệu quả hơn, chúng ta muốn dùng modun N = pq
càng nhỏ càng tốt. Mặt khác, nếu nếu đối phương có thể có phân tích N thì
thông tin được mã hóa của chúng ta sẽ không còn bảo mật. Do vậy rất quan
trọng khi hiểu được khó khăn như thế nào để phân tích những số lớn, và đặc
biệt là để hiểu được tiềm năng của những thuật toán khác nhau mà hiện nay
được dùng để phân tích thừa số.
Trong vài phần tiếp theo chúng ta sẽ thảo luận một cách chi tiết hơn về một
số phương pháp được biết đến để phân tích những số nguyên lớn.
19


Chúng ta bắt đầu với thuật toán có tên gọi phương pháp Pollard p − 1. Mặc

UCLN(an! − 1, N).
(Để đơn giản ta có thể lấy a = 2). Nếu UCLN bằng 1 thì ta tiếp tục giá trị tiếp
theo của n. Nếu UCLN bằng N thì ta thật không may mắn, nhưng một giá trị
a khác có thể sẽ đúng. Và nếu ta lấy số nằm trong khoảng từ 1 đến N thì ta
có thừa số không tầm thường của N và ta sẽ thực hiện được.
20


Nhận xét 1.4.1. Có hai nhận xét quan trọng cần làm trước khi chúng ta đưa ý
tưởng của Pollard vào thực hành. Vấn đề đầu tiên liên quan đến giá trị an! − 1.
Thậm chí với a = 2 và với những giá trị trung bình của n, cho n = 100 và sẽ
không khả thi để tính chính xác được an! − 1. Thực chất, số 2100! có hơn 10157
chữ số, con số mà lớn hơn số lượng các hạt cơ bản trong vũ trụ được biết đến!
May mắn là không cần phải tính toán nó một cách chính xác. Chúng ta chỉ
quan tâm đến UCLN của an! − 1 và N, vì vậy chỉ cần thoản mãn việc tính

an! − 1 (mod N).
sau đó thì lấy UCLN với N. Như vậy chúng ta chưa bao giờ phải làm việc với
các con số lớn hơn N.
Thứ hai, chúng ta thậm chí không cần tính số mũ n!. Thay vào đó, giả sử
rằng ta đã tính an! ở bước trước, chúng ta có thể tính giá trị tiếp theo như sau

a(n+1)! ≡ (an! )n+1 (mod N).
Điều này dẫn đến thuật toán được trình bày ở Bảng 1.3.
Đưa vào. Số nguyên N để phân tích.
1. Đặt a = 2 (hoặc một số giá trị khác thuận tiện).
2. Vòng lặp j = 2, 3, 4, ... lên đến một giới hạn nhất định.
3. Đặt a = aj mod n.
4. Tính d = UCLN(a − 1, N)†.
5. Nếu 1 < d < N thì thành công, trả lại d.

UCLN(211! − 1, 13927189) = 1,

UCLN(213! − 1, 13927189) = 1,

UCLN(214! − 1, 13927189) = 3823.

Dòng cuối cùng cho ta một thừa số không tầm thường p = 3823 của N. Thừa
số này là số nguyên tố, và thừa số q = N/p = 13927189/3823 = 3643 cũng là
số nguyên tố. Lý do số mũ 14! được làm trong ví dụ này là thừa số p − 1 phân
tích được thành tích của các số nguyên tố nhỏ,

p − 1 = 3822 = 2 · 3 · 72 · 13.
Các thừa số khác thỏa mãn p − 1 = 3642 = 2 · 3 · 607, mà không phải là tích
của các số nguyên tố nhỏ.

Ví dụ 1.4.3. Chúng ta trình bày một ví dụ khác sử dụng các số lớn. Cho
N = 168441398857. Khi đó

250! − 1 ≡ 114787431143 (mod N),

251! − 1 ≡ 36475745067 (mod N),

252! − 1 ≡ 67210629098 (mod N),

UCLN(250! − 1, N) = 1,

UCLN(251! − 1, N) = 1,

UCLN(252! − 1, N) = 1,



Ví dụ 1.5.1. Ta phân tích thừa số N = 25217 bằng cách đi tìm số nguyên b
sao cho N + b2 số chính phương:

25217 + 12 = 25218

không chính phương

25217 + 22 = 25221

không chính phương

25217 + 32 = 25226

không chính phương

25217 + 42 = 25233

không chính phương

25217 + 52 = 25242

không chính phương

25217 + 62 = 25218

không chính phương

25217 + 72 = 25266



không chính phương
không chính phương

3 · 203299 + 32 = 609906

không chính phương

3 · 203299 + 42 = 609913

không chính phương

3 · 203299 + 52 = 609922

3 · 203299 + 62 = 609933

không chính phương
không chính phương

3 · 203299 + 72 = 609946

Đã thấy! **chính phương**.

3 · 203299 + 82 = 609961 = 7812
Do đó

3 · 203299 = 7812 − 82 = (781 + 8)(781 − 8) = 789 · 773,

sau đó khi ta tính