Đề tài Giải thuật MD5-Message Digest

Giải thuật MD5-Message Digest Giáo viên hướng dẫn : Thầy Trần Ngọc Thái Nhóm SV thực hiện : Nguyễn Khánh Tùng Nguyễn Ngọc Hiệu Lớp : CT702 Giải thuật MD5-Message Digest 1.Giới thiệu 2.Thuật ngữ và kí pháp 3.Mô tả thuật toán 4.Tóm lược 5.Sự khác nhau giữa MD4 và MD5 Giải thuật MD5-Message Digest 1.Giới thiệu Giải thuật có đầu vào là 1 thông điệp(dạng chữ kí) có độ dài tùy ý nào đó,qua quá trình xử lí và phân tích sẽ cho kết quả đầu ra là một dạng để nhận biết (tương tự như dấu điểm chỉ) dài 128bit hoặc thông điệp tóm lược. Giải thuật MD5 ứng dụng trên chữ kí số,nơi mà 1 file lớn hầu hết phải được đảm bảo an toàn dữ liệu cùng các phương tiện như khóa bí mật và công khai,ví dụ như hệ mã RSA. Giải thuật MD5 được thiết kế để chạy khá hiệu quả trên những hệ thống 32bit.Thêm vào đó giải thuật MD5 được thể hiện khá ngắn gọn Giải thuật MD5-Message Digest Được phát triển từ giải thuật chữ kí số MD4,MD5 có các bước nhỏ gọn hơn MD4 nhưng khó thay đổi hơn trong quá trình thiết kế. Được đánh giá là sử dụng nhanh chóng hơn MD4 Đảm bảo tốc độ cũng như tính bảo mật Được công nhận là giải thuật đạt chuẩn. Dựa trên nền tảng của công nghệ OSI ,đối tượng của MD5 được định nghĩa md5 OBJECT IDENTIFIER:: iso(1) member-body(2) US(840) rsadsi(113549) digestAlgorithm(2) 5} các tham số của MD5 cần phải có kiểu NULL Giải thuật MD5-Message Digest 2.Thuật ngữ và kí pháp Trong tài liệu này,1 từ có độ dài 32bit và 1 byte có độ dài 8 bit.Sự sắp xếp tuần tự của các bit có thể là trình tự sắp xếp tự nhiên của 1 byte ,nơi mà mỗi nhóm liên tiếp nhau của 8 bit liên tục sẽ biểu diễn 1 byte và những byte đầu tiên trong danh sách các byte đó là những byte quan trọng (diễn tả thuộc tính của từ).Tương tự như vậy,thứ tự sắp xếp của byte là thứ tự của 32 bit từ.Như vậy mỗi nhóm 4 byte liên tiếp sẽ cho ta 1 từ cùng với đặc điểm ít đặc trưng nhất của nó. Giải thuật MD5-Message Digest Kí kiệu của kí tự “+” có nghĩa là cộng từ (i.e.,modulo-2^32 addition). Kí hiệu X2^64,chỉ 64 bit thấp của b được sử dụng.(Những mẩu này được nối vào như hai từ 32 bit và nối vào những từ thứ tự thấp trước tiên như trong thỏa thuận với những qui định trước). Tại thời điểm này,kết quả thông điệp (sau khi nối các mẩu với b) có 1 độ dài chính xác 512 bit.Tương đương,thông điệp này có độ dài chính xác của 16 từ 32 bit. Giải thuật MD5-Message Digest 3.3.Bước 3:Khởi tạo bộ đệm MD Một bộ đệm 4 từ A,B,C,D được sử dụng để tính toán thông điệp tóm lược.Ở đây từng từ A,B,C,D lần lượt là một bản đăng kí 32 bit.Những bản đăng kí này được khởi tạo với những giá trị trong hệ 16,những byte thấp trước tiên. word A:01 23 45 67 word B:89 ab cd ef word C:fe dc ba 98 word D:76 54 32 10 Giải thuật MD5-Message Digest 3.4.Bước 4:Xử lí thông điệp trong khối 16 từ Trước hết chúng ta định nghĩa 4 hàm phụ mà từng hàm nhập vào 3 từ 32 bit và đưa ra ở đầu ra 1 từ 32 bit F(X,Y,Z) = XY v not(X)Z G(X,Y,Z) = XZ v Ynot(Z) H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X v not(Z)) Trong mỗi mẩu xác định những hoạt động của F có điều kiện: If X then Y else Z Hàm F cho phép sử dụng “+” thay cho “v” từ XY và not(X)Z ,không bao giờ cùng có trong 1 vị trí bit.Nó chú ý đến những điều đó nếu những bit của X,Y và Z là độc lập và ngang hàng,mỗi bit của F(X,Y,Z) là độc lập và ngang hàng. Giải thuật MD5-Message Digest Các hàm G,H,I tương tự như hàm F.Trong đó chúng hành động song song phân theo bit để đưa ra đầu ra từ những bit của X,Y và Z.Trong một trạng thái như vậy nếu các bit của X,Y,Z là độc lập và ngang hàng thì mỗi bit của G(X,Y,Z),H(X,Y,Z),I(X,Y,Z) cũng sẽ độc lập và ngang hàng. Bước này sử dụng 1 bảng 64 yếu tố T[1…64] được xây dựng từ hàm sin.Yếu tố T[i] của bảng được biểu thị bằng phần nguyên của 4294967296*abs(sin(i)),với i là số radians bất kì. Giải thuật MD5-Message Digest //Xử lí mỗi khối 16 từ for i =0 to n/16-1 do for j = 0 to 15 do Set X[j] to M[i*16+j]. End// /* Save A as AA, B as BB, C as CC, and D as DD. */ AA = A BB = B CC = C DD = D   Giải thuật MD5-Message Digest /* Round 1. */ //để [abcd k s i] hiển thị thao tác a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). //Làm 16 thao tác như sau: [ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] [ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] [ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] [ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] Giải thuật MD5-Message Digest /* Round 2 để [abcd k s i] hiển thị thao tác a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */ /* làm 16 thao tác như sau */ [ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] [ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] [ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] [ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] Giải thuật MD5-Message Digest /* Round 3. */ /* để[abcd k s t] hiển thị thao tác a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */ /* làm 16 thao tác như sau */ [ABCD 5 4 33] [DABC 8 11 34][CDAB 11 16 35] [BCDA 14 23 36] [ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] [ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] [ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47][BCDA 2 23 48] Giải thuật MD5-Message Digest /* Round 4. */ /*Để [abcd k s t] hiển thị thao tác a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */ /* làm 16 thao tác như sau. */ [ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] [ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] [ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] [ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] Giải thuật MD5-Message Digest /*rồi thực hiện thêm vào như sau(tăng dần mỗi bản đăng kí bởi giá trị của nó trước khi khối này được khởi động)*/ A = A + AA B = B + BB C = C + CC D = D + DD End; /*lặp trong i*/ Giải thuật MD5-Message Digest 3.5.Bước 5: Đầu ra Thông điệp tóm lược đưa ra đầu ra là A,B,C,D.Với nó,chúng ta bắt đầu với byte thấp của A và kết thúc với byte cao của D Điều này hoàn thành sự mô tả MD5. Giải thuật MD5-Message Digest 4.Tóm lược Giải thuật thông điệp tóm lược thực hiện đơn giản và cung cấp 1 đặc điểm nhận dạng hoặc thông điệp tóm lược của 1 thông điệp có độ dài tùy ý.Nó dự đoán được những khó khăn khi tiếp xúc với 2 thông điệp có cùng nội dung tóm lược là những hoạt động trong bậc của 2^64,và khó khăn của việc đi đến một vài thông điệp tóm lược bất kì cho trước hoạt động trong bậc của 2^128. Giải thuật MD5-Message Digest 5.Sự khác nhau giữa MD4 và MD5 + Một vòng tròn thứ tư đã được thêm vào       +Mỗi bước bây giờ có 1 hằng số cộng duy nhất     + Hàm G trong vòng 2 đã được thay đổi từ (XY v XZ v YZ) sang (XZ v Ynot(Z)) để làm G ít đối xứng hơn +Mỗi bước bây giờ thêm kết quả của bước kề trước +Các từ nhập vào theo thứ tự nào đó được truy nhập trong các vòng 2 và 3 đựợc thay đổi để làm cho những mẫu này ít ảnh hưởng lẫn nhau.