Hàm băm mật mã

K y u công trình khoa h c 2015 – Ph n I<br /> <br /> HÀM BĂM MẬT MÃ<br /> Nguyễn Minh Hòa<br /> Khoa Toán-Tin, Đại học Thăng Long<br /> Email: mr.nmh175@gmail.com<br /> Tóm tắt: Khái niệm hàm băm đã xuất hiện từ lâu trong lĩnh vực máy tính. Nó ánh xạ<br /> một xâu nhị phân (văn bản, hình ảnh, âm thanh,…) có độ dài bất kỳ thành một xâu có độ dài<br /> cố định. Bản chất của mã băm có thể coi như “dấu vân tay” của một văn bản. Nhờ có nó ta<br /> có thể đảm bảo rằng một văn bản là chính xác và không bị sửa đổi. Hiện nay trên thế giới có<br /> rất nhiều hàm băm phục vụ cho nhiều mục đích khác nhau như quân sự, truyền tin, xác thực…<br /> Với mong muốn làm chủ mã nguồn, làm chủ chương trình, chúng tôi đã cố gắng tìm hiểu và<br /> cài đặt hàm băm SHA-256 phục vụ cho đề tài Xây dựng hệ thống chữ ký số cho trường Đại<br /> học Thăng Long. Trong bài báo sẽ mô tả chi tiết về hàm băm này.<br /> Từ khóa:Hàm băm, Mã băm, Chữ ký số, SHA-256.<br /> 1.<br /> <br /> Giới thiệu<br /> <br /> Hàm băm là hàm ánh xạ một xâu nhị phân có độ dài bất kỳ thành một xâu nhị phân có độ dài<br /> cố định (thường được gọi là mã băm). Thông thường, độ dài của mã băm có thể là 128, 160,<br /> 256 hoặc 512 bit.Hàm băm có thể coi là hàm nén thông điệp một cách hợp lý.<br /> Để có thể dùng trong thực tế, hàm băm cần đảm bảo các tính chất như: thời gian tính toán<br /> nhanh, mã băm sinh ra phải ngẫu nhiên và thuật toán phải công khai. Nhằm mục đích đáp ứng<br /> các tính chất trên, hàm băm SHA-256 đã được xây dựng dựa trên sơ đồ Merkle-Damgard Ứng<br /> và hàm nén Davies-Meyer.Ứng dụng của nó là để kiểm tra tính toàn vẹn của thông điệp.<br /> Bài báo này sẽ trình bày chi tiết các lý thuyết và cách thức hoạt động của hàm băm SHA-256.<br /> Nội dung các phần bao gồm: Phần 2 sẽ mô tả về hàm băm kháng xung đột - một mô hình hàm<br /> băm phù hợp với thực tế; Phần 3 mô tả về hàm băm SHA-256; Phần cuối cũng sẽ nói về thực<br /> tế cài đặt hàm băm SHA-256 của dự án.<br /> 2. Hàm băm kháng xung đột<br /> 2.1. Các định nghĩa<br /> Định nghĩa 1.Hàm băm là hàm tính được một cách “hiệu quả”<br /> <br /> Nó ánh xạ một xâu nhị phân độ dài bất kỳ trong không gian thông điệp thành một xâu<br /> nhị phân độ dài cố định, gọi là mã băm.<br /> Thông thường độ dài của mã băm là d= 128, 160, 256 hoặc 512 bit.<br /> Ví dụ 1. Một số hàm băm trong thực tế.<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 11<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> Hàm băm<br /> <br /> d<br /> <br /> MD4<br /> <br /> 128<br /> <br /> SHA-1<br /> <br /> 160<br /> <br /> SHA-256<br /> <br /> 256<br /> <br /> SHA-512<br /> <br /> 512<br /> <br /> SHA-3 (Keccak)<br /> <br /> 224, 256, 384, 512<br /> <br /> Giả sử hàm băm được thiết kế một cách lý tưởng (như ngẫu nhiên), khi đó cho trước<br /> <br /> . Con số này rất gần 0<br /> mã bămx, xác suất tìm được một dữ liệum thỏa mãn H(m) = x chỉ là<br /> khi d đủ lớn. Như vậy hàm băm cho ta một biểu diễn nén hợp lý của dữ liệu.<br /> Bên cạnh đó, để có thể dùng trong thực tế, hàm băm cần có một số tính chất sau:<br /> • Tính hiệu quả: có thuật toán “nhanh” (trong thời gian đa thức ) để tính h.<br /> • Tính ngẫu nhiên: giá trị H(m) là khó dự đoán.<br /> • Tính công khai.<br /> Định nghĩa 2.Một xung đột cho hàm H là một cặp<br /> <br /> thỏa mãn<br /> <br /> Rõ ràng, vì kích thước đầu vào của hàm băm lớn hơn so với kích thước đầu ra, nên<br /> theo nguyên lý “chuồng bồ câu”, luôn tồn tại xung đột. Tuy vậy, để hàm băm là an toàn thì<br /> việc tìm thấy xung đột phải rất “khó”. Có nghĩa rằng, xác suất tìm thấy xung đột phải “nhỏ”.<br /> Định nghĩa 3.Hàm H gọi là kháng xung độtnếu với mọi thuật toán (tường minh1)<br /> “hiệu quả” A, ta có<br /> <br /> là nhỏ “không đáng kể”.<br /> Hiệnnay, hàm băm<br /> dài tối đa<br /> đột.<br /> <br /> , ánh xạ các xâu nhị phân độ<br /> <br /> sang các xâu độ dài 256, được thừa nhận một cách rộng rãi là kháng xung<br /> <br /> Mục đích của hàm băm không phải là giữ bí mật không điệp mà là đảm bảo tính toàn<br /> vẹn thông điệp.<br /> <br /> 1<br /> <br /> Vì xung đột luôn tồn tại, nên ta có ngay thuật toán in ra xung đột đó. Tường minh ở đây hiểu rẳng thuật<br /> toán phải xây dựng xung đột từ mô tả của hàm băm, chứ không phải từ xung đột đã có.<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 12<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> 2.2. Tấn công dùng nghịch lý ngày sinh<br /> <br /> . Thuật toán sau đây có thể được dùng để tìm xung<br /> <br /> Xét hàm băm<br /> <br /> đột cho các hàm băm trong thời gian<br /> <br /> .<br /> <br /> Thuật toán:<br /> 1. Chọn ngẫu nhiên<br /> phân biệt là cao).<br /> <br /> xâu trong<br /> <br /> (xác suất chúng đôi một<br /> <br /> :<br /> <br /> 2.<br /> <br /> Với<br /> <br /> , ta tính<br /> <br /> .<br /> <br /> 3.<br /> <br /> Tìm xung đột<br /> <br /> . Nếu không tìm thấy thì quay lại bước 1.<br /> <br /> Thuật toán được đánh giá dựa trên định lý sau đây:<br /> Định lý 1 (Nghịch lý ngày sinh nhật). Xét<br /> nhiên độc lập. Nếu<br /> <br /> là các biến ngẫu<br /> <br /> thì<br /> <br /> Từ định lý trên, ta thấy rằng kỳ vọng tìm được xung đột của thuật toán trên là 2. Thời<br /> gian cần cho thuật toán là<br /> Hàm băm<br /> <br /> và không gian cần là<br /> <br /> .<br /> <br /> Kích thước mã băm<br /> <br /> Tốc độ (MB/s)<br /> <br /> SHA-1<br /> <br /> 160<br /> <br /> 153<br /> <br /> SHA-256<br /> <br /> 256<br /> <br /> 111<br /> <br /> SHA-512<br /> <br /> 512<br /> <br /> 99<br /> <br /> Whirlpool<br /> <br /> 512<br /> <br /> Thời gian tấn công<br /> <br /> 57<br /> <br /> 2.3. Sơ đồ Merkle-Damgard<br /> Để xây dựng hàm băm kháng xung đột, kích thước mã băm tối thiểu nên là 160 bit.<br /> Tuy nhiên đầu vào có thể là một xâu với kích thước tùy ý. Trên thực tế, việc thiết kế hàm<br /> băm trên miền vô hạn là khó. Bởi vậy người ta thường thiết kế một hàm nén ánh xạ các xâu<br /> bit độ dài cố định s thành các xâu bít độ dài cố định d, sau đó thực hiện tính toán lặp với hàm<br /> nén để được hàm băm với đầu vào tùy ý.<br /> Phép biến đổi Merkle-Damgard là một cách phổ biến để mở rộng một hàm nén kháng<br /> xung đột với kích thước đầu vào cố định thành hàm băm kháng xung đột kích thước đầu vào<br /> tùy ý. Trong sơ đồ Merkle-Damgard, ta sử dụng hàm nén kích thước đầu vào cố định<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 13<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> Hình 1. Sơ đồ Merkle-Damgard<br /> Mục đích của ta là xây dựng hàm băm kích thước đầu vào tùy ý<br /> <br /> Sơ đồ Merkle-Damgard được mô tả như trong Hình 1.<br /> Thuật toán Merkle-Damgard được mô tả như sau:<br /> 1. Dữ liệu cần bămm với độ dài |m| = L sẽ được ghép với dãy bit<br /> <br /> với l là số nguyên không âm nhỏ nhất để độ dài củam||PB chia hết cho k.<br /> 2. Thông điệp m||PB sẽ được chia thành các khốik bit:<br /> <br /> 3. Gán<br /> là một dãy d bit cố định.<br /> 4. Với i = 0, 1, …, t ta tính<br /> <br /> 5. Output<br /> <br /> .<br /> <br /> Tính an toàn của sơ đồ Merkle-Damgard được chỉ ra bởi định lý sau.<br /> Định lý 2. Nếu hàm nén h là kháng xung đột, vậy hàm H xây dựng theo sơ đồ MerkleDamgard cũng là kháng xung đột.<br /> 2.4. Xây dựng hàm nén<br /> Sơ đồ trước cho phép ta đưa bài toán thiết kế hàm băm kháng xung đột với đầu vào bất<br /> kỳ về bài toán thiết kế hàm nén với đầu vào cố định. Bây giờ ta xem xét một cách thiết kế<br /> hàm nén dựa trên mã khối an toàn.<br /> Xét hệ mã khối E trên không gian khóa K và không gian thông điệp<br /> <br /> :<br /> <br /> Hàm nén Davies-Meyer định nghĩa bởi:<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 14<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> Giả sử (E,D) là một hệ mã khối “lý tưởng” (tập gồm |K| hoán vị ngẫu nhiên). Tìm một<br /> xung độth(x,y)= h(x',y')cho hàm nén Davies-Meyer định nghĩa ở trên mất<br /> D).<br /> <br /> lần tính (E,<br /> <br /> Để phù hợp với tiêu chuẩn quốc gia Việt Nam về chữ ký số (TCVN 7635:2007),<br /> chúng tôi sử dụng SHA-256 là hàm băm phục vụ dự án chữ ký số của trường Đại học Thăng<br /> Long. Hàm băm chuẩn SHA-256 được xây dựng dựa trên sơ đồ Merkle-Damgard,hàm nén<br /> Davies-Meyer và hệ mã khối SHACAL-2 với kích thước khối là 256.Phần tiếp theo, chúng ta<br /> sẽ mô tả chi tiết SHA-256 và SHACAL-2.<br /> 3. Hàm băm SHA-256<br /> Hàm băm SHA256 nhận đầu vào là một xâu bit (ký tự, tập tin…) bất kỳ có độ dài tối<br /> đa<br /> bit và tạo ra một mã băm có độ dài 256 bit và thường được biểu diễn dưới dạng 64<br /> chữ số trong hệ cơ số 16.<br /> 3.1. Sơ đồ chung<br /> Hàm băm này được xây dựng dựa trên sơ đồ Merkle-Damgard với<br /> là dãy 256 bit được chia thành 8 khối liên tiếp<br /> <br /> • Vector khởi tạo<br /> <br /> • Dữ liệu đầu vào được chia thành các khối m[i] kích thước 512 bit, và<br /> • Hàm nén Davies-Meyer<br /> <br /> định nghĩa bởi<br /> trong đó E là hệ mã khối an toàn<br /> <br /> 3.2. Hệ mã khối SHACAL-2<br /> Ta sử dụng một số ký hiệu sau để mô tả hệ mã khối SHACAL-2:<br /> Ký hiệu<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> Mô tả<br /> <br /> 15<br /> <br />