chương 7
các hàm hash
7.1 các chũ kí và hàm hash.
Bạn đọc có thể thấy rằng các sơ dồ chữ kí trong chương 6 chỉ cho phép
kí các bức điện nhỏ.Ví dụ, khi dùng DSS, bức điện 160 bit sẽ được kí bằng
chữ kí dài 320 bít. Trên thực tế ta cần các bức điện dài hơn nhiều. Chẳng hạn,
một tài liệu về pháp luật có thể dài nhiều Megabyte.
Một cách đơn giản để gải bài toán này là chặt các bức điện dài thành
nhiều đoạn 160 bit, sau đó kí lên các đoạn đó độc lập nhau. Điều này cũng
tương tự như mã một chuôĩ dài bản rõ bằng cách mã của mỗi kí tự bản rõ độc
lập nhau bằng cùng một bản khoá. (Ví dụ: chế độ ECB trong DES).
Biện pháp này có một số vấ đề trong việc tạo ra các chữ kí số. Trước
hết, với một bức điện dài, ta kết thúc bằng một chữ kí rất lớn ( dài gấp đôi bức
điện gốc trong trường hợp DSS). Nhược điểm khác là các sơ đồ chữ kí “an
toàn” lại chậm vì chúng dùng các pháp số học phức tạp như số mũ modulo.
Tuy nhiên, vấn đề nghiêm trọng hơn với phép toán này là búc điện đã kí có
thể bị sắp xếp lại các đoạn khác nhau,hoặc một số đoạn trong chúng có thể bị
loại bỏ và bức điện nhận được vẫn phải xác minh được. Ta cần bảo vệ sự
nguyên vẹn của toàn bộ bức điện và điều này không thể thực hiện được bằng
cách kí độc lập từng mẩu nhỏ của chúng.
Giải pháp cho tất cả các vấn đề này là dùng hàm Hash mã khoá công
khai nhanh. Hàm này lấy một bức điện có độ dài tuỳ ý và tạo ra một bản tóm
lược thông báo có kích thước qui định (160 bit nếu dùng DSS).
Sau đó bản tóm lược thông báo sẽ được kí. Vơi DSS, việc dùng hàm
Hash được biểu diễn trê hình 7.1.
Khi Bob muốn kí bức điện x, trước tiên anh ta xây dựng một bnr tóm
lược thông báo z = h(x) và sau đó tính y = sig
K
(z ). Bob truyền cặp ( x, y)
trên kênh. Xét thấy có thể thực hiện xác minh (bởi ai đó ) bằng cách trước hết
khôi phục bản tóm lược thông báo z =h (x) bằng hàm h công khai và sau đó

như sau:
Định nghĩa 7.1
Hàm hash h là hàm không va chạm yếu nếu khi cho trước một bức điện
x, không thể tiến hành về mặt tính toán để tìm một bức điện x ≠ x
’
sao cho
h (x
’
) = h(x).
Một tấn công kiểu khác như sau: Trước hết Oscar tìm hai bức điện x ≠ x
’

sao cho h(x) =h(x
’
). Sau đó Oscar đưa x cho Bob và thyết phục Bob kí bản
tóm lược thông báo h(x) để nhận được y. Khi đố (x
’
,y) là thông báo (bức
điện ) giả mạo hợp lệ.
Đây là lí do đưa ra một tính chất không va chạm khác.
Định nghĩa 7.2.
Hàm Hash h là không va chạm mạnh nếu không có khả năng tính toán
để tìm ra bức điênk x và x
’
sao cho x ≠ x
’
và h(x) = h(x
’
).
Nhận xét rằng: không va chạm mạnh bao hàm va chạm yếu.

Giả sử h: X→Z là hàm Hash, trong đó XvàZ hữu hạn và X≥
2Z. Cho A là thuật toán đảo đối với h. Khi đó tồn tại một thuật toán Las
Vagas xác suất tìm được một va chạm đối với h với xác suất ít nhất là1/2.
Chứng minh :
Xét thuật toán B đưa ra trong hình 7.2. Rõ ràng B là một thuật toán xác
suất kiểu Las Vegas vì nó hoạc tìm thấy một va chạm, hoặc cho câu trả lời
không. Vấn đề còn lại là ta phải tịnh xac suất thành công, Với x bất kỳ thuộc
X, định nghĩa x ∼ x
1
nếu h(x) = h(x
1
). Dễ thấy rằng, ∼ là quan hệ tương
đương. Ta định nghĩa:
[x] = {x
1
∈X: x ∼x
1
}
Mỗi lớp tương đương [x] chứa ảnh đảo của một phần tử thuộc Z nên số các
lớp tương đương nhiều nhất là Z. Kí hiệu tập các lớp tương đương là C.
Bây giờ giả sử, x là phần tử ∈X được chọn trong bước 1. Với giá trị x
này, sẽ có[x]giá trị x
1
có thể cho phép trở lại bước 3. [x]-1 các giá trị x
1

này khác với x và như vậy bước 4 thành công. (Chú ý rằng thuật thoán A
không biết biểu diễn các lớp tương đương [x] đã chon trong bước 1). Như
vậy, khi cho trước lựa chọn cụ thể x∈X, xác suất thành công là
([x)-1/[x].

(c-1)/c
= 1/X∑
c
∈
C
(c-1) = (1/X) ∑
c
∈
C
c - ∑
c
∈
C
1
>= (X -Z) / X
>= ((X -Z)/2) /X= ẵ
Như vậy, ta đã xây dựng thuật toán Las Vegas có xác suất thành công ít nhất
bằng 1/2.
Vì thế, đó là điều kiện đủ để hàm Hash thoả mãn tính chất không va
chạm mạnh vì nó bao hàm hai tính chất khác.Phần còn lại của chương này ta
chỉ quan tâm đến các hàm Hash không va chạm mạnh.
7.3 tấn công ngày sinh nhật(birthday)
Trong phần này, ta sẽ xác định điều kiện an toàn cần thít ch hàm Hash
và điều kiện này chỉ phụ thuộc vào lực lượng của tập Z (tương đương về kích
thước của bảng thông báo ).Điều kiện cần thiết nà rút ra tư phương pháp tìm
kiếm đơn giản ác va chạm mà người ta đã biết đến dưới cái tên tấn công ngày
sinh nhật (birthday phương pháparradox), trong bài toán:một nhóm 23 người
ngẫu nhiên, có ít nhất 2 người có ngày sinh trùng nhau với xác suất ít nhất
là1/2.(Dĩ nhiên, đây chưa phải là nghịch lí,song đó là trực giác đối lập có thể
xảy ra). Còn lí do của thuật ngữ “tấn công ngày sinh nhật ” sẽ rõ ràng khi ta

đảo không xấp xỉ bằng nhau thì xác suất tìm thấy một va chạm sẽ tăng lên ).
Vì các ảnh đảo đều có kích thước bằng nhau và các x
i được
chọn một cách
ngẫu nhiên nên các z
i
nhận được có thể xem như các phần tử ngẫu nhiên của
Z. Song việc tính toán xác suất để các phần tử ngẫu nhiên z
1
, z
2,....
z
k
∈Z là
riêng biệt khá đơn giản.Xét các z
i
theo thứ tự z
1
, …,z
k
. Phép chọn z
1
đầu tiên
là tuỳ ý. Xác suất để z
2
≠z
1
là 1-1/n; xác suất để z
3
≠ z

i
1(
e
-1/n
= e
-k(k-1)/n
Vì thế ta ước lượng xác suất để có ít nhất một va chạm là
1-e
-k(k-1)/n
Nếu kí hiệu xác suất này là ε thì có thể giải phương trình đối với k (như một
hàm của n và ε)
1-e
-k(k-1)/n
≈ 1 -ε
-k(k-1)/n ≈ ln(1-ε)
k
2
- k ≈ nln 1/(1-ε)
Nếu bỏ qua số hạng k thì :
k=
ε1
−
1
lnn
Nếu lấy ε = 0.5 thì
k
n17.1
≈
Điều này nói lên rằng, việc chặt (băm) trên
n

Định lý 7.2.
Nếu cho trước một va chạm với hàm Hash Chaum-Van Heyst-Pfĩtmann
h có thể tính được logarithm rời rạc log
α
β
một cách có hiệu quả.
Chứng minh
Giả sử cho trước va chạm
Giả sử p l sà ố nguyên tố lớn v q =(p-1)/2 cà ũng l sà ố
nguyên tố. Cho α v à β l hai phà ần tử nguyên thuỷ của Zp.
Giá trị log
α
β không công khai v già ả sử rằng không có khả
năng tính toán được giá trị của nó.
H m Hash:à
h: {0,...,q-1}×{0,...,q-1} → Zp\ {0}
được định nghĩa như sau:
h(x1,x2) =α
x
1
β
x
2
mod p
h(x
1
,x
2
) = h(x
3

x
2
≡ α
x
3
β
x
4
(mod p)
Ta kí hiệu
D = UCLN (x
4
-x
2
,p-1)
Vì p-1 =2q ,q là số nguyên tố nên d ∈ {1, 2, q, p-1}. Vì thế, ta có 4 xác suất
với d sẽ xem xét lần lượt dwois đây.
Trước hết ,giả sử d =1 ,khi đó cho
y= (x
4
-x
2
)
-1
mod (p-1)
ta có
β ≡ β
(x
4
-x

,q) =1. Giả sử:
y=(x
4
-x
2
)
-1
mod q
xét thấy (x
4
-x
2
)y = kq+1
với số nguyên k nào đó. Vì thế ta có:
β
(x
4
-x
2
)y
≡ β
kq+1
(mod p)
≡ (-1)
k
β (mod p)
≡ ± β (mod p)
Vì β
q
≡-1(mod p)

và q-1≥ x
3
≥ 0
nên
(q-1) ≥ x
4
-x
2
≥ -(q-1)
do vậy UCLN(x
4
-x
2
,p-1) không thể bằng q, nói cách khác trường hợp này
không xảy ra.
Xác suất cuối cùng là d = p-1. Điều nàychỉ xảy ra khi x2 =x4. Song khi
đó ta có
α
x
1
β
x
2
≡ α
x
3
β
x
4
(mod p)

Giả sử p =12347 (vì thế q = 6173), α = 2, β = 8461. Giả sử ta được
đưa trước một va chạm
α
5692
β
144
≡ α
212
β
4214
(mod 12347)
Như vậy x
1
= 5692, x
2
= 144, x
3
= 212, x
4
= 4214. Xét thấy UCLN (x
4
-x
2
,p-1)
=2 nên ta bắt đầu bằng việc tính
y = (x
4
- x
2
)

= 8461 (mod 12347)
Vì thế , ta các định được log
α
β.