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.
Trong thuật toán đợc trình bày ở hình 4.14, hai giá trị r bất kỳ
trong cùng một lớp tơng đơng sẽ dẫn tới cùng một giá trị y. Bây giờ
xét giá trị x thu đợc từ chơng trình con A khi đã biết y. Ta có:
[y]={y, wy}
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

cho từng số nguyên lẻ cho tới . Nếu n < 10
12
thì đây là một
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.
[ ]
n
Đầu vào: n và B
1. a=2
2. For j=2 to B do
a = a
j
mod n
3. d = UCLN(a-1,n)
4. if 1 < d < n then
d là một thừa số của n
else
không tìm đợc thừa số của n
(không thành công)
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)

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 nhng 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ỉ có các thừa
số nguyên tố bé. Trong khi phơng pháp p-1 phụ thuộc vào quan hệ

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
}là một cơ sở nhân tử. Giả sử c lớn hơn
B một chút (chẳng hạn C=B+10) và giả sử ta đã có C đồng d thức:

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
1
+a
2

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
bậc hai do Pomerance đa ra dùng các số nguyên dạng x
j
=j +
[ ]
n
,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
2
y
2
(mod n), song nó đợc thực hiện bằng các tính

n
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 nhất
những bài báo Hội nghị [DH 76] thực tế đã xuất hiện sớm hơn một
chút. Hệ mật RSA đợc Rivest, Shamis và Adleman [RSA 78] phát
minh. Hệ mật Rabin đợc mô tả trong [RA 79]: một hệ tơng tự với
phép giải mã không mập mờ đã đợc Willians tìm ra trong [Wi 80].
Bạn đọc nếu tham khảo [Di 92] là một bài báo tổng quát và mặt mã
khoá công khai của Diffie.

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 :
ở đây p
i
là các số nguyên tố khác nhau. Hãy chứng minh tỏ rằng
x 0 là một căn nguyên thuỷ theo modulo p khi và chỉ khi
x
(p-1)/p

1
(mod pq) khi và chỉ khi x
1
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 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
15061 12347 7817 7946 11675 13924 13892 18031
2620 6276 8500 201 8850 11178 16477 10161
3533 13842 7537 12259 18110 44 2364 15570
3460 9886 8687 4481 11231 7547 11383 17910
12867 13203 5102 4742 5053 15407 2976 9330
12192 56 2471 14334 841 13995 13297 8186
2430 9741 11675 242 6686 738 13874 8186

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
27486 9741 2149 29329 2149 5501 14015 30155
18154 22319 27705 20321 23254 13624 3249 5443
2149 16975 16087 146000 27705 19386 7325 26277
19554 23614 7553 4734 8091 23973 14015 107
3183 17347 25234 4595 21498 6360 19837 8463
6000 31280 29413 2066 369 23204 8425 7792
25973 4477 30989

=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
tính đợc ở bớc 3 của hình 4.16
thực tế là bản rõ x của Alice. Bởi vậy, Oscar có thể giải mã đợc thông
báo mà Alice đã gửi, ngay cả khi bản rõ đợc gửi qua hệ mật đợc coi
là an toàn.
b) Minh hoạ cách tấn công qua việc tính x theo phơng pháp
này nếu n = 18721,b
1

3
,
mà không cần phải phân tích bất cứ n
i
nào.
4.10. Bản rõ x đợc gọi là cố định nếu e
k
(x) = x. Hãy chứng tỏ rằng
đối với hệ mật RSA, số các bản rõ cố định x Z
n
*
bằng
Đầu vào : n, b
1
, b
2
, y
1
, y
2
1.
Tính c
1
= b
1
-1
mod b
2
2.
Tính c

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 thực hiện
việc phân tích thừa số trừ việc phân ra các luỹ thừa bậc hai. Hãy kiểm
tra chơng trình của bạn qua việc tính các ký hiệu Jacobi sau:
4.13. Hãy viết một chơng trình tính số các số giả nguyên tố Euler
theo các cơ sở 837, 851 và 1189.
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)
nhng
a
(n-1)/2
1 (mod p
2
p
3
p
s
)
nên











4.15. Giả sử ta có thuật toán Las-Vegas với xác suất sai .
a) Hãy chứng minh rằng, xác suất thành công lần đầu sau phép thử
thứ n là :
P
n
=
n-1
(1-)
b) Số phép thử trung bình để đạt thành công là :
(n ì p
n
)
Hãy chứng tỏ rằng giá trị này bằng 1/(1-)
c) Giả sử là một số dơng thực nhỏ hơn 1. Hãy chứng tỏ rằng số
các phép lặp cần thiết để giảm xác suất sai tối đa là:
4.16. Giả sử thiếu trần trọng, Bob đã để lộ số mũ giải mã của mình là
a = 14039 trong hệ mật RSA với khoa công khai n = 36581 và b =
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
(32767)
c) Xác định 4 bản giả mã có thể của bản mã y đã cho.
4.19. Hãy phân tích ra thừa số các số 262063 và 9420457 bằng ph-