Tổng quan về hàm băm

Hàm băm là hàm 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. Các hàm băm nhận một chuỗi bit có chiều dài tùy ý (hữu hạn) làm dữ liệu đầu vào và tạo ra một chuỗi bit mới có chiều dài cố định n bit (n > 0), được gọi là giá trị băm hay mã băm.

Tính chất cơ bản của hàm băm:

    Tính kháng tiền ảnh: Với mọi đầu ra y cho trước không thể tính toán để tìm được bất kỳ dữ liệu đầu vào x’ nào sao cho giá trị băm h(x’) bằng giá trị đầu ra y đã cho.
    Tính kháng tiền ảnh thứ hai: Với mọi dữ liệu đầu vào x1 cho trước, không thể tính toán để tìm ra được bất kỳ một đầu vào x2 nào (x1 ≠ x2) sao cho giá trị băm h(x2) = h(x1).
    Tính kháng xung đột: Không thể tính toán để tìm được hai dữ liệu đầu vào x1 ≠ x2 sao cho chúng có cùng giá trị băm.

    Ký hiệu D là miền xác định và R là miền giá trị của hàm băm h(x), ta thường có số lượng phần tử của D  lớn hơn rất nhiều so với số lượng phần tử trong R. Vì vậy hàm băm h(x) không là đơn ánh, tức là luôn tồn tại một cặp đầu vào khác nhau có cùng giá trị mã băm. Giả sử hạn chế hàm h(x) trên miền xác định chỉ bao gồm các chuỗi bit có chiều dài bằng t (t > n). Nếu h(x) là ngẫu nhiên theo nghĩa tất cả các giá trị đầu ra của nó có xác suất bằng nhau thì có khoảng 2^(t – n) đầu vào ánh xạ vào mỗi giá trị đầu ra. Xác suất để hai giá trị đầu vào (có chiều dài bằng nhau) ánh xạ bào cùng một giá trị đầu ra sẽ bằng 2^(-n ) (hoàn toàn không phụ thuộc vào t). Nếu n khá lớn thì 2^(-n) sẽ rất nhỏ. Nhờ vậy, mặc dù với mỗi chuỗi bit cho trước thường tồn tại một (hoặc nhiều) chuỗi bit khác sao cho mã băm của nó trùng với mã băm của chuỗi bit đã cho, nhưng việc tính toán để tìm ra chuỗi bit này là rất khó nếu ta chọn được hàm h(x) thích hợp và giá trị n (chiều dài mã băm) là đủ lớn.

    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’) thì 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’ sao cho 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.

    Trong lĩnh vực mã hoá thông tin, mã băm được xem như hình ảnh đặc trưng thu gọn của một chuỗi bit có độ dài tuỳ ý hữu hạn, và được dùng để nhận diện chuỗi bit đó. Kết hợp với các công cụ tạo chữ ký số, các hàm băm được dùng cho việc đảm bảo tính toàn vẹn của dữ liệu.

    Trong lược đồ ký điện tử (tạo chữ ký số), mã băm của chuỗi bit được tính tại thời điểm xác định T1 và được bảo vệ để chống lại mọi sự thay đổi bất hợp pháp. Tại thời điểm T2 sau đó, để kiểm tra xem chuỗi bit x có bị thay đổi hay không, người ta chỉ cần tính mã băm của chuỗi bit này tại thời điểm T2, đem so sánh với mã băm tại thời điểm T1. Nếu hai giá trị này là bằng nhau thì người ta chấp nhận chuỗi bit tại thời điểm T2 hay chuỗi bit x chưa bị thay đổi. Như vậy, vấn đề bảo đảm tính toàn vẹn của chuỗi bit có chiều dài tuỳ ý (có thể là rất lớn) được thay bằng việc bảo vệ sự toàn vẹn của chuỗi bit có chiều dài cố định thường là khá nhỏ.