Hình 4.14. Phân tích modulus của rabin với một chương trình
con giải mã cho trước.
Bởi vậy giá trị x sẽ thu được ở bước 3. Tiếp theo xét bước 4. Nhận
thấy rằng x
1
2
= r
2
(mod n). Điều đó dẫn tới x
1
≡ ±r (mod n) hoặc x
1
≡
±wr (mod n), trong đó w là một trong các căn bậc hai không tầm
thường của 1 modulo n. Trong trường hợp thứ hai ta có :
n(x
1
-r

)(x
1
+r)
song n không phải là ước của một thừa số nào ở vế phải. Bởi vậy,
việc tính UCLN(x
1
+r,n)(hoặc UCLN(x
1
-r, n)) phải dẫn tới hoặc p
hoặc q, và như vậy phép phân tích n được hoàn thành.
Ta sẽ tính xác suất thành công của thuật toán này trên tất cả
(n-1) phép chọn ngẫu nhiên r. Với hai thặng dư khác không r

2
~ r
3
thì r
1
~ r
3
. Điều đó cho ta thấy rằng quan hệ ~ là một
quan hệ tương đương. Các lớp tương đương của Z
n
\{0} đều có bốn
phần tử, lớp tương đương chứa r là tập
[r] = {±r, ±wr (mod n)}
trong đó w là căn bậc hai không tầm thường của 1 modulo n.
1. Chọn một số ngẫu nhiên r , 1≤ r ≤ n-1
2. Tính y = r
2 -
B
2
/4 mod n
3. Gọi chương trình con A(y) để tìm bản giải
mã x
4. Tính x
1
= x+B/2
5. If x
1
≡ ± r (mod n) then quit (không thành
công)
Else UCLN(x

liên phân số và dĩ nhiên cả những phép chia thử.
Trong toàn bộ phần này, xchúng ta cỏìng số nguyên n cần
phân tích ra thừa số là một số lẻ. Phép chia thử bao gồm việc chia n
cho từng số nguyên lẻ cho tới . Nếu n < 10
12
thì đây là một
[ ]
n
ph ng pháp phân tích th a s h p lý m t cách ho n h o, tuy ươ ừ ố ợ ộ à ả
nhiên v i n l n h n nói chung ta ph i dùng các k thu t tinh t ớ ớ ơ ả ỹ ậ ế
h n.ơ
4.8.1. Phương pháp p-1
Thuật toán p-1 của Pollar (đưa ra vào năm 1947) là một thí dụ
về một thuật toán đơn giản đơn khi được áp dụng với các số nguyên
lớn. Thuật toán này (trình bày trên hình 4.15) có hai đầu vào: số
nguyên lẻ n cần được phân tích và một cận B. Có thể mô tả thuật
toán như sau:
Hình 4.15. Thuật toán phân tích thừa số p-1.
Giả sử p là ước mhuyên tố của n và q ≤ B , với mỗi mũ
nguyên tố p(p-1). Khi đó
(p-1)B!
cu i vòng l p for (b c 2)ở ố ặ ướ
a ≡ 2
B!
(mod n)
nên a ≡ 2
B!
(mod p)
vì pn. nên theo định ý Fermat ta có :


). Nếu B là O((log n)
i
)
với một số nguyên i xác định nào đó thì thuật toán thực sự là thuật
toán thời gian đa thức, tuy nhiên với phép chọn B như vậy, xác suất
thành công sẽ rất nhỏ. Mặt khác, nếu tăng kích thước của B lên thật
lớn (chẳng hạn tới ?????????????? ) thì thuật toán sẽ thành công
nhưng nó sẽ không thực hiện nhanh hơn phép chia thử.
Như vậy, điểm bất lợi của thuật toán này là nó yêu cầu n phải
có ước nguyên tố p sao cho (p-1) chỉ các thừa số nguyên tố bé. Ta có
thể dễ dàng xây dựng được hệ mật RSA với modulus n= pq hạn chế
được việc phân tích theo phương pháp này. Trước tiên tìm một số
nguyên tố lớn p
1
sao cho p= 2p
1
+1 cũng là một số nguyên tố và một
số nguyên tố lớn q
1
sao cho q= 2q
1
+1 cũng là một số nguyên tố (nhờ
dùng một trong các thuật toán kiểm tra tính nguyên tố Monte-Carlo
nêu trong phần 4.5). Khi đó modulo của RSA n= pq sẽ chống được
cách phân tích theo phương pháp p-1.
Thuật toán đường cong elliptic mạnh hơn (được Lenstra xây
dựng vào những năm 1980) trên thực tế là sự tổng quát hoá của
phương pháp p-1. Ta sẽ không thảo luận về lý thuyết ở đây mà chỉ
nhấn mạnh rằng, thành công của phương pháp đường cong elliptic
tuỳ thuộc vào tình huống tương tự : một số nguyên “gần với” p chỉ

Gi s n=15770708441(giá tr n n y ã dùng trong ví d ả ử ị à đ ụ
4.14). Gi s b = {2,3,5,7,11,13}. Xét ba ng th c sau:ả ử đồ ứ
8340934156
2
≡ 3 × 7 (mod n)
12044942944
2
≡ 1 × 7 × 13 (mod n)
2773700011
2
=2 × 3 × 13 (mod n)
Nếu lấy tích của ba đồng dư thức trên:
(8340934156 × 2044942944×2773700011)
2
≡(2× 3× 7× 13)
2
(mod n)
Rút gọn các biểu thức bên trong các dấu ngặc theo modulo n, ta có:
9503435785
2
≡ 546
2
(mod n)
Sau đó tính:
UCLN(9503435785-546, 15770708441)=115759
Ta thấy 115759 là một thừa số của n.
Giả sử B = {p
1
, . . . .p
B

)
B
Nếu có thể tìm được một tập con các a
j
sao cho tổng theo modulo 2
là vector (0,. . ., 0) thì tích của các x
j
tương ứng sẽ sử dụng mỗi nhân
tử trong B một số chẵn lần.
Ta s minh ho b ng cách tr l i ví d 4.15. Trong tr ng ẽ ạ ằ ở ạ ụ ườ
h p n y n u C < B, v n tìm c s ph thu c tuy n tính.ợ à ế ẫ đượ ự ụ ộ ế
Ví dụ 4.15 (tiếp)
Cho 3 vector a
1
, a
2
, a
3
:
a
1
=(0, 1, 0, 1, 0, 0)
a
2
=(1, 0, 0, 1, 0, 1)
a
3
= (1, 1, 0, 0, 0, 1)
Dễ dàng thấy rằng:
a

nguyên x
j
mà các giá trị x
j
2
mod n có thể phân tích hoàn toàn trên cơ
sở b. Một vài phương pháp có thể thực hiện được điều đó. Biện pháp
sàng
[ ]
n
bậc hai do Pomerance đưa ra dùng các số nguyên dạng x
j
=j +
,j=1,2 Tên “sàng bậc hai” lấy từ thủ tục sàng (không mô tả ở đây)
dùng để xác định các x
j
phân tích được trên b.
ở đây dĩ nhiên là một sự thoả hiệp: nếu B = | B | là một số lớn
thì thích hợp hơn cả là nên phân tích số nguyên x
j
trên b. Tuy nhiên
khi B càng lớn thì ta càng phải gom nhiều đồng dư thức hơn trước
khi có thể tìm được một quan hệ phụ thuộc. Lựa chọn tối ưu cho B
xấp xỉ bằng
??????????????????
và điều này dẫn đến thời gian thực hiện cỡ
??????????????????????????
Sàng trường số là thuật toán phân tích mới hơn (từ cuối những
năm 80) Thuật toán này cũng phân tích n bằng cách xây dựng một
đồng dư thức x

251
-1 (do Davis,
Holdredye v Simmons th c hi n). Quá trình n y ti p t c trong à ự ệ à ế ụ
nh ng n m 80 v n n m 1989 ã có th phân tích c các sữ ă à đế ă đ ể đượ ố
có t i 106 ch s theo ph ng pháp n y( do Lenstra v Manasse ớ ữ ố ươ à à
th c hi n) nh phân b các phép tính cho h ng tr m tr m l m ự ệ ờ ố à ă ạ à
vi c tách bi t (ng i ta g i ph ng pháp n y l “phân tích th a ệ ệ ườ ọ ươ à à ừ
s b ng th i n t ”). ố ằ ư đ ệ ử
G n ây h n, 4/1994 Atkins, Graff, Lenstra v Leyland ã ầ đ ơ à đ
phân tích c m t s 129 ch s ( c g i l RSA-129) nh sđượ ộ ố ữ ố đượ ọ à ờ ử
d ng s ng b c hai (các s RSA-100, RSA-110, ,RSA-500 l m t ụ à ậ ố à ộ
danh sách các modulo RSA c công b trên internet nh l s đượ ố ư à ự
thách cho các thu t toán phân tích. M i m t s RSA-d l m t đố ậ ỗ ộ ố à ộ
s d ch s , s n y l tích c a hai s nguyên t có kích th c ố ữ ố ố à à ủ ố ố ướ
x p x nhau). Vi c phân tích s RSA-129 c n h ng tr m tính toánấ ỉ ệ ố ầ à ă
v i máy tính 5000 MIPS (tri u l nh/s) c th c hi n b i 600 ớ ệ ệ đượ ự ệ ở
nh nghiên c u trên to n th gi i.à ứ à ế ớ
S ng tr ng s l m t thu t toán m i nh t trong ba thu t à ườ ố à ộ ậ ớ ấ ậ
toán toán. Nó có v có ti m n ng l n do th i gian ch y ti m c n ẻ ề ă ớ ờ ạ ệ ậ
c a nó nhanh h pn c hai thu t toán trên. Thu t toán n y hi n v nủ ơ ả ậ ậ à ệ ẫ
còn trong th i kì nghiên c u, tuy nhiên ng i ta ã d oán l ờ ứ ườ đ ự đ à
s ng tr ng s ph i ch ng t l nhanh h n v i các s có trên à ườ ố ả ứ ỏ à ơ ớ ố
125-130 ch s . N m 1990, Lenstra, Manase v Pollaid ã dùng ữ ố ă à đ
s ng tr ng s phân tích (2à ườ ố để
512
- 1) th nh ba s nguyên t có 7, à ố ố
49 v 99 ch s .à ữ ố
4.9. chú giải và tai liêu dẫn
ý tưởng về mật mã khoá công khai đã được Diffie và Hellman
nêu ra vào 1976. Mặc dù [HD 76A] là tài liệu được trích dẫn nhiều

a) 17
-1
mod 101
b) 357
-1
mod 1234
c) 3125
-1
mod 9987
4.2. Giải hệ phương trình đồng dư sau:
x ≡ 12 (mod 25)
x ≡ 9 (mod 26)
x ≡ 23 (mod 27)
4.3. Giải hệ phương trình đồng dư sau
13x ≡ 4 (mod 99)
15x ≡ 56 (mod 101)
g i ý: tr c tiên hãy dùng thu t toán Euclide m rông r i áp d ng ợ ướ ậ ỡ ồ ụ
nh lý ph n d c a China.đị ầ ư ủ
4.4. Ta nghiên cứu một số tính chất của các căn nguyên thuỷ
a) 97 là một số nguyen tố. Hãy chứng minh rằng x ≠ 0 là một
căn nguyên thuỷ theo modulo 97 khi và chỉ khi
x
32
≡ 1 (mod 97) và x
48
≡ 1 (mod 97)
b) Hãy dùng phương pháp này để tìm căn nguyên thuỷ nhỏ
nhất theo modulo 97.
c) Giả sử p là một số nguyên tố và p-1 có phần tích ra các mũ
nguyên tố sau :

≡ x
1
(mod p) và x
1
≡ x
1
(mod q). Điều này rút ra từ định lý phần dư China.
4.6. Hai ví d v b n mã RSA c nêu các b ng 4.1 v ụ ề ả đượ ở ả à
b ng 4.2. Nhi m v c a b n l ph i gi i mã chúng. Các tham s ả ệ ụ ủ ạ à ả ả ố
công khai c a h th ng l n =18923 v b = 1261 (b ng 4.1) v n = ủ ệ ố à à ả à
31313, b = 4913 (v i b ng 4.2). Phép gi i m cáo th th c hi n ớ ả ả ả ể ự ệ
nh sau. Tr c h t h phân tích n ( i u n y khá d vì n quá ư ướ ế ỹ đ ề à ể
nh ). Sau ó tính s m a t ỏ đ ố ũ ừ φ(n) v cu i cùng s gi i mã b n à ố ẽ ả ả
∏
=
=−
n
1 i
1
e
i
p 1p
mã. Hãy dùng thu t toán bình ph ng v nhân l y lu th a ậ ươ à để ấ ỹ ừ
theo modulo n.
B ng 4.1 B n mã RSAả ả
12423 11524 7243 7459 14303 6127 10964 16399
9792 13692 14407 18817 18830 13556 3159 16647
5300 13951 91 8986 8007 13167 10022 17213
2264 9553 18194 3830 2664 13998 12501 18873
13236 5300 13951 8850 12129 6091 18110 3332

DOG  3 × 26
2
+ 14 × 26 +6 = 2398
CAT  2 × 26
2
+ 0 × 26 + 19 = 1371
ZZ  25 × 26
2
+ 25 × 26 + 25 = 17575
Bước cuối cùng trong chương trình của bạn là làm ngược lại
quá trình trên.
Bản rõ đầu lấy trong cuốn “The diary of Samuel Mảchbankls”
của Robertson Davies, 1947. Bản rõ thứ hai lấy từ cuốn “Lake
Wobegon Days” của Garrison Keillor, 1985.
4.7. Bài tập này mô tả cái được gọi là sự trục trặc về thủ tục. Đây
là một ví dụ về một bản mà có thể bị đối phương giải mà không cần
phải xác định khoá nếu dùng thiêú thận trọng hệ mật ( vì đối phương
không phải xác định
B ng 4.2 B n mã RSAả ả
6340 8309 14010 8936 27358 25023 16481 25809
23316 7135 24996 30596 27570 26486 30388 9395
27584 14999 4517 12146 29421 26439 1606 17881
25774 7647 23901 7372 25774 18436 12056 13547
7908 8635 2149 1908 22076 7372 8686 1307
4082 11803 5314 107 7359 22470 7372 22827
15698 30317 4685 14696 30388 8671 29956 15705
1417 26905 25809 28347 26277 7879 20240 21519
12437 1108 27106 18743 24144 10685 25234 30155
23055 8267 9917 7994 9694 2149 10042 27705
15930 29748 8635 23645 11738 24591 20240 27212

1
,b
2
) =1.
Bây giờ ta hãy xét tình hình xảy ra nếu Alice mã hoá cùng một bản
rõ x để gửi cho cả Bob và Charlie. Như vậy, Alice sẽ tính y
1
=x
b
1

mod n và y
2
=x
b
2
mod n và rồi gửi y
1
cho Bob và gửi y
2
cho Charlie.
Giả sử Oscar thu được y
1
và y
2
và thực hiện các tính toán được nếu ở
hình 4.16 sau.
Hình 4.16. trục trặc thủ tục modulo chung.
a) Hãy chứng tỏ rằng giá trị x
1

2
= (c
1
b
1
- 1)/b
2
3. Tính x
1
= y
1
c
1
(y
2
c
2
)
-1
mod n
4.9 Đây lại là một ví dụ khác về sự trục trặc thủ tục xoay quanh hệ
mật RSA. Giả sử có ba người dùng trong mạng là Bob, Bar và Bert,
họ đều có số mũ mã hoá b =3. Các modulo tương ứng n
1
, n
2
, n
3
. Giả
sử Alice mã hoá cùng một bản rõ x để gửi cho Bob, Bar và Bert. Khi

1
) ≡ x (mod p), e
K
(x
2
) ≡ x (mod p).
4.11. Giả sử A là một thuật toán tất định có đầu vào là một RSA
modulo n và bản mã y. A sẽ hoặc giải mã y hoặc không có lời giải.
Giả sử rằng có ε × n bản mã mà có thể giải, hay chỉ rõ cách dùng A
làm một chương con trong thuật toán giải mã Las Vegas có xác suất
không thành công là ε.
Chỉ dẫn: sử dung tính chất nhân của RSA là
e
K
(x
1
) e
K
(x
2
) = e
K
(x
1
x
2
)
trong đó tất cả các phép toán số học là theo modulo n.
4.12. Viết một chương trình để đánh giá các ký hiệu Jacobi bằng
cách dùng bốn tính chất được nêu ở phần 4.5. Chương trình không

theo các cơ sở 837, 851 và 1189.
4.14. Mục đích của bài tập này là phải chứng tỏ rằng: xác suất của
kiểm tra tính nguyên tố Solovay- Strassen nhiều nhất là 1/2 . Giả sử
Z
n
*
là nhóm các phần tử khả nghịch theo modulo n. Ta định nghĩa:
a) không bậc hai theo modulo p
1
. (Chú ý rằng, a như vậy tồn tại theo
định lý phần dư China). Hãy chứng minh rằng:
≡ -1 (mod n)
nhưng
a
(n-1)/2
≡ 1 (mod p
2
p
3
…p
s


n
a
∑
∞
=
1n
.






ε
δ
2
log
2
log
4679. áp dụng dụng thuật toán sác suất để phân tích n theo thông tin
được biết này. Hãy kiểm tra thuật toan của bạn với các phép chọn
ngẫu nhiên w = 9983 và w = 13461. Hãy chỉ ra tất cả các tính toán .
4.17. Hãy chứng minh các phương trình 4.1 và 4.2 có liên quan đến
các hàm half và parity.
4.18. giả sử p = 199, q = 211 và b = 1357 trong hệ mật Rabin. Hãy
thực hiện tính toán sau:
a) Xác định 4 căn bậc hai của modulo n, trong đó n =pq.
b) Tính phép mã y = e
k