Xét ký hiệu Jacobi . Phân tích luỹ thừa nguyên tố của
9975 là: 9975=3 x 5
2
x 7 x 19. Bởi vậy ta có:
=
=(-1)(-1)
2
(-1)(-1)
= -1.
Giả sử n > 1 là một số lẻ. Nếu n là một số nguyên tố thì
a
(n-1)/2
(mod n) với a bất kỳ. Mặt khác nếu n là một hợp số thì đồng d
thức trên có thể đúng hoặc không. Nếu phơng trình đó vẫn đúng thì a
đợc gọi
là số giả nguyên tố Euler theo cơ số n. Ví dụ: 10 là số giả nguyên tố
Euler
theo cơ số 91 vì :
= -1 = 10
45
mod 91
Tuy nhiên có thể chứng tỏ rằng, với một hợp số lẻ n bất kỳ, sẽ
cóp nhiều nhất một nửa các số nguyên a (sao cho 1 a n-1) là các số
giả nguyên tố Euler cơ số n (xem các bài tập). Điều đó chứng tỏ rằng,
việc kiểm tra tính nguyên tố theo thuật toán Soloway-Strasson đợc nêu
ở hình 4.7 là thuật toán Monte-Carlo định hớng cóvới xác xuất sai
tối đa là 1/2.
Đến đây vẫn cha xác định rõ thuật toán ttrên có theo thời gian đa thức
hay không.
Ta đã biết cách đánh giá a
(n-1)/2
(mod n) trong thời gian đa thức
O((log n)
3
), tuy nhiên cần phải làm thế nào để tính các ký hiệu Jacobi
một cách có hiệu quả. Vì ký hiệu Jacobi đợc xác định theo các thừa số
trong phân tích của n. Tuy nhiên nếu có thể phân tích đợc n thì ta đã
=
19
6278
7
6278
5
6278
3
6278
9975
6278
2
19
8
7
6
5
3
3
2
2
91
10
n
a
n
a
biết nó có phải là số nguyên tố hay không, bởi vậy cách làm này sẽ
dẫn tới một vòng luẩn quẩn.
Hình 4.7. Thuật toán kiểm tra tính nguyên tố Solova-Strassen với số
nguyên lẻ n.
1. Chọn một số nguyên ngẫu nhiên a, 1 a n-1
2. Nếu a
(n-1)/2
(mod n) thì
Trả lời n là số nguyên tố
Nếu không
Trả lời n là một hợp số
Rất may là có thể đánh giá ký hiệu Jacobi mà không cần phải
phân tích n nhờ sử dụng một số kết quả của lý thuyết số, trong đó kết
quả quan trọng nhất là tính chất 4 (tổng quát hoá luật tơng hỗ bậc
hai ).
Ta sẽ liệt kê mà không chứng minh các tính chất này.
1. Nếu n là một số nguyên tố lẻ và m
1
m
2
(mod n) thì:
=
2. Nếu n là một số nguyên lẻ thì
1 nếu n 1 (mod 8)
= -1 nếu n 3 (mod 8)
3. Nếu n là một số nguyên lẻ thì
Đặc biệt nếu m=2
k
t với t là một số lẻ thì:
n
a
n
1
m
n
2
m
n
2
=
n
m
n
m
n
mm
2121
=
n
t
n
2
n
m
k
4. Giả sử m và n là các số nguyên lẻ, khi đó:
=
ví dụ
Để minh hoạ cho việc áp dụng các tính chất trên , ta sẽ đánh giá
kí
hiệu Jacobi nh trong bảng dới đây. Cần chú ý là trong ví dụ
này, ta đã sử dụng liên tiếp các tính chất4, 1,3 ,và 2.
Nói chung, bằng cách áp dụng 4 tính chất trên, có thể tính
toánkí
hiệu Jacobi trong thời gian đa thức. Các phép tính số học dùng ở đây
chỉ là rút gọn theo modulo và phân tích ra các luỹ thừa của thuật toán
đợc biểu diễn dới dạng nhị phân thì việc phân tích ra các luỹ thừa của
hai số chính là việc xác định số các số 0 tiếp sau. Bởi vậy, độ phức tạp
của thuật toán đợc xác định bởi số các phép rút gọn theo modulo cần
tiến hành. Không khó khăn lắm có thể chứng tỏ rằng, cần thực hiện
nhiều nhất là.
n
2
lại còn hợp trường các trong
m
n
4) (mod 3nm nếu
m
n
9283
7411
n
m
=
7411
9283
9283
7411
theo tính chất 4
=
7411
1872
theo tính chất 1
. =
7411
117
4
7411
2
theo tính chất 3
=
7411
117
theo tính chất 2
=
117
7411
theo tính chất 4
=
177
40
theo tính chất 1
=
117
5
3
117
2
theo tính chất 3
=
117
5
theo tính chất 2
=
5
117
theo tính chất 4
=
5
2
theo tính chất 1
= -1 theo tính chất 2
O(log n) phép rút gọn theo modulo. Mỗi phép có thể thực hiện trong
thời gian O((log n)
2
). Điều đó chứng tỏ rằng, độ phức tạp là O((log n)
3
)
là đa thức theo log n. Thực ra bằng các phân tích chính xác hơn, có thể
chứng tỏ răng, độ phức tạp chỉ cỡ O((log n)
2
).
Giả sử ta đã tạo đợc một số ngẫu nhiên n và đã kiểm tra tính
nguyên tố của nó theo thuật toán Soloway- Strasen. Nếu chạy thuật
toán m lần thì câu trả lời n là một số nguyên tố sẽ có mức độ tin cậy
nh thế nào? Quả là liều lĩnh nếu coi răng, xác suất này là 1-2
-m
. Kết
luận này thờng đợc nêu trong các giáo trình và bài báo kĩ thuật, tuy
nhiên ta không thể dẫn ra theo các số liệu cho trớc.
Cần phải thận trọng hơn khi sự dụng các tính toán xác suất. Ta sẽ
định nghĩa các biến ngẫu nhiên sau:
a- Chỉ sự kiện số nguyên lẻ n có kích thớc đã định là một
hợp số.
b- Chỉ sự kiện thuật toán trả lời n là số nguyên tố m lần
liên tiếp .
Điều chắc chắn là prob(b| a)2
-m
. Tuy nhiên xác suất mà ta thực sự quan
tâm là prob(a/b), xác suất này thờng không giống nh prob(b/a).
Có thể tính prob(a/b) bằng định lý Bayes (định lý2.1). Trớc hết cần
phải biết prob(a). Giả sử N n 2N. áp dụng định lý về số nguyên
tố: các số nguyên tố(lẻ) giửa N và 2N xấp xỉ bằng:
2N/ln 2N N/ln N N/ ln N
` n/ln n
Vì có N/2 n/2 số nguyên tố lẻ giửa N và 2N, ta sẽ dùng ớc lợng
Prob(a) 1 2/ln n
Sau đó có thể tính toán nh sau:
prob(a| b) =
????
Chú ý rằng trong tính toán trên ? chỉ sự kiện số nguyên lẻ ngẫu nhiên
n là một số nguyên tố.
Khá thú vị nếu so sánh hai hàm sau của m
????/
Giả sự n 2
256
e
177
(đây là kích thớc của các số nguyên tố sự dụng
trong hệ mặt RSA). Khi đó hàm đầu tiên xấp xỉ bằng????. Ta sẽ lập
bảng cho hai hàm ứng với một số giá trị của m (xem hình4.8).
Hình 4.8. Các xác suất sai đối với phép kiểm tra Solovay- Strasen
M 2
-m
1 0,500 0,978
2 0250, 0,956
5 0,312.10
-1
0,732
10 0,977.10
-3
0,787.10
-
20 0,954.10
-6
0,834.10
-4
30 0,930.10
-9
0,815.10
-7
50 0,888.10
-15
0,777.10
-13
100 0,789.10
-30
0,690.10
-28
Mặc dù????? tiến tới o khá nhanh theo hàm mũ nhng vẫn không tiến
nhanh bằng 2
-m
. Tuy nhiên, nếu lấy m vào cỡ 50 hoặc 100 thì các xác
suất sai đó cùng qui về một lợng rất nhỏ.
prob(b)
prob(a)a)prob(b
prob(b)
prob(a)a)prob(b
Phần này sẽ kết thúc bằng một thuật toán Monte- Carlo khác cho
bài toán hợp số, đó là thuật toán Miller- Rabin (M-R) (đợc coi là một
phép kiểm tra giả nguyên tố mạnh). Thuật toán đợc mô tả trong hình
4.9. Đây lá một thuật toán với thời gian đa thức: độ phức tạp của nó cỡ
O((log n)
3
) tơng tự nh thuật toán S-S Thực ra trong thức tế thuật toán
M-R thực hiện tốt hơn thuật toán S-S.
Bây giờ chúng ta sẽ chỉ ra rằng thuật toán này không thể lời n là một
hợp số
nếu n là số nguyên tố, tức nó là một thuật toán định hớng có .
Định lý 4.10
thuật toán Miller Rabin về các hợp số là thuật toán monte-carlo
định hớng có
Hình 4.9 Thuật toán kiểm tra tính nguyên tố Miller-rabin với số
nguyên lẻ n
1. Viết n-1=2
k
m, trong đó m là một số lẻ
2. Chọn số nguyên ngẫu nhiên a, 1 a (n-1 )
3. Tính b=a
m
mod n
4. IF b1 (mod n) then
Trả lời n là số nguyên tố và quit
5. For I=0 to k-1 do
6. IF b-1 (mod n) then
Trả lời n là số nguyên tố và quit
Else b=b
2
mod n
7.Trả lời n là hợp số
Chứng minh:
Ta sẽ chứng minh bằng cách giả sử thuật toán trả lời n là hợp
số với số nguyên tố n nào đó và nhân đợc mâu thuẫt. Vì thuật toán trả
lời nlà hợ số nên chắc chắn là a
m
1(mod n). Bây giờ xét dãy các
giá trị b đợc kiểm tra trong bớc 2 của thuật toán .Vì b đợc bình phơng
trong mỗi phép lặp của vòng For nên ta sẽ kiểm tra các giá trị a
m
, a
2m
,,a
2k-1m
. Vì thuật toán trả lời n là hợp số nên suy ra:
A
2m
-1 (mod n)
Với 0 i k-1
Bây giờ sử dụng giả thiết n là số nguyên tố. Theo định lý Ferma
(hệ quả 4.6) ta có
A
2km
1 (mod 1)
Vì n-1 = 2
k
m. Khi đó a
2k-1m
là căn bậc hai của một modulo n = 1 mod
n. Điều này có thể thấy rõ nh sau: x là căn bậc hai của 1 theo modulo n
khi và chỉ khi
n(x-1)(x+1)
Vì n là một số nguyên tố nên hoặc n(x-1)(tức là x1 modun) hoặc
n(x+1) (tức là x-1 modun)
Ta đã có
a
2k-1m
-1(mod n)
bởi vậy ta phải có:
a
2k-1m
1(mod n)
Khi đó a
2k-2m
phải là căn bậc hai của 1. Bằng lập luận tơng tự:
A
2k-1m
1(mod n)
điều này là mâu thuẫn, bởi vậy trong trờng hợp này thuật toán phải có
câu trả lời n là số nguyên tố.
Còn một vấn đề cha cha đợc xem xét là xác xuất sai của thuật toán
M-R. Mặc dù không chứng minh ở đây nhng có thể chứng tỏ đợc rằng
xác xuất này nhiều nhất là 1/4.
4.6 Các phơng pháp tấn công hệ mật rsa
Trong phần này ta sẽ lu tâm đến vấn đề:Liệu có các phơng pháp
tấn công RSA khác với phơng pháp phân tích n không ? trớc tiên ta
thấy rằng thám mã chỉ cần tính đợc (n) là đủ. Nếu đã biết n và (n)
và n là tích của 2 số nguyên tố p và q thì có thể dễ dàng phân tích đợc
n bằng cách giải 2 phơng trình sau để tìm hai số p và q cha biết:
n=pq
(n)=(p-1)(q-1)
Nếu thay q=n/p và phơng trình thứ 2 thì ta sẽ thu đợc phơng trình bậc
2 của biến cha biết p :
P
2
-(n-(n) + 1)p + n=0
Hai nghiệm của phơng trình này là p và q là các nhân tữ của n.
Bởi vậy thám mã biết đợc (n) thì anh ta có thể phân tích đợc n và phá
đợc hệ mật.Nói cách khác, việc tính (n) không dễ hơn việc phân tích
n.Sau đây là một ví dụ dụ minh hoạ :
Ví dụ 4.9
Giả sử thám mã đả biết rằng n=84773093 và (n)= 4754668.
Thông tin này sẽ dẫn tới phơng trình:
P
2
-18426p+84773093=0
Giải phơng trình này thu đợc hai nghiệm 9539 và 8887.Đây là
hai thừa số của n.
4.6.1 Số mũ giải mã
Bây giờ chúng ta sẽ chứng minh một kết quả rất thú vị là một
thuật toán bất kỳ để tính số mũ giải mã a đều có thể đợc dùng nh một
chơng trình con (hay một điều kiện )trong thuật toán xác suất phân
tích n .Bởi vậy việc tính a sẽ không dễ hơn việc phân tích n.Tuy nhiên,
có một điều không ngoài quy luật là ta vẫn có thể phá hệ mật mà
không cần tính a.
Kết quả này có ý nghĩa nhiều hơn về mặt lý thuyết .Nó cho thấy rằng
nếu a bị lộ thì giá trị m cũng không còn khó phân tích nữa.Nếu điều
này xẩy ra thì việc Bob chọn một số mũ mới cũng chẳng có ý nghĩa;
Điều cần thiết là Bob phải chọn lại n.
Thuật toán mà ta sẽ mô tả là một thuật toán xác suất kiểu las
vegas.Sau đây là định nghĩa của kiểu thuật toán này.
Định nghĩa 4.5
Giả sử 0 1 là một số thực.Thuật toán las vegas là một thuật
toán xác suất cao cho với một trờng hợp bất kỳ của bài toán I, thuật
toán có thể không cho kết quả với một xác suất nào đó (chẳng hạn
thuật toán có thể kết thúc với thông báo không trả lời).Tuy nhiên,
nếu thuật toán cho lời giải thì lời giải này là đúng .
Nhân xét:Thuật toán las vegas có thể không cho câu trả lời nhng
một câu trả lời bất kỳ mà thuật toán cho là đều là câu tra lời đúng.Ng-
ợc lại, thuật toán monte-carlo luôn luôn cho câu trả lời nhng câu trà lời
này có thể là sai.
Nếu ta có một thuật toán las vegas để giải một bài toán thì đơn
giản ta chỉ chạy lặp đi lặp lại thuật toán này cho tới khi nó tìm ra một
câu trả lời.Xác suất để thuật toán không trả lời sau m lần liên tiếp là
m
.Số lần chạy trung bình để thu đợc câu tra lời thực tế là 1/ (Xem các
bài tập ).
Giả sử A là một thuật toán giả định tính số mũ giải mã a từ b. Ta sẽ
mô tả một thuật toán las vegas dùng A nh một chơng trình giả định
(oracle) con.Thuật toán sẻ phân tích n với xác suất tối thiểu là 1/2.Bởi
vậy nếu thuật toán chạy m lần thì n sẽ đợc phân tích với xác suất tối
thiểu là 1-1/2
m
.
Thuật toán đợc xây dựng trên cơ sở một số nguyên tố nhất định
liên quan tới các căn bậc 2 của một theo modulo n, trong đó n=pq là
tích của hai số nguyên tố lẻ phân biệt ta biết rằng phơng trình đồng d
X
2
1( mod p) có hai nghiệm theo modulo p là X=1 mod p .Tơng tự,
phơng trình đồng d X
2
1(mod q) cũng có hai nghiệm là X=1 mod q .
Vì X
2
1 (mod n) khi và chỉ khi X
2
1 (mod p) và X
2
1 (mod q) nên
suy ra X
2
1 (mod n) khi và chỉ khi X=1 mod p và X=1 mod q.Bởi
vậy có 4 căn bậc 2 của 1 theo modulo n và các căn này có thể tìm đợc
thông qua định lý phần d china.Hai trong các nghiệm này là X=1
mod n; chúng đợc gọi là các căn bậc hai tầm thờng và là các giá trị đối
của nhau theo modulo n.
Sau đây là một ví dụ dụ nhỏ để minh hoạ :
Ví dụ 4.10
Giả sử n=403=13 11.Bốn căn bậc hai của một theo modulo
403 là 1,92,311 và 402.Căn bậc hai 92 nhận đợc bằng cách giải hệ
X1 (mod 13) , X-1 (mod 31) theo định lý phần d china.Nếu tìm đợc
không tầm thờng này, nghiệm không tầm thờng kia phải là 403-
92=311.Đó là nghiệm của hệ X-1(mod 13), X1 (mod 31).
Giả sử X là căn bậc hai không tầm thờng của 1 modulo n. Khi
đó ta có
n(x-1)(x+1)
nhng n không là ớc của một nhân tử nào ở vế phải .Điều đó kéo theo
UCLN (X+1,n) = p hoặc q(và tơng tự UCLN(X-1,n)=p hoặc q).Tất
nhiên có thể tính UCLN bằng thuật toán Euclide mà không cần phải
biết phân tích nhân tử của n.Bởi vậy, hiểu biết về căn bậc hai không
tầm thờng của 1 mod n sẽ làm cho việc phân tích n chỉ cần thực hiện
trong thời gian đa thức.
Trong ví dụ dụ 4.10 ở trên, UCLN (93,403) =31 và UCLN
(312,403)=13
Trên hình 4.10 trình bày thuật toán (dùng thuật toán giả định A làm
chơng trình con) để phân tích n bằng cách tìm một căn bậc hai không
tầm thờng của 1 modulo n (A thực hiện tính số mũ giải mã a theo số
mũ mã b ).Trớc tiên ta sẽ đa ra một ví dụ để minh hoạ cho việc áp
dụng thuật toán này.
ví dụ 4.11
Giả sử n=89855713, b=34986517 và a=82330933 và giá trị
ngẫu nhiên w=5.Ta có :
ab-1=2
3
.360059073378795
trong bớc 6, v=85877701 còn ở bớc 10 , v=1.Trong bớc 12 ta tính
UCLN (85877702,n)=9103.
Đây là một thừa số của n; thừa số kia là n/9103=9871.
Bây giờ sẽ tiến hành phân tích thuật toán.Trớc tiên, nhân thấy
rằng nếu ta may mắn chọn đợc w là bội của p hoặc q thì có thể ngay
lập tức phân tích đợc n.Điều này đợc biểu thị ở bớc 2. Nếu nguyên tố
cùng nhau với n thì chúng ta sẽ tính w
r
, w
2r
, w
4r
, ,Bằng cách bình ph -
ơng liện tiếp cho tới khi
W
2r
1 (mod n)
Với giá trị t nào đó.Vì
Ab-1=2
s
r0 (mod (n))
Hình 4.10 Thuật toán phân tích thừa số (cho trớc số mũ giải mã a).
Không có nhận xét nào:
Đăng nhận xét