Đề tài Mã hóa thông tin, thuật toán băm MD5, thuật toán mã hóa RSA

một hàm lấy số liệu đầu vào có kích cỡ tuỳ ý (bản tin) và tạo thành đầu ra có kích cỡ cố định gọi là bản tóm tắt. Tập hợp thông tin này sau đó được mật mã hoá sử dụng khoá bí mật của người gửi có sử dụng một thuật toán không đối xứng thích hợp. Kết quả sau khi mật mã hoá khối thông tin là chữ ký điện tử. MD được tính toán là một giá trị bit nhằm để mô tả tình trạng hiện thời của tài liệu. Nếu tài liệu thay đổi, MD cũng sẽ thay đổi. Bằng cách hợp nhất MD vào chữ ký điện tử, khi chữ kýđiện tử đã được tạo thành nó cho phép người nhận tài liệu có thể dễ dàng phát hiện ra tài liệu có bị biến đổi hay không. Mục đích sử dụng của chữ ký điện tử cũng tương tự như chữ ký thông thường, bao gồm: Nhận thực: Nếu người nhận thành công trong việc giải mã thông tin với một khóa công cộng xác định thì người đó có thể chắc chắn rằng bản tin đó đã được ký bởi chính người sử dụng khoá bí mật tương ứng. Một vấn đề nữa là phải kiểm tra xem khoá công cộng này có thực sự là của người gửi đích thực hay không. Vấn đề này có thể được giải quyết bằng cách sử dụng các chứng nhận chữ ký điện tử. Tính toàn vẹn: Nếu một bản tin đã được ký mà thay đổi trong quá trình truyền dẫn, người nhận sẽ không thể giải mã được với khoá công cộng. Đây là một cách dễ dàng để phát hiện ra những thay đổi cố ý hoặc vô ý trong thông tin được phát. Tính không thể phủ nhận: Trong các phiên giao dịch điện tử, một yêu cầu rất quan trọng đối với mỗi bên tham gia là phải đảm bảo rằng bên còn lại không thể từ chối việc phải thực thi một số hành động nào đó. Chữ ký điện tử cũng rất thích hợp với yêu cầu này do một tài liệu điện tử chỉ có thể được ký bởi chính người sở hữu khoá bí mật. Thủ tục ký và kiểm tra: Các bước cần thiết để ký và kiểm tra một mẫu thông tin được mô tả ở (hình 2.1). Các thành phần cần thiết của một hệ thống như vậy là các thuật toán khoá công cộng và thuật toán Hash mà sẽ được lựa chọn một cách cẩn thận theo yêu cầu. Số liệu gốc trước tiên sẽ được làm mới lại bằng cách sử dụng hàm một chiều Hash, sau đó được mật mã hoá bằng khoá bí mật của người gửi. Mục đích của thủ tục này là giảm thời gian mật mã hoá do các thuật toán không đối xứng thực thi chậm hơn nhiều các thuật toán đối xứng. Cả số liệu gốc lẫn chữ ký đều được gửi qua kênh thông tin không an toàn đến người nhận. Hình 2.2: Thủ tục ký và kiểm tra chữ 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