Luận án 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

 i 
LỜI CAM ĐOAN 
Tôi xin cam đoan đây là công trình nghiên cứu của tôi, các số liệu và 
kết quả trình bày trong luận án là trung thực và chưa được công bố ở bất kỳ 
công trình nào khác. 
 Tác giả 
 Hồ Quang Bửu 
 ii 
LỜI CẢM ƠN 
Luận án Tiến sĩ kỹ thuật này được thực hiện tại Học viện Công nghệ Bưu 
chính Viễn thông. Tác giả xin tỏ lòng biết ơn đến thầy giáo GS.TSKH. Nguyễn 
Xuân Quỳnh đã trực tiếp định hướng, tạo mọi điều kiện trong suốt quá trình 
nghiên cứu. Tác giả cũng xin cảm ơn GS.TS. Nguyễn Bình đã trực tiếp hướng dẫn 
học thuật hóa, kiểm tra những kết quả của các công trình nghiên cứu. 
Tôi xin chân thành cảm ơn Lãnh đạo Học viện Công nghệ Bưu chính Viễn 
thông đã tạo những điều kiện thuận lợi để hoàn thành và bảo vệ luận án trong thời 
gian nghiên cứu của nghiên cứu sinh. Tôi xin cảm ơn khoa Quốc tế và Đào tạo sau 
đại học, Sở Thông tin truyền thông tỉnh Quảng Nam (nơi tôi đang công tác), cũng 
như các đồng nghiệp đã tạo điều kiện và giúp đỡ tôi hoàn thành được đề tài nghiên 
cứu của mình. 
Cuối cùng là sự biết ơn tới gia đình, bạn bè đã thông cảm, động viên giúp đỡ 
cho tôi có đủ nghị lực để hoàn thành luận án. 
 Hà nội, tháng 12 năm 2013 
 iii 
MỤC LỤC 
LỜI CAM ĐOAN ...................................................................................................... i 
LỜI CẢM ƠN .......................................................................................................... ii 
MỤC LỤC ...............................................................................................................iii 
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT ............................................. vi 
DANH MỤC CÁC BẢNG ....................................................................................viii 
DANH MỤC CÁC HÌNH VẼ ................................................................................. ix 
PHẦN MỞ ĐẦU ...................................................................................................... 1 
1. MỞ ĐẦU ....................................................................................................... 1 
2. TÌNH HÌNH NGHIÊN CỨU ......................................................................... 1 
3. LÝ DO CHỌN ĐỀ TÀI ................................................................................. 4 
4. MỤC TIÊU NGHIÊN CỨU .......................................................................... 4 
5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU .................................................... 5 
6. PHƯƠNG PHÁP NGHIÊN CỨU ................................................................. 5 
7. Ý NGHĨA KHOA HỌC VÀ THỰC TIÊN CỦA ĐỀ TÀI ............................ 5 
CHƯƠNG 1. TỔNG QUAN VỀ MẬT MÃ HỌC .................................................. 6 
1.1. CÁC KHÁI NIỆM CƠ BẢN ......................................................................... 6 
1.2. CÁC HỆ MẬT KHÓA BÍ MẬT .................................................................... 8 
1.2.1. Sơ đồ khối chức năng hệ mật khóa bí mật .................................... 8 
1.2.2. Các hệ mật thay thế ....................................................................... 8 
1.2.3. Các hệ mật hoán vị (MHV) ......................................................... 11 
1.2.4. Các hệ mật mã tích ...................................................................... 12 
1.2.5. Các hệ mật mã dòng và việc tạo các dãy giả ngẫu nhiên ............ 15 
1.2.6. Chuẩn mã dữ liệu DES ................................................................ 26 
1.2.7. Ưu nhược điểm của mật mã khóa bí mật ..................................... 29 
 iv 
1.3. HỆ MẬT KHÓA CÔNG KHAI ................................................................... 30 
1.3.1. Sơ đồ chức năng .......................................................................... 30 
1.3.2. Một số bài toán xây dựng hệ mật khóa công khai ....................... 31 
1.4. CƠ BẢN VỀ HÀM BĂM ............................................................................ 33 
1.4.1. Mở đầu ......................................................................................... 33 
1.4.2. Các định nghĩa và tính chất cơ bản.............................................. 35 
1.4.3. Một số phương pháp xây dựng hàm băm .................................... 37 
1.4.4. Các loại tấn công hàm băm cơ bản .............................................. 41 
1.4.5. Độ an toàn mục tiêu ..................................................................... 43 
1.5. TÍNH TOÀN VẸN CỦA DỮ LIỆU VÀ XÁC THỰC THÔNG BÁO........ 44 
1.5.1. Các phương pháp kiểm tra tính toàn vẹn dữ liệu ........................ 44 
1.5.2. Chữ ký số ..................................................................................... 46 
1.6. KẾT LUẬN CHƯƠNG 1............................................................................. 49 
CHƯƠNG 2. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC .. 50 
2.1. NHÓM NHÂN CYCLIC TRÊN VÀNH ĐA THỨC .................................. 50 
2.1.1. Định nghĩa nhóm nhân cyclic trên vành đa thức ......................... 50 
2.1.2. Các loại nhóm nhân cyclic trên vành đa thức.............................. 52 
2.2. CẤP SỐ NHÂN CYCLIC TRÊN VÀNH ĐA THỨC ................................. 54 
2.2.1. Khái niệm về cấp số nhân cyclic trên vành đa thức .................... 54 
2.2.2. Phân hoạch vành đa thức ............................................................. 55 
2.3. XÂY DỰNG M-DÃY LỒNG GHÉP TRÊN VÀNH ĐA THỨC CÓ HAI 
LỚP KỀ CYCLIC ....................................................................................... 61 
2.3.1. Vành đa thức có hai lớp kề .......................................................... 61 
2.3.2. M-dãy xây dựng trên vành đa thức .............................................. 63 
2.3.3. Xây dựng M-dãy lồng ghép từ các cấp số nhân cyclic trên vành 
đa thức có hai lớp kề ...................................................................................... 64 
 v 
2.4. HỆ MẬT XÂY DỰNG TRÊN CÁC CẤP SỐ NHÂN CYCLIC ................ 71 
2.4.1. Vấn đề mã hóa ............................................................................. 71 
2.4.2. Xây dựng hệ mật dùng cấp số nhân cyclic .................................. 76 
2.5. KẾT LUẬN CHƯƠNG 2 ............................................................... 82 
CHƯƠNG 3. HÀM BĂM XÂY DỰNG TRÊN CẤP SỐ NHÂN CYCLIC ....... 83 
3.1. CÁC HÀM BĂM HỌ MD4 ........................................................... 83 
3.1.1. Cấu trúc........................................................................................ 83 
3.1.2. Mở rộng thông báo ...................................................................... 87 
3.1.3. Các bước mã hóa ......................................................................... 89 
3.2. XÂY DỰNG HÀM BĂM MỚI TRÊN CÁC CẤP SỐ NHÂN CYCLIC ... 94 
3.2.1. Sơ đồ khối mật mã trong hàm băm.............................................. 94 
3.2.2. Các đánh giá kết quả mô phỏng hàm băm mới ......................... 100 
3.3. KẾT LUẬN CHƯƠNG 3........................................................................... 101 
KẾT LUẬN VÀ KIẾN NGHỊ .............................................................................. 102 
DANH MỤC CÁC CÔNG TRÌNH CÓ LIÊN QUAN ĐẾN LUẬN ÁN ........... 104 
TÀI LIỆU THAM KHẢO .................................................................................... 105 
PHỤ LỤC A: THÔNG SỐ CỦA MỘT SỐ HÀM BĂM .................................... 109 
PHỤ LỤC B: CÁC CHƯƠNG TRÌNH TÍNH TOÁN VÀ MÔ PHỎNG ........... 122 
 vi 
DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT 
AES Advanced Encryption Standard 
ANSI American National Standards Institute 
CAST Carlisle Adams and Stafford Tavares 
CBC Cipher Block Chaining 
CFB Cipher Feedback Block 
CGP Cấp số nhân cyclic (Cyclic Geometic Progressions) 
CMG Nhóm nhân cyclic (Cyclic Multiplicate Group) 
CRC Cyclic Redundancy Check 
CRF Collision Resistant Function 
CRHF Collision Resistant Hash Function 
S
C Chu trình 
0
d Khoảng cách Hamming 
deg Bậc của đa thức (Degree) 
DEA Data Encryption Algorithm 
DES Chuẩn mã dữ liệu (Data Encryption Standard) 
( )e x Đa thức lũy đẳng 
ECB Electronic Codebook 
F Trường (Field) 
G Nhóm (Group) 
GF(p) Trường đặc số p 
h Hàm băm (Hash) 
I Ideal 
IDEA International Data Encryption Algorithm 
IV Initial Value 
MAC Message Authentication Code 
MDC Manipulation Detection Code 
MD-x Message Digest x 
NESSIE New European Schemes for Signatures, Integrity 
and Encryption 
 vii 
NIST National Institute for Standards and Technology (US) 
OFB Output Feedback 
ord Cấp của đa thức (Order) 
OWF One-Way Function 
OWHF One-Way Hash Function 
R Vành (Ring) 
RIPE Race Integrity Primitives Evaluation 
RSA Rivest Shamir Adleman 
SHA Secure Hash Algorithm 
TDEA Triple Data Encryption Algorithm 
UOWHF Universal One-Way Hash Function 
VEST Very Efficient Substitution Transposition 
W Trọng số (Weight) 
2[ ]/ 1
nx x Z Vành đa thức trên 2GF 
 viii 
DANH MỤC CÁC BẢNG 
Bảng 1. Một số hàm băm ......................................................................................... 3 
Bảng 1.1. Trạng thái của các vector đầu ra M-dãy ................................................ 22 
Bảng 1.2. Các đặc tính của dãy tuyến tính có chu kỳ 2m-1 .................................... 26 
Bảng 1.3. Bảng IP và IP-1 ....................................................................................... 28 
Bảng 1.4. Độ an toàn mục tiêu của hàm băm ......................................................... 43 
Bảng 2.1. Số kiểu phân hoạch không suy biến M của một số vành ....................... 57 
Bảng 2.2. Tổng số các kiểu phân hoạch của vành 2[ ]/ 1
nx x Z ........................... 58 
Bảng 2.3. M-dãy xây dựng trên vành 152[ ] / 1x x Z .................................................. 63 
Bảng 2.4. Các tam thức cấp cực đại 4095 (32.5.7.13) trên vành x13 + 1 ................ 68 
Bảng 2.5. Một số phần tử của M-dãy trên vành x13+1 ........................................... 69 
Bảng 2.6. M-dãy với chiều dài 4095 theo phân hoạch cực đại .............................. 69 
Bảng 2.7. Số lượng M-dãy lồng ghép với một vài giá trị n khác nhau .................. 70 
Bảng 2.8. Bảng hoán vị ban đầu (IP) ..................................................................... 78 
Bảng 2.9. Bảng hoán vị đảo (IP-1) .......................................................................... 78 
Bảng 2.10. Khoảng cách Hamming dH(C1,Ci) giữa các cặp bản mã khi các bản rõ 
khác nhau 1 bit, dH(M1,Mi) = 1, với cùng một khóa K ................................... 80 
Bảng 2.11. Khoảng cách Hamming dH(C1,Ci) giữa các cặp bản mã khi các khóa 
khác khóa K1 2 bit dH(K1, Ki)=2 với cùng một bản rõ M ............................... 81 
Bảng 3.1. Thông số của các hàm băm họ MD4 ..................................................... 85 
Bảng 3.2. Ký hiệu các thông số và các biến ........................................................... 86 
Bảng 3.3. Khoảng cách Hamming dH(MD1, MDi) khi các khối dữ liệu khác khối 
ban đầu 1 bit ................................................................................................... 97 
Bảng 3.4. Khoảng cách Hamming dH(MD1, MDi) giữa các cặp giá trị băm khi các 
khóa khác khóa K1 2 bit. ................................................................................. 99 
Bảng 3.5. Tính khoảng cách Hamming trung bình khi thay đổi khóa K và thay đổi 
bản tin rõ. ...................................................................................................... 100 
 ix 
DANH MỤC CÁC HÌNH VẼ 
Hình 1.1. Sơ đồ khối chức năng hệ mật khóa bí mật ............................................... 8 
Hình 1.2. M-dãy tạo từ thanh ghi dịch phản hồi tuyến tính LFSR ........................ 22 
Hình 1.3. Mạch tạo M-dãy từ đa thức g(x) = 1+x+x
4
 ........................................... 23 
Hình 1.4. Bộ tạo dãy Gold đối với g1(d) = d
3
 + d +1 và g2(d) = d
3
 + d
2
 +1............ 24 
Hình 1.5. Sơ đồ mã hóa DES ................................................................................. 27 
Hình 1.6. Mô tả hàm f trong DES .......................................................................... 28 
Hình 1.7. Các bước tạo khóa cho các vòng mã hóa của DES ................................ 29 
Hình 1.8. Sơ đồ khối chức năng hệ mật khóa công khai ........................................ 30 
Hình 1.9. Phân loại hàm băm ................................................................................. 36 
Hình 1.10. Các sơ đồ hàm băm đơn a) Matyas-Mayer–Oseas; 
 b) Davies-Mayer và c) Miyaguchi – Preneel ...................................... 37 
Hình 1.11. Thuật toán MDC-2 ............................................................................... 39 
Hình 1.12. Thuật toán MDC-4 ............................................................................... 40 
Hình 1.13. Sơ đồ Miyaguchi – Preneel .................................................................. 41 
Hình 1.14. Kiểm tra tính toàn vẹn bằng MAC ....................................................... 45 
Hình 1.15. Kiểm tra tình toàn vẹn dùng MDC và thuật toán mã hóa .................... 45 
Hình 1.16. Kiểm tra tính toàn vẹn dùng MDC và kênh an toàn ............................ 46 
Hình 1.17. Quá trình tạo chữ ký số và kiểm tra chữ ký số ..................................... 47 
Hình 1.18. Sơ đồ chữ ký số dùng RSA .................................................................. 47 
Hình 1.19. Sơ đồ chữ ký số dùng RSA và có bảo mật thông báo .......................... 48 
Hình 2.1. Mã hóa và giải mã xây dựng trên cấp số nhân cyclic ............................ 71 
Hình 2.2. Sơ đồ thiết bị mã hoá .............................................................................. 75 
Hình 2.3. Sơ đồ thiết bị giải mã ............................................................................. 75 
Hình 2.4. Sơ đồ mạng thay thế Feistel ................................................................... 76 
Hình 2.5. Sơ đồ mã hóa khối E .............................................................................. 77 
Hình 2.6. Sơ đồ khối mã hóa , với khóa 4 51 1K x x ..................................... 79 
Hình 3.1. Tương tác giữa mở rộng thông báo và các thao tác bước ...................... 83 
Hình 3.2. Một bước mã hóa của MD5 ................................................................... 92 
Hình 3.3. Sơ đồ thực hiện hàm băm ....................................................................... 95 
Hình 3.4. Sơ đồ bộ mã hóa khóa E với khóa K1 .................................................... 95 
 1 
PHẦN MỞ ĐẦU 
1. MỞ ĐẦU 
Trong sự phát triển của xã hội loài người, kể từ khi có sự trao đổi thông tin, 
thì an toàn thông tin trở thành một nhu cầu gắn liền với nó. Từ thủa sơ khai, an 
toàn thông tin được hiểu đơn giản là giữ bí mật và điều này được xem như một 
 ... sactions 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. 
[37]. Message authentication with one-way hash functions, INFOCOM’92. 
Eleventh Annual Joint Conference of the 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 n , độ dài đầu ra hàm nén m , số lượng các thanh ghi r , số bước mã hóa s , độ 
dài của một từ w, số lượng các từ thông báo t được tách từ thông báo ban đầu có 
chiều dài l . 
Khi mô tả mở rộng thông báo, có các phép hoán vị 
k 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 
iW . 
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 
iR từ 1,..., ,i i r iR R W 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 ( ,...)iR để mô tả giá trị thực tế của r thanh ghi sau 
bước i , 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 LiR là cho luồng 
bên trái và 
R
iR là cho luồng bên phải. Các giá trị khởi tạo ký hiệu là ,...,r lR R . 
 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: 
Giống RIPE-128: Sau bước 15 (và các bước 31, 47, 63 tương ứng) thay nội 
dung 12
LR bằng 12
RR (và 31
LR bằng 31
RR , 46
LR bằng 46
RR , 61
LR bằng 61
RR tương ứ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 
nội dung 14
LR bằng 14
RR (và 27
LR bằng 27
RR , 46
LR bằng 46
RR , 59
LR bằng 59
RR , 77
LR bằng 
77
RR 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] 
 123 
 [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 ---------- 
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; 
 124 
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 ------------------------ 
+ 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; 
 125 
end; 
somu=0; 
tg=[]; 
for jj=1:dx 
 if x(jj)==1 
 somu=somu+1; 
 tg(somu,:)=shift(y,jj-1); 
 end 
end 
stg=size(tg); 
if stg(1)==1 
 kq=tg; 
else 
 kq=sum(tg); 
 kq=mod(kq,2); 
end 
+ 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 2 1
k
x 
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 ------------------------ 
 4. Chương trình mã hóa hệ mật đề xuất 
% 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 
 127 
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 
 128 
%------- Hoan vi dao ------------------------ 
C16 = [L16 R16]; 
C = IP128(C16,-1); % Du lieu ra 
end 
% &&&&&&&&&& End of file &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 
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'; 
 129 
 %------------ 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 
 130 
 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 
end 
% ------------------- Gia tri bam cuoi cung ------------------- 
switch flag 
case 0 
 MD=E; 
case 1 
 MD=Ei; 
otherwise 
 MD='Khong xac dinh'; 
 131 
End 
% ----------- end of file ---------------- 
6. Chương trình tính toán độ khuếch tán của hàm băm đề xuất 
%---------- 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); 
 132 
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 ---------------------------------------