Giáo trình An toàn bảo mật dữ liệu: Phần 2 - NXB Đại học Thái Nguyên
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (44.37 MB, 106 trang )
C hư ơ ng 3
M ẬT MÃ KHĨA CƠNG KHAI
3.1. Giói thiệu chung
Trong mơ hình mật mã chúng ta nghiên cứu cho đen nay (mật mã
khóa bí mật), Alice và Bob thoả thuận chọn một cách bí mật khố k. Từ k
người ta suy ra qui tắc mã hoá ek và qui tắc giải mã dk.Trong các hệ mật
này, chúng ta thấy dk hoặc trùng với ek, hoặc dễ dàng rút ra từ ek (ví dụ
phép giải mã DES nói chung đồng nhất với phép mã hoá, chỉ khác là
lược đồ khoá thỉ đào ngược). Các hệ mật loại này được gọi là hệ mật
khố bí mật (hoặc riêng, hoặc đối xứng), vì việc tiết lộ ek sẽ làm cho hệ
thống khơng an tồn.
Một đặc điểm của hệ mật khố bí mật là ở chỗ nó u cầu thoả thuận
về khoá giữa Alice và Bob bằng sử dụng kênh an toàn, trước khi bản mã
bất ki được truyền.Trong thực tế thực hiện điều này là rất khó.
Ý tưởng nằm sau hệ mật khố cơng khai là ở chỗ người ta có thể tìm
ra một hệ mật trong đó khơng thể tính tốn để xác định dk khi biết ek.
Nếu thế thỉ qui tắc mã ek có thể cho cơng khai bằng cách cơng bố nó
trong một thư mục (vì thế mới 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 ngirịi khác hất kỳ)
CĨ thể gửi thơng báo đã mã tới Bob (mà không cần liên lạc trước về khố
bí mật) bằng cách dùng qui tắc mã hố cơng khai eic- Bob sẽ là người duy
nhất có thể giải bản mã này bằng cách sử dụng qui tắc giải mã bí mật dk
của anh ta.
Ta có thể hình dung như sau: Alice đặt một vật vào hộp sắt sau đó
khố nó với cái khố bấm do Bob để lại. Bob là người duy nhất có thể
mờ hộp vi chỉ anh ta có chìa.
Một nhận xét rất quan trọng là hệ mật khố cơng khai có thể khơng
bao giờ cung cấp độ mật vơ điều kiện. Đó là vì bằng quan sát bản mã y,
đối phương có thể mã hố mỗi bản rõ có thể nhờ ek cho đến khi tìm thấy
132
X duy nhất thoả mãn y=ek(x). Nghiệm X này ià giải mã của y. Như vậy độ
an toàn của các hệ mật khố cơng khai là độ an tồn tính tốn.
Hàm mã hố cơng khai ẽk của Bob phải dễ dàng tính tốn. Chúng ta
chú ý rằng v iệ c tính h àm n g ư ợ c , n g h ĩa là v iệ c g iả i m ã, phái k h ó đ ố i v ớ i
bất kỳ người nào ngồi Bob. Tính chất dễ tính tốn và khó đảo ngược này
thương được gọi là tính chất một chiều (tựa như bán dẫn). Chúng ta
mong muốn rằng ek là hàm một chiều.
Các hàm một chiều đóng vai trị trung tâm trong mật mã, chúng
quan trọng đối với việc thiết lập các hệ mật khố cơng khai và trong các
nội dung khác. Đáng tiếc là, mặc dù có nhiều hàm được người ta tin là
hàm một chiều, nhưng hiện nay vẫn chưa có hàm nào được chứng minh
là hàm một chiều.
Nếu ta định thiết lập hệ mật khố cơng khai thì việc tìm hàm một
chiều là chưa đù. Bob muốn có thể giải mã các thơng báo nhận được một
cách có hiệu quả. Như vậy Bob cần có một cửa sập (trap door), nó chứa
thơng tin bí mật cho phép dễ dàng đảo ngược ek. Nghĩa là Bob có thể giải
mã hiệu quả vì anh ta có tri thức bí mật đặc biệt về k. Do đó ta nói rằng:
f(x) là hàm một chiều cửa sập nếu đó là hàm một chiều, nhưng nó trở nên
dễ đào nguợc khi có tri thức về cửa sập xác định. Nói chung, có những
cách để tìm cửa sập của hàm một chiều.
Sau dãy là một ví dụ về một hàm đưực coi là hàm mội chiều. Giả sử
n là tích của hai số nguyên tố lớn p và q, giả sử b là một số nguyên
dương. Khi đó ta xác định ánh xạ f : Zn -> Zn là f (x) = x b m od n (với b
và n đã được chọn thích hợp thì đây chính là hàm mã RSA, sau này ta sẽ
nói nhiều hơn về nó).
Ý tưởng về một hệ mật khố cơng khai được Diffie và Hellman đưa
ra vào năm 1976. Còn việc hiện thực hố nó thì do Rivesrt, Shamir và
Adleman đưa ra lần đẩu tiên vào năm 1977, họ đã tạo nên hệ mật nổi
tiếng RSA (sẽ được nghiên cứu trong chương này). Kể từ đó đã cơng bố
một số hệ, độ mật của chúng dựa trên các bài tính tốn khác nhau. Trong
đó, quan trọng nhất là các hệ mật khố công khai sau:
133
- Hệ mật RSA:
Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa
số ngun lớn.
- Hệ mật Rabin:
Độ bảo mật của hệ Rabin cũng dựa trên độ khó của việc phân tích ra
thừa số nguyên lớn.
- Hệ mật ElGamal:
Hệ mật ElGamal dựa trên tính khó giải của bài tốn logarit rịi rạc
trên các trường hữu hạn.
- Hệ mật trên các đường cong Elliptic:
Các hệ mật này là biến tướng của các hệ mật khác (chẳng hạn như
hệ mật ElGamal), chúng làm việc trên các đường cong Elliptic chứ không
phải là trên các trường hữu hạn. Hệ mật này đảm bảo độ mật với số khố
nhỏ hơn các hệ mật khố cơng khai khác.
- Hệ mật xếp ba lô Merkle - Hellman:
Hệ này và các hệ liên quan dựa trên tính khó giải của bài toán tổng
các tập con (bài toán này là bài toán NP đầy đủ - là một lớp khá lớn các
bài tốn khơng có giải thuật được biết trong thời gian đa thức). Tuy nhiên
tất cả các hệ mật xếp ba lô khác nhau đều đã bị chứng tỏ là không an toàn
(ngoại trừ hệ mật Chor-Rivest).
- Hệ mậtMcEliece:
Hệ này dựa trên lý thuyết mã đại số và vẫn còn được coi là an tồn.
Hệ mật McEliece dựa trên bài tố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 Chor-Rivest:
Hệ mật Chor-Rivest cũng được xem như một hệ mật xếp ba lô. Tuy
nhiên nó vẫn được coi là an tồn
134
3.2. Hệ m ật RSA
Bài tốn phân tích thừa số
Bài tốn phân tích một số ngun n >1 thành thừa số ngun tố
cũng được xem là một bài tốn khó thường được sử dụng trong lý
thuyết mật mã. Biết một số n là hợp số thì việc phân tích n thành thừa
số mới là có nghĩa, do đó thường khi để giải bài tốn phân tích n thành
thưa số, ta thử trước n có là hợp số hay khơng; và bài tốn phân tích n
thành thừa số có thể dẫn về bài tốn tìm một ước so của n, vì khi biết
một ước số d cùa n thì tiến trình phân tích n được tiếp tục thực hiện
bằng cách phân tích d và nịd.
Bài tốn phân tích thành thừa số, hay bài tốn tìm ước số của một số
ngun cho trước, đã được nghiên cứu nhiều, nhưng cũng chưa có một
thuật tốn hiệu quả nào để giải nó trong trường hợp tổng quát mà người
ta có xu hướng giải bài toán này theo những trường hợp đặc biệt của số
cần phải phân tích, chẳng hạn khi n có một ước số nguyên tố p với p - 1
là B-mịn với một cận B > 0 nào đó, hoặc khi n là số Blum, tức là số có
dạng tích của hai số nguyên tố lớn nào đó (n = p.q).
Ta xét trường hợp thứ nhất với (p - 1) - thuật toán Pollard như sau:
Một số nguyên n được gọi là B-mịn nếu tất cả các uớc số nguyên tố của
nó đều < B Ý chính chứa trong (p - 1) - thuật toán Pollard như sau: Giả
sừ
11 là B-m ịn. Kí liiệu Q là bội chung bó nhất của tất cả các lũy thừa cùa
các số nguyên tố < B mà bản thân chúng < n. Nếu q' < n thì /lnq < ln/7,
tức / <
ln/ỉ
ln q
(Ị_JCJ là số nguyên bé nhất lớn hơn x)
Ta có:
[lnn/lngj
e = n ?
q
Trong đó tích lấy theo tất cả các số nguyên tố khác nhau q < B. Nếu
p là một thừa số nguyên tố của n sao cho p - 1 là B-mịn thỉ p-l|Q và do
đó với mọi a bất kì thỏa mãn gcd(a, p) = 1, theo định lý Fermat ta có ay=
135
1 mod p. Vì vậy, nếu lấy d = gcd(aQ - 1 ,n) thì p|d. Neu d = n thì coi như
thuật tốn khơng cho ta điều mong muốn, tuy nhiên điều đó chắc khơng
xảy ra nếu n có ít nhất hai thừa số nguyên tố khác nhau. Từ những lập
luận đó ta có:
(p —l)-thuật tốn Pollard phân tích thành thừa số:
VÀO: một hợp số n không phải lũy thừa của một số nguyên tố
RA: một thừa số không tầm thường của n.
1. Chọn một cận cho độ mịn B
2. Chọn ngẫu nhiên một số nguyên a, 2 < a < n - 1, và tính d =
gcd(a, n). Nếu d > 2 thỉ cho ra kết quả (d)
3. Với mỗi số nguyên tố q < B thực hiện:
3.1. Tính / =
3.2. Tính a
ln n
ln q
mod n
4. Tính d = gcd(a - 1, n)
5. Nếu 1 < d < n thì cho ra kết quả (d). Nếu ngược lại thì thuật tốn
coi nhu khơng có kết quả.
Ví dụ 3.1. Dùng thuật toán cho số n = 19048567. Ta chọn B = 19, và
a = 3 và tính được gcd (3, n) = 1. Chuyến sang thực hiện bước 3 ta đuợc
bảng sau đây (mỗi hàng ứng với một giá trị của q):
Bảng 3.1. Kết quả tính bước 3 của thuật (oán Pollard
136
Q
L
A
2
24
2293244
3
15
13555889
5
10
16937223
7
8
15214586
11
6
9685355
13
6
13271154
17
5
11406961
19
5
554506
Sau đó ta tính d = gcd (554506 - 1, 19048567) = 5281. Vậy ta được
một thừa số p = 5281, và do đó một thừa số nữa là q = n/p = 3607. Cả hai
thừa số đó đều là số nguyên tố.
Chú ý rằng ở đây p - 1 = 25.3.5.11, có tất cả các ước số nguyên tố
đều < 19, do đó chắc chắn thuật tốn sẽ kết thúc có kết quả. Thuật tốn sẽ
kết thúc khơng có kết quả khi độ mịn B được chọn quá bé để không một
thùa số nguyên tố p nào của n mà p - 1 chỉ chứa các ước số nguyên tố <
B. Như vậy, có thể xem (p-l)-thuật tốn Pollard phân tích n thành thừa số
ngun tố là có hiệu quả đối với những số nguyên n là B-mịn, người ta
tính được thời gian cần để thực hiện thuật tốn đó là cỡ o (#ln/í/ln#)
phép nhân theo mơdulo.
Bây giờ ta xét trường hợp các số nguyên Blum, tức là các số có dạng
n = p.q, tích của hai số ngun tố lớn. Trước hết ta chú ý rằng nếu ta biết
hai số nguyên khác nhau
X,
V sao cho x2= y2 mod n thì ta dễ tìm được một
thừa số của n. Thực vậy, tị x2= y2 mod n ta có X2 - y2 = (x - y) (x + y)
chia hết cho n, do n không là ước số của X + y hoặc X - y nên gcd(x - y,
n) phải là một ước số của n, tức bằng p hoặc q.
Ta biết nếu n = p.q là số Blum thì phương trình đồng dư
x2= a2 mod n
có 4 nghiệm , hai nghiệm tầm thường là X = a và X = -a. Hai nghiệm
không tầm thường khác là ± b, chúng là nghiệm cùa hai hệ phương trình
đồng dư bậc nhất sau đây:
ỊX = a m o d p
\ x = —a m o d q
í x — a m°d p
[jf = a m o d q
137
Bằng lập luận như trên ta thấy rằng nếu n là số Blum, a là một số
nguyên tố với n và ta biết một nghiệm khơng tầm thường của phuơng
trình X = a2 mod n, tức biết một X í ± a sao cho x 2= a2 mod n thỉ gcd(x-a,
n) sẽ là một ước số của n. Những điều trên đây là căn cứ cho một số
phương pháp tìm ước số nguyên tố của một số nguyên dạng Blum; ý
chung của các phương pháp đó là dẫn về việc tim một nghiệm không tầm
thường của một phương trinh dạng X = a2 mod n, chẳng hạn như phương
trình X 3 1 mod n.
Một trường hợp khá lý thú trong lý thuyết mật mã là khi ta biết hai
số a, b là nghịch đảo của nhau theo mod <ị)(n) (nhung khơng biết ộ(n)) và
tìm một phân tích thành thừa số của n. Bài toán được đặt ra cụ thể là:
Biết n có dạng Blum, biết a và b sao cho ab = 1 mod <|)(n). Hãy tìm một
ước số nguyên tố của n, hay tỉm một nghiệm không tầm thường của
phương trình x2= 1 mod n. Ta giả thiết ab - 1 = 2s.r với r là số lẻ. Ta phát
triển một thuật toán xác suất kiểu Las Vegas như sau: Ta chọn một số
ngẫu nhiên V (1 < V < n - 1). Nếu may mắn V là bội số của p hay q, thỉ ta
đuợc ngay một ước số cùa n là gcd(v, n). Nếu V nguyên tố với n, thỉ ta
tính các bình phương liên tiếp kể từ vr, được vr, v2r, v4r,... cho đến khi
được vỉ r = lmodrt với một t nào đó. số t như vậy bao giờ cũng đạt được
vỉ có 2s.r = 0 mod ộ(n) nên có v i r = 1mod n Như vậy, ta đã tim được
'
2m r
một sô X = V
2
'
Ắ
sao cho X = 1 mod n. Tât nhiên có X Ỷ 1 mod n. Nêu
cũng có X Ỷ -1 m odn thì X là nghiệm khơng tầm th ư ờ ng của x 2= 1 mod n,
từ đó ta có thể tìm ước số của n. Nếu khơng thỉ thuật toán coi như thất
bại, cho ta kết quả khơng đúng. Người ta có thể ước lượng xác suất cho
kết quả
không đúng
với một lần thử với một số V là < 1/2, do đó nếu ta
th iế t k ế th u ậ t to á n v ớ i m s ố n g ẫ u n h iê n V i,
v m, th ì s ẽ c ó th ể đ ạt đư ợ c
xác suất cho kết quả khơng đúng là < l/2m!
3.2.1. Thuật tốn mã hóa, giải mã RSA
Giả sử n=p.q,trong đó p,q là hai số nguyên tố lẻ khác nhau và <ỉ>(n)
là hàm ơle. Hệ mật RSA được định nghĩa nhu sau:
138
Cho p = c = z n ; K={(n,p,q,a,b) : ab=l mod O(n)}
Với mỗi k=(n,p,q,a,b), quy tắc mã hóa và giải mã của hệ mật RSA
được xác định như sau:
ek(x)=xb mod n
và
dk(y)=yamod n
(x,yeZ n).
3.2.2. Kiểm tra qui tắc giải mã
Do
ab=l
mod
<t>(n),
0(n)= (p-l)(q-l)=
O(p)
O(q)
nên
ab=l+tO (n),với t là số nguyên khác 0. Chú ý rằng 0< X
(*) Giả sử (x ,n )= l, ta có
ya mod n = (xb)a mod n = x 1+tll)
(v ì (x,n) =1 nên x<I>(n>mod n= l)
= X ( do x
Nếu d=n thì X = 0 và đương nhiên y = 0. Do đó yamod n = 0 = X.
Giả sử d=p khi đó do 0< X
Ký hiệu
u = pabmodn;
Thế thì,
u +kn = pab, 0< u
u = p(pab_1-k:q) = p (p t<I>(n)-kq).
v ế phải chia hết cho p nên vế trái phải chia hết cho p, nghĩa là u
phải chia hết cho p. Nhung 0< u
tố khác nhau. Thế thì u=p=x, tức là yamod n
= X.
Vậy (xb)a mod n = X, V xe[l,n-1].
139
V í dụ 3.2.
Giả sử Bob chọn p = 101 và q = 113. Thế thỉ n= 11413 và
ơclit mờ rộng sẽ tìm được b '1=6597 mod 11200. Vỉ thế số mũ bí mật cúa
Bob là a=6597.
Bob công bố n =11413
và b =3533 trong thư mục khố cơng
khai.Bây giờ giả sử Alice muốn gửi bản rõ 9726 cho Bob. Cơ sẽ tính:
97263533 mod 11413=5761
và gửi bản mã 5761 trên kênh.
Khi Bob nhận được bản mã 5761, anh sẽ dùng số mũ bí mật cùa
mình để giải
5 76 16597 mod 11413=9726
Do ab=l mod 3>(n), <t>(n)= (p-l)(q-l)= O(p)
ý
rằng 0< X
(*) Giả sử (x ,n)= l, ta có
ya mod n s (xb)a mod n s x 1+t®(n) mod n = x Ị x ^ m o d n] mod n
—X. 1 mod n
(v ì (x,n) =1 nên x®(n) mod n=l)
=x ( do x
3.2.3. Độ an toàn của hệ RSA
Độ an toàn của hệ RSA dựa trên hy vọng rằng hàm mã hoá ek(x)=xb
mod n là một chiều, tị đó đối phương khơng thể tính tốn để giải ban mã
được. Cái cửa sập cho phép Bob giải mã là kiến thức về phân tích n=p.q.
Vỉ Bob biết p và q nên có thể tính được 0(n)= (p-l)(q-l) và sau đó tính số
mũ giải mã a nhờ thuật toán ơclit mở rộng.
Muốn biết p và q thi Oscar phải phân tích được n, vì vậy nếu bài
tốn phân tích số là khó thì Oscar sẽ khơng phân tích được n. Cho đến
nay, người ta thấy rằng bài tốn phân tích số là khó và đốn rằng việc
phá vỡ hệ RSA là tương đương với việc phân tích số nhưng đáng tế c là
140
chua chứng minh được điều đó. Một cách tổng quát, chưa có phương
pháp nào phá được hệ RSA. Nghĩa là hệ RSA vẫn được coi là an toàn.
3.2.4. Thực hiện RSA
Việc thiết lập hệ RSA được Bob tiến hành theo các bước sau :
1/ Sinh ra hai số nguyên tố lớn p và q
2/ Tính n=p.q và <t>(n)=(p-1)(q-1)
3/ Chọn ngẫu nhiên b (0 < b <í>(n)) sao cho (b, 0(n))= 1
4/ Tính a=b'*mod O(n) nhờ thuật tốn ơclit mở rộng.
5/ Cơng bố n và b trong thư mục như khố cơng khai của mình.
Như đã phân tích ở trên, muốn cho hệ RSA an tồn thì n=p.q phải
lớn để khơng thể phân tích được nó về mặt tính tốn.
3.2.5. Vẩn đề điểm bất động trong RSA
Giả sử rằng cặp khóa cơng khai là (e,n)=(17,35).
Giả sử thơng báo có giá trị bằng 8.
Ta có 8 17 = 8 m od 3 5 .
Như vậy mã hóa của thơng báo vẫn là thơng báo ban đầu. Nói một
cách khác với khóa mã là 17 thì thơng tin khơng được che dấu. Rõ ràng
là phái tránh được tình trạng này định lý sau cho ta tính được số bản tin
khơng thể che dấu đirợc vái một lira chon cho trước của (e.n)
Định lý 3.1.
Nếu các thông báo được mã bàng hệ mật RSA với cặp khóa cơng
khai (e,n) với n=p.q thì số các thông báo không thê che dấu được bang:
N = (1 + U C L N ( e - l , p - l)X l + U C L N ( d - l ,q - 1 »
Chửng minh:
Một thông báo là không thể che dấu được nếu M e = M m od n
Ta có: M e - M m od p v à M e = M m od q
Ta có thể viết lại các phương trình trên như sau:
141
M e 1 = 1 m od p hoặc M e 1 = 0 m od p
M e 1 = 1m od q hoặc M e 1 = 0 m od q
Chú ý rằng phương trinh đồng dư 2 3 M e_1 = O m od p chi có một
nghiệm tương tự với q ta có được kết quả của định lý
Ví dụ 3.3. n = 35
Giả sử e = 3 ta có (1+ ƯCLN(2,4))(1+UCLN(2,6))=9
Các thơng báo khơng thể che dấu được là 9 thông báo sau:
{0,1,6,14,15,20,21,29,34}
Giả sử e = 17. ta có (1+ UCLN(6,4))(1+UCLN(16,6))=15
Các thơng báo khơng thể che dấu được là 15 thông báo sau:
{0,1,6,7,8,13,14,15,20,21,22,27,28,29,34}
Giả sử p = 2p’ +1 và q = 2q’ +1 trong đó p’ và q’ là các số nguyên
tố. Khi đó:
U C L N ( e — 1 ,2 p ') = 1; 2 hoặc p’
Nếu U C L N (e-l,2 p ') không phải là p’ và Ư C L N (e-l,2 q ') khơng
phải là q' thì số thơng báo khơng thể che dấu chỉ nhiều nhất là 9.
Nếu U C L N (e-l,2p')= p' thi số các thông báo không thể che dấu
tối thiểu là 2(p'+l). Tuy nhiên xác suất để xảy ra điều này là rất nhỏ
(bằng 1/p’)
3.3. Hệ mật Rabin
3.3.1.
Tạo khóa
Tóm lược: Mỗi đầu tạo một khố cơng khai và một khố bí mật
tương úng theo các bước sau:
(1) Tạo 2 số nguyên tố lớn, ngẫu nhiên và phân biệt p và q có kích
thước xấp xi nhau.
(2) Tính n = p .q .
142
(3) Khố cơng khai là n, khố bí mật là các cặp số (p, q).
3.3.2. M ã hóa và giải mã của hệ mật Rabin
M ã hoá: B phải thực hiện các bước sau:
(1) Nhận khố cơng khai của A: n.
(2) Biểu thị bản tin dưới dạng một số nguyên m nằm trong dải
Ịo ,n -
1].
(3) Tính c = m 2 m od n
(4) Gửi bản mã c cho A.
Giải ttiã.Để khôi phục bản rõ m từ c, A phải thực hiện các bước sau:
Tìm 4 căn bậc hai của c m od n là m i, m2, m3 hoặc Iti4.
(1)
Thông báo cho người gửi là một trong 4 giá trị mi, m2, m3 hoặc
m4. Bằng một cách nào đó A sẽ quyết định m là giá trị nào.
3. 3. 3. Ví dụ
Tạo khố
A chọn các số ngun tố p = 277 và q = 331. A tính n = p
q =
91687. Khố cơng khai của A là 91687. Khố bí mật của A là cặp số (p =
277, q = 331).
M ã hoá
Giả sử rằng 6 bit cuối cùng của bản tin gốc được lặp lại trước khi
thực hiện mã hoá. Việc thêm vào độ thừa này nhằm giúp cho bên giải mã
nhận biết được bản mã đúng.
Để mã hoá bản tin 10 bit m = 1001111001, B sẽ lặp lại 6 bit cuối
cùng của Fn để có được bản tin 16 bit sau: m = 1001111001111001, biểu
diễn thập phân tư ơ n g ứ ng là m = 40596.
Sau đó B tính c = m2 modn = 40 5962 mod91687 = 62111 rồi gửi c cho A
Giải mã
Đe giải mã bản mã c, A tính bốn giá trị cãn bậc 2 của c m od n :
143
m, =69654,
m2 = 22033,
m, = 40596, m4 =51118
Biểu diễn nhị phân tương ứng của các số trên là:
m, =10001000000010110 ,
m3 = 1001111001111001
m2 =101011000010001
,
m4 = 1100011110101110
Vì chỉ có m3 mới có độ thừa cần thiết nên A sẽ giải mã c bằng m3 và
khôi phục lại bản tin gốc là m = 1001111001.
3.3.4. Đánh giá hiệu quả
Thuật toán mã hoá Rabin là một thuật tốn cực nhanh vỉ nó chỉ cần
thực hiện một phép bình phương modulo đơn giản. Trong khi đó, chẳng
hạn với thuật tốn RSA có e = 3 phải cần tới một phép nhân modulo và
một phép bỉnh phương modulo. Thuật tốn giải mã Rabin có chậm hơn
thuật tốn mã hố, tuy nhiên về mặt tốc độ nó cung tương đương với
thuật toán giải mã RSA.
3.4. Hệ m ật Elgamal
3.4.1. Bài toán logarit rời rạc
Định nghĩa 3.1.
Cho G là nhóm cylic hữu hạn bậc n, a là phần tử sinh cùa G, p là
phần tư thuộc G. Lôgarit rời rạc của
lo g
/?
/3
theo cơ số a được ký hiệu là
, là một số nguyên X, 0 < x < n -l, thỏa mãn p = ữ x.
Ví dụ 3.4.
Cho p=101, Zỉ01 là nhóm cyclic có bậc n=100, a =2 là phần tử sinh
của nhóm Z{01, ta có 288 = 92 (mod 101) =>log2 92 = 88 trên Z{ 0 J.
Bỗ đề 3.1.
Cho a là phần từ sinh cùa nhóm cyclic G bậc n, p , ỵ e G t s là một
số nguyên, ta có:
log a(/?ỵ) = (log a p + log a y) m od n
log a P s = s .( \o g a p m o d n
144
3.4.1.1. Bài tốn lơgarit rời rạc tổng qt (GDLP)
Bài tốn lôgarit rời rạc tổng quát (Generalized discrete logarithm
problem - GDLP). cho G là nhóm cyclic hữu hạn bậc n, a là phần tử sinh
của G, phần tử P e g , tìm số nguyên X, 0 < X < n-1, sao cho a x = p.
Độ khó của bài tốn lôgarit rời rạc tổng quái (GDLP) độc lập với
phần tử sinh
Chừng minh:
Cho a và y là 2 phần tử sinh của nhóm cyclic G bậc n, và peG.
Đặt:
'x = loga p
y = logy p
=>ax = p = Yy = ( a z y .
z = lo g a Y
Vậy ta có:
ị
ị Ịog^ p _
X = zy m o d n
p ) ạ oga y ) - i m odn
Điều này có nghĩa rằng bất kỳ thuật tốn nào được dùng để tính
lơgarit theo cơ số a cũng có thể dùng để tính lơgarit theo cơ số Y bất kỳ,
với y cũng là phần tử sinh của G.
3.4.1.2. Bài tốn lơgarit rời rạc (DLP)
Bài tốn lơgarit rời rạc {Discrete logarithm problem -DLP). cho p là
số nguyên tố, ữ là phần tử sinh của nhóm Zp, và phần tử /? E Zp, tim số
nguyên X, 0 < X < p-2, sao cho a x = p (m od p)
Ví dụ 3.5. Xét Z jg , phần tử sinh g = 2. Ta có bảng sau:
X
1
2
3
4
logỉX
18
1
13 2
6
7
8
9
10 11 12 13 14 15 16 17 18
16 14
6
3
8
17 12 15
5
5
7
11
4
10
9
Từ bảng trên ta có: 213s3m odl9.
Nhìn chung đây là một bài tốn rất khó khi p đù lớn (chẳng hạn
p * 1 0 200). Khi đó ngay cả với các máy tính cực mạnh ta cũng phải chịu
bó tay. Tuy nhiên, trên thực tế bài tốn này chỉ thực sự khó khi p-1 khơng
145
phải là tích của các số ngun tố nhỏ. Nói chung bài toán logarit rời rại
trên truờng hữu hạn GF(p) có độ phức tạp lớn hơn so với trên G F(2m ).
3.4.1.3. Một số thuật toán giài bài toán logarit rời rạc
Thuât toán vét can
Vét cạn là một thuật toán giải bài tốn tìm 1 phương án đúng tron
khơng gian n phương án.
Thuật tốn vét cạn tìm phuơng án đúng bằng cách lựa chọn lần lưc
từng phương án trong tập hợp tất cả các phương án của bài toán để tìm r
phương án tối ưu.
Trong nhiều bài tốn, khơng gian các phương án quá lớn. Do vậ)
khi áp dụng thuật tốn vét cạn khơng đảm bảo về thời gian cũng nh
kỹ thuật.
Tht tốn bước lớn bước nhị
Tính log* /? =? trên Zp
- Tính m=[Vn], với n là cấp của X,
X
là phần tử sinh.
- Tính bảng giá trị (ý, X J) với j=
- Tính bảng giá trị
-
Tính
với i=
b ả n g g iá trị XJ c h o đ ế n kh i
thỏa
m ã n X J = /?. x ~ m i
Khi đó log* p = im + j
Ví dụ 3.6. Tìm log31 45 =? trên Z'61.
0(61)=6O =>m=[V60]=8
j
3Vmod61
1
6
3
2
1
1
1
Ta có
x~ m m od p = 31-8 m od 61 = (3 1 -1) 8 m od 61 = 28 mod. 61 = 12
146
p . x m i = 4 5 . 1 2 ' m od 61
i
0
1
2
3
4
5
6
7
4 5 .12‘m od61
45
52
14
46
3
36
5
60
Ta thấy tại i = 2j = 3 thì 317 m od 61 = 4 5 .1 2 ' m od 61 = 46
Vậy log31 45 = 8.3 + 2 = 26
Tht tốn
p-
pollard
Nhóm G được chia thành 3 nhóm con có kích thước gần bằng nhau
dựa vào một số tính chất dễ kiểm tra. Định nghĩa dãy các phần tử nhóm
X0,X1,X2,... bời x 0= l và:
de/
x ,+l = / ( * , ) - •
7 ? jf„
xf,
ifxl e S l
if x, g S 2
a.x„ i f xl e S ì
Với i>0. Dùng dãy các phần tử nhóm này để định nghĩa 2 dãy khác
của các
số
nguyên
a o ,ai,a2
và bo,bi,b2... thỏa mãn
X, = a a '
p b' .
Với a0 = ố0 = 0 thi:
ah
a /+1
ự Xi e Si
2 a, mod n,
i f Xị G s 2
a, + 1, if Xị e s 3
bị +1,
i f Xị G S ị
bi+ỉ = 2 bt mod n,
bị,
i f X, e s 2
i f X, G S-Ị
Thuật tốn tìm chu kỳ Floyd có thể được sử dụng để tỉm 2 phần tử
của nhóm
Xi
và
x 2j
sao cho
Xj=X2 i
Khi
đó0La‘p b' = a a2'Ị3b2'
và do đó
p b‘ ~bh = a a' ~ °2' . Lấy logarit theo cơ số a của cả 2 vế của đẳng thức
cuối ta có: (bị - b2j ). loga p = (a2l - aị )(mod n)
147
Nếu bi ^ b2i(m o d n ) (truờng hợp bị = b2i(.mod) xảy ra với xác
suất nhỏ), phương trình này có thể giải hiệu quả để xác định lo g a /?.
T huật toán
INPUT: phần tử sinh a của nhóm tuần hồn G có bận n ngun tố,
phần từ PeG.
OUTPUT: logarith rời rạc X = \oga p
Set xo<— 1, ao<- 0, bo<—0.
For i=l,2,... do
Dùng các đại lượng xi_1, a i_1,ò Ể_1và x 2l_ 2 , a 2t - 2l b2i- 2fà được
tính trước để tính các đại lượng Xi.CLi.b^à x 2i,a 2i,b 2i theo các công
thúc trên.
N ếu
Xị
= * 2/thì làm:
Set r<- b,-b2, mod n
Nếu r=0 thi dừng thuật tốn và Output(‘fail’)
Ngược lại, tính X = r _1( a 2j — a ^m o d n v à trả v ề (x).
Ví dụ 3.7. (Tính logarith trong nhóm con của z 383 ), phần tử a =2
là phần tử sinh cùa nhóm con G trong z 383 có bậc n=191. Già sử p =
228. Phân nhóm các phần tử của G thành 3 nhóm con theo q'iy tắc
X
e Si
nếu X=1 (mod 3), X € s 2 nếu x=0(mod 3) và X e S 3 nếu x=2(mod 3).
Bảng sau chi ra các giá trị của Xị, dị, bi, x 2t, a 2i, b2itại cuối mỗi vịng lặp.
Cuối cùng tính:
r = ò14 - b28 m od 191 — 125, r _1 = 125-1 m od 191 =
136, r -1 ( a 28 —a 14) m od 191 = 110 Cho nên log2 228 = 110.
Bàng 3.2. Giải lôgarit rời rạc bằng thuật tốn p-pollard.
i
1
2
3
4
148
Xi
228
279
92
184
bi
dí
0
0
0
1
1
2
4
4
^2 i
a 2i
*2 i
279
184
14
256
0
1
1
2
2
4
6
7
205
14
28
256
152
304
372
121
12
144
5
6
7
8
9
10
11
12
13
14
1
1
2
2
2
3
3
6
6
12
5
6
6
7
8
8
9
18
19
38
304
121
144
235
72
14
256
304
121
144
3
6
12
48
48
96
97
98
5
10
8
18
38
152
154
118
119
120
51
104
Thiiât toán Pohlis-Hellman
Giả sử n = p e^ p 6^ ....pịr là phân tích của n. Nếu x = loga /?thì
phương pháp ở đây là xác định Xị = jcmod p f 1,1 < i < / và sau đó sử dụng
thuật tốn Gauss rồi tìm
X
mod. n. Mỗi số ngun Xị được xác định bằng
c á c h tính tư ng c h ữ s ố c ù a n ó là
Iq,1\, ■■; l e
_1
tro n g b iể u d iễ n cù a Xi th e o
c ơ s ố p ,: Xị =l0 + l lp ẵ +... + lei_ìp f ‘ - ì , o z l j < p , - \ , 0 < j < e ắ - \ .
Thuật toán
INPUT:phần tử sinh a của nhóm tuần hồn G có bậc n và phần tử
pe G
OUTPUT: logarithm rơi rạc x=logaỊi
Tìm phân tích của n: « = p ị xP 2 2 ■■ p e/ , với Ẽi> 1.
For i =1 to n do
Set q<-p,, e<-ej
Set Y<- 1 and 1-1<—0
tính ã <- a n ' q
(tính
lị)
For j=0 to e-1 do
Compute^ < - y a lj~iqJ
and p <—(y3ỵ~ỉ )n/qJ
149
Compute lj <- log ã p
Set Xj<- 10 +liq+...+ le.iqe'1
Dùng thuật tốn Gauss rồi tìm số ngun
X,
0 < X < n — lsao chc
X = Xị (mod p et ' ), 1 < / < r
Retum(x)
Ví dụ 3.8. Tính logarith trong z 251 . Giả sử p=251. Phần từ a=71 là
phần từ sinh của z 251 bậc n=250. Lấy p=210. Thế thì X=log7i210 được
tính nhu sau:
Phân tích của n là 250=2.53
(a) tính X 1=X mod 2
c ó ã = a n/2 mod p = 250vàP = p n ỉ l mod p = 250
•Vỉvậy Xi=log25o250=l
(b ) tín h x 2= X m o d 53= 10+1 i 5+1252
tính ã = a nl5 mod p - 20
tính Ỵ=1 và p = (/3ỵ
nx»d p = 149. Dùng phép vét cạn tính
được lo=log2o149=2
tính Y = Y- ữ 2mod p = 21
và p = (yỡ/_1) w/25 mod /> = 113.
Dùng phương pháp vét cạn tính được lx = log20 113 = 4
tính y = y. a* 5modp — 115
vàp =
m odp = 149. Dùng phương pháp vét cạn tính
được l2 = log20 149 = 2cho nên *2 = 2 + 4.5 + 2. 52 = 72
Cuối cùng, giải cặp phương trình đồng dư X = l(m o d 2), x =
7 2 m o d l 2 5 để nhận đ ư ợ c X = l o g 71 2 1 0 = 1 9 7
150
Nhận xét Thuật tốn phân tích số ở bước 1 cần phải tìm được ước
số nhị trước; nếu bậc n khơng là số ngun mịn thì thuật tốn này khơng
hiệu quả.
Thuật tốn tính chỉ số
Thuật tốn
INPUT: phẩn tử sinh a của nhóm tuần hồn G bậc n, phẩn tử Pe G
OUTPUT: logarith rời rạc y — loga /?
(Chọn cơ sở nhân tử S). Chọn tập con 5 = {pi,p2, —,Ptì của G sao
cho một phần đáng kể các phần tử con của G có thể biểu diễn như là tích
của các phần tử trong G.
(Chinh các quan hệ tuyến tính gồm logarith của các phần từ trong
trong S)
Chọn ngẫu nhiên số nguyên k, 0 < k < n — lv à tính a k
Cố gắng viết a k như là tích của các phần tử trong S:
t
a k = Y \ p iC i , C ị > 0
7=1
Nếu thành công, lấy logarith của cả 2 vế để được quan hệ tuyến tính
t
k = X c , logư p, (mod n)
/=1
Lặp lại cho đến khi nhận được t+c quan hệ tuyến tính với c là số
n g u y ê n d ư ơ n g n h ỏ (v í dụ c = 1 0 ) sa o c h o h ệ p h ư ơ n g trình đ ư ợ c c h o bởi
t+c quan hệ có lời giải duy nhất với xác suất cao.
Tim logarith của các phần tử trong s.
Giải hệ t+c phương trình tuyến tính theo modulo n (với t ân số) đã
thu được ở bước 2 để nhận được các giá trị của loga P i , l < i < t
Tính y.
Chọn số nguyên ngẫu nhiên k, 0 < k < n — l v à tỉnh (ĩ. a k
151
c ố gắng viết /?. ak như là tích của các phần tử trong S:
p . a k = Ú P ị 1 , d ị > 0 . Nếu không thành công thi quay lại bước 4.1.
/=1
ngược lại, lấy logarith của cả 2 vế phương trình trên và được
^ % a P = { ỵ ! l=ìd i ^ % a p , - * ) m o d / i;
cho nên tính y -
l° 8 a Pi —Ẵ :jnx)d« và trả về (y).
Ví dụ thuật tốn trong z*p
Trong trường Zp với p nguyên tố, cơ sờ nhân tử s có thể chọn như là
t số nguyên tố đầu tiên. Quan hệ ờ bước 2.2 của thuật toán trên có thể
sinh ra bằng cách tính a kmo d p, sau đó bằng cách chia thử để kiểm tra
xem số ngun này có phải là tích của các số ngun tố trong s hay
khơng.
Sau đây chúng ta xét một ví dụ trong Z 229 , tức là p = 229 Phần
tử a = 6 là phân từ sinh của z 229 có bậc n = 228. Xét /? = 13. Khi đó
log16 13 được tính như sau bằng kỹ thuật tính chì số.
Cơ sờ nhân tử được chọn là 5 số nguyên tố đầu tiên:
5 = {2,3.5,7,11}
Nhận được 6 quan hệ sau chứa các phần tử của cơ sờ nhân tử (những
phép thừ không thành công được bỏ qua):
6 100m od229 = 180 = 22.3 2.5
6 18m od229 = 176 = 2*.11
6 12m o d 2 2 9 = 1 65 = 3.5.11
6 62m o d 2 2 9 = 1 5 4 = 2.7.11
6 143m o d 2 2 9 = 2 1 0 = 2.3.5.7
6206m od229 = 210 = 2.3.5.7
152
Các quan hệ này dẫn đến 6 phương trình sau cho logarith của các
phần tử trong cơ sờ nhân tử:
100 = 2. log6 2 + 2. log6 3 + log6 5 (m ođ228)
18 = 41og6 2 + log6 ll(m o d 2 2 8 )
12 = lo g 6 3 + lo g 6 5 + lo g 6 11 (m o d 2 2 8 )
62 = log6 2 + log6 7 + log6 ll(m o d 2 2 8 )
143 = log6 2 + 2 log6 3 + log6 ll(m o d 2 2 8 )
206 = log6 2 + log6 3 + log6 5 + log6 7(m od228)
Giải hệ gồm 6 phương trình tuyến tính có 5 ẩn số (đó là logarith
Xị = lo g 6 Pi) sẽ cho lời giải lo g 6 2 = 21 , lo g 6 3 = 2 0 8 , lo g 6 5 = 98,
log6 7 = 107, log6 l l = 162.
Giả sử rằng chọn số nguyên k = 77. Vì p . a k = 13 .6 77m od229 =
147 = 3. 72, tù đó suy ra rằng
lo g 6 13 = ( lo g 6 3 + 2 lo g 6 7 - 7 7 )m o d 2 2 8 = 117.
Ví dụ thuật tốn tính chì sé trong trường F*m
Các phần tử của trường hữu hạn F^m được biểu diễn như là các đa
thức trong z 2[x] có bậc nhiều nhất (m-1), với phép nhân được thực hiện
theo modulo một đa thức bất khả quy cố định f(x) bậc m trong z 2[x]. Cơ
sờ nhân tứ s có thẻ chọn là tập tất cá các đa thúc bất khá quy trong Z 2IXI
có bậc khơng vượt q một số b nào đó. Quan hệ ờ bước 2.2 được sinh ra
bằng cách tính x k m o d f ( x ) v à sử dụng phép chia thử để kiểm tra xem đa
thức này có phải là tích của các đa thức trong s hay khơng. Ví dụ sau
được tính trong F *7 .
Đa thức f ( x ) = X 7 + X + 1 là bất khả quy trên z 2. Các phần tử của
trường hữu hạn F 1 có bậc 128 có thể biểu diễn như là tập tất cả các đa
thức trong z 2[x] có bậc nhiều nhất bằng 6, với phép nhân thực hiện theo
modulo / ( * ) . Bậc của F *7 là n = 27 - 1 = 127và X là phần tử sinh của
153
F *7 Giả sừ /? = X 4 + X3 + X 2 + X + 1. Khi đó y = lo g a p có thề tính
sau theo thuật tốn tính chi số.
Cơ sở nhân tử được chọn là tập tất cả các đa thức bất khả quy trong
z 2[x] có bậc khơng q 3:
s ={x,x + l , x 2 + X + l , x 3 + X + l , x 3 + X2 + 1}
Có 5 quan hệ sau giữa các phần tò của cơ sở nhân tử:
X18 mod f ( x ) = X6 + 4 = x*(x + l ) 2
X 105 m o d f ( x ) = X 6 + X s + X 4 + X
= x ( x + l ) 2( x 3 + X2 + 1)
X18 mod f ( x ) = X6 + X4 = x 2(x + l ) 2( x 2+ X + 1)
X18 m o d f ( x ) = X 6 + X 4 = ( x + l ) 2 ( x 3 + X +
1)
X 121 m o d f ( x ) = X 6 + X s + X* + X 3 + X 2 + X + l
= o 3 + X + 1 ) 0 3 + x 2 + 1)
Các quan hệ này dẫn đến 5 phương trình đối với các logarith của các
phần tử trong cơ sở nhân tử, ta đặt:
Pi = logx x , p 2 = logx ( x + l ) , p 3 = \ogx ( x 2 + X + l ) , p 4
lo g x O 3 + X+ l ) , p s = log^ c*3 + X2 + 1)
=
18 = 4 Pj + 2 p 2( m o d l2 7 )
105 = Pi + 2 p2 + p5(m o d l2 7 )
72 = 2pj + 2pz + p3(m o d l2 7 )
45 = 2p2 + p4(m o d l2 7 )
121 = p4 + p5(m o d l2 7 )
Giải hệ 5 phương trình tuyến tính theo 5 ẩn Pi ch o kết quả Pi =
l , p 2 = 7 ,p 3 = 56, p4 = 31, p5 = 90. Giả
sử k = 66được
chọn
/?. a k = O 4 + X3 + X2 + X + 1). X66 mod. f ( x ) = Xs + X3 + X =
x (x 2 + * + l ) 2
nên logjO t4 + X3 + X2 + X + 1) = (P! + 2p3 - 66) m od 127 = 47
Nhận xét:
Thuật tốn tính chi số khó triển khai vì:
154
Vì
- Kỹ thuật để chọn cơ sở nhân tò chưa được chỉ ra.
- Phương pháp hiệu quả để chỉ ra một số quan hệ cần thiết cũng
chưa được chỉ ra.
- Kỹ thuật này cũng không được áp dụng cho mọi nhóm.
3.4.2. Mã hỏa, giải mã Elgantal
3.4.2.1. Thuật tốn tạo khóa
Tóm lược: Mỗi đầu liên lạc tạo một khố cơng khai và một khố bí
mật tương ứng :
(1) Tạo 1 số nguyên tố p lớn và một phần tử sinh a của nhóm nhân
Z* cùa các số nguyên m od p
(2) Chọn một số nguyên ngẫu nhiên a, 1 < a < p - 2 và tính
a a in o d p
(3) Khố cơng khai là bộ 3 số ( p , a , a a ), khố bí mật là a.
3.4.2.2. Thuật tốn mã hóa, giai mã
Tóm lược B mã hố một thơng tin báo m để gửi cho A bản mã cần gửi.
M ã hoá: B phải thực hiện các bước sau:
(1) Nhận khố cơng khai ( p , a , a a ) cùa A.
(2) Biểu thị bản tin dưới dạng một số nguyên m trong dải
{ 0 ,1 ,...,p - 1 } .
(3) Chọn số nguyên ngẫu nhiên k, l < k < p - 2
(4) Tính Y = a k m o d p và 5 = m (a a
f m od p .
(5) Gửi bản mã c = (y, 8) cho A
Giải mã: Đe khôi phục bản rõ m từ c, A phải thực hiện các bước sau:
(1) Sử dụng khố riêng a để tính Ỵp_1_a m o d p
(Chú ý Yp_1_a = Y_a = Y _ak)
155
(2) Khơi phục bản rõ bằng cách tính (y a )ô m o d p .
Chứng minh hoạt động giài mã:
Thuật toán trên cho phép A thu được bản rõ vì:
Ỵ-a 5 = a _ak.m(xak = m m o d p
3.4.2.3. Ví dụ
Tạo khố
A chọn p = 2357 và một phần từ sinh a - 2 của Z 2357 . A chọn
khố bí mật a = 1751 và tính a a modp = 21751 mod2357 = 1185. Khố
cơng khai của A là (p = 2357, a = 2 , a 3 = 1185 )
M ã hoá
Để mã hoá bản tin m = 2035, B sẽ chọn một số nguyên ngẫu nhiên k
= 1520 và tính:
Y = 2 1520 m o d 2 3 5 7 = 1430
và
ô = 2035.1 1851520 mod 2357 - 6 9 7
Sau đó B gửi c = (1430,697) cho A
Giải mã
Đe giải mã A phải tính:
Ỵp-i-a = Ị430605 m od2357 = 872
Sau đó khơi phục bản rõ m bằng cách tính:
m = 872.697 m od 2357 = 2035.
3.4.3. Tham số của hệ mật
Để chống lại các thuật tốn tấn cơng P-Pollard, Pollig-Hellman, số
ngun tố p được chọn phải thỏa mãn một số điều kiện sau:
( p - 1 có ước sỗ n g u y ê n tỗ lớn (cỡ 100 b it trở lên)
Ị p có độ lờn cỡ 1024 bit trở lên
156
