Giáo trình Mật mã học (Phần 1)

 ph−ơng pháp đã nêu ở trên b−ớc c trong thuật toán 
trên để biến đổi m thμnh véctơ nhị phân M có độ dμi M: 
( )1,0,0,1,1,0,1M = 
(4) Tính ( ) 15212400modCCCCC 6320 =+++= 
(5) Gửi 1521C = cho A. 
4.6.3.3. Giải mã 
(1) Tính ( ) 19132400modhdcr =−= 
(2) Tính ( ) ( ) ( ) 5x2x3xxmodxgxu 231913 +++=ƒ= 
Ch−ơng 4: Mật mã khóa công khai 
147
(3) Tính ( ) ( ) ( ) xxx4xxfxuxg 234 +++=+= 
(4) Phân tích ( ) ( )( )( )6x3x2xxxs +++= 
(Do đó 6t,3t,2t,0t 4321 ==== ) 
(5) Các thμnh phần của M bằng 1 có các chỉ số 
 ( ) ( ) ( ) ( ) 06633220 1111 =π=π=π=π −−−− 
Bởi vậy ( )1,0,0,1,1,0,1M = 
(6) Sử dụng b−ớc f trong thuật toán giải mã để biến đổi M 
thμnh số nguyên m = 22 vμ nh− vậy khôi phục đ−ợc bản rõ ban đầu. 
4.6.4. Chú ý 
- Hệ mật nμy đ−ợc xem lμ an toμn nếu không bị lộ khóa bí mật. 
- Có thể mở rộng hệ mật nμy cho tr−ờng hợp pZ với p lμ luỹ 
thừa của một số nguyên tố. 
- Để lμm cho bμi toán logarit rời rạc lμ dễ giải, các tham số p 
vμ h phải chọn sao cho 1pq h −= chỉ có các nhân tử có giá trị nhỏ. 
- Trong thực tế, kích th−ớc khuyến nghị của các tham số lμ 
25h,200p ≈≈ (Ví dụ 197p = vμ 24h = ). 
- Trở ngại lớn nhất của thuật toán lμ khóa công khai với kích 
th−ớc chừng plogh.p bit lμ quá lớn. Ví dụ với 197p = vμ 24h = 
khóa công khai có chừng 36.000 bit. 
4.7. hệ mật McElice 
Hệ mật McEliece sử dụng nguyên lý t−ơng tự nh− hệ mật 
Merkle-Hellman. Phép giải mã lμ một tr−ờng hợp đặc biệt của bμi 
toán NP đầy đủ nh−ng nó đ−ợc ngụy trang giống nh− tr−ờng hợp 
Giáo trình Mật mã học 
148 
chung của bμi toán. Trong hệ thống nμy bμi toán NP đ−ợc áp dụng 
ở đây lμ bμi toán giải mã cho một mã sửa sai (nhị phân) tuyến 
tính nói chung. Tuy nhiên, đối với nhiều lớp mã đặc biệt đều tồn 
tại các thuật toán giải mã với thời gian đa thức. Một trong những 
lớp mã nμy lμ mã Goppa, chúng đ−ợc dùng lμm cơ sở cho hệ mật 
McEliece. 
4.7.1. Định nghĩa 1 
Giải sử k, n lμ các số nguyên d−ơng, nk ≤ . Mã [ ]k,nC lμ một 
không gian k chiều của ( )n2Z (không gian véctơ của tất cả các 
véctơ nhị phân n chiều). 
Ma trận sinh của mã [ ]k,nC lμ ma trận nhị phân nkì , các 
hμng của ma trận nμy tạo nên cơ sở của C. 
Giả sử ( )n2Zy,x ∈ , trong đó ( )n1 x,,xx K= vμ ( )n1 y,,yy K= . 
Ta xác định khoảng cách Hamming: ( ) { }ii yx,ni1:iy,xd ≠≤≤= 
tức lμ số các toạ độ mμ ở đó x vμ y khác nhau. 
Khoảng cách mã C đ−ợc định nghĩa nh− sau: 
 ( ) ( ){ }yx,Cy,x:y,xdminCd ≠∈= 
Mã [ ]k,n có khoảng cách d đ−ợc ký hiệu lμ mã [ ]d,k,n . 
Mã sửa sai đ−ợc dùng để sửa các sai ngẫu nhiên xảy ra khi 
truyền số liệu (nhị phân) qua kênh có nhiễu. Điều đó đ−ợc thực 
hiện nh− sau: Giả sử G lμ một ma trận sinh đối với mã [ ]d,k,n , x 
lμ véctơ nhị phân k chiều cần truyền đi. Ng−ời gửi Alice sẽ mã hoá 
x thμnh một véctơ n chiều Gxy = rồi truyền y qua kênh. 
Giả sử Bob nhận đ−ợc véctơ n chiều r không giống y, Bob sẽ 
giải mã r bằng chiến thuật giải mã "ng−ời láng giềng gần nhất". 
Ch−ơng 4: Mật mã khóa công khai 
149
Theo chiến thuật nμy, Bob sẽ tìm thấy từ y' có khoảng cách tới r 
nhỏ nhất. Sau đó anh ta giải mã r thμnh y', rồi xác định véctơ k 
chiều x' sao cho G'x'y = . Bob hy vọng y'y = vμ bởi vậy x'x = (tức 
lμ Bob tin rằng các sai số trên đ−ờng truyền đã đ−ợc sửa). 
Dễ dμng thấy rằng, nếu sai số trên đ−ờng truyền nhiều nhất 
lμ ( ) 2/1d − thì trên thực tế chiến thuật nμy sẽ sửa đ−ợc tất cả 
các sai. 
Ta xét trên thực tế, thuật toán giải mã nμy đ−ợc thực hiện 
nh− thế nμo? Vì k2C = nên Bob so sánh r với mỗi từ mã anh ta 
phải kiểm tra k2 véctơ lμ một số lớn theo hμm mũ so với k. Nói 
cách khác, thuật toán nμy không phải lμ thuật toán chạy trong 
thời gian đa thức. 
Một biện pháp khác (tạo cơ sở cho nhiều thuật toán giải mã 
thực tế) dựa trên khái niệm về syndrom. Ma trận kiểm tra tính 
chẵn lẻ của mã [ ]d,k,nC (có ma trận sinh G) lμ một mã trận nhị 
phân ( ) nkn ì− chiều (ký hiệu lμ H). Các hμng của H sẽ tạo cơ sở 
cho các phần bù trực giao của C (ký hiệu lμ ⊥C ) vμ đ−ợc gọi lμ mã 
đối ngẫu với C. Nói cách khác, các hμng của H lμ những véctơ độc 
lập tuyến tính, còn ⊥HG lμ một ma trận không cấp k ì (n – k). 
Cho véctơ ( )n2Zr ∈ , ta xác định syndrom của r lμ ⊥rH . 
Syndrom ⊥rH lμ một véctơ cột có ( )kn − thμnh phần. 
4.7.2. Định lý 2 
Giả sử C lμ một mã [ ]k,n có ma trận sinh G vμ ma trận kiểm 
tra tính chẵn lẻ H. Khi đó ( )n2Zx ∈ lμ một từ mã khi vμ chỉ khi 
[ ]TT 000xH K= . 
Giáo trình Mật mã học 
150 
Hơn nữa nếu ( )n2Ze,Cx ∈∈ vμ exr += thì TT eHxH = . 
Ta coi e lμ véctơ sai xuất hiện trong quá trình truyền từ mã 
x. Khi đó r biểu diễn véctơ thu đ−ợc. Định lý trên phát biểu rằng 
syndrom chỉ phụ thuộc vμo các sai số mμ không phụ thuộc vμo từ 
mã cụ thể nμo đ−ợc truyền đi. 
Điều nμy gợi ý tới một cách giải mã gọi lμ giải mã theo 
syndrom. Tr−ớc tiên tính TrHs = nếu s lμ một véctơ không, thì ta 
giải mã r thμnh r. Nếu không thì ta sẽ lần l−ợt tạo tất cả các véctơ 
sai có trọng số 1. Với mỗi véctơ nμy, ta tính TeH . Nếu có một 
véctơ e nμo đó thỏa mãn seH T = thì ta giải mã r thμnh er − . 
Ng−ợc lại, lại tiếp tục tạo các véctơ sai có trọng số ( )[ ]2/1d,,3,2 −K . 
Theo thuật toán nμy, có thể giải mã cho một véctơ nhận đ−ợc 
trong nhiều nhất ⎟⎟
⎟
⎠
⎞
⎜⎜
⎜
⎝
⎛ −++⎟⎟⎠
⎞
⎜⎜⎝
⎛+
2
1d
n
1
n
1 K b−ớc. 
Ph−ơng pháp nμy lμm việc trên một mã tuyến tính bất kỳ. 
Đối với một số loại mã đặc biệt, thủ tục giải mã có thể nhanh 
chóng hơn. Tuy nhiên, trên thực tế, cách giải quyết nμy cho chiến 
thuật giải mã "ng−ời láng giếng gần nhất" vẫn lμ một bμi toán NP 
đầy đủ. Nh− vậy, vẫn ch−a có một thuật toán giải trong thời gian 
đa thức đã biết nμo cho bμi toán giải mã theo "ng−ời láng giềng 
gần nhất" tổng quát. (Khi số các sai số không bị giới hạn bởi 
( )[ ]2/1d − ). 
Cũng giống nh− bμi toán tổng tập con, có thể chỉ ra một 
tr−ờng hợp đặc biệt "dễ", sau đó ngụy trang sao cho nó giống với 
bμi toán chung "khó". Để đ−a ra lý thuyết sẽ rất dμi dòng, bởi vậy 
Ch−ơng 4: Mật mã khóa công khai 
151
ta sẽ chỉ tóm l−ợc các kết quả ở đây. Một tr−ờng hợp khá dễ đ−ợc 
McEliece đề nghị lμ dùng một mã trong lớp các mã Goppa. Trên 
thực tế, các mã nμy có một thuật toán giải mã hữu hiệu. Hơn nữa 
các, các mã nμy rất dễ tạo vμ có một số l−ợng lớn các mã Goppa 
t−ơng đ−ơng có cùng tham số. 
Các tham số của mã Goppa có dạng 1t2d,2n m +== vμ 
mtnk −= . Để áp dụng trong thực tế cho một hệ mật khóa công 
khai, McEliece đề nghị chọn 10m = vμ 50t = . Điều nμy ứng với 
mã Goppa [ ]101,524,1024 . Mỗi bản rõ lμ một véctơ nhị phân cấp 
524 vμ mỗi bản mã lμ một véctơ nhị phân cấp 1024. Khoá công 
khai lμ một ma trận nhị phân cấp 524 ì 1024. Hình 4.1 sẽ mô tả 
hệ mật McEliece. 
Cho G là một ma trận sinh của một mã Goppa C[n, k, d], trong đó 
n = 2m, d = 2t + 1 và k = n - mt. Cho s là một ma trận khả nghịch cấp k ì k trên 
Z2. Giả sử P là một ma trận hoán vị cấp n ì n, ta đặt G' = SGP. Cho P = (Z2)2, 
C = (Z2)
n và ký hiệu: K = {(G, S, P, G')} 
Trong đó G, S, P đ−ợc xây dựng nh− mô tả ở trên và đ−ợc giữ kín, còn G' 
đ−ợc công khai. Với K = (G, S, P, G'), ta định nghĩa: ek(x, e) = xG' + e. ở đây, e 
∈ (Z2)n là một véctơ ngẫu nhiên có trọng số t. 
Bob giải mã bản mã y ∈ (Z2)n theo các b−ớc sau: 
1. Tính y1 = yP
-1. 
2. Giải mã (Decode) y1, Bob tìm đ−ợc y1 = x1 + e1, x1 ∈ C. 
3. Tính x0 ∈ (Z2)k sao cho x0G = x1. 
4. Tính x = x0S
-1. 
Hình 4.1: Hệ mật McEliece 
Để minh họa cho các thủ tục mã vμ giải mã (code and 
decode), xét ví dụ sau: 
Giáo trình Mật mã học 
152 
Ví dụ 1: Ma trận: 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
1111000
1100100
1010010
0110001
G 
lμ ma trận sinh của mã Hamming [ ]3,4,7 . Giả sử Bob chọn 
ma trận S vμ ma trận P nh− sau: 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
0011
1110
1001
1011
S vμ 
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎜
⎝
⎛
=
0010000
0100000
0000100
0000001
1000000
0001000
0000010
P 
Khi đó ma trận sinh công khai lμ: 
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
0111010
1011001
0010011
0001111
'G 
Bây giờ giả sử Alice mã hóa bản rõ x = (1, 1, 0, 1) bằng cách 
dùng một véctơ sai ngẫu nhiên trọng số 1 có dạng: e = (0, 0, 0, 1, 0, 0) 
Bản mã tính đ−ợc lμ: 
( ) ( )
( ) ( )
( )0,1,1,0,1,1,0
0,0,1,0,0,0,00,1,0,0,1,1,0
0,0,1,0,0,0,0
0111010
1011001
0010011
0001111
1,0,1,1
e'Gxy
=
+=
+
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
=
+=
Ch−ơng 4: Mật mã khóa công khai 
153
Khi Bob nhận đ−ợc bản mã y, tr−ớc hết anh ta tính 
( )
( )1,1,1,0,0,0,1
0000100
0100000
1000000
0000010
0010000
0000001
0001000
0,1,1,0,1,1,0Pyy 11
=
⎟⎟
⎟⎟
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜⎜
⎜⎜
⎜
⎝
⎛
== −
Tiếp theo Bob giải mã 1y để nhận đ−ợc ( )0,1,1,0,0,0,1x1 = 
(Cần để ý lμ ee1 ≠ do phép nhân với 1P − ) 
Sau đó anh ta lập ( )0,0,0,1x0 = (bốn thμnh phần đầu tiên 
của 1x ). 
Cuối cùng Bob tính: 
( ) ( )1,0,1,10,0,0,1
1001
1110
0011
1011
xSx 0
1 =
⎟⎟
⎟⎟
⎟
⎠
⎞
⎜⎜
⎜⎜
⎜
⎝
⎛
== − 
Đây chính lμ bản rõ mã Alice đã mã. 
4.8. các hμm băm vμ tính toμn vẹn của dữ liệu 
4.8.1. Mở đầu 
Các hμm băm đóng vai trò cơ bản trong mật mã hiện đại. 
Hμm băm sẽ tạo ra một đầu ra từ bản tin đầu vμo. Đầu ra nμy 
đ−ợc định nghĩa lμ mã băm (kết quả băm, giá trị băm). 
Giáo trình Mật mã học 
154 
Nói một cách chính xác hơn, hμm băm h sẽ tạo ra ánh xạ 
các xâu bit có độ dμi hữu hạn tuỳ ý thμnh các xâu bit có độ dμi n 
cố định. 
Hμm băm h lμ một ánh xạ có độ dμi n cố định RD:h → vμ 
RD > điều nμy có nghĩa lμ không thể tránh khỏi các va chạm 
(tức lμ cùng một giá trị đầu ra có thể có nhiều bộ giá trị vμo khác 
nhau). Nếu hμm h lμ ngẫu nhiên theo nghĩa tất cả các đầu ra lμ 
đồng xác suất thì có chừng nt2 − các đầu vμo ánh xạ tới mỗi đầu ra 
(t: số bit đầu vμo, n: số bit đầu ra, t > n) vμ 2 đầu vμo đ−ợc chọn 
ngẫu nhiên sẽ có cùng đầu ra với xác suất n2− (không phụ thuộc 
vμo t). 
ý t−ởng cơ bản của việc sử dụng các hμm băm trong mật mã 
lμ sử dụng chúng nh− một ảnh biểu diễn rút gọn (đôi khi còn đ−ợc 
gọi lμ vết, dấu tay số hay tóm l−ợc thông báo) của một xâu vμo vμ 
có thể đ−ợc dùng nh− thể nó chính lμ xâu vμo đó. 
Các hμm băm đ−ợc dùng cho các sơ đồ chữ ký số kết hợp với 
việc đảm bảo tính toμn vẹn của dữ liệu, khi đó bản tin tr−ớc hết 
đ−ợc băm vμ rồi giá trị băm (đ−ợc xem nh− đại diện cho bản tin) 
sẽ đ−ợc ký thay cho vị trí bản tin gốc. 
Một lớp các hμm băm đ−ợc gọi lμ các mã xác thực thông báo 
(MAC - Message Authentication Codes) sẽ cho phép xác thực 
thông báo bằng kỹ thuật đối xứng (mật mã cổ điển). 
Các thuật toán MAC sử dụng 2 đầu vμo (bao gồm bản tin vμ 
một khóa bí mật) để tạo ra một đầu ra có kích cỡ cố định (n bit) với 
ý đồ đảm bảo rằng nếu không biết khóa thì việc tạo ra cùng một 
Ch−ơng 4: Mật mã khóa công khai 
155
đầu ra lμ không khả thi. MAC có thể đ−ợc dùng để đảm bảo tính 
toμn vẹn của dữ liệu, xác thực tính nguyên bản của số liệu cũng 
nh− định danh trong sơ đồ mật mã cổ điển. 
Một ứng dụng điển hình của hμm băm (không dùng khóa) để 
đảm bảo tính toμn vẹn của dữ liệu có thể đ−ợc mô tả nh− sau: 
Giá trị băm t−ơng ứng với một bản tin riêng x sẽ đ−ợc tính ở 
thời điểm T1. Tính toμn vẹn của giá trị băm nμy (chứ không phải 
lμ bản thân bản tin) sẽ đ−ợc bảo vệ theo một cách nμo đó. ở thời 
điểm tiếp theo sau T2, phép kiểm tra sau sẽ đ−ợc tiến hμnh để xác 
định xem liệu thông báo có bị sửa đổi hay không, tức lμ xem liệu 
bản tin 'x có giống bản tin gốc hay không. Giá trị băm của 'x sẽ 
đ−ợc tính toán vμ so sánh với giá trị băm đã đ−ợc bảo vệ, nếu 
chúng bằng nhau thì bên thu sẽ chấp nhận rằng x vμ 'x lμ nh− 
nhau vμ nh− vậy có nghĩa lμ bản tin đã không bị sửa đổi. Nh− vậy 
vấn đề đảm bảo tính vẹn toμn của một bản tin lớn sẽ đ−ợc gửi về 
đảm bảo cho một giá trị băm có kích cỡ cố định (vμ nhỏ). 
ứng dụng trên th−ờng đ−ợc gọi lμ mã phát hiện sự sửa đổi 
(MDC - Manipulation Detection Codes). 
4.8.2. Các định nghĩa vμ tính chất cơ bản 
4.8.2.1. Định nghĩa hμm băm 
Hμm băm lμ một hμm h có ít nhất hai tính chất sau: 
a) Tính chất nén: h sẽ ánh xạ một đầu vμo x có độ dμi bit hữu 
hạn tùy ý tới một đầu ra h(x) có độ dμi bit n hữu hạn. 
b) Tính chất dễ dμng tính toán: Với h cho tr−ớc vμ một đầu 
vμo x, có thể dễ dμng tính đ−ợc h(x). 
Giáo trình Mật mã học 
156 
4.8.2.2. Một số tính chất của các hμm băm không có khóa 
Giả sử h lμ một hμm băm không có khóa, x vμ 'x lμ các đầu 
vμo y vμ 'y lμ các đầu ra. Ngoμi hai tính chất cơ bản trên ta còn có 
3 tính chất sau: 
a) Tính khó tính toán nghịch ảnh: 
Đối với hầu hết các đầu ra đ−ợc xác định tr−ớc, không có khả 
năng tính toán để tìm một đầu vμo bất kỳ mμ khi băm sẽ cho ra 
đầu ra t−ơng ứng (Tức lμ tìm một nghịch ảnh x' sao cho ( ) y'xh = 
với y cho tr−ớc vμ không biến đầu vμo t−ơng ứng). 
b) Tính khó tìm nghịch ảnh thứ hai: 
Không có khả năng tính toán để tìm một đầu vμo đã cho 
tr−ớc (Tức lμ với x cho tr−ớc phải tìm x'x ≠ sao cho ( ) ( )'xhxh = ). 
c) Tính khó va chạm 
Không có khả năng về tính toán để tìm hai đầu vμo khác 
nhau bất kỳ x vμ 'x để ( ) ( )'xhxh = . 
4.8.2.3. Định nghĩa hμm băm một chiều (OWHF - oneway 
 hash function) 
OWHF lμ một hμm băm (có hai tính chất cơ bản) có tính chất 
bổ sung lμ : 
- Khó tìm nghịch ảnh 
- Khó tìm nghịch ảnh thứ hai. 
4.8.2.4. Định nghĩa hμm băm khó va chạm (CRHF: Collision 
 resistant HF) 
CRHF lμ một hμm băm (có hai tính chất cơ bản) có tính chất 
bổ sung lμ: 
Ch−ơng 4: Mật mã khóa công khai 
157
- Khó tìm nghịch ảnh thứ hai 
- Khó vμ chạm. 
4.8.2.5. Chú ý về các thuật ngữ 
Khó tìm nghịch ảnh ≡ Một chiều. 
Khó tìm nghịch ảnh thứ hai ≡ Khó va chạm yếu. 
Khó va chạm ≡ Khó va chạm mạnh. 
OWHF ≡ Hμm băm một chiều yếu. 
CRHF ≡ Hμm băm một chiều mạnh. 
4.8.2.6. Ví dụ 
r bit kiểm tra của một mã xyclic ( )k,n với k > r có thể coi lμ 
một hμm băm thoả mãn hai tính chất cơ bản (dễ tính toán vμ 
nén). Tuy nhiên nó không thoả mãn tính chất khó tìm nghịch ảnh 
thứ hai. 
4.2.8.7. Định nghĩa thuật toán mã xác thực thông báo (MAC) 
Thuật toán MAC lμ một họ các hμm kh (đ−ợc tham số hóa 
bằng một khóa bí mật k) có các tính chất sau: 
(1) Dễ dμng tính toán: Với kh đã biết vμ giá trị k cho tr−ớc vμ 
một đầu vμo x, ( )xhk có thể đ−ợc tính dễ dμng ( ( )xhk đ−ợc gọi lμ 
giá trị MAC hay MAC). 
(2) Nén: kh ánh xạ một đầu vμo x có độ dμi bit hữu hạn tuỳ 
tới một đầu ra ( )xhk có độ dμi bit n cố định. 
(3) Khó tính toán: Với các cặp giá trị ( )( )iki xh,x không có khả 
năng tính một cặp ( )( )xh,x k với ixx ≠ (kể cả có khả năng 
( ) ( )ikk xhxh = với một i nμo đó). 
Giáo trình Mật mã học 
158 
Nếu tính chất c không thỏa mãn thì thuật toán đ−ợc coi lμ 
giả mạo MAC. 
4.8.2.8. Phân loại các hμm băm mật mã vμ ứng dụng 
Hình 4.2 
4.8.3. Các hμm băm không có khóa 
(Các hμm băm dựa trên mật mã khối). 
4.8.3.1. Định nghĩa 1 
Mật mã khối (n, r) lμ một mã khối xác định một hμm khả 
nghịch từ các bản rõ n bit sang các bản rõ n bit bằng cách sử dụng 
một khóa r bit. Nếu E lμ một phép mã hoá nh− vậy thì ( )xEk ký 
hiệu cho phép mã hoá x bằng khóa k. 
4.8.3.2. Định nghĩa 2 
Cho h lμ một hμm băm có lặp đ−ợc xây dựng từ một mật mã 
khối với hμm nén f thực hiện s phép mã hoá khối để xử lý từng 
khối bản tin n bit. Khi đó tốc độ của h lμ 1/s. 
MDC Các ứng dụng khác
OWHF CRHF 
Các ứng dụng khác MDC
Hàm băm
Không có khóa Có khóa
Ch−ơng 4: Mật mã khóa công khai 
159
4.8.3.3. MDC độ dμi đơn 
Ba sơ đồ d−ới đây có liên quan chặt chẽ với các hμm băm độ 
dμi đơn, xây dựng trên các mật mã khối. Các sơ đồ nμy có sử dụng 
các thμnh phần đ−ợc xác định tr−ớc nh− sau: 
- Một mật mã khối n bit khởi sinh kE đ−ợc tham số hóa bằng 
một khóa đối xứng k. 
- Một hμm g ánh xạ n bit vμo thμnh khóa k sử dụng cho E 
(Nếu các khóa cho E cũng có độ dμi n thì g có thể lμ hμm đồng nhất). 
- Một giá trị ban đầu cố định IV thích hợp để dùng với E. 
g E
Hi-1
xi
Hi
E
Hi-1
Hi
g E
Hi-1
xi
Hi
Matyas - Mayer - Oseas
xi
Davies - Mayer Miyaguchi - Preneel 
Hình 4.3 
4.8.3.3.1. Thuật toán băm Matyas - Mayer - Oseas 
Vμo: Xâu bit x. 
Ra : Mã băm n bit của x. 
(1) Đầu vμo x đ−ợc phân chia thμnh các khối n bit vμ đ−ợc 
độn nếu cần thiết nhằm tạo khối cuối cùng hoμn chỉnh. Ta đ−ợc t 
khối n bit: t21 xxx K . Phải xác định tr−ớc một giá trị ban đầu n 
bit (ký hiệu IV). 
Giáo trình Mật mã học 
160 
(2) Đầu ra lμ tH đ−ợc xác định nh− sau: 
( ) ( ) ti1,xxEH,IVH iiHgi0 1i ≤≤⊕== − . 
4.8.3.3.2. Thuật toán băm Davies - Mayer 
Vμo: Xâu bit x 
Ra : Mã băm n bit của x 
(1) Đầu vμo x đ−ợc phân thμnh các khối k bit (k lμ kích th−ớc 
khóa) vμ đ−ợc độn nếu cần thiết để tạo khối cuối cùng hoμn chỉnh. 
Biểu thị thông báo đã độn thμnh t khối n bit: t21 xxx K . Xác 
định tr−ớc một giá trị ban đầu n bit (ký hiệu IV). 
(2) Đầu ra lμ tH đ−ợc xác định nh− sau: 
( ) ti1,HHEH,IVH 1i1ixii0 ≤≤⊕== −− . 
4.8.3.3.3. Thuật toán băm Miyaguchi - Preneel 
Sơ đồ nμy t−ơng tự nh− C1 ngoại trừ 1iH − (đầu ra ở giai 
đoạn tr−ớc) đ−ợc cộng 2mod với tín hiệu ra ở giai đoạn hiện thời. 
Nh− vậy: 
 ( ) ( ) ti1,HxxEH,IVH 1iiiHgi0 1i ≤≤⊕⊕== −− . 
Nhận xét: Sơ đồ D_M có thể coi lμ sơ đồ đối ngẫu với sơ đồ 
M - M - O theo nghĩa ix vμ 1iH − đổi lẫn vai trò. 
4.8.3.4. MDC độ dμi kép: MDC - 2 vμ MDC - 4 
MDC -2 vμ MDC - 4 lμ các mã phát hiện sự sửa đổi yêu cầu 
t−ơng ứng lμ 2 vμ 4 phép toán mã hoá khối trên mỗi khối đầu vμo 
hμm băm. Chúng sử dụng 2 hoặc 4 phép lặp của sơ đồ M - D - O để 
tạo ra hμm băm có dộ dμi kép. Khi dùng DES chúng sẽ tạo ra mã 
băm 128 bit. Tuy nhiên trong cấu trúc tổng quát có thể dùng các 
Ch−ơng 4: Mật mã khóa công khai 
161
hệ mật mã khối khác MDC-2 vμ MDC4 sử dụng các thμnh phần 
xác định nh− sau: 
- DES đ−ợc dùng lμm mật mã khối Ek có đầu vμo/ra 64 bit vμ 
đ−ợc tham số hoá bằng khóa k 56 bit. 
- Hai hμm g vμ g~ ánh xạ các giá trị 64 bit U thμnh các khóa 
DES 56 bit nh− sau: 
Cho 6421 uuuU K= , xóa mọi bit thứ 8 bắt đầu từ u8 vμ đặt 
các bit thứ 2 vμ thứ 3 về "10" đối với g vμ "01" đối với g~ . 
( )
( ) 6310976541
6310976541
uuuuuuu10uUg~
uuuuuuu01uUg
K
K
=
=
Đồng thời điều nμy cũng phải đảm bảo rằng chúng không 
phải lμ các khóa DES yếu hoặc nửa yếu vì các khóa loại nμy có bit 
thứ hai bằng bit thứ ba. Đồng thời điều nμy cũng đảm bảo yêu cầu 
bảo mật lμ ( ) ( )IVg~IVg ≠ . 
Thuật toán MDC - 2 có thể đ−ợc mô tả theo sơ đồ sau: 
g E
Hi-1
Hi
int 3
A B
A D
gE
Hi-1
xi
int 4
A B
A D
int 1 int 2
out 1
Hi
out 2
Hình 4.4 
Giáo trình Mật mã học 
162 
4.8.3.4.1. Thuật toán MDC - 2 
Vμo: Xâu bit x có độ dμi r = 64t với 2t ≥ . 
Ra : Mã băm 128 bit của x 
(1) Phân x thμnh các khối 64 bit ix : t21 xxx K . 
(2) Chọn các hằng số không bí mật IV vμ V~I từ một tập các 
giá trị khuyến nghị đã đ−ợc mô tả tr−ớc. Tập ngầm định các giá 
trị cho tr−ớc nμy lμ (ở dạng HEXA): 
2525252525252525x0V~I
5252525252525252x0IV
=
=
(3) Ký hiệu⎟⎟ lμ phép ghép vμ RiLi C,C lμ các nửa 32 bit phải 
vμ trái của Ci 
Đầu ra ( ) tt H~Hxh = đ−ợc xác định nh− sau: (với ti1 ≤≤ ) 
( ) ( )
( ) ( ) RiLiiiiik~i1ii0
R
i
L
iiiikii1ii0
CC~H~,xxEC~,H~g~k~,V~IH~
C~CH,xxEC,Hgk,IVH
=⊕===
=⊕===
−
−
Thuật toán MDC - 4 có thể đ−ợc mô tả theo sơ đồ sau: 
MDC - 2
MDC - 2
int 1
xi
int 2
int 2
int 1
int 3 int 4
out 1 out 2
Hi
Gi
Gi-1
Gi-1 Gi-1
Hi
Gi
Gi-1
Hình 4.5 
Ch−ơng 4: Mật mã khóa công khai 
163
4.8.4.Các hμm băm có khóa (MAC) 
Các hμm băm có khóa đ−ợc sử dụng để xác thực thông báo vμ 
th−ờng đ−ợc gọi lμ các thuật toán tạo mã xác thực thông báo 
(MAC). 
MAC dựa trên các mật mã khối. 
Thuật toán 
Vμo: Dữ liệu x, mật mã khối E, khóa MAC bí mật k của E. 
Ra : n bit MAC trên x (n lμ độ dμi khối của E) 
(1) Độn vμ chia khối: Độn thêm các bit vμo x nếu cần. Chia 
dữ liệu đã độn thμnh từng khối n bit : t21 xxx K . 
(2) Xử lý theo chế độ CBC. 
Ký hiệu kE lμ phép mã hóa E với khóa k. 
Tính khối tH nh− sau: 
( )
( ) .ti2;xHKH
xEH
i1iki
1k1
≤≤⊕←
←
−
(3) Xử lý thêm để tăng sức mạnh của MAC 
Dùng một khóa bí mật thứ hai k'k ≠ . Tính 
( ) ( )'tktt1'k't HEH,HEH =← − 
(4) Kết thúc: MAC lμ khối n bit Ht. 
E
IV = 0
E
x1
H1
k
E
H2
k
x2 x3
H3
E
xt
K
E
K'
E
K
Ht
Ht
H't
Xử
lý
thêm
Hình 4.6: Thuật toán MAC dùng CBC