Giáo trình Bảo mật thơng tin

CHƢƠNG 4: CÁC HỆ MẬT MÃ KHỐ CƠNG KHAI
4.1. Giới thiệu về mật mã khố cơng khai
Trong mơ hình mật mã cổ điển Alice (ngƣời gửi) và Bob (ngƣời nhận) chọn
một cách bí mật khố K. Sau đó dùng K để tạo luật mã hố ekvà luật giải mã dk. Trong
hệ mật này dk hoặc giống nhƣ ek hoặc dễ dàng tính đƣợc từ ek. Các hệ mật thuộc loại
này đƣợc gọi là hệ mật khố bí mật, nếu để lộ ek thì làm cho hệ thống mất an toàn.
Nhƣợc điểm của hệ mật này là nó u cầu phải có thơng tin về khố K giữa
Alice và Bob qua một kênh an toàn trƣớc khi gửi một bản mã bất kỳ. Trên thực tế điều
này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách xa nhau và họ chỉ có thể liên
lạc với nhau bằng thƣ tín điện tử (Email). Trong tình huống đó Alice và Bob khơng thể
tạo một kênh bảo mật với giá phải chăng.
Ý tƣởng xây dựng một hệ mật khố cơng khai (hay khố dùng chung) là tìm
một hệ mật khơng có khả năng tính tốn để xác định dk khi biết ek. Nếu thực hiện đƣợc
nhƣ vậy thì quy tắc mã ek có thể đƣợc cơng khai bằng cách cơng bố nó trong một danh
bạ (bởi vậy nên có thuật ngữ hệ mật khố cơng khai). Ƣu điểm của hệ mật khố cơng
khai là ở chỗ Alice (hoặc bất kì một ai) có thể gửi một bản tin đã mã cho Bob (mà
không cần thông tin trƣớc về khố mật) bằng cách dùng luật mã cơng khai ek. Ngƣời
nhận sẽ là ngƣời duy nhất có thể giải đƣợc bản mã này bằng cách sử dụng luật giải mã
bí mật dk của mình.
Có thể hình dung hệ mật này tƣơng tự nhƣ sau: Bob tạo hai khóa lập mã Kd và
giải mã Ke rồi gửi khóa lập mã cho Alice, Alice dùng khóa lập mã của Bob để mã hóa
sau đó gửi bản tin đã mã cho Bob. Bob dùng khóa bí mật của mình để giải mã bản tin
nhận đƣợc.
Ý tƣởng về một hệ mật khoá công khai đã đƣợc Diffie và Hellman đƣa ra vào
năm 1976. Việc hiện thực hố nó do Rivesrt, Shamir và Adleman đƣa ra đầu tiên vào
năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA. Kể từ đó một số hệ mật đƣợc công bố,
độ mật của chúng dựa trên các bài tốn tính tốn khác nhau.

89

Giáo trình Bảo mật thơng tin

4.1.1. Một số bài tốn cơ bản
Phần này giới thiệu một số bài toán số học đƣợc sử dụng khi xây dựng các hệ
mật mã khố cơng khai
Bài tốn phân tích số ngun (thành thừa số nguyên tố):
Cho số nguyên dƣơng n , tìm tất cả các ƣớc số nguyên tố của nó, hay là tìm
dạng phân tích chính tắc của n = p1 . p2 ... pk , trong đó pi là các số nguyên tố từng cặp
1

2

k

khác nhau và các i  1.
Bài tốn này có liên hệ mật thiết với các bài tốn thử tính ngun tố hay thử
tính hợp số của một số nguyên.
Trong lý thuyết mật mã, bài toán này thƣờng đƣợc sử dụng với các dữ liệu n là
số ngun Blum, tức các số ngun dƣơng có dạng tích của hai số ngun tố lớn nào
đó.
Bài tốn RSA (Rivest-Shamir-Adleman) :
Cho số nguyên dƣơng n là tích của hai số nguyên tố lẻ khác nhau, một số
nguyên dƣơng e sao cho gcd(e, (n)) = 1, và một số nguyên c, tìm một số nguyên m
sao cho me  c (mod n) .
Điều kiện gcd(e, (n)) = 1 bảo đảm với mỗi số nguyên c  0, 1,..., n -1 có
đúng một số m  0, 1,..., n -1 sao cho me  c (mod n)
Nếu biết hai thừa số nguyên tố của n thì sẽ tính đƣợc (n) = (p -1)(q -1). Vì
gcd(e, (n)) =1 nên tính đƣợc d = e -1mod (n), do đó sẽ tìm đƣợc m = c d modn. Nhƣ

vậy, bài tốn RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số
ngun.
Bài tốn thặng dƣ bậc hai :
Cho một số nguyên lẻ n là hợp số, và một số nguyên a Jn ( tập tất cả các số a
có ký hiệu Jacobi J(a,n) =1). Hãy quyết định xem a có là thặng dƣ bậc hai theo mod n
hay không?
Trong lý thuyết mật mã, bài toán này cũng thƣờng đƣợc xét với trƣờng hợp n là
số nguyên Blum. Khi đó nếu a Jn , thì a là thặng dƣ bậc hai theo modn khi và chỉ khi
J(a,n) =1, điều kiện này có thể thử đƣợc vì nó tƣơng đƣơng với điều kiện a (p -1)/2  1
(modp). Nhƣ vậy, trong trƣờng hợp này, bài tốn thặng dƣ bậc hai có thể qui dẫn trong

90


Giáo trình Bảo mật thơng tin

thời gian đa thức về bài tốn phân tích số ngun. Mặt khác, nếu khơng biết cách phân
tích n thành thừa số ngun tố thì cho đến nay, khơng có cách nào giải đƣợc bài toán
thặng dƣ bậc hai trong thời gian đa thức.
Bài toán tìm căn bậc hai mod n :
Cho một số nguyên lẻ n là hợp số Blum, và một số a Qn (tập các thặng dƣ bậc
hai theo modn). Hãy tìm một căn bậc hai của a theo modn, nghĩa tìm x sao cho x 2  a
(modn).
Nếu biết phân tích n thành thừa số nguyên tố n =p*q, thì bằng cách giải các
phƣơng trình x 2  a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng
lại theo định lý số dƣ China sẽ đƣợc nghiệm theo modn, tức là căn bậc hai của a theo
modn cần tìm. Vì mỗi phƣơng trình x 2  a theo modp và modq có hai nghiệm (tƣơng
ứng theo modp và modq ), nên kết hợp lại thu đƣợc bốn nghiệm, tức bốn căn bậc hai
của a theo modn. Ngƣời ta đã tìm đƣợc một số thuật tốn tƣơng đối đơn giản (trong
thời gian đa thức) giải phƣơng trình x 2  a (modp) với p là số nguyên tố. Nhƣ vậy, bài

tốn tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài tốn phân tích
số ngun.
Ngƣợc lại, nếu có thuật tốn  giải bài tốn tìm căn bậc hai modn thì cũng có
thể xây dựng một thuật tốn giải bài tốn phân tích số nguyên nhƣ sau: Chọn ngẫu
nhiên một số x với gcd(x,n) =1, và tính a = x2modn. Dùng thuật tốn  cho a để tìm
một căn bậc hai modn của a. Gọi căn bậc hai tìm đƣợc đó là y. Nếu y  x (modn), thì
phép thử thất bại, ta phải chọn tiếp một số x khác, nếu y ≢ x (modn) thì gcd(x-y, n) là
một ƣớc số khơng tầm thƣờng của n, cụ thể là p hay là q. Vì n có 4 căn bậc hai modn
nên xác suất của thành công ở mỗi lần thử là 1/2, do đó số trung bình (kỳ vọng tốn
học) các phép thử để thu đƣợc một thừa số p hay q của n là 2, từ đó ta thu đƣợc một
thuật tốn giải bài tốn phân tích số ngun (Blum) với thời gian trung bình đa thức.
Bài tốn logarithm rời rạc :
Cho số nguyên tố p, một phần tử nguyên thuỷ  theo modulo p (hay  là phần
tử nguyên thuỷ của Z p ), và một phần tử   Z p . Tìm số nguyên x (0 x  p - 2) sao cho

 x   (modp).
Bài toán logarithm rời rạc suy rộng :

91


Giáo trình Bảo mật thơng tin

Cho một nhóm cyclic hữu hạn G cấp n, một phần tử sinh (nguyên thuỷ)  của
G, và một phần tử  G. Tìm số nguyên x (0 x  n - 1) sao cho  x = .
Các nhóm đƣợc quan tâm nhiều nhất trong lý thuyết mật mã là: nhóm nhân của
trƣờng hữu hạn GF(p) - đẳng cấu với nhóm Z p của trƣờng Zp, nhóm nhân

của


trƣờng hữu hạn GF(2m), nhóm nhân Z n  a :0  a  n  1, gcd(a, n)  1 của trƣờng Zn
với n là hợp số, nhóm gồm các điểm trên một đƣờng cong elliptic xác định trên một
trƣờng hữu hạn,...
Bài toán Diffie-Hellman :
Cho số nguyên tố p, một phần tử nguyên thuỷ  theo modp (tức phần tử sinh
của Z p ), và các phần tử  a mod p và  b mod p . Hãy tìm giá trị  ab mod p
Có thể chứng minh đƣợc rằng bài toán Diffie-Hellman qui dẫn đƣợc về bài
toán logarithm rời rạc trong thời gian đa thức.
Bài toán tổng tập con (hay bài toán KNAPSACK) :
Cho một tập các số nguyên dƣơng a1 , a2 ,..., an  và một số nguyên dƣơng s. Hãy
xác định xem có hay khơng một tập con các aj mà tổng của chúng bằng s. Một cách
tƣơng đƣơng, hãy xác định xem có hay khơng các xi 0,1 (1 i  n) sao cho



n
i 1

ai xi  s.

Bài toán này là một bài toán P- đầy đủ, tức là thuộc lớp những bài tốn khó
mà cho đến nay chƣa tìm đƣợc thuật toán giải chúng trong thời gian đa thức.
Bài tốn giải mã đối với mã tuyến tính :
Mã tuyến tính là một lớp mã truyền tin có tính chất tự sửa sai đƣợc sử dụng
trong kỹ thuật truyền tin số hố. Có thể phát biểu trực tiếp bài tốn giải mã đối với mã
tuyến tính nhƣ sau:
Cho một ma trận cấp n x m A = (aij) gồm các thành phần là 0 hoặc 1, một vectơ
y = (y1,y2,...,ym) các giá trị 0 và 1 và một số nguyên dƣơng K. Hỏi có hay khơng một
vectơ x = (x1,x2,...,xn) gồm các số 0 hoặc 1 và có khơng nhiều hơn K số 1 sao cho với
n


mọi j (1j m):

 x .a
i 1

i

ij

 y j (mod 2)

ở đây, x là vectơ thông tin, và y là vectơ mã, phép giải mã là tìm lại x khi nhận đƣợc y.

92


Giáo trình Bảo mật thơng tin

4.1.2. Một số hệ mật mã khố cơng khai quan trọng :
-

Hệ mật mã RSA: Độ bảo mật dựa trên độ khó của việc phân tích ra thừa số
nguyên tố các số nguyên lớn.

-

Hệ mật mã xếp ba lơ Merkle - Hellman: dựa trên tính khó giải của bài tốn tổng
các tập con (là bài toán NP đầy đủ - một lớp khá lớn các bài tốn khơng có
thuật giải đƣợc biết trong thời gian đa thức).


-

Hệ mật mã McEliece: dựa trên lý thuyết mã đại số. Hệ mật McEliece dựa trên
bài toán giải mã cho các mã tuyến tính (cũng là một bài tốn NP đầy đủ).

-

Hệ mật mã Elgamal: trên tính khó giải của bài toán logarithm rời rạc trên các
trƣờng hữu hạn.

-

Hệ mật mã Chor - Rivest: đƣợc xem nhƣ một loại hệ mật xếp ba lô.

-

Hệ mật mã trên các đƣờng cong Elliptic: Các hệ mật mã này là biến tƣớng của
các hệ mật mã khác (chẳng hạn nhƣ hệ mật Elgamal), chúng làm việc trên các
đƣờng cong Elliptic. Hệ mật mã này đảm bảo độ mật với khoá số nhỏ hơn các
hệ mật mã khố cơng khai khác.
Một chú ý quan trọng là một hệ mật mã khố cơng khai không bao giờ đảm bảo

đƣợc độ mật tuyệt đối (an tồn vơ điều kiện). Vì khi đối phƣơng nghiên cứu một bản
mã y có thể mã lần lƣợt các bản rõ bằng luật mã công khai ek cho tới khi tìm đƣợc bản
rõ duy nhất x đảm bảo y = ek(x). Bản rõ này chính là kết quả giải mã của y. Bởi vậy ta
chỉ nghiên cứu độ mật về mặt tính tốn của các hệ mật mã này.
4.1.3. Hàm cửa sập một chiều
Hàm mã khố cơng khai ek phải là một hàm dễ tính tốn. Song việc tìm hàm
ngƣợc (hàm giải mã) phải rất khó khăn (đối với bất kỳ ai khơng phải là Bob). Đặc tính

dễ tính tốn nhƣng khó tính tốn hàm ngƣợc thƣờng đƣợc gọi là đặc tính một chiều.
Bởi vậy điều kiện cần thiết là ek phải là hàm một chiều.
Khái niệm: Hàm số số học y = f(x) đƣợc gọi là hàm một chiều (one-way
function), nếu việc tính thuận từ x ra y là “dễ”, nhƣng việc tính ngƣợc từ y tìm lại x là

93


Giáo trình Bảo mật thơng tin

rất “khó”, (có thể hiểu “dễ” là tính đƣợc trong thời gian đa thức, cịn “khó” là khơng tính
đƣợc trong thời gian đa thức)
Các hàm một chiều đóng vai trị quan trọng trong mật mã học: chúng rất quan
trọng các hệ mật khố cơng khai và trong nhiều lĩnh vực khác. Tuy nhiên, mặc dù có
rất nhiều hàm đƣợc coi là hàm một chiều nhƣng cho tới nay vẫn khơng tồn tại một
hàm nào có thể chứng minh đƣợc là hàm một chiều.
Ví dụ 1. Cho p là một số nguyên tố và  là một phần tử nguyên thuỷ theo modulo p.
Hàm số y = x modp (từ Z *p vào Z *p ) là một hàm một chiều vì hàm ngƣợc của nó, tính x
từ y mà ta ký hiệu x = loga ( y) là một hàm có độ phức tạp tính tốn rất lớn.
Ví dụ 2. Cho n =p.q là tích của hai số nguyên tố lớn. Hàm số y = x 2 modn (từ Zn vào
Zn ) cũng đƣợc xem là một hàm một phía.
Ví dụ 3. Cho n =p.q là tích của hai số nguyên tố lớn, a là một số nguyên sao cho
gcd(a, (n)) =1. Hàm số y = x a modn (từ Zn vào Zn ) cũng là một hàm một phía, nếu
giả thiết là biết n nhƣng không biết p, q.
Để xây dựng một hệ mật mã khố cơng khai thì việc tìm đƣợc một hàm một
chiều vẫn chƣa đủ. ek không phải là hàm một chiều đối với Bob vì anh ta phải có khả
năng giải mã các bản tin nhận đƣợc một cách hiệu quả. Điều cần thiết là Bob phải có
một cửa sập chứa thơng tin bí mật cho phép dễ dàng tìm hàm ngƣợc của ek. Nhƣ vậy
Bob có thể giải mã một cách hữu hiệu vì anh ta có một hiểu biết tuyệt mật nào đó về
K. Bởi vậy một hàm đƣợc gọi là cửa sập một chiều nếu nó là hàm một chiều và nó trở

nên dễ tính ngƣợc nếu biết một cửa sập nhất định.
Khái niệm: Hàm y = f (x ) đƣợc gọi là hàm cửa sập một chiều (trapdoor oneway function), nếu việc tính thuận từ x ra y là “dễ”, việc tính ngƣợc từ y tìm lại x là rất
“khó”, nhƣng có một cửa sập z để với sự trợ giúp của cửa sập z thì việc tính x từ y và z
lại trở thành dễ.
Ví dụ 4. Hàm số y = x a modn khi biết p và q là hàm cửa sập một chiều. Từ x tính y là
dễ, từ y tìm x (nếu chỉ biết n, a) là rất khó, nhƣng vì biết p và q nên tính đƣợc (n) =
(p-1)(q-1), và dùng thuật tốn Euclide mở rộng tìm đƣợc b sao cho a.b  1 (mod(n)) ,
từ đó dễ tính đƣợc x = y b modn . Ở đây, có thể xem b là cửa sập.

94


Giáo trình Bảo mật thơng tin

4.1.4. Định nghĩa hệ mật mã khóa cơng khai
Sơ đồ chung của hệ mật mã khố cơng khai đƣợc cho bởi S = (P, C, K, E, D)
trong đó P là tập ký tự bản rõ, C là tập ký tự bản mã, K là tập các khố, mỗi khố K
gồm có hai phần K = (K’, K''), K' là khố cơng khai dành cho việc lập mật mã, cịn K''
là khố bí mật dành cho việc giải mã. Với mỗi ký tự bản rõ xP, thuật toán lập mã E
cho ta ký tự mã tƣơng ứng y =E(K', x)  C , và với ký tự mã y thuật toán giải mã D sẽ
cho ta lại ký tự bản rõ x: D (K'', y) = D (K'', E (K', x)) = x
4.2. Kiểm tra tính ngun tố theo xác suất
Các thuật tốn mã hóa khóa cơng khai đều cần phải sử dụng các số nguyên tố.
Có một số phƣơng pháp để sinh số nguyên tố và hầu hết chúng đều dựa trên các thuật
toán kiểm tra tính nguyên tố của một số nguyên.
Các thuật toán kiểm tra số nguyên tố đƣợc chia làm hai loại: thuật toán tất định
và thuật toán xác suất. Các thuật tốn tất định cho biết chính xác câu trả lời một số
nguyên có phải là một số nguyên tố hay khơng, cịn thuật tốn xác suất cho biết xác
suất của một số nguyên là số nguyên tố là bao nhiêu.
Các thuật toán xác suất thƣờng đƣợc xây dựng cho các bài toán quyết định, tức

các bài toán xác định trên một tập hợp dữ liệu sao cho ứng với mỗi dữ liệu bài tốn có
một trả lời có hoặc khơng. Ngƣời ta chia các thuật tốn xác suất thành hai loại: loại
thuật toán Monte Carlo và loại thuật toán Las Vegas. Thuật tốn Monte Carlo ln kết
thúc với kết quả có hoặc khơng đối với mọi dữ liệu đầu vào bất kỳ; cịn thuật tốn Las
Vegas tuy cũng kết thúc với mọi dữ liệu, nhƣng có thể kết thúc với một thơng báo
khơng có trả lời có hoặc khơng.
Thuật tốn Monte Carlo đƣợc gọi là thiên về có, nếu nó cho trả lời có thì trả lời
đó chắc chắn là đúng, cịn nếu nó cho trả lời khơng thì trả lời đó có thể sai với một xác
suất  nào đó. Tƣơng tự, một thuật tốn Monte Carlo đƣợc gọi là thiên về khơng, nếu
nó cho trả lời khơng thì trả lời đó chắc chắn là đúng, cịn nếu nó cho trả lời có thì trả
lời đó có thể sai với một xác suất  nào đó.
Cịn với thuật tốn Las Vegas, nếu nó kết thúc với trả lời có hoặc khơng, thì trả
lời đó chắc chắn đúng, và nó có thể kết thúc với thơng báo khơng có trả lời với một
xác suất  nào đó.

95


Giáo trình Bảo mật thơng tin

4.2.1. Một số khái niệm và định nghĩa
Một bài toán quyết định là một bài tốn trong đó một câu hỏi cần đƣợc trả lời
có hoặc khơng. Một thuật tốn xác suất là một thuật tốn bất kỳ có sử dụng các số
ngẫu nhiên (ngƣợc lại, thuật tố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 tốn xác suất cho các
bài toán quyết định.
Định nghĩa 1: Thuật toán Monte Carlo định hƣớng “có” là một thuật tốn xác suất
cho một bài tốn quyết định, trong đó câu trả lời “có” ln ln là đúng cịn câu trả lời
“khơng” có thể là sai.
Thuật tốn Monte Carlo định hƣớng “khơng” cũng đƣợc định nghĩa theo cách

tƣơng tự.
Ta nói rằng, một thuật tốn Monte Carlo định hƣớng “có” có xác suất sai bằng 
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 tốn có câu trả lời sai
“không” với xác suất không lớn hơn  (xác suất này đƣợc tính trên mọi phép chọn ngẫu
nhiên).
Bài toán hợp số: Cho số nguyên dƣơng n ≥ 2. Hỏi n có phải là hợp số hay
khơng?
Phần sau sẽ mơ tả hai thuật tốn Soloway - Strasson và Miler Rabin để giải
quyết bài toán này. Đây là các thuật tốn Monte- Carlo định hƣớng “có” cho bài tốn
hợp số và xác xuất sai 1/2. Bởi vậy, nếu thuật tốn trả lời “có” thì n là hợp số; ngƣợc
lại nếu n khơng là hợp số thì thuật tốn trả lời “có” với xác xuất tối thiểu 1/2.
Định nghĩa 2: Phƣơng trình đồng dƣ bậc hai và thặng dƣ bậc hai
Phƣơng trình đồng dƣ bậc hai có dạng x2 = a (mod n) (1) với n nguyên dƣơng, a
nguyên thỏa mãn điều kiện gcd(a,n) = 1.
Nếu phƣơng trình (1) có nghiệm thì ta nói a là thặng dƣ bậc hai theo modulo n,
ngƣợc lại nếu phƣơng trình vơ nghiệm, a đƣợc gọi là một bất thặng dƣ bậc hai theo
modulo n.
Ví dụ: Các thặng dƣ bậc hai theo modulo 11 là 1, 3, 4, 5 và 9 vì (1)2 = 1, (5)2
= 3, (2)2 = 4, (4)2 = 5, (3)2 = 9 (các phép số học đều thực hiện trong Z11).
Tập các thặng dƣ bậc hai theo modulo n đƣợc ký hiệu là Qn, tập các bất thặng
dƣ bậc hai theo modulo n đƣợc ký hiệu là

96


Giáo trình Bảo mật thơng tin

Định lý: Nếu p là một số nguyên tố và  là một phần tử sinh của Z*p, khi đó a
là một thặng dƣ bậc hai theo modulo p khi và chỉ khi a = i mod p, trong đó i là một số
nguyên chẵn.

Từ định lý trên suy ra  Qn = 

 = (p-1)/2, hay tập Z*n đƣợc phân hoạch thành

2 tập con Qn và
Ví dụ với p = 13,  = 6  Z*13 ta có

Vậy Q13 = {1, 3, 4, 9, 10, 12} và

= {2, 5, 6, 7, 8, 11}

Tiêu chuẩn Euler: Nếu p là số nguyên tố, a là thặng dƣ bậc hai theo modulo p khi và
chỉ khi
Định nghĩa 3: Ký hiệu Legendre
Giả sử p là một số nguyên tố lẻ, với một số nguyên a bất kỳ a ≥ 0, ta định nghĩa
ký hiệu Legendre

nhƣ sau

Theo tiêu chuẩn Euler: 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). Nếu a không là
một thặng dƣ bậc hai theo modulo p thì a(p-1)/2 -1 (mod p) vì ap-1  1(mod p). Vậy ký
hiệu Legendre đƣợc đánh giá theo định lý sau:
Định lý: Giả sử p là một số nguyên tố, khi đó

 a(p-1)/2 (mod p).

Ví dụ: p = 13
L(9/13) = 96 mod 13  1 mod 13
L(6/13) = 66 mod 13  12 mod 13  -1 mod 13

Định nghĩa 4: Ký hiệu Jacobi

97


Giáo trình Bảo mật thơng tin

Ký hiệu Jacobi

là sự khái quát hóa của ký hiệu Legendre, nó định nghĩa

cho bất kỳ cặp số nguyên a và n nào.
Định nghĩa
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:

Nếu n là số nguyên tố thì ký hiệu Jacobi và Legendre là đồng nhất
Trên thực tế có thể tính đƣợc ký hiệu Jacobi một cách thuận lợi nhờ các tính chất sau:

 

1. Nếu n là một số nguyên tố lẻ và m1  m2 (mod n) thì:  1    2 
m

m

 n   n 


 


2. Nếu n là một số nguyên lẻ thì
1 nếu n   1 (mod 8)
-1 nếun   3 (mod 8)
3. Nếu n là một số nguyên lẻ thì

 m1m2   m1  m2 

   

 n   n  n 
Đặc biệt nếu m=2kt với t là một số lẻ thì:
k

m
2  t 

   
 n 
n n
4. Giả sử m và n là các số nguyên lẻ, khi đó:

98


Giáo trình Bảo mật thơng tin


Ví dụ 1: Tính ký hiệu Jacobi
Phân tích lũy thừa nguyên của 9975 = 3 . 52 . 7. 19. Vậy ta có:
2

 6278   6278  6278   6278  6278 



 


 9975   3  5   7  19 
2

 2  3   6  8 
2
         1 1  1 1
 3  5   7  19 
 - 1.

Ví dụ 2: Tính kí hiệu Jacobi
 7411 
 9283 

  

 9283 
 7411 

=


 1872 


 7411 

4
=   2   117 
 7411   7411 

 7411 


 9283 

theo tính chất 4

theo tính chất 1
theo tính chất 3

=

 117 


 7411 

theo tính chất 2

=


 7411 


 117 

theo tính chất 4

=

 40 


 177 

theo tính chất 1

3
=   2   5 
 117   117 

theo tính chất 3

=

 5 


 117 


theo tính chất 2

=

 117 


 5 

theo tính chất 4

=

2
 
 5

theo tính chất 1

= -1
theo tính chất 2
Nói chung, bằng cách áp dụng 4 tính chất trên, có thể tính tốn kí hiệu Jacobi
trong thời gian đa thức. Các phép tính số học ở đây chỉ là rút gọn theo modulo và
phân tích ra các thừa số nguyên tố. Bởi vậy, độ phức tạp của thuật toán đƣợc xác định

99


Giáo trình Bảo mật thơng tin


bởi số các phép rút gọn theo modulo cần tiến hành 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 logn. 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).
4.2.2. Thuật toán kiểm tra số nguyên tố theo xác suất
a. Thuật toán Solova – Strassen
Thuật toán Solovay-Strassen là một trong các phƣơng pháp kiểm tra tính
nguyên tố theo xác suất do Robert M. Solovay và Volker Strassen phát triển
Định nghĩa Số giả nguyên tố Euler
Xem tiêu chuẩn Euler là mệnh đề Q(p,a). Khi đó Q(p,a) đúng với mọi số nguyên tố p
và mọi số tự nhiên a, 1 < a < p. Thay số nguyên tố p bằng số lẻ n và ký hiệu Legendre bằng
ký hiệu Jacobi, ta định nghĩa: Hợp số n đƣợc gọi là số giả nguyên tố Euler cơ sở a (1 < a < p)
nếu:

trong đó

là ký hiệu Jacobi.

Giải thuật Solova - Strassen
Input: n là số tự nhiên lẻ
Output: FALSE nếu n là hợp số, TRUE nếu n là số nguyên tố
1. Chọn a ngẫu nhiên trong khoảng[1, n-1]
2. Tính ký hiệu Jacobi J=
3. Tính x =a (n-1)/2 mod n
4. Nếu J ≠ x thì trả về FALSE
nếu khác trả về TRUE.
b. Thuật toán Miller – Rabin
Thuật toán Miller-Rabin là một thuật toán xác suất để kiểm tra tính nguyên tố
đƣợc đề xuất đầu tiên bởi Gary L. Miller nhƣ một thuật toán tất định, dựa trên giả thiết
Riemann tổng quát; Michael O. Rabin đã sửa chữa nó thành một thuật tốn xác suất.

Tiêu chuẩn Miler-Rabin
Giả sử p là một số nguyên tố lẻ, khi đó p - 1 là số chẵn và ta có thể viết p − 1
dƣới dạng 2s.m, trong đó s là một số tự nhiên ≥ 1 và m là số lẻ. Điều này nghĩa là ta rút
hết các thừa số 2 khỏi p − 1. Lấy số a bất kỳ trong tập {1,2,..,p-1}.

100


Giáo trình Bảo mật thơng tin

với k = 0, 1, 2,..., s. Khi đó xk = (xk − 1)2, với k=1,2,...,s và

Xét dãy số xk =
xs = p &minus 1.

Từ định lý Fermat nhỏ: ap-1  1 (mod p) hay xs  1 (mod p) hay xs-1  1 (modp)
Do đó, hoặc xs-1  1 (mod p) hoặc xs-1  -1 (mod p)
Nếu xs-1  -1 (mod p) ta dừng lại, còn nếu ngƣợc lại ta tiếp tục với xs − 2.
Sau một số hữu hạn bƣớc


hoặc ta có một chỉ số k, 0 ≤ k ≤ s-1 sao cho xk  -1 (mod p),



hoặc tới k=0 ta vẫn có xk  1 (mod p) .

Ta có mệnh đề Q(p,a) nhƣ sau:
Nếu p là số nguyên tố lẻ và p - 1 = 2s.m thì với mọi a: 0

hoặc xk =

 1 (mod p), với mọi k=0,1,2,...,s

hoặc tồn tai k: 0 ≤ k ≤ s sao cho xk =

 -1 (mod p).

Giải thuật Miller-Rabin
Input: Số tự nhiên lẻ n.
Output: NguyenTo: TRUE/FALSE
1. Phân tích n-1 = 2s.m trong đó s ≥ 1và m là số tự nhiên lẻ
2. Chọn ngẫu nhiên số tự nhiên a {2,...,n-1}.
3. Đặt b = am(mod n)
4. Nếu bb1 (mod n) thì trả về TRUE. Kết thúc.
5. Cho k chạy từ 0 đến s-1:
1. Nếu b -1 (mod n) thì trả về TRUE. Kết thúc.
2. Thay b = b2(mod n).
6. Trả lời FALSE. Kết thúc.
4.3. Một số kiến thức toán học
4.3.1. Định lý phần dƣ China
Định lý phần dƣ China là một phƣơng pháp giải các hệ phƣơng trình đồng dƣ.
Giả sử m1,…, mk là các số nguyên tố cùng nhau từng đôi một (tức là gcd(mi, mj) =1
nếu ji), a1,. . ., ak là các số nguyên, xét hệ phƣơng trình đồng dƣ sau:

101


Giáo trình Bảo mật thơng tin

Định lý phần dƣ China
Giả sử m1,…,mk là các số nguyên dƣơng nguyên tố cùng nhau từng đôi một và
a1,…, ak là các số nguyên. Khi đó, hệ k đồng dƣ thức x  ai (mod mi) (1  i  k ) sẽ có
một nghiệm duy nhất theo modulo M = m1.m2…mk đƣợc cho theo cơng thức
x=
trong đó Mi =

, yi = Mi-1 mod mi với 1  i  r.

Ví dụ: giải hệ phƣơng trình đồng dƣ
x  2 (mod 3)
x  3 (mod 5)
x  9 (mod 11)
Ta có M = m1.m2.m3 = 3. 5. 11 = 165
M1 =

= 55  y1 = 55-1 mod 3 = 1

M2 =

= 33  y1 = 33-1 mod 5 = 2

M3 =

= 15  y1 = 15-1 mod 11 = 3

 x = 2. 55. 1 + 3. 33. 2 + 9. 15. 3 (mod 165) = 53 (mod 165)
4.3.2. Một số định lý số học
a. Định lý Ferma:

Nếu p là số nguyên tố, a là số nguyên thì ap  a (mod p)
Nếu p khơng chia hết cho a thì ap-1  1 (mod p)
Ví dụ: 47  4 (mod 7); 47-1 = 46  1 (mod 7)
b. Định lý Euler:
Nếu gcd(a, n) = 1 thì a(n)  1 (mod n)
Trƣờng hợp n là số nguyên tố ta có định lý Ferma

102


Giáo trình Bảo mật thơng tin

Ví dụ: n = 10, (n) = (2). (5) = 1*4 = 4
Ta có 74  1 (mod 10); 94  1 (mod 10); 214  1 (mod 10);
Hệ quả 1:
Nếu gcd(a, n) =1 và a  b(mod(n) ) với a, b là các số tự nhiên thì ca  cb (mod n)
hay ca  ca mod(n) mod n
Chứng minh
Vì a  b(mod(n) )  a = b + k. (n)
 ca = c b + k. (n) = cb. c k. (n) = cb. (c(n))k
Vì gcd(c,m) = 1 nên theo định lý Euler c(n)  1 mod n
 ca  cb modm
Nhận xét: Hệ quả này làm giảm nhẹ việc tính tốn đồng dƣ của lũy thừa lớn
Ví dụ: Tính 21004 mod 15
Ta có (15) = (3). (5) = 2*4 = 8
 21004mod 15  21004 mod8 mod 15 = 24 mod 15  1 (mod 15)
Hệ quả 2:
Nếu các số nguyên dƣơng e và d thỏa mãn e.d  1 (mod (n)) thì với mọi số
nguyên x nguyên tố cùng nhau với n ta có (xe)d  x (mod n)
Hệ quả này đóng vai trò then chốt trong việc thiết lập các hệ mã mũ.

c. Định lý Lagrange
Theo định lý Euler a  Z*n : a(n)  1 mod n
Vậy tập Z*n có thể biểu diễn dƣới dạng Z*n = {a Zn : a(n)  1 mod n }
Cấp (bậc) của một phần tử:
t đƣợc gọi là bậc của a  Z*n nếu t là số nhỏ nhất thỏa mãn at  1 mod n
Ví dụ: n = 21  (n) = (3). (7) = 2. 6 =12  tập Z*21 có 12 phần tử và có bậc tƣơng
ứng nhƣ sau:

Định lý Lagrange:
Giả sử G là một nhóm cấp n và g  G. Khi đó cấp của g là ƣớc của n.

103


Giáo trình Bảo mật thơng tin

4.3.3. Phần tử ngun thủy
Từ định lý Lagrange: nếu p là số nguyên tố thì Zp* là một nhóm cấp p-1 và một
phần tử bất kì trong Zp* sẽ có bậc là ƣớc của p-1.
Nếu p là số ngun tố thì nhóm Zp* là nhóm cyclic khi đó tồn tại một phần tử 
 Zp* có cấp bằng p-1. Phần tử  có cấp p-1 đƣợc gọi là phần tử nguyên thuỷ (phần tử
sinh) modulo p.
 là phần tử nguyên thuỷ theo modulo p thì các phần tử 0, 1,… p-2 đều khác
nhau theo modulo p và lập thành Z*p = {i : 0  i  p-2}
Một phần tử bất kì   Zp* có thể đƣợc viết là  = i, trong đó 0  i  p-2 (theo một
cách duy nhất ). Cấp của  = i đƣợc tính theo cơng thức:

p -1
UCLN(p - 1, i)
Nhƣ vậy bản thân  là phần tử nguyên thuỷ khi và chỉ khi UCLN(p-1, i) = 1. Do đó số

các phần tử nguyên thuỷ theo modulo p là (p-1).
Ví dụ :
Xét p=13.
Bằng cách tính các luỹ thừa liên tiếp
nguyên thuỷ theo modulo 13:
20 mod 13 =1
21 mod 13 =2
23 mod 13 =8
24 mod 13 =3
26 mod 13 =12
27 mod 13 =11

của 2 ta có thể thấy rằng 2 là phần tử
22 mod 13 =4
25 mod 13 =6
28 mod 13 =9

29 mod 13 =5
210 mod 13 =10
211 mod 13 =7
Phần tử 2i là nguyên thuỷ khi và chỉ khi gcd(i,12) = 1; nghĩa là i = 1, 5, 7, 11. Bởi
vậy các phần tử nguyên thuỷ theo modulo 13 là 2, 6, 7 và 11.
Tính chất của phần tử nguyên thủy
1. Với mọi số nguyên tố p, Zp * là nhóm cyclic và có (p-1) phần tử nguyên thuỷ.
2. Nếu p-1 =
 1; …;

.

là khai triển chính tắc của p -1, và nếu

1

thì a là phần tử nguyên thuỷ theo modp (tức của Zp * )
3. Nếu g là phần tử nguyên thuỷ theo modp thì   gi modp i mà gcd(i, p -1) = 1
cũng là phần tử nguyên thuỷ theo modp .

104


Giáo trình Bảo mật thơng tin

4.3.4. Tính đồng dƣ của lũy thừa lớn (xe mod n)
Nếu e > (n) ta dùng hệ quả 1 của định lý Euler để làm giảm số mũ
Nếu e < (n) ta có hai thuật tốn hữu hiệu để tính, đó là thuật tốn bình phương
và nhân và thuật tốn bình phương liên tiếp.
Thuật tốn bình phƣơng và nhân:
Thuật tốn bình phƣơng và nhân là thuật tốn tính nhanh lũy thừa tự nhiên của
một số (thực hoặc nguyên), trong trƣờng hợp cơ số là số ngun có thể đƣợc rút gọn
theo một mơđun nào đó.
Phép nâng lên lũy thừa tự nhiên bậc n của số x (x đƣợc gọi là cơ số) đƣợc định
nghĩa từ hệ thức

Với n lớn số phép nhân là rất lớn.
Ví dụ với n=35 q trình tính x35 qua 35 bƣớc:
Nhận xét rằng có thể giảm bớt số phép nhân chẳng hạn với dãy phép tính
,

,
,

.

Q trình tính tốn trên chính là q trình tính nhờ cơng thức đệ quy
1. Với n = 0 thì xn = 1
2. Với n > 0 ta có cơng thức

Nhƣ vậy phép tính xn đƣợc quy về một số phép bình phƣơng và phép nhân do
vậy mà có tên gọi thuật tốn bình phƣơng và nhân.
Trong giải thuật đệ quy trên đây ta xét tính chẵn lẻ của n và liên tục chia n cho
2 lấy phần nguyên cho đến khi n=0. Thực chất quá trình này chính là tìm các bít của n.
Do đó ta có thể thực hiện phép đổi ra số nhị phân trƣớc sau đó tính lũy thừa theo quy
tắc bình phƣơng và nhân.
Các bƣớc thực hiện:

105


Giáo trình Bảo mật thơng tin

Bƣớc 1: Biểu diễn số mũ e dƣới dạng nhị phân e =
Bƣớc 2: y =1;
for (i = l-1; i>=0; i--)
if (bi) y = x.y2 mod n ; else y = y2mod n;
Bƣớc 3: return y;
Ví dụ:
Tính y = 97263533 mod 11413
Bƣớc 1: Phân tích 3533 dƣới dạng nhị phân: 110111001101
Bƣớc 2:
i

bi

y

11

1

12 9726 = 9726

10

1

97262  9726 = 2659

9

0

26592 = 5634

8

1

56342  9726 = 9167

7

1

91672  9726 = 4958

6

1

49582  9726 = 7783

5

0

77832 = 6298

4

0

62982 = 4629

3

1

46292  9726 = 10185

2

1

101852  9726 = 105

1

0

1052 = 11025

0

1

110252  9726 = 5761

Vậy 97263533 mod 11413 = 5761.
Thuật tốn bình phƣơng liên tiếp
Bƣớc 1: Biểu diễn số mũ e dƣới dạng nhị phân e =
Bƣớc 2: Liên tiếp tính các đồng dƣ bình phƣơng
mod n
Bƣớc 3: Lấy tích của các lũy thừa tƣơng ứng với các bi ≠ 0, rút gọn theo
modulo n.
Ví dụ: Tính y = 8743 mod 103

106


Giáo trình Bảo mật thơng tin

Bƣớc 1: Phân tích 43 = 25 + 23 + 21 + 20
Bƣớc 2: Tính liên tiếp các đồng dƣ bình phƣơng
= 87 (mod 103) = 87
= 872(mod 103) = 50
= 874 (mod 103) = 502 (mod 103) = 28
= 878 (mod 103) = 282 (mod 103) = 63
= 8716 (mod 103) = 632 (mod 103) = 55
= 8732 (mod 103) = 552 (mod 103) = 38
Bƣớc 3: Lấy tích của các lũy thừa bậc 25, 23, 21, 20 rút gọn theo modulo 130
y = 8743(mod 103) = 38. 63. 50. 87 (mod 103) =85 (mod 103)
4.4. Hệ mật mã RSA
Hệ mật mã RSA đƣợc đặt tên dựa theo các chữ cái đầu của 3 tác giả của hệ mật
là Rivest, Shamir và Adleman. Đây là thuật tốn mã hóa nổi tiếng nhất và cũng là
thuật toán đƣợc ứng dụng thực tế nhất.
Hệ mật RSA sử dụng các tính tốn trong Zn, trong đó n là tích của 2 số nguyên
tố phân biệt p và q (n đƣợc gọi là số nguyên Blum).
4.4.1 Định nghĩa
Sơ đồ hệ mật mã RSA là một bộ gồm 5 thành phần (P, C, K, E, D),
trong đó: P = C = Zn , với n là một số nguyên Blum, tức là tích của hai số nguyên tố;
K = {K = (K’, K''): K' = (n,e) và K'' = d, gcd(e,  (n)) =1, e.d  1(mod (n))};
E và D đƣợc xác định bởi:
E (K', x) = xe modn  x P ,
D (K'', y) = yd modn  y C .
Để chứng tỏ định nghĩa trên là hợp thức, cần chứng minh với mọi cặp khoá K =
(K', K'' ) và mọi x P, ta đều có D (K'', E (K', x)) = x.
Thực vậy, do e.d  1(mod (n)) ta có thể viết e.d = t . (n) +1.
Nếu x nguyên tố với n , thì theo định lý Euler ta có
ed
t ( n ) 1
 xt ( n ) .x (mod n)  x.

D (K'', E (K', x)) = x  x

107


Giáo trình Bảo mật thơng tin

Nếu x khơng ngun tố với n , thì do n =p.q, hoặc x chia hết cho p và nguyên tố
với q, hoặc x chia hết cho q và nguyên tố với p, và  (n) =(p -1).(q -1), trong cả hai
trƣờng hợp ta đều có

x t ( n ) 1  x (mod p ),
x t ( n ) 1  x (mod q );
từ đó suy ra

xt ( n ) 1  x (mod n), tức D (K'', E (K', x)) = x.

Ví dụ:
Chọn n = p.q = 61.53 = 3233  (n) = 60.52 = 3120
Chọn e = 17 thỏa mãn gcd(e, (n) ) =1
 d = e-1 mod (n) = 17-1 mod 3120 = 2753
Công khai K‟ = (n, e), giữ bí mật p,q và khóa K” = d
Hàm mã hóa y = eK‟(x) = xe mod n = x17mod 3233
Hàm giải mã x = dK”(y) = yd mod n = y2753 mod 3233
Giả sử cần mã hóa tài liệu x = 123 ta tính y = 12317mod 3233 = 855
Để giải mã văn bản y = 855 ta tính x = 8552753mod 3233 = 123.
4.4.2. Thực hiện hệ mật mã RSA
Giả sử Alice cần gửi bản tin mật cho Bob
-

Bob tạo hai số nguyên tố lớn p và q
Bob tính n = p.q và (n) = (p-1)(q-1)
Bob chọn một số ngẫu nhiên e (0< e < (n)) sao cho gcd(e,(n)) = 1
Bob tính d = e-1 mod (n) bằng cách dùng thuật tốn Euclide
Bob cơng bố n và e trong một danh bạ và chúng làm khố cơng khai.

-

Alice sử dụng khóa cơng khai (n, e) để mã hóa bản tin gửi cho Bob, Bob nhận
đƣợc bản mã sẽ dùng khóa bí mật d để giải mã.
Cách tấn cơng dễ thấy nhất hệ mật này là thám mã phân tích số n ra thừa số

nguyên tố để tính đƣợc (n) = (p-1)(q-1) sau đó tính d từ e thu đƣợc. Vì thế để hệ mật
RSA đƣợc coi là an tồn thì n phải là số đủ lớn để việc phân tích nó khơng có khả
năng về mặt tính tốn. Các thuật tốn phân tích hiện thời có khả năng phân tích các số
có 130 chữ số thập phân, vì vậy để đảm bảo an toàn nên chọn các số p và q khoảng
150 chữ số, khi đó n có khoảng 200 chữ số.
4.4.3. Tính bảo mật của hệ mật mã RSA
Bài toán thám mã (khi chỉ biết bản mã):
Biết khoá công khai K' = (n,e) và bản mã y = x e modn. Tìm bản rõ x.

108


Giáo trình Bảo mật thơng tin

Đây chính là bài tốn RSA. Nếu biết hai thừa số p, q của n thì dễ tìm đƣợc x từ
y, và nói chung bài tốn RSA (hay bài tốn thám mã RSA) là có độ khó tƣơng đƣơng
với bài tốn phân tích số ngun (Blum) thành thừa số nguyên tố. Do đó, giữ tuyệt mật
khố bí mật d , hay giữ tuyệt mật các thừa số p, q có ý nghĩa quyết định đến việc bảo

vệ tính an tồn của hệ mật mã RSA.
Một mạng truyền tin bảo mật sử dụng sơ đồ các hệ mật mã RSA đƣợc xem là
an toàn nếu tuân thủ các điều kiện cơ bản: mỗi ngƣời tham gia phải độc lập lựa chọn
các tham số n, e, d của riêng mình, chọn n cũng có nghĩa là chọn các thừa số p, q của
n (n =p.q) và do có p,q nên tính đƣợc  (n) = (p-1).(q-1), từ đó tìm đƣợc e, d tƣơng đối
dễ dàng; nhƣng cũng vì vậy mà sau khi đã chọn thì mỗi ngƣời tham gia phải giữ tuyệt
đối bí mật các giá trị p, q, d , chỉ cơng bố khố cơng khai (n, e)
Tuy nhiên, đó là điều kiện chung, trong thực tế vẫn có thể cịn nhiều sơ hở mà
ngƣời thám mã có thể lợi dụng để tấn cơng vào tính bảo mật của các hệ mã RSA .
4.4.4. Các phƣơng pháp tấn công hệ mật mã RSA
Đặt 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 ?
Nếu thám mã tính đƣợc (n): Nếu đã biết n, (n) và n là tích của 2 số
ngun 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=p*q
(n)=(p-1)*(q-1)
Nếu thay q=n/p vào 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- (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. Nhƣ vậy thám mã biết
đƣợc (n) thì có thể phân tích đƣợc n và phá đƣợc hệ mật.
Ví dụ: Giả sử thám mã đã biết đƣợc n = 84773093 và (n) = 4754668, thông tin này
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 là hai thừa số của n.
a. Số mũ giải mã
Một kết quả đã đƣợc chứng minh là một thuật toán bất kỳ để tính số mũ giải mã
d đề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

109

Giáo trình Bảo mật thơng tin

xác suất phân tích n. Bởi vậy việc tính d khơng dễ hơn việc phân tích n. Tuy nhiên, có
một điều khơng ngồi quy luật là vẫn có thể phá hệ mật mà khơng cần tính d.
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 d bị lộ
thì giá trị n 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 tố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:
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 sao cho với một trƣờng hợp bất kỳ của bài tốn i, thuật tố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 tố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 tốn cho lời giải thì lời giải này là đúng .
Nhận xét: Thuật tố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 trả lời đúng. Ngƣợc lại, thuật tốn Monte Carlo ln luôn cho câu trả lời nhƣng câu trả lời này có thể sai.
Nếu ta có một thuật tốn Las Vegas để giải một bài tố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 tố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 trả lời thực tế là 1/.
Giả sử A là một thuật tốn giả định tính số mũ giải mã d từ e. Ta sẽ mơ tả một thuật
tốn Las Vegas dùng A nhƣ một chƣơng trình giả định (oracle) con. Thuật tố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 tố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 = p*q 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ƣ x2  1(mod q) cũng có hai nghiệm

là x = 1 mod q .
Vì x2  1 (mod n) khi và chỉ khi x2  1 (mod p) và x2  1 (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.

110


Giáo trình Bảo mật thơng tin

Ví dụ: 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ệ x  1 (mod 13) , x  -1 (mod 31) theo định lý phần dƣ
China. Nếu tìm đƣợc nghiệm 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), x  1 (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 gcd(x+1, n) =
p hoặc q(và tƣơng tự gcd(x-1, n) = p hoặc q). Tất nhiên có thể tính ƢCLN bằng thuật
tố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. Yếu tố quan trọng này là cơ sở của nhiều kết quả quan trong
mật mã.
Trong ví dụ trên, gcd(93, 403) = 31 và gcd(312, 403) = 13
Dƣới đây là thuật tốn 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ã d theo số mũ mã e).
1. Chọn w ngẫu nhiên sao cho 1 w  n-1
2. Tính x = gcd(w, n)

3. Nếu 1 < x < n thì kết thúc ( thành cơng x = p hoặc x = q)
4. Tính a = A(e)
5. Viết ed – 1 = 2s .r
( r lẻ)
r
6. Tính v = w mod n
7. Nếu v = 1 (mod n) thì kết thúc (khơng thành cơng)
8. While v  1 (mod n) do
9.

v0 = v

10.

v = v2 mod n

11. if v0  -1 (mod n) then kết thúc (khơng thành cơng)
Else

Tính x = gcd(v0+1, n)
(thành cơng x=p hoặc x=q)

Ví dụ:
Giả sử n = 89855713, e = 34986517 và d = 82330933 và giá trị ngẫu nhiên w = 5.
Ta có : ed – 1 = 23 . 360059073378795
Trong bƣớc 6, v = 85877701 còn ở bƣớc 10 v=1
Trong bƣớc 12 ta tính gcd(85877702, n) = 9103
Đây là một thừa số của n; thừa số kia là n/9103 = 9871.

111

Giáo trình Bảo mật thơng tin

Bây giờ sẽ tiến hành phân tích thuật tốn.
Trƣớc tiên, nhận thấy rằng nếu 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 w nguyên tố cùng
nhau với n thì ta sẽ tính wr, w2r, w4r,. . . bằng cách bình phƣơng liên tiếp cho tới khi w2t
 1 (mod n) với giá trị t nào đó.
Vì ed – 1 = 2s .r  0 (mod (n)) nên ta có

 1 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 v02  1 (mod n) nhƣng v0  1 (mod n). Nếu v0  -1(modn ) thì thuật tố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 tốn thành cơng
với xác suất là . Có hai cách mà theo đó thuật tốn có thể khơng thành cơng khi phân
tích n :
1. wr  1 (bƣớc 7)
2.

 -1 (mod n) với giá trị t nào đó 0 ≤ t ≤ s-t (bƣớc 11)

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 tố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 wr  1 (modn). 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 lẻ các nghiệm theo modulo q. Sau đó
kết hợp chúng nhờ định lý phần dƣ China. Chú ý rằng x  1 (mod n) khi và chỉ khi x 
1 (mod p) và x  1 (mod q).
Nhƣ vậy, trƣớc hết ta phải xét wr  1 (mod n) .Vì p là một số nguyên tố nên Z*p
là một nhóm cyclic. 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)
gur  1 (mod p)
(p-1) ur
Giả sử biểu diễn p-1 = 2i p1, trong đó p1 là một số lẻ và q -1 = 2jq1, q1 là một số
lẻ.
Vì (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

112


Giáo trình Bảo mật thơng tin

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 wr1 (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) 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 wr 1 (mod n ) sẽ là p1q1.
Tiếp theo, xét đồng dƣ thức

 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 đó xét theo modulo q.

(Để ý rằng

 1(mod n) khi và chỉ khi

 -1 (mod p) và

 -1 (mod q).

Đầu tiên ta xét w 2 r  1mod p  . Nếu viết w = gu nhƣ ở phần trên ta nhận
t

đƣợc: g u 2 r  1mod p 
t

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)
Loại bỏ thừa số chung ta có
Xét thấy nếu t  i thì có thể là khơng có nghiệm do 2i+1 │ 2t+1 nhƣng 2i+1 │ 2i

2

 u2 t  1 r

| 
 2 i 
 p1



i1

Mặt khác nếu t  i -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ƣờng hợp này là
p 1 1
t
 =2 p1
i t 1
2
2

Tƣơng tự, đồng dƣ thức w 2 r  1 (mod q) sẽ :
i

- Không có nghiệm nếu t  j
- 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 w 2 r  1mod n  là
i

- 0 nếu t  min{i, j}

113