Chữ kí điện tữ mã hóa MD5

ký. Để kiểm tra tính toàn vẹn của số liệu, người nhận rút khoá công cộng của người gửi từ chứng nhận điện tử của nó và sử dụng khoá công cộng này để giải mật mã chữ ký điện tử. Sau đó áp dụng hàm Hash mà đã được người gửi sử dụng cho số liệu gốc nhận được. Các tóm tắt bản tin thu được sẽ được so sánh với nhau để thẩm định rằng bản tin không bị sửa đổi trong quá trình truyền dẫn và nó thực sự được gửi từ người gửi mong đợi. Chú ý rằng người nhận phải lấy chứng nhận số của người gửi từ một server chứng nhận, đây chính là bước kiểm tra giá trị chứng nhận 2.2.4 CHỨNG NHẬN CHỮ KÝ ĐIỆN TỬ Các khóa công cộng đã được mô tả trong phần trước và được sử dụng trong nối mạng số liệu để kiểm tra các chữ ký điện tử, bản thân chúng không mang bất cứ thông tin nào về các thực thể cung cấp các chữ ký. Công nghệ nối mạng số liệu thừa nhận vấn đề này và tiếp nhận các chứng nhận an ninh để ràng buộc khóa công cộng và nhận dạng thực thể phát hành khóa. Chứng nhận chữ ký điện tử đảm bảo rằng một khoá công cộng là sở hữu của thực thể mà nó thể hiện. Để thực hiện được điều này, thì chính chứng nhận này cũng phải được kiểm tra để đảm bảo rằng nó đại diện cho đối tượng cần mong muốn (đối tượng này có thể là một cá nhân hoặc một tổ chức). Điều này được thực hiện bằng cách sử dụng một tổ chức thứ ba đáng tin cậy được gọi là thẩm quyền chứng nhận (CA - Certificate Authority) gồm có VeriSign, Entrust, và Certicom. Các thẩm quyền này được phép cung cấp các dịch vụ này cho các thực thể được nhận dạng hợp lệ khi chúng yêu cầu. Để thực hiện chức năng của mình, một CA phải được tin tưởng bởi các thực thể dựa trên các dịch vụ của nó. Người dùng có thể mua chứng nhận số từ CA và sử dụng chứng nhận này để nhận thực và để lưu hành khoá riêng của họ. Một chứng nhận số điển hình chứa những thông tin sau: Tên của người đang nắm giữ chứng nhận chữ ký điện tử, cũng như thông tin khác mà có thể nhận dạng duy nhất người này, thông tin phụ thêm có thể là URL của một Web Server đang sử dụng chứng nhận hay một địa chỉ email. Khoá công cộng của người đang nắm giữ chứng nhận chữ ký điện tử. Tên của CA lưu hành chứng nhận này. Thời hạn sử dụng của chứng nhận(thường là ngày bắt đầu và ngày hết hạn). Một chữ ký số của CA để có thể nhận ra chứng nhậnchữ ký điện tử đề phòng trường hợp phiên truyền dẫn bị phá rối. Tất cả các chứng nhận được ký bằng một khóa riêng của CA. Người sử dụng chứng nhận có thể xem kiểm tra thông tin của chứng nhận có hợp lệ không bằng cách giải mật mã chữ ký bằng một khoá kiểm tra công cộng nhận được từ chứng nhận phát đi từ thẩm quyền mức phân cấp cao hơn và kiểm tra xem nó có phù hợp với MD (Message Digest) của nội dung nhận được trong chứng nhận hay không. Chữ ký thường là một MD được mật mã hóa. Dạng chính của chứng nhận số là X.509, một tiêu chuẩn công nghiệp cho nhận thực. Những chứng nhận này là rất thông dụng trong các ứng dụng Internet. Trong lĩnh vực vô tuyến có loại chứng nhận số khác gọi là chứng nhận WTLS Server WAP (WAP Server WTLS Certificate), các chứng nhận này thường được gọi ngắn gọn là chứng nhận WTLS, đây là phiên bản đơn giản hơn của X.509 được tạo ra do chứng nhận X.509 quá lớn đối với các ứng dụng vô tuyến. Các chứng nhận WTLS chủ yếu được sử dụng trong các ứng dụng WAP nơi mà các trình duyệt muốn nhận thực nhận dạng của một Server WAP và mật mã hoá thông tin bằng cách sử dụng giao thức an ninh lớp truyền tải vô tuyến (WTLS - Wireless Transport Layer Security). 2.2.5 CHUẨN CHỮ KÝ ĐIỆN TỬ (Digital Signature Standard) Chuẩn chữ ký điện tử (DSS) được sửa đổi từ hệ chữ ký ElGammal. Nó được công bố tại hội nghị Tiêu chuẩn xử lý thông tin Liên Bang (FIPS) vào 19/05/1994 và trở thành chuẩn vào 01/12/1994. DSS sử dụng một khoá công khai để kiểm tra tính toàn vẹn của dữ liệu nhận được và đồng nhất với dữ liệu của người gửi. DSS cũng có thể sử dụng bởi người thứ ba để xác định tính xác thực của chữ ký và dữ liệu trong nó. Đầu tiên chúng ta hãy tìm hiểu động cơ của sự thay đổi này, sau đó sẽ tìm hiểu thuật toán của DSS.Trong rất nhiều trường hợp, một bức điện có thể được mã hoá và giải mã một lần, vì vậy nó đáp ứng cho việc sử dụng của bất kỳ hệ thống bảo mật nào được biết là an toàn lúc bức điện được mã hoá. Nói cách khác, một bức điện được ký đảm nhiệm chức năng như một văn bản hợp pháp, chẳng hạn như các bản hợp đồng, vì vậy nó cũng giống như việc cần thiết để xác minh chữ ký sau rất nhiều năm bức điện được ký. Điều này rất quan trọng cho việc phòng ngừa về độ an toàn của chữ ký được đưa ra bởi một hệ thống bảo mật. Vì hệ chữ ký ElGammal không đảm nhận được điều này, việc thực hiện này cần một giá trị lớn modulo p. Tất nhiên p nên có ít nhất 512-bit, và nhiều người cho rằng độ dài của p nên là 1024-bit nhằm chống lại việc giả mạo trong tương lai.Tuy nhiên, ngay cả một thuật toán modulo 512-bit dùng để ký cũng phải thực hiện việc tính toán đến 1024-bit. Cho ứng dụng tiềm năng này, có rất nhiều card thông minh được đưa ra, nhằm thực hiện một chữ ký ngắn hơn như mong muốn. DSS đã sửa đổi hệ chữ ký ElGammal cho phù hợp theo cách này một cách khéo léo, để mỗi 160-bit bức điện được ký sử dụng một chữ ký 320-bit, nhưng việc tính toán được thực hiện với 512-bit modulo p. Cách này được thực hiện nhờ việc chia nhỏ Z*p thành các trương có kích thước 2160. Việc thay đổi này sẽ làm thay đổi giá trị δ δ = (x+αy) k-1 mod(p-1) Điều này cũng làm cho giá trị kiểm tra cũng thay đổi: Αxβy ≡ yδ (mod p). Nếu UCLN(x + αy, p - 1) = 1 thì sẽ tồn tại δ -1 mod (p - 1), do đó sẽ biến đổi thành: α - xα-1 βyδ -1 ≡(mod p) Đây chính là sự đổi mới của DSS. Chúng ta cho q là một số nguyên tố 160-bit sao cho q | (p-1), và α là một số thứ q của 1 mod p, thì β và y cũng là số thứ q của 1 mod p. Do đó α, β và y có thể được tối giản trong modulo p mà không ảnh hưởng gì đến việc xác minh chữ ký. Cho p là một số nguyên tố 512-bit trong trường logarit rời rạc Zp, q là một số nguyên tố 160-bit và q chia hết (p-1). Cho α € Zp ; P = Zp , A = Zq*Zq, và định nghĩa:K = {(p, q, α, a, β) : β ≡ αa (mod p)} trong đó giá trị p, q, α và β là công khai, còn a là bí mật. Với K = (p, α, a, β) và chọn một số ngẫu nhiên k (1 ≤ k ≤ q-1), định nghĩa: Sigk(x, k) = (y, δ) Chú ý rằng, với DSS thì δ ≠ 0 (mod q) vì giá trị: δ -1 mod q cần cho việc xác minh chữ ký (điều này cũng tương tự như việc yêu cầu UCLN(,δ p-1) = Khi B tính một giá trị δ ≡ 0 (mod q) trong thuật toán ký, anh ta nên bỏ nó đi và chọn một số ngẫu nhiên k mới. Ví dụ: Chúng ta chọn q = 101 và p = 78*q + 1 = 7879 và g = 3 là một nguyên tố trong Z7879. Vì vậy, ta có thể tính: α = 378 mod 7879 = 170. Chọn a = 75, do đó: β = αa mod 7879 = 4567. Bây giờ, B muốn ký một bức điện x = 1234, anh ta chọn một số ngẫu nhiên k = 50. Vì vậy: K -1mod 101 = 99. Tiếp đó: y = (17050 mod 7879) mod 101 = 2518 mod 101 = 94 δ = (1234 + 75*94)99 mod 101 = 97. Cặp chữ ký (94, 97) cho bức điện 1234 được xác thực như sau: δ -1 = 97-1 mod 101 = 25 e1 = 1234*25 mod 101 = 45 e2 = 94*25 mod 101 = 27 (17045456727 mod 7879) mod 101 = 2518 mod 101 = 94. Kể từ khi DSS được đề xuất vào năm 1991, đã có nhiều phê bình đưa ra. Chẳng hạn như kích cỡ của moduloe p bị cố định 512-bit, điều mà nhiều người không muốn. Vì vậy, NIST đã thay đổi chuẩn này để có thể thay đổi kích thước moduloe (chia bởi 64) thành một dãy từ 512 đến 1024-bit. Ngoài ra, một sự phê bình khác về DSS là chữ ký được tạo ra nhanh hơn so với việc xác minh nó. Trái ngược với hệ chữ ký RSA thì việc xác minh công khai là rất nhanh chóng (mà ta biết trong thƣơng mại điện tử việc xác minh là rất quan trọng và đòi hỏi thời gian thực hiện phải nhanh chóng). 2.2.6 GIẢI PHÁP ỨNG DỤNG CHỮ KÝ ĐIỆN TỬ Phần này, em xin được đề xuất giải pháp ứng dụng chữ ký điện tử trong hệ thống quản lý. Quá trình gửi và nhận các tệp văn bản phục vụ quản lý dựa vào thuật toán băm MD5 và thuật toán mã hóa RSA. 2.2.6.1 Quá trình ký và gửi các tệp văn bản - Từ file cần gửi ban đầu, chương trình sẽ sử dụng hàm băm MD5 để mã hóa thành chuỗi ký tự dài 128 bit, hash value (gọi là bản tóm lược). - Chương trình sử dụng thuật toán RSA để mã hóa khóa riêng (private key) của người gửi và bản tóm lược hash value thành một dạng khác (giá trị băm ở dạng mật mã) gọi là chữ ký điện tử. - Kết hợp file ban đầu với chữ ký điện tử thành một thông điệp đã ký và gửi đi cho người nhận Hình 2.3. Sơ đồ mô tả quá trình ký và gửi các tệp văn bản 2.2.6.2 Quá trình nhận các tệp văn bản Sau khi người nhận đăng nhập vào hệ thống và thực hiện việc nhận các tệp văn bản. Hệ thống sẽ tách thông điệp đã ký thành ra file và chữ ký điện tử. Đến giai đoạn này sẽ có 2 quá trình kiểm tra : Kiểm tra file có đúng người gửi hay không? - Sử dụng thuật toán RSA để giải mã chữ ký điện tử bằng khóa công khai (username) của người gửi. - Nếu giải mã không được thì file nhận được không đúng người gửi. - Nếu giải mã thành công thì file nhận được đúng người gửi và có được Bản tóm lược 1 Kiểm tra file có bị thay đổi hay không? - Từ file được tách ra ta sử dụng hàm băm MD5 mã hóa thành Bản tóm lược 2. - Kiểm tra Bản tóm lược 1 và Bản tóm lược 2 có giống nhau hay không? Nếu giống nhau thì file nhận được là vẹn toàn (không bị thay đổi hay tác động), ngược lại là file đã bị thay đổi Hình 2.4. Sơ đồ mô tả quá trình nhận các tệp văn bản 2.2.7 VẬN DỤNG VÀO HỆ THỐNG Để vận dụng giải pháp này trong hệ thống gửi và nhận tệp văn bản chúng ta cần tìm hiểu thêm trong các tài liệu tham khảo, từ đó có thể lựa chọn, sử dụng các thuật toán, ngôn ngữ để xây dựng chương trình. Trong khuôn khổ một bài báo, chúng tôi giới thiệu tổng quan một số bước để xây dựng các hàm và thuật toán chính như sau: - Do sử dụng hàm băm MD5 để mã hóa văn bản gốc thành 32 kí tự nên kích thuớc của khóa có độ đài phải đủ lớn và trong thuật toán RSA có cả hàm mũ... nên ta cần xây dựng các hàm xử lý số có kích thước lớn với các phép toán cơ bản: cộng, trừ, nhân, chia, modulo… - Xây dựng thuật toán phát sinh số nguyên tố; - Xây dựng thuật toán chọn e, thuật toán chọn d; - Sử dụng khóa riêng (n, d) để tính toán chữ ký S = Md - Sử dụng khóa công khai của người gửi (n, e) để tính toán lại M = S mod n; - Xây dựng các hàm gửi và nhận file... 2.2.8 KẾT LUẬN Chữ ký điện tử là nền tảng để bảo đảm an ninh trong lĩnh vực thương mại điện tử, các phần mềm quản lý có kiến trúc kiểu Client/Server. Chúng tôi đã nêu được quy trình ứng dụng chữ ký điện tử trên cơ sở kết hợp giữa thuật toán băm MD5 và thuật toán mã hóa RSA. Từ đó, chúng tôi đã đề ra giải pháp ứng dụng chữ ký điện tử trong phần mềm quản lý cụ thể là quá trình gửi và nhận các tệp văn bản. Từ giải pháp này, ta có thể xây dựng và cài đặt các hàm sử dụng tính năng của chữ ký điện tử trong quá trình gửi và nhận các tệp văn bản ứng dụng cho các hệ thống quản lý nhằm đảm bảo tính bảo mật của hệ thống. CHƯƠNG 3 : TỔNG QUAN VỀ HÀM BĂM VÀ THUẬT TOÁN HÀM BĂM MD5 2.3.1 ĐẶT VẤN ĐỀ Trên thực tế, các thông điệp sử dụng chữ ký điện tử có độ dài bất kỳ, thậm chí lên đến vài Megabyte. Trong khi đó, thuật toán chữ ký điện tử được trình bày trên đây lại áp dụng trên các thông điệp có độ dài cố định và thường tương đối ngắn, chẳng hạn như phương pháp DSS sử dụng chữ ký 320 bit trên thông điệp 160 bit. Để giải quyết vấn đề này, chúng ta có thể chia nhỏ thông điệp cần ký thành các đoạn nhỏ có độ dài thích hợp và ký trên từng mảnh thông điệp này. Tuy nhiên, giải pháp này lại có nhiều khuyết điểm và không thích hợp áp dụng trong thực tế: Nếu văn bản cần được ký quá dài thì số lượng chữ ký được tạo ra sẽ rất nhiều và kết quả nhận được là một thông điệp có kích thước rất lớn. Chẳng hạn như khi sử dụng phương pháp DSS thì thông điệp sau khi được ký sẽ có độ dài gấp đôi văn bản nguyên thủy ban đầu. Hầu hết các phương pháp chữ ký điện tử có độ an toàn cao đều đòi hỏi chi phí tính toán cao và do đó, tốc độ xử lý rất chậm. Việc áp dụng thuật toán tạo chữ ký điện tử nhiều lần trên một văn bản sẽ thực hiện rất lâu. Từng đoạn văn bản sau khi được ký có thể dễ dàng bị thay đổi thứ tự hay bỏ bớt đi mà không làm mất đi tính hợp lệ của văn bản. Việc chia nhỏ văn bản sẽ không thể bảo đảm được tính toàn vẹn của thông tin ban đầu cần được ký. 2.3.2 GIỚI THIỆU VỀ HÀM BĂM MẬT MÃ Hàm băm mật mã là một thủ tục tất định có đầu vào là khối dữ liệu bất kỳ và trả về một xâu bit có độ dài cố định, gọi là giá trị băm (mật mã), mà bất kỳ sự thay đổi vô tình hay các ý trên dữ liệu sẽ thay đổi giá trị băm. Dữ liệu đem mã hóa thường được gọi là thông điệp (message), và giá trị băm đôi khi còn được gọi là tóm lược thông điệp (message digest) hay giá trị tóm lược (digest). Hàm băm mật mã lý tưởng có 4 tính chất chính sau: • dễ dàng tính giá trị băm với bất kỳ thông điệp cho trước nào, • không thể tìm được một thông điệp từ một giá trị băm cho trước, • không thể sửa được một thông điệp mà không làm thay đổi giá trị băm của nó, • không thể tìm ra 2 thông điệp khác nhau mà có cùng giá trị băm. Hàm băm mật mã có rất nhiều ứng dụng trong an toàn thông tin, nhất là cho chữ ký điện tử (Digital Signatures), mã xác thực thông điệp (MACs – Message Authentication Codes), và một số dạng xác thực khác. Chúng cũng có thể sử dụng như các hàm băm thông thường, để đánh chỉ số dữ liệu trong bảng băm: như điểm chỉ, để nhận diện dữ liệu lặp hay xác định tệp dữ liệu duy nhất: hay như checksums để nhận biết sự thay đổi dữ liệu. Thật vậy, trong lĩnh vực an toàn thông tin, giá trị băm mật mã đôi khi được gọi điểm chỉ (số), checksums, hay giá trị băm, dù rằng tất cả các thuật ngữ này chỉ đại diện về mặt chức năng nhưng các tính 2.3.2.1. Tính chất Hầu hết các hàm băm mật mã được thiết kế với đầu xâu đầu vào có độ dài tùy ý và kết quả đầu ra là một giá trị băm có độ dài cố định. Hàm băm mật mã phải có thể chống lại được tất cả các kiểu tấn công phân tích đã biết. Tối thiểu, nó phải có các tính chất sau: Kháng tiền ảnh (Preimage resistance): cho trước một giá trị băm h, khó tìm ra thông điệp m thỏa mã h = hash(m). Khái niệm như là hàm một chiều (one way function). Các hàm thiếu tính chất này sẽ bị tổn thương bởi các tấn công tiền ảnh (preimage attacks). Kháng tiền ảnh thứ 2 (Second preimage resistance): cho trước một đầu vào m1, khó có thể tìm ra đầu vào m2 khác (không bằng m1) thỏa mãn hash(m1) = hash(m2). Tính chất này đôi khi như là kháng va chạm yếu (weak collision resistance). Các hàm thiếu tính chất này sẽ bị tổn thương bởi các tấn công tiền ảnh thứ 2 (second preimage attacks). Kháng va chạm (Collision resistance): khó có thể tìm ra 2 thông điệp m1 và m2 thỏa mãn hash(m1) = hash(m2). Một cặp như vậy được gọi là một va chạm băm (mật mã), và tính chất này đôi khi như là kháng va chạm mạnh (strong collision resistance). Tính chất này yêu cầu rằng một giá trị băm tối thiểu cũng mạnh hơn yêu cầu kháng tiền ảnh, hơn nữa các va chạm có thể tìm được bởi tấn công ngày sinh (birthday attack). Các tính chất trên nói lên rằng đối phương ác ý không thể thay hoặc sửa dữ liệu đầu vào mà không làm thay đổi giá trị tóm lược của nó. Do đó, nếu 2 xâu có cùng một giá trị tóm lược, thì người ta tin tưởng rằng chúng là giống nhau. Một hàm có các tiêu chí này vẫn có thể có các tính chất không mong muốn. Hiện tại các hàm băm mật mã thông thường vẫn bị tổn thương bởi các tấn công mở rộng độ dài (length-extension attacks): cho trước h(m) và len(m) nhưng không biết m, bằng cách chọn m’ hợp lý, kẻ tấn công có thể tính h(m || m’), với || ký hiệu là phép ghép xâu. Tính chất này có thể được sử dụng để phá vỡ các lược đồ xác thực đơn giản dựa vào hàm băm. Cấu trúc HMAC (Hash Message Authentication Code) gặp phải các vấn đề như vậy. Về mặt lý tưởng, người ta có thể muốn các điều kiện mạnh hơn. Kẻ tấn công không thể tìm ra 2 thông điệp có các giá trị tóm lược gần giống nhau; hoặc luận ra bất kỳ thông tin có ích nào về dữ liệu, mà chỉ cho trước giá trị tóm lược. Do đó, hàm băm mật mã phải tiến gần tới hàm ngẫu nhiên (đến mức có thể) mà vẫn là tất định và tính toán hiệu quả. Thuật toán checksum, như là CRC32 và các CRC (Cyclic Redundancy Check) khác, được thiết kế nhiều yêu cầu yếu hơn, và nói chung không giống như là các hàm băm mật mã. Ví dụ, có một CRC đã được sử dụng kiểm tra tính toàn vẹn trong chuẩn mã WEP (Wired Equivalent Privacy), nhưng đã có một tấn công khai thác tính tuyến tính của checksum. 2.3.2.2 Ứng dụng Một ứng dụng tiêu biểu của hàm băm mật mã sẽ như sau: Alice đặt ra một bài toán khó cho Bob, và tuyên bố rằng cô ta đã giải được. Bob sẽ phải cố gắng tự thực hiện, nhưng chưa dám chắc rằng Alice không giải sai. Do đó, Alice viết ra lời giải của mình, gắn thêm một giá trị nonce ngẫu nhiên, tính giá trị băm của nó và cho Bob biết giá trị băm đó (giữ bí mật lời giải và giá trị nonce). Bằng cách này, khi Bob tìm ra lời giải của mình vài ngày sau đó, Alice có thể chứng minh rằng cô ta có lời giải sớm hơn bằng cách tiết lộ giá trị nonce cho Bob. (Đây là một ví dụ về một lược đồ cam kết đơn giản trong thực tế, vai trò của Alice và Bob thường sẽ là các chương trình máy tính, và bí mật sẽ là một cái gì đó dễ dàng giả mạo hơn là một bài toán đó theo yêu cầu). Một ứng dụng quan trọng của băm an toàn là xác minh tính toàn vẹn của thông điệp. Xác định liệu có thay đổi nào đã được thực hiện đối với thông điệp (hoặc một tập tin), ví dụ, có thể được thực hiện bằng cách so sánh các giá trị tóm lược thông điệp đã tính toán trước, và sau đó, truyền đi (hoặc sự kiện nào đó). Một giá trị tóm lược thông điệp cũng có thể phục vụ như là một phương tiện nhận dạng một tập tin đáng tin cậy một số hệ thống quản lý mã nguồn, bao gồm Git, Mercurial và Monotone, sử dụng giá trị sha1sum của nhiều dạng nội dung khác nhau (nội dung tập tin, cây thư mục, vv) để nhận dạng chúng một cách duy nhất duy nhất.Một ứng dụng khác liên quan tới việc xác thực mật khẩu. Mật khẩu thường không được lưu trữ dạng văn bản rõ, với các lý do hiển nhiên, mà thay bằng dạng giá trị tóm lược. Để xác thực người dùng, mật khẩu đại diện cho người sử dụng được băm và so sánh với giá trị băm lưu trữ. Điều này đôi khi được gọi là phép mã hóa một chiều (one-way encryption). Đối với cả hai lý do bảo mật và hiệu suất, hầu hết các thuật toán chữ ký số chỉ định rằng chỉ giá trị tóm lược của thông báo được "ký", chứ không phải toàn bộ thông báo. Các hàm băm cũng có thể được sử dụng trong việc tạo các bit giả ngẫu nhiên (pseudorandom) Các giá trị băm còn được sử dụng để nhận dạng tập tin trên mạng chia sẻ peer-to-peer. Ví dụ, trong một liên kết ed2k, một giá trị băm MD4-biến thể được kết hợp với kích thước tập tin, cung cấp đủ thông tin để định vị các nguồn tập tin, tải các tập tin và xác nhận nội dung của nó. (Trong máy tính, các liên kết ed2k là các hyperlinks được sử dụng để biểu thị các tập tin được lưu trữ trong mạng eDonkey P2P.) Các liên kết Magnet là một ví dụ khác. Các giá trị băm tập tin như vậy thường là băm đầu danh sách băm hoặc cây băm để có thêm nhiều tiện lợi. 2.3.3 HÀM BĂM DỰA TRÊN MÃ KHỐI Có một số phương pháp sử dụng thuật toán mã khối để xây dựng một hàm băm mật mã, cụ thể nó là hàm nén một chiều (one-way compression function).Các phương pháp tương tự như các chế độ hoạt động của mã khối sử dụng cho phép mã. Tất cả các hàm băm đã biết, bao gồm MD4, MD5, SHA-1 và SHA-2 được xây dựng từ các thành phần giống mã khối, chúng được thiết kế riêng cho mục đích này, với thông tin phản hồi để bảo đảm rằng các hàm nhận được là không song ánh. Một thuật toán mật mã khối chuẩn như AES có thể được sử dụng thay cho những thuật toán mật mã khối tùy chỉnh điều này thường phải trả giá về hiệu năng, nhưng có thể được thuận lợi khi hệ thống cần thực hiện băm mật mã và chức năng mật mã khác như mã hóa đều có thể sử dụng chung một thuật toán mã khối, nhưng bị hạn chế ở kích thước mã hoặc phần cứng phải phù hợp với nó, chẳng hạn như trong một số hệ thống nhúng như thẻ thông minh. CẤU TRÚC MERKLE-DAMGARD Một hàm băm phải có thể xử lý thông điệp độ dài tùy ý cho kết quả đầu ra có độ dài cố định. Điều này có thể đạt được bằng cách chặt đầu vào thành chuỗi các khối có kích thước bằng nhau, và tác động vào chúng theo thứ tự bằng cách sử dụng một hàm nén một chiều. Hàm nén hoặc có thể được thiết kế đặc biệt cho băm hoặc được xây dựng từ một thuật toán mã khối. Một hàm băm được xây dựng với cấu trúc Merkle-Damgård có khả năng kháng va chạm dựa vào hàm nén của nó; bất kỳ va chạm nào đối với hàm băm đầy đủ có thể đều bắt nguồn từ một va chạm trong các hàm nén. Hình 3.1 Cấu trúc băm Merkle-Damgård. Khối cuối xử lý cũng phải được thêm cho đủ độ dài khối; điều này rất quan trọng đối với tính an toàn của cấu trúc Merkle-Damgård. Hầu hết các hàm băm phổ dụng, bao gồm SHA-1 và MD5, thực hiện theo cấu trúc này. Cấu trúc trên vẫn tiềm ẩn lỗi cố hữu, bao gồm các tấn công mở rộng độ dài và các tấn công tạo-và-dán, và không thể song song được. Kết quả là, có nhiều ứng cử viên trong cuộc thi về hàm băm mật mã của NIST được xây dựng dựa trên các kiến trúc khác. 2.3.5 BIRTHDAY ATTACK Như đã biết, một dạng tấn công có khả năng đối với các hệ chữ ký điện tử có dùng hàm Băm là tìm cách tạo ra những văn bản x và x’ có nội dung khác nhau (một có lợi và một là bất lợi cho bên ký) mà giá trị Băm giống nhau. Kẻ địch có thể tìm cách tạo ra một số lượng rất lớn các văn bản có nội dung không thay đổi nhưng khác nhau về biểu diễn nhị phân (đơn giản là việc thêm bớt khoảng trắng hay dùng nhiều từ đồng nghĩa để thay thế ...), sau đó sử dụng một chương trình máy tính để tính giá trị Băm của các văn bản đó và đem so sánh với nhau để hi vọng tìm ra một cặp văn bản đụng độ (sử dụng phương pháp thống kê). Nhưng việc này đòi hỏi số văn bản cần được tính giá trị Băm phải lớn hơn kích thước không gian Băm rất nhiều. Chẳng hạn như nếu hàm Băm có không gian Băm 64-bit thì số lượng văn bản cần được đem ra nạp vào chương trình phải ít nhất 264 (với một máy tính có thể thực hiện việc Băm 1 triệu bức điện trong 1 giây, thì phải mất 6000.000 năm tính toán. Tuy nhiên nếu kẻ địch thử với lượng văn bản ít hơn nhiều, trong phạm vi có thể tính được thì xác suất để tìm được đụng độ sẽ như thế nào? Câu trả lời là “có thể thực hiện được”. Bản chất của hiện tượng này được minh hoạ rõ thông qua phát biểu sau, thường được gọi là nghịch lý ngày sinh (birthday paradox) HÀM BĂM MẬT MÃ Hàm băm mật mã là hàm toán học chuyển đổi một thông điệp có độ dài bất kỳ thành một dãy bit có độ dài cố định (tùy thuộc vào thuật toán băm). Dãy bit này được gọi là thông điệp rút gọn (message digest) hay giá trị băm (hash value), đại diện cho thông điệp ban đầu. Dễ dàng nhận thấy rằng hàm băm h không phải là một song ánh. Do đó, với thông điệp x bất kỳ, tồn tại thông điệp x’ ≠ x sao cho h(x)= h(x’). Lúc này, ta nói rằng “có sự đụng độ xảy ra”. Một hàm băm h được gọi là an toàn (hay “ít bị đụng độ”) khi không thể xác định được (bằng cách tính toán) cặp thông điệp x và x’ thỏa mãn x≠x’ và h(x) = h(x’). Trên thực tế, các thuật toán băm là hàm một chiều, do đó, rất khó để xây dựng lại thông điệp ban đầu từ thông điệp rút gọn. Hàm băm giúp xác định được tính toàn vẹn dữ liệu của thông tin: mọi thay đổi, dù là rất nhỏ, trên thông điệp cho trước, ví dụ như đổi giá trị 1 bit, đều làm thay đổi thông điệp rút gọn tương ứng. Tính chất này hữu ích trong việc phát sinh, kiểm tra chữ ký điện tử, các đoạn mã chứng nhận thông điệp, phát sinh số ngẫu nhiên, tạo ra khóa cho quá trình mã hóa… Hàm băm là nền tảng cho nhiều ứng dụng mã hóa. Có nhiều thuật toán để thực hiện hàm băm, trong số đó, phương pháp SHA-1 và MD5 thường được sử dụng khá phổ biến từ thập niên 1990 đến nay. Hàm băm MD4 (Message Digest 4) và MD5 (Message Digest 5): • Hàm băm MD4 được Giáo sư Ron Rivest đề nghị vào năm 1990. Vào năm 1992, phiên bản cải tiến MD5 của thuật toán này ra đời. • Thông điệp rút gọn có độ dài 128 bit. • Năm 1995, Hans Dobbertin đã chỉ ra sự đụng độ ngay chính trong bản thân hàm nén của giải thuật (mặc dù chưa thật sự phá vỡ được giải thuật). Năm 2004, nhóm tác giả Xiaoyun Wang, Dengguo Feng, Xuejia Lai và Hongbo Yu đã công bố kết quả về việc phá vỡ thuật toán MD4 và MD5 bằng phương pháp tấn công đụng độ Phương pháp Secure Hash Standard (SHS): • Phương pháp Secure Hash Standard (SHS) do NIST và NSA xây dựng được công bố trên Federal Register vào ngày 31 tháng 1 năm 1992 và sau đó chính thức trở thành phương pháp chuẩn từ ngày 13 tháng 5 năm 1993. • Thông điệp rút gọn có độ dài 160 bit. Ngày 26/08/2002, Viện Tiêu chuẩn và Công nghệ quốc gia của Hoa Kỳ (National Institute of Standard and Technology - NIST) đã đề xuất hệ thống chuẩn hàm băm an toàn (Secure Hash Standard) gồm 4 thuật toán hàm băm SHA-1, SHA-256, SHA-384, SHA-512. Đến 25/03/2004, NIST đã chấp nhận thêm thuật toán hàm băm SHA-224 vào hệ thống chuẩn hàm băm. Các thuật toán hàm băm do NIST đề xuất được đặc tả trong tài liệu FIPS180-2 CẤU TRÚC HÀM BĂM Hầu hết các hàm băm mật mã đều có cấu trúc giải thuật như sau: Cho trước một thông điệp M có độ dài bất kỳ. Tùy theo thuật toán được sử dụng, chúng ta có thể cần bổ sung một số bit vào thông điệp này để nhận được thông điệp có độ dài là bội số của một hằng số cho trước. Chia nhỏ thông điệp thành từng khối có kích thước bằng nhau: M1, M2, …Ms Gọi H là trạng thái có kích thước n bit, f là “hàm nén” thực hiện thao tác trộn khối dữ liệu với trạng thái hiện hành. Khởi gán H0 bằng một vector khởi tạo nào đó Hi = f(Hi-1,M) với i = 1, 2, 3, …, s Hs chính là thông điệp rút gọn của thông điệp M ban đầu 2.3.8 TÍNH AN TOÀN HÀM BĂM VÀ HIỆN TƯỢNG ĐỤNG ĐỘ Hàm băm được xem là an toàn đối với hiện tượng đụng độ khi rất khó tìm được hai thông điệp có cùng giá trị băm. Nhận xét: Trong một tập hợp mà các phần tử mang một trong N giá trị cho trước với xác suất bằng nhau, chúng ta cần khoảng N phép thử ngẫu nhiên để tìm ra một cặp phần tử có cùng giá trị. Như vậy, phương pháp hàm băm được xem là an toàn đối với hiện tượng đụng độ nếu chưa có phương pháp tấn công nào có thể tìm ra cặp thông điệp có cùng giá trị hàm băm với số lượng tính toán ít hơn đáng kể so với ngưỡng 2n/2, với n là kích thước (tính bằng bit) của giá trị băm. Phương pháp tấn công dựa vào đụng độ: • Tìm ra 2 thông điệp có nội dung khác nhau nhưng cùng giá trị băm. • Ký trên một thông điệp, sau đó, người ký sẽ không thừa nhận đây là chữ ký của mình mà nói rằng mình đã ký trên một thông điệp khác. • Như vậy, cần phải chọn 2 thông điệp “đụng độ” với nhau trước khi ký. 2.3.9 TÍNH MỘT CHIỀU Hàm băm được xem là hàm một chiều khi cho trước giá trị băm, không thể tái tạo lại thông điệp ban đầu, hay còn gọi là “tiền ảnh” (“pre-image”). Như vậy, trong trường hợp lý tưởng, cần phải thực hiện hàm băm cho khoảng 2n thông điệp để tìm ra được “tiền ảnh” tương ứng với một giá trị băm. Nếu tìm ra được một phương pháp tấn công cho phép xác định được “tiền ảnh” tương ứng với một giá trị băm cho trước thì thuật toán băm sẽ không còn an toàn nữa. Cách tấn công nhằm tạo ra một thông điệp khác với thông điệp ban đầu nhưng có cùng giá trị băm gọi là tấn công “tiền ảnh thứ hai” (second pre-image attack). 2.3.10 SỬ DỤNG CHO CÁC NGUYÊN THỦY MẬT MÃ Các hàm băm có thể được dùng để xây dựng nguyên thủy mật mã khác. Tuy nhiên, để những nguyên thủy mật mã này được an toàn, thì cần phải chú ý xây dựng chúng theo đúng nguyên lý. Mã xác thực thông điêp (MACs) thường được xây dựng từ hàm băm. HMAC cũng dựa vào MAC. Cũng như thuật toán mã khối có thể được dùng để xây dựng hàm băm, hàm băm có thể được sử dụng để xây dựng các thuật toán mã khối. Cấu trúc Luby-Rackoff sử dụng các hàm băm xây dựng mã khối có thể chứng minh được an toàn nếu hàm băm mà nó dựa vào là an toàn. Ngoài ra, có nhiều hàm băm (bao gồm cả các hàm băm SHA) được xây dựng bằng cách sử dụng một thuật toán mã khối mục đích đặc biệt theo cấu trúc Davies-Meyer hoặc cấu trúc khác mã khối đó cũng có thể được sử dụng trong một chế độ hoạt động thông thường, mà không có sự đảm bảo an toàn tương tự  Bộ sinh số giả ngẫu nhiên (PRNGs) có thể được xây dựng dựa vào hàm băm. Điều này được thực hiện bằng cách kết hợp một mầm ngẫu nhiên (bí mật) với một bộ đếm và lấy giá trị băm của nó. Thuật toán mã dòng (tream cipher) có thể được xây dựng dựa vào các hàm băm. Thường điều này được thực hiện bằng cách: đầu tiên, xây dựng một Bộ sinh số số giả ngẫu nhiên an toàn mật mã sau đó, sử dụng dòng các byte ngẫu nhiên như là dòng khóa (keystream). SEAL là một thuật toán mã dòng sử dụng SHA-1 để tạo ra các bảng bên trong, mà sau đó được sử dụng trong một bộ sinh dòng khóa nhiều hay ít không liên quan đến các thuật toán băm SEAL không được đảm bảo tính mạnh (hay yếu) như SHA-1. 2.3.11 GHÉP CÁC HÀM BĂM MẬT MÃ Ghép các kết quả đầu ra từ nhiều hàm băm tạo ra tính kháng va chạm tối thiểu cũng tốt như là độ mạnh nhất của thuật toán trong các kết nối. Ví dụ, SSL sử dụng ghép nối MD5 và SHA-1 để đảm bảo giao thức đó sẽ vẫn an toàn thậm chí nếu một hàm băm bị phá vỡ. Tuy nhiên, với các hàm băm Merkle-Damgård, hàm ghép nối chỉ mạnh như các thành phần tốt nhất, chứ không mạnh hơn. Joux chỉ ra rằng 2-va chạm dẫn đến n-va chạm nếu dễ dàng tìm ra 2 thông điệp có cùng giá trị băm MD5, thì không khó để tìm thấy nhiều thông điệp khi kẻ tấn công muốn lấy các giá trị băm MD5 giống nhau. Trong số n thông điệp với cùng giá trị băm MD5, có khả năng có được một va chạm SHA-1. Nhưng công việc cần thực hiện thêm là tìm va chạm SHA-1 (làm sao để tốt hơn tìm kiếm ngày sinh) là đa thức. Lập luận này được tổng kết bởi Finney. 2.3.12 THUẬT TOÁN BĂM MẬT MÃ Có một danh sách dài các hàm băm mật mã, mặc dù trong đó có nhiều hàm băm được cho là dễ bị tổn thương và không nên sử dụng. Ngay cả khi một hàm băm chưa bị phá vỡ, một tấn công thành công đối với một biến thể yếu đó có thể làm giảm sự tự tin của các chuyên gia và dẫn đến loại bỏ nó. Ví dụ, vào tháng 8 năm 2004 người ta đã tìm ra những điểm yếu của một vài hàm băm phổ biến vào thời đó, bao gồm SHA-0, RIPEMD, và MD5. Điều này đã đặt ra câu hỏi an ninh lâu dài của các thuật toán sau này được bắt nguồn từ những hàm băm này - đặc biệt, SHA-1 (một phiên bản mạnh của SHA-0), RIPEMD-128, và RIPEMD-160 (cả hai phiên bản mạnh của RIPEMD). Vì vậy, cả SHA-0 và RIPEMD đều không được sử dụng rộng rãi kể từ khi chúng được thay thế bởi các phiên bản mạnh. Đến năm 2009, hai hàm băm mật mã được sử dụng thông dụng nhất vẫn là MD5 và SHA-1. Tuy nhiên, MD5 đã bị phá vỡ do có một tấn công lên nó để phá vỡ SSL trong năm 2008 SHA-0 và SHA-1 là các thành viên của họ hàm băm SHA được phát triển bởi NSA. Vào tháng 2 năm 2005, đã tấn công thành công trên SHA-1, việc tìm kiếm va chạm trong khoảng 269 phép toán băm, thay vì 280 theo dự kiến cho hàm băm 160-bit. Vào tháng 8 năm 2005, có một tấn công thành công trên SHA-1 trong đó việc tìm kiếm va chạm chỉ cần 263 phép toán băm. Điểm yếu lý thuyết của SHA-1 tồn tại vốn có, nhưng gợi ý rằng có thể thực hiện về mặt thực tế để phá vỡ nó cũng phải mất vài năm. Các ứng dụng mới có thể tránh được những vấn đề này bằng cách sử dụng thêm các thành viên tiên tiến của họ SHA, như SHA-2, hoặc sử dụng các kỹ thuật như băm ngẫu nhiên hóa sẽ công quan tâm đến kháng va chạm. Tuy nhiên, để đảm bảo tính chất mạnh lâu dài của các ứng dụng có sử dụng hàm băm, hiện có một cuộc thi nhằm thiết kế hàm băm thay thế cho SHA-2, nó sẽ có tên là SHA-3 và trở thành một tiêu chuẩn FIPS vào năm 2012 2.3.13 PHƯƠNG PHÁP SECURE HASH STANDARD (SHS) Phương pháp Secure Hash Standard (SHS) do NIST và NSA xây dựng được công bố trên Federal Register vào ngày 31 tháng 1 năm 1992 và sau đó chính thức trở thành phương pháp chuẩn từ ngày 13 tháng 5 năm 1993. Nhìn chung, SHS được xây dựng trên cùng cơ sở với phương pháp MD4 và MD5. Tuy nhiên, phương pháp SHS lại áp dụng trên hệ thống big-endian thay vì little-endian như phương pháp MD4 và MD5. Ngoài ra, thông điệp rút gọn kết quả của hàm băm SHS có độ dài 160 bit (nên phương pháp này thường được sử dụng kết hợp với thuật toán DSS). 2.3.14 MỘT SỐ HÀM BĂM NỔI TIẾNG Hàm băm MD4 (Message Digest 4) Hàm băm MD5 (Message Digest 5) SHS (Secure Hash Standard) Hàm băm Davies-Mayer Hàm AES-Hash Hàm băm Davies-Mayer và AES-Hash SHA-1… 2.3.15 HÀM BĂM MD5 2.3.15.1 Giới thiệu : Hàm băm MD4 (Message Digest 4) được Giáo sư Rivest đề nghị vào năm 1990. Vào năm sau, phiên bản cải tiến MD5 của thuật toán này ra đời. Cùng với phương pháp SHS, đây là ba phương pháp có ưu điểm tốc độ xử lý rất nhanh nên thích hợp áp dụng trong thực tế đối với các thông điệp dài. Thông điệp ban đầu x sẽ được mở rộng thành dãy bit X có độ dài là bội số của 512. Một bit 1 được thêm vào sau dãy bit x, tiếp đến là dãy gồm d bit 0 và cuối cùng là dãy 64 bit l biểu diễn độ dài của thông điệp x. Dãy gồm d bit 0 được thêm vào sao cho dãy X có độ dài là bội số 512. 2.3.15.2 Khái niệm 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 (cũng do ông thiết kế, trước đó nữa là MD2). Ứng dụng Md5 có 2 ứng dụng quan trọng: 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. 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). Thuật giải 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ó sẻ chia hết cho 512. Bộ đệm hoạt động như sau: - Trước tiên chèn bit 1 vào cuối thông điệp. - 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 . - 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. 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 từ 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. 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… Hình bên dưới 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àm băm MD5 (còn được gọi là hàm tóm tắt thông điệp - message degests) sẻ trả về một chuổi số thập lục phân gồm 32 số liên tiếp. Dưới đây là các ví dụ mô tả các kết quả thu được sau khi băm. MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6 Thậm chỉ chỉ cần một thay đổi nhỏ cũng làm thay đổi hoàn toàn kết quả trả về: MD5("The quick brown fox jumps over the lazy cog") = 1055d3e698d289f2af8663725127bd4b Ngay cả một chuổi rổng cũng cho ra một kết quả phức tạp: MD5(" ") = d41d8cd98f00b204e9800998ecf8427e 2.3.16 MD5 (Message Digest) Ronald Rivest là người đã phát minh ra các hàm Băm MD2, MD4 (1990) và MD5 (1991). Do tính chất tương tự của các hàm Băm này, sau đây chúng ta sẽ xem xét hàm Băm MD5, đây là một cải tiến của MD4 và là hàm Băm được sử dung rộng rãi nhất, nguyên tắc thiết kế của hàm băm này cũng là nguyên tắc chung cho rất nhiều các hàm băm khác Miêu tả MD5: Đầu vào là những khối 512-bit, được chia cho 16 khối con 32-bit. Đầu ra của thuật toán là một thiết lập của 4 khối 32-bit để tạo thành một hàm Băm 128-bit duy nhất. Đầu tiên, ta chia bức điện thành các khối 512-bit, với khối cuối cùng (đặt là x và x <512-bit) của bức điện, chúng ta cộng thêm một bit 1 vào cuối của x, theo sau đó là các bit 0 để được độ dài cần thiết (512 bit). Kết quả là bức điện vào là một chuỗi M có độ dài chia hết cho 512, vì vậy ta có thể chia M ra thành các N word 32-bit (N word này sẽ chia hết cho 16). Bây giờ, ta bắt đầu tìm cốt của bức điện với 4 khối 32-bit A, B, C và D (được xem như thanh ghi) : A = 0x01234567 B = 0x89abcdef C = 0xfedcba98 D = 0x76543210. Người ta thường gọi A, B, C, D là các chuỗi biến số (chaining variables). Khối của bức điện Vòng 1 Vòng 2 Vòng 3 Vòng 4 A BCD A BCD Hình 3.2: Sơ đồ vòng lặp chính của MD5 Bức điện được chia ra thành nhiều khối 512-bit, mỗi khối 512-bit lại được chia ra 16 khối 32-bit đi vào bốn vòng lặp của MD5. Giả sử ta đặt a, b, c và d thay cho A, B, C và D đối với khối 512-bit đầu tiên của bức điện. Bốn vòng lặp trong MD5 đều có cấu trúc giống nhau. Mỗi vòng thực hiện 16 lần biến đổi: thực hiện với một hàm phi tuyến của 3 trong 4 giá trị a, b, c và d sau đó nó cộng kết quả đến giá trị thứ 4, tiếp đó cộng với một khối con 32-bit và một hằng số. Sau đó, nó dịch trái một lượng bit thay đổi và cộng kết quả vào một trong 4 giá trị a, b, c hay d. Kết quả cuối cùng là một giá trị mới được thay thế một trong 4 giá trị a, b, c hay d. Hàm phi tuyến a b d c <<<S Mj ti Hình 3.3: Sơ đồ 1 vòng lặp của MD5 F Có bốn hàm phi tuyến, mỗi hàm này được sử dụng cho mỗi vòng: F (X, Y, Z) = (X Ù Y) Ú ((Ø X) Ù Z) G(X, Y, Z) = (X Ù Z) Ú ((Ø Z) Ù Y) H (X, Y, Z) = X Å Y Å Z I (X, Y, Z) = Y Å (X Ú (¬Z)) quy ước: X Ù Y Phép toán AND trên bit giữa X và Y X Ú Y Phép toán OR trên bit giữa X và Y X Å Y Phép toán XOR trên bit giữa X và Y ¬X Phép toán NOT trên bit của X X + Y Phép cộng (modulo ) X <<< s Các bit của X được dịch chuyển xoay vòng sang trái s vị trí (0 ≤ s < 32) Những hàm này được thiết kế sao cho các bit tương ứng của X, Y và Z là độc lập và không ưu tiên, và mỗi bit của kết quả cũng độc lập và ngang bằng nhau. Nếu Mj là một biểu diễn của khối con thứ j (j = 16) và <<<s là phép dịch trái của s bit, thì các vòng lặp có thể biểu diễn như sau: FF(a,b,c,d,Mj,s,ti) được biểu diễn a = b + ((a + F(b,c,d) + Mj + ti)<<<s) GG(a,b,c,d,Mj,s,ti)được biểu diễn a=b + ((a + G(b,c,d) + Mj + ti) <<<s) HH(a,b,c,d,Mj,s,ti) được biểu diễn a=b+ ((a+H(b,c,d) + Mj + ti) <<< s) II(a,b,c,d,Mj,s,ti) được biểu diễn a = b + ((a + I(b,c,d) + Mj + ti) <<< s). Cách thực hiện: Bốn vòng (64 bước) sẽ thực hiện như sau: Vòng 1: FF (a, b, c, d, M0, 7, 0x76aa478) FF (d, a, b, c, M1, 12, 0xe8c7b756) FF (c, d, a, b, M2, 17, 0x242070db) FF (b, c, d, a, M3, 22, 0xc1bdceee) FF (a, b, c, d, M4, 7, 0xf57c0faf) FF (d, a, b, c, M5, 12, 0x4787c62a) FF (c, d, a, b, M6, 17, 0xa8304613) FF (b, c, d, a, M7, 22, 0xfd469501) FF (a, b, c, d, M8, 7, 0x698098d8) FF (d, a, b, c, M9, 12, 0x8b44f7af) FF (c, d, a, b, M10, 17, 0xffff5bb1) FF (b, c, d, a, M11, 22, 0x895cd7be) FF (a, b, c, d, M12, 7, 0x6b901122) FF (d, a, b, c, M13, 12, 0xfd987193) FF (c, d, a, b, M14, 17, 0xa679438e) FF (b, c, d, a, M15, 22, 0x49b40821). Vòng 2: GG (a, b, c, d, M1, 5, 0x61e2562) GG (d, a, b, c, M6, 9, 0xc040b340) GG (c, d, a, b, M11, 14, 0x265e5a51) GG (b, c, d, a, M0, 20, 0xe9b6c7aa) GG (a, b, c, d, M5, 5, 0xd62f105d) GG (d, a, b, c, M10, 9, 0x02441453) GG (c, d, a, b, M15, 14, 0xd8a1e681) GG (b, c, d, a, M4, 20, 0xe7d3fbc8) GG (a, b, c, d, M9, 5, 0x21e1cde6) GG (d, a, b, c, M14, 9, 0xc33707d6) GG (c, d, a, b, M3, 14, 0xf4d50d87) GG (b, c, d, a, M8, 20, 0x455a14ed) GG (a, b, c, d, M13, 5, 0xa9e3e905) GG (d, a, b, c, M2, 9, 0xfcefa3f8) GG (c, d, a, b, M7, 14, 0x676f02d9) GG (b, c, d, a, M12, 20, 0x8d2a4c8a). Vòng 3: HH (a, b, c, d, M5, 4, 0xfffa3942) HH (d, a, b, c, M8, 11, 0x8771f681) HH (c, d, a, b, M11, 16, 0x6d9d6122) HH (b, c, d, a, M14, 23, 0xfde5380c) HH (a, b, c, d, M1, 4, 0xa4beea44) HH (d, a, b, c, M4, 11, 0x4bdecfa9) HH (c, d, a, b, M7, 16, 0xf6bb4b60) HH (b, c, d, a, M10, 23, 0xbebfbc70) HH (a, b, c, d, M13, 4, 0x289b7ec6) HH (d, a, b, c, M0, 11, 0xeaa127fa) HH (c, d, a, b, M3, 16, 0xd4ef3085) HH (b, c, d, a, M6, 23, 0x04881d05) HH (a, b, c, d, M9, 4, 0xd9d4d039) HH (d, a, b, c, M12, 11, 0xe6db99e5) HH (c, d, a, b, M15, 16, 0x1fa27cf8) HH (b, c, d, a, M2, 23, 0xc4ac5665). Vòng 4: II (a, b, c, d, M0, 6, 0xf4292244) II (d, a, b, c, M7, 10, 0x432aff97) II (c, d, a, b, M14, 15, 0xab9423a7) II (b, c, d, a, M5, 21, 0xfc93a039) II (a, b, c, d, M12, 6, 0x655b59c3) II (d, a, b, c, M3, 10, 0x8f0ccc92) II (c, d, a, b, M10, 15, 0xffeff47d) II (b, c, d, a, M1, 21, 0x85845dd1) II (a, b, c, d, M8, 6, 0x6fa87e4f) II (d, a, b, c, M15, 10, 0xfe2ce6e0) II (c, d, a, b, M6, 15, 0xa3013414) II (b, c, d, a, M13, 21, 0x4e0811a1) II (a, b, c, d, M4, 6, 0xf7537e82) II (d, a, b, c, M11, 10, 0xbd3af235) II (c, d, a, b, M2, 15, 0x2ad7d2bb) II (b, c, d, a, M9, 21, 0xeb86d391). Những hằng số ti được chọn theo quy luật sau: ở bước thứ i giá trị ti là phần nguyên của 232*abs(sin(i)), trong đó i = [0..63] được tính theo radian. Sau tất cả những bước này a, b, c và d lần lượt được cộng với A, B, C và D để cho kết quả đầu ra và thuật toán tiếp tục với khối dữ liệu 512-bit tiếp theo cho đến hết bức điện. Đầu ra cuối cùng là một khối 128-bit của A, B, C và D, đây chính là hàm Băm nhận được. SỰ KHÁC NHAU GIỮA MD4 VÀ MD5 MD4 chỉ có ba chu kỳ biến đổi trong khi MD5 được bổ sung thêm chu kỳ thứ tư giúp tăng mức độ an toàn. Mỗi thao tác trong từng chu kỳ biến đổi của MD5 sử dụng các hằng số ti phân biệt trong khi MD4 sử dụng hằng số chung cho mọi thao tác trong cùng chu kỳ biến đổi (Trong MD4, hằng số ti sử dụng trong mỗi chu kỳ lần lượt là 0, 0x5a827999, 0x6ed9eba1). Hàm G ở chu kỳ hai của MD4: G(X, Y, Z)=((X ∧ Y)∨(X ∧ Z)∨(Y ∧ Z)) được thay thế bằng ((X ∧ Z) ∨ (Y ∧ Z)) nhằm giảm tính đối xứng. Mỗi bước biến đổi trong từng chu kỳ chịu ảnh hưởng kết quả của bước biến đổi trước đó nhằm tăng nhanh tốc độ của hiệu ứng lan truyền (avalanche). Các hệ số dịch chuyển xoay vòng trong mỗi chu kỳ được tối ưu hóa nhằm tăng tốc độ hiệu ứng lan truyền. Ngoài ra, mỗi chu kỳ sử dụng bốn hệ số dịch chuyển khác nhau CHƯƠNG 4: XÂY DỰNG CHƯƠNG TRÌNH MÔ PHỎNG THUẬT TOÁN MD5 2.4.1 NHIỆM VỤ CỦA CHƯƠNG TRÌNH - Đưa ra thuật toán MD5 - Sơ đồ khối thuật toán MD5 - Kết quả mô phỏng của chương trình - Kết quả thực nghiệm 2.4.2 THUẬT TOÁN VÀ SƠ ĐỒ KHỐI 2.4.2.1 Thuật toán: Khởi gán các biến: h0 := 0x67452301. h1 := 0xEFCDAB89. h2 := 0x98BADCFE. h3 := 0x10325476. Hệ số quay trái R[i]của mỗi chu kỳ: R[ 0..15] := { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} R[16..31] := { 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} R[32..47] := { 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} R[48..63] := { 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21} Hằng số K[i] for i from 0 to 63 K[i] := floor(abs(sin(i + 1)) × (2 pow 32)) Tiền xử lý: Thêm bit 1 vào cuối thông điệp. Thêm vào k bit 0 sao cho độ dài thông điệp nhận được đồng dư 448 (mod 512). Thêm 64 bit biểu diễn độ dài của thông điệp gốc(giá trị lưu dạng big-endian). Quá trình xử lý: Chia thông điệp (đã padding) thành các khối 512 bit Với mỗi khối 512-bit: Chia thành 16 word (32 bit, little-endian) w[0..15] A= h0, B= h1, C= h2, D= h3 64 chu kỳ xử lý h0+=A, h1+=B, h2+=C, h3+=D Kết quả:= h0 | h1 | h2 | h3 Chu kỳ xử lý trong MD5 Trong đó: t là số thứ tự của chu kỳ. A, B, C, D, là 4 word (32 bit) của trạng thái. F là hàm phi tuyến (thay đổi tùy theo chu kỳ). Đầu tiên, bốn biến A, B, C, D được khởi tạo. Những biến này được gọi là chaining variables. Bốn chu kỳ biến đổi trong MD5 hoàn toàn khác nhau và lần lượt sử dụng các hàm F, G, H và I. Mỗi hàm có tham số X, Y, Z là các từ 32 bit và kết quả là một từ 32 bit. <<< s là phép quay trái s vị trí. ⊞ phép cộng modulo 232. Mã giả thuật toán md5 H0 = 0x67452301; H1 = 0xEFCDAB89; H2 = 0x98BADCFE; H3 = 0x10325476; for i from 0 to 63 f = F[i] (B, C, D) g = G[i] (i) temp = D D = C C = B B = ((A + f + K[i] + w[g]) <<< R[i]) + B A = temp 0 ≤ i ≤ 15 f := (B Ù C) Ú ((Ø B) Ù D) g := i 16 ≤ i ≤ 31 f := (D Ù B) Ú ((Ø D) Ù C) g := (5×i + 1) mod 16 32 ≤ i ≤ 47 f := B Å C Å D g := (3×i + 5) mod 16 48 ≤ i ≤ 63 f := C Å (B Ú (Ø D)) g := (7×i) mod 16 2.4.2.2 SƠ ĐỒ KHỐI THUẬT TOÁN MD5 F T Begin H0:=0x67452301 H1:=0xEFCDAB89 H2:=0x98BADCFE H3:=0x10325476 Chia thông điệp thành M khối 512 bit i<=M i=1 i++ A=H0; B=H1; C=H2; D=H3; Xử lý trên mỗi khối 512 bit MD: H0 H1 H2 H3 End H0=H0+A; H1=H1+B; H2=H2+C; H3=H3+D Tiền xử lý Sơ đồ khối tổng quát Sơ đồ khối Tiền xử lý: F T Begin m=chiều dài thông điệp Str[m+1]=1 k=1 (m+1+k)%512 !=448 Str[m+1+k]=0 k++ i=64 i!=0 Str[m+1+k+i]=m%2 m=m/2 End F T i-- Sơ đồ khối quá trình xử lý trên mỗi khối 512 bit: S Đ Đ Đ S Đ S Begin i =1 i <=15 i <=31 i <=47 f := (B Ù C) Ú ((Ø B) Ù D) g := i f := (D Ù B) Ú ((Ø D) Ù C) g := (5×i + 1) mod 16 f := B Å C Å D g := (3×i + 5) mod 16 f := C Å (B Ú (Ø D)) g := (7×i) mod 16 temp = D , D = C , C = B B = ((A + f + K[i] + w[g]) <<< R[i]) + B i <=64 End i =i+1 S 2.4.3 KẾT QUẢ CHƯƠNG TRÌNH MÔ PHỎNG THUẬT TOÁN BĂM MD5 2.4.3.1 Giao diện chương trình mô phỏng 2.4.3.2 Các bước thực hiện chương trình: Bước 1: Mở file MD5.exe sẽ xuất hiện giao diện chương trình mô phỏng Bước 2 : Nhập thông điệp, chọn Get MD5 to Word String và chọn hàm băm MD5 theo 2 kiểu : Get(Binary)MD5 hoặc Get (Standard)MD5 HEX Bước 3 : Lúc này nút Get MD5 sẽ hiện lên . Ta bấm vào nút Get MD5 thì sẽ có kết quả tại khung MD5 2.4.7.3 Kết quả thực nghiệm: Kết quả này đúng với chuẩn đã đưa ra Kết quả 1 : MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6 Kết quả 2 : MD5("The quick brown fox jumps over the lazy cog") = 1055d3e698d289f2af8663725127bd4b Kết quả 3 : Cho một chuỗi rổng MD5 (" ") = d41d8cd98f00b204e9800998ecf8427e Kết luận: Trong chương này, chúng ta đã thực hiện được việc tìm hiểu về thuật toán băm MD5 trên các khía cạnh: - Tìm hiểu, nắm rõ thuật toán, các bước thực hiện thuật toán. - Biểu diễn sơ đồ khối của thuật toán. - Thực hiện mô phỏng thuật toán băm MD5 và các kết quả thu được đúng với các tài liệu tiêu chuẩn về thuật toán MD5, chứng tỏ chương trình mô phỏng đã được thực hiện chính xác theo thuật toán. PHẦN III KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Sau một thời gian tập trung nghiên cứu, Em đã tìm hiểu chi tiết về một số vấn đề về chữ ký điện tử và đặc biệt là thuật toán MD5. Qua đó cho thấy rằng chữ ký điện tử là nền tảng để bảo đảm an ninh trong lĩnh vực thương mại điện tử, các phần mềm quản lý có kiến trúc kiểu Client/Server. Em đã nêu được quy trình ứng dụng chữ ký điện tử trên cơ sở kết hợp giữa thuật toán băm MD5. Từ đó, đề ra giải pháp ứng dụng chữ ký điện tử trong phần mềm quản lý, cụ thể là quá trình gửi và nhận các tệp văn bản.Từ giải pháp này, ta có thể xây dựng và cài đặt các hàm sử dụng tính năng của chữ ký điện tử trong quá trình gửi và nhận các tệp văn bản ứng dụng cho các hệ thống quản lý nhằm hướng tới việc xây dựng được hệ mật mã có độ an toàn cao hơn và chữ ký số có tính xác thực cao hơn trong tương lai. Đề tài cũng chọn ra một giải pháp tạo chữ ký số tương đối mạnh là sử dụng thuật toán băm MD5 để xây dựng thử nghiệm chương trình ứng dụng chữ ký số tích hợp ký trực tiếp trên MSWORD. Tuy nhiên, do thời gian hạn chế nên có một số vấn đề mới chỉ nêu ra mà chưa tập trung nghiên cứu sâu được chẳng hạn như: hàm băm RSA,SHS,SHA-1... Tuy nhiên đây là một lĩnh vực khó và thời gian hạn chế nên em mới chỉ dừng lại ở việc xây dựng chương trình demo. Hướng tiếp là xây dựng thành một chương trình có thể ứng dụng rộng rải hơn. Với thời lượng và kiến thức còn hạn chế nên đồ án tốt nghiệp của em chắc chắn sẽ không tránh khỏi thiếu sót, rất mong nhận được sự đóng góp ý kiến của các thầy cô và bạn bè để đồ án được hoàn thiện hơn. Đà Nẵng, ngày 17 tháng 08 năm 2010 Sinh viên thực hiện Lê Thị Kim Vui DANH MỤC TÀI LIỆU THAM KHẢO TIẾNG VIỆT: [1] TS. Dương Anh Đức - ThS. Trần Minh Triết, Mã hóa và ứng dụng, Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia thành phố Hồ Chí Minh, 2005 [2] Phan Đình Diệu, Lý thuyết mật mã và an toàn thông tin, Đại học Quốc gia Hà Nội, 1999 [3] PGS.TS Hồ Thuần (2000), Giáo trình “Lý thuyết mật mã và an toàn dữ liệu”, Trường Đại học Bách Khoa Hà Nội. TIẾNG ANH: [4] R. Rivest, The MD5 Message-Digest Algorithm, MIT Laboratory for Computer Science and RSA Data Security, Inc, April 1992. [5] Federal Information Processing Standards Publication 180-2 Specifications for the SECURE HASH STANDARD, 2002. [6] Mohan Atreya, Ben Hammond, Stephen Paine, Paul Starrett, Stephen Wu (2002), Digital Signatures, RSA. [7] FIPS (2004), Announcing the Secure Hash Standard. [8] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu (2004), Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, International Association for Cryptologic Research. [9] Billy Brumley, A3/A8 & COMP128, Helsinki University of Technology. [10] William Stallings, Cryptography and Network Security : Principles and Practice, FourthEdition, Prentice Hall, 2006. [11]