HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

ĐINH MẠNH TOÀN NGHIÊN CỨU ỨNG DỤNG HỆ MẬT TRÊN CẤP SỐ NHÂN CYCLIC
TRONG HÀM BĂM
Chuyên ngành : Kỹ thuật Viễn thông
Mã số : 60.52.02.08

TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2013

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông

TS. Ngô Đức Thiện
1

MỞ ĐẦU
1. Lý do chọn đề tài:
Với sự bùng nổ của mạng internet hiện nay, mạng máy tính đang ngày càng đóng vai trò
thiết yếu trong mọi lĩnh vực hoạt động của toàn xã hội, đi đôi với lợi ích mà nó mang lại thì
một vấn đề hết sức quan trọng đó là yêu cầu bảo mật thông tin, xác thực nội dung thông tin
cũng như xác thực chủ thể nội dung.
Sự phát triển của ngành mật mã học gắn liền với quá trình hình thành của hai hệ mật chính
là hệ mật khóa bí mật và hệ mật mã công khai. Hệ mật khóa công khai với các ưu điểm như:
không phải sử dụng kênh an toàn để truyền khóa, số lượng khóa cần tạo và bảo mật phù hợp
cho số lượng người dùng, thuận tiện và phù hợp cho yêu cầu bảo mật thông tin và các dịch
vụ xác thực trên mạng với sự bùng nổ số lượng người dùng như hiện nay.
Việc giao dịch điện tử an toàn cũng như truyền thông tin trên mạng đòi hỏi cần có các dịch
vụ xác thực nội dung và chữ ký số. Trong các sơ đồ xác thực và chữ ký số thì hàm băm
đóng một vai trò quan trọng, nó là một hàm dùng để nén một chuỗi bit ở đầu vào tùy ý
thành một chuỗi bit có độ dài cố định ở đầu ra, chuỗi đầu ra được gọi mã băm, (hay kết quả
băm, giá trị băm, mã xác thực). Mã băm có thể xem như “đại diện” của tài liệu số hay “tóm
lược” thông báo và được sử dụng trong một số ứng dụng như: Xác thực tính toàn vẹn của dữ
liệu; xác thực số, chữ ký số, bảo vệ bản quyền tài liệu số, nhận dạng mật khẩu; nhận dạng
đối tượng
Các sơ đồ hàm băm thường được xây dựng trên mật mã khối theo một số sơ đồ cụ thể. Đặc
tính quan trọng nhất của hàm băm là tính khuếch tán và độ dài mã băm, cả hai đặc tính này
đều phụ thuộc vào mật mã khối được sử dụng trong lược đồ hàm băm. Do đó, nếu ta xây
dựng được một hệ mật đảm bảo tính khuếch tán tốt và tính dễ tính toán (không yêu cầu tính

Chương 3: Áp dụng hệ mật xây dựng trên cấp số nhân cyclic vào hàm băm
Nội dung chương này đề cập đến cấu trúc cơ bản của các hàm băm, một số ví dụ về hàm
băm và các phép tấn công hàm băm cơ bản. Phần tiếp theo là đề xuất xây dựng một hàm
băm MDC-2 mới 256 bit.
3

Được sự giúp đỡ tận tình của thầy TS. Ngô Đức Thiện và sự nổ lực của bản thân luận văn
đã được hòan thành. Tuy nhiên do thời gian hạn hẹp và trình độ hạn chế việc hiểu và trình
bày các vấn đề được nêu không thể tránh khỏi còn nhiều thiếu sót. Rất mong được sự góp ý
của các thầy và các bạn có quan tâm.
CHƯƠNG 1: TỔNG QUAN VỀ MẬT MÃ HỌC VÀ HÀM BĂM
1.1 Hệ mật khóa bí mật

Nguồn tin
Nguồn tin
Bộ mã hóa
Bộ mã hóa
Kênh mở
Kênh mở
Bộ giải mã
Bộ giải mã
Nhận tin
Nhận tin
Thám mã
Thám mã
Kênh an toàn
Kênh an toàn
Nguồn khóa
Nguồn khóa
Bản rõ

1
( , )
RB
M E K C


Nguồn tin
Nhận tin

Hình 1.2. Sơ đồ mật mã hóa công khai
1.2.2. Một số bài toán xây dựng hệ mật khóa công khai
4

Với yêu cầu với hệ mật khóa công khai: 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
1.2.2.1. Bài toán logarit rời rạc và hệ mật liên quan
1.2.2.2. Bài toán phân tích thừa số và hệ mật RSA
1.2.2.3. Bài toán xếp ba lô và hệ mật Merkle – Hellman
1.2.2.4. Bài toán mã sửa sai và hệ mật Mc. Eliece
1.2.2.5. Đường cong Elliptic và các hệ mật liên quan
1.3. Hàm băm và ứng dụng
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). 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 được phân ra thành 2 loại chính :
- Các hàm băm không khóa MDC.
- Các hàm băm có khóa MAC.
Hàm băm

1.3.1.3. Thuật toán mã xác thực thông báo (MAC).
1.3.2. Các phương pháp xây dựng hàm băm
1.3.2.1. Các hàm băm không có khoá
a) 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:
H
i-1
g
g
E
E
+
+
H
i
x
i
Matyas – Mayer - Oseas Davies - Mayer
E
E
x
i
E
E
+
+
H
i
H

1.3.2.2. Các hàm băm có khoá (MAC)
1.3.3. Ứng dụng của hàm băm
1.3.3.1. Tính toàn vẹn của dữ liệu và xác thực thông báo
Tính toàn vẹn của dữ liệu là tính chất đảm bảo dữ liệu không bị sửa đổi một cách bất hợp
pháp kể từ khi dữ liệu được tạo ra, được phát hoặc được lưu giữ bởi một nguồn xác định.
Các phương pháp cung cấp tính toàn vẹn của dữ liệu đó bằng cách dùng các hàm băm:
7

- Sử dụng MDC và kênh tin cậy
- Dùng MDC và mã hóa
- Chỉ dùng MAC
1.3.3.2. Chữ ký số
a) Định nghĩa chữ ký số
b) Các ưu điểm của chữ ký số
1.4. KẾT LUẬN CHƯƠNG 1
CHƯƠNG 2: HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN
CYCLIC
Chương này tập trung vào việc nghiên cứu phân tích cấu trúc nhóm nhân cyclic và cấp số
nhân trên vành đa thức, trên cơ sở đó xây dựng một hệ mật khóa bí mật làm cơ sở thực hiện
các hàm băm mới.
2.1. Nhóm nhân Cyclic trên vành đa thức
2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức
Định nghĩa 2.1: Nhóm nhân cyclic (CMG-Cyclic Multiplicate Group) trong vành đa thức là
tập hợp các phần tử đều bằng lũy thừa của một phần tử gọi là phần tử sinh. Trong vành đa
thức có nhiều nhóm nhân cyclic, số nhóm nhân bằng số các lũy đẳng có thể có trong vành.
23
{ , , , }
m
A     



2.1.2.2. Nhóm nhân cyclic với phần tử sinh
()ax

2.1.2.3. Đa thức đối xứng và các nhóm nhân cyclic đối xứng
2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC
2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức
Xét vành đa thức
2
[ ]/ 1
n
xx
với n lẻ, giả sử
()ax
là số hạng đầu tiên của cấp số
nhân cyclic và
()qx
là công bội của cấp số nhân.
Định nghĩa 2.6:Cấp số nhân cyclic (CGP - Cyclic Geometic Progressions) trên vành
đa thức là một tập hợp con có dạng sau:

21
( , )
{ ( ), ( ) ( ), ( ) ( ), , ( ) ( )}
m
aq
A a x a x q x a x q x a x q x




Hình 2.1. Mã hóa và giải mã xây dựng trên cấp số nhân cyclic
2.3.2. Xây dựng hệ mật dùng cấp số nhân cyclic
2.3.2.1. Mạng hoán vị - thay thế Feistel
2.3.2.2. Xây dựng hệ mật dùng cấp số nhân cyclic
Trong sơ đồ xây dựng hệ mật, sơ đồ Feistel được sử dụng làm nền cho hệ mật dùng các cấp
số nhân cyclic trên vành đa thức.
10

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

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 

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
21
và cũng là
một đa thức có trọng số lẻ. Cần chú ý rằng với
61n 
vành
61
2
/1[]Z x x 
là một vành có hai
lớp kề cyclic.

11

trong hình 2.6.

Hình 2.6 Sơ đồ khối mã hóa , với khóa
45
1
1K x x  

Một khâu mã hóa được thực hiện theo quy tắc:
12

 
1
11
,
i i i
i i i i
L R K
R L f R K










2.3.2.3. Tạo khóa cho hệ mật
Ta có thể sử dụng các CGP để tạo các khóa cho hệ mật, tuy nhiên để tạo số lượng khóa

và
1
0
0
()
n
i
i
e x x




là các đa thức bất khả quy.
Bổ đề 2.14
Vành đa thức theo modulo
1
n
x 
là một vành đa thức có hai lớp kề cyclic nếu n thoả
mãn:
 n phải là một số nguyên tố;
 phần tử thứ hai phải thoả điều kiện
( )/
2 1mod
np
n


với mỗi ước nguyên tố p của

deg ( ) 1b x m

c) M-dãy lồng ghép xây dựng từ các cấp số nhân cyclic trên vành đa thức có hai lớp kề
Bổ đề 2.15: M-dãy lồng ghép trên vành đa thức có hai lớp kề có thể được tạo từ
phương trình đồng dư sau:
( ) ( ) ( )mod ( ); 1,2, ,2 1
im
b x c x a x h x i  

Thực chất
()bx
là một CGP.
Trong đó:
1
( ) 2 1ord
n
ax



Số lượng các đa thức
()ax
là:
(2 1)
m
a
N






()cx
là đa thức mầm với
deg ( ) 1c x m
.
Số lượng các M-dãy lồng ghép tính theo công thức:
ah
N N N

Số lượng các M-dãy lồng ghép của một số vành tính được như trong bảng 2.5
Bảng 2.5 Số lượng M-dãy lồng ghép với một vài giá trị n khác nhau
n

(2 1)
m
a
N



2
2
n
h
N



ah

1,782.10
16

268.435.455
2.3.2.4. Đánh giá độ khuếch tán của hệ mật
Tiến hành tính toán độ khuếch tán khi thay đổi dữ liệu của hệ mật như trên với các
tham số sau:
Phần tử sinh của khóa:
15 30 45 59
0
( ) 1K x x x x x    

Phần tử đầu:
2
( ) 1
a
K x x x  

Đa thức lấy modulo:
60
0
()
i
i
h x x




Các khóa được tạo từ phương trình đồng dư sau:

Bản rõ
i
M

Bản mã
i
C

1
( , )
Hi
d C C

0
00112233445566778899AABBCCDDEEFF
C1CD0CE5889A8BB1639A7D9C8E342CD5
0
1
20112233445566778899AABBCCDDEEFF
94268991A180A02052383AC24DCFAE48
63
2
04112233445566778899AABBCCDDEEFF
65DC3F5436F70668AF463CE5975A5D2C
67
3
00912233445566778899AABBCCDDEEFF
5C98A3F3593EE31D255EF781F73BC3DF
63
4

00112233441566778899AABBCCDDEEFF
24A9B5206FD09A827871AB4413F8E1C1
67
12
00112233445466778899AABBCCDDEEFF
565CEAF217B3CF7D0F3526FFF8071B85
67
13
00112233445576778899AABBCCDDEEFF
80B4158BF96319F5AF5C8729B8531FA6
67
14
00112233445562778899AABBCCDDEEFF
91934A7ED4E42FA0502BC3F103EDE009
67
15
00112233445566578899AABBCCDDEEFF
691C9B15763AECE4881F09B5941FBDE4
63
16
001122334455667F8899AABBCCDDEEFF
EBB9E9D937B252E499FB60D608FE4899
63
17
0011223344556677C899AABBCCDDEEFF
F2BE0900EC234E56298B4E8765E2F448
67
18
00112233445566778C99AABBCCDDEEFF
F2FA5CBBCE01D7CFC78B4E2D3059A10C

00112233445566778899AABBC8DDEEFF
6E966F93BBADDBEF250121E22A251F64
67
27
00112233445566778899AABBCCFDEEFF
DC878A2FECD62360F46A833CE961C750
63
28
00112233445566778899AABBCCDFEEFF
10696449CE5E01AC1A959296F861928D
63
29
00112233445566778899AABBCCDDCEFF
A0D0466342FEC719B20D8D622E53793E
63
30
00112233445566778899AABBCCDDECFF
D71CA88D24DC4F3B7EE372738442796B
63
31
00112233445566778899AABBCCDDEE7F
2A4878CC92B11A80C1DD235F75B6B180
63
32
00112233445566778899AABBCCDDEEFE
D0FE170E5E42167DAE8EEA0D6823B3FC
67
(Chú ý: trong bảng 2.6, những ký tự hexa in đậm chứa bit thay đổi)
Khoảng cách Hamming trung bình giữa các bản mã là:
33




;
Ví dụ 2.7:
   
0
5 56 57 58 59 60
12 F.1 1000.0100 1111.1
1
Hex Bin
K
x x x x x x

       

Bảng 2.7 là kết quả tính toán phân bố của bộ mã khi thay đổi khóa K, mỗi khóa khác
với khóa đầu tiên 2 bit, với cùng một bản rõ [2]:
Bảng 2.7 Khoảng cách Hamming
1
( , )
Hi
d C C
giữa các cặp bản mã khi các khóa khác khóa
1
K
2
bit
 
1

423456789ABCDEF1
B25EF4355618A32DF68218698388C07E
66
33
2
173456789ABCDEF1
956624ACFB8C1D2BB5F253B7BF2C768E
68
35
3
126456789ABCDEF1
C818DED35C9B8B4A5B5DBA1697C703E6
60
33
4
123156789ABCDEF1
D15BC0521DF97629CDA9CFD095FC8429
64
33
5
1234C6789ABCDEF1
DA311FCD09B6CE36A1A305A6878FD5BE
78
33
6
12345C789ABCDEF1
B642596F432140C01E9025F6844E9A16
68
33
7

123456789ABC7EF1
A688E42CC74777E5E40A195302CE18CF
57
33
14
123456789ABCDBF1
E9E58EC43FDACE98F3C3BA6A029525A9
62
33
15
123456789ABCDEA1
27E8EAE2859B880B277345112B8B7104
60
31
(Chú ý: trong bảng 2.7, các ký tự hexa in đậm chứa các bit của khóa đã thay đổi, trọng
số các đa thức sinh tạo khóa luôn đảm bảo là lẻ)
Khoảng cách Hamming trung bình giữa các bản mã:
15
( ) 1
1
1
( , ) 63,93
15
H tb H i
i
d d C C





 Mỗi khối thông điệp con m
1
,m
2
,…,m
k
sẽ lần lượt đi qua một hàm nén của hàm
băm h(m).
 Kết quả của khối thứ m
i-1
sau khi đi qua hàm nén sẽ là nguồn dữ liệu đầu vào
cho bước thứ i tiếp theo.

18

Giả sử nếu gọi IV (initial value) là giá trị khởi tạo
ban đầu thì quá trình lặp và xử lý các khối con
được mô tả như sau:
0
1
( , ); 1, , .
( ) ( )
i I i
k
H IV
H f H m i k
h m g H




3.4.3. Tấn công bằng các kết quả tính toán được
3.4.5. Tấn công đa mục tiêu
3.4.6. Tấn công bằng các thông báo dài
3.5. XÂY DỰNG HÀM BĂM MỚI TRÊN CÁC CẤP SỐ NHÂN CYCLIC
19

Trong mục này sẽ đề cập đến việc áp dụng hệ mật trình bày ở chương 2 để xây dựng
một hàm băm MDC-2 có độ dài mã băm là 256 bit. Sơ đồ hàm băm như trong hình 3.3, sau
bước băm cuối cùng thì mã băm đầu ra được ghép từ đầu ra 1 (out 1
i
H
) và đầu ra 2 (Out 2
i
H

) [4], [6], [7], [8].
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 chương 2). Các khóa
i
K
vẫn là các phần tử trong
một cấp số nhân trên vành đa thức có hai lớp kề cyclic
61
1x 
được chọn như sau:
với
a
K

còn bit thứ 61 là bit kiểm tra chẵn lẻ. Việc
trích chọn được lấy liên tục các bit cách nhau 2 vị trí trong
1i
H

và
1i
H


(trong khoảng bit 1
đến bit 120).

Hình 3.3. Sơ đồ thực hiện hàm băm

 
61
0
mod 1; 1,16
i
ia
K K K x i  

20

Dưới đây là một vài kết quả đánh giá của hàm băm xây dựng trên các cấp số nhân
cyclic.
Bảng 3.2 là kết quả tính toán khoảng cách Hamming của một số mã băm của các bản
tin rõ khi thay đổi duy nhất một bit dữ liệu 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 khối bản tin đầu tiên của bản rõ [7].





Bản tin đầu tiên được xây dựng như sau: Khối đầu tiên gồm 64 ký tự dạng hexa
(tương ứng 256 bit) được chọn là:
M
1
=
0123456789ABCDEF0123456789ABCDEF
0123456789ABCDEF0123456789ABCDEF
Các khối tiếp theo (từ 2 đến 10) được tạo một cách ngẫu nhiên.
Bảng 3.2 Khoảng cách Hamming d
H
(MD
1
, MD
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
d
H
(MD
1
,MD
i
)
0

0123456789ABCDEF0123456789ABCDCF
0123456789ABCDEF0123456789ABCDEF
ED088B0CFB75953D73EED891C5B52ACE
45A9C21F1607B5FC8C91FEA0E09F01ED
122
32
0123456789ABCDEF0123456789ABCDEE
0123456789ABCDEF0123456789ABCDEF
DEF1D35924863B9FB60C9F985D9ABA36
3D67062B7AA0B26E2CF845734BA82A4B
140
33
0123456789ABCDEF0123456789ABCDEF
2123456789ABCDEF0123456789ABCDEF
574316CDBAB234C20EA3568BE172BAA4
2A3F41374210AFCE70AEEDCB9994EE7E
136
34
0123456789ABCDEF0123456789ABCDEF
0023456789ABCDEF0123456789ABCDEF
8EB4D6AF5AB1E575D21DA802368FA89E
5DFD6A501F98CD256AFB1830C34FB79C
134
…
…
…
…
62
0123456789ABCDEF0123456789ABCDEF
0123456789ABCDEF0123456789ABCFEF

i
d d MD MD




0 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 256 bit được tạo ngẫu nhiên [7].
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
0
K
như sau:
0( )
123456789ABCDEF.1
Hex
K 
(

Chú ý: vị trí các bit “1” trong các khóa
0i
K
tương ứng là số mũ của
x
trong đa thức
sinh tạo khóa. Ví dụ:
   
0
5 56 57 58 59 60
12 F.1 1000.0100 1111.1
1
Hex Bin
K
x x x x x x

       

Bảng 3.3 Khoảng cách Hamming d
H
(MD
1
, MD
i
) giữa các cặp giá trị băm khi các khóa khác khóa K
1
2 bit.
TT
Khóa K
i

35
3
129456789ABCDEF1
71FB25099EA653865989F97902643D9B
0E03EFF0E16B8CA156A4919A3A528E74
133
33
4
123156789ABCDEF1
7BD398826699C84A63089539C013B7E1
D077258721BBC05CE02709A9FE01A9BA
123
33
5
1234F6789ABCDEF1
52885E7E8BB73C1DFDBBAB44BCAF9BC1
449C73A8D24C376041E28BA78B794E41
138
35
6
123453789ABCDEF1
BE7525A3BE96823C52473D868D96441C
30CCE0D89908FA9FD21CFB594AEDAAD1
130
33
7
123456D89ABCDEF1
66D3CF874C1A5C6D02A6B4763E8F7596
C2E8E29DEA340CA31A907DC3093BD60A
119

33
13
123456789ABC8EF1
76AEBF7739066421A97CB110E8F843AD
F5C247A186793CF1BD747D0DA1B4825A
123
31
14
123456789ABCDBF1
F61035831137662A2005B0E570C3FBDF
5006C8621B46C945692993250C4CE272
122
33
15
123456789ABCDEA1
E0599B76112AF746ACCD9517CD579C6B
A492E4CB44F71F65394F27B404AD0C19
132
31
23

Khoảng cách Hamming trung bình của các giá trị băm với giá trị băm ban đầu:

15
( ) 1
1
1
( , ) 130,67
15
H tb H i

KẾT LUẬN
Các kết quả đạt được của luận văn:
 Nghiên cứu cơ bản về các hệ mật khóa bí mật, hệ mật khóa công khai và các hàm
băm sử dụng cho việc xác thực và đảm bảo tính toàn vẹn dữ liệu.
 Nghiên cứu cấu trúc nhóm nhân cylic, cấp số nhân cyclic trên vành đa thức.
 Nghiên cứu cách xây dựng hệ mật mã khối khóa bí mật xây dựng từ cấp số nhân
cyclic trên vành đa thức
1
n
x 
với
2
k
n 
.
 Nghiên cứu cách tạo khóa cho hệ mật khóa bí mật bằng các cấp số nhân cyclic trên
vành có hai lớp kề cyclic.
 Đề xuất một hàm băm mới MDC-2 theo với hệ mật xây dựng theo cấp số nhân
cyclic.