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
)
trong đó

mod p
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
nhất, 0 a p-2 sao cho
a
(mod p), với Z

-i
mod p) có lu ý 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

mj+i
=

(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
525 = 29ì10+19
= 309
Có thể kiểm tra thấy rằng quả thực 3

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:
Tuy nhiên
p-1 0 (mod q
c+1
)
Đó 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
=0. Ngợc lại chúng ta sẽ tính liên tiếp các giá trị:
=
(p-1)/q
mod p,

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à
p-1 0 (mod q
c+1
)
Thuật toán tính các giá trị a
0
, . . ., a
c-1
trong đó
log mod qc

-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

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

4
= 25
Bởi vậy a

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
B
(mod p-1)
1 j C. C đồng d thức đợc cho theo B giá trị log

p

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

nên có thể dễ dàng tìm đợc log

.
Sau đây là một ví dụ minh hoạ 2 bớc của thuật toán.
Ví dụ 5.4.

log
5
2 + 3log
5
3 5136 ( mod 10006)
3log
5
3 + log
5
7 9865 ( mod 10006)
0 nếu
(p-1)/2
1( mod p)
L
1
()=
1 trong các trường hợp còn lại
Bây giờ ta có 3 đồng d thức theo 3 giá trị log cha 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

và thời gian để tính một giá trị logarithm rời rạc riêng là khoảng
Hình 5.5. Bít thứ i của logarithm rời rạc.
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 tng 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.
0 nếu
(p-1)/2
1( mod p)
L
1
()=