-
1
-HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
******************************************** HỒ QUANG BỬU

VỀ MỘT PHƯƠNG PHÁP XÂY DỰNG HÀM
BĂM CHO VIỆC XÁC THỰC TRÊN CƠ SỞ
ỨNG DỤNG CÁC THUẬT TOÁN MÃ HÓA ĐỐI
XỨNG
LUẬN ÁN TIẾN SĨ KỸ THUẬT
LUẬN ÁN TIẾN SĨ KỸ THUẬT

NGƯỜI HƯỚNG DẪN KHOA HỌC
1. GS.TSKH. NGUYỄN XUÂN QUỲNH
2. GS.TS. NGUYỄN BÌNH
HÀ NỘI - 2014 -
26
-
bản rõ đầu vào giống nhau và sử dụng cùng một khóa thì bản mã
đầu ra sẽ giống nhau. Ngoài ra các M-dãy đề xuất trong luận án
hoàn toàn có thể sử dụng mật mã dòng.
 Xây dựng một hàm băm mới có độ dài 128 bit với khối mật mã
được xây dựng trên các cấp số nhân cyclic. Đây là cơ sở để xây
dựng thêm các hàm băm mới với một số ưu điểm: (1) phương
pháp mã hóa đơn giản hơn, (2) có thể dễ dàng mở rộng độ dài
mã băm nhằm mục đích hạn chế phép tấn công ngày sinh nhật,
(3) hàm băm có độ khuếch tán (hay hỗn loạn) khá tốt (đây là một
tính chất quan trọng của hàm băm). Theo các kết quả mô phỏng
đánh giá tính khuếch tán của hệ mật mới và của các hàm băm đề
xuất cho thấy tính khuếch tán khá tốt. Với hệ mật thì độ khuếch
tán tương đương DES, với hàm băm độ khuếch tán đạt xấp xỉ

xác thực (Authentication); (3) đảm bảo tính toàn vẹn (Integrity).
Tình hình nghiên cứu
Cho đến nay các nghiên cứu về hàm băm được chia thành hai
loại: hàm băm không khóa và hàm băm có khóa, và thông thường các
hàm băm này dựa trên mật mã khối với hai phương pháp chính là Mã
phát hiện sửa đổi (MDC-Manipullation Detection Code) và Mã xác
thực thông báo (MAC-Message Authentication Code).
Các hàm băm dựa trên mật mã khối đã được nghiên cứu khá
mạnh trên thế giới, các nhóm nghiên cứu tập trung chủ yếu vào
hướng xây dựng các hệ mật mã khối và đưa chúng vào lược đồ xây
dựng hàm băm. Các lược đồ được sử dụng để xây dựng hàm băm phổ
biến bao gồm: (1) Matyas – Mayer – Oseas (M-M-O); (2) Davies –

-
4
-

Mayer (D-M); (3) Miyaguchi – Preneel (M-P); (4) MDC-2; (5)
MDC-4…
Hiện nay trên thế giới có khá nhiều hệ mật mã khối khóa bí mật
đã được nghiên cứu sử dụng cho các lược đồ xây dựng hàm băm như
trên, điển hình là các hệ mật sau: DES, IDEA, RD.5, TDEA, AES,
CAST,… Những nghiên cứu về các hệ mật này và phương pháp sử
dụng chúng cho lược đồ hàm băm đã xuất hiện trong rất nhiều công
trình từ rất nhiều năm qua, tuy nhiên chúng đã được tổng kết trong
các công trình sau:
 Knudsen, L.; Preneel, B; Construction of secure and fast hash
functions using nonbinary error-correcting codes, IEEE
Transactions on Information Theory, Volume 48, Issue 9,
Sept. 2002 Page(s): 2524 - 2539.

[ ]/ 1
n
x x

Z với
2
k
n

,
(Vành đa thức này là vành chẵn đặc biệt và không được xem xét
trong lý thuyết mã sửa sai), do đó dễ dàng mở rộng độ dài từ, (3)
Một số mô phỏng đánh giá cho thấy kết quả khuếch tán của hệ
mật khá tốt (tương đương DES).
 Đề xuất phương pháp tạo khóa cho hệ mật từ các M-dãy theo các
cấp số nhân của vành đa thức có hai lớp kề cyclic, đây cũng là
vành đặc biệt và ít được dùng trong lý thuyết mã sửa sai. Các M-
dãy xây dựng theo phương pháp này có chu kỳ lớn và cũng đảm
bảo tính chất giả ngẫu nhiên của dãy. Trong luận án đã sử dụng
các M-dãy trên vành
61
1
x

vào việc tạo các khóa con bên trong
hệ mật, cụ thể là 16 khóa con cho 16 vòng mã hóa theo sơ đồ
Feistel. Do số lượng khóa tạo được rất nhiều (
60
2 1


-

Phạm vi nghiên cứu của luận án
Luận án thuộc phạm vi lý thuyết cơ sở, tập trung nghiên cứu
các thuật toán mã hóa và sử dụng chúng trong lược đồ xây dựng các
hàm băm. Các thuật toán mã hóa và sơ đồ tạo khóa trong các sơ đồ
mã hóa được xây dựng trên cấu trúc cấp số nhân cyclic, đây là một
cấu trúc đại số được xây dựng trên cơ sở là nhóm nhân cyclic trên
vành đa thức.
Phương pháp nghiên cứu
Phương pháp nghiên cứu của đề tài là phân tích và tổng hợp
dựa vào các công cụ toán học, đặc biệt là đại số đa thức, lý thuyết
thông tin và mã hóa, lý thuyết xác xuất cùng với sự hỗ trợ tính toán
của máy tính và các chương trình phần mềm mô phỏng để thử
nghiệm đánh giá.
Ý nghĩa khoa học và thực tiễn của luận án
Những kết quả trong luận án này là một đóng góp nhỏ bé vào việc
phát triển lý thuyết mật mã nói chung và các hàm băm nói riêng. Các
nghiên cứu trong luận án đưa ra được một phương pháp xây dựng
mật mã khối và một số hàm băm trên cơ sở là các cấp số nhân cyclic
của vành đa thức.
Bố cục của luận án
Luận án gồm phần mở đầu, 4 chương nội dung, phần kết luận,
chương trình mô phỏng.
Chương 1. Luận văn tập trung tìm hiểu các vấn đề chung nhất về
mật mã khóa bí mật (hay còn gọi là mật mã cổ điển) và mật mã khóa
công khai (hay mật mã hiện đại), từ đó phân tích các ưu và nhược
điểm của từng hệ mật.

-

Bảng 3.3. Khoảng cách Hamming trung bình khi thay đổi khóa K và thay đổi bản tin rõ.
Bản tin thứ
i

1 2 3 4 5
 
i
H tb
d
63,27 63,67 64,23 64,67 64,50
Bản tin thứ
i

6 7 8 9 10
 
i
H tb
d
62,30 63,87 65,37 64,33 63,97
Khoảng cách Hamming trung bình tính được:
 
10
( )
1
1
64,02
10
i
H tb
H tb

giữa các cặp giá trị băm
khi các khóa khác khóa
1
K

2 bit.
TT Khóa K
i
Giá trị băm MD
i

1
( , )
H i
d MD MD
1 123456789ABCDEF1 53C51349140008F9AA66F954C307AD44 0
2
B23456789ABCDEF1
537140BB7C26F26EDD57CFDDA9CE1B8F 64
3
173456789ABCDEF1
2BA0259D1F16C021F3A22319AF753ED0 60
4
126456789ABCDEF1
A9FD04E4E1BAC7C06119B3FBD8FFD12D 78
5
123E56789ABCDEF1
773979064BE2FC31F0BE347B1EB2D776 72
6 1234F6789ABCDEF1 CD24285FFA002E865E8AECFACEAB37A5 66
7

băm ban đầu:
16
( ) 1
2
1
( , ) 64,13
15
H tb H i
i
d d MD MD

 


Để khảo sát thêm tính khuếch tán của hàm băm, ta thay đổi cả bản
tin rõ và khóa như sau: Giữa nguyên bản tin và lần lượt thay đổi từng
bit của khóa K
1
từ bit 1 đến bit 60, bit 61 dùng để kiểm tra chẵn lẻ.
Sau đó tính khoảng cách Hamming trung bình giữa các giá trị băm
với giá trị băm ban đầu theo công thức:
60
( ) 1
2
1
( , )
60
H tb H i
i
d d MD MD





1
,
K K
M E C D C D C K

  
Trong đó: M – bản rõ; C – bản mã; K – khóa
* Các phương pháp xử lý thông tin số trong các hệ thống mật
mã bao gồm:
+ Mật mã khóa bí mật:
 Hoán vị.
 Thay thế.
 Xử lý bit (chú yếu trong các ngôn ngữ lập trình)
 Phương pháp hỗn hợp (điển hình là chuẩn mã hóa dữ
liệu – DES của Mỹ)
+ Mật mã khóa công khai:
Xây dựng trên 5 bài toán cơ bản:
 Bài toán logarith rời rạc
 Bài toán phân tích thừa số
 Bài toán xếp ba lô
 Bài toán mã sửa sai
 Bài toán đường cong eliptic
+ Mật mã khối: quá trình xử lý thông tin được thực hiện trong
các khối có độ dài xác định.
+ Mật mã dòng: quá trình xử lý thông tin thực hiện trên từng
bit.

của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng
cách sắp xếp lại các ký tự này. Ở đây không có một phép toán đại số
nào cần thực hiện khi mã hoá và giải mã.
1.2.4. Hệ mật mã tích
1.2.5. Các hệ mật mã dòng và tạo dãy giả ngẫu nhiên
1.2.6. Chuẩn mã dữ liệu DES

-
21
-
0123456789AB
4
DEF

C3D7A66C29F82331
31
0123456789ABCDEF
0123456789ABCCEF
8353E1BF4DB4264B
6D7007E1DFA73B51
64
32
0123456789ABCDEF
0123456789ABCDFF
7945A131C04B6182
ED6E54D50BE28723
62
33
0123456789ABCDEF
0123456789ABCDED



Bảng 3.2 là kết quả tính toán phân bố của bộ mã khi thay đổi khóa
khởi tạo
K
, mỗi khóa khác với khóa đầu tiên 2 bit. Sở dĩ ta phải thay
đổi 2 bit (tương ứng thay đổi 2 vị trí) là để đảm bảo đa thức sinh của
khóa có trọng số lẻ.
Bản tin đầu vào gồm 10 khối 128 bit được tạo ngẫu nhiên [2].
Chú ý, chiều dài của khóa là 61 bit, do đó khi mô tả khóa bằng 16
ký tự hexa nhưng thực tế chỉ có 15 ký tự đầu là dạng hexa, còn ký tự
cuối cùng chỉ có 1 bit nên nó nhận giá trị “1” hoặc “0”.
Chọn phần tử đầu của cấp số nhân tạo khóa là:
2
1
a
K x x
  

Phần tử sinh khóa đầu tiên
1
K
như sau:
1( )
123456789ABCDEF.1
Hex
K  (
1
( ) 33
W K

20
-
0123456789ABCDEF A9C64A47762FF6BD
8
012345
7
789ABCDEF

0123456789ABCDEF
0CA4992082D77070
73C61EA33CE5D66D
68
9
0123456
3
89ABCDEF

0123456789ABCDEF
1E25F66DC86E2888
44CCBDC4367DA463
64
10
01234567
9
9ABCDEF

0123456789ABCDEF
1AD3061B585D4602
FBEBA645F50D0203
58

14
0123456789AB
8
DEF

0123456789ABCDEF
AD5C0C8D0A61348B
B96861BE92EEBB16
64
15
0123456789ABC
5
EF

0123456789ABCDEF

7906EF1395B4DE95
522E47E70DD5C738

64
16
0123456789ABCD
F
F

0123456789ABCDEF

FD4109489863FD3B
4E79C434BF8355DC



66
21
0123456789ABCDEF
0121456789ABCDEF
ADFA46A0CEC37C5A
E0C53DAF31B45B8D

68
22
0123456789ABCDEF
0123056789ABCDEF
A0A88D98F147A0D7
C4284C7EAF58BC1F
68
23
0123456789ABCDEF
0123416789ABCDEF
8DD5B3218D448641
313E52AD01747037
68
24
0123456789ABCDEF
0123457789ABCDEF
62F9919F4FF1A2AE
27C31BD6042FBB04
54
25
0123456789ABCDEF
0123456589ABCDEF

9
-

Mô tả đầy đủ của DES được nêu trong Công bố số 46 về các
chuẩn xử lý thông tin Liên bang (Mỹ) vào 15/1/1977. DES mã hoá
một xâu bit x của bản rõ độ dài 64 bằng một khoá 54 bit. Bản mã
nhận được cũng là một xâu bit có độ dài 64.
Thuật toán DES thường được thực hiện qua 16 vòng mã hóa
theo lược đồ Feistel, hàm mã hóa trong mỗi bước được thực hiện kết
hợp giữa các phép hoán vị và thay thế.
1.2.7 Ưu nhược điểm của mật mã khóa bí mật
Ưu điểm:
 Đơn giản (thời gian nhanh, yêu cầu phần cứng không phức tạp)
 Hiệu quả: (Tỷ lệ mã bằng 1) dễ sử dụng cho các ứng dụng
nhạy cảm với độ trễ và các ứng dụng di động.
Nhược điểm:
Phải dùng kênh an toàn để truyền khóa (Khó thiết lập và chi phí
tốn kém)
 Việc tạo và giữ khóa bí mật phức tạp, khó làm việc trên
mạng do phải tạo khóa nhiều.
 Các thuật toán là song ánh, vì vậy nếu biết M và K thì chắc
chắn biết C. Thám mã có thể suy luận ra K, kết hợp với C tại
kênh mở có thể suy ra M.
 Khó xây dựng các dịch vụ an toàn khác như: đảm bảo tính
toàn vẹn, xác thực, chữ ký số…
Vì các nhược điểm này nên phải sử dụng cả các hệ mật khóa công
khai. -

Ưu điểm của hệ mật khóa công khai:
 Không cần tạo 2 khóa bí mật
 Không cần kênh an toàn riêng
 Biết khóa mã hóa trên kênh mở nhưng rất khó giải mã.
Yêu cầu: Dễ mã hóa, khó giải mã (Hàm một chiều)
Các hướng nghiên cứu từ năm 1976 cho đến nay đã tìm được 5
hàm một chiều, tương ứng với 5 bài toán là các bài toán:
- Bài toán logarith rời rạc: Với các hệ mật tiêu biểu như: Thủ tục
trao đổi khóa Diffie – Hellman, hệ mật Omura-Massey, hệ mật
Elgamal.
- Bài toán phân tích thừa số và hệ mật RSA.
- Bài toán xếp ba lô với hệ mật Merkle – Hellman
- Bài toán mã sửa sai và hệ mật Mc.Eliece
- Hệ mật xây dựng trên đường cong Elliptic.

-
19
-
0 là kết quả tính toán phân bố của 32 hàm băm khi thay đổi duy
nhất một bit dữ liệu trong 32 khối bản tin rõ so với bản tin ban đầu,
để thuận tiện cho việc quan sát chúng tôi chỉ thay đổi 1 bit trong
chuỗi bản tin đầu tiên của một khối.
Mỗi khối bản tin bao gồm 10 bản tin, mỗi bản tin có độ dài 128
bit. Các hàm băm sử dụng cùng một bộ khóa
K
khởi tạo:
Phần tử sinh của khóa khởi tạo là đa thức:
9 18 27 36
1
i

khi các khối dữ liệu
khác khối ban đầu 1 bit
TT Bản rõ
Giá trị băm
1
( , )
H i
d MD MD

1
0123456789ABCDEF
0123456789ABCDEF
4771249F4AB0E564
908F1456E0D3A239
0
2
2
123456789ABCDEF

0123456789ABCDEF
7B13337D3B31DC7B
91287CE5FCDFD274
56
3
0
3
23456789ABCDEF

0123456789ABCDEF
995F0EF13134BFAF

7
6789ABCDEF

09B62BF471BA9644 60

-
18
-
với
a
K
là một đa thức có trọng số lẻ tùy ý sao cho:
deg 61
a
K

;
0
K
là một phần tử nguyên thủy của nhóm nhân cyclic có cấp bằng
60
2 1

và cũng là một đa thức có trọng số lẻ [3].
Giả sử ta chọn khóa:
3
0
1
K x x
  Sơ đồ khối mã hóa f với khóa
4 5
1
1
K x x
  
Một khâu mã hóa được thực hiện theo quy tắc:
 
1
1 1
,
i i i
i i i i
L R K
R L f R K

 
 



 



Khối g

Trong chương 1, luận án tập trung tìm hiểu các vấn đề chung nhất
về mật mã khóa bí mật (hay còn gọi là mật mã cổ điển) và mật mã
khóa công khai (hay mật mã hiện đại), từ đó phân tích các ưu và
nhược điểm của từng hệ mật.
Các nghiên cứu về cấu trúc nhóm nhân và cấp số nhân cyclic trên
vành đa thức cho các kết quả khá lý thú trong việc xây dựng các mã
sửa sai và mật mã. Để tăng chiều dài cho mật mã khối có thể sử dụng
cấu trúc các cấp số nhân cyclic trong các hàm mật mã, nội dung này
sẽ được trình bày trong chương 2. -
12
-
CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN
CÁC CẤP SỐ NHÂN CYCLIC
2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC
Trong mục này luận án đề cập đến các vấn đề:
- Định nghĩa nhóm nhân cyclic trên vành đa thức.
- Phân loại nhóm nhân cyclic.
2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC
Bao gồm các nội dung:
- Khái niệm về cấp số nhân cyclic trên vành đa thức.
- Phân hoạch vành đa thức: khái niệm về phân hoạch, các bước
phân hoạch vành đa thức, các kiểu phân hoạch.
2.3. XÂY DỰNG M-DÃY LỒNG GHÉP TRÊN VÀNH ĐA THỨC CÓ
HAI LỚP KỀ CYCLIC
Trong mục này luận án đề cập đến các vấn đề:
- Vành đa thức có hai lớp kề.
- Các M-dãy xây dựng trên vành đa thức.

H
có độ dài 128 bit. Khối mật mã E trong sơ đồ này được xây dựng
theo mô hình mạng hoán vị thay thế Feistel (Hình 2.6).

Hàm E được xây dựng trên cơ sở
hệ mật sử dụng các cấp số nhân
cyclic trên vành đa thức có hai lớp
kề (đã được mô tả trong mục 2.5.2).
Các khóa
i
K
là các phần tử trong
một cấp số nhân được chọn như sau
[5]:


61
0
mod 1; 1,16
i
i a
K K K x i  

-
16
-
20
0123456789ABCDEF0103456789ABCDEF
F4C77D14D1C3D56C3BFE5567E88F2FBD 63
21

32
0123456789ABCDEF0123456789ABCDFF
07564D6E503D8A9F901C46CFE655D09D 66
33
0123456789ABCDEF0123456789ABCDEE
0730E7E6141F31CA7E6B02567FBB85FB 66

Khoảng cách Hamming trung bình giữa các bản mã là:
33
( ) 1
2
1
( , ) 65,16
32
H tb H i
i
d d C C

 


Tiến hành tính toán độ khuếch tán của các từ mã khi thay đổi 1 bit
của khóa so với khóa ban đâu, ta được kết quả là:
16
( ) 1
2
1
( , ) 64,93
15
H tb H i
-
13
-
Sơ đồ này (hình 2.5) sẽ mã hóa cho chuỗi bit có độ dài 128, các
hoán vị IP và hoán vị đảo IP
-1
được tác giả xây dựng và phát triển từ
các bảng IP của hệ mật DES, cho trong bảng 2.8 và bảng 2.9.
Hàm
f
được xây dựng trên cơ sở hệ mật sử dụng các cấp số nhân
cyclic trên vành đa thức có hai lớp kề. Các khóa
i
K
là các phần tử
trong một cấp số nhân được chọn như sau:
61
mod 1; ( 1,16)
i
i a o
K K K x i  

với
a
K
là một đa thức có trọng số lẻ tùy ý sao cho:
deg 61
a

K x x    Phần tử đầu của cấp số
nhân và cũng là khóa đầu tiên là:
4 5
1 0
. 1 (045).
a
K K K x x    
Sơ đồ khối bộ mã hóa
f
với
khóa
1
K
như trong hình 2.6.
Một khâu mã hóa được thực hiện theo quy tắc:
 
1
1 1
,
i i i
i i i i
L R K
R L f R K

 
 



 


Bảng 2.10 là kết quả tính toán phân bố của bộ mã khi thay đổi 32
bản tin rõ [2], mỗi bản tin chỉ khác 1 bit, với cùng một bộ khóa K.
Với phần tử sinh của khóa
3 7 9
1
K x x x x
    
, phần tử đầu
2
1
a
K x x
  
; phần tử đầu của cấp số nhân (khóa đầu tiên) là:
4 5 7 8 10 11
1
. 1
a
K K K x x x x x x
       

Bản tin rõ đầu tiên gồm 32 ký tự dạng hexa là:
M
1
= 0123456789ABCDEF0123456789ABCDEF
Bảng 2.10. Khoảng cách Hamming
1
( , )
H i

0122456789ABCDEF0123456789ABCDEF
318B9AB229793B92F6D26B8F66F71FD4 66
6
0123656789ABCDEF0123456789ABCDEF
F15FF724D7A18806A95C1CF3FB2BC871 63
7
0123446789ABCDEF0123456789ABCDEF
F60072AA91BD7CEC5A629A89E22D0EEA 66
8
0123457789ABCDEF0123456789ABCDEF
E029AC24899C12893546C42D5F74C59D 66
9
0123456389ABCDEF0123456789ABCDEF
ABA4425CDC28CF0BDEB34969C3907BE5 66
10
01234567C9ABCDEF0123456789ABCDEF
DCFCE627E6484BB24B0ED91051661ECA 66
11
012345678DABCDEF0123456789ABCDEF
BA9A5D727F482D18C34AFBAB0488698E 66
12
0123456789BBCDEF0123456789ABCDEF
CF9528E0BF93184E0DD5E9EC4B0BED78 66
13
0123456789A9CDEF0123456789ABCDEF
D78E46904ACBF02ACC9A47D3A8634AE9 63
14
0123456789ABEDEF0123456789ABCDEF
EC3B44672A217541592F4BF0FAD021D9 63
15