i

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của tôi, các số liệu và
kết quả trình bày trong luận án là trung thực và chưa được công bố ở bất kỳ
công trình nào khác.
Tác giả

Hồ Quang Bửu
ii LỜI CẢM ƠN

Luận án Tiến sĩ kỹ thuật này được thực hiện tại Học viện Công nghệ Bưu
chính Viễn thông. Tác giả xin tỏ lòng biết ơn đến thầy giáo GS.TSKH. Nguyễn
Xuân Quỳnh đã trực tiếp định hướng, tạo mọi điều kiện trong suốt quá trình
nghiên cứu. Tác giả cũng xin cảm ơn GS.TS. Nguyễn Bình đã trực tiếp hướng dẫn
học thuật hóa, kiểm tra những kết quả của các công trình nghiên cứu.
Tôi xin chân thành cảm ơn Lãnh đạo Học viện Công nghệ Bưu chính Viễn
thông đã tạo những điều kiện thuận lợi để hoàn thành và bảo vệ luận án trong thời
gian nghiên cứu của nghiên cứu sinh. Tôi xin cảm ơn khoa Quốc tế và Đào tạo sau
đại học, Sở Thông tin truyền thông tỉnh Quảng Nam (nơi tôi đang công tác), cũng
như các đồng nghiệp đã tạo điều kiện và giúp đỡ tôi hoàn thành được đề tài nghiên
cứu của mình.
Cuối cùng là sự biết ơn tới gia đình, bạn bè đã thông cảm, động viên giúp đỡ
cho tôi có đủ nghị lực để hoàn thành luận án.


1.3. HỆ MẬT KHÓA CÔNG KHAI 30
1.3.1. Sơ đồ chức năng 30
1.3.2. Một số bài toán xây dựng hệ mật khóa công khai 31
1.4. CƠ BẢN VỀ HÀM BĂM 33
1.4.1. Mở đầu 33
1.4.2. Các định nghĩa và tính chất cơ bản 35
1.4.3. Một số phương pháp xây dựng hàm băm 37
1.4.4. Các loại tấn công hàm băm cơ bản 41
1.4.5. Độ an toàn mục tiêu 43
1.5. TÍNH TOÀN VẸN CỦA DỮ LIỆU VÀ XÁC THỰC THÔNG BÁO 44
1.5.1. Các phương pháp kiểm tra tính toàn vẹn dữ liệu 44
1.5.2. Chữ ký số 46
1.6. KẾT LUẬN CHƯƠNG 1 49
CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC 50
2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC 50
2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức 50
2.1.2. Các loại nhóm nhân cyclic trên vành đa thức 52
2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC 54
2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức 54
2.2.2. Phân hoạch vành đa thức 55
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 61
2.3.1. Vành đa thức có hai lớp kề 61
2.3.2. M-dãy xây dựng trên vành đa thức 63
2.3.3. Xây dựng M-dãy lồng ghép từ các cấp số nhân cyclic trên vành
đa thức có hai lớp kề 64
v

2.4. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC 71

CFB
Cipher Feedback Block
CGP
Cấp số nhân cyclic (Cyclic Geometic Progressions)
CMG
Nhóm nhân cyclic (Cyclic Multiplicate Group)
CRC
Cyclic Redundancy Check
CRF
Collision Resistant Function
CRHF
Collision Resistant Hash Function
S
C

Chu trình
0
d

Khoảng cách Hamming
deg
Bậc của đa thức (Degree)
DEA
Data Encryption Algorithm
DES
Chuẩn mã dữ liệu (Data Encryption Standard)
()ex

Đa thức lũy đẳng
ECB

NIST
National Institute for Standards and Technology (US)
OFB
Output Feedback
ord
Cấp của đa thức (Order)
OWF
One-Way Function
OWHF
One-Way Hash Function
R
Vành (Ring)
RIPE
Race Integrity Primitives Evaluation
RSA
Rivest Shamir Adleman
SHA
Secure Hash Algorithm
TDEA
Triple Data Encryption Algorithm
UOWHF
Universal One-Way Hash Function
VEST
Very Efficient Substitution Transposition
W

Trọng số (Weight)
2
[ ]/ 1
n

63
Bảng 2.4. Các tam thức cấp cực đại 4095 (3
2
.5.7.13) trên vành x
13
+ 1 68
Bảng 2.5. Một số phần tử của M-dãy trên vành x
13
+1 69
Bảng 2.6. M-dãy với chiều dài 4095 theo phân hoạch cực đại 69
Bảng 2.7. Số lượng M-dãy lồng ghép với một vài giá trị n khác nhau 70
Bảng 2.8. Bảng hoán vị ban đầu (IP) 78
Bảng 2.9. Bảng hoán vị đảo (IP
-1
) 78
Bảng 2.10. Khoảng cách Hamming d
H
(C
1
,C
i
) giữa các cặp bản mã khi các bản rõ
khác nhau 1 bit, d
H
(M
1
,M
i
) = 1, với cùng một khóa K 80
Bảng 2.11. Khoảng cách Hamming d

i
) giữa các cặp giá trị băm khi các
khóa khác khóa K
1
2 bit. 99
Bảng 3.5. Tính khoảng cách Hamming trung bình khi thay đổi khóa K và thay đổi
bản tin rõ. 100

ix

DANH MỤC CÁC HÌNH VẼ
Hình 1.1. Sơ đồ khối chức năng hệ mật khóa bí mật 8
Hình 1.2. M-dãy tạo từ thanh ghi dịch phản hồi tuyến tính LFSR 22
Hình 1.3. Mạch tạo M-dãy từ đa thức g(x) = 1+x+x
4
23
Hình 1.4. Bộ tạo dãy Gold đối với g
1
(d) = d
3
+ d +1 và g
2
(d) = d
3
+ d
2
+1 24
Hình 1.5. Sơ đồ mã hóa DES 27
Hình 1.6. Mô tả hàm f trong DES 28
Hình 1.7. Các bước tạo khóa cho các vòng mã hóa của DES 29

PHẦN MỞ ĐẦU
1. MỞ ĐẦU
Trong sự phát triển của xã hội loài người, kể từ khi có sự trao đổi thông tin,
thì an toàn thông tin trở thành một nhu cầu gắn liền với nó. Từ thủa sơ khai, an
toàn thông tin được hiểu đơn giản là giữ bí mật và điều này được xem như một
nghệ thuật chứ không phải là một ngành khoa học. Với sự phát triển của khoa học
kỹ thuật và công nghệ, cùng với các nhu cầu đặc biệt có liên quan tới an toàn thông
tin, ngày nay cần có các yêu cầu kỹ thuật đặc biệt trong việc đảm bảo an toàn
thông tin, các kỹ thuật đó bao gồm: Kỹ thuật mật mã (Cryptography); kỹ thuật
ngụy trang (Steganography); kỹ thuật tạo bóng mờ (Watermarking – hay thủy
vân).
Hiện nay việc trao đổi thông tin thương mại trên Internet có nhiều nguy cơ
không an toàn do thông tin có thể bị lộ hay bị sửa đổi. Nói chung, để bảo vệ các
thông tin khỏi sự truy cập trái phép cần phải kiểm soát được những vấn đề như:
thông tin được tạo ra, lưu trữ và truy nhập như thế nào, ở đâu, bởi ai và vào thời
điểm nào.
Để giải quyết các vấn đề trên, kỹ thuật mật mã hiện đại phải đảm bảo các dịch vụ
an toàn cơ bản: (1) bí mật (Confidential); (2) xác thực (Authentication); (3) đảm bảo tính
toàn vẹn (Integrity), và để thực hiện các nhiệm vụ này người ta sử dụng hàm băm mật mã
(Cryptographic Hash Function).
2. 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. Thông thường các hàm băm đều xây dựng 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).
2

thuật toán mã hóa, các các phép toán trong hàm mã hóa và tăng chiều dài mã
băm… Một số hàm băm cho trong bảng 1 dưới đây.
Bảng 1: Một số hàm băm
3
TT
Thuật toán
Kích thước đầu ra (bit)
Xung đột
1
HAVAL
256/224/192/160/128
Có
2
MD2
128
Khả năng lớn
3
MD4
128
Có
4
MD5
128
Có
5
PANAMA
256

Tiger 192/160/128
192/160/128
Không
14
VEST-4/8
160/256
Không
15
VEST-16/32
320/256
Không
16
WHIRLPOOL
512
Không

SHA-1, MD5, và RIPEMD-160 nằm trong số các thuật toán băm được dùng
rộng rãi nhất của năm 2005. Tháng 8 năm 2004, các nhà nghiên cứu đã tìm được
các điểm yếu của một loạt hàm băm, trong đó có MD5, SHA-0 và RIPEMD.
Tháng 2 năm 2005, người ta ghi nhận một tấn công đối với SHA-1. Tháng 8 năm
2005 người ta lại ghi nhận một tấn công khác đối với SHA-1.
Các hàm băm SHA-1, MD5, RIPEMD đều thuộc họ MD4. Cấu trúc và thuật
toán mã hóa của họ MD4 khá phức tạp (được trình bày trong chương 3 của luận
án) và trải qua nhiều bước như: mở rộng thông báo đầu vào (theo kiểu hoán vị
4
vòng hoặc đệ quy), các bước mã hóa sử dụng các phép toán Boolean, phép cộng số
tự nhiên theo modulo, phép dịch và quay bit, tổ hợp mã băm đầu ra với vector khởi

5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU
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ật 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ố chặt chẽ được xây dựng trên cơ sở là
nhóm nhân cyclic trên vành đa thức.
6. 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ật mã, 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á.
7. Ý NGHĨA KHOA HỌC VÀ THỰC TIÊN CỦA ĐỀ TÀI
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. 6
CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ HỌC
1.1. CÁC KHÁI NIỆM CƠ BẢN
Mật mã học là một bộ phận của khoa học mật mã (Cryptology), được chia
thành 2 bộ phận chính [4]:
+ Mật mã học (Cryptography): chia thành 3 nội dung:
 Mật mã khóa bí mật (Khóa đối xứng)
 Mật mã khóa công khai (khóa bất đối xứng)
 Hàm băm, xác thực và chữ ký số

Ta có:
 
K
C E M
hay
 
,C E M KEncryption
M
C
K
7
Với hệ mật này, việc mã hóa và giải mã sử dụng chung một khóa, do đó hai
bên liên lạc phải thống nhất và bảo mật khóa trước khi truyền tin. Các thuật toán
mã hóa trong hệ mật khóa bí mật thường sử dụng các phương pháp sau:
 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).
+ Mật mã khóa công khai (khóa không đối xứng):
Thông thường mỗi bên liên lạc tự tạo cho mình một cặp khóa Công khai và bí
mật, khóa công khai dùng để mã hóa bản tin và khóa này được công khai trên
mạng, còn khóa bí mật dùng để giải mã (chỉ có bên nhận tin lưu trữ). Các thuật
toán mã hóa công khai cho đến nay được xây dựng theo một trong năm bài toán
một chiều cơ bản đó là:

a) P là một tập hữu hạn các bản rõ có thể.
b) C là một tập hữu hạn các bản mã có thể.
c) K là một tập hữu hạn các khoá có thể (không gian khoá).
d) Đối với mỗi
Kk
có một quy tắc mã
Ee
k


CPe
k
:

và một quy tắc giải mã tương ứng
Dd
k


PCd
k
:

sao cho:
  
xxed
kk

với
Px

Thám mã
Nguồn khoá
K
Nguồn tin
Bộ mã hoá
Kênh mở
(không an toàn)
Bộ giải mã
Nhận tin
9
Ví dụ 1.1:
Với văn bản tiếng Anh,
26n 
hoặc 27, như vậy
26
,,M C K Z
hoặc
27
Z

Ta sử dụng MDV (với modulo 26) để mã hoá một văn bản tiếng Anh thông
thường bằng cách thiết lập sự tương ứng giữa các ký tự và các thặng dư theo mod
26 như sau:

Ký tự
A
B

R
S
T
U
V
W
X
Y
Z
Mã tương ứng
13
14
15
16
17
18
19
20
21
22
23
24
25
Nhận xét:
- Khi
3k
, hệ mật này thường được gọi là mã Caesar đã từng được Hoàng đế
Caesar sử dụng.
- MDV (theo mod 26) là không an toàn vì nó có thể bị thám theo phương pháp
tìm khoá vét cạn (thám mã có thể dễ dàng thử mọi khoá


thì
 
,1an 

10
Nhận xét: Do khoảng trống xuất hiện nhiều trong văn bản, nên khi mã hóa
nên mã hóa cả khoảng trống để giảm số lần xuất hiện.
d) Mật mã cũi lợn
Sử dụng các hình tượng khác nhau không nằm trong bảng ký tự thay thế cho
các ký tự.
1.2.2.2. Các hệ mật trên là hệ mật thay thế đa biểu
Hệ mậtVigenère
Sử dụng phép tương ứng
25Z1B0A  ,,, 
mô tả ở trên, ta có thể
gắn cho mỗi khoá
K
một chuỗi ký tự có độ dài m, được gọi là từ khoá. Mật mã
Vigenère sẽ mã hoá đồng thời m ký tự: mỗi phần tử của bản rõ tương đương với m
ký tự.
Ví dụ 1.2:
Giả sử bản tin m = 6 và từ khoá là k = CIPHER. Từ khoá này tương ứng với
dãy số k = (2, 8, 15, 7, 4, 17). Giả sử bản rõ là:
meet me at sunset
Ta sẽ biến đổi các phần tử của bản rõ thành các thặng dư theo mod 26, viết
chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau:

Khoá
14
12
19
0
16
21
2
1
7
1
17
9
6
1
Bản mã

Như vậy, dãy ký tự tương ứng với xâu bản mã sẽ là:
OMTA QV CB HBRJGB
Ta có thể mô tả mật mã Vigenère như sau:
Cho m là một số nguyên dương cố định nào đó.
Ta định nghĩa
 
26
n
P C K Z  

Với khoá
 
12

m
26
. Bởi vậy, thậm chí với m khá nhỏ, phương pháp tìm kiến vét cạn cũng yêu
cầu thời gian khá lớn. Ví dụ, với m = 6 thì không gian khoá cũng có kích thước lớn
hơn
8
103.
khoá.
1.2.3. Các hệ mật hoán vị (MHV)
Khác với MTT, ý tưởng của MHV là giữ các ký tự 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ã.
* Hệ mật hoán vị độ dài K
Chia bản rõ thành khác khối độ dài
K
và hoán vị các ký tự trong mỗi khối
Ví dụ 1.3:
Giả sử m = 6 và khoá là phép hoán vị sau:

1
2
3
4
5
6
3
5
1
6
4

Khi sử dụng phép hoán vị ngược
1
π

trên dãy bản mã (sau khi đã nhóm lại
theo các nhóm 6 ký tự), ta sẽ nhận lại được bản rõ ban đầu.
Từ ví dụ trên, ta có thể định nghĩa MHV như sau:
Định nghĩa 1.1 [[4]: Cho m là một số nguyên dương xác định nào đó.
Cho
 
26
m
P C Z
và cho K là tất cả các hoán vị có thể có của
 
1, 2, , m
.
Đối với một khoá

(tức là một phép hoán vị nào đó), ta xác định:

 
   
 
1
1
, , , ,
m
m
e x x x x

trọng to lớn trong việc thiết kế các hệ mật hiện nay.
Để đơn giản, trong phần này chỉ hạn chế xét các hệ mật trong đó C=P; các hệ
mật loại này được gọi là tự đồng cấu. Giả sử
 
1111
D,E,K,P,PS 
và
 
2222
D,E,K,P,PS 
là hai hệ mật tự đồng cấu có cùng các không gian bản mã
và rõ. Khi đó, tích của
1
S
và
2
S
(kí hiệu là
21
SS 
) được xác định là hệ mật sau:

12
( , , , , )P P K K E D
(1.1)
Khoá của hệ mật tích có dạng
 
21
k,kk 
trong đó

1
k
e
rồi lại mã hóa bằng
2
k
e
. Quá trình
giải mã tương tự nhưng thực hiện theo thứ tự ngược lại:
13
1 2 1 2 1 2 2 1
1 2 2 1
11
( , ) ( , ) ( , )
( ( )) ( ( ( )))
( ( ( ( ))))
( ( ))
k k k k k k k k
k k k k
kk
d e x d e e x
d d e e x
d e x
x




Sau đây là một ví dụ đơn giản để minh hoạ khái niệm hệ mật tích
Giả sử
26
P C Z
;
 
 
26
, : , 26 1k a Z UCLN a

Với
aK
, ta xác định:
 
mod 26
a
e x ax

và
 
1
mod 26
a
d y a y



 
26
,x y Z

. Bởi vậy, một khoá trong mã tích
SM
có dạng
 
k,a
, trong
đó:

( , )
( ) mod26
ak
e x ax k
(1.5)
Đây chính là định nghĩa về khoá trong hệ mã Affine. Hơn nữa, xác suất của
một khoá trong hệ mã Affine là:
   
2611213121 
. Đó là tích của xác suất
tương ứng của các khoá a và k. Bởi vậy
SM
là hệ mã Affine.
14
Bây giờ ta sẽ xét
MS
. Một khoá này trong hệ mã này có dạng
( , )ka
, trong

 
126,aUCLN 
, bởi vậy a có phần tử nghịch
đảo). Nói cách khác, khoá
 
1
k,a
của hệ mã Affine tương đương với khoá
1
1
( , )a k a

của mã tích
MS
. Bởi vậy, ta có một song ánh giữa hai không gian
khoá. Vì mỗi khoá là đồng xác suất nên có thể thấy rằng
MS
thực sự là mã
Affine.
Ta chứng minh rằng
MSSM 
. Bởi vậy, hai hệ mật là giao hoán. Tuy
nhiên, không phải mọi cặp hệ mật đều giao hoán; có thể tìm ta được các cặp phản
ví dụ. Mặt khác ta thấy rằng phép tích luôn kết hợp:
   
321321
SSSSSS 

Nếu lấy tích của một hệ mật tự đồng cấu với chính nó thì ta thu được hệ mật
SS

1
S
và
2
S
là luỹ đẳng và giao
hoán thì
1
S
và
2
S
cũng là luỹ đẳng. Điều này rút ra từ các phép toán đại số sau:
15
     
 
   
21
2211
2211
21212121
SS
SSSS
SSSS
SSSSSSSS



( ) ( )
kk
y y y e x e x  
(1.7)
Các hệ mật thuộc dạng này thường được gọi là các mã khối. Một quan điểm
sử dụng khác là mật mã dòng. Ý tưởng cơ bản ở đây là tạo ra một dòng khoá
12
z z z
và dùng nó để mã hoá một xâu bản rõ
12
x x x
theo quy tắc:
12
1 2 1 2
( ) ( )
zz
y y y e x e x  

Mã dòng hoạt động như sau. Giả sử
kK
là khoá, và
12
x x x
là xâu bản
rõ. Hàm
i
f
được dùng để tạo
i
z

xx
ta phải tính liên tiếp
1 1 2 2
, , , z y z y

Việc giải mã xâu bản mã
12
yy
có thể được thực hiện bằng cách tính liên
tiếp
1 1 2 2
, , , z x z x

Sau đây là định nghĩa dưới dạng toán học:
Định nghĩa 1.2 [4].
16
Mật mã dòng là một bộ
( , , , , , , )P C K L F E D
thoả mãn các điều kiện sau:
1) P là một tập hữu hạn các bản rõ có thể.
2) C là tập hữu hạn các bản mã có thể.
3) K là tập hữu hạn các khoá có thể (không gian khoá)
4) L là tập hữu hạn các bộ chữ của dòng khoá.
5)
12
( )F f f
là bộ tạo dòng khoá. Với

d e x x

với mọi bản rõ
xP
.
Ta có thể coi mã khối là một trường hợp đặc biệt của mã dòng, trong đó dùng
khoá không đổi:
i
Zk
với mọi
1i 
.
Mã dòng được gọi là đồng bộ nếu dòng khoá không phụ thuộc vào xâu bản
rõ, tức là nếu dòng khoá được tạo ra chỉ là hàm của khoá k. Khi đó, ta coi k là một
"mầm" để mở rộng thành dòng khoá
12
zz

Một hệ mã dòng được gọi là tuần hoàn với chu kỳ d nếu
i d i
zz


với mọi số
nguyên
1i 
. Mã Vigenère với độ dài từ khoá m có thể coi là mã dòng tuần hoàn
với chu kỳ m. Trong trường hợp này, khoá là
1
( , , )


Nếu ta coi "0" biểu thị giá trị "sai" và "1" biểu thị giá trị "đúng" trong đại số
Boolean thì phép cộng theo modulo 2 sẽ ứng với phép hoặc có loại trừ. Bởi vậy,
phép mã (và giải mã) dễ dàng thực hiện bằng mạch cứng.
Ta xem xét một phương pháp tạo một dòng khoá (đồng bộ) khác. Giả sử bắt
đầu với
1
( , , )
m
kk
và
,1
ii
z k i m  
(cũng giống như trước đây), tuy nhiên bây
giờ ta tạo dòng khoá theo một quan hệ đệ quy tuyến tính cấp m: