Kiểm tra tính nguyên tố xác suất

 

Để thiết lập hệ mật RSA, ta phải tạo ra các số nguyên tố ngẫu nhiên lớn (chẳng hạn có 80 chữ số). Trong thực tế, phương cách thực hiện điều này là: trước hết phải tạo ra các số ngẩu nhiên lớn, sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức (chẳng hạn như thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen). Cả hai thuật toán trên đều được trình bày trong phần này. Chúng là các thuật toán nhanh (tức là một số nguyên n được kiểm tra trong thời đa thức theo log2n, là số các bít trong biểu diện nhị phân của n). Tuy nhiên, vẫn có khả năng là thuận toán cho rằng n là số nguyên tố trong khi thực tế n là hợp lệ số. Bởi vậy, bằng cách thay đổi thuật toán nhiều lần, có thể giảm xác suất sai số dưới một mức ngưỡng cho phép (sau này sẽ thảo luận kỹ hơn một chút về vấn đề này).

Một vấn đề quan trọng khác: là cần phải kiểm tra bao nhiêu số nguyên ngẫu nhiên (với kích thươc xác định)cho tới khi tìm được một số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số (được gọi là định lý số nguyên tố) phát biểu rằng: số các số nguyên tố không lớn hơn N xấp xỉ bằng N/ln N. Bởi vậy, nếu p được chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1/ln p. Với một mođun 512 bít, ta có 1/ln p ằ 1/77. Điều này có nghĩa là tính trung bình, cư 177 số nguyên ngẫu nhiên p với kích thước tương ứng sẽ có một số là số nguyên tố. Dĩ nhiên, nếu chĩ hạn chế xét các số nguyên lẻ thì xác suất sẽ tăng gấp đôi tới khoảng 2/177). Bỡi vậy trên thực tế, hoàn toàn có khả năng tạo được các nguyên tố đủ lớn và do đó về mặt thực thể ta có thể thiết lập được một hệ mật RSA. Sau đây sẽ tiếp tục xem xét điều này được thực hiên như thế nào.

Một bài toán quyết định là một bài toán toán trong đó một câu hỏi cần được trả lời có hoặc không. Một thuật toán xác suất là một thuật toán bất kỳ có sử dụng các số ngẫu nhiên (ngược lại, thuật toán không sử dụng các số ngẫu nhiên sẽ được gọi là một thuật toán tất định). Các định nghĩa sau có liên quan tới các thuật toán xác suất cho các bài toán quyết định.

 

Định nghĩa 4.1

Thuật toán Monte Carlo định hướng có là một thuật toán xác suất cho một bài toán quyết định, trong đó câu trả lời có luôn luôn là đúng còn câu trả lời không có thể là sai. Thuật toán Monte Carlo định hướng không cũng được định nghĩa theo cách tương tự. Chúng ta nói rằng, một thuật toán Monte Carlo định hướng có có xác suất sai bằng e nếu với bất kỳ mổt trường hợp nào mà câu trả lời là có thì thuật toán có câu trả lời sai không với xác suất không lớn hơn e (xác suất này được tính trên mọi phép chon ngẫu nhiên, có thể thực hiên bởi thuật toán với một câu vào đã cho).

 

Bài toán quyết định ở đây là bài toán hợp lệ số mô tả ở hình 4.5.

Cần chú ý rằng một thuật toán quyết định chỉ có câu trả lời có hoặc không đặc biệt trong bài toán hợp lệ số là ta không yêu cầu thuật toán tính tích thừa số khi n là hợp lệ số.

Trước tiên ta sẽ mô tả thuật toán Soloway- Strasson. Đây là một thuật toán Monte- Carlo định hướng có cho bài toán hợp số có

Trước tiên ta sẽ mô tả thuật toán Soloway- Strasson. Đây là một thuật toán Monte-Carlo định hướng có cho bài toán hợp số và xác xuất sai 1/2. Bởi vậy, nếu thuật toán trả lời có thì n là hợp số; ngược lại nếu n là hợp số thì thuật toán trả lời có với xác xuất tối thiểu 1/2.

 

Hình 4.5. Bài toán hợp số.

Đặc trưng của bài toán: một số nguyên dương n 2

Câu hỏi: n có phải là hợp số không ?
 
 

 

 

 


Hình 4.6. Bài toán về các thặng dư bậc hai.

 

 

Đặc trưng của bài toán: cho p là một số nguyên tố lẻ và một số nguyên x sao cho 0 Ê x Ê p-1

Câu hỏi: x có phải là thặng dư bậc hai phép modulo p ?

 
 
 

 

 

 

 

 

 


Mặc dù thuật toán Miller-Rabin (ta sẽ xét sau) nhanh hơn thuật toán Soloway-Strasson (S-S) nhưng ta sẽ xét thuật toán S-S trước vì nó dễ hiểu hơn về khái niệm, đồng thời lại liên quan tới một số vấn đề của lý thuyết số (mà ta sẽ còn dùng trong các chương trình sau). Ta sẽ xây dựng một số nền tảng sâu sắc hơn trong lý thuyết số trước khi mô tả thuật toán.

 

 

Định nghĩa 4.2.

Giả sử p là một số nguyên tố lẻ và x là một số nguyên, 1 Ê x Ê p-1. x được gọi là thặng dư bậc hai theo modulo p nếu phương trình đồng dư y2 x (modulo p) có một nghiệm yưẻZp x được gọi là thặng dư không bậc hai theo modulo p nếu x ??? 0 (mod p) và x không phải là thặng dư bậc hai theo modulo p.

 

Ví dụ 4.6.

Các thặng dư bậc hai theo modulo 11 là 1,3,4,5 và 9. Cần để ý rằng, (1)2=1, (5)2=3, (2)2=4, (4)2=5, (3)2=9 (ở đây tất cả các phép số học đều thực hiện trong Z11).

 

Bài toán quyết định thặng dư bậc hai được trình bày trên hình 4.6 sẽ được thấy một cách tươnngf minh như sau:

 

Trước hết, ta sẽ chứng minh một kết quả- tiêu chuẩn Euler tạo nên thuật toán tất định theo thời gian đa thức cho bài toán về các thặng dư bậc hai.

 

 

Định lý 4.8. (Tiêu chuẩn Euler)

Giả sử p là một số nguyên tố, khi đó x là một thặng dư bậc hai theo modulo p khi và chỉ khi:

x(p-1)/2 1 (mod p)

Chứng minh:

Trước hết giả sử rằng, xy2(mod p). Theo hệ quả 4.6, nếu p là số nguyên tố thì xp-11 (mod p) với mọi x 0 (mod p). Bởi vậy ta có :

x(p-1)/2 (y2)(p-1)/2 (mod p)

yp-1(mod p)

1 (mod p)

 

Ngược lại, giả sử rằng x(p-1)/21 (mod p). Cho p là một phần tử nguyên thuỷ theo modulo p. Khi đó xbi (mod p) với giá trị i nào đó. Ta có

x(p-1)/2 (bi)(p-1)/2 (mod p)

bi(p-1)/2(mod p)

Vì p có bậc bằng p-1 nên p-1 phải là ước của i(p-1)/2. Bởi vậy i là số chẵn và như vậy căn bậc hai của x là bi/2.;

 

Định lý 4.8 sẽ dẫn tới một thuật toán thời gian đa thức cho các thặng dư bậc hai nhờ sử dụng kỹ thuật bình phương và nhân cho phép lấy luỹ thừa theo modulo p. Độ phức tạp của thuật toán khoảng O((log p)3).

 

Sau đây tiếp tục đưa ra một số định nghĩa từ lý thuyết số:

 

Định nghĩa 4.3.
 
Giả sử p là số nguyên tố lẻ. Với một số nguyên tố bất kỳ a 0, ta

 

 
 
định nghĩa ký hiệu Legendre như sau:

 


0 nếu a 0 (mod p)

= 1 nếu là thăng dư bậc hai theo modulo p

-1 nếu là thăng dư không bậc hai theo modulo p

 

Ta đã biết là a(p-1)/2 1 (mod p) khi và chỉ khi a là một thặng dư bậc hai theo modulo p. Nếu a là bội của p thì rõ ràng a(p-1)/2 0(mod p). Cuối cùng, nếu a là một thặng dư không bậc hai theo modulo p thì a(p-1) -1 (mod p) vì ap-11(mod p). Bởi vậy, ta có kết quả cho phép xây dựng một thuật toán hữu hiệu để đánh giá các ký hiệu Legendre như sau

 

Định Lý 4.9.

 

 
 
 


 
 
Giả sử p là một số nguyên tố. Khi đó a(p-1)/2 (mod p).

 

Sau đây là một định nghĩa tổng quát hoá cho ký hiệu Legendre.

 

Định nghĩa 4.4.

Giả sử n là một số nguyên dương lẻ và phân tích theo các luỹ thừa nguyên tố của n là p1e1 ....... pKek . Giả sử a 0 là một số nguyên. Ký hiệu

 

Jacobi được định nghĩa như sau:

 
 
 


 
 

 

 

 

Ví dụ 4.7.

 
 
 


Xét ký hiệu Jacobi . Phân tích luỹ thừa nguyên tố của 9975 là: 9975=3 x 52 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 = 1045 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 chưa 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 đã 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à m1 m2 (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=2kt với t là một số lẻ thì:

 

 
 
 

 

 

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

 

 

theo tính chất 4

 

= theo tính chất 1

. = theo tính chất 3

= theo tính chất 2

= theo tính chất 4

= theo tính chất 1

= theo tính chất 3

= theo tính chất 2

= theo tính chất 4

= 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 ằ 2256 ằ e177 (đâ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ũ nhưng 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ỏ.

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=2km, 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=am 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=b2 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à am 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ị am , a2m ,ẳ,a2k-1m. Vì thuật toán trả lời n là hợp số nên suy ra:

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

A2km 1 (mod 1)

Vì n-1 = 2km. Khi đó a2k-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ó

a2k-1m -1(mod n)

bởi vậy ta phải có:

a2k-1m 1(mod n)

 

Khi đó a2k-2m phải là căn bậc hai của 1. Bằng lập luận tương tự:

A2k-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 đề chưa chưa đượ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 nhưng 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ẽ lưu 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 F(n) là đủ. Nếu đã biết n và F(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 chưa biết:

n=pq

F(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 chưa biết p :

P2-(n-F(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 F(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 F(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à F(n)= 4754668. Thông tin này sẽ dẫn tới phương trình:

 

P2-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 Ê e Ê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 e 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 nhưng 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 nhưng 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à em.Số lần chạy trung bình để thu được câu tra lời thực tế là 1/e (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/2m.

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ư X2 1( mod p) có hai nghiệm theo modulo p là X=1 mod p .Tương tự, phương trình đồng dư X21(mod q) cũng có hai nghiệm là X=1 mod q .

Vì X2 1 (mod n) khi và chỉ khi X21 (mod p) và X21 (mod q) nên suy ra X2 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)

 

nhưng 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=23.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 wr , w2r, w4r,,Bằng cách bình phương liện tiếp cho tới khi

W2r 1 (mod n)

Với giá trị t nào đó.Vì

Ab-1=2sr0 (mod F(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).

 

 

 

 

1.     Chọn w ngẫu nhiên sao cho 1Ê w Ê n-1

2.     Tính x=UCLN(w,n)

3.     IF 1 < x < n then quit (thành công :x=p hoặc x=q)

4.     Tính a=A(b)

5.     Viết ab-1=2sr, r Lợ

6.     Tính v=wr mod n

7.     IF v=1 (mod n) then quit (không thàmh công)

8.     While v 1 (mod n) do

9.     V0=v

10.            v=v2 mod n

11.            If v0 -1 (mod n) then

Quit (không thành cô g)

Else

Tính x=UCLN(v0+1,n)

(thành công :x=p hoặc x=q)

 

 

Nếu ta có W2r1(mod n) .Bởi vậy, vòng lặp while sẽ kết thúc sau nhiều nhất là s bước lặp .kết thúc vòng lặp, ta tìm được một giá trị v0 sao cho v021 (mod n) nhưng v0 1 (mod n) .Nếu v0-1 (mod ,n ) thì thuật toán không thành công ; ngược lại , v0 sẽ là một căn bậc hai không tầm thường của 1 modulo n và ta phân tích được n (bước 12 ).

Nhiệm vụ chính còn lại bây giờ là phải chứng minh rằng, thuật toán thành công với xác suất là ẵ .Có hai cách mà theo đó thuật toán có thể không thành công khi phân tích n :

1.Wr1 (mod n) (bước 7)

2.W2r-1 ( mod n ) với giá trị t nào đó , 0 Ê t Ê s-1 (bước 11)

 

Chúng ta có n+1 phương trình đồng dư để xem xét.Nếu giá trị ngẫu nhiên w là một nghiệm của ít nhất một trong các đồng dư thức này thì phép lựa chọn w này là tồi và thuật toán sẽ không thành công. Bởi vậy, ta sẽ chuyển sang tính số các nghiệm của mỗi đông dư thức này.

 

Trước tiên xét đồng dư thức wr1 (md n). Phương pháp phân tích một đồng dư thức giống như cách xem xét một cách riêng rẻ các nghiệm theo modulo q. Sau đó kết hợp chúng nhờ định lý phần dư China. Cần đề ý rằng x1 (mod n) khi và chỉ khi x1 (mod p) và x1 (mod q).

 

Như vậy, trước hết ta phải xét wr1 (mod n). Vì p là một số nguyên tố nên Zp* là một nhóm cyclic theo định lý 4.7. Giả sử g là một phần tử nguyên thuỷ theo modulo p. Ta có thể viết w=gu với số nguyên duy nhất u nào đó, 0 Ê u Ê p-2. Khi đó ta có :

Wr 1(mod p)

gur1 (mod p)

(p-1) ẵur

 

Giả sử ta biểu diễn p-1=2ip1 trong đó p1 là một số lẻ và q-1 =2jq1, q1 là một số lẻ.

 

Vì

F(n)=(p-1)(q-1) ẵ(ab-1)=2sr

nên ta có

 

2i+jp1q1ẵ2sr

 

Bởi vậy:

 

i+j Ê s

Và

 

P1q1ẵ r

 

Bây giờ điều kiện p-1 ẵ ur sẻ trở thành 2ip1 ẵur. Vì p1ẵr và r lẻ nên điều kiện cần và đủ là 2iẵu.Vì thế, u=k. 2i, 0Ê k Ê p1-1 và số các nghiệm của dư thức wr1 (mod p) sẻ là p1.

 

Bằng lập luận tương tư, ta thấy đồng dư thức wr 1 (mod q) sẻ có đúng q1 nghiệm.Có thể kết hợp nghiệm bất kỳ theo modulo p với nghiệm bất kỳ theo modulo q để thu được một nghiệm duy nhất theo modulo n nhờ định lý phần dư China. Do vậy số các nghiệm của đồng dư thức wr1 (modn ) sẻ là p1q1.

 

Tiếp theo, xét đồng dư thức w2r 1(mod n) với giá trị t cố định

(trong đó : 0 Ê t Ê s-1).

 

Trước tiên lại xét đồng dư thức theo modulo p rồi sau đo xét theo modulo q. (Để ý rằng, ???-1 (mod n) khi và chỉ khi w2r-1 (mod p) và

. Đầu tiên ta xét nếu viết như ở phần trên ta nhận được

Vì g(p-1)/2 -1(mod p) nên ta có

u2tr (p-1)/2( mod p-1)

(p-1) │ (u2tr-(p-1)/2)

2(p-1)│ (u2t+1r-(p-1))

Vì p-1=2ip1 nên ta nhận được

2i+2 p1 │ u 2t+1r-2ip1)

Loai bỏ thừa số chung ta có

2i+1 │ (u-2i)

Xét thấy nếu thì có thể là không có nghiệm do 2i+1 │ 2t+1 nhưng

2i+1 │ 2i

Mặt khác nếu -1 thì u sẽ là một nghiệm khi và chỉ khi u là bội lẻ của 2i-t-1 .

 

(chú ý rằng r/p1 là một số nguyên lẻ). Bởi vậy, số các nghiệm trong trườnh hợp này là

=2tp1

Tương tự, đồng dư thức (mod q) sẽ :

- Không có nghiệm nếu

- Có 2tq1 nghiệm nếu t Ê j-1

Từ định lý phần dư China ta sẽ thấy rằng số các nghiệm của là

-             0 nếu

-             22t p1q1 nếu

t có thể nằm trong dải từ 0 tới s-1. Không mất tính tổnh quát giả sử i Ê j; khi đó số các nghiệm sẽ bằng 0 nếu . Tổng số các lựa chọntồi của w nhiều nhất là

p1q1+p1q1(1+22+24+ẳ+22i-1) = pư1q1(1+)

=

 

Để ý là p-1 = 2ip1 còn q-1=2jq1. Bây giờ giả sử j i 1 khi đó p1q1<n/4

Ta cũng có :

 

22ip1q1 Ê 2i+j p1q1 =(p-1)(q-1) < n

Bởi vậy:

p1q1()<

 

Vì có nhiều nhất là (n-1)/2 phép chọn tồi đối với w nên điều đó có nghĩa là có ít nhất (n-1)/2 phép chọn tốt và vì thế xác suất thành công của thuật toán tối thiểu là 1/2.

4.6.2 .Thông tin riêng có liên quan tới các bit cửa bản rõ 11111111111111

 

Xét một kết quả khác có liên quan tới thông tin về bản rõ có thể bị rò rỉ bởi phép mã hoá RSA. Sau đây là hai trường hợp xét về thông tin riêng

 

1.     Cho y=eưKư(x), hãy tính parity(y) trong đó parity(y) chỉ bít cấp

thấp của x.

2.     Cho y=eK(x), hãy tính half(y) trong đó half(y)=0 nếu và half(y)=1 néu

 

Ta sẽ chứng minh rằng với y=eK(x) cho trước một thuật toán bất kỳ tính parity(y) hoặc half(y) đều có thể được dùng như một chương trình con để xây dựng một thuật toán tính bản x. Điều đó có nghĩa là, với một bản mã cho trước, việc tính bit bậc thấp của bản rõ sẽ tương đương đa thức với việc xác định toàn bộ bản rõ !

 

Trước hết, ta sẽ chứng minh rằng, việc tính parity(y) là tương đương đa thức với việc tính half (y). Điều này rút ra từ hai đồng nhất thức đơn giản sau (xét bài tập ):

 

halt(y)=parity(y x eK(2) mod n) (4.1)

parity(y)=half(y x eK(2ư-1)mod n) (4.2)

và từ quy tắc nhận eK(x1) eK(x2)=eK(x1x2)

 

Ta sẽ chỉ ra cách tính x=dK(y) theo một thuật toán giả định cho trước để tính half(y). Thuật toán được trình bày trên hình 4.11 .Trong các bước 2.4 ta tính :

 

yi = half(y x (eK(2))I)=half(eK(x x2i))

 

với . Nhận thấy rằng:

half (eK(x))= 0 x

half(eK(2x)=0

half(eK(4x))= 0

 

Bởi vậy ta có thể tìm theo kỹ thuật tìm tìm kiếm nhị phân (được làm trong các bước 7-11). Dưới đây là một ví dụ nhỏ để minh hoạ

 

Ví dụ 4.12

 

Giả sử n=1457, b=779 và ta có bản mã y=772. eK(2) được tính bằng 946. Giả giử rằng (sử dụng thuật toán giả định đối với half(y)) . ta nhận được các giá trị yi sau theo bước 3 thuật toán:

 

Hình 4.11.Giả mã bản mã RSA với một thuật toán giả định tính

half(y) cho trước

 

 

1.      Ký hiệu k=│log2 n │

2.      For i=0 to k do

3.      yi =half(y)

4.        y=(y* eK(2)) mod 2

5.      lo=0

6.      hi=n

7.      for i=0 to k do

8.      mid=(hi+lo)/2

9.      IF yi=1 then

lo=mid

else

hi=mid

10. x=│hi│
 
 

 

 

 

 


Hình 4.12. Phép tìm kiếm nhị phân để giải mã RSA.

 

I

Lo

Mid

Hi

0

0.00

728.50

1457.00

1

728.50

1092.75

1457.00

2

728.50

910.62

1092.75

3

910.62

1001.69

1092.75

4

910.62

956.16

1001.69

5

956.16

978.92

1001.69

6

978.92

990.00

1001.69

7

990.30

996.00

1001.69

8

996.00

998.84

1001.69

9

998.84

1000,26

1001.26

10

998.84

999.55

1000.26

 

998.84

999.25

999.55

 

i │0 │ 1 │ 2 │ 3 │ 4 │ 5 │6 │ 7 │ 8 │ 9 │ 10

yi │1 │ 0 │ 1 │ 0 │ 1 │ 1│ 1 │ 1 │ 1 │ 0 │ 0

 

Sau đó tiến hành tìm kiếm nhị phân theo hình 4.12. Bản rõ tìm thấy là x=│999.55│=999.

ưưưưưưưưưưưưưưưưưưưưư

 

 

4.7. Hệ MậT RABIN

 

Trong phần này sẽ mô tả hệ ma trận Rabin. Đây là hệ mật có độ an toàn cao về mặt tính toán chống lại được cách tấn công bản rõ lựa chọn và không có khả năng phân tích được n=pq(hệ được trình bày trong hình 4.13).

 

Chúng ta sẽ chỉ ra rằng, hàm mã hoá ek không phải là một đơn ánh, vì thế phép giải mã không thể thực hiện được một cách xác định. Thực tế có 4 bản rõ có thể ứng với một bản mã bất kỳ cho trước. Chính xác hơn, giả sử w là một trong 4 căn bậc hai của một modulo n. Giả sử xє Zn. Khi đó có thể kiểm tra các phương trình sau:


 

(Cần chú ý là tất cả các phép tính số học đều thực hiện trong Zn, còn phép chia cho 2 và 4 giống như phép nhân 2-1và 4-1 theo modulo n ).

 

Hình 4.13. Hệ mật Rabin

Giả sử n là tích của hai số nguyên tố phân biệt p và q, p.q Ê 3 (mod 4). Giả sử p =C=Zn và ta xác định

K={(n , p , q , B): 0 Ê B Ên-1}

Với K = (n , p , q , B) ta định nghĩa:

ek(x) = x( x+B) mod n

và

các giá trị n và B được công khai trong khi p và q được giữ kín.

 
 
 

 

 

 

 

 

 

 


Bốn bản rõ mã hoá thành eK(x) là x, -x B, w(x+B/2) và -w(x+B/2), trong đó w là một căn bậc hai không tầm thường của 1modulo n. Nói chung Bob không có cách nào để xác định bản nào trong bốn bản rõ có thể này là bản rõ đúng, trừ phi bản rõ có đủ độ dư để loại bỏ ba trong bốn bản rõ đó.

 

Bây giờ ta xem xet bài toán giải mã theo quan điểm của Bob. Anh ta đã có bản mã y và muốn xác định x sao cho:

x2+ bx y(mod n)

Đây là một phương trình bậc hai theo giá trị x chưa biết. Ta có thể loại bỏ số hạng tuyến tính bằng phép thế x1=x+B/2 (Hay x = x1- B/2). Khi đó phương trình trên có dạng

Nếu đặt thì có thể viết lai phương trình đồng dư như sau:

x1 C (mod n)

 

Như vậy phép giải mã sẽ chỉ còn là thực hiện phép khai căn bậc hai theo modulo n. điều này tương đương với việc giải phương trình đồng dư sau:

x12 C (mod p)

x12 C (mod q)

 

(Có hai căn bậc hai của C modolo p và hai căn bậc của C theo modolo q. Bằng cách dùng định lý phần dư China, các nghiệm này có thể được kết hợp để tạo nên bốn nghiệm theo modulo n). Có thể dùng tiêu chuẩn Eucler để xác định xem C có phải là một thặng dư bậc hai theo modulo p ( và modulo q) hay không . Trên thực tế, C là một thặng dư bậc hai theo modulo p và modulo q nếu phép mã hoá được thực hiện đúng. Tuy nhiên tiêu chuẩn Eucler không giúp chúng ta tìm được các căn bậc hai của C. Nó chỉ ra một câu trả lời Có hoăc Không.

Khi p 3 (mod 4), ta có một công thức đơn giản để tính các căn bậc hai của các thặng dư bậc hai theo modulo p. Giả sử C là một thặng dư bậc hai và p 3 (mod 4) . Khi đó ta có:

( C(p+1)/4)2 C(p+1)/2(mod p)

C(p-1)/2 C (mod p)

C(mod p)

ở đây ta lại một lần nữa sử dụng tiêu chuẩn Eucler, hai tiêu chuẩn này phát biểu rằng, nếu C là một thặng dư bậc hai theo modulo p thì C(p+1)/2 1(mod p).

Vì thế , hai căn bậc hai của C modulo p là C(p+1)/4mod p. Tương tự, hai căn bậc hai của C modulo q là C(p+1)/4mod q. Sau đó ta có thể thu được bốn căn bậc hai của x1 của C modulo n bằng cách dùng định lý phần dư China.

 

Nhận xét:

Một điều lý thú là với p 1 (mod 4), người ta chưa biết được một thuật toán tất định theo thời gian đa thức nào để tính căn bậc hai của các thặng dư bậc hai theo modulo p . Tuy nhiên, vẫn có thuật toán Las Vegas với thời gian đa thức để tính nó .

Một khi đã xác định bốn giá trị có thể của x1, ta tính x từ phương trình x=x1-B/2 để tìm được bốn bản rõ có thể. Điều này dẫn đến công thức giải mã sau:

Ví dụ 4.13

 

Ta xẽ minh hoạ các thủ tục mã hoá và giải mã đối với hệ mật Rabin một ví dụ nhỏ. Giả sử n=77=711 và B=9. Khi đó hàm mã hoá là

eK(y)=x2+9x mod 77

và hàm giải mã là

Giả sử Bob muốn giải mã bản mã y=22. Điều cần thiết trước tiên là tìm các căn bậc hai của 23 theo modulo 7 và modulo 11. Vì cả 7 va11 đều đồng dư với 3 modulo 4 nên ta có

23(7+1)/4 22 4 mod 7

và 23(11+1)/4 13 1 mod 7

 

Sử dụng định lý phần dư China, ta sẽ tính được bốn căn bậc hai của 23 theo modulo 77 là 10, 32 mod 77 . Cuối cùng bốn bản giõi có thể là :

10- 43 mod 77=44

67- 43 mod 77=24

32- 43 mod 77=66

45- 43 mod 77= 2

 

Có thể kiểm tra lại rằng, mỗi một bản rõ này đều được mã hoá thành một bản mã 22.

 

Bây giờ chúng ta xẽ thảo luận về độ mật của hệ Rabin. Ta xẽ chứng minh rằng một thuật toán giải mã giả định A có thể được dùng như một chương trình con trong một thuật toán Las Vegas để phân tích modulo n với xác suất tối thiểu bằng 1/2. Thuật toán này được mô tả ở hình 4.14.

 

Có một số điểm cần được giải thích ở đây. Trước hết ta thấy rằng