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. 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
1
+r,n)=p hoặc q (thành
công)


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
1
và r
2
,
định nghĩa:
r
1
~ r
2
r
1
2
r
2
2
(mod n)

Dễ dàng thấy rằng r ~ r với mọi r, r
1
~ r
2
cũng có nghĩa là r


Nếu r=y thì thuật toán không thành công; trong khi nếu r=wy thì
thuật toán sẽ thành công. Vì r đợc chọn ngẫu nhiên, nên một giá trị
bất kỳ trong bốn giá trị có thể đều cùng khả năng. Ta kết luận rằng
xác suất thành công của thuật toán là 1/2.

Điều thú vị là hệ mật rabin là an toàn đối với phơng pháp tấn
công bản rõ chọn lọc, mhmg hệ này lại hoàn toàn không an toànđối
với phơng pháp tấn công bảm mã chọn lọc. Thuật toán ở hình 4.14,
phần dùng để chứng minh sự an toàn đối với phép tấn công bản rõ
chọn lọc cũng có thể đợc dùng để phá hệ mật Rabin khi thực hiện
tấn công bản mã chọn lọc!. Trong phơng pháp tấn công bản mã
chọn lọc, chơng trình con A đợc thay bằng thuật toán giải mã của
Bob. 4.8. Các thuật toán phân tích thừa số.
Đã có một khối lợng khổng lồ các tìa liệu về các thuật toán
phân tích thừa số và việc nghiên cứu kỹ lỡng sẽ đòi hỏi phải có một
cuốn sách dày hơn quyển sách này. ở đây chỉ cố gắng đa ra một cái
nhìn khái quát bao gồm việc thảo luận sơ lợc về các thuật toán phân
tichs thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế.
Ba thuật toán hiệu quả nhất trên các số thật lớn là sàng bậc hai, thuật
toán đờng cong elliptic và sàng trờng số. Các thuật toán nổi tiếng
khác (những thuật toán toán có trớc) bao gồm phơng pháp và
thuật toán p-1 của Pollard, thuật toán p+1 của Williams, thuật toán
liên phân số và dĩ nhiên cả những phép chia thử.

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)
a 2
B!
(mod n)
nên a 2
B!

) 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ó

phân tích n.

Ta sẽ minh hoạ bằng một ví dụ đã đợc dự tính kỹ lỡng.

Ví dụ 4.15
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

với 1 j C. Với mỗi j xét véctor :

a
j
= (
1j
mod 2,
2j
mod 2, . . .,
Bj
mod 2) (Z
2
)
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

1
, a
2
, . . .,
a
C
sao cho tổng theo modulo 2 là một vector toàn chứa số 0 chính là
bài toán tìm sự phụ thuộc tuyến tính (trên Z
2
) của các vector này. Với
C > B, sự phụ thuộc tuyến tính này nhất định phải tồn tại và ta có thể
dễ dàng tìm đợc bằng phơng pháp loại trừ Gaux. Lý do giải thích
tại sao lấy C > B+1 là do không có gì bảo đảm để một đồng d thức
cho trớc bất kỳ sẽ tạo đợc phân tích n. Khoảng 50% thuật toán cho
ra x y (mod n). Tuy nhiên nếu C > B+1 thì có thể nhận đợc một
vài đồng d thức nh vậy. (Nảy sinh từ các phụ thuộc tuyến tính khác
của các a
j
). Hy vọng là ít nhất một trong các đồng d thức kết quả sẽ
dẫn đến việc phân tích n.
Vấn đề còn lại là phải làm thế nào để nhận đợc các số 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

bậc hai do Pomerance đa ra dùng các số nguyên dạng x

2
(mod n), song nó đợc thực hiện bằng các tính
toán trên vành các số đại số.

4.8.3.Các thuật toán phân tích trên thực tế.
Thời gian chạy tiệm cận của các thuật toán sàng bậc hai,
đơng cong elliptic và sàng trờng số nh sau:

Sàng bậc hai O?????????????//
Đờng cong elliptic ??????????????
Sàng trờng số ?????????????????

trong đó O(1) là hàm của n, hàm này tiến tới 0 khi nặ và p là thừa
số nguyên tố nhỏ nhất của n.

Trong trờng hợp xấu nhất p ?????????, thời gian chạy tiệm
cận của các thuật toán đờng cong elliptic và sàng bậc hai cơ bản
nh nhau. Tuy nhiên trong trờng hợp này, phơng pháp sàng bậc hai
nói chung trội hơn phơng pháp đờng cong elliptic. Phơng pháp
đơng cong elliptic hiệu quả hơn nếu các thừa số nguyên tố của n có
kích thớc khác nhau. Một số rất lớn đã đợc phân tích bằng phơng
pháp đờng cong elliptic là tham số Fermat (2
2048
-1) (đợc Brent
thực hiện năm 1988) .

Để phân tích các modulo RSA (trong đó n=pq, p và q là các số
nguyên tố có cùng kích thớc), sàng bậc hai là một thuật toán thành
công nhất hiện nay. Sau đây là một số kết quả quan trọng. Vào năm
1983, thuật toán sàng bậc hai đã phân tích thành công một số có 69

ý 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.

Phép thử Solovay- Stassen lần đầu tiên mô tả trong [SS 77].
Phép thử Miller- Rabin đợc nêu trong[Mi 76] và [Ra 80]. Thảo luận
của chúng ta về các xác suất sai dựa trên các nhập xét của Brassard
và Bratly [BB 88A, 8.6] (cũng có thể trong[BBCGP 88]. Các cận tối
nhất hiện thời về xác suất sai của thuật toán Miller- Rabin có thể tìm
thấy trong [DLP 93].

Nội dung của phần 4.6 dựa trên quan điểm của Salomaa [SA
90, các trang 143-154]. Phép phân tích n với số mũ giải mã cho trớc
đợc nêu trong [DE 84]: các kết quả về thông tin riêng bị lộ bởi RSA
lấy từ [GMT 82].

Nh đã nói trên, đã có rất nguồn tài liệu về các thuật toán phân
tích. Pomerance [Po 90]là tổng quát về phếp phân tích. Lenstra và
Lenstra [LL 90] là một báo cáo hay là về các thuật toán lý thuyết nói
chung. Bressoud [Br 89] là một giáo trình sơ cấp về phép phân tích
thừa số và phép kiểm tra tính nguyên tố. Các giáo trinh về mật mã có
chú trọng tới lý thuyết số là các sách của Koblitz [Ko 87] và của
Kranakis [Kr 86]. Còn sách của Lenstra và Lenstra [LL 93] là một
chuyên thảo tốt về sàng trờng số.


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 :

=
=
n
1 i
1
e
i
p 1p

ở đây p
i

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

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
27486 9741 2149 29329 2149 5501 14015 30155
18154 22319 27705 20321 23254 13624 3249 5443

2
. Giả sử UCLN(b
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.


1
= y
1
c
1
(y
2
c
2
)
-1
mod n 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

1
, y
2
, y
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

UCLN(b-1, p-1) ì UCLN(b-1, p-1)
Chỉ dẫn: xét hệ hai phơng trình đồng d:
e
K
(x
1
) x (mod p), e
K
(x
2
) x (mod p).


















111111.11
1234567
,
1987
20964


??


a


n


??????

?? ??
?? không bậc hai theo modulo p . (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

-1 (mod n)
nhng
a
(n-1)/2
1 (mod p
2

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à:



=1n







2
log
2
log


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