Chương 5
Các hệ mật khoá công khai khác
Trong chương này ta sẽ xem xét một số hệ mật khoá công khai khác.
Hệ mật Elgamal dựa trên bài toán logarithm rời rạc là bài toán được dùng
nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dành nhiều thời gian để thảo
luận về bài toán quan trọng này. ở các phần sau sẽ xem xét sơ lược một số
hệ mật khoá công khai quan trọng khác bao gồm các hệ thoóng loại Elgamal
dựa trên các trường hữu hạn và các đường cong elliptic, hệ mật xếp ba lô
Merkle-Helman và hệ mật McElice.
5.1. Hệ mật Elgamal và các logarithm rời rạc.
Hệ mật Elgamal được xây dựng trên bài toán logảithm rời rạc . Chúng
ta sẽ bắt đầu băng việc mô tả bài toán bài khi thiết lập môi trường hữu hạn
Z
p
, p là số nguyên tố ( hình 5.1) ( Nhớ lại rằng nhóm nhân Z
p
*
là nhóm cyclic
và phần tử sinh của Z
p
*
được gọi là phần tử nguyên thuỷ).
Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công
trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ
thể không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời
rạc. Để gây khó khăn cho các phương pháp tấn công đã biết p phải có ít nhất
150 chữ số và (p-1) phải có ít nhất một thừa số nguyên tố lớn. Lợi thế của
bài toán logarithm rời rạc trong xây dượng hệ mật là khó tìm được các
logarithm rời rạc ,song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu
quả theo thuật toán "bình phương và nhân". Nói cách khác , luỹ thừa theo
modulo p là hàm một chiều với các số nguyên tố p thích hợp.

*
Mục tiêu:Hãy tìm một số nguyên duy nhất a, 0 ≤ a ≤ p-2 sao
cho:
α
a
≡ β (mod p)
Ta sẽ xác định số nguyên a bằng logα β
Cho p l sà ố nguyên tố sao cho b i toán logarithm rà ời rạc trong Zp
l khó già ải. Cho α ∈ Zp
*
l phà ần tử nguyên thuỷ.Giả sử P = Zp
*
,
C = Zp
*
× Zp
*
. Ta định nghĩa:
K = {(p, α,a,β): β ≡ α
a
(mod p)}
Các giá trị p, α,β được công khai, còn a giữ kín
Với K = (p, α,a,β) v mà ột số ngẫu nhiên bí mật k ∈ Zp-1, ta xác
định:
e
k
(x,k) = (y
1
,y
2

)
-1
mod p
Ví dụ 5.1
Cho p = 2579, α = 2, a = 765. Khi đó
β = 2
765
mod 2579 = 949
Bây giờ ta giả sử Alice muốn gửi thông báo x = 1299 tới Bob. Giả sử số
ngẫu nhiên k mà cô chọn là k = 853. Sau đó cô ta tính
y
1
= 2
853
mod 2579
= 435
y2 = 1299 × 949853 mod 2579
= 2396
Khi đó Bob thu được bản mã y = (435,2396), anh ta tính
x = 2396 × (435
765
)
-1
mod 2579
= 1299
Đó chính là bản rõ mà Alice đã mã hoá.
5.1.1. Các thuật toán cho bài toán logarithm rời rạc.
Trong phần này ta xem rằng p là số nguyên tố, α là phần tử nguyên
thuỷ theo modulo p. Ta thấy rằng p và α là các số cố định. Khi đó bài toán
logarithm rời rạc có thể được phát biểu dưới dạng sau: tìm một số mũ a duy

-i
mod p, 0 ≤ i ≤ m-1
4. Sắp xếp m cặp thứ tự (i, βα
-i
mod p) có lưu ý tới các toạ độ thứ hai
của các cặp được sắp này, ta sẽ thu được một danh sách L
2

5. Tìm một cặp (j,y) ∈ L
1
và một cặp (i,y) ∈ L
2
( tức là một cặp có tạo
độ thứ hai như nhau).
6. Xác định log
α
β = mj + i mod (p-1)
7.
- Nếu cần, các bước 1 và 2 có thể tính toán trước ( tuy nhiên, điều này
không ảnh hưởng tới thời gian chạy tiệm cận)
- Tiếp theo cần để ý là nếu (j,y) ∈ L
1
và (i,y) ∈ L
2
thì
α
mj
= y = βα
-i
Bởi vậy

(10,644) (11,654) (12,26) (13,147) (14,800)
(15,727) (16,781) (17,464) (18,314) (19,275)
(20,582) (21,496) (22,564) (23,15) (24,676)
(25,586) (26,575) (27,295) (28,81)
Danh sách này sẽ được sắp xếp để tạo L
1
.
Danh sách thứ hai chứa các cặp được sắp (i,525×(3
i
)
-1
mod 809), với 0
≤ i ≤ 28. Danh sách này gồm:
(0,525) (1,175) (2,328) (3,379) (4,396)
(5,132) (6,44) (7,554) (8,724) (9,511)
(10,440) (11,686) (12,768) (13,256) (14,,355)
(15,388) (16,399) (17,133) (18,314) (19,644)
(20,754) (21,496) (22,564) (23,15) (24,676)
(25,356) (26,658) (27,489) (28,163)
Sau khi sắp xếp danh sách này, ta có L
2
.
Bây giờ nếu xử lý đồng thời qua cả hai danh sách, ta sẽ tìm được ( 10,644)
trong L
1
và (19,644) trong L
2
. Bây giờ ta có thể tính
log
3

i
≤ q-1 với 0 ≤ i ≤ c-1. Cũng có thể biểu diễn như sau:
a = x + q
c
s
với s là một số nguyên nào đó.
Bước đầu tiên của thuật toán tính a
0
. Kết quả chính ở đây là:
β
(p-1)/q
≡ α
(p-1)a0/q
(mod p)
Để thấy rõ điều đó cần chú ý rằng:
Điều này đủ để cho thấy:
Kết quả này đúng khi và chỉ khi:
p-1 ≡ 0 (mod q
c+1
)
Tuy nhiên
Đó chính là điều cần chứng minh.
Do đó ta sẽ bắt đầu bằng việc tính β
(p-1)/q
mod p. Nếu
β
(p-1)/q
≡ 1 (mod p)
thì a
0

mod q
c
Dễ dàng thấy rằng
Vì thế dẫn đến
Như vậy ta sẽ tính β
1
(p-1)/
q
2
mod p và rồi tìm i sao cho
Khi đó a
1
= i.
Nếu c =2 thì công việc kết thúc; nếu không, phải lặp lại công việc này
c-2 lần nữa để tìm a
2
,. . .,a
c-1
.
Hình 5.4 là mô tả giải mã của thuật toán Pohlig - Hellman. Trong
thuật toán này, α là phần tử nguyên thuỷ theo modulo p, q là số nguyên tố .
p-1 ≡ 0 (mod q
c
)
và
Thuật toán tính các giá trị a
0
, . . ., a
c-1
trong đó

α
-a
j
q
j
mod p
8. j = j +1
Chúng ta minh hoạ thuật toán Pohlig - Hellman (P - H) qua một ví dụ nhỏ.
Ví dụ 5.3
Giả sử p=29; khi đó
n = p-1 = 28 = 2
2
.7
1
Giả sử α = 2 và β = 18. Ta phải xác định a = log
2
18. Trước tiên tính a mod 4
rồi tính a mod 7.
Ta sẽ bắt đầu bằng việc đặt q = 2, c = 2. Trước hết
γ
0
= 1
và γ
1
= α
28/2
mod 29
= 2
14
mod 29

= 28
Vì
γ
1
≡ 28 mod 29
Ta có a
1
= 1. Bởi vậy a ≡ 3 ( mod 4).
Tiếp theo đặt q = 7 và c = 1, ta có
β
28/7
mod 29 = 18
4
mod 29
= 25
và γ
1
= α
28/7
mod 29
= 2
4
mod 29
= 16.
Sau đó tính: γ
2
= 24
γ
3
= 7

theo modulo p như sau:
α
x
j
≡ p
1
a
1j
p2
a
2j
. . . p
B
a
Bj
(mod p)
1 ≤ j ≤ C. Cần để ý rằng, các đồng dư này có thể viết tương đương như sau:
x
j
≡ a
1j
log
α
p
1
+ . . . + a
Bj
log
α
p

1
c
1
p
2
c
2
. . . p
B
c
B
(mod p)
Điều đó tương đương với
log
α
β + s ≡ c
1
log
α
p
1
+ . . . + c
B
log
α
p
B
( mod p-1)
Vì mọi giá trị đều đả biết trừ giá trị log
α

9865
mod 10007 = 189 = 3
3
×7
ta tìm được hai đồng dư thức nữa:
log
5
2 + 3log
5
3 ≡ 5136 ( mod 10006)
3log
5
3 + log
5
7 ≡ 9865 ( mod 10006)
Bây giờ ta có 3 đồng dư thức theo 3 giá trị log chưa biết. Giải các
phương trình đồng dư này, ta có log
5
2 = 6578, log
5
3 = 6190, log
5
7 = 1301.
Bây giờ giả sử ta cần tìm log
5
9451, ta chọn số mũ "ngẫu nhiên"
s=7736 và tính:
9451×5
7736
mod 10007 = 8400

Bản chất của bài toán: I = (p, α, β, i) trong đó p là số nguyên tố ,
α∈Z
p
*
là phần tử nguyên thuỷ, β ∈ Z
p
*
và i là một số nguyên sao cho 1
≤ i ≤ log
2
(p-1).
Mục tiêu:Tính L
i
(β) là bít thấp nhất thứ i của log
α
β. (với α và p cho
trước)
5.1.2. Độ bảo mật tưng bít của các logarithm rời rạc.
Bây giờ ta xem xét vấn đề về thông tin bộ phận của các logarithm rời
rạc và thử xem việc tính các bít riêng của các logarithm rời rạc là khó hay
dễ. Cụ thể , xét bài toán trình bày trên hình 5.5. Bài toán này được gọi là bài
toán về bít thứ i.
Trước tiên, ta sẽ chỉ ra rằng, bít thấp nhất của các logarithm rời rạc rất
dễ tính toán. Nói cách khác, nếu i = 1 thì bài toán về bít thứ i có thể giải
được một cách hiệu quả. Điều này rút ra từ tiêu chuẩn Euler liên quan đến
thặng dư bình phương theo modulo p, với p là số nguyên tố .
Xét ánh xạ f: Z
p
*
Z

bình phương và một nữa không phải.