Luận án Tiến sĩ Kỹ thuật viễn thống: 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

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

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

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

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

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

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

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

1.3. HỆ MẬT KHÓA CÔNG KHAI ................................................................... 30

1.3.1. Sơ đồ chức năng .......................................................................... 30

1.4. CƠ BẢN VỀ HÀM BĂM ............................................................................ 33

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.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.5. TÍNH TOÀN VẸN CỦA DỮ LIỆU VÀ XÁC THỰC THÔNG BÁO........ 44

1.4.5. Độ an toàn mục tiêu ..................................................................... 43

1.5.1. Các phương pháp kiểm tra tính toàn vẹn dữ liệu ........................ 44

1.6. KẾT LUẬN CHƯƠNG 1............................................................................. 49

1.5.2. Chữ ký số ..................................................................................... 46

2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC .................................. 50

CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC .. 50

2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức ......................... 50

2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC ................................. 54

2.1.2. Các loại nhóm nhân cyclic trên vành đa thức.............................. 52

2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức .................... 54

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.2.2. Phân hoạch vành đa thức ............................................................. 55

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

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.2. XÂY DỰNG HÀM BĂM MỚI TRÊN CÁC CẤP SỐ NHÂN CYCLIC ... 94

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

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

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

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

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

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

Advanced Encryption Standard AES

American National Standards Institute

ANSI CAST

Carlisle Adams and Stafford Tavares Cipher Block Chaining CBC

Cipher Feedback Block CFB

CGP Cấp số nhân cyclic (Cyclic Geometic Progressions)

CMG

Nhóm nhân cyclic (Cyclic Multiplicate Group) Cyclic Redundancy Check CRC

Collision Resistant Function CRF

Collision Resistant Hash Function CRHF

Chu trình

Khoảng cách Hamming

deg

Bậc của đa thức (Degree) Data Encryption Algorithm DEA

DES Chuẩn mã dữ liệu (Data Encryption Standard)

Đa thức lũy đẳng

Electronic Codebook ECB

Trường (Field)

G Nhóm (Group)

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

Hàm băm (Hash)

Ideal International Data Encryption Algorithm IDEA

Initial Value IV

Message Authentication Code MAC

Manipulation Detection Code MDC

Message Digest x

MD-x NESSIE New European Schemes for Signatures, Integrity and Encryption

vii

National Institute for Standards and Technology (US) NIST

Output Feedback OFB

ord

Cấp của đa thức (Order) One-Way Function OWF

One-Way Hash Function OWHF

Vành (Ring) Race Integrity Primitives Evaluation RIPE

Rivest Shamir Adleman RSA

Secure Hash Algorithm

SHA TDEA

Triple Data Encryption Algorithm Universal One-Way Hash Function

UOWHF VEST Very Efficient Substitution Transposition

Trọng số (Weight) Vành đa thức trên

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 ........................... 58

Bảng 2.3. M-dãy xây dựng trên vành .................................................. 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

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+x4 ........................................... 23 Hình 1.4. Bộ tạo dãy Gold đối với g1(d) = d3 + d +1 và g2(d) = d3 + d2 +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 ..................................... 79 Hình 2.6. Sơ đồ khối mã hóa , với khóa

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

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

Để 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).

điểm nào.

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).

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

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

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.

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

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

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

 Davies – Mayer (D-M).

 Miyaguchi – Preneel (M-P).

 MDC-2

 MDC-4

 MAC…

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

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

TT Thuật toán Kích thước đầu ra (bit) Xung đột

1 HAVAL 256/224/192/160/128 Có

Khả năng lớn 2 MD2 128

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ị

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.

 Viết các chương trình phần mềm mô phỏng, thử nghiệm và đánh giá kết quả

đã nghiên cứu.

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.

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ố

+ Phân tích mật mã (Cryptonalys): Dành riêng cho các nhà nghiên cứu

chuyên sâu về mật mã, chuyên nghiên cứu tìm hiểu các phương pháp thám mã:

 Phương pháp tấn công tổng lực (tìm khóa vét cạn)

 Phương pháp thống kê

 Phương pháp phân tích cấu trúc…

Trong lý thuyết mã mã hóa nguồn và mã sửa sai khâu mã hóa (coding) thường chỉ có đầu vào là bản tin và đầu ra là bản mã (và ngược lại với khâu giải mã (decoding)). Tuy nhiên với mật mã học thì hai khâu này có một sự khác biệt đó là đầu vào của mã hóa (giải mã) ngoài bản tin ra còn có thêm khóa (K).

* Mã hóa (Encryption): C M Encryption hay Ta có:

M C * Giải mã (Decryption) Decryption

Ta có:

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 (khóa đối xứng):

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à:

 Bài toán logarit 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 trên đường cong elliptic

+ Mật mã khối:

Trong các hệ mật mã khối quá trình xử lý thông tin được thực hiện theo các

khối bit có độ dài xác định.

+ Mật mã dòng: Trong các hệ mật mã dòng quá trình xử lý thông tin thực

hiện trên từng bit.

+ Độ phức tạp tính toán:

- Độ phức tạp tính toán P (theo thời gian đa thức) các bài toán này là khả thi

và khá đơn giản.

- Độ phức tạp NP: NP là ký hiệu lớp các bài toán giải được bằng thuật toán không tất định (NonDeterminal) trong thời gian đa thức (Polynomial). Bài toán thuộc lớp NP thường khó giải và khá phức tạp.

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

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

Bản rõ M

Bản mã C

Bản rõ M

Nguồn tin

Bộ mã hoá

Bộ giải mã

Nhận tin

Kênh mở (không an toàn)

(Alice)

(Bob)

(Oscar) Thám mã

Kênh an toàn

Nguồn khoá

Hình 1.1. Sơ đồ khối chức năng hệ mật khóa bí mật

Một hệ mật là một bộ gồm 5 tham số thoả mãn các điều kiện

sau [4]:

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 có một quy tắc mã

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

sao cho: với .

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

1.2.2.1. Các hệ mật thay thế đơn biểu

a) Mật mã dịch vòng (MDV)

Giả sử với , ta định nghĩa:

Mã hóa:

Giải mã:

Ví dụ 1.1:

Với văn bản tiếng Anh, hoặc 27, như vậy hoặc

Ký tự

A B C D

F G H

J K

L M

Mã tương ứng

Ký tự

N O

P Q R

T U V W X Y

Mã tương ứng

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:

Nhận xét:

- Khi , 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á có thể cho tới khi

tìm được bản rõ có nghĩa). Trung bình có thể tìm được bản rõ đúng sau khi

thử khoảng quy tắc giải mã.

- Từ ví dụ trên ta thấy rằng, điều kiện cần để một hệ mật an toàn là phép tìm

khoá vét cạn phải không thể thực hiện được. Tuy nhiên, một không gian khoá

lớn vẫn chưa đủ để đảm bảm độ mật.

b. Mã thay thế (MTT).

Thay thế một ký tự bằng một ký tự khác trong bảng ký tự. Số khóa có thể có

là: , với các máy tính hiện nay thì chưa đủ an toàn.

Khi độ dài bản rõ đủ lớn, có thể sử dụng phương pháp thống kê để thám mã.

c) Hệ mật Affine

đây là một phương trình tuyến tính Mã hóa:

Giải mã:

Điều kiện tồn tại: để có thì

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 mô tả ở trên, ta có thể

gắn cho mỗi khoá 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

19 Bản rõ

8 Khoá

1 Bản mã

Như vậy, dãy ký tự tương ứng với xâu bản mã sẽ là:

chúng thành các nhóm 6 rồi cộng với từ khoá theo modulo 26 như sau:

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

Với khoá , ta xác định:

và

trong đó tất cả các phép toán được thực hiện trong .

Chú ý: Để giải mã, ta có thể dùng cùng từ khoá nhưng thay cho cộng, ta trừ

nó theo modulo 26.

Ta thấy rằng, số các từ khoá có thể với độ dài m trong mật mã Vigenere là

. 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 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 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 2

Khi đó, phép hoán vị ngược sẽ là:

1 2 3 4 5 6

3 6 1 5 2 4

Giả sử ta có bản rõ: asecondclasscarriageonthetrain

Trước tiên, ta nhóm bản rõ thành các nhóm 6 ký tự:

Sau đó, mỗi nhóm 6 chữ cái lại được sắp xếp lại theo phép hoán vị , ta có:

Cuối cùng, ta có bản mã sau:

EOANCSLSDSACRICARAOTGHNERIENAT

Khi sử dụng phép hoán vị ngược 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 và cho K là tất cả các hoán vị có thể có của .

và

Đối với một khoá (tức là một phép hoán vị nào đó), ta xác định:

trong đó là phép hoán vị ngược của

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

Một phát minh khác do Shannon đưa ra trong bài báo của mình năm 1949 là ý tưởng kết hợp các hệ mật bằng cách tạo tích của chúng. Ý tưởng này có tầm quan 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ệ và mật loại này được gọi là tự đồng cấu. Giả sử

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 và (kí hiệu là ) được xác định là hệ mật sau:

(1.1)

Khoá của hệ mật tích có dạng trong đó và .

Các quy tắc mã và giải mã của hệ mật tích được xác định như sau: Với mỗi

, ta có một quy tắc mã xác định theo công thức:

(1.2)

và quy tắc giải mã:

(1.3)

Nghĩa là, trước tiên ta mã hoá x bằng rồi lại mã hóa bằng . Quá trình

giải mã tương tự nhưng thực hiện theo thứ tự ngược lại:

Ta biết rằng, các hệ mật đều có các phân bố xác suất ứng với các không gian khoá của chúng. Bởi vậy, cần phải xác định phân bố xác suất cho không gian khoá

của hệ mật tích. Hiển nhiên ta có thể viết:

(1.4)

Nói một cách khác, ta chọn có phân bố rồi chọn một cách độc lập

có phân bố .

Sau đây là một ví dụ đơn giản để minh hoạ khái niệm hệ mật tích

Giả sử ;

Với , ta xác định:

và

Cho M là một hệ mã nhân (với các khoá được chọn đồng xác suất) và S là chính là MDV (với các khoá chọn đồng xác suất). Khi đó dễ dàng thấy rằng hệ mã Affine (cùng với các khoá được chọn đồng xác suất). Tuy nhiên, việc chứng tỏ cũng là hệ mã Affine khó hơn một chút (cũng với các khóa đồng xác suất).

Ta sẽ chứng minh các khẳng định này. Một khoá dịch vòng là phần tử . Còn khoá trong hệ và quy tắc giải mã tương ứng là

mã nhân là phần từ sao cho . Quy tắc mã tương ứng là

. Bởi vậy, một khoá trong mã tích có dạng , trong

đó:

(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 . Đó là tích của xác suất một khoá trong hệ mã Affine là:

tương ứng của các khoá a và k. Bởi vậy là hệ mã Affine.

Bây giờ ta sẽ xét . Một khoá này trong hệ mã này có dạng , trong

đó:

(1.6)

Như vậy, khoá của mã tích đồng nhất với khoá của hệ

mã Affine. Vấn đề còn lại là phải chứng tỏ rằng mỗi khoá của mã Affine xuất hiện khi và với cùng xác suất 1/312 như trong mã tích . Nhận thấy rằng

chỉ khi , (hãy nhớ lại rằng , bởi vậy a có phần tử nghịch

đảo). Nói cách khác, khoá của hệ mã Affine tương đương với khoá

của mã tích . Bởi vậy, ta có một song ánh giữa hai không gian

thực sự là mã

khoá. Vì mỗi khoá là đồng xác suất nên có thể thấy rằng Affine.

Ta chứng minh rằng

. 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:

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

(kí hiệu là ). Nếu lấy tích n lần thì hệ mật kết quả là . Ta gọi là hệ

mật lặp.

Một hệ mật S được gọi là luỹ đẳng nếu

. Có nhiều hệ mật đã nghiên cứu trong chương 1 là hê mật luỹ đẳng. Chẳng hạn các hệ MDV, MTT, Affine, Hill, Vigenère và hoán vị đều là luỹ đẳng. Hiển nhiên là nếu hệ mật S là luỹ đẳng

vì nó yêu cầu lượng khoá cực lớn mà không

thì không nên sử dụng hệ mật tích có độ bảo mật cao hơn.

Nếu một hệ mật không phải là luỹ đẳng thì có thể làm tăng độ mật bằng cách lặp nhiều lần. Ý tưởng này đã được dùng trong chuẩn mã dữ liệu (DES). Trong DES dùng 16 phép lặp, tất nhiên hệ mật ban đầu phải là hệ mật không luỹ đẳng. Một phương pháp có thể xây dựng các hệ mật không luỹ đẳng đơn giản là lấy tích của hai hệ mật đơn giản khác nhau.

Nhật xét:

Có thể dễ dàng chứng tỏ rằng, nếu cả hai hệ mật và là luỹ đẳng và giao

hoán thì và cũng là luỹ đẳng. Điều này rút ra từ các phép toán đại số sau:

(Chú ý: Dùng tính chất kết hợp trong chứng minh trên).

Bởi vậy, nếu cả và đều là luỹ đẳng và ta muốn là không luỹ

đẳng thì điều kiện cần là và không giao hoán.

Rất may mắn là nhiều hệ mật đơn giản thoả mãn điều kiện trên. Kỹ thuật thường được sử dụng trong thực tế là lấy tích các hệ mã kiểu thay thế và các hệ mã kiểu hoán vị.

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

1.2.5.1. Các hệ mã dòng

Trong các hệ mật nghiên cứu ở trên, các phần tử liên tiếp của bản rõ đều được

mã hoá bằng cùng một khoá k. Tức xâu bản mã y nhận được có dạng:

(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á

và dùng nó để mã hoá một xâu bản rõ theo quy tắc:

Mã dòng hoạt động như sau. Giả sử là khoá, và là xâu bản

rõ. Hàm được dùng để tạo ( là phần tử thứ i của dòng khoá), trong đó là

một hàm của khoá k và là ký tự đầu tiên của bản rõ:

Phần tử của dòng khoá được dùng để mã tạo ra . Bởi vậy, để

mã hoá xâu bản rõ ta phải tính liên tiếp

Việc giải mã xâu bản mã có thể được thực hiện bằng cách tính liên

tiếp

Sau đây là định nghĩa dưới dạng toán học:

Định nghĩa 1.2 [4].

Mật mã dòng là một bộ 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) là bộ tạo dòng khoá. Với

6) Với mỗi có một quy tắc mã và một quy tắc giải mã tương

ứng ; và là các hàm thoả mãn

với mọi bản rõ .

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: với mọi .

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á

Một hệ mã dòng được gọi là tuần hoàn với chu kỳ d nếu với mọi số

nguyên với chu kỳ m. Trong trường hợp này, khoá là . Mã Vigenère với độ dài từ khoá m có thể coi là mã dòng tuần hoàn . Bản thân k sẽ tạo m

phần tử đầu tiên của dòng khoá: . Sau đó, dòng khoá sẽ tự lặp lại.

Nhận thấy rằng, trong mã dòng tương ứng với mật mã Vigenère, các hàm mã và giải mã được dùng giống như các hàm mã và giải mã được dùng trong MDV:

và

Các mã dòng thường được mô tả trong các bộ chữ nhị phân tức là . Trong trường hợp này, các phép toán mã và giải mã là phép cộng

theo modulo 2.

và

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 (cũng giống như trước đây), tuy nhiên bây và đầu với

giờ ta tạo dòng khoá theo một quan hệ đệ quy tuyến tính cấp m:

(1.8)

trong đó là các hằng số cho trước.

Nhận xét:

Phép đệ quy được nói là có bậc m vì mỗi số hạng phụ thuộc vào m số hạng là một hàm tuyến tính của đứng trước. Phép đệ quy này là tuyến tính bởi vì

các số hạng đứng trước. Chú ý ta có thể lấy mà không làm mất tính tổng

quát. Trong trường hợp ngược lại, phép đệ quy sẽ là có bậc .

Ở đây khoá k gồm 2m giá trị . Nếu thì

dòng khoá sẽ chứa toàn các số 0. Dĩ nhiên phải tránh điều này vì khi đó bản mã sẽ

đồng nhất với bản rõ. Tuy nhiên, nếu chọn thích hợp các hằng số thì một

vector khởi đầu bất kì khác sẽ tạo nên một dòng khoá có chu kỳ .

Việc mã hóa và giải mã hệ mật mã dòng mô tả như dưới đây.

+ Mã hóa:

+ Giải mã:

 Để hệ thống an toàn, dãy bit khóa ngẫu nhiên phải dài hơn bản tin:

(Dẫy ngẫu nhiên có ).

 Việc tạo dãy ngẫu nhiên tốn kém và việc lưu trữ không hiệu quả, do đó phải tạo dãy giả ngẫu nhiên (có tính tiền định và được xây dựng từ các bit mầm).

1.2.5.2. Một số phương pháp tạo M- dãy

a) M-dãy và các tính chất cơ bản:

Một dãy có chiều dài cực đại (MLS) là một kiểu dãy nhị phân giả ngẫu nhiên.

Chúng là các bit tuần tự được tạo ra bằng các thanh ghi dịch phản hồi tuyến tính

(LFSR) và do vậy chúng có chu kỳ và các chuỗi nhị phân tái tạo được nhờ tính dịch vòng (ví dụ với thanh ghi m ô nhớ có thể tạo được chuỗi có chiều dài 2m-1).

Một dãy có chiều dài cực đại còn được gọi là M-dãy.

Các M-dãy có thể được biểu diễn bằng các hệ số của các đa thức bất khả quy

của vành đa thức trên trường nhị phân. Các ứng dụng cơ bản của M-dãy bao gồm:

đo đáp ứng xung, tạo chuỗi giả ngẫu nhiên trong các hệ thống thông tin số dùng để

trải phổ trực tiếp và trải phổ nhảy tần…

Biểu diễn LFSR – dãy M bằng mô hình hệ thống LFSSM

LFSSM là tên viết tắt của Linear Finite State Sequencial Machine – máy

trình tự tuyến tính có trạng thái hữu hạn.

 Trình tự vì sử dụng các ô nhớ theo trình tự.

 Hữu hạn vì số trạng thái là hữu hạn.

 Tuyến tính vì sử dụng các thuật toán tuyến tính XOR trên GF(2).

Một LFSSM được đặc trưng bởi tập hợp 5 phần tử {S, I, Y, M, }, trong đó:

S là trạng thái hiện tại, I là tập đầu vào, Y là tập đầu ra, M là hàm trạng thái kế tiếp

ánh xạ lên S và  là hàm truyền đạt ánh xạ từ S lên Y.

(a) không gian trạng thái của , không gian đầu vào , không gian

đầu ra là các không gian vector trên trường hữu hạn .

(b) với vector trạng thái , vector vào , và vector ra tại thời điểm ,

trạng thái kế tiếp thì đầu ra có dạng sau:

(1.9)

Trong đó: A,B,C là các ma trận trên K, là các vector cột.

Hưởng ứng cưỡng bức: tín hiệu ra khi có tín hiệu vào

Hưởng ứng tự do: tín hiệu ra khi không có tín hiệu vào.

LFSR như hình dưới là lớp con của LFSSM, được mô tả như sau:

Trong đó: là trạng thái hiện tại của ô nhớ i, là trạng thái kế tiếp.

Tuy nhiên, vì kích thước (độ dài) của thanh ghi dịch trong thực tế rất lớn

(hàng chục hoặc hàng trăm) nên việc biểu diễn bằng ma trận rất cồng kềnh, người

ta hay sử dụng các công cụ trên trường hữu hạn (Galois field) như hàm vết, biến

đổi d.

Một số tính chất cơ bản của M-dãy [1]

i). Tính chất dịch: Dịch vòng trái hoặc phải của một M-dãy cũng là M-dãy.

ii). Tính chất hồi qui: Một M-dãy bất kỳ trong Sm đều thỏa mãn sự hồi qui:

(1.10)

Ngược lại, bất cứ nghiệm nào của phương trình hồi qui này cũng là M-dãy

trong tập Sm. Có m nghiệm độc lập tuyến tính của phương trình hồi qui này, do đó

có M-dãy độc lập tuyến tính trong Sm.

iii). Tính chất cửa sổ: Nếu trượt một cửa sổ có độ rộng m dọc theo M-dãy thì ta nhìn thấy đúng 1 lần mỗi bộ m nhị phân khác 0 trong 2m -1 bộ. trong

iv). Tính chất số lượng số ‘1’, số ‘0’: số 1 nhiều hơn số số 0 một đơn vị: Bất

kì M-dãy nào trong cũng chứa 2m-1 số 1 và 2m-1-1 số 0.

v). Tính chất cộng: Tổng của hai M-dãy trong (mod 2, từng số hạng

một) là M-dãy khác trong

vi). Tính chất dịch và cộng: Tổng của M-dãy và dịch vòng của chính nó

(mod 2, từng số hạng một) là M-dãy khác.

vii). Tính chất tự tương quan có dạng nhọn: Hàm tự tương quan tuần hoàn

chuẩn hóa của M-dãy được xác định bởi:

(1.11)

và bằng 1 khi i=0(modN) và bằng -1/N khi i ≠ 0(mod N).

viii). Tính chất hành trình: Hành trình là một dãy các số 1 liên tiếp hoặc các

số 0 liên tiếp. Trong M-dãy bất kì, một nửa các hành trình có độ dài 1, một phần tư

có độ dài 2, 1/8 có độ dài 3 v.v… đến khi nào các phân số này còn cho số nguyên

các hành trình. Cụ thể, có hành trình có độ dài m các số 1, hành trình có

độ dài m -1 các số 0. Đối với độ dài hành trình k, 0 < k < m -1, số các hành trình của số 0 bằng số hành trình của số 1 và bằng 2m-k-2.

ix). Tính chất pha đặc trưng: Có đúng một M-dãy trong tập Sm thỏa mãn

, i ∈ Ζ. M-dãy này được gọi là M-dãy đặc trưng, hoặc pha đặc trưng của

các M-dãy trong Sm.

x). Tính chất phép chia: Phép chia cho n > 0 của M-dãy (tức lấy mẫu c cứ

mỗi n bít mã) kí hiệu là c[n], có chu kì bằng N/gcd(N, n) nếu nó không phải là dãy

toàn 0. Đa thức sinh của nó g(d) có nghiệm là các lũy thừa bậc n của các nghiệm

của g(d).

b) Tạo M-dãy bằng đa thức nguyên thủy

* Đa thức nguyên thủy: Đa thức bất khả quy bậc được gọi là đa thức

nguyên thủy nếu nó là ước của với nhưng không là ước của

(với ) [4].

Ví dụ 1.4: Với ta có và:

Hai đa thức nguyên thủy

Với ta có:

Nguyên thủy Không nguyên thủy

(vì là ước của )

Bổ đề 1.1: Dãy giả ngẫu nhiên (M-dãy) được tạo từ phương trình đồng dư sau [4]:

Với: - đa thức nguyên thủy bậc .

- đa thức mầm, thỏa mãn: ; chọn ngẫu nhiên

ứng với bit.

Ví dụ 1.5:

M-dãy được tạo như sau:

Giả sử:

Trạng thái các vec tơ mã đầu ra của M-dãy cho trong bảng 1.1. Nếu ta lấy bất

kỳ cột nào ta cũng được một M-dãy.

Nhận xét:

+ Chu kỳ dãy:

+ Số con “1” trong dãy: ; Số con “0” trong dãy:

Và do đó:

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

M-dãy 0 1 1 1 0 0 0 1 1 0

2 0 0 1 1

3 1 1 0 1

4 1 0 1 0

5 0 1 0 1

6 1 1 1 0

7 0 1 1 1

8 1 1 1 1

9 1 0 1 1

10 1 0 0 1

11 12 13 1 0 0 0 0 1 0 0 0 0 1 0

14 0 0 0 1

15 1 1 0 0

Dạng tổng quát phần cứng như trong hình 1.2

Hình 1.2. M-dãy tạo từ thanh ghi dịch phản hồi tuyến tính LFSR

Hình 1.3 là mạch điện tạo M-dãy với đa thức nguyên thủy là:

Hình 1.3. Mạch tạo M-dãy từ đa thức g(x) = 1+x+x4

c) Một số M-dãy tuyến tính khác

+ Các dãy Gold

Để tạo dãy tuyến tính có khoảng tuyến tính và kích thước tập hợp lớn, thông

thường sử dụng giải pháp ghép tuyến tính các M-dãy. Trong một hệ thống truy

nhập ngẫu nhiên hoặc các hệ thống hỗn hợp, kích thước yêu cầu của tập hợp có thể

đến vài trăm. Tập hợp Gold chứa đựng một số lớn các dãy thoả mãn hai tính chất

ACF và CCF đến một mức độ chấp nhận được. Tập gồm N+2 các dãy Gold với độ dài N bằng 2m -1 có thể được xây dựng từ cặp ưa thích các M-dãy có chu kì N

giống nhau. Cặp M-dãy ưa thích, chẳng hạn x và y, có hàm tương quan chéo 3 trị:

θx, y (n) = -1; - t(m) ; t(m) - 2

Khi tính các trị tương quan chéo, đầu tiên các số 0 và 1 được biến đổi thành

các số +1 và -1. Tập các M-dãy bao gồm cặp ưa thích các dãy x và y , các tổng

mod 2 của x và các dịch vòng của y. Cụ thể, tập các dãy Gold là:

(1.12) SGold = {x, y, x y, xT-1y, xT-2 y,..., xT-(N-1) y}

Với Ty = (y1, y2, y3,... , yN -1, y0) là dịch vòng trái của y. Biên độ tương quan

cực đại đối với hai M-dãy bất kì trong cùng tập là bằng hằng số t(m). Người ta biết

rằng các cặp ưa thích của các M-dãy không tồn tại đối với m = 4, 8, 12, 16 và tiên

đoán rằng không tồn tại nghiệm đối với tất cả m = 0 (mod 4).

Hình 1.4. Bộ tạo dãy Gold đối với g1(d) = d3 + d +1 và g2(d) = d3 + d2 +1

Mỗi dãy trong tập Gold có thể được tạo nên bởi đa thức f(d) cho bởi:

(1.13)

Vì hai đa thức h(d) và h’(d) đều là nguyên tố, ta có:

(1.14)

Điều đó có nghĩa là Gold thoả mãn quan hệ hồi quy tuyến tính bậc 2m, hay

nói cách khác ELS của dãy Gold là 2m. Mặc dù giá trị này cao hơn giá trị ELS của

tập hợp liên thông, nó vẫn còn thấp hơn so với yêu cầu của các hệ thống cần bảo

mật. Dãy Gold tạo nên một tập hợp lớn có các tính chất tương quan ACF và CCF

tốt nhưng giá trị ELS thấp.

+ Các dãy Kasami

Lớp quan trọng khác các dãy nhị phân SSMA là các dãy Kasami. Giả sử m là số nguyên chẵn và x là M-dãy có chu kì N = 2m -1, được tạo từ đa thức nguyên

thủy h(d). Các dãy Kasami nhận được bằng cách chia dãy x và thực hiện phép cộng

mod 2 trên các dãy dịch vòng. Decimating dãy tức là lấy mẫu nó một cách tuần

hoàn. Để xây dựng các dãy Kasami đầu tiên ta nhận được dãy y = x[s(m)], s(m)=2m/2 +1. Dãy lấy mẫu y cũng là M-dãy tuần hoàn, nhưng với chu kì nhỏ hơn và bằng (2m -1) / s(m) = 2m/2 -1. Tập nhỏ các dãy Kasami được cho bởi:

(1.15)

Tổng số dãy trong tập là 2m/2. Hàm tương quan chéo đối với 2 dãy bấy kỳ

trong tập Skasami nhận các giá trị trong tập {-1, -s(m), s(m) - 2}.

Tập bé Kasami được thiết kế để cải thiện các tính chất liên quan của dãy

Gold và các dãy liên thông cực đại. Với M-dãy, khi thực hiện lấy mẫu với khoảng các lấy mẫu 2m/2+1, ta sẽ thu được một M-dãy có chu kỳ N=2m/2-1 và tạo nên bởi

đa thức nguyên thủy h’(d) có bậc m/2. Như vậy, mỗi thành viên của tập bé Kasami

có thể được tạo nên bởi đa thức f(d) =h(d+h’(d) bậc 3m/2.

Tập lớn Kasami: Được tổ hợp từ tập Gold với tập bé theo cách sau:

Cho m là một số chẵn và h(d) là một đa thức nguyên thủy sinh ra M-dãy {u}. Cho w = u[s(m)] là một M-dãy có chu kỳ 2m/2-1 tạo nên bởi đa thức nguyên

thủy h’(d) bậc m/2 và h”(d) là một đa thức bậc m sinh ra dãy u[t(m)].

Tập Kasami lớn, ký hiệu KL(n), được tạo bởi f(d) = h(d)h’(d)h”(d)

Người ta đã chứng minh được rằng các hàm tương quan cho dãy KL(n) lấy

giá trị trong tập:

max= t(m).

{-1, -t(m), t(m) -2, -S(m), S(m) -2} (1.16)

Do đó ta có: c

Tương tự như dãy Gold tập Kl(n) chứa 2m/2(2m+1) dãy khi m=2mod 4 và

2m/2(2m+1)-1 dãy khi m= 0mod 4.

max vẫn

Các tập Gold và các tập bé Kasami là những tập con của tập Kasami lớn.

Đồng thời trong khi kích thước của tập tăng lên đáng kể, giới hạn trên c

như của tập Gold. ELS của các phần tử trong tập là 5m/2, tức là bằng deg[f(d)].

Các dãy được đề cập trong Bảng 1.2 là những dãy nổi tiếng nhất được tạo

nên từ M-dãy. Đó là những dãy tuyến tính và chúng được tạo ra bằng thuật toán

cộng modulo 2, là thuật toán tuyến tính trong trường nhị phân GF(2). Các dãy này

có các đặc tính tương quan tốt, trong đó dãy bé Kasami là tốt nhất. Các dãy khác

như dãy Gold, dãy Kasami lớn đều có kích thước lớn. Tuy nhiên, giá trị ELS của

chúng thấp, khoảng cùng bậc với ELS của M-dãy trong khi các giá trị ACF và

CCF kém hơn M-dãy nhiều lần. Nguyên nhân chính dẫn tới ELS thấp rõ ràng là do

phương pháp tuyến tính để cấu tạo dãy.

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

Họ m Kích cỡ Ruv.max

Gold Lẻ 2m +1 1+2(m+1) /2

Gold (good-like) 2(mod 4) 2m +1 1+2(m+2) /2

Kasami (small set) Chẵn 2m/2 1+2(m+2) /2

Kasami (large set) Chẵn 2m/2(2m+1) 1+2(m+2) /2

Bent 0(mod 4) 2m/2 1+2m/2`

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

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 [4], [25], [28], [31], [32]. 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. Trước hết ta mô tả ở mức cao về hệ thống.

Thuật toán tiến hành theo 3 giai đoạn:

1) Với bản rõ cho trước x, một xâu bit sẽ được xây dựng bằng cách hoán

vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết:

, trong đó gồm 32 bit đầu và là 32 bit cuối.

2) Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính ,

theo quy tắc sau:

trong đó  kí hiệu phép cộng theo modulo 2. f là một hàm mà ta sẽ mô tả ở là các xâu bit độ dài 48 được tính như hàm của khoá k. (trên sau, còn

thực tế mỗi là một phép chọn hoán vị bit trong k). Các khóa con sẽ

tạo thành bảng khoá.

3) Áp dụng phép hoán vị ngược cho xâu bit , ta thu được bản mã

y, tức là .

Sơ đồ mã hóa DES được xây dựng trên lược đồ Feistel như trong hình 1.5.

Hình 1.5. Sơ đồ mã hóa DES

Có 64! cách chọn các bảng hoán vị, DES chọn các bảng hoán vị IP và hoán vị

đảo IP-1 như trong bảng 1.3.

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

Các mô tả về hàm mã hóa f và khối tạo khóa con trong DES như mô tả

trong Hình 1.6 và Hình 1.7.

Hình 1.6. Mô tả hàm f trong DES

Hình 1.7. Các bước tạo khóa cho các vòng mã hóa của DES

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

1.2.7.1. Ư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.

1.2.7.2. 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.

1.3. HỆ MẬT KHÓA CÔNG KHAI

1.3.1. Sơ đồ chức năng

Đích Nguồn C C M M Mã hóa Kênh mở Giải mã

A B

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

- Khóa công khai của B (Lấy trên kênh mở)

- Khóa bí mật của B

Phép mã hóa là ánh xạ 1:1:

Giải mã:

Ưu điểm của hệ mật khóa công khai:

+ Không sử dụng kênh an toàn (đây là nhược điểm của hệ mật khóa bí mật).

+ Dễ bảo vệ, lưu trữ và sinh khóa.

+ Dễ tạo các dịch vụ an toàn khác.

Ví dụ: Với n người dùng:

Số khóa cần tạo Số khóa cần lưu giữ bí mật

Hệ mật khóa bí mật

Hệ mật khóa công khai 1

Nhược điểm của hệ mật khóa công khai:

+ Phức tạp (với trường số lớn thì phần cứng phức tạp)

+ Hiệu quả không cao, do đó khó thực hiện các dịch vụ nhạy cảm đối với độ

trễ và dịch vụ di động.

1.3.2. Một số bài toán xây dựng hệ mật khóa công khai

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 [4].

1.3.2.1. Bài toán logarit rời rạc:

Bài toán này xây trên các hàm mũ của các phần tử trong trường hữu hạn với p là số nguyên tố lớn. Bài toán ngược là phép logarit nhưng trên trường hữu

hạn và đây là bài toán khó giải khi p lớn.

Các hệ mật liên quan bao gồm:

 Thủ tục trao đổi và thỏa thuận khóa Diffie-Hellman

 Hệ mật Omura – Massey

 Hệ mật Elgamal…

1.3.2.2. Bài toán phân tích thừa số và hệ mật RSA

+ Định lý 1.1 (định lý cơ bản của số học) [4], [27], [30]:

Cho n là một số nguyên tố, tồn tại phân tích duy nhất:

(1.17)

Với: - số nguyên tố

- số nguyên dương

Nếu là tích của 2 số nguyên tố: ( -là 2 số nguyên tố lớn thỏa

mãn )

Đây là bài toán phân tích số nguyên tố lớn khó (tìm đơn giản khi biết ,

cho rất khó tìm được )

+ Hệ mật RSA (Rivest – Shamir – Adleman)

- Tạo khóa: Mỗi bên liên lạc (A,B) tạo cho mình một cặp khóa công khai –

bí mật theo các bước sau:

Bước 1: Chọn hai số nguyên tố lớn p và q có độ lớn tương đương. Bước 2: Tính

Bước 3: Chọn e ngẫu nhiên thỏa mãn:

Bước 4: Tính d với

Bước 5: + Khóa công khai: (n,e) + Khóa bí mật: d

trong đó: e là số mũ mã hóa; d là số mũ giải mã. Vai trò của e và d là như

nhau (2 số nghịch đảo), tức là nếu mã hóa dùng e thì giải mã dùng d và ngược lại.

- Mã hóa: B cần gửi bản tin m cho A.

Bước 1: B nhận khóa công khai của A: (n,e)

Bước 2: B tính

Bước 3: B gửi bản mã C cho A.

- Giải mã: A nhận C và giải mã ra m:

A tính

+ Nhận xét:

 Thám mã phải thực hiện bài toán phân tích thừa số

thì mới tính được (nếu biết d muốn tìm e phải thỏa mãn điều

kiện: )

 Hiệu quả truyền tin cao  Hệ mật RSA được sử dụng rộng rãi hơn 30 năm qua.

1.3.2.3. Bài toán xếp ba lô

Bài toán xếp ba lô được xây dựng trên dãy siêu tăng, và hệ mật xây dựng trên

bài toán này là hệ mật Merkle – Hellman. Đây là một trong các hệ mật bị thám mã

nhanh nhất.

1.3.2.4. Bài toán mã sửa sai và hệ mật Mc. Eliece

Sử dụng mã sửa sai tuyến tính ; (với là số sai sửa

được). Ma trận sinh: và ma trận kiểm tra ; thỏa mãn: .

Một trong những lớp mã này là mã Goppa, chúng được dùng làm cơ sở cho

hệ mật Mc. Eliece.

1.3.2.5. Đường cong Elliptic và các hệ mật liên quan

Bài toán này được xây dựng trên các nhóm cộng của đường cong elliptic.

đường cong Elliptic trên trường số thực có dạng sau:

Trong đó: là các số thực.

+ Đường cong Elliptic trên trường hữu hạn (Dạng Weiestrass)

Với , nếu thì phải là thặng dư bậc hai.

Điều kiện: tồn tại

Các hệ mật liên quan:

 Trao đổi khóa Diffie-Helfman trên đường cong Elliptic.

 Hệ mật Omura – Massey trên đường cong Elliptic

 Hệ mật Elgamal trên đường cong Elliptic.

1.4. CƠ BẢN VỀ HÀM BĂM

1.4.1. Mở đầu

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 h là một ánh xạ có độ dài n cố định và điều

này có nghĩa là không thể tránh khỏi các va chạm (tức là cùng một giá trị đầu ra có

thể có nhiều bộ giá trị vào khác nhau). Nếu hàm h là ngẫu nhiên theo nghĩa tất cả

các đầu ra là đồng xác suất thì có chừng các đầu vào ánh xạ tới mỗi đầu ra (t:

số bit đầu vào, n: số bit đầu ra, t > n) và 2 đầu vào được chọn ngẫu nhiên sẽ có

cùng đầu ra với xác suất (không phụ thuộc vào t).

Ý tưởng cơ bản của việc sử dụng các hàm băm trong mật mã là sử dụng

chúng như một ảnh biểu diễn rút gọn (đôi khi còn được gọi là vết, dấu tay số hay

tóm lược thông báo) của một xâu vào và có thể được dùng như thể nó chính là xâu

vào đó.

Các hàm băm được dùng cho các sơ đồ chữ ký số kết hợp với việc đảm bảo

tính toàn vẹn của dữ liệu, khi đó bản tin trước hết được băm và rồi giá trị băm

(được xem như đại diện cho bản tin) sẽ được ký thay cho vị trí bản tin gốc [4],

[34], [37].

Một lớp các hàm băm được gọi là các mã xác thực thông báo (MAC -

Message Authentication Codes) sẽ cho phép xác thực thông báo bằng kỹ thuật đối

xứng (mật mã cổ điển).

Các thuật toán MAC sử dụng 2 đầu vào (bao gồm bản tin và một khoá bí

mật) để tạo ra một đầu ra có kích cỡ cố định (n bit) với ý đồ đảm bảo rằng nếu

không biết khoá thì việc tạo ra cùng một đầu ra là không khả thi. MAC có thể được

dùng để đảm bảo tính toàn vẹn của dữ liệu, xác thực tính nguyên bản của số liệu

cũng như định danh trong sơ đồ mật mã cổ điển.

Một ứng dụng điển hình của hàm băm (không dùng khoá) để đảm bảo tính

toàn vẹn của dữ liệu có thể được mô tả như sau:

Giá trị băm tương ứng với một bản tin riêng x sẽ được tính ở thời điểm T1.

Tính toàn vẹn của giá trị băm này (chứ không phải là bản thân bản tin) sẽ được bảo

vệ theo một cách nào đó. ở thời điểm tiếp theo sau T2 phép kiểm tra sau sẽ được

tiến hành để xác định xem liệu thông báo có bị sửa đổi hay không, tức là xem liệu

bản tin có giống bản tin gốc hay không. Giá trị băm của sẽ được tính toán và

so sánh với giá trị băm đã được bảo vệ, nếu chúng bằng nhau thì bên thu sẽ chấp

nhận rằng và là như nhau và như vậy có nghĩa là bản tin đã không bị sửa đổi.

Như vậy vấn đề đảm bảo tính vẹn toàn của một bản tin lớn sẽ được gui về đảm bảo

cho một giá trị băm có kích cỡ cố định (và nhỏ).

Ứng dụng trên thường được gọi là mã phát hiện sự sửa đổi (MDC -

Manipulation Detection Codes).

1.4.2. Các định nghĩa và tính chất cơ bản

1.4.2.1. Định nghĩa Hàm băm

Định nghĩa 1.3 [4], [15], [23], 24], [26]:

Hàm băm là một hàm h có ít nhất hai tính chất sau: a)Tính chất nén: h sẽ ánh xạ một đầu vào x có độ dài bit hữu hạn tuỳ tới một

đầu ra có độ dài bit n hữu hạn.

b) Tính chất dễ dàng tính toán: Với h cho trước và một đầu vào x, có thể dễ

dàng tính được .

1.4.2.2. Một số tính chất của các hàm băm không có khoá.

Giả sử h là một hàm băm không có khoá, x và là các đầu vào, y và là các

đầu ra. Ngoài hai tính chất cơ bản trên ta còn có 3 tính chất sau [23], [24], [26]:

a) Tính kháng tiền ảnh:

Đối với mọi mã băm cho trước cần ít nhất khoảng thời gian để

có thể tìm được sao cho .

b) Kháng tiền ảnh thứ hai:

Với mọi thông điệp cho trước cần ít nhất một khoảng thời gian

để có thể tìm được thông điệp sao cho và

c) Tính kháng va chạm

Cần ít nhất một khoảng thời gian để có thể tìm được sao

cho mà .

1.4.2.3. Hàm băm một chiều (OWHF - oneway hash function).

Định nghĩa 1.4 [23], [24], [26]:

OWHF là một hàm băm (có hai tính chất cơ bản) có tính chất bổ sung là: - Kháng tiền ảnh - Kháng tiền ảnh thứ hai.

1.4.2.4. Hàm băm khó va chạm (CRHF: Collision resistant HF)

Định nghĩa 1.5 [23], [24], [26]:

CRHF là một hàm băm (có hai tính chất cơ bản) có tính chất bổ sung là: - Kháng tiền ảnh thứ hai - Kháng va chạm

Chú ý về các thuật ngữ

Kháng tiền ảnh  Một chiều

Kháng tiền ảnh thứ hai  Kháng va chạm yếu.

OWHF  Hàm băm một chiều yếu.

CRHF  Hàm băm một chiều mạnh.

1.4.2.5. Thuật toán mã xác thực thông báo (MAC).

Định nghĩa 1.6 [4]:

Thuật toán MAC là một họ các hàm (được tham số hoá bằng một khoá bí

mật k) có các tính chất sau:

(1) Dễ dàng tính toán: Với đã biết và giá trị k cho trước và một đầu

vào x, có thể được tính dễ dàng ( được gọi là giá trị MAC

hay MAC).

(2) Nén: ánh xạ một đầu vào x có độ dài bit hữu hạn tuỳ tới một đầu ra

có độ dài bit n cố định.

(3) Khó tính toán: Với các cặp giá trị không có khả năng tính

một cặp với (kể cả có khả năng với

một i nào đó).

Nếu tính chất (3) không thoả mãn thì thuật toán được coi là giả mạo MAC.

Hàm băm

Không có khoá

Có khoá

MDC

Các ứng dụng khác

MAC

OWHF

CRHF

1.4.2.6. Phân loại các hàm băm mật mã và ứng dụng

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

1.4.3. Một số phương pháp xây dựng hàm băm

1.4.3.1. Các hàm băm không có khoá

Định nghĩa 1.7 [4]:

Mật mã khối (n, r) là một mã khối xác định một hàm khả nghịch từ các bản

rõ n bit sang các bản mã n bit bằng cách sử dụng một khoá r bit. Nếu E là một

phép mã hoá như vậy thì ký hiệu cho phép mã hoá x bằng khoá k.

Định nghĩa 1.8 [4]:

Cho h là một hàm băm có lặp được xây dựng từ một mật mã khối với hàm

nén  thực hiện s phép mã hoá khối để xử lý từng khối bản tin n bit. Khi đó tốc độ

của h là 1/s.

a) MDC độ dài đơn.

Ba sơ đồ hình 1.10 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:

- Một mật mã khối n bit khởi sinh được tham số hoá bằng một khoá đối

xứng k.

- Một hàm g ánh xạ n bit vào thành khoá k sử dụng cho E (Nếu các khoá

cho E cũng có độ dài n thì g có thể là hàm đồng nhất)

- Một giá trị ban đầu cố định IV thích hợp để dùng với E.

xi Hi-1 xi

Hi-1 Hi-1 xi g g E E E

Hi Hi

b) c) Hi a)

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

và c) Miyaguchi – Preneel

* Thuật toán băm Matyas - Mayer - Oseas.

Vào: Xâu bit x

Ra: Mã băm n bit của x (1) Đầu vào x được phân chia thành các khối n bit và được độn nếu cần thiết

nhằm tạo khối cuối cùng hoàn chỉnh. Ta được t khối n bit: . Phải

xác định trước một giá trị ban đầu n bit (ký hiệu IV).

(2) Đầu ra là được xác định như sau:

* Thuật toán băm Davies - Mayer

Vào: Xâu bit x

Ra: Mã băm n bit của x (3) Đầu vào x được phân thành các khối k bit (k là kích thước khoá) và được

độn nếu cần thiết để tạo khối cuối cùng hoàn chỉnh. Biểu thị thông báo đã

độn thành t khối n bit: . Xác định trước một giá trị ban đầu n bit

(ký hiệu IV).

(4) Đầu ra là được xác định như sau:

* Thuật toán băm Miyaguchi - Preneel

Sơ đồ này tương tự như sơ đồ M-M-O ngoại trừ (đầu ra ở giai đoạn

trước) được cộng mod2 với tín hiệu ra ở giai đoạn hiện thời. Như vậy:

Nhận xét: Sơ đồ D_M có thể coi là sơ đồ đối ngẫu với sơ đồ M - M - O theo

nghĩa và đổi lẫn vai trò.

b) MDC độ dài kép: MDC -2 và MDC - 4.

MDC -2 và MDC - 4 là các mã phát hiện sự sửa đổi yêu cầu tương ứng là 2

và 4 phép toán mã hoá khối trên mỗi khối đầu vào hàm băm. Chúng sử dụng 2

hoặc 4 phép lặp của sơ đồ M - D - O để tạo ra hàm băm có dộ dài kép. Khi dùng

DES chúng sẽ tạo ra mã băm 128 bit. Tuy nhiên trong cấu trúc tổng quát có thể

dùng các hệ mật mã khối khác MDC-2 và MDC4 sử dụng các thành phần xác định

như sau:

- DES được dùng làm mật mã khối có đầu vào/ ra 64 bit và được tham số

hoá bằng khoá k 56 bit.

- Hai hàm g và ánh xạ các giá trị 64 bit U thành các khoá DES 56 bit như

Cho , xoá mọi bit thứ 8 và đặt các bit thứ 2 và thứ 3 về "10" đối

với g và "01" đối với .

Đồng thời điều này cũng phải đảm bảo rằng chúng không phải là các khoá DES yếu hoặc nửa yếu vì các khoá loại này có bit thứ hai bằng bit thứ ba. Đồng

thời điều này cũng đảm bảo yêu cầu bảo mật là .

Thuật toán MDC -2 có thể được mô tả theo sơ đồ hình 1.11:

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

* Thuật toán MDC - 2

Vào: Xâu bit có độ dài với .

Ra: Mã băm 128 bit của x (1) Phân x thành các khối 64 bit .

(2) Chọn các hằng số không bí mật IV và

từ một tập các giá trị khuyến nghị đã được mô tả trước. Tập ngầm định các giá trị cho trước này là (ở dạng HEXA)

(3) Ký hiệu  là phép ghép và là các nửa 32 bit phải và trái của

Đầu ra được xác định như sau: (với )

Thuật toán MDC - 4 có thể được mô tả theo sơ đồ sau:

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

1.4.3.2. Các hàm băm có khoá (MAC)

Các hàm băm có khoá được sử dụng để xác thực thông báo và thường được

gọi là các thuật toán tạo mã xác thực thông báo (MAC).

MAC dựa trên các mật mã khối.

Thuật toán [4]

Vào: Dữ liệu x, mật mã khối E, khoá MAC bí mật k của E.

Ra: n bit MAC trên x (n là độ dài khối của E) (1) Độn và chia khối: Độn thêm các bit vào x nếu cần. Chia dữ liệu đã độn . thành từng khối n bit:

(2) Xử lý theo chế độ CBC.

Ký hiệu là phép mã hoá E với khoá k.

Tính khối như sau:

(3) Xử lý thêm để tăng sức mạnh của MAC

Dùng một khoá bí mật thứ hai . Tính

(4) Kết thúc: MAC là khối n bit Ht

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

1.4.4. Các loại tấn công hàm băm cơ bản

1.4.4.1. Tấn công vào độ dài MDC

Cho trước một thông báo cố định và mã băm có độ dài bit,

phương pháp vét cạn để tìm một xung đột với chọn ngẫu nhiên một chuỗi và

tính thử xem hay không. Giả sử mã băm là một biến ngẫu nhiên có

phân phối chuẩn thì xác suất để tìn được xung đột là .

1.4.4.2. Tấn công vào không gian khóa của MAC

Khóa bí mật của MAC có thể xác định bằng cách tìm trên toàn bộ không gian

khóa. Với một cặp đầu vào/ đầu ra (thông báo/ MAC) cho trước, ta có thể thử tất

cả các khóa có thể để tính MAC từ thông báo đã cho, và kiểm tra giá trị MAC có

trùng với đầu ra ban đầu. Khi đó sẽ xác định được khóa bó mật của MAC. Nếu

chiều dài khóa của MAC là bit thì khóa bí mật có thể tìm được với xác suất

1.4.4.3. Tấn công vào độ dài MAC

Với một hàm băm MAC bit, việc tìm được giá trị hàm băm MAC của một

thông báo cho trước hoặc tìm tiền ảnh có xác suất thành công là khoảng . Tuy

nhiên, các giá trị băm tìm thấy không thể kiểm chứng được nếu không biết trước

cặp đầu vào/ đầu ra (thông báo/mã băm), hoặc biết trước khóa bí mật của MAC.

Mục tiêu xây dựng các hàm băm MAC là không thể tìm được chính xác một cặp

(thông báo/mã băm) mới với xác suất thành công lơn hơn , nghĩa là lớn

hơn xác suất tìm được khóa bí mật và xác suất tìm mã băm MAC.

1.4.4.4. Tấn công bằng các kết quả tính toán được

Việc tính toán trước một số lượng các cặp đầu vào/ đầu ra của hàm băm sẽ

giúp nhanh chóng tìm được tiền ảnh cũng như tiền ảnh thứ hai của một mã băm. Ở

đây, ta đánh đổi chi phí tính toán và không gian lưu trữ để đạt mục tiêu trong thời

gian ngắn. Chẳng hạn với mã băm 64 bit, người ta sẽ chọn ngẫu nhiên thông

báo đầu vào và tính mã băm của chúng, sau đó lưu trữ kết quả thành các cặp đầu

vào/ đầu ra. Việc tốn thời gian và không gian để tính toán trước giúp tăng khả năng

tòm được một tiền ảnh của một mã băm đó từ lên . Tương tự, xác suất

để tìm một tiền ảnh thứ hai tăng lên lần nếu có cặp đầu vào/ đầu ra của hàm

OWHF đã được tính trước.

1.4.4.5. Tấn công đa mục tiêu

Để tấn công kháng tiền ảnh thứ hai của một hàm băm, người ta thường cố

định một mục tiêu (mã băm của tiền ảnh thứ hai) rồi tìm một tiền ảnh khác thỏa

mãn mục tiêu đó. Nhưng nếu có mục tiêu, ta chỉ cần tìm một tiền ảnh khác thỏa

mãn một trong các mục tiêu đó. Như vậy xác suất để tìm được tiền ảnh thứ hai

tăng lên lần so với phương pháp sử dụng một mục tiêu. Điều này có nghĩa là khi

sử dụng các hàm băm có khóa, việc sử dụng nhiều lần một khóa duy nhất sẽ giảm

độ an toàn của chính hàm băm. Nếu có thông báo kèm theo mã băm, khả năng

xuất hiện một xung đột của hàm băm tăng lên lần.

1.4.4.6. Tấn công bằng các thông báo dài

Giả sử là một hàm băm bit có hàm nén là và không áp dụng thuật toán

mở rộng thông báo. Đặt là một thông báo được chia thành khối thông báo

con. Khi đó, tiền ảnh thứ hai của có thể được tìm thấy trong khoảng thời

gian tương đương với việc thực hiện hàm nén và cần không gian lưu

trữ bit, với mọi trong khoảng

Như vậy, đối với các thông báo có chiều dài lớn, việc tìm tiền ảnh thứ hai

nhìn chung dễ dàng hơn tìm tiền ảnh của một mã băm (trường hợp xấu nhất là phải

thực hiện hàm nén đến lần). Với , chi phí tính toán sẽ thấp nhất nếu

chọn , khi đó ta sẽ phải thực hiện khoảng hàm nén để tìm một tiền

ảnh thứ hai.

1.4.5. Độ an toàn mục tiêu

Để đánh giá độ an toàn tính toán của các hàm băm, chúng ta cần xác định

mục tiêu của cả người thiết kế hàm băm lẫn người muốn tấn công hàm băm đó.

Bảng 1.4 cho biết độ an toàn mục tiêu của một số hàm băm thông dụng.

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

Hàm băm

Mục tiêu thiết kế

Độ an toàn

Mục tiêu tấn công

OWHF

Kháng tiền ảnh

Tìm tiền ảnh

Kháng tiền ảnh thứ hai

Tìm tiền ảnh khác

CRHF

Kháng xung đột

Tìm xung đột

MAC

Không thể tìm khóa

Tìm khóa MAC

Kháng tính toán

Tìm cặp

khác

Trong thực tế, ta có thể xem việc thực hiện phép toán là giới hạn tính

toán của các hệ thống máy tính hiện tại, Do đó đối với hàm băm bit, ta đặt độ an

toàn mục tiêu thực tế dựa trên như sau:

 Hàm băm một chiều có : Để hàm băm thỏa mãn kháng tiền ảnh

thứ nhất và thứ hai, cần nhiều nhất là phép toán.

 Hàm băm kháng xung đột ( ). Dựa vào bảng 1.4, một xung đột

của hàm băm kháng xung đột chỉ có thể được tìm thấy trong khoảng

thời gian tương đương với việc thực hiện phép toán.

 Hàm MAC ( ) và khóa bí mật có chiều dài 64 đến 80 bit. Với

thuật toán MAC tiêu biểu, tính kháng tiền ảnh và kháng tiền ảnh thứ

hai phụ thuộc trực tiếp vào khóa bí mật của hàm MAC, do đó độ an

toàn của MAC phụ thuộc vào chiều dài của khóa bí mật.

1.5. TÍNH TOÀN VẸN CỦA DỮ LIỆU VÀ XÁC THỰC THÔNG BÁO

Định nghĩa 1.9 [4]

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 được xác định.

1.5.1. Các phương pháp kiểm tra tính toàn vẹn dữ liệu

Toàn vẹn dữ liệu chú trọng chủ yếu ở các khối dữ liệu nhị phân. Các thao tác cho khối dữ liệu không còn toàn vẹn nữa bao gồm: chèn thêm một số bit, xoát bớt một số bit, thay đổi trật tự một số bit, thay thế một số bit và tất cả các thao tác kết hợp khác.

Có ba 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.

a) Chỉ dùng MAC

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

b) Dùng MDC và mã hoá

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

c) Sử dụng MDC và kênh an toàn

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

1.5.2. Chữ ký số

Định nghĩa 1.10 [4], [34]:

Xác thực tính nguyên bản của dữ liệu là một kiểu xác thực đảm bảo một bên liên lạc được chứng thực là nguồn thực sự tạo ra dữ liệu đó ở một thời điểm nào đó trong quá khứ.

Xác thực thông báo là một thuật ngữ được dùng tương đương với xác thực

nguyên gốc của dữ liệu.

Một dạng cụ thể của xác thực nguồn gốc dữ liệu được sử dụng khá phổ biển là chữ ký điện tử. Chữ ký điện tử hay chữ ký số (electronic signature, digital signature) là thông tin đi kèm theo dữ liệu nhằm mục đích xác định nguồn gốc của dữ liệu đó. Nguồn gốc dữ liệu ở đây chính là chủ của dữ liệu đó, và chữ ký số chính là khóa bí mật riêng mã chỉ người sở hữu dữ liệu mới có.

Chữ ký số cũng đảm bảo các chức năng như xác định được người chủ của một dữ liệu (xác thực chủ thể nội dung) và xác định dữ liệu có bị thay đổi không (xác thực nội dung). Trước khi gửi dữ liệu đến các bên, người chủ dữ liệu sẽ tiến hành ký vào dữ liệu đó. Quá trình ký bao gồm tính toán mã băm của dữ liệu và mã hóa giá trị băm bằng khóa bí mật của người ký. Khi cần kiểm tra, bên nhận tiến hành giải mã (với khóa công khai của bên gửi) để lấy lại mã băm và kiểm tra với mã băm tính toán độc lập từ văn bản nhận được. Nếu hai giá trị này khớp nhau thì bên nhận có thể tin rằng văn bản xuất phát từ người sở hữu khóa bí mật. Cả hai bên tham gia vào quá trình thông tin đều có thể tin tường là văn bản không bị sửa đổi trong khi truyền vì nếu văn bản bị thay đổi thì mã băm sẽ thay đổi và lập tức bị phát hiện.

Các bước tạo chữ ký và kiểm tra chữ ký được mô tả trên hình sau:

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

Ví dụ 1.6: Sơ đồ chữ ký số sử dụng RSA như hình 1.18.

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

Quá trình ký:

 Băm thông báo M để có mã băm:

 Mã hóa mã băm bằng hệ mật RSA với khóa bí mật của A (dA):

được chữ ký số của DSA.

và truyền đi.  Ghép chữ ký số DSA với thông báo:

Quá trình kiểm tra:

 Tách thông báo M và chữ ký số DSA.

 Giải mã RSA chữ ký số bằng khóa công khai của A (eA) để thu được mã

băm của bên phát.

 Tiến hành băm M để tạo mã băm độc lập: HMDC và so sánh với mã băm

bên phát.

Nhận xét: Sơ đồ này không bảo mật thông báo M.

Để bảo mật thông báo người ta sử dụng sơ đồ chữ ký số dạng như hình 1.19.

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

1.6. KẾT LUẬN CHƯƠNG 1

Trong 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); mật mã khóa công khai (hay mật

mã hiện đại) và hàm băm, 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.

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

2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức

Định nghĩa 2.1 [6], [10]:

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.

(2.1)

Trong đó:

là nhóm nhân cyclic

là phần tử sinh (đa thức sinh), .

. Cấp

là cấp của nhóm nhân, cũng chính là cấp của phần tử sinh của nhóm là tổng số các phần tử của nhóm.

Phần tử đơn vị của nhóm chính là một lũy đẳng có cấp bằng 1.

Định nghĩa 2.2 [6], [10]:

Trong vành đa thức , nếu tồn tại một đa thức mà bình phương

của nó lại bằng chính nó thì được gọi là đa thức lũy đẳng và ký hiệu là .

(2.2)

Các lũy đẳng được xác định trên cơ sở phân tích chu trình .

Trong mỗi vành đa thức đều tồn tại một lũy đẳng ,

lũy đẳng này được gọi là lũy đẳng “nuốt” (Swallowing Idempotent).

Trong một vành bất kỳ, với n lẻ luôn tồn tại một lớp kề chỉ chứa một lũy

đẳng “nuốt” .

* Tính chất của lũy đẳng “nuốt”

- Nếu đa thức và trọng số của (ký hiệu là )

là số lẻ thì .

- Nếu đa thức và là số chẵn thì .

* Các chu trình Cs

Các chu trình theo modulo n trên trường GF(2) được xác định như sau:

trong đó

Khi đó tập các số nguyên theo modulo n được phân hoạch thành các chu

trình. Ta có:

* Ý nghĩa của các chu trình:

 Số các chu trình cho ta biết số các đa thức bất khả quy trong vành

 Lực lượng của các chu trình cho ta biết bậc của đa thức bất khả quy tương

ứng trong phân tích của nhị thức .

 Các số trong một chu trình cho biết số mũ tương ứng của đa thức lũy đẳng

Định lý 2.1: Cấp của một đa thức , (ký hiệu ), là số nguyên

dương m nhỏ nhất thỏa mãn [6], [7], [10]:

(2.3)

Trong đó là một lũy đẳng nào đó.

Như vậy sẽ tạo nên một nhóm cyclic cấp m của vành.

Định lý 2.2: Nếu là phần tử của nhóm nhân nào đó thì cấp cực đại của

được xác định như sau [6], [7], [8], [10]:

- Nếu n lẻ và ; trong đó là các đa thức bất khả quy.

Khi đó , với .

- Nếu n chẵn và .

Khi đó , với .

Bổ đề 2.1: Trong vành với ( nguyên dương), tập các đa

thức có trọng số lẻ sẽ tạo nên một nhóm nhân G các đa thức theo modulo

[7], [8], [9].

Bổ đề 2.2: Mọi phần tử trong nhóm nhân G có cấp là hoặc có cấp là ước

của [7], [8], [9] [11], [12].

Bổ đề 2.3: Số các thặng dư bậc hai trong nhóm nhân G của vành được xác

định như sau [7], [8], [9]:

(2.4)

* Các phần tử cấp n và các nhóm nhân cyclic cấp n.

Xét . . Ta có bổ đề sau:

Bổ đề 2.4: Đa thức là phần tử cấp n khi nó có chứa một số lẻ các đơn

thức có mũ lẻ có cấp n và một số chẵn các đơn thức có mũ chẵn có cấp là ước của n. Số các đa thức cấp n bằng [1].

Ví dụ 2.1: Với n = 8, có tất cả các phần tử cấp . Ta có thể sử dụng

các phần tử này để xây dựng các nhóm nhân cyclic cấp .

Có tất cả các nhóm nhân cyclic cấp và nhóm nhân I cũng thuộc vào

lớp các nhóm nhân này. Ta gọi I là nhóm nhân cyclic đơn vị.

2.1.2. Các loại nhóm nhân cyclic trên vành đa thức

2.1.2.1. Nhóm nhân cyclic đơn vị

Định nghĩa 2.3: Nhóm nhân cyclic đơn vị là một nhóm nhân bao gồm mọi đơn

thức có trong vành và nó có cấp là . Ký hiệu là [4], [6].

Hay nói cách khác nhóm nhân cyclic đơn vị là nhóm nhân cyclic có phần tử sinh

là x.

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

Định nghĩa 2.4: Nhóm nhân cyclic với phần tử sinh là đa thức bao gồm các

phần tử là lũy thừa của phần tử sinh và có thể viết dưới dạng sau [6], [10]:

(2.5)

Trong đó: là cấp của .

2.1.2.3. Đa thức đối xứng và các nhóm nhân cyclic đối xứng

Định nghĩa 2.5: (Đa thức đối xứng) [6], [10]

Đa thức được gọi là đa thức đối xứng với đa thức nếu:

thì

Với: .

Bổ đề 2.5: Nếu là một phần tử cấp thì cấp của cũng bằng . Tức là,

nếu là một nhóm nhân cyclic cấp có phần tử sinh là thì cũng là nhóm

nhân cyclic cấp với phần tử sinh là [6], [10]. Khi đó ta có:

(2.7)

Như vậy, với mỗi phần tử của nhóm nhân cyclic ta có tương ứng một

phần tử của nhóm nhân cyclic . Từ nhóm nhân cyclic A ta dễ dàng thiết lập

được nhóm nhân cyclic . Hai nhóm nhân A và được gọi là hai nhóm nhân

cyclic đối xứng trong vành đa thức.

Từ việc khảo sát các nhóm nhân đối xứng trong vành đa thức ta thấy chỉ cần

khảo sát các nhóm nhân trong một nửa vành là ta có thể suy ra kết quả khảo sát

cho toàn bộ vành. Khi coi mỗi nhóm nhân là một mã tương ứng mà ta có thể xây

dựng được trên nó, ta sẽ khảo sát được các mã trên vành.

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 với n lẻ.

Đị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 [6], [10]:

(2.8)

Trong đó: m là số các số hạng của cấp số nhân.

là số hạng đầu của cấp số nhân.

là công bội.

Giá trị của m chính là cấp của nhóm nhân sinh với phần tử sinh và lũy

đẳng . Cấp lớn nhất của phần tử được xác định bởi định lý 2.2.

Trong trường hợp ta chọn số hạng đầu , công bội là thì

Là một cấp số nhân cyclic cấp m.

Như vậy, trong vành đa thức , nếu ta chọn số hạng đầu và hạt

nhân phân hoạch khác nhau thì ta sẽ tạo ra nhiều kiểu phân hoạch khác nhau

của vành, do đó ta có các cấp số nhân cyclic để xây dựng được các mã cyclic có

cấu trúc khác nhau.

* Các cấp số nhân cyclic cấp n

Nếu ta nhân các phần tử của một nhóm nhân cyclic cấp với một phần tử bất

kỳ trong nhóm nhóm nhân G của vành đa thức ta sẽ thu được một cấp số nhân có

công bội là phần tử sinh của nhóm nhân và có số hạng ban đầu là đa thức đem

nhân.

Bổ đề 2.6: Số các cấp số nhân cyclic cấp n xây dựng được trong G trên vành

( nguyên dương) được xác định như sau [7], [8], [9]:

Ví dụ 2.2:

Số cấp số nhân N

(2.9)

2.2.2. Phân hoạch vành đa thức

Quá trình phân hoạch vành đa thức thực chất là quá trình phân chia các phần

tử trong vành đa thức thành các tập (hay các lớp kề) không trùng nhau. Các phần

tử sinh của nhóm nhân sinh được gọi là các hạt nhân của phân hoạch. Trong mỗi

phân hoạch vành đa thức, các lớp kề của nó là các cấp số nhân cyclic với cùng một

công bội.

2.2.2.1. Các bước phân hoạch vành đa thức

Để phân hoạch một vành đa thức ta thực hiện theo các bước sau đây [6], [7]:

Bước 1: + Chọn một phần tử sinh .

+ Xây dựng nhóm nhân cyclic: ,

trong đó: .

+ ;

Bước 2: + Chọn .

+ Xây dựng cấp số nhân cyclic:

Bước 3: Lặp lại bước 2 cho đến khi

Thông số là cấp của được xác định theo định lý 2.1. Giá trị chỉ có

thể bằng hoặc ước số của .

Do vành đa thức có cấu trúc đối xứng, một nửa vành gồm các phần tử có

trọng số lẻ, một nửa vành gồm các phần tử có trọng số chẵn. Vì vậy khi phân

hoạch ta chỉ cần tìm các phần tử có trọng số lẻ của vành rồi có thể dễ dàng suy ra

các phần tử chẵn.

Để xây dựng được tất cả các nhóm nhân của vành ta thực hiện các bước sau:

 Xác định tất cả các đa thức lũy đẳng trong vành, trên cơ sở phân tích các

chu trình.

 Chọn các đa thức lũy đẳng có trọng số lẻ để xây dựng các nhóm nhân

chứa chúng.

 Xây dựng tất cả các nhóm nhân cyclic có thể có của vành. Tùy theo từng

lũy đẳng mà mỗi lũy đẳng có thể tham gia trong nhiều nhóm nhân.

 Lấy đối xứng tất cả các nhóm nhân có chứa các phần tử có trọng số lẻ sẽ tạo được tất cả các nhóm nhân có chứa các phần tử có trọng số chẵn.

2.2.2.2. Phân hoạch vành đa thức suy biến và không suy biến

Có nhiều dạng phân hoạch vành đa thức khác nhau, song dạng phân hoạch

chung nhất là phân hoạch suy biến và phân hoạch không suy biến.

Định nghĩa 2.7:

Phân hoạch vành đa thức được gọi là không suy biến nếu phân hoạch bao

gồm tất cả các phần tử khác 0 trong vành đa thức. Ngược lại, phân hoạch là phân

hoạch suy biến [6].

Bổ đề 2.7: Trong một phân hoạch không suy biến tùy ý, số lớp kề trong phân

hoạch xác định theo biểu thức sau [6]:

(2.10)

* Điều kiện để phân hoạch không suy biến

Định lý 2.3: Điều kiện cần và đủ để phân hoạch vành không suy biến là nhóm

nhân sinh của phân hoạch có lũy đẳng bằng 1 [6].

Bổ đề 2.8: Số kiểu phân hoạch không suy biến khác nhau bằng số các bậc

khác nhau của các phần tử trong vành (trừ các phần tử lũy đẳng có bậc là 1), ký

hiệu là M [6].

Số kiểu phân hoạch không suy biến khác nhau chính là số ước khác nhau của

giá trị cấp lớn nhất của phần tử a(x) (max ord a(x)). Giá trị max ord a(x) .

Kết quả tính số kiểu phân hoạch không suy biến M của một số vành được

thống kê trong bảng 2.1.

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

max ord Phân tích của max ord n M

5 15 3.5 3

7 7 7 1

9 63 3.3.7 5

11 1023 3.11.31 7

13 4095 3.3.5.7.13 16

15 15 3.5 3

Bổ đề 2.9: Số kiểu phân hoạch suy biến (ký hiệu là I) bằng số Ideal trong

vành đa thức [6].

Trong vành đa thức , số Ideal của vành được xây dựng tương

ứng với các đa thức sinh , mỗi Ideal tương ứng với bộ mã cyclic (theo quan

điểm xây dựng mã cyclic cổ điển).

Các đa thức sinh tương ứng với mỗi Ideal được lập từ tổ hợp các đa

thức bất khả quy trong phân tích của nhị thức xn + 1.

, với

, với | xn + 1,

Như vậy, số đa thức sinh g(x) (tương ứng là Ideal) có thể thiết lập được từ t đa

thức bất khả quy trong phân tích nhị thức xn + 1 được xác định: .

Bổ đề 2.10: Tổng số các kiểu phân hoạch có trong một vành đa thức (ký hiệu

là C) được xác định bởi biểu thức: [6].

Tổng số các kiểu phân hoạch C của một số vành khác nhau như

trong trong bảng 2.2.

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

n

M

I

C = M.I

Số đa thức bất khả quy trong phân tích xn + 1

5 2 3 2 6

7 9 11 3 3 2 1 5 7 6 6 2 6 30 14

13 15 2 5 16 3 2 30 32 90

Như vậy, trong một vành đa thức , với mỗi giá trị n thì số kiểu

phân hoạch cũng khá nhiều, tạo ra khả năng lớn để chọn dạng mã cyclic có đặc

tính sửa sai tốt. Trong mỗi dạng mã đã xác định, ta tiến hành lựa chọn các mã sửa

sai tối ưu để sử dụng.

2.2.2.3. Các loại phân hoạch

a) Phân hoạch chuẩn

Phân hoạch chuẩn hay phân hoạch theo I – nhóm nhân cyclic đơn vị [6].

(2.11)

Hạt nhân của phân hoạch là , có cấp .

+ Các lớp kề có độ lớn bằng hoặc ước của .

Bổ đề 2.11: Trong phân hoạch chuẩn thì số lớp kề trong phân hoạch được xác

định theo biểu thức [6]:

(2.12)

+ Khi n là số nguyên tố thì có thể tính chính xác được số lớp kề.

Có một lớp kề chỉ chứa , số phần tử còn lại trong các lớp kề là

. Do đó số các lớp kề là: .

b) Phân hoạch cực đại

Định nghĩa 2.8:

Phân hoạch được gọi là cực đại nếu nhóm nhân cyclic sinh có phần tử sinh

với cấp lớn nhất, [6].

Bổ đề 2.12: Trong phân hoạch cực đại thì số lớp kề của phân hoạch được xác

định theo công thức sau [6]:

(2.13)

c) Phân hoạch cực tiểu

Định nghĩa 2.9: Phân hoạch là cực tiểu (hay phân hoạch tầm thường) là phân

hoạch có phần tử sinh của nhóm nhân cyclic là [6].

Bổ đề 2.13: Trong phân hoạch cực tiểu với phần tử của nhóm nhân ,

số lớp kề trong phân hoạch được xác định [6]:

(2.14)

Trong phân hoạch cực tiểu, mỗi lớp kề chỉ gồm 1 phần tử, do vậy số lớp kề

trong phân hoạch này đúng bằng số phần tử khác 0 có trong vành: 2n – 1 .

d) Phân hoạch vành thành các cấp số nhân có cùng trọng số

Trong trường hợp và thì cấp số nhân bao gồm

các đa thức có cùng trọng số. Vành đa thức được phân hoạch thành các cấp số

nhân với các phần tử trong mỗi cấp số nhân sẽ có cùng trọng số.

Dạng phân hoạch này chính là phân hoạch không suy biến và phân hoạch

theo nhóm nhân đơn vị.

e) Phân hoạch vành thành các phần tử có trọng số cùng tính chẵn lẻ.

Xét cấp số nhân cyclic có dạng sau [6]:

(2.15)

- Nếu lẻ.

+ Phần tử đầu tiên là đa thức có trọng số lẻ thì tất cả các phần tử của

cấp số nhân đều là đa thức có trọng số lẻ. Vì tích của các đa thức có

trọng số lẻ là một đa thức có trọng số lẻ.

+ Phần tử đầu tiên là đa thức có trọng số chẵn thì tất cả các phần tử

của cấp số nhân đều là đa thức có trọng số chẵn.

Vậy khi lẻ  các lớp kề có các đa thức có trọng số chẵn hoặc lẻ.

- Nếu chẵn, với phần tử đầu tiên là đa thức bất kỳ thì tất cả các

phần tử của cấp số nhân đều là đa thức có trọng số chẵn  phân hoạch suy biến.

Tóm lại, nếu công bội (hạt nhân phân hoạch) là một đa thức có trọng số

lẻ thì các phần tử của mỗi cấp số nhân trong phân hoạch sẽ cùng tính chẵn lẻ về

trọng số.

f) Phân hoạch vành đa thức thành các cấp số nhân theo modulo h(x).

Vành đa thức có thể được phân hoạch thành các cấp số nhân

theo modulo với [6], [7], [8].

Từ phân tích nhị thức

Trong đó, fi(x) là các đa thức bất khả quy.

Như vậy, . Tuỳ theo là tổ hợp của các fi(x) sao cho deg

giá trị mà có số đa thức bất khả quy khác nhau, nên sẽ có số khác nhau. Khi

đó, trên vành sẽ có nhiều phân hoạch ứng với các khác nhau.

Trong trường hợp này phân hoạch vành chỉ gồm 2k – 1 phần tử cho nên phân

hoạch sẽ suy biến và vành đa thức bị suy biến thành các vành nhỏ hơn.

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

2.3.1. Vành đa thức có hai lớp kề

Định nghĩa 2.10

Vành đa thức theo modulo được gọi là vành đa thức có hai lớp kề

thành tích của các đa thức bất khả quy trên trường

cyclic nếu phân tích của GF(2) có dạng sau [2]:

(2.16)

Trong đó và là các đa thức bất khả quy.

Bổ đề 2.14

Vành đa thức theo modulo là một vành đa thức có hai lớp kề cyclic nếu

n thoả mãn [2], [7], [8]:

 n phải là một số nguyên tố;

 phần tử thứ hai phải thoả điều kiện với mỗi ước nguyên

tố p của (n). (Trong đó (n) là hàm phi Euler)

Thuật toán xác định giá trị n [8], [9], [10], [11]

Vào: số nguyên tố n

Bước 1: tìm phân tích của (n-1);

xác định các ước nguyên tố pi của phân tích này.

thì n không thoả mãn.

Bước 2: với mỗi pi tính - Nếu tồn tại pi sao cho - n thoả mãn trong các trường hợp còn lại.

Ra: Giá trị n thoả mãn.

Theo thuật toán này ta xác định được một số giá trị n đảm bảo vành đa thức

theo mod xn+1 là một vành đa thức có hai lớp kề cyclic.

Dưới đây là một số giá trị n thỏa mãn.

269 293 317 347 349 373 379 389 419 421 443 461 467 491 509 523 541 547 557 563 587 613

619 653 659 661 677 701 709 757 773 787 797 821 827 829 853 859 877 883 907 941 947 1019

1061 1091 1109 1117 1123 1171 1187 1213 1229 1237 1259 1277 1283 1291 1301 1307 1373

1381 1427 1451 1453 1483 1493 1499 1523 1531 1549 1571 1619 1621 1637 1667 1669 1693

1733 1741 1747 1787 1861 1867 1877 1901 1907 1931 1949 1973 1979 1987 1997 2027 2029

2053 2069 2083 2099 2131 2141 2213 2221 2237 2243 2267 2269 2293 2309 2333 2339 2357

2371 2389 2437 2459 2467 2477 2531 2539 2549 2557 2579 2621 2659 2677 2683 2693 2699

2707 2741 2789 2797 2803 2819 2837 2843 2851 2861 2909 2939 2957 2963 3011 3019 3037

3067 3083 3187 3203 3253 3299 3307 3323 3347 3371 3413 3461 3467 3469 3491 3499 3517

3533 3539 3547 3557 3571 3581 3613 3637 3643 3659 3677 3691 3701 3709 3733 3779 3797

3803 3851 3853 3877 3907 3917 3923 3931 3947 3989 4003 4013 4019 4021 4091 4093 4099

4133 4139 4157 4219 4229 4243 4253 4259 4261 4283 4349 4357 4363 4373 4397 4451 4483

4493 4507 4517 4547 4603 4621 4637 4691 4723 4787 4789 4813 4877 4933 4957 4973 4987

5003 5011 5051 5059 5077 5099 5107 5147 5171 5179 5189 5227 5261 5309 5333 5387 5443

5477 5483 5501 5507 5557 5563 5573 5651 5659 5683 5693 5701 5717 5741 5749 5779 5813

5827 5843 5851 5869 5923 5939 5987 6011 6029 6053 6067 6101 6131 6173 6197 6203 6211

6229 6269 6277 6299 6317 6323 6373 6379 6389 6397 6469 6491 6547 6619 6637 6653 6659

6691 6701 6709 6733 6763 6779 6781 6803 6827 6829 6869 6883 6899 6907 6917 6947 6949

6971 7013 7019 7027 7043 7069 7109 7187 7211 7219 7229 7237 7243 7253 7283 7307 7331

7349 7411 7451 7459 7477 7499 7507 7517 7523 7541 7547 7549 7573 7589 7603 7621 7643

7669 7691 7717 7757 7789 7829 7853 7877 7883 7901 7907 7933 7949 8053 8069 8093 8117

8123 8147 8171 8179 8219 8221 8237 8243 8269 8291 8293 8363 8387 8429 8443 8467 8539

8563 8573 8597 8627 8669 8677 8693 8699 8731 8741 8747 8803 8819 8821 8837 8861 8867

8923 8933 8963 8971 9011 9029 9059 9173 9181 9203 9221 9227 9283 9293 9323 9341 9349

n = 3 5 11 13 19 29 37 53 59 61 67 83 101 107 131 139 149 163 173 179 181 197 211 227

9371 9397 9419 9421 9437 9467 9491 9533 9539 9547 9587 9613 9619 9629 9643 9661 9677

9733 9749 9803 9851 9859 9883 9901 9907 9923 9941 9949

2.3.2. M-dãy xây dựng trên vành đa thức

Xét vành đa thức với là số lẻ. Theo cách thông thường thì

các M-dãy có thể được tạo từ bất kỳ các thức nguyên thủy có bậc là theo

phương trình đồng dư sau:

(2.17)

Trong đó: - đa thức nguyên thủy;

- đa thức mầm;

Chu kỳ của M-dãy là: . Từ đây ta có thể xây dựng các M-dãy với

độ dài lớn như các dãy giả ngẫu nhiên được sử dụng rộng rãi trong các ứng dụng

của viễn thông.

Ví dụ 2.3:

Chọn ta có M-dãy xây dựng theo phương trình

đồng dư sau:

Các giá trị của M-dãy cho trong bảng 2.3.

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

M-Dãy

0 1 1000 0100

2 0010

3 0001

4 1100

5 0110

6 0011

7 1101

8 1010

9 0101

10 1110

11 0111

12 1111

13 1011

14 1001

15 1000

Ngoài ra, M-dãy còn được tạo từ phương trình đồng dư sau:

Trong đó: .

Số lượng các giá trị của là:

Với là hàm Phi-Euler.

Trong ví dụ trên ta có các giá trị của là:

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ề

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:

(2.18)

Trong đó:

Số lượng các đa thức là:

Trọng số là một số chẵn.

Trọng số là một số lẻ với

Số lượng các đa thức tính như sau:

(2.19)

là đa thức mầm với .

Số lượng các M-dãy lồng ghép tính theo công thức:

(2.20)

Chứng minh:

Xét nhóm nhân A tạo bởi đa thức sinh :

Ta có: .

Nhóm nhân bao gồm tất cả các phần tử có trọng số chẵn trong vành đa

thức, trừ phần tử . Trong A, có đa thức có bậc bằng .

Xét nhóm nhân A lấy theo modulo , ta nhận thấy có đa thức có

trọng số lẻ và đa thức có trọng số chẵn. Do đó, có tất cả các đa thức với

bậc thỏa mãn điều kiện sau:

(2.21)

Rõ ràng đây là một M-dãy lồng ghép.

Ví dụ 2.3:

M-dãy lồng ghép trên , ta có , các đa thức này như sau:

Ta có 8 M-dãy lồng ghép xây dựng theo phương trình:

Giả sử: ;

Số lượng đa thức là , bao gồm các đa thức sau:

Các M-dãy xây dựng từ đa thức như sau:

Ví dụ 2.4:

Xây dựng M-dãy trên vành đa thức . Các phần tử trong vành

này có cấp cực đại là:

Vành đa thức này có chiều dài của các phân hoạch là bội số chung của tổ hợp

3, 5, 7,13.

Ta sẽ tạo ra M-dãy trên vành này có chu kỳ là 4095. Chọn

Công bội sẽ được chọn là các đa thức có bậc là 4095, chẳng hạn ta có

thể chọn các tam thức ở bảng sau để trở thành công bội trong phân hoạch tạo

M-dãy theo modulo .

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

Các tam thức cấp cực đại 4095 trên vành x13 + 1

(1101000000000) (1100010000000) (1100001000000) (1100000010000) (1100000001000) (1100000000010) (1010000000001) (1010000000100) (1010000001000) (1010001000000) (1010010000000) (1011000000000) (1001010000000) (1001000100000) (1001000001000) (1+x+x3) (1+x+x5) (1+x+x6) (1+x+x8) (1+x+x9) (1+x+x11) (1+x2+x12) (1+x2+x10) (1+x2+x9) (1+x2+x6) (1+x2+x5) (1+x2+x3) (1+x3+x5) (1+x3+x7) (1+x3+x9) (1001000000010) (1000100000001) (1000100000010) (1000100000100) (1000100100000) (1000101000000) (1000110000000) (1000011000000) (1000010000001) (1000001000100) (1000001001000) (1000000110000) (1000000101000) (1000000100010) (1000000100001) (1+x3+x11) (1+x4+x12) (1+x4+x11) (1+x4+x10) (1+x4+x7) (1+x4+x6) (1+x4+x5) (1+x5+x6) (1+x5+x12) (1+x6+x10) (1+x6+x9) (1+x7+x8) (1+x7+x9) (1+x7+x11) (1+x7+x12)

Ví dụ chọn

Tính cấp số nhân:

Sau khi chạy chương trình bằng MATLAB ta sẽ có cấp số nhân A, do chiều

dài tương đối lớn, ở đây chỉ minh họa một số phần tử trong A.

Bảng 2.5. Một số phần tử của M-dãy trên vành x13+1

TT Phần tử của cấp số nhân TT Phần tử của cấp số nhân

1 2 3 4 5 6 7 8 110100000000 101000100000 111001110100 011101111111 100000101111 000100111101 010110000100 100000001001 ... 128 .... 512 ... 1024 ... 4095 ..... 100000010001 ... 101001000000 .... 100010000010 100000000000

Kết thúc phân hoạch trên tương ứng với việc kết thúc chu kỳ của m-dãy, từ

đây ta sẽ tạo được dãy cực đại có các thuộc tính dịch, hồi quy, cửa sổ… được dùng

làm dãy dãy giả ngẫu nhiên PN.

Ta có thể lấy bất kỳ bit nào trong chuỗi 12 bit của cấp số nhân A làm m-dãy,

giả sử ta lấy bit cuối cùng làm M-dãy thì chuỗi 4095 bit như sau:

Bảng 2.6. M-dãy với chiều dài 4095 theo phân hoạch cực đại

Bit 1 đến 32 Bit 33 đến 64

...

Bit 513 đến 544

00011101110100101101100001010010 00011001110001001000110110110001 ............ 01110011010111010011010010101011 ............ 11110110001010100100110110010110 ............ 10111011011101011110110110000001 ............ 100101101110000100000111101011000

... Bit 1025 đến 1056 ... Bit 2049 đến 2080 ... Bit 4063 đến 4095

- Số lượng bit “1” của M-dãy tính được là: , với xác suất là:

- Số lượng bit “0” của M-dãy tính được là: , với xác suất là:

Có thể coi xác suất xuất hiện của bit “1” và bit “0” là như nhau và xấp xỉ 0,5.

Như vậy chúng ta đã tạo ra được một M-dãy tuyến tính bằng phương pháp

mới dựa trên phân hoạch vành đa thức có hai lớp kề cyclic theo modulo . Việc

thay đổi các công bội khác nhau sẽ cho ta các khả năng tạo M-dãy ở rộng,

điều này có thể được ứng dụng trong việc bảo mật… Chẳng hạn, số khả năng phân

hoạch M tạo m dãy tuyến tính trên vành đa thức theo modulo sẽ được

tính dựa trên các phần tử có cấp cực đại 4095 được chọn làm công bội , với

cách tính theo hàm Phi-Euler:

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.7

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

8 8 64 15 5

600 512 30.720 1.023 11

1.728 2.048 3.538.944 4.095 13

139.968 131.072 1,8346.1010 262.143 19

132.765.696 134.217.728 1,782.1016 268.435.455 29

Các M-dãy tạo theo phương pháp này có ưu điểm: (1) có phân bố gần giống

ngẫu nhiên, (2) dễ thực hiện, (3) độ dài lớn tùy ỳ. Trên cơ sở đó ta có thể sử dụng

các M-dãy này vào việc tạo khóa cho các hệ mật khóa bí mật nói chung.

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

Các mã khống chế sai thường được xây dựng trên các vành đa thức lẻ [5],

[18], [21], [35], [36]. Vành đa thức với là một trường hợp đặc

biệt không được xem xét tới khi xây dựng mã sửa sai. Tuy nhiên, với việc sử dụng

cấu trúc nhóm nhân và cấp số nhân cyclic trên các vành đa thức này ta có những

ứng dụng khá lý thú trong mật mã.

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

Mỗi cấp số nhân cyclic cấp n có thể coi là một phép biến đổi tuyến tính của

vector mã ban đầu (được coi là nhóm nhân cyclic đơn vị I) .

Gọi là phần tử sinh của một nhóm nhân cyclic cấp . Ta có bổ đề sau:

Bổ đề 2.16: Tổng các số hạng của một cấp số nhân cyclic cấp có công bội

và số hạng đầu được xác định theo biểu thức sau [4]:

(2.22)

Hiển nhiên là . Hệ mật xây dựng trên các cấp số nhân này có thể được

mô tả theo sơ đồ khối hình 2.1.

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

Mỗi phép biến đổi (mã hoá) A có thể được đặc trưng bởi một ma trận vuông

cấp n có dạng sau:

(2.23)

là một ma trận không suy biến nên luôn tồn tại thoả mãn:

Tập các phép biến đổi này là một tập kín đối với phép tính (nhân ma trận) và

tạo nên một nhóm nhân có phần tử đơn vị là phép biến đổi đồng nhất (ma trận đơn

vị I).

Nhóm nhân trong vành các ma trận vuông này là nhóm tuyến tính đầy đủ và

được ký hiệu là .

Thuật toán mã hoá khá đơn giản, chỉ dựa trên phép toán nhân và bình phương

một đa thức theo modulo ( có cấp ) với một đa thức

bất kỳ .

Vấn đề giải mã

Để giải mã ta phải tìm phép biến đổi ngược là ma trận nghịch đảo của ma

trận . Tuy nhiên ta có thể dễ dàng thực hiện giải mã dựa trên bổ đề sau:

Bổ đề 2.17: Ma trận có cấp (order) là n, hoặc là ước của n. Tức là ta luôn

có: [4].

Hay: (2.24)

Ở đây, là phần tử sinh của một nhóm nhân cyclic có cấp bằng hoặc

bằng ước của .

Ví dụ 2.5:

Xét chọn đa thức làm phần tử sinh, ta có:

Chú ý: Ở đây ta biểu diễn các đa thức qua các số mũ của các thành phần khác

Vào

Mã hoá

Vào

Giải mã (A2)2 =

I 

A 

không. Ví dụ: .

Các ma trân luân hoàn

Khi sử dụng cấp số nhân có công bội và có số hạng đầu là một đa thức

ta sẽ có một lớp các biến đổi đặc biệt, được đặc trưng bởi một loại ma

trận đặc biệt, được gọi là ma trận luân hoàn.

Định nghĩa 2.11: Ma trận vuông trên trường được gọi là ma trận

luân hoàn nếu nó có dạng sau [4]:

(2.25)

Bổ đề 2.18: Đại số các ma trận luân hoàn cấp trên trường đẳng cấu với

đối với phép ánh xạ các ma trận luân hoàn thành các đa thức đại số

dạng [4]:

(2.26)

Bổ đề 2.19: Tổng và tích của hai ma trận luân hoàn là một ma trận luân hoàn [4].

Ta có:

Trong đó:

Bổ đề 2.20: Ma trận luân hoàn là khả nghịch khi và chỉ khi đa thức là

nguyên tố cùng nhau với . Ma trận nghịch đảo B nếu tồn tại sẽ tương ứng

với đa thức thoả mãn điều kiện [4]:

(2.27)

Trong trường hợp vành và , ta luôn có:

Bổ đề 2.21: Tập các ma trận luân hoàn A ứng với sẽ tạo nên một

nhóm con nhân Abel trong nhóm nhân của vành các ma trận vuông. Trong nhóm này

tồn tại các nhóm con là các nhóm nhân cyclic có cấp bằng hoặc ước của [4].

Bổ đề 2.22: Cấp của ma trận luân hoàn A bằng cấp của đa thức tương

ứng của nó [4].

Khi thì ma trận luân hoàn A tương ứng là một ma trận tự

nghịch đảo.

Bổ đề 2.23: Số các ma trận luân hoàn dùng để lập mã bằng số các phần tử của

nhóm nhân trong vành đa thức [4].

Với trường hợp ma trận luân hoàn, thuật toán mã hoá chỉ là một phép cộng

với n bước dịch vòng.

Thuật toán giải mã bao gồm một phép tính nghịch đảo của một đa thức theo

modulo và n bước dịch vòng tương ứng của phần tử nghịch đảo này.

Ví dụ 2.6: Chọn

Vào

(7)

(6)

(5)

(4)

(3)

(2)

(1)

(0)

(10110101)

(00001000)

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

Vào

(7)’

(6)’

(5)’

(4)’

(3)’

(2)’

(1)’

(0)’

(00001000)

(10110101)

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

= I

Đa thức nghịch đảo: . Ta có:

A.A-1 =

1 0 0 0 0 0 0

1 1 0 0 0 0 0

1 1 1 0 0 0 0

0 1 1 1 0 0 0

0 0 1 1 1 0 0

0 0 0 1 1 1 0

0 0 0 0 1 1 1

0 0 0 0 0 1 1

0 1 0 1 1 0 1

1 0 1 0 1 1 0

1 1 0 1 0 1 1

0 1 1 0 1 0 1

1 0 1 1 0 1 0

1 1 0 1 1 0 1

0 1 1 0 1 1 0

1 0 1 1 0 1 1

1 0 0 0 0 0 0

0 1 0 0 0 0 0

0 0 1 0 0 0 0

0 0 0 1 0 0 0

0 0 0 0 1 0 0

0 0 0 0 0 1 0

0 0 0 0 0 0 1

0 0 0 0 0 0 0

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

2.4.2.1. Mạng hoán vị - thay thế Feistel

Trong mật mã cổ điển, việc sử dụng riêng các phép hoán vị hoặc thay thế đều không đảm bảo độ mật cần thiết. Một phương án kết hợp do Shanon đề xướng nên

sử dụng các hệ mật mã tích bằng cách dùng các phép hoán vị và thay thế kết hợp

để tăng độ mật.

Một trong các phương án đó là sử dụng mạng hoán vị thay thế theo lược đồ

Feistel. Lược đồ Feistel được đề xuất vào đầu những năm 70 và đã được kiểm chứng

là một lược đồ tốt chống được các phân tích mật mã, lược đồ này đươc sử dụng

trong nhiều hệ mật mã khác nhau trong đó có chuẩn mã dữ liệu (DES) của Mỹ.

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

2.4.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.

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ình 2.5. Sơ đồ mã hóa khối E

Hàm đượ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 là các phần tử trong một cấp số nhân

được chọn như sau:

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

là một phần tử nguyên thủy của nhóm nhân cyclic có cấp bằng và

cũng là một đa thức có trọng số lẻ. Cần chú ý rằng với vành

là một vành có hai lớp kề cyclic.

Bảng 2.8. Bảng hoán vị ban đầu (IP)

Bảng 2.9. Bảng hoán vị đảo (IP-1)

Giả sử ta chọn khóa ,

Phần tử đầu Phần tử đầu của cấp số nhân và cũng là

khóa đầu tiên là: Sơ đồ khối bộ mã hóa với

64 bit

….

khóa như trong hình 2.6.

(63)

(62)

(5)

(4)

(3)

(2)

(1)

(0)

Dữ liệu vào

64 bit

Dữ liệu ra

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

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

(2.28)

Trong sơ đồ mã hóa hình 2.5 tác giả có thay đổi so với sơ đồ Feistel, đó là

nửa trái ở bước thứ bằng nửa phải ở bước thứ cộng với khóa (chỉ cộng

61 bit đầu tiên với khóa). Sở dĩ phải làm như vậy để tránh trường hợp khi các bit

dữ liệu đầu vào toàn là bit “0” thì dữ liệu mã hóa đầu ra cũng sẽ toàn là bit “0”, vì

hàm f trong sơ đồ của chúng tôi thực hiện cộng các bit dữ liệu chứ không cộng với

các bit của khóa.

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

, phần tử đầu ; phần tử đầu của cấp số nhân

(khóa đầu tiên) là:

Bản tin rõ đầu tiên gồm 32 ký tự dạng hexa (tương ứng 128 bit) là:

M1 = 0123456789ABCDEF0123456789ABCDEF

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

Bản rõ Bản mã

0123456789ABCDEF0123456789ABCDEF 2123456789ABCDEF0123456789ABCDEF 0023456789ABCDEF0123456789ABCDEF 0133456789ABCDEF0123456789ABCDEF 0122456789ABCDEF0123456789ABCDEF 0123656789ABCDEF0123456789ABCDEF 0123446789ABCDEF0123456789ABCDEF 0123457789ABCDEF0123456789ABCDEF 0123456389ABCDEF0123456789ABCDEF 01234567C9ABCDEF0123456789ABCDEF 012345678DABCDEF0123456789ABCDEF 0123456789BBCDEF0123456789ABCDEF 0123456789A9CDEF0123456789ABCDEF 0123456789ABEDEF0123456789ABCDEF 0123456789ABCCEF0123456789ABCDEF 0123456789ABCDFF0123456789ABCDEF 0123456789ABCDEB0123456789ABCDEF 0123456789ABCDEF4123456789ABCDEF 0123456789ABCDEF0523456789ABCDEF 0123456789ABCDEF0103456789ABCDEF 0123456789ABCDEF0121456789ABCDEF 0123456789ABCDEF0123556789ABCDEF 0123456789ABCDEF0123476789ABCDEF 0123456789ABCDEF0123452789ABCDEF 0123456789ABCDEF0123456F89ABCDEF 0123456789ABCDEF0123456799ABCDEF 0123456789ABCDEF0123456788ABCDEF 0123456789ABCDEF0123456789EBCDEF 0123456789ABCDEF0123456789AACDEF 0123456789ABCDEF0123456789AB8DEF 0123456789ABCDEF0123456789ABC5EF 0123456789ABCDEF0123456789ABCDFF 0123456789ABCDEF0123456789ABCDEE

E9D8211132A6A374BC286082EFA45DA8 3FEDC41619D4B600C059740D7A7D3DB6 BA63820AED3E453E46236D0BBCE621CB 64ED9A2B835B2A1A1887D0527791796F 318B9AB229793B92F6D26B8F66F71FD4 F15FF724D7A18806A95C1CF3FB2BC871 F60072AA91BD7CEC5A629A89E22D0EEA E029AC24899C12893546C42D5F74C59D ABA4425CDC28CF0BDEB34969C3907BE5 DCFCE627E6484BB24B0ED91051661ECA BA9A5D727F482D18C34AFBAB0488698E CF9528E0BF93184E0DD5E9EC4B0BED78 D78E46904ACBF02ACC9A47D3A8634AE9 EC3B44672A217541592F4BF0FAD021D9 AABAF5812D7EF0CF1F33BF1A09EEA7A3 C5EC075C3B572E410712D17F66CAF907 E2D5A84270DAC03952A60CFD8D3F7443 4668F1890782644268C688441882E43A 13D32C9861E4DF17F1C6EEEE90C6C681 F4C77D14D1C3D56C3BFE5567E88F2FBD 3829E4410CF0C4F5C44533DC9F167AF9 72F1CA3D0680EE7D4DA55539D515A021 BD09D0D46298F5133D500DD1B1D4EF8F 60B685BE82763B4198EF5656014C9B5F CE8966D625E75B2D212E8137A2DD9C62 96BABA38D98A9752F121910FDA1F6719 1EFE98838C64E01668B87F5ABC1FFEB3 5825A87F960913A4241D4445D970B340 2F2F07A8A0186137DEFCF09D37F7E60B D369DC985C020CC46CB055A628928946 B7A8933663E16463FDD0391FE945E8E5 07564D6E503D8A9F901C46CFE655D09D 0730E7E6141F31CA7E6B02567FBB85FB

0 63 66 66 66 63 66 66 66 66 66 66 63 63 66 66 66 66 66 63 63 66 63 66 63 66 66 66 66 66 63 66 66

(Chú ý: trong bảng 2.10, những ký tự hexa in đậm chứa bit thay đổi)

TT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

Khoảng cách Hamming trung bình giữa các bản mã là:

(2.29)

Bảng 2.11 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]:

M = 0123456789ABCDEF0123456789ABCDEF

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ẻ.

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 vẫn là Phần tử

sinh khóa đầu tiên có trọng số như sau:

Các khóa chỉ thay đổi 2 bit trong một số hexa của khóa đầu tiên .

Chú ý: vị trí các bit “1” trong các khóa tương ứng là số mũ của trong

đa thức sinh tạo khóa. Ví dụ 2.7:

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

Bản mã Khóa

123456789ABCDEF1 223456789ABCDEF1 113456789ABCDEF1 125456789ABCDEF1 123756789ABCDEF1 123436789ABCDEF1 123455789ABCDEF1 123456189ABCDEF1 123456749ABCDEF1 123456780ABCDEF1 1234567896BCDEF1 123456789A7CDEF1 123456789ABADEF1 123456789ABC1EF1 123456789ABCD2F1 123456789ABCDEC1

0 66 70 68 70 62 74 56 58 70 60 70 58 70 60 62

33 33 33 33 35 33 33 31 33 31 33 33 33 31 31 31

B5733992DC61C07BD38B6196D2434300 61E6E5A5C93122EFB5D6D4A81DED9184 CCDE27DCCFF1C9853E4996E02A1619A9 ADDC3348559C4D7101D62EB489A5F66F DA18C6B04FFA4F97C0412EAB528B5C78 77F9E155A67092ABF8F7A5F66D0827EB C4014F02F5A63F6E8C2C98855D2A34EA 15629261C809D76B6CD525B168622F21 68E00F4AB5A9061FD7822787633024AC 176D974F14841A053D9B5B79E607A4AA 398840062A8D0BD055EB5B961AEB0691 93CFF32DD509BDE42409312E8818E3FF 56A632C099DF4A1AF8C9AD2A928845B1 2180C04805CF8DEAA539B3BF86BAD257 83390D707279E0F64EE8C762334DD474 AF304D735EDF45A4397E7CF3832B8346

TT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

(Chú ý: trong bảng 2.11, 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ã:

(2.30)

Qua các kết quả khảo sát khoảng cách Hamming ở trên ta thấy tính khuếch

tán của hệ thống là tốt, tương đương với hệ mật DES.

Phép giải mã được thực hiện theo chu trình ngược lại so với sơ đồ mã hóa,

các khóa phải được sử dụng theo thứ tự ngược lại. Tức là, nếu các khóa mã hóa

cho mỗi vòng là thì các khóa giải mã cho vòng tương ứng sẽ

là .

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

Nội dung chương này đề cập đến cấu trúc cấp số nhân của vành đa thức, xây

dựng được một hệ mật trên các cấp số nhân cyclic này. Cụ thể là hệ mật mới này

được xây dựng theo lược đồ Feistel có sửa đổi (sơ đồ mật mã khối có độ dài đầu ra

128 bit), hàm mật mã f và việc tạo khóa được xây dựng theo cấu trúc của cấp số

nhân cyclic trên vành đa thức chẵn.

Một số ưu điểm nổi bật của hệ mật này là (1) Mạch điện mã hóa và giải mã

cùng một cấu trúc và rất đơn giản chỉ gồm các thanh ghi dịch và bộ cộng modul 2,

tốc độ xử lý nhanh, (2) Dễ dàng mở rộng độ dài từ mã trên các vành đa thức

với , (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) và đây là cơ sở để xây dựng các hàm băm mới, được

trình bày trong chương 3.

CHƯƠNG 3. HÀM BĂM XÂY DỰNG TRÊN

CẤP SỐ NHÂN CYCLIC

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

Sở dĩ phần này đề cập đến các hàm băm họ MD4 là vì đa số các hàm băm

đang sử dụng phổ biến như MD4, MD5, RIPEMD-{0, 128, 160, 256, 320}, SHA-

{0,1,224, 256, 384, 512} đều là các nhánh trong họ MD4 [23].

3.1.1. Cấu trúc

Các hàm băm họ MD4 đều dựa theo nguyên lý thiết kế của Merkle-

Damgºard. Chúng có nhiều điểm tương đồng trong các hàm nén. Sơ đồ cơ bản

được mô tả trong hình 3.1 [23].

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

Các hàm nén sử dụng một số các thanh ghi được khởi tạo cùng với IV. Các

thanh ghi sau đó được cập nhật trong các bước liên tiếp phụ thuộc vào thông báo.

Ngoài việc phụ thuộc vào thông báo, các bước đơn lẻ rất giống nhau, chỉ thay đổi

một vài thông số cụ thể.

Đầu ra cuối cùng của hàm nén được tính từ trạng thái cuối cùng của các

thanh ghi và IV (thông thường là cộng chúng với nhau). Việc tính ngược hàm nén

là không thể, điều này rất cần thiết để tránh phép tấn công kẻ đứng giữa.

3.1.1.1. Các thông số

Chi tiết về cấu trúc tổng quát của mỗi hàm được mô tả bớt một vài tham số

như trong bảng 3.1. Các thông số chính của tất cả các hàm băm đều dựa theo

nguyen lý MD: đầu ra hàm băm có độ dài n, đầu ra hàm nén có độ dài m và đầu

vào các khối thông báo có độ dài l.

Hầu hết các hàm của họ MD4 đều được tối ưu trong thiết kế phần mềm trên

các vi xử lý 32 bit, ví dụ chiều dài một từ là bít. Ngoại trừ SHA-384 và

SHA-512 có .

Các tham số khác được suy ra bao gồm: Số lượng các từ đầu vào của hàm

nén, ký hiệu là t, và được tính là . Tương tự, chiều dài đầu ra m của hàm

nén chính là chiều dài của giá trị chuỗi, trong các họ MD4 các hàm băm được dùng

khởi tạo các thanh ghi, số lượng r các thanh ghi tính được là: .

Thông số quan trọng tiếp theo là số bước s (còn gọi là các vòng). Đây được

xem là thông số bảo mật. Để tăng tính bảo mật của hàm băm thông thường tăng số

bước s, tuy nhiên khi đó hiệu quả sẽ giảm.

Các thông số cơ bản của một số hàm băm cụ thể được mô tả trong bảng 3.1.

Chú ý SHA-0 và RIPEMD-0 là các hàm băm nguyên thủy không có ký hiệu “-0”.

Sau này ký hiệu này được thêm vào để tránh nhầm lẫn. Ký hiệu “2x” trong bảng

liên quan đến việc các hàm sử dụng 2 tính toán song song độc lập. Ngoại trừ SHA-

224 và SHA-384 độ dài đầu ra m của hàm nén vào đầu ra n của hàm băm là giống

nhau, . Trong SHA-224 và SHA-384 ở bước cuối cùng cắt bỏ bit để giảm

giá trị băm thực tế.

3.1.1.2. Ký hiệu

Khối thông báo đầu vào được chia thành t khối nhỏ (các từ thông báo)

ký hiệu . Sau đó các từ thông báo này được mở rộng thành các giá

trị , trong đó các là các đầu vào ở bước thứ i. Giá trị trong các

thanh ghi ở các bước được ký hiệu là .

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

(Ký hiệu * là thiết kế ban đầu không có ký hiệu “-0” nó được thêm vào sau này để tránh nhầm lẫn)

Các ký hiệu và thông số được thống kê trong Bảng 3.2.

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

số lượng các thanh ghi số lượng các bước (vòng) số lượng các từ thông báo đầu vào

l độ dài các khối thông báo đầu vào (theo bit) m độ dài đầu ra hàm nén (theo bit) n độ dài đầu ra hàm băm (theo bit) r s t w chiều dài một từ (theo bit)

hoán vị sử dụng ở bước thứ k.

phép toán logic ở bước thứ i.

hệ số sử dụng ở bước thứ i.

nội dung trong thanh ghi ở bước thứ i.

số bit dịch ở bước thứ i.

từ thông báo đầu vào ở bước i, phụ thuộc vào thông báo. từ thông báo

3.1.1.3. Phân loại họ MD4

Có hai điểm khác biệt chính để phân loại các hàm băm họ MD4 thành các

phân lớp sau:

 Hàm mở rộng thông báo được thực hiện ở hoán vị trong các vòng hay

mở rộng đệ quy.

 Số lượng xử lý tính toán song song.

Tùy thuộc vào hai đặc điểm này các hàm được phân loại thành các phân lớp sau:

+ Họ MD:

MD4 và MD5 thuộc phân lớp này là vì sử dụng hoán vị vòng và chỉ xử lý

tính toán theo một luồng.

+ Họ RIPEMD:

Họ RIPEMD bao gồm RIPEMD-{0;128; 160; 256; 320} và cả MD4 mở

rộng. Các hàm này sử dụng hoán vị vòng cho việc mở rộng thông báo nhưng xử lý

tính toán song song 2 luồng.

+ Họ SHA:

Họ SHA sử dụng hàm nén SHA-{0, 1, 224, 256, 384, 512} và xử lý tính toán

một luồng, nhưng việc nén thông báo được thực hiện theo hàm đệ quy.

Chú ý: (HAVAL). Có một hàm băm đáng quan tâm đó là HAVAL, nó gần

giống với thiết kế theo cấu trúc tổng quát. Nhưng có một sự khác biệt quan trọng là

việc sử dụng các hàm Boolean rất khác với các hàm đã đề cập, chúng ta không đề

cập HAVAL là một bộ phận của họ MD4.

Chi tiết thông số của các hàm băm được mô tả trong Phụ lục A.

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

Mở rộng thông báo mô tả việc các giá trị (được xem là các đầu vào cho

các bước mã hóa) được tính toán từ khối thông báo đầu vào hiện tại . Do đó

khối thông báo đầu vào hiện tại được chia thành t từ và sau đó

tính ra s giá trị .

Trong họ MD4 có hai phương pháp để thực hiện việc này đó là: dùng hoán vị

vòng và các hàm đệ quy.

3.1.2.1. Hoán vị vòng

Kiểu mở rộng thông báo này được dùng trong MD4, MD5, tất cả các biến thể

của RIPEMD và HAVAL. Hoán vị vòng có nghĩa là các bước được nhóm lại với

nhau thành vòng bao gồm mỗi t bước (thông thường là 16). Sau đó, trong mỗi

vòng mỗi một từ thông báo được dùng làm đầu vào trong một bước.

Có thể mô tả một hoàn vị vòng cho mỗi vòng k như sau:

(3.1)

Hay nói cách khác: được dùng làm đàu vào ở bước này.

(3.2)

Mô tả mở rộng thông báo của MD4 như sau:

Thông thường phép hoán vị được lựa chọn theo cách các ít các mẫu càng tốt,

ví dụ không có 2 từ được đưa vào hai vòng liên tiếp. Điều này là để có tính

khuếch tán tốt. Ngoài ra rất nhiều nhà thiết kế đều muốn một “mở rộng” đơn giản

để lựa chọn các tham số. Ví dụ mở rộng thông báo của MD5 sử dụng công thức rất

đơn giản:

(3.3)

3.1.2.2. Mở rộng thông báo theo kiểu đệ quy

Khác với các phép hoán vị vòng, các hàm trong họ SHA sử dụng csc phpes

mở rộng thông báo đệ quy: sau khi chọn csc giá trị khởi tạo

Giá trị sau được tính đệ quy từ trước.

Kiểu mở rộng thông báo này có ưu điểm là tăng độ khuếch tán, vì tất cả các

đều phụ thuộc (gần như) vào . Do đó, nếu một trong các từ của thông báo bị

thay đổi, nhiều bước trong giai đoạn 2 của bước tính toán sẽ bị ảnh hưởng. Điều

này làm cho việc dự đoán tiến trình trong một bước khó khăn hơn.

Trong SHA-0, thuật toán đệ quy sử dụng như sau:

(3.4)

Tuy nhiên có một khiếm khuyết trong phép đệ quy này: bit thứ k của mỗi từ

chỉ bị ảnh hưởng bởi các bit thư k ở trước. Có nghĩa là phép mở rộng này có

độ khuếch tán thấp hơn mong đợi với cùng một cấu trúc. Bản SHA-1 sửa đổi sử

dụng phép mở rộng thông báo sau để có độ khuếch tán tốt hơn:

(3.5)

Trong các phiên bản SHA sau này NIST quyết định ghép thêm không những

các phép và quay bít, mà còn thêm phép dịch bit và cộng modulo trong khi mở

rộng thông báo. Do đó, hai hàm phụ:

được thêm vào để tăng độ khuếch tán giữa các bit hơn so với việc xoay một

bit của SHA-1. Ngoài ra việc sử dụng phép dịch bit (>>) trong các hàm này (thay

vì phép quay >>>) tránh việc quay đối xứng có thể gây ra các nhược điểm tiềm

tàng.

SHA-256 (và cả SHA-224, sử dụng SHA-256 nhưng loại bỏ 32 đầu ra) dùng

quy tắc mở rộng thông báo như sau:

(3.6)

Do việc sử dụng các phép tính modulo thay vì phép trước đây, phép mở

rộng thông báo này không còn là tuyến tính nữa.

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

Bước mã hóa là phần chính, có thể nói là trái tim của mỗi hàm nén. Chúng

phải được thực hiện dễ dàng, rất hiệu quả, tuy nhiên tại cùng thời điểm chúng phải

có độ khuếch tán tốt và khó phân tích.

Căn cứ vào hiệu quả có hai hướng trong bước mã hóa của họ MD4 đó là:

 Chỉ một trong các thanh ghi (hoặc hai) bị thay đổi tại mỗi bước. Điều này rất quan trọng để đạt hiệu quả khi lập trình phần mềm, không thể tính các thanh ghi khác nhau theo cách song song.

 Các bước mã hóa được xây dựng hiệu quả cao và các phép toán cơ bản

đơn giản.

Để đạt được hướng thứ 2, thì trong các bước đơn của quá trình nén của tất cả

các hàm băm họ MD4 đều dựa trên các phép toán sau:

 Các phép toán Boolean

 Phép cộng số tự nhiên modulo .

 Dịch bít và quay.

Sở dĩ sử dụng các phép toán này là vì chúng có thể được thực hiện rất hiệu

quả trên cấu trúc máy tính hiện đại, ngoài ra việc trộn các hàm Boolean và phép

cộng được tin là có độ bảo mật cao.

3.1.3.1. Các phép toán Boolean

Một phần quan trọng trong bước mã hóa của họ MD4 đó là được cấu tạo từ

các hàm Boolean, áp dụng cho phép toán bit trên toàn bộ các từ thông báo. Nếu ta

tính trên các bit, ta áp dụng nó vào 3 từ có hàm Boolean

bằng quy tắc sau:

(3.7)

Cụ thể, các thuật toán bước của MD4 sử dụng các hàm Boolean sau đây:

Việc sử dụng các hàm này là vì chúng có các đặc tính quan trọng để có hiệu

ứng thác lũ tốt, có nghĩa một thay đổi nhỏ trong các thanh ghi sẽ gây ra sự thay đổi

lớn chỉ sau vài vòng.

Nếu các bit của x, y và z là độc lập thì các bit đầu ra sẽ độc lập, khi thay đổi 1

bit đầu vào sẽ làm thay đổi một nửa các khả năng có thể ở đầu ra.

3.1.3.2. Cấu trúc và ký hiệu

Quy ước ký hiệu: Theo cách mô tả thông thường các các hàm băm họ MD4

các thanh ghi được đánh ký hiệu là và các bước mã hóa được ký hiệu là:

Sau đó thuật toán được thiết lập theo kiểu “đầu tiên thực hiện ,

tiếp theo , tiếp theo …”. Điều này thuận lợi cho việc

thiết lập các thao tác với hiệu quả với các thanh ghi cố định.

Cấu trúc tổng quát: Cấu trúc tổng quát của họ MD4 rất đơn giản: thao tác chủ

yếu là phép cộng modulo. Các chuỗi cần công bao gồm giá trị của các thanh ghi,

giá trị từ thông báo , một vài hằng số và một giá trị tính được từ hàm

thực hiện trên 3 giá trị thanh ghi. Ngoài ra còn có thêm thao tác xoay bit.

Trong phần lớn các trường hợp giá trị và và hàm Boolean là độc lập

ở các bước hoặc các vòng. Một tính chất quan trọng trong các bước mã hóa đó là

chúng đều có tính song ánh, có nghĩa là bất kỳ hai trong số các giá trị

đều xác định giá trị thứ ba.

3.1.3.3. Các đặc điểm riêng

MD4. Thuật toán nén gồm 3 vòng mỗi vòng gồm 16 bước, tổng công có 48

bước. Các bước mã hóa nén trong MD4 được mô tả như sau:

Trong đó hàm Boolean và các hằng số trong các vòng là độc lập, còn

giá trị thay đổi sau mỗi bước nhưng theo quy luật sau:

MD5. Thiết kế của MD5 gần giống MD4. Nhưng các hàm ITE và XOR trong

MD4 được thay thế trong MD5 là ITEzxy và ONXxzy. Các bước mã hóa rất giống

MD4 nhưng có điểm khác là: sau bước xoay, có thêm một thanh ghi nữa:

(3.8)

Theo quan điểm mật mã học thì đây là điểm đáng quan tâm, nó làm tăng hiệu

ứng thác lũ. Một bước mã hóa của MD5 như Hình 3.2.

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

RIPEMD-128/ RIPEMD-160. Sự khác biệt quan trọng trong hàm nén của

RIPEMD là thông báo được xử lý song song hai luồng. Có nghĩa là ta có 2 tập 4

(trong RIPEMD-128) hoặc 5 (trong RIPEMD-160) các thanh ghi, chúng được khởi

tạo với cùng giá trị IV và được cập nhật trong cùng bước mã hóa, nhưng với các

hằng số khác nhau, số vòng xoay khác nhau và lịch trình thông báo khác nhau. Sau

khi xử lý xong các vòng mã hóa, kết quả cuối cùng ở hai luồng tính toán được kết

hợp với IV để cho ra mã băm đầu ra.

Các bước mã hóa của RIPE-128 giống với MD4 và RIPEMD-160, đều sử

dụng hàm sau đây:

(3.8)

RIPEMD-256/ RIPEMD-320. Các hàm mã hóa của hai hàm băm này gần

giống với RIPEMD-128 và RIPEMD-160. Chỉ có 2 điểm khác là: sự ảnh hưởng

giữa các luồng tính toán song song bị giới hạn sau mỗi vòng (mỗi lần tráo đổi 2

thanh ghi) và không kết hợp hai luồng ở vòng cuối nhằm mục đích tăng độ dài mã

băm lên 2 lần.

SHA-0/ SHA-1. Sự khác biệt lớn nhất giữa SHA-0 và SHA-1 so với MD- và

RIPEMD- là việc xoay bit được thực hiện chỉ trong một thanh ghi. Hàm là các

hàm ITE, MAJ và XOR, và có thêm một thanh ghi được cập nhật trong mỗi bước

quay, trong trường hợp này là 30 bit. Hàm mã hóa được mô tả như sau:

(3.9)

SHA-224/ SHA-256. Các hàm nén của hai hàm băm này giống hệt nhau,

ngoại trừ vector khởi tạo IV. Điều khác biệt duy nhất là khi tính một giá trị băm

cuối cùng thì SHA-224 chỉ lấy 224 bít tận cùng bên trái.

Điều này là để có sự đa dạng trong tiêu chuẩn về chiều dài của hàm băm, các

hàm băm thường là các khối trong các thủ tục bảo mật và chiều dài của mã băm sẽ

được quyết định bởi các thủ tục lận cận.

Hai hàm băm này hàm mã hóa có độ phức tạp tăng lên vì 2 cơ chế: sử dụng

nhiều thanh ghi hơn. Và sử dụng bước mã hóa phức tạp hơn.

Trong mỗi bước mã hóa không chỉ 1 thanh ghi mà 2 thanh ghi được cập nhật,

ta gọi là nội dung của thanh ghi được cập nhật ở bước thứ i.

Hai hàm phụ trong SHA-224/ SHA-256 được định nghĩa như sau:

Chúng làm tăng tính khuếch tán giữa các bit.

Bước mã hóa của SHA-224/ SHA-256 được mô tả như sau:

(3.10)

Trong đó là biến phụ được tính như sau:

(3.11)

Có điểm đáng chú ý là tất cả 64 bước của hàm nén đều dùng cùng hàm

Boolean và chỉ khác hằng số và khối thông báo .

Hai hàm băm này có độ phức tạp cao hơn, bước mã hóa tính toán chậm hơn

nhưng độ bảo mật tốt hơn.

SHA-384/ SHA-512. SHA-384 và SHA-512 tương tự như SHA-224 và SHA-

256: SHA-384 đơn thuần là phiên bản ngắn hơn SHA-512 và có IV khác. Như mô

tả ở trên hai hàm băm này sử dụng các từ 64 bit thay vì 32 bit, thuận lợi cho kiến

trúc máy tính 64 bit hiện đại. Bước mã hóa gần giống SHA-256 với một vài hằng

số được thay đổi để có độ dài từ lớn hơn (Xem phụ lục A).

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

Trên cơ sở đó phân tích các hàm băm ở trên ta nhận 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. Độ phức tạp của các hàm băm thể hiện

ở chỗ thuật toán băm trải qua nhiều bước và nhiều vòng, ví dụ trong họ MD4 như

nói ở trên quá trình băm bao gồm: mở rộng thông báo (hoán vị vòng hoặc dùng

hàm đệ quy), trong các vòng mã hóa các hàm nén sử dụng các phép toán như:

Boolean, cộng số nguyên theo modulo, xoay bit, dịch bit… Mã băm đầu ra là tổ

hợp của kết quả sau 1 quá trình tính toán với giá trị khởi tạo IV ban đầu.

Việc sử dụng CGP trên vành đa thức để xây dựng hệ mật như trong chương 2

thể hiện một số ưu điểm: cấu trúc đại số chặt chẽ, số lượng CGP 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ế), tốc độ tính toán nhanh.

Với những ưu điểm này trong phần này tác giả áp dụng hệ mật để xây dựng một

hàm băm đơn 128 bit, trong đó khối mã hóa thực hiện trên các CGP của vành đa

thức còn các khóa trong các vòng mã hóa được xây dựng từ các CGP của

vành đa thức có hai lớp kề cyclic.

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

Trong phần này tác giả đưa ra một phương pháp xây dựng hàm băm 128 bit

dựa trên các cấp số nhân cyclic của vành đa thức, với nền tảng là sơ đồ hàm băm

Matyas–Mayer–Oseas như Hình 3.3, đầu ra có độ dài 128 bit. Khối mật mã

trong sơ đồ này được xây dựng theo mô hình mạng hoán vị thay thế Feistel (như

trong Hình 2.4).

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

Hàm đượ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 là các

phần tử trong một cấp số nhân được chọn như sau [2], [11], [12]:

(3.12)

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

phần tử nguyên thủy của nhóm nhân cyclic có cấp bằng và cũng là một đa

thức có trọng số lẻ [2], [8].

Giả sử ta chọn khóa:

Phần tử đầu là .

Phần tử đầu của cấp số nhân và cũng là khóa đầu tiên là:

. (Chú ý giá trị là dạng biểu diễn số

mũ của đa thức). Sơ đồ khối bộ mã hóa như trong Hình 3.4. với khóa

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

Sơ đồ khối mã hóa f với khóa

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

(3.13)

Khối trong sơ đồ Hình 3.3 thực hiện việc trích chọn các khóa cho các vòng

tiếp theo của quá trình băm. Khối mật mã trong sơ đồ sử dụng các khóa có độ

dài 61 bit. Trong 61 bit khóa ở bước thứ do khối tạo ra thì 60 bit đầu tiên sẽ

được trích chọn từ 128 bit của 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 (trong khoảng bit

1 đến bit 120). 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.3 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 khởi tạo:

Phần tử sinh của khóa khởi tạo là đa thức:

;

Phần tử đầu phần tử đầu của cấp số nhân (khóa đầu tiên), cũng

là khóa khởi tạo sẽ là:

Khối bản tin đầu tiên được xây dựng như sau: Bản tin đầu tiên gồm 32 ký tự

dạng hexa (tương ứng 128 bit) được chọn là:

M1=0123456789ABCDEF0123456789ABCDEF

Các bản tin tiếp theo (từ 2 đến 10) được tạo một cách ngẫu nhiên.

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

Giá trị băm

Bản rõ

TT

0123456789ABCDEF 0123456789ABCDEF 2123456789ABCDEF 0123456789ABCDEF 0323456789ABCDEF 0123456789ABCDEF 0133456789ABCDEF 0123456789ABCDEF 012B456789ABCDEF 0123456789ABCDEF 0123056789ABCDEF 0123456789ABCDEF 0123476789ABCDEF 0123456789ABCDEF 0123457789ABCDEF 0123456789ABCDEF 0123456389ABCDEF 0123456789ABCDEF 0123456799ABCDEF 0123456789ABCDEF 012345678DABCDEF 0123456789ABCDEF 01234567898BCDEF 0123456789ABCDEF 0123456789AFCDEF 0123456789ABCDEF 0123456789AB8DEF 0123456789ABCDEF 0123456789ABC5EF 0123456789ABCDEF 0123456789ABCDFF 0123456789ABCDEF 0123456789ABCDEB 0123456789ABCDEF 0123456789ABCDEF 8123456789ABCDEF 0123456789ABCDEF 0323456789ABCDEF 0123456789ABCDEF 0133456789ABCDEF 0123456789ABCDEF 0121456789ABCDEF 0123456789ABCDEF 0123056789ABCDEF

4771249F4AB0E564 908F1456E0D3A239 7B13337D3B31DC7B 91287CE5FCDFD274 995F0EF13134BFAF D43A47B676DFA356 00EEA6CB284338F5 704DE9AFEC8A592C 0BC2CE7B57041014 0609BC377F579110 E1EDDCED0686C4F6 E1DACEE0AA906D52 09B62BF471BA9644 A9C64A47762FF6BD 0CA4992082D77070 73C61EA33CE5D66D 1E25F66DC86E2888 44CCBDC4367DA463 1AD3061B585D4602 FBEBA645F50D0203 E1589BF99823EF04 1210020DA32B4C50 1EE7BE47AC923862 90929EA7F6E837C1 BEB0D922F4ECAE48 CF098E0B9CCDF9CE AD5C0C8D0A61348B B96861BE92EEBB16 7906EF1395B4DE95 522E47E70DD5C738 FD4109489863FD3B 4E79C434BF8355DC C6DBEA49E116BEDC 1FF11DF8F7A44A3F BBE4AE6094334B90 49D253F55195427D BA79EFB1AF077CB5 1988B7580AEA44C1 22C2135FCD25DB6C BB0CE7ED5F43BEFE ADFA46A0CEC37C5A E0C53DAF31B45B8D A0A88D98F147A0D7 C4284C7EAF58BC1F

0123456789ABCDEF 0123416789ABCDEF 0123456789ABCDEF 0123457789ABCDEF 0123456789ABCDEF 0123456589ABCDEF 0123456789ABCDEF 0123456799ABCDEF 0123456789ABCDEF 012345678DABCDEF 0123456789ABCDEF 01234567892BCDEF 0123456789ABCDEF 0123456789AACDEF 0123456789ABCDEF 0123456789AB4DEF 0123456789ABCDEF 0123456789ABCCEF 0123456789ABCDEF 0123456789ABCDFF 0123456789ABCDEF 0123456789ABCDED

8DD5B3218D448641 313E52AD01747037 62F9919F4FF1A2AE 27C31BD6042FBB04 FF3D7A429626EF4E C61B8CF1325300F4 48CBABA51460CEF1 4ABFA6A62B4C006B A69350AB67BBCC6F 0053037523D9343F 36F0DCFCCF106D0F 76F938F7FBFBBE0C 4D16387FD0FA8E8A E12F2ED638A059FF 422DDC211E659AB0 C3D7A66C29F82331 8353E1BF4DB4264B 6D7007E1DFA73B51 7945A131C04B6182 ED6E54D50BE28723 5DA15DE212D18181 4813623B0E06F874

(Chú ý: Trong bảng 3.3 và bảng 3.4, các ký tự hexa in đậm chứa bit thay đổi).

Tiến hành thay đổi lần lượt từng bit từ bit 1 đến bit 128 của bản tin đầu

vào , tính khoảng cách Hamming của từng lần thay đổi, cuối

cùng tính được khoảng cách Hamming trung bình giữa các giá trị băm với giá trị

băm ban đầu là:

(3.14)

Bảng 3.4 là kết quả tính toán phân bố của bộ mã khi thay đổi khóa khởi tạo

, 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 [20].

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à:

Phần tử sinh khóa đầu tiên như sau:

( ).

Các khóa chỉ thay đổi 2 bit trong một số hexa của khóa đầu tiên .

Chú ý: vị trí các bit “1” trong các khóa tương ứng là số mũ của trong đa

thức sinh tạo khóa. Ví dụ:

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.

Khóa Ki

TT

Giá trị băm MDi

1 123456789ABCDEF1 53C51349140008F9AA66F954C307AD44

2 B23456789ABCDEF1 537140BB7C26F26EDD57CFDDA9CE1B8F

3 173456789ABCDEF1 2BA0259D1F16C021F3A22319AF753ED0

4 126456789ABCDEF1 A9FD04E4E1BAC7C06119B3FBD8FFD12D

5 123E56789ABCDEF1 773979064BE2FC31F0BE347B1EB2D776

6 1234F6789ABCDEF1 CD24285FFA002E865E8AECFACEAB37A5

7 12345C789ABCDEF1 12F25C639775234298EFF42CB48F44A8

8 123456289ABCDEF1 764025970C5F0A26A623D1A24B6D1809

9 1234567D9ABCDEF1 530804E85FA92A29C9D3B064481D81F4

10 123456780ABCDEF1 36188474DCE9230F7BFE8799EC1221C4

11 123456789FBCDEF1 633497CBED502E08B33AB54809D2DBE2

12 123456789AECDEF1 6756EEEBC53E948FE408A13DFF72AA20

13 123456789AB6DEF1 8778B1FBDE80A5DA4BEF05156D968B48

14 123456789ABC7EF1 18DA5D34CA879807D99ECDBC169ED8AD

15 123456789ABCDBF1 F9787D06F99822CB41E264158FF93D0C

16 123456789ABCDEA1 27395F8741475A8AA3845BB4FB6D0D0E

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

(3.15)

100

Để 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à từ bit 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

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:

(3.16)

Thực hiện lặp lại với 10 bản tin được tạo ngẫu nhiên khác nhau ta có kết quả

như Bảng 3.5.

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õ.

1 2 3 4 5 Bản tin thứ

63,27 63,67 64,23 64,67 64,50

6 7 8 9 10 Bản tin thứ

62,30 63,87 65,37 64,33 63,97

Khoảng cách Hamming trung bình tính được:

(3.17)

Qua các kết quả khảo sát khoảng cách Hamming ở trên ta thấy tính khuếch

tán của các hàm băm đề xuất là khá tốt.

Để tăng hiệu quả hàm băm ta có thể sử dụng các sơ đồ hàm băm kép với cách

xây dựng tương tự như đã trình bày ở trên.

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

Theo kết quả mô phỏng đánh giá độ khuếch tán của hàm băm đề xuất,

khoảng cách Hamming của các mã băm đạt xấp xỉ một nửa độ dài mã băm, tức là

khi ta thay 1 bit trong bản tin đầu vào thì mã băm đầu ra sẽ thay đổi một nửa chiều

dài. Từ đây ta thấy độ khuếch tán là rất tốt.

Để có thêm kết luận về hàm băm đề xuất, phải thực hiện thêm các đánh khác

như: tính xung đột, tính bảo mật…

101

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

Nội dung chương này đề cập đến các hàm băm hộ MD4, đây là họ có nhiều

hàm băm đang được sử dụng rộng rãi. Phần tiếp theo là đề xuất xây dựng một hàm

băm mới 128 bit, với mục đích tăng độ dài hàm băm hạn chế phép tấn công ngày

sinh nhật; các mô phỏng đánh giá độ khuếch tán của hàm băm mới đề xuất này cho

thấy kết quả rất khả quan.

102

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

Các kết quả nghiên cứu chính của luận án bao gồm các nội dung sau đây:

 Đề xuất phương pháp xây dựng hệ mật trên các cấp số nhân cyclic của vành đa

thức. Hệ mật mới này được xây dựng theo lược đồ Feistel có sửa đổi với sơ đồ

mật mã khối có độ dài đầu ra 128 bit. Ưu điểm nổi bật của hệ mật này là (1)

Mạch điện mã hóa và giải mã cùng một cấu trúc và rất đơn giản chỉ gồm các

thanh ghi dịch và bộ cộng modul 2, tốc độ xử lý nhanh, (2) Phương pháp mã

hóa hàm được xây dựng trên cấu trúc của cấp số nhân cyclic trên vành đa

thức với , (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 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 ( khóa) nên mỗi lần mã hóa một khối

thông tin vào, có thể sử dụng các khóa khác, điều này sẽ tránh được vấn đề của

các mật mã khối là khi 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,

103

(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ỉ một nửa độ dài mã băm.

Kiến nghị hướng phát triển

 Phát triển thêm các hệ mật mã mới trên cơ sở hàm mã hóa xây dựng từ các cấp

số nhân cyclic và kết hợp thêm các khâu phi tuyến để tăng độ an toàn cho hệ

mật.

 Trên cơ sở hàm băm đề xuất trong luận án, xây dựng thêm các hàm băm mới

có độ dài lớn hơn.

 Tìm hiểu và thực hiện thêm các phương pháp đánh giá hàm băm đề xuất để

hoàn thiện nghiên cứu về hàm băm mới này.

 Nghiên cứu, thiết kế và thử nghiệm mạch điện phần cứng cho hệ mật đề xuất.

104

DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN

ĐẾN LUẬN ÁN

[1]. Nguyễn Bình,Vương Đức Hạnh, Hồ Quang Bửu “Quasi–cyclic Codes over Polynomial Rings withTwo Cyclotomic Cosets”, Tạp chí Khoa học và Công nghệ, Viện Khoa học và Công nghệ Việt Nam, chuyên san các công trình về điện tử viễn thông và CNTT, tập 1, số 1 năm 2010 trang 77-81.

[2]. Hồ Quang Bửu, Trần Đức Sự, “Constructing Interleaved M-sequences over Polynomial Rings with Two Cyclotomic Cosets”, Tạp chí Khoa học và Công nghệ Quân sự, số 47, 02 -2012, trang 133-140.

[3]. Hồ Quang Bửu, Ngô Đức Thiện, Trần Đức Sự, “Xây dựng hệ mật trên các cấp số nhân cyclic của vành đa thức”, Tạp chí Khoa học và Công nghệ, Viện Khoa học và Công nghệ Việt Nam, Chuyên san các công trình nghiên cứu về Điện tử, Viễn thông và CNTT, Tập 50 số 2A, tháng 9-2012, ISSN 0866 708X.

[4]. Hồ Quang Bửu, Ngô Đức Thiện, Trần Đức Sự, “Xây dựng hàm băm trên các cấp số nhân cyclic”, Chuyên san các công trình nghiên cứu, phát triển và ứng dụng CNTT và Truyền thông, Kỳ 3 Tạp chí Thông tin, KHCN của bộ Thông tin và Truyền thông, Tập V-1 số 7 (27), tháng 5-2012, ISSN 1859-3526.

[5]. Nguyễn Toàn Thắng, Ngô Đức Thiện, Hồ Quang Bửu, “Xây dựng hàm băm mở rộng trên các cấp số nhân cyclic”, Hội thảo Điện tử - Truyền thông An toàn thông tin, ATC/REV, tháng 10- 2012, pp. 52 - 57.

[6]. Hồ Quang Bửu, đề tài khoa học cấp bộ TT&TT: “Nghiên cứu thực trạng và khả năng triển khai ứng dụng xác thực cổng thông tin điện tử”. Mã số: 125- 10-KHKT-RD, ban hành theo quyết định số: 234/QĐ-BTTTT ngày 10/2/2010.

105

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1]. Bùi Lai An, (2012), “Về một cấu trúc tổng quát của mã PN phi tuyến đa

chiều đa cấp theo kiểu lồng ghép”, Luận án tiến sĩ kỹ thuật, 2012.

[2]. Đặng Hoài Bắc, (2010) “Các mã cyclic và cyclic cục bộ trên vành đa thức có

hai lớp kề cyclic”, Luận án TS kỹ thuật.

[3]. Nguyễn Bình (2004), "Nghiên cứu xây dựng hạ tầng khóa công khai phục vụ thư tín điện tử và thương mại điện tử”, Báo các kết quả nghiên cứu đề tài Bộ Bưu chính - Viễn thông, 6/2004.

[4]. Nguyễn Bình (2004), Giáo trình Mật mã học, Học viện Công nghệ Bưu

chính Viễn thông, Nxb Bưu điện, 2004.

[5]. Nguyễn Bình (2008), Giáo trình Lý thuyết thông tin, Học viện Công nghệ

Bưu chính Viễn thông, Nxb Bưu điện, 2008.

[6]. Lê Đình Thích (2002), Nghiên cứu các mã xyclic cục bộ trên vành đa thức,

Luận án Tiến sĩ kỹ thuật.

Tiếng Anh

[7]. Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh, Young Hoon Kim (2007), “Polynomial rings with two cyclotomic cosets and their applications in Communication”, MMU International Symposium on Information and Communications Technologies 2007, Malaysia, ISBN: 983-43160-0-3.

[8]. Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh (2007), “Decomposition in polynomial ring with with two cyclotomic cosets”, 36th AIC, November 18-23 2007, Manila.

[9]. Nguyen Binh, Dang Hoai Bac (2004), “Cyclic Codes over Extended Rings of

Polynomial Rings with Two Cyclotomic Cosets”, REV’04, Vietnam.

[10]. Nguyen Binh, Le Dinh Thich (2002), “The Oders of Polynomials and Algorithms for Defining Oder of Polynomial over Polynomial Ring”, VICA- 5, Hanoi, Vietnam.

106

[11]. Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh (2007), "Novel Algebraic Structure for Cyclic Codes", Applied Algebra, Algebraic Algorithms, and Error Correcting Codes –Conf., AAECC 17, LNCS 4851, pp 301-310, Springer-Verlag Berlin Heidelberg.

for Cryptography"

[12]. Dang Hoai Bac, Nguyen Binh, Nguyen Xuan Quynh (2007), "New Algebraic Structure Based on Cyclic Geometric Progressions over Polynomial Ring International Conference on IEEE, Applied Computational Intelligence and Security (CIS) CIS'07, December 15-19, 2007, Harbin, China.

[13]. Nguyen Binh (2002), “Crypto-System Based on Cyclic Geometric

Progressions over Polynomial Ring (Part I)”, REV’02, Vietnam.

[14]. Nguyen Binh (2002), “Circulant Crypto System over Polynomial Ring

(Part II)”, REV’02, Vietnam.

[15]. Bart PRENEEL (2003), “Analysis and Design of Cryptographic Hash

Functions”, Ph.D project, February 2003.

[16]. Bellovir S., Merritt M. (1992), “Encrypted Key Exchange”, Proc. IEEE

Symp. Security and Privacy IEEE Comp Soc Press 1992.

[17]. Denning D., Branstad D. (1996), “A Taxonomy of Key Escrow Ecryption

Systems”, Comm ACM, v39 n3, Mar 1996.

[18]. Hamming R. W. (1980), Coding and Information Theory, Englwood Cliffs,

N.J Prentice Hall.

[19]. Huth M. R. A. (2001), Secure Communication Systems, Cambridge

University Press, 2001.

[20]. Jean-Yves Chouinard (2002), ELG 5373 Secure Communications and Data Encryption, School of Information Technology and Engineering, University of Ottawa, April 2002.

[21]. John B. Anderson and Seshadri Mohan, (1991), Source and Channel Coding,

Kluwer Academic Publishers, Boston/Dordrecht/London.

[22]. Knudsen, L.; Preneel, B (2002), 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

107

[23]. Magnus Daum (2005), “Cryptanalysis of Hash Functions of the MD4- Family”, Dissertation zur Erlangung des Grades eines Doktor der Naturwissenschaften der Ruhr-UniversitÄat Bochum am Fachbereich Mathematik vorgelegt von Magnus Daum unter der Betreuung von Prof. Dr. Hans Dobbertin Bochum, Mai 2005.

[24]. Markku-Juhani Olavi Saarinen (2009), “Cryptanalysis of Dedicated Crypto- graphic Hash Functions”, Thesis submitted to The University of London for the degree of Doctor of Philosophy. Department of Mathematics Royal Holloway, University of London, 2009.

[25]. Menezes A. J, Van Oorchot P. C. (1998), Handbook of Applied

Cryptography, CRC Press, (1998).

[26]. Michal Rjaˇ sko (2008), “Properties of Cryptographic Hash Functions”, Comenius University in Bratislava, Faculty of Mathematics, Physics and Informatics Department of Computer Science, Advisor: RNDr. Martin Stanek, PhD. Bratislava 2008.

[27]. Paul J. McCarthy (1996), Algebraic Extensions of Fields, Blaisdell

Publishing Company.

[28]. Pascal JUNOD (2004), “Statiscal Cryptanalysis of Block Ciphers”, Thèse No 3179 (2004), Présentée à La Faculté Informatique & Communications, Institud de Systèmes de Communications.

[29]. Preneel, B.; Govaerts, R.; Vandewalle, J., “Hash functions for information authentication”, CompEuro'92. Computer Systems and Software En- gineering', Proceedings. 4-8 May 1992 Page(s):475 – 480.

[30]. Rudolf Lidl, Harald Neiderreiter (1983), Finite Fields, Addision-Wesley

Publishing Company.

[31]. Schneier B. (1996), Applied Cryptography, John Wiley Press, 1996.

[32]. Stallings W. (2000), “Networks Security Essentials: Applications and

Standards”, Prentice Hall, (2000).

[33]. Stinson D. R. (1995), Cryptography: Theory and Practice, CRC Press, 1995.

[34]. Shamir A. (1985), “Identity-based cryptorytions and signature schemes, Advanced in Cryptology” - CRYPTO'84, LNCS196, Springer_Verlag, pp.47-53, 1985

108

[35]. Shannon C. E. (1948), A mathematical theory of communication, Bell Syst

Tech J.

[36]. Todd K. Moon (2005), Error Correction Coding, Wiley-Interscience, a John

Wiley & Sons, Inc., Publication.

Joint Conference of the

[37]. Message authentication with one-way hash functions, INFOCOM’92. Eleventh Annual IEEE Computer and Communications Societies. IEEE, 4-8 May 1992 Page(s): 2055 - 2059 vol.3.

109

PHỤ LỤC A:

THÔNG SỐ CỦA MỘT SỐ HÀM BĂM

Phụ lục này trình bày các thông số của các hàm nén sử dụng trong các hàm

băm họ MD4.

Với mỗi hàm, đầu tiên là các mô tả về các thông số, ví dụ độ dài mã băm đầu

ra , độ dài đầu ra hàm nén , số lượng các thanh ghi , số bước mã hóa , độ

dài của một từ , số lượng các từ thông báo được tách từ thông báo ban đầu có

chiều dài .

Khi mô tả mở rộng thông báo, có các phép hoán vị khác nhau nếu phép

mở rộng theo kiểu hoán vị vòng, còn nếu mở rộng theo kiểu đệ quy thì sử dụng .

Khi mô tả các bước mã hóa sử dụng các công thức cho bước mã hóa, ví dụ

tính từ cùng với các bảng các phần của các bước độc lập.

Một số hàm có thay đổi nhỏ trong các thanh ghi khác với tính toán theo công

thức đa cho, sử dụng ký hiệu để mô tả giá trị thực tế của thanh ghi sau

bước , và được gọi là trạng thái.

Trong trường hợp tính toán song song hai luồng, ký hiệu là cho luồng

bên trái và là cho luồng bên phải. Các giá trị khởi tạo ký hiệu là .

110

MD4

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

111

MD5

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

112

MD4 mở rộng

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

113

RIPEMD-0

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

114

RIPEMD-128

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

115

RIPEMD-160

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

116

RIPEMD-256 Giống RIPEMD-128

Các thông số:

Giá trị khởi tạo:

Bước mã hóa:

dung tương ứng). bằng bằng bằng (và , ,

Giống RIPE-128: Sau bước 15 (và các bước 31, 47, 63 tương ứng) thay nội bằng

Đầu ra:

RIPEMD-320 Giống RIPEMD-160

Các thông số:

Giá trị khởi tạo:

Bước mã hóa:

Giống RIPE-160: Sau bước 15 (và các bước 31, 47, 63, 79 tương ứng) thay bằng bằng bằng bằng bằng (và , , , nội dung

tương ứng).

Đầu ra:

117

SHA-0 và SHA-1

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

118

SHA-256

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

Trạng thái:

Đầu ra:

119

SHA-512

Các thông số:

Mở rộng thông báo:

Giá trị khởi tạo:

Bước mã hóa:

120

Trạng thái:

Đầu ra:

SHA-224

SHA-224 giống với SHA-256

Các thông số:

Giá trị khởi tạo:

Đầu ra:

Đầu ra hàm nén giống SHA-256, nhưng đầu ra hàm băm chỉ lấy 224 bit.

121

SHA-384

SHA-384 giống với SHA-512

Các thông số:

Giá trị khởi tạo:

Đầu ra:

122

PHỤ LỤC B:

CÁC CHƯƠNG TRÌNH TÍNH TOÁN VÀ MÔ PHỎNG

1. Hàm tính hoán vị IP và IP-1 128 bit

function A=IP128(ax,flag)

% Hoan vi va hoan vi nguoc 128 bit

% Cu phap: A = IP128(AX,FLAG)

% AX 128 bit thong tin vao

% A 128 bit thong tin ra

% FLAG = 1 --> Hoan vi thuan

% FLAG = -1 --> Hoan vi nguoc

IP= [[122:-8:2]

[124:-8:4]

[126:-8:6]

[128:-8:8]

[121:-8:1]

[123:-8:3]

[125:-8:5]

[127:-8:7]];

IPI = [[80:-1:65]

[16:-1:1]

[96:-1:81]

[32:-1:17]

[112:-1:97]

[48:-1:33]

[128:-1:113]

[64:-1:49]];

IP = reshape(IP',1,128);

IPI = reshape(IPI,1,128);

switch flag

case 1

for ii=1:128

A(ii)=ax(IP(ii));

end

case -1

for ii=1:128

A(ii)=ax(IPI(ii));

end

otherwise

A='Khong hop le';

return;

end

% ---------- end of file ----------

123

2. Hàm tính các phần tử của cấp số nhân cyclic trên vành có 2 lớp kề

function ketquabin = CGP2LK(ax,px,s,n);

% tim cap so nhan cho vanh co 2 lop ke Cyclic

% cu phap: KQBIN = CGP2LK(ax,px,s,n);

% ax la da thuc dau, dang BIN

% px la cong boi,dang BIN

% KQBIN --> ket qua dang BIN

% s --> so phan tu

% n --> vanh da thuc X^n + 1 (n la so nguyen to)

%--------------------------------

ax(length(ax)+1:n)=0;

px(length(px)+1:n)=0;

kq=nhandathuc(ax,px,n);

%--------------------------

for jj=2:s

tg=nhandathuc(kq(jj-1,:),px,n);

kq=[kq;tg];

end

ketquabin=kq;

% ---------- end of file ------------------------

124

+ Hàm nhân hai đa thức dạng nhị phân

function kq= nhandathuc(x,y,n);

% Cu phap KQ = NHANDATHUC(X,Y,n);

% X, Y la vec to nhi phan, la he so cua da thuc.

% KQ --> ket qua dang BINVEC

% n --> vanh da thuc: X^n + 1

dx=length(x);

dy=length(y);

if dx <= n

x((dx+1):n)=0;

else

disp('Do dai vuot qua n');

kq=[];

return;

end

if dy <= n

y((dy+1):n)=0;

else

disp('Do dai vuot qua n');

kq=[];

return;

end;

somu=0;

tg=[];

for jj=1:dx

if x(jj)==1

somu=somu+1;

tg(somu,:)=shift(y,jj-1);

end

stg=size(tg);

if stg(1)==1

kq=tg;

else

kq=sum(tg);

kq=mod(kq,2);

end

125

+ Hàm chuyển đổi đa thức dạng số mũ sang dạng nhị phân

function kq=pol2bin(ax);

% Chuyen tu so mu da thuc ax thanh dang vecto nhi phan

% Cu phap: KQ= POL2BIN(ax);

% AX: la da thuc dang POL,

% n: Vanh da thuc X^n+1;

% KQ la da thuc dang BINVEC

m=max(ax);

kq=zeros(1,m+1);

for jj=1:length(ax)

vt=ax(jj);

kq(vt+1)=1;

end

126

3. Hàm tính các phần tử của cấp số nhân cyclic trên vành

function ketquabin = CGPC(ax,px,n);

% Tim cap so nhan cho vanh chan dang: X^n+1 Voi n=2^k

% cu phap: KQBIN = CGPC(ax,px,n);

% ax la da thuc dau, dang BIN

% px la cong boi,dang BIN

% KQBIN --> ket qua dang BIN

%--------------------------------

ax(length(ax)+1:n)=0;

px(length(px)+1:n)=0;

kq=ax;

%--------------------------

for jj=2:n

tg=nhandathuc(kq(jj-1,:),px,n);

kq=[kq;tg];

end

ketquabin=kq;

% ---------- end of file ------------------------

% Xay dung he mat DES tren cac cap so nhan cyclic

% He mat xay dung cho chuoi 128 bit theo so do Feistel

% Phep hoan vi va hoan vi dao lay theo tieu chuan DES

% Khoa K la nhom nhan xay dung tren vanh X^61+1,

% voi phan tu sinh la kx

% Qua trinh ma hoa va giai ma trai qua 16 buoc theo tieu chuan DES

%---------- Chuan bi du lieu -------------------------

clear;

nmsg = 1; % So chuoi 128 bit thong tin can mo phong = so bo khoa

4. Chương trình mã hóa hệ mật đề xuất

msg=[];

for ii=0:15

tg=dec2binvec(ii,4);

msg=[msg;tg];

end

msg=[msg;msg];

msg=reshape(msg',1,128);

fprintf('Ban ro dau vao: M = %s\n',bin2hex(msg));

%----------- Tinh toan khoa K-----------------------------

nK = nmsg*16; % Tong so khoa

Ki=pol2bin( [0 10 30 40 50 ]); % Phan tu sinh cua khoa

Ka=pol2bin([0 1 3]);

K = cgp2lk(Ka,Ki,nK,61); % Tap cac khoa (CGP tren Vanh X^61+1)

%&&&&&&&&&&&&&&&&& Qua trinh ma hoa &&&&&&&&&&&&&&&&&&&&&&

for ii=1:nmsg

%------------- Hoan vi khoi dau------------------------

M0 = IP128(msg,1); % Hoan vi khoi dau

L(1,:) = M0(1:64); % Nua trai L0

R(1,:) = M0(65:128); % Nua phai R0.

Fk=[];

%------- 16 buoc mat ma --------------------------------

for jj = 1:16

L(jj+1,:)=R(jj,:);

ttk = 16*(ii-1); % Thu tu bo khoa dung cho moi vong

AK = cgpc(K(ttk+jj,:),[0 1],64); % Ma tran A cua khoa thu jj

AK=AK'; % Hoan vi ma tran A

F=R(jj,:)*AK; % Nua phai sau khi nhan voi khoa

R(jj+1,:) = mod(L(jj,:)+F,2); % Nua phai sau buoc jj

end

L16 = L(17,:); % Nua trai sau buoc 16

R16 = R(17,:); % Nua phai sau buoc 16

127

%------- Hoan vi dao ------------------------

C16 = [L16 R16];

C = IP128(C16,-1); % Du lieu ra

end

% &&&&&&&&&& End of file &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

128

5. Chương trình tính toán hàm băm đề xuất

function MD=bamcgp(x,Ka,Ki)

% Thuc hien ham bam theo so do Matyas-Meyer-Oseas

% Cu phap: MD = bamcgp(msg,Ka,Ki)

% MD: Dau ra ma bam 128 bit

% msg: Ban tin ro dau vao

% Ka: Phan tu dau cua cap so nhan tao khoa dau tien

% Ki: Phan tu sinh cua cap so nhan tao khoa dau tien

%------- Tao cac khoi n bit cua dau vao x-------------

msg=x;

sox = length(msg);

while mod(sox,128)~=0

msg=[msg 0]; % Chen them bit "0" cho du chieu dai 128 bit

sox=length(msg);

end

if sox == 128

flag=0;

msg(129:256)=zeros(1,128);

else

flag=1;

end

t=length(msg)/128;

msg=reshape(msg,128,t); % Chia thanh cac khoi 128 bit

msg=msg';

%------------ Tinh toan buoc dau tien -------------------

K = cgp2lk(Ka,Ki,16,61); % Tao tap khoa dau

M = IP128(msg(1,:),1); % Hoan vi khoi dau

L(1,:) = M(1:64); % Nua trai L0

R(1,:) = M(65:128); % Nua phai R0.

%------- 16 buoc mat ma khoi --------------------------------

for jj = 1:16

L(jj+1,:)=R(jj,:);

L(jj+1,1:61)=mod(L(jj+1,1:61)+K(jj,:),2); % Nhan nua phai voi Ki

AK = cgpc(K(jj,:),[0 1],64); % Ma tran A cua khoa thu jj

AK=AK'; % Hoan vi ma tran A

F=R(jj,:)*AK; % Nua phai sau khi nhan voi khoa

R(jj+1,:) = mod(L(jj,:)+F,2); % Nua phai sau buoc jj

end

L16 = L(17,:); % Nua trai sau buoc 16

R16 = R(17,:); % Nua phai sau buoc 16

E = IP128([L16 R16],-1); % Hoan vi dao - Du lieu bam sau buoc 1

%-------- tao khoa cho buoc tiep theo ----------------

Htg = xor(msg(1,:),E); % E + msg

Ktg=Htg(1:2:120); % Lay 60 bit

Wk=mod(sum(Ktg),2); % Kiem tra tinh chan le

if Wk==1

H(1,:)=[Ktg 0]; % trong so le --> bit 61 = 0

else

H(1,:)=[Ktg 1]; % trong so chan --> bit 61 = 1

end

% ------------------- Cac buoc tiep theo -------------------

for ii=1:t-1

K=cgp2lk(Ka,H(ii,:),16,61); % Tao khoa

M = IP128(msg(ii+1,:),1); % Hoan vi khoi dau

L(1,:) = M(1:64); % Nua trai L0

129

R(1,:) = M(65:128); % Nua phai R0.

%------- 16 buoc mat ma khoi --------------------------------

for jj = 1:16

L(jj+1,:)=R(jj,:);

L(jj+1,1:61)=mod(L(jj+1,1:61)+K(jj,:),2); % Nhan nua phai voi Ki

AK = cgpc(K(jj,:),[0 1],64); % Ma tran A cua khoa thu jj

AK=AK'; % Hoan vi ma tran A

F=R(jj,:)*AK; % Nua phai sau khi nhan voi khoa

R(jj+1,:) = mod(L(jj,:)+F,2); % Nua phai sau buoc jj

end

L16 = L(17,:); % Nua trai sau buoc 16

R16 = R(17,:); % Nua phai sau buoc 16

Ei = IP128([L16 R16],-1); % Hoan vi dao - Du lieu bam sau buoc ii

%-------- tao khoa cho buoc tiep theo ----------------

Htg = xor(msg(ii+1,:),Ei); % E + msg

Ktg=Htg(1:2:120); % Lay 60 bit

Wk=mod(sum(Ktg),2); % Kiem tra tinh chan le

if Wk==1

H(ii+1,:)=[Ktg 0]; % trong so le --> bit 61 = 0

else

H(ii+1,:)=[Ktg 1]; % trong so chan --> bit 61 = 1

end

% ------------------- Gia tri bam cuoi cung -------------------

switch flag

case 0

MD=E;

case 1

MD=Ei;

otherwise

MD='Khong xac dinh';

130

End

% ----------- end of file ----------------

131

%---------- Chuan bi du lieu -------------------------

clear;

nmsg = 10; % So chuoi 128 bit thong tin can tinh = so bo khoa

msg=[];

for ii=0:15

tg=dec2binvec(ii,4);

msg=[msg;tg];

end

msg=[msg;msg];

msg=msg';

msg(1,:)=reshape(msg,1,128); %msg1: 0123456789ABCDEF0123456789ABCDEF

for jj=2:10

msg(jj,:) = rand(1,128);

end;

%----------- Tinh toan khoa K-----------------------------

nK = nmsg*16; % Tong so khoa

Ki=pol2bin([ 0 1 3 7 9]); % Phan tu sinh cua khoa

Ka=pol2bin([0 1 2]); % Phan tu dau cua cap so nhan K

%--------- Ma hoa ban tin dau tien ---------------

E1=descgp(msg(1,:),Ka,Ki); % Ma ra khi chua thay bit du lieu

msc=msg; % du lieu vao ban dau

disp('Ket qua khi thay doi 1 bit du lieu');

disp(' Thu tu Ban ro Ban ma K/C Hamming');

msghex=bin2hex(msg(1,:));

Cihex=bin2hex(E1);

fprintf('%5d %45s %45s %15d\n',0,msghex,Cihex,0);

6. Chương trình tính toán độ khuếch tán của hàm băm đề xuất

sohm=0; % Tinh khoang cach Hamming

% thay doi 1 bit thong tin dau vao va tinh gia tri bam

for p=0:31

msg=msc;

vt=round(4*rand(1)); % Thay doi ngau nhien 1 bit cua 1 so HEX

if vt==0

vt=1;

end

posit=p*4+vt; %Vi tri bit thay doi

msg(1,posit)=xor(msg(1,posit),[1]);

%------------------------------------------

E=descgp(msg,Ka,Ki);

hm=sum(xor(E1,E)); % Tinh so bit sai khac, khoang cach Hamming

%********************** Hien thi ket qua ***************************

msghex=bin2hex(msg);

Cihex= bin2hex(E);

fprintf('%5d %45s %45s %15d\n',p+1,msghex,Cihex,hm);

sohm=sohm+hm;

end

fprintf('Khoang cach Hamming trung binh: %6.2f\n',sohm/32);

%--------------- End of file ---------------------------------------

132

Luận án Tiến sĩ Kỹ thuật viễn thống: 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

Tags: