Xem mẫu
- Giáo trình Bảo mật thông tin
CHƢƠNG 4: CÁC HỆ MẬT MÃ KHOÁ CÔNG KHAI
4.1. Giới thiệu về mật mã khoá 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 khoá K. Sau đó dùng K để tạo luật mã hoá 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 khoá 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ó yêu cầu phải có thông tin về khoá 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 khoá công khai (hay khoá dùng chung) là tìm
một hệ mật không có khả năng tính toá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 khoá công khai). Ƣu điểm của hệ mật khoá 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ề khoá 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 hoá 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 toán tính toán khác nhau.
89
- Giáo trình Bảo mật thông tin
4.1.1. Một số bài toá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ã khoá công khai
Bài toán phân tích số nguyên (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 toán này có liên hệ mật thiết với các bài toán thử tính nguyên 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ố nguyên Blum, tức các số nguyên dƣơng có dạng tích của hai số nguyên tố lớn nào
đó.
Bài toá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 toán RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số
nguyên.
Bài toá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 toá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 toán phân tích số nguyên. Mặt khác, nếu không biết cách phân
tích n thành thừa số nguyên 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 toá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
toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích
số nguyên.
Ngƣợc lại, nếu có thuật toán giải bài toán tìm căn bậc hai modn thì cũng có
thể xây dựng một thuật toán giải bài toá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 toá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 toá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 toán giải bài toán phân tích số nguyên (Blum) với thời gian trung bình đa thức.
Bài toá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 toá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 toá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ố hoá. Có thể phát biểu trực tiếp bài toá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 (1j 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ã khoá 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 toá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 toá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 toá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ã khoá công khai khác.
Một chú ý quan trọng là một hệ mật mã khoá công khai không bao giờ đảm bảo
đƣợc độ mật tuyệt đối (an toà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 toá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ã khoá công khai ek phải là một hàm dễ tính toá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 toán nhƣng khó tính toá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 khoá 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 toá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ã khoá 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 one-
way 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 toá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ã khoá 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 khoá, mỗi khoá K
gồm có hai phần K = (K’, K''), K' là khoá công khai dành cho việc lập mật mã, còn K''
là khoá bí mật dành cho việc giải mã. Với mỗi ký tự bản rõ xP, 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 nguyên tố theo xác suất
Các thuật toá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 toá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 toá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 toán có
một trả lời có hoặc không. Ngƣời ta chia các thuật toá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 toán Monte Carlo luôn 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 toá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 toá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 toá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 toá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 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 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ự.
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
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 (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 toán Soloway - Strasson và Miler Rabin để giải
quyết bài toán này. Đây là các 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 không 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.
Đị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:
m m
1. Nếu n là một số nguyên tố lẻ và m1 m2 (mod n) thì: 1 2
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
1 1 1 1
2
3 5 7 19
- 1.
Ví dụ 2: Tính kí hiệu Jacobi 7411
9283
7411 9283 theo tính chất 4
9283 7411
= 1872 theo tính chất 1
7411
4
= 2 117 theo tính chất 3
7411 7411
= 117 theo tính chất 2
7411
= 7411 theo tính chất 4
117
= 40 theo tính chất 1
177
3
= 2 5 theo tính chất 3
117 117
= 5 theo tính chất 2
117
= 117 theo tính chất 4
5
= 2 theo tính chất 1
5
= -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 toá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 toá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
Xét dãy số xk = với k = 0, 1, 2,..., s. Khi đó xk = (xk − 1)2, với k=1,2,...,s và
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
- 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 toá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ử nguyên 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ố nguyên 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 của 2 ta có thể thấy rằng 2 là phần tử
nguyên thuỷ theo modulo 13:
20 mod 13 =1 21 mod 13 =2 22 mod 13 =4
23 mod 13 =8 24 mod 13 =3 25 mod 13 =6
26 mod 13 =12 27 mod 13 =11 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 = . là khai triển chính tắc của p -1, và nếu
1; …; 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 toán hữu hiệu để tính, đó là thuật toán bình phương
và nhân và thuật toán bình phương liên tiếp.
Thuật toán bình phƣơng và nhân:
Thuật toán bình phƣơng và nhân là thuật toá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ố nguyên 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 quá 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
, ,
, .
Quá trình tính toán trên chính là quá 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 toá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 toá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 toá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 toá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ó
t ( n ) 1
D (K'', E (K', x)) = x x
ed
xt ( n ) .x (mod n) x.
107
- Giáo trình Bảo mật thông tin
Nếu x không nguyên 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 toán Euclide
- Bob công bố n và e trong một danh bạ và chúng làm khoá 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 toà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 toán. Các thuật toá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
nguon tai.lieu . vn
