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 thuật toán mã hóa đối xứng

Học viện 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 thuật toán mã hóa đối xứng

Chuyên ngành: Kỹ thuật viễn thông

Mã số: 62.52.70.05

Họ và tên nghiên cứu sinh: Hồ Quang Bửu

Người hướng dẫn khoa học 1: GS.TSKH. Nguyễn Xuân Quỳnh

Người hướng dẫn khoa học 2: GS.TS. Nguyễn Bình

2014

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.

Hà nội, tháng 12 năm 2013

iii

MỤC LỤC

LỜI CAM ĐOAN......................................................................................................i

LỜI CẢM ƠN ..........................................................................................................ii

MỤC LỤC...............................................................................................................iii

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT.............................................vi

DANH MỤC CÁC BẢNG....................................................................................viii

DANH MỤC CÁC HÌNH VẼ.................................................................................ix

PHẦN MỞ ĐẦU......................................................................................................1

1. MỞ ĐẦU .......................................................................................................1

2. TÌNH HÌNH NGHIÊN CỨU.........................................................................1

3. LÝ DO CHỌN ĐỀ TÀI.................................................................................4

4. MỤC TIÊU NGHIÊN CỨU..........................................................................4

5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU ....................................................5

6. PHƯƠNG PHÁP NGHIÊN CỨU .................................................................5

7. Ý NGHĨA KHOA HỌC VÀ THỰC TIÊN CỦA ĐỀ TÀI............................5

CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ HỌC..................................................6

1.1. CÁC KHÁI NIỆM CƠ BẢN .........................................................................6

1.2. CÁC HỆ MẬT KHÓA BÍ MẬT....................................................................8

1.2.1. Sơ đồ khối chức năng hệ mật khóa bí mật ....................................8

1.2.2. Các hệ mật thay thế .......................................................................8

1.2.3. Các hệ mật hoán vị (MHV) .........................................................11

1.2.4. Các hệ mật mã tích ......................................................................12

1.2.5. Các hệ mật mã dòng và việc tạo các dãy giả ngẫu nhiên ............15

1.2.6. Chuẩn mã dữ liệu DES ................................................................26

1.2.7. Ưu nhược điểm của mật mã khóa bí mật.....................................29

iv

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

2.4.1. Vấn đề mã hóa .............................................................................71

2.4.2. Xây dựng hệ mật dùng cấp số nhân cyclic ..................................76

2.5. KẾT LUẬN CHƯƠNG 2...............................................................82

CHƯƠNG 3. HÀM BĂM XÂY DỰNG TRÊN CẤP SỐ NHÂN CYCLIC.......83

3.1. CÁC HÀM BĂM HỌ MD4 ...........................................................83

3.1.1. Cấu trúc........................................................................................83

3.1.2. Mở rộng thông báo ......................................................................87

3.1.3. Các bước mã hóa .........................................................................89

3.2. XÂY DỰNG HÀM BĂM MỚI TRÊN CÁC CẤP SỐ NHÂN CYCLIC ...94

3.2.1. Sơ đồ khối mật mã trong hàm băm..............................................94

3.2.2. Các đánh giá kết quả mô phỏng hàm băm mới .........................100

3.3. KẾT LUẬN CHƯƠNG 3...........................................................................101

KẾT LUẬN VÀ KIẾN NGHỊ..............................................................................102

DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN...........104

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

PHỤ LỤC A: THÔNG SỐ CỦA MỘT SỐ HÀM BĂM....................................109

PHỤ LỤC B: CÁC CHƯƠNG TRÌNH TÍNH TOÁN VÀ MÔ PHỎNG ...........122

vi

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT

AES Advanced Encryption Standard

ANSI American National Standards Institute

CAST Carlisle Adams and Stafford Tavares

CBC Cipher Block Chaining

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

CS

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)

e x( )

Đa thức lũy đẳng

ECB Electronic Codebook

F

Trường (Field)

G Nhóm (Group)

GF(p) Trường đặc số

p

h

Hàm băm (Hash)

I Ideal

IDEA International Data Encryption Algorithm

IV Initial Value

MAC Message Authentication Code

MDC Manipulation Detection Code

MD-x Message Digest x

NESSIE New European Schemes for Signatures, Integrity

and Encryption

vii

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 Z x x 

Vành đa thức trên

GF2

viii

DANH MỤC CÁC BẢNG

Bảng 1. Một số hàm băm .........................................................................................3

Bảng 1.1. Trạng thái của các vector đầu ra M-dãy ................................................22

Bảng 1.2. Các đặc tính của dãy tuyến tính có chu kỳ 2m

-1 ....................................26

Bảng 1.3. Bảng IP và IP-1

.......................................................................................28

Bảng 1.4. Độ an toàn mục tiêu của hàm băm.........................................................43

Bảng 2.1. Số kiểu phân hoạch không suy biến M của một số vành.......................57

Bảng 2.2. Tổng số các kiểu phân hoạch của vành

2

[ ]/ 1 n Z x x  ...........................58

Bảng 2.3. M-dãy xây dựng trên vành

15

2 Z [ ] / 1 x x  ..................................................63

Bảng 2.4. Các tam thức cấp cực đại 4095 (32

.5.7.13) trên vành x13 + 1................68

Bảng 2.5. Một số phần tử của M-dãy trên vành x13+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 dH(C1,Ci) giữa các cặp bản mã khi các bản rõ

khác nhau 1 bit, dH(M1,Mi) = 1, với cùng một khóa K...................................80

Bảng 2.11. Khoảng cách Hamming dH(C1,Ci) giữa các cặp bản mã khi các khóa

khác khóa K1 2 bit dH(K1, Ki)=2 với cùng một bản rõ M ...............................81

Bảng 3.1. Thông số của các hàm băm họ MD4 .....................................................85

Bảng 3.2. Ký hiệu các thông số và các biến...........................................................86

Bảng 3.3. Khoảng cách Hamming dH(MD1, MDi) khi các khối dữ liệu khác khối

ban đầu 1 bit ...................................................................................................97

Bảng 3.4. Khoảng cách Hamming dH(MD1, MDi) giữa các cặp giá trị băm khi các

khóa khác khóa K1 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 g1(d) = d

3 + d +1 và g2(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

Hình 1.8. Sơ đồ khối chức năng hệ mật khóa công khai........................................30

Hình 1.9. Phân loại hàm băm.................................................................................36

Hình 1.10. Các sơ đồ hàm băm đơn a) Matyas-Mayer–Oseas;

b) Davies-Mayer và c) Miyaguchi – Preneel ......................................37

Hình 1.11. Thuật toán MDC-2 ...............................................................................39

Hình 1.12. Thuật toán MDC-4 ...............................................................................40

Hình 1.13. Sơ đồ Miyaguchi – Preneel ..................................................................41

Hình 1.14. Kiểm tra tính toàn vẹn bằng MAC.......................................................45

Hình 1.15. Kiểm tra tình toàn vẹn dùng MDC và thuật toán mã hóa ....................45

Hình 1.16. Kiểm tra tính toàn vẹn dùng MDC và kênh an toàn ............................46

Hình 1.17. Quá trình tạo chữ ký số và kiểm tra chữ ký số.....................................47

Hình 1.18. Sơ đồ chữ ký số dùng RSA ..................................................................47

Hình 1.19. Sơ đồ chữ ký số dùng RSA và có bảo mật thông báo..........................48

Hình 2.1. Mã hóa và giải mã xây dựng trên cấp số nhân cyclic ............................71

Hình 2.2. Sơ đồ thiết bị mã hoá..............................................................................75

Hình 2.3. Sơ đồ thiết bị giải mã .............................................................................75

Hình 2.4. Sơ đồ mạng thay thế Feistel ...................................................................76

Hình 2.5. Sơ đồ mã hóa khối E ..............................................................................77

Hình 2.6. Sơ đồ khối mã hóa , với khóa

4 5

1 K x x    1 .....................................79

Hình 3.1. Tương tác giữa mở rộng thông báo và các thao tác bước ......................83

Hình 3.2. Một bước mã hóa của MD5 ...................................................................92

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

Hình 3.4. Sơ đồ bộ mã hóa khóa E với khóa K1 ....................................................95

1

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

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, điển hình là các hệ mật

sau: DES, IDEA, TDEA, AES, CAST,… Những nghiên cứu về các hệ mật này đã

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 [19], [20], [25], [28], [31], [33]. Các sơ đồ mã

hóa thường sử dụng một số lưu đồ như: Feistel cân bằng (như trong DES), Feistel

không cân bằng 4 nhánh, Lai-Massey, các mạng thay thế hoán vị…

Một hàm băm mật mã học là một hàm

h x( )

phải có các tính chất sau [24], [25],

[26]:

 Tính chất nén

 Tính chất dễ tính toán.

 Kháng tiền ảnh.

 Kháng tiền ảnh thứ hai.

 Kháng va chạm.

Các lược đồ được sử dụng để xây dựng hàm băm phổ biến bao gồm [4], [15],

[22], [29], [37]:

 Matyas – Mayer – Oseas (M-M-O).

 Davies – Mayer (D-M).

 Miyaguchi – Preneel (M-P).

 MDC-2

 MDC-4

 MAC…

Cho đến nay đã có nhiều nghiên cứu về hàm băm trên thế giới, các nghiên cứu

tập trung xây dựng các hàm băm có độ bảo mật tốt và đặc biệt là khả năng kháng

va chạm, thông thường để có được các tính chất này người ta thường phát triển các

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 Có lỗi

6 RIPEMD 128 Có

7 RIPEMD-128/256 128/256 Không

8 RIPEMD-160/256 160/256 Không

9 SHA-0 160 Không

10 SHA-1 160 Có lỗi

11 SHA-256/224 256/244 Không

12 SHA-512/384 512/384 Không

13 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

tạo IV…[23], [24].

Ở Việt Nam việc nghiên cứu các hệ mật cũng đã rất phát triển từ nhiều năm

qua, tuy nhiên việc sử dụng các hệ mật này cho các lược đồ xây dựng hàm băm

còn khá mới mẻ. Cũng có một số công trình nghiên cứu về hệ mật [13], [14] và

xây dựng hạ tầng khóa công khai phục vụ thương mại điện tử [3].

3. LÝ DO CHỌN ĐỀ TÀI

Việc sử dụng cấu trúc nhóm nhân cyclic và cấp số nhân cyclic trên vành đa

thức trong việc tạo mã sửa sai trong thời gian qua ở Việt nam đã có các kết quả

đáng khích lệ [2,] [6], [7], [8], [9], [10], [11], [12], [13], [14], bởi một số lý do: cấu

trúc đại số chặt chẽ, số lượng cấp số nhân trên vành đa thức nhiều (thuận lợi cho

việc tạo khóa trong các hệ mật), mạch điện phần cứng thực hiện khá dễ dàng

(thuận lợi cho việc áp dùng vào thực tế).

Trên cơ sở đó phân tích các hàm băm hiện có tác giả thấy rằng, mặc dù các

hàm băm có tính chất tốt nhưng lại có nhược điểm là phức tạp dẫn tới yêu cầu về

tài nguyên tính toán và thời gian tính toán. Với các ưu điểm của cấu trúc của cấp

số nhân cyclic như đề cập ở trên tác giả nhận thấy việc sử dụng cấu trúc này vào

việc xây dựng các hệ mật và các hàm băm là hướng nghiên cứu mở, đây là một

vấn đề cần thiết trong quá trình phát triển lý thuyết mật mã nói chung và xây dựng

các hàm băm mới nói riêng ở Việt Nam.

4. MỤC TIÊU NGHIÊN CỨU

 Khảo sát đánh giá hệ mật khối sử dụng cho lược đồ hàm băm.

 Xây dựng hệ mật trên các cấp số nhân cyclic trên vành đa thức.

 Xây dựng các hàm băm mới sử dụng hệ mật dựa trên các cấp số nhân cyclic

trên vành đa thức.