Nghiên cứu về hàm băm trên cơ sở mạng hoán vị thay thế điều khiển được và ứng dụng trong mã hóa xác thực văn bản

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG

–––––––––––––––––

ĐỖ THU HOÀI

NGHIÊN CỨU VỀ HÀM BĂM TRÊN CƠ SỞ MẠNG

HOÁN VỊ THAY THẾ ĐIỀU KHIỂN ĐƯỢC VÀ ỨNG

DỤNG TRONG MÃ HÕA XÁC THỰC VĂN BẢN

Chuyên ngành: Khoa học máy tính

Mã số : 62.48.01

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

Thái Nguyên, năm 2013

1

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

LỜI CAM ĐOAN

Em xin cam đoan toàn bộ luận văn: “Nghiên cứu về hàm băm trên cơ sở

mạng hoán vị thay thế điều khiển đƣợc và ứng dụng trong mã hóa xác thực văn

bản” là do bản thân tìm hiểu, nghiên cứu. Không có sự sao chép nội dung từ các

luận văn khác. Tất cả nội dung hoặc hình ảnh minh họa đều có nguồn gốc xuất xứ

rõ ràng từ các tài liệu tham khảo ở nhiều nguồn khác nhau mà xây dựng nên. Ngoài

ra còn có sự góp ý và định hƣớng của thầy giáo TS Vũ Đức Thái.

Em xin cam đoan những lời trên là đúng, mọi thông tin sai lệch em xin hoàn

toàn chịu trách nhiệm trƣớc Hội đồng.

2

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

MỤC LỤC

LỜI CAM ĐOAN ...............................................................................................................................1

MỤC LỤC...........................................................................................................................................2

DANH MỤC CÁC CHỮ VIẾT TẮT .................................................................................................4

DANH MỤC HÌNH ẢNH ..................................................................................................................5

DANH MỤC BẢNG BIỂU ................................................................................................................7

CHƢƠNG 1 TỔNG QUAN VỀ HÀM BĂM...................................................................................10

1.1 Giới thiệu về hàm băm......................................................................................................10

1.1.1 Định nghĩa về hàm băm ............................................................................................10

1.1.2 Lịch sử phát triển của hàm băm ................................................................................11

1.1.3 Thuộc tính an toàn của hàm băm ..............................................................................13

1.1.4 Các quan niệm an toàn ..............................................................................................15

1.2 Ứng dụng của hàm băm ....................................................................................................16

1.3 Xu hƣớng thiết kế..............................................................................................................17

1.3.1 Hàm băm không khóa và có khóa .............................................................................17

1.3.2 Hàm băm lặp .............................................................................................................18

1.3.3 Hàm băm dựa trên hình cây ......................................................................................28

1.3.4 Hàm nén ....................................................................................................................29

CHƢƠNG 2 KIẾN TRÚC MẠNG CHUYỂN VỊ THAY THẾ ĐIỀU KHIỂN ĐƢỢC...................30

2.1 Các phần tử mã hóa cơ bản điều khiển đƣợc dựa trên mạng chuyển vị thay thế ..............30

2.1.1 Phần tử điều khiển cơ bản .........................................................................................30

2.1.2 Phân loại các phần tử cơ bản.....................................................................................32

2.1.3 Nhóm phụ của các phần tử U2/1 với một đầu ra tuyến tính........................................37

2.2 Tô pô đối xứng..................................................................................................................41

CHƢƠNG 3 XÂY DỰNG VÀ CÀI ĐẶT CHƢƠNG TRÌNH MÔ PHỎNG...................................51

3.1 Bài toán ứng dụng .............................................................................................................51

3.2 Thiết kế CSDL, thuật toán và giao diện chƣơng trình hàm băm.......................................51

3.2.1 Thiết kế cơ sở dữ liệu .......................................................................................................51

3.2.2 Thuật toán thực hiện.........................................................................................................53

3.2.3 Phân tích các modul chƣơng trình chính ..........................................................................54

3.2.4 Giao diện chƣơng trình ....................................................................................................58

3

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

3.3 Cài đặt chƣơng trình..........................................................................................................58

3.4 Tích hợp Add-In vào cho phần mềm Microsoftword 2007...............................................59

3.5 Thử nghiệm và đánh giá kết quả .......................................................................................60

3.5.1 Một số kết quả thử nghiệm của chƣơng trình...................................................................60

3.5.2 Đánh giá kết quả ..............................................................................................................61

3.6 Nghiên cứu sử dụng công nghệ FPGA để cấu hình các phần tử điều khiển đƣợc. ..........62

3.7 Kết luận .............................................................................................................................69

KẾT LUẬN.......................................................................................................................................71

TÀI LIỆU THAM KHẢO.................................................................................................................72

PHỤ LỤC..........................................................................................................................................74

4

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

DANH MỤC CÁC CHỮ VIẾT TẮT

Từ viết tắt Nghĩa tiếng Anh Nghĩa tiếng Việt

AES Advanced Encryption Standard Tiêu chuẩn mã hóa tiên tiến

CE Controlled Element Phần tử điều khiển đƣợc

CSPN Controlled Substitution

Permutation Network

Mạng Hoán vị-Thay thế điều khiển

đƣợc

DES Data Encrypt Standar Chuẩn mã hóa dữ liệu

DDP Data Dependent Permutation (data￾driven permutation)

Hoán vị phụ thuộc vào dữ liệu

FPGA Field Programmable Gate Array Thiết bị lập trình có khá năng tái

cấu hình.

HMAC Hashed Message Authentication

Code

Xác thực thông điệp bằng hàm băm

NIST National Institute of Standards and

Technology

Viện Tiêu chuẩn và Công nghệ

Quốc gia của Mỹ

NMAC Non-Message Authentication Code Không mã xác thực thông điệp

MAC Message Authentication Code Mã xác thực thông điệp

MD5 Message-Digest algorithm 5 Giải thuật tóm tắt thông điệp

MDP Message-Digest Permutation Hoán vị tóm tắt thông điệp

NL Non Linearity Phi tuyến

PKC Public Key Cryptographic Mật mã khóa công khai

RIPEMD Race Integrity Primitives

Evaluation Message Digest

Phân loại đánh giá tính toàn vẹn

nguyên thủy của thông điệp

RO Reverse Osmosis Thẩm thấu ngƣợc

SHA Secure Hash Algorithm Thuật giải băm an toàn

SPN Substitution Permutation Network Mạng hoán vị thay thế

TT Truth Table Bảng giá trị chân lý của các phép

toán logic

UOWHFs Universal One -Way Hash

Functions

Hàm băm 1 chiều phổ dụng

5

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

DANH MỤC HÌNH ẢNH

Hình 1.1. Hoạt động của một hàm băm ............................................................................................11

Hình 1.2. Sơ đồ biểu diễn các thuộc tính khả năng chống đụng độ, ngăn sự nghịch ảnh và nghịch

ảnh thứ 2............................................................................................................................................14

Hình 1.3. Thuật toán bƣớc đệm Merkle-Damgard............................................................................20

Hình 1.4. Cấu trúc Merkle-Damgard ................................................................................................20

Hình 1.5. Tấn công đa đụng độ.........................................................................................................21

Hình 1.6. Cấu trúc kim cƣơng...........................................................................................................24

Hình 1.7. Cấu trúc NMAC (a) và HMAC (b) ...................................................................................27

Hình 1.8. Cấu trúc MDP. ..................................................................................................................28

Hình 1.9. Cấu trúc cây mẫu...............................................................................................................29

Hình 2.1. Phần tử cơ bản F2/1: a. Sơ đồ tổng quát; b. Sơ đồ dạng hàm Logic với 3 biến vào; c. Sơ

đồ dạng 2 phép thế; d,e. Biểu diễn CE thuộc loại P2/1; f. Đặc trƣng vi phân của F2/1 ......................30

Hình 2.2. Mô tả trực quan toàn bộ các khả năng có thể có của hộp S 2x2 ......................................34

Hình 2.3. Tô pô của các phần tử F8/12 (a), F-1

8/12 (b), F32/96 (c), và F-1

32/96 (d)...............................44

Hình 2.4. Cấu trúc của các phần tử 32/96 (a), -1

32/96 (b), 64/384 (c) và -1

64/384 (d).......................45

Hình 2.5. Cấu trúc các phần tử đối xứng F2n/4m (a), P16/32 (b) và F64/256..........................................46

Hình 3.1: Kết quả thử nghiệm với file *.doc.....................................................................................52

Hình 3.2 : Kết quả thử nghiệm với file *.txt .....................................................................................53

Hình 3.3. Các phần tử cơ bản (a,e), (e,g), (f,i), (p,h), (x,d)...............................................................55

Hình 3.4. Phần tử CP F8/12.................................................................................................................55

Hình 3.5. Phần tử CP F-1

8/12...............................................................................................................56

Hình 3.6. Phần tử F96/1.......................................................................................................................56

Hình 3.7. Phần tử F32/96 (a), F -1

32/96 (b).

............................................................................................57

Hình 3.8. Phần tử F32/32 .....................................................................................................................57

Hình 3.9. Giao diện chƣơng trình .....................................................................................................58

Hình 3.10. Xây dựng thƣ viện HashDLL.dll.....................................................................................59

Hình 3.11. Giao diện sử dụng Add-In “Ez Hash Function” trong word 2007. .................................60

Hình 3.12. Phần tử (a) đƣợc biểu diễn thành một cặp hàm logic 4 biến (b) hoặc thành 4 phép

thế 2x2 (c). .......................................................................................................................................64

Hình 3.13. Cấu trúc tổng quát của các phần tử n/m ........................................................................65

6

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

Hình 3.14. Các đặc trƣng vi phân có thể của các phần tử F2/2..........................................................66

7

Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn/

DANH MỤC BẢNG BIỂU

Bảng 1.2. Một số thuật ngữ về hàm băm ..........................................................................................18

Bảng 2.1. Xác suất của các đặc trƣng vi phân của các phần tử ...35

Bảng 2.2. Toàn bộ các phần tử điều khiển đƣợc thỏa mãn tiêu chí lựa chọn....................................36

Bảng 2.3. Tập các đối hợp phi tuyến tính cơ bản điều khiển đƣợc ...................................................38

Bảng 2.4. Xác suất của các đặc trƣng vi phân của các phần tử và

tập .........................................................................................................................................40

Bảng 2.5. Các phần tử hoán vị điều khiển đƣợc với cấu trúc đối xứng ...........................................47