Đăng ký Đăng nhập
Trang chủ Tìm hiểu về mã hoán vị, hàm băm md5, các dịch vụ pgp...

Tài liệu Tìm hiểu về mã hoán vị, hàm băm md5, các dịch vụ pgp

.PDF
47
240
145

Mô tả:

TRƢỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM ---------------------------- BÁO CÁO BÀI TẬP LỚN MÔN HỌC AN TOÀN BẢO MẬT THÔNG TIN Đề tài: TÌM HIỂU VỀ MÃ HOÁN VỊ, HÀM BĂM MD5, CÁC DỊCH VỤ PGP GVHD : TS. Hồ Thị Hƣơng Thơm Nhóm 01 : Lê Hoàng Dƣơng Lê Quyết Tiến Đặng Trung Hiếu Nguyễn Hoàng Thùy Trang Bùi Thị Hƣơng Hải Phòng, tháng 6 năm 2014 CHƢƠNG 1: TỔNG QUAN VỀ MÃ HÓA ........................................................................1 1.1. Khái niệm về mã hóa dữ liệu: ...................................................................................1 1.2. Phân loại mã hóa dữ liệu:.......................................................................................... 1 1.2.1. Phân loại theo các phƣơng pháp: .......................................................................1 1.2.2. Phân loại theo số lƣợng khóa: ............................................................................3 1.3. Tầm quan trọng của mã hóa dữ liệu: ........................................................................3 1.4. Các ứng dụng của mã hóa dữ liệu:............................................................................3 CHƢƠNG 2: MÃ HOÁN VỊ ............................................................................................... 5 2.1. Cơ sở lý thuyết: .........................................................................................................5 (1) Đảo ngƣợc toàn bộ bản rõ ......................................................................................5 (2) Mã hóa theo mẫu hình học .....................................................................................5 2.2. Cài đặt chƣơng trình: ................................................................................................ 6 CHƢƠNG 3: HÀM BĂM MD5 .......................................................................................... 8 3.1. Cơ sở lý thuyết: .......................................................................................................10 3.1.1. Hàm băm: .........................................................................................................10 3.1.2. Hàm băm MD5: ............................................................................................... 12 3.1.2.1. Giới thiệu: .................................................................................................12 3.1.2.2. Thuật toán MD5: ....................................................................................... 12 3.2. Cài đặt chƣơng trình: .............................................................................................. 18 CHƢƠNG 4: CÁC DỊCH VỤ PGP ...................................................................................27 4.1. Tổng quan về PGP ..................................................................................................27 4.1.1. Giới thiệu chung về PGP .................................................................................27 4.1.2. Mục đích sử dụng PGP ....................................................................................27 4.1.3. Hoạt động của PGP .......................................................................................... 27 4.1.3.1. Xác thực ....................................................................................................28 4.1.3.2. Mã hóa ......................................................................................................28 4.1.3.3. Bảo mật và xác thực..................................................................................29 4.1.3.4. Nén ............................................................................................................29 4.1.3.5. Tƣơng thích thƣ điện tử ............................................................................29 4.1.3.6. Khoá riêng và công khai của PGP ............................................................ 30 4.1.3.7. Các chùm khoá PGP .................................................................................31 4.1.3.8. Sinh mẩu tin PGP ...................................................................................... 31 4.1.3.9. Quản lý khoá PGP.....................................................................................31 4.2. Cài đặt và thử nghiệm: ............................................................................................ 32 4.2.1. Cài đặt: .............................................................................................................32 4.2.2. Sử dụng PGP Desktop Proffessionnal: ............................................................ 35 CHƢƠNG 1: TỔNG QUAN VỀ MÃ HÓA 1.1. Khái niệm về mã hóa dữ liệu: Mã hóa đã đƣợc con ngƣời sử dụng từ lâu đời. Các hình thức mã hóa sơ khai đã đƣợc tìm thấy từ khoảng 4000 năm trƣớc trong nền văn minh Ai Cập cổ đại. Trải qua hàng nghìn năm lịch sử, mã hóa đã đƣợc sử dụng rộng rãi ở khắp nơi trên thế giới từ Đông sang Tây để giữ bí mật cho việc giao lƣu thông tin trong nhiều lĩnh vực hoạt động giữa con ngƣời và các quốc gia, đặc biệt trong các lĩnh vực quân sự, chính trị, ngoại giao. Vậy Encrypt (Encipher, Encryption): mã hóa – đó là quá trình biến đổi thông tin từ dạng ban đầu – có thể hiểu đƣợc thành dạng không thể hiểu đƣợc, với mục đích giữ bí mật thông tin đó. Hệ mật mã: Hệ mật mã đƣợc định nghĩa là một bộ năm (P, C, K, E, D), trong đó:      P là tập hữu hạn các các bản rõ có thể C tập hữu hạn các bản mã có thể K là tập hữu hạn các khoá có thể E là tập các hàm lập mã D là tập các hàm giải mã. Với mỗi k ∈ K, có một hàm lập mã ek ∈ E, ek : P → C và một hàm giải mã dk∈ D, dk: C → P sao cho dk(ek(x)) = x , ∀ x ∈ P Hình 1.1 Quá trình mã hóa và giải mã 1.2. Phân loại mã hóa dữ liệu: 1.2.1. Phân loại theo các phƣơng pháp:  Mã hóa 2 chiều (1) Mã hóa đối xứng (Symetric cryptography): - Mã hóa đối xứng còn có một số tên gọi khác nhƣ Secret Key Cryptography hay Private Key Cryptography, sử dụng một khóa cho cả 2 quá trình mã hóa và giải mã. Trong hệ thống mã hóa đối xứng, trƣớc khi truyền dữ liệu, 2 bên gửi 1 và nhận phải thỏa thuận về khóa dùng chung cho quá trình mã hóa và giải mã. Sau đó, bên gửi sẽ mã hóa bản rõ (PlainText) bằng cách sử dụng khóa bí mật này và gửi cho bên nhận. Bên nhận sau khi nhận đƣợc thông điệp đã mã hóa sẽ dùng chính khóa bí mật mà 2 bên đã thỏa thuận để giải mã và lấy lại bản rõ (PlainText). Hình 1.2 Mã hóa đối xứng - Mã hóa đối xứng có thể chia làm 2 loại:  Loại tác động theo từng nhóm bits– Mã khối (Block cipher): từng khối dữ liệu trong văn bản ban đầu đƣợc thay thế bằng một khối dữ liệu khác có cùng độ dài. Đối với các thuật toán ngày nay thì kích thƣớc chung của một khối là 64 bits.  Loại tác động lên bản rõ theo từng bit một – Mã dòng (Stream cipher): dữ liệu của văn bản đƣợc mã hóa từng bit một. Các thuật toán mã hóa theo phƣơng pháp này có tốc độ nhanh hơn các thuật toán theo mã hóa khối, và nó thƣờng đƣợc áp dụng trong trƣờng hợp lƣợng dữ liệu mã hóa chƣa biết trƣớc. - Một số loại mã hóa đối xứng: DES, 3DES, RC4, AES,… (2) Mã hóa bất đối xứng (Asysmetric Cryptography): - Hay còn đƣợc gọi với một cái tên khác là mã hóa công khai (Public Key Cryptograpy), nó đƣợc thiết kế sao khóa đƣợc sử dụng trong quá trình mã hóa khác biệt với kháo sử dụng trong quá trình giải mã. Một ngƣời có thể dùng khóa này để mã hóa dữ liệu nhƣng chỉ duy nhất ngƣời có khóa giải mã tƣơng ứng mới có thể đọc đƣợc dữ liệu mà thôi. Khóa để mã hóa là Public Key, khóa để giải mã là Private Key. 2 Hình 1.3 Mã hóa bất đối xứng - Một ví dụ điển hình của mã hóa bất đối xứng là mã hóa RSA.  Mã hóa 1 chiều: là loại mã hóa mà chỉ có thể mã hóa từ một thông điệp thành một thông điệp rút gọn mà không thể giải mã trở lại thành thông điệp ban đầu. Ví dụ về mã hóa một chiều có thể kể đến SHA1, MD5,… 1.2.2. Phân loại theo số lƣợng khóa:  Mã hóa khóa bí mật (Private Key Cryptography): là dạng mã hóa mà khi ngƣời dùng trao đổi thông tin với nhau không cần trao đổi khóa bí mật, nhƣng khi nhận đƣợc thông điệp gửi đến thì không thể xác nhận chính xác đƣợc ngƣời gửi cũng nhƣ nội dung có bị thay đổi hay không.  Mã hóa khóa công khai (Public Key Cryptography): là dạng mã hóa cho phép ngƣời trao sử dụng trao đổi các thông tin mật mã mà không cần phải trao đổi các khóa chung bí mật trƣớc đó. Điều này đƣợc thực hiện bằng các sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa bí mật. 1.3. Tầm quan trọng của mã hóa dữ liệu: Thuật ngữ Cryptography đề cập tới ngành khoa học nghiên cứu về mã hóa và giải mã thông tin. Cụ thể hơn là nghiên cứu các cách thức chuyển đổi thông tin từ dạng rõ sang dạng mờ và ngƣợc lại. Đây là một phƣơng pháp rất tốt trong việc chống lại những truy cập bất hợp pháp tới dữ liệu đƣợc truyền đi trên mạng, áp dụng mã hóa sẽ khiến thông tin đƣợc truyền đi dƣới dạng mờ và không thể đọc bởi bất kỳ ai cố tình muốn lấy thông tin đó. Mã hóa đƣợc áp dụng nhƣ một biện pháp nhằm giúp chúng ta bảo vệ chính mình cũng nhƣ những thông tin chúng ta muốn truyền đi. Bên cạnh đó mã hóa còn có những ứng dụng khác nhau nhƣ bảo đảm tính toàn vẹn của dữ liệu, tính bí mật, tính xác thực và tính không thể chối bỏ. 1.4. Các ứng dụng của mã hóa dữ liệu: Một số ứng dụng của mã hóa dữ liệu phổ biến: (1) Securing Mail (Bảo mật email) (2) Authentication System (Xác thực hệ thống) (3) Secure E-commere (An toàn trong thƣơng mại điện tử) (4) Virtual Private Network (Bảo mật mạng riêng ảo) 3 (5) Wireless Encryption (Mã hóa mạng không dây) (6) Là nền tảng của chữ ký điện tử, các hệ thống PKI (hạ tầng khóa công khai) (7) … 4 CHƢƠNG 2: MÃ HOÁN VỊ 2.1. Cơ sở lý thuyết: Hệ mã hoán vị hay còn gọi là hệ mã hóa đổi chỗ. Là hệ mã hóa mà các ký tự của bản rõ vẫn giữ nguyên, nhƣng thứ tự của chúng đƣợc sắp xếp lại. Không giống nhƣ mã thay thế, ở đây không có phép toán đại số nào cần thực hiện khi mã hóa và giải mã. Phƣơng pháp này có các kỹ thuật mã hóa sau: (1) Đảo ngƣợc toàn bộ bản rõ Nghĩa là bản gốc đƣợc viết theo thứ tự ngƣợc lại từ sau ra trƣớc, để tạo bản mã. Đây là phƣơng pháp mã hóa đơn giản nhất vì vậy không đảm bảo an toàn. Ví dụ: Plaintext: SECURE EMAIL Bản mã: LIAMEERUCES (2) Mã hóa theo mẫu hình học Bản gốc đƣợc sắp xếp lại theo một mẫu hình học nào đó, thƣờng là một mảng hoặc ma trận hai chiều. Ví dụ: Bản rõ: “KHOA CONG NGHE THONG TIN” đƣợc viết theo ma trận 4x5 nhƣ sau: Cột 1 Cột 2 Cột 3 Cột 4 Cột 5 K H O A C O N G N G H E T H O N G T I N Nếu lấy các ký tự ra theo số thứ tự cột 3, 1, 4, 2, 5 thì ta thu đƣợc bản mã “OGTTKOHNANHIHNEGCGON” (3) Đổi chỗ cột: Đầu tiên biểu diễn các ký tự trong bản rõ thành dạng hình chữ nhật theo cột, sau đó các cột đƣợc sắp xếp lại và các chữ cái đƣợc lấy ra theo hàng ngang. Ví dụ: Bản rõ là “KHOA CONG NGHE THONG TIN” đƣợc viết dƣới dạng ma trận 4x5 theo cột nhƣ sau: Cột 1 Cột 2 Cột 3 Cột 4 Cột 5 K C N T G H O G H T O N H O I A G E N N 5 Vì có 5 cột nên ta có thể sắp xếp lại theo 5!=120 cách khác nhau. Để tăng độ an toàn có thể chọn 1 trong các cách sắp xếp lại đó. Nếu ta chuyển vị trí các cột theo thứ tự 3, 5, 2, 4, 1. Rồi lấy các ký tự ra theo hàng ngang ta sẽ đƣợc bản mã là: “NGCTKGTOHHHINÔENGNA” Lƣu ý: các ký tự trống đƣợc bỏ đi. (4) Hoán vị các ký tự của bản rõ theo chu kỳ cố định Cho m là một số nguyên dƣơng xác định nào đó. Cho P = C = (Z26)m và cho K gồm tất cả các hoán vị của {1,…,m}. Đối với một khóa π (tức là một hoán vị) ta xác định: Bản mã: eπ (x1,x2,..,xm) = (xπ(1),…, xπ(m)) Giải mã: dπ (x1,x2,..,xm) = (yπ-1(1),…, yπ-1(m)) Ví dụ: Mã hóa bản rõ “BAO MAT” chọn m = 6 và π là một hoán vị dãy i = 123456 thành 351462 Vị trí đầu Vị trí hoán vị Từ Mã hóa 1 3 B O 2 5 A A 3 1 O B 4 4 M M 5 6 A T 6 2 T A Trên bảng trên ta thấy ký tự đầu sau khi hoán vị chuyển đến vị trí thứ 3, ký tự thứ 2 chuyển tới vị trí thứ 5, ký tự thứ 3 chuyển tới vị trí thứ 1… Nhƣ vậy sau khi mã hóa ta thu đƣợc bản mã là: “OABMTA”. Nếu kích thƣớc bản rõ lớn hơn nhiều so với d thì ta sẽ phải chia bản rõ thành các khối d ký tự và tiến hành mã hóa theo từng khối. Ví dụ: Bản rõ “KHOA CONG NGHE THONG TIN” giả sử d=6, và f hoán vị dãy i = 12345 thành f(i) = 35142 Ta thu đƣợc bản mã “OCKAHGGONNTOHHETNIG” 2.2. Cài đặt chƣơng trình: 2.2.1. Mã nguồn cài đặt: 6 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace ThuatToanMaHoa { public class ThuatToanMaHoaHoanVi { private Dictionary _BangHoanVi; private Dictionary _BangGiaiHoanVi; private int _KichThuocHoanVi { get { return _BangHoanVi.Keys.Count; } } public ThuatToanMaHoaHoanVi(string vPath) { int level = 1; try { StreamReader sr = new StreamReader(vPath); try { _BangHoanVi = new Dictionary(); _BangGiaiHoanVi = new Dictionary(); int num = int.Parse(sr.ReadLine()); for (int i = 0; i < num; i++) { int val = int.Parse(sr.ReadLine()); _BangHoanVi.Add(i, val); if (!_BangGiaiHoanVi.Keys.Contains(val)) _BangGiaiHoanVi.Add(val, i); if (val >= num || val < 0) { level = 2; throw new Exception("Giá trị của bảng hoán vị không đƣợc vƣợt quá giới hạn của bảng"); } } if (_BangGiaiHoanVi.Keys.Count != _BangHoanVi.Keys.Count) { level = 2; throw new Exception("Giá trị của bảng hoán vị có trùng lặp"); } sr.Close(); } 7 catch (Exception ex) { sr.Close(); throw ex; } } catch (Exception ex) { if (level == 1) throw new Exception("Đƣờng dẫn file bảng hoán vị không đúng"); else throw ex; } } public string MaHoaHoanVi(string vBanRo,bool vThemDauCachTrong) { if (vThemDauCachTrong) while (vBanRo.Length % _KichThuocHoanVi != 0) vBanRo += " "; if (vBanRo.Length % _KichThuocHoanVi != 0) throw new Exception("Kích thƣớc chuỗi đầu vào phải chia hết cho kích thƣớc bảng hoán vị"); char[] banMa = vBanRo.ToArray(); int len = vBanRo.Length; for (int i = 0; i < len; ++i) { int thuTu = i % _KichThuocHoanVi; int dich = i - thuTu; banMa[dich + _BangHoanVi[thuTu]] = vBanRo[dich + thuTu]; } return new string(banMa); } public string GiaiMaHoanVi(string vBanMa,bool vThemDauCachTrong) { if (vThemDauCachTrong) while (vBanMa.Length % _KichThuocHoanVi != 0) vBanMa += " "; if (vBanMa.Length % _KichThuocHoanVi != 0) throw new Exception("Kích thƣớc chuỗi đầu vào phải chia hết cho kích thƣớc bảng hoán vị"); char[] banRo = vBanMa.ToArray(); int len = vBanMa.Length; for (int i = 0; i < len; ++i) { int thuTu = i % _KichThuocHoanVi; int dich = i - thuTu; banRo[dich + thuTu] = vBanMa[dich + _BangHoanVi[thuTu]]; 8 } return new string(banRo); } } } 2.2.2. Giao diện demo: Hình 2.1 Giao diện demo thuật toán mã hoán vị 9 CHƢƠNG 3: HÀM BĂM MD5 3.1. Cơ sở lý thuyết: 3.1.1. Hàm băm: Hàm băm là các thuật toán không sử dụng khóa để mã hóa (ở đây ta dùng thuật ngữ “băm” thay cho “mã hóa”), nó có nhiệm vụ “lọc” (băm) thông điệp đƣợc đƣa vào theo một thuật toán h một chiều nào đó, rồi đƣa ra một bản băm – văn bản đại diện – có kích thƣớc cố định. Do đó ngƣời nhận không biết đƣợc nội dung hay độ dài ban đầu của thông điệp đã đƣợc băm bằng hàm băm. Giá trị của hàm băm là duy nhất, và không thể suy ngƣợc lại đƣợc nội dung thông điệp từ giá trị băm này.  Đặc trưng Hàm băm h là hàm băm một chiều (one-way hash) với các đặc tính sau:  Với thông điệp đầu vào x thu đƣợc bản băm z = h(x) là duy nhất.  Nếu dữ liệu trong thông điệp x thay đổi hay bị xóa để thành thông điệp x’ thì h(x’)  h(x). Cho dù chỉ là một sự thay đổi nhỏ hay chỉ là xóa đi 1 bit dữ liệu của thông điệp thì giá trị băm cũng vẫn thay đổi. Điều này có nghĩa là: hai thông điệp hoàn toàn khác nhau thì giá trị hàm băm cũng khác nhau. Nội dung của thông điệp gốc không thể bị suy ra từ giá trị hàm băm. Nghĩa là: với thông điệp x thì dễ dàng tính đƣợc z = h(x), nhƣng lại không thể (thực chất là khó) suy ngƣợc lại đƣợc x nếu chỉ biết giá trị hàm băm h  Tính chất Tính chất 1: Hàm băm h là không va chạm yếu Xét một kiểu tấn công nhƣ sau: Đáng lẽ: thông tin phải đƣợc truyền đúng từ A đến B Ng-êi göi A (x, y = sigK(h(x)) Ng-êi nhËn B Hình 3.1 Cách đi đúng của thông tin 10 Nhƣng: trên đƣờng truyền, thông tin bị lấy trộm và bị thay đổi (x, y = sigK(h(x)) Ng-êi nhËn B (x, y = sigK(h(x)) (x’, y = sigK(h(x)) Ng-êi göi A Tªn nghe lÐn, lÊy trém tin Hình 3.2 Thông tin bị lấy trộm và bị thay đổi trên đường truyền Ngƣời A gửi cho B (x, y) với y = sigK(h(x)). Nhƣng trên đƣờng truyền, tin bị lấy trộm. Tên trộm, bằng cách nào đó tìm đƣợc một bản thông điệp x’ có h(x’) = h(x) mà x’  x. Sau đó, hắn đƣa x’ thay thế x rồi truyền tiếp cho ngƣời B. Ngƣời B nhận đƣợc và vẫn xác thực đƣợc thông tin đúng đắn. Do đó, để tránh kiểu tấn công nhƣ trên, hàm h phải thỏa mãn tính không va chạm yếu: Hàm băm h là không va chạm yếu nếu khi cho trƣớc một bức điện x, không thể tiến hành về mặt tính toán để tìm ra một bức điện x’  x mà h(x’) = h(x). Tính chất 2: Hàm băm h là không va chạm mạnh: Xét một kiểu tấn công nhƣ sau: Đầu tiên, tên giả mạo tìm ra đƣợc hai bức thông điệp x’ và x (x’  x) mà có h(x’) = h(x) (ta coi bức thông điệp x là hợp lệ, còn x’ là giả mạo). Tiếp theo, hắn đƣa cho ông A và thuyết phục ông này kí vào bản tóm lƣợc h(x) để nhận đƣợc y. Khi đó (x’, y) là bức điện giả mạo nhƣng hợp lệ. Để tránh kiểu tấn công này, hàm h phải thỏa mãn tính không va chạm mạnh: Hàm băm h là không va chạm mạnh nếu không có khả năng tính toán để tìm ra hai bức thông điệp x và x’ mà x  x’ và h(x) = h(x’). Tính chất 3: Hàm băm h là hàm một chiều: Xét một kiểu tấn công nhƣ sau: Việc giả mạo các chữ ký trên bản tóm lƣợc z thƣờng xảy ta với các sơ đồ chữ ký số. Giả sử tên giả mạo tính chữ ký trên bản tóm lƣợc z, sau đó hắn tìm một bản thông điệp x’ đƣợc tính ngƣợc từ bản đại diện z, z = h(x’). Tên trộm thay thế bản thông điệp x hợp lệ bằng bản thông điệp x’ giả mạo, nhƣng lại có z = h(x’). Và hắn ký số trên bản đại diện cho x’ bằng đúng chữ ký hợp lệ. Nếu làm đƣợc nhƣ vậy thì (x’, y) là bức điện giả mạo nhƣng hợp lệ. Để tránh đƣợc kiểu tấn công này, h cần thỏa mãn tính chất một chiều: Hàm băm h là một chiều nếu khi cho trƣớc một bản tóm lƣợc thông báo z thì không thể thực hiện về mặt tính toán để tìm ra thông điệp ban đầu x sao cho h(x) = z . 11  Các thuật toán băm Các hàm băm dòng MD: MD2, MD4, MD5 đƣợc Rivest đƣa ra thu đƣợc kết quả đầu ra với độ dài là 128 bit. Hàm băm MD4 đƣa ra vào năm 1990. Một năm sau phiên bản mạnh MD5 cũng đƣợc đƣa ra. Chuẩn hàm băm an toàn: SHA, phức tạp hơn nhiều cũng dựa trên các phƣơng pháp tƣơng tự, đƣợc công bố trong Hồ sơ Liên bang năm 1992 và đƣợc chấp nhận làm tiêu chuẩn vào năm 1993 do Viện Tiêu Chuẩn và Công Nghệ Quốc Gia (NIST), kết quả đầu ra có độ dài 160 bit. 3.1.2. Hàm băm MD5: 3.1.2.1. Giới thiệu: MD5 (Message-Digest algorithm 5) là một hàm băm để mã hóa với giá trị băm là 128bit. Từng đƣợc xem là một chuẩn trên Internet, MD5 đã đƣợc sử dụng rộng rãi trong các chƣơng trình an ninh mạng, và cũng thƣờng đƣợc dùng để kiểm tra tính nguyên vẹn của tập tin. MD5 đƣợc thiết kế bởi Ronald Rivest vào năm 1991 để thay thế cho hàm băm trƣớc đó MD4. MD5 có 2 ứng dụng quan trọng: (1) MD5 đƣợc sử dụng rộng rải trong thế giới phần mềm để đảm bảo rằng tập tin tải về không bị hỏng. Ngƣời sử dụng có thể so sánh giữa thông số kiểm tra phần mềm bằng MD5 đƣợc công bố với thông số kiểm tra phần mềm tải về bằng MD5. Hệ điều hành Unix sử dụng MD5 để kiểm tra các gói mà nó phân phối, trong khi hệ điều hành Windows sử dụng phần mềm của hãng thứ ba. (2) MD5 đƣợc dùng để mã hóa mật khẩu. Mục đích của việc mã hóa này là biến đổi một chuổi mật khẩu thành một đoạn mã khác, sao cho từ đoạn mã đó không thể nào lần trở lại mật khẩu. Có nghĩa là việc giải mã là không thể hoặc phải mất một khoãng thời gian vô tận (đủ để làm nản lòng các hacker). 3.1.2.2. Thuật toán MD5: MD5 biến đổi một thông điệp có chiều dài bất kì thành một khối có kích thƣớc cố định 128 bits. Thông điệp đƣa vào sẽ đƣợc cắt thành các khối 512 bits. Thông điệp đƣợc đƣa vào bộ đệm để chiều dài của nó chia hết cho 512. Bộ đệm hoạt động nhƣ sau: (1) Trƣớc tiên nó sẽ chèn bit 1 vào cuối thông điệp. (2) Tiếp đó là hàng loạt bit Zero cho tới khi chiều dài của nó nhỏ hơn bội số của 512 một khoảng 64 bit . (3) Phần còn lại sẽ đƣợc lấp đầy bởi một số nguyên 64 bit biểu diễn chiều dài ban đầu của thông điệp. Trong trƣờng hợp độ dài của thông điệp lớn hơn 2^64 thì chỉ có 64 bit thấp đƣợc sử dụng. 12 Thuật toán chính của MD5 hoạt động trên một bộ 128 bit. Chia nhỏ nó ra thành 4 word 32 bit, kí hiệu là A,B,C và D. Các giá trị này là các hằng số cố định. Khối dữ liệu đầu vào của thuật toán có độ dài là bội số của 512 sẽ đƣợc chia thành L khối 512 bit. Sau đó thuật toán chính sẽ luân phiên hoạt động trên các khối 512 bit. Mỗi khối sẽ phối hợp với một bộ. Quá trình xử lý một khối thông điệp bao gồm 4 bƣớc tƣơng tự nhau, gọi là vòng (“Round”). Mỗi vòng lại gồm 16 quá trình tƣơng tự nhau dựa trên hàm một chiều F, phép cộng module và phép xoay trái…Đây là hình mô tả một quá trình trong một vòng. Có 4 hàm một chiều F có thể sử dụng. Mỗi vòng sử dụng một hàm khác nhau. Hình 3.3 uá trình trong một v ng Thuật toán: Input : Thông điệp có độ dài tùy ý. Ouput : Bản băm, đại diện cho thông điệp gốc, độ dài cố định 128 bit. Mô tả thuật toán: Giả sử đầu vào là một xâu a có độ dài b bit (b có thể bằng 0) Bước 1: Khởi tạo các thanh ghi Có 4 thanh ghi đƣợc sử dụng để tính toán nhằm đƣa ra các đoạn mã: A, B, C, D. Bản tóm lƣợc của thông điệp đƣợc xây dựng nhƣ sự kết nối của các thanh ghi. Mỗi thanh ghi có độ dài 32 bit. Các thanh ghi này đƣợc khởi tạo giá trị hecxa. word A := 67 45 23 01 13 word B := EF CD AB 89 word C := 98 BA DC FE word D := 10 32 54 76 Bước 2: Xử lý thông điệp a trong 16 khối word, có nghĩa là xử lý cùng một lúc 16 word = 512 bit (chia mảng M thành các khối 512 bit, đƣa từng khối 512 bit đó vào mảng T[j]). Mỗi lần xử lý một khối 512 bit. Lặp lại N/16 lần. Gán giá trị cho bốn biến AA, BB, CC, DD lần lƣợt bằng giá trị của 4 thanh ghi A, B, C, D. Bước 3:Thực hiện bốn vòng băm với các khối cần xử lý Một số phép toán logic đƣợc sử dụng trong bốn vòng này.  X  Y là phép toán AND theo bit giữa X và Y  X  Y là phép toán OR theo bit giữa X và Y  X  Y là phép toán XOR theo bit giữa X và Y   X chỉ phép bù của X  X + Y là phép cộng theo modulo 232  X <<< s là phép dịch vòng trái X đi s vị trí (0  s  31) 14 Bội số của 512 bít 1…512 bit K bít Message 512 bit Y1 512 ABCD 128 100 … 000 512 bit Y0 128 HMD5 K mod 264 512 bit … 512 HMD5 Chiều dài của message Yp 512 bit … YL-1 512 128 HMD5 512 128 HMD5 Digest 128 bit Hình 3.4 uá trình tạo bản băm của MD5 Các vòng 1, 2, 3 và 4 dùng tƣơng ứng ba hàm F, G, H và I. Mỗi hàm này là một hàm boolean tính theo bit. Chúng đƣợc xác định nhƣ sau: F(X, Y, Z) = (X  Y)  ((  X)  Z) G(X, Y, Z) = (X  Z)  (Y  (  Z)) H(X, Y, Z) = X  Y  Z I(X, Y, Z) = Y  (X  (  Z)) Thuật toán MD5 1. A := 67 45 23 01 B := ef cd ab 89 C := 98 ba dc fe D := 10 32 54 76 2. for i := 0 to n/16 - 1 do { 3. for j := 0 to 15 do T[j] = M[16i + j]; 4. AA := A; Mỗi lần xử lý 16 từ, mỗi từ 32 bit, tl: 512 bit. BB := B; CC := C; DD := D; 5. round_1(); 6. round_2(); 15 7. round_3(); 8. round_4(); 9. A = A + AA B = B + BB C = C + CC D = D + DD } Bốn vòng trong MD5 là hoàn toàn khác nhau. Mỗi vòng (5, 6, 7, 8) gồm một trong 16 word trong T. T = getFromM(i*16, 16) AA = A BB = B CC = C DD = D round_1() round_2() round_3() round_4() A = A + AA B = B + BB C = C + CC D = D + DD i=i+1 a M = getBufferMsg(a) A = 67 45 23 B = ef cd ab C = 98 ba dc D = 10 32 54 n = length(M) 01 89 fe 76 i=0 DCBA F i > n div 16 -1 T Hình 3.5 Lược đồ thuật toán MD5 MD5 sử dụng thêm một mảng S[1 … 64] đƣợc xây dựng từ hàm sin. Với S[i], giá trị của phần tử thứ i trong mảng S, tƣơng đƣơng với phần nguyên của 4294967296  abs(sin(i)), với i tính theo radian.  Vòng 1 sử dụng giá trị trong mảng S[1 … 16]  Vòng 2 sử dụng giá trị trong mảng S[17 … 32]  Vòng 3 sử dụng giá trị trong mảng S[33 … 48]  Vòng 4 sử dụng giá trị trong mảng S[49 … 64] 16 Ta có mảng S[1 … 64] nhƣ sau (tất cả đều để ở hệ cơ số 16): 1. D76AA478 17. F61E2562 33. FFFA3942 49. F4292244 2. E8C7B756 18. D040B340 34. 8771F681 50. 432AFF97 3. 242070DB 19. 265E5A51 35. 6D9D6122 51. AB9423A7 4. C1BDCEEE 20. E9B6C7AA 36. FDE5390C 52. FC93A039 5. F57C0FAF 21. D62F105D 37. A4BEEA44 53. 655B59C3 6. 4787C62A 22. 02441453 38. 4BDECFA9 54. 8F0CCC92 7. A8304613 23. D8A1E681 39. F6BB4B60 55. FFEFF47D 8. FD469501 24. E7D3FBC 40. BEBFBC70 56. 85845DD1 9. 698098D8 25. 21E1CDE6 41. 289B7EC6 57. 6FA87E4F 10. 8B44F7AF 26. C33707D6 42. EAA127FA 58. FE2CE6E0 11. FFFF5BB1 27. F4D50D87 43. D4EF3085 59. A3014314 12. 895CD7BE 28. 455A14ED 44. 04881D05 60. 4E0811A1 13. 6B901122 29. A9E3E905 45. D9D4D039 61. F7537E82 14. FD987193 30. FCEFA3F8 46. E6DB99E5 62. BD3AF235 15. A679438E 31. 676F02D9 47. 1FA27CF8 63. 2AD7D2BB 16. 49B40821 32. 8D2A4C8A 48. D4AC5665 64. EB86D391 17 Các phép toán đƣợc thực hiện trong bốn vòng tạo ra các giá trị mới trong bốn thanh ghi. Cuối cùng, bốn thanh ghi đƣợc cập nhật ở 3.5 bằng cách cộng ngƣợc các giá trị lƣu trƣớc đó ở 2.3. Phép cộng này đƣợc xác định là cộng các số nguyên dƣơng, đƣợc rút gọn theo modulo 232. Vòng 1 (round_1()) Vòng 2 (round_2()) 1. A = (A + F(B, C, D) + T0] + S[1] <<< 7 1. A = (A + G(B, C, D) + T[1] + S[17] <<< 5 2. D = (D + F(A, B, C) + T[1] + S[2]) <<< 12 3. C = (C + F(D, A, B) + T[2] + S[3]) <<< 17 4. B = (B + F(C, D, A) + T[3] + S[4]) <<< 22 5. A = (A + F(B, C, D) + T[4] + S[5]) <<< 7 6. D = (D + F(A, B, C) + T[5] + S[6]) <<< 12 7. C = (C + F(D, A, B) + T[6] + S[7]) <<< 17 8. B = (B + F(C, D, A) + T[7] + S[8]) <<< 22 9. A = (A + F(B, C, D) + T[8] + S[9]) <<< 7 10. D = (D + F(A, B, C) + T[9] + S[10]) <<< 12 11. C = (C + F(D, A, B) + T[10] + S[11]) <<< 17 12. B = (B + F(C, D, A) + T[11] + S[12]) <<< 22 13. A = (A + F(B, C, D) + T[12] + S[13]) <<< 7 14. D = (D + F(A, B, C) + T[13] + S[14]) <<< 12 15. C = (C + F(D, A, B) + T[14] + S[15]) <<< 17 16. B = (B + F(C, D, A) + T[15] + S[16]) <<< 22 2. D = (D + G(A, B, C) + T[6] + S[18]) <<< 9 3. C = (C + G(D, A, B) + T[21] + S[19]) <<< 14 4. B = (B + G(C, D, A) + T[0] + S[20]) <<< 20 5. A = (A + G(B, C, D) + T[5] + S[21]) <<< 5 6. D = (D + G(A, B, C) + T[10] + S[22]) <<< 9 7. C = (C + G(D, A, B) + T[15] + S[23]) <<< 14 8. B = (B + G(C, D, A) + T[4] + S[24]) <<< 20 9. A = (A + G(B, C, D) + T[9] + S[25]) <<< 5 10.D = (D + G(A, B, C) + T[14] + S[26]) <<< 9 11.C = (C + G(D, A, B) + T[3] + S[27]) <<< 14 12.B = (B + G(C, D, A) + T[8] + S[28]) <<< 20 13.A = (A + G(B, C, D) + T[13] + S[29]) <<< 5 14.D = (D + G(A, B, C) + T[2] + S[30]) <<< 9 15.C = (C + G(D, A, B) + T[7] + S[31]) <<< 14 16.B = (B + G(C, D, A) + T[12] + S[32]) <<< 20 Vòng 3 (round_1()) Vòng 4 (round_4()) 1. A = (A + H(B, C, D) + T[5] + S[33]) <<< 4 1. A = (A + I(B, C, D) + T[0] + S[49]) <<< 6 2. D = (D + H(A, B, C) + T[8] + S[34]) <<< 11 3. C = (C + H(D, A, B) + T[11] + S[35]) <<< 16 4. B = (B + H(C, D, A) + T[14] + S[36]) <<< 23 5. A = (A + H(B, C, D) + T[1] + S[37]) <<< 4 6. D = (D + H(A, B, C) + T[4] + S[38]) <<< 11 7. C = (C + H(D, A, B) + T[7] + S[39]) <<< 16 8. B = (B + H(C, D, A) + T[10] + S[40]) <<< 23 9. A = (A + H(B, C, D) + T[13] + S[41]) <<< 4 10. D = (D + H(A, B, C) + T[0] + S[42]) <<< 11 11. C = (C + H(D, A, B) + T[3] + S[43]) <<<16 12. B = (B + H(C, D, A) + T[6] + S[44]) <<< 23 13. A = (A + H(B, C, D) + T[9] + S[45]) <<< 4 14. D = (D + H(A, B, C) + T[12] + S[46]) <<< 11 15. C = (C + H(D, A, B) + T[15] + S[47]) <<< 16 16. B = (B + H(C, D, A) + T[2] + S[48]) <<< 23 2. D = (D + I(A, B, C) + T[7] + S[50]) <<< 10 3. C = (C + I(D, A, B) + T[14] + S[51]) <<< 15 4. B = (B + I(C, D, A) + T[5] + S[52]) <<< 21 5. A = (A + I(B, C, D) + T[12] + S[53]) <<< 6 6. D = (D + I(A, B, C) + T[3] + S[54]) <<< 10 7. C = (C + I(D, A, B) + T[10] + S[55]) <<< 15 8. B = (B + I(C, D, A) + T[1] + S[56]) <<< 21 9. A = (A + I(B, C, D) + T[8] + S[57]) <<< 6 10. D = (D + I(A, B, C) + T[15] + S[58]) <<< 10 11. C = (C + I(D, A, B) + T[6] + S[59]) <<< 15 12. B = (B + I(C, D, A) + T[13] + S[60]) <<< 21 13. A = (A + I(B, C, D) + T[4] + S[61]) <<< 6 14. D = (D + I(A, B, C) + T[11] + S[62]) <<< 10 15. C = (C + I(D, A, B) + T[2] + S[63]) <<< 15 16. B = (B + I(C, D, A) + T[9] + S[64]) <<< 21 Bước 5: Output Kết quả ra là đoạn mã có độ dài 128 bit, đƣợc thu gọn từ thông điệp a có độ dài b bit. Đoạn mã này thu đƣợc từ 4 thanh ghi A, B, C, D: bắt đầu từ byte thấp của thanh ghi A cho đến byte cao của thanh ghi D. 3.2. Cài đặt chƣơng trình: 3.2.1. Mã nguồn chƣơng trình: 18
- Xem thêm -

Tài liệu liên quan