Hàng băm (hash) là gì? Tính chất, Ứng dụng hàm trong thực tế

Làm sao để xác thực một ứng dụng hay tài liệu có toàn vẹn và đúng nguồn gốc? Làm sao để lưu mật khẩu một cách an toàn? Để trả lời thắc mắc đó, hãy cùng mình tìm hiểu hàng băm là gì và một số ứng dụng của nó nhé. Géc gôooo!

Xem thêm:

Hash (băm) là gì?

Hash là thuật toán mã hóa thông tin một chiều. Nó giúp chuyển đổi dữ liệu đầu vào như: file, hình ảnh hoặc chữ cái và ký tự có kích thước không cố định để tạo đầu ra có kích thước cố định.

Lưu ý: Không thể dịch ngược chuỗi mã hóa để tìm thông tin gốc ban đầu.

Hàm Băm (Hash)

Hàng băm (hash table) là gì?

Hàng băm (hash table) là giải thuật nhằm sinh ra các giá trị băm tương ứng với mỗi khối dữ liệu.

Là bất kỳ hàm nào có thể được sử dụng để ánh xạ dữ liệu có kích thước tùy ý thành các giá trị kích thước cố định.

Các giá trị được trả về bởi hàm băm được gọi là giá trị băm, mã băm, thông điệp băm, hoặc đơn giản là “hash”.

Bảng băm

Tính chất cơ bản

Tính bất định – Deterministic: Nghĩa là cùng một thông điệp đầu vào luôn tạo ra cùng một hàm băm.

Tính nhanh chóng – Quick: Tiêu tốn ít thời gian hơn để tính toán giá trị băm của dữ liệu đầu vào.

Hiệu ứng lan truyền – Avalanche effect: Chỉ một sự thay đổi nhỏ của thông điệp cũng có thể làm thay đổi kết quả hash.

Avalanche effect

Tính một chiều – One-way function: Không thể suy ra dữ liệu ban đầu từ kết quả, ví dụ như không thể chỉ dựa vào một dấu vân tay mà có thể suy ra người đó là ai.

Ngăn chặn đụng độ – Collision resistant: Không khả thi (không thể) để tìm được giá trị 2 chuỗi đầu vào có cùng kết quả giá trị băm.

Hạn chế của hàm Hash

Hàm băm cũng có một số hạn chế cần lưu ý, bao gồm:

  • Va chạm: Khi hai giá trị đầu vào khác nhau tạo ra cùng một giá trị băm, thì hiện tượng này được gọi là va chạm. Va chạm có thể dẫn đến các vấn đề như tìm kiếm dữ liệu chậm hoặc kém hiệu quả.
  • Không thể đảo ngược: Hàm băm thường không thể đảo ngược. Nghĩa là không thể tính toán lại giá trị đầu vào từ giá trị băm. Điều này có thể dẫn đến các vấn đề bảo mật, chẳng hạn như không thể khôi phục mật khẩu đã bị băm.

Ưu điểm của băm

Ưu điểm chính của bảng băm so với các cấu trúc dữ liệu khác là tốc độ . Thời gian truy cập của một phần tử là trung bình O(1). Do đó việc tra cứu có thể được thực hiện rất nhanh. Bảng băm đặc biệt hiệu quả khi có thể dự đoán trước số lượng mục nhập tối đa.

Thuộc tính của hàm băm tốt

Tính đồng nhất

Hàm băm tốt phải ánh xạ các khóa càng đồng đều càng tốt. Nghĩa là xác suất tạo ra mọi giá trị băm trong phạm vi đầu ra gần như giống nhau. Điều này cũng giúp giảm va chạm.

Xác định

Hàm băm phải luôn tạo ra cùng một giá trị băm cho một giá trị đầu vào nhất định.

Giá thấp

Để áp dụng hàm băm, chi phí tính toán phải thấp. Điều này giúp kỹ thuật băm trở nên thích hợp hơn các phương pháp truyền thống khác.

Ứng dụng của hàm băm trong thực tế

Hàm băm thường được sử dụng trong các ứng dụng như băm mật khẩu, tìm kiếm dữ liệu, phân loại dữ liệu,… Cụ thể:

Hashing trong định danh tệp hoặc dữ liệu

Giá trị băm có thể được sử dụng như một phương tiện để định danh tập tin một cách đáng tin cậy. Một số hệ thống quản lý mã nguồn, như Git, Mercurial hay Monotone, sử dụng giá trị shalsum của nội dung tệp, cây thư mục, thông tin thư mục gốc, v.v. để định danh chúng.

Giá trị băm cũng được sử dụng để xác định các tệp khi chia sẻ tệp mạng ngang hàng. Nhằm cung cấp đầy đủ thông tin để định vị nguồn gốc của tệp, xác minh nội dung tệp tải xuống.

Hashing trong xác minh tính toàn vẹn của thông điệp hoặc tập tin

Khi download một phần mềm hoặc tệp tin nào đó trên một số trang web, ta được cung cấp kèm theo các mã băm MD5 hoặc SHA.

Khi đó sau khi tải về tập tin, ta có thể tính và so sánh giá trị băm của tệp tải về với giá trị băm được cung cấp trên web, nếu có sự sai khác tức là tệp tin tải về đã bị sửa đôi.

Hashing trong tạo và xác nhận chữ ký

Chữ ký số là cách xác nhận thông điệp bằng cách dùng hàm băm mật mã để tạo ra bản tóm lược. Thay vì phải tính toán và chữ ký trên văn bản dài, ta chỉ cần làm việc với một khối dữ liệu nhỏ và không thay đổi. Hàm băm mật mã đảm bảo thông điệp không bị thay đổi khi tạo chữ ký số. Chữ ký số giúp bảo vệ thông điệp một cách an toàn và hiệu quả.

Hashing trong xác minh mật khẩu

Mật khẩu có thể được bảo vệ bằng cách lưu dưới dạng băm. Khi đăng nhập, mật khẩu nhập vào sẽ được băm và đối chiếu với bản băm đã lưu. Để chống lại các cuộc tấn công dò mật khẩu, ta có thể kéo dài thời gian băm bằng key stretching.

Hashing trong blockchain

Với blockchain, ngoài việc có thể trỏ tới block trước đó, mỗi block còn có thể lưu giá trị digest của khối được trỏ tới. Qua việc kiểm tra giá trị hash có thể nhận dạng khối được trỏ tới có bị thay đổi hay không. Cấu trúc blockchain cho phép chỉ cần lưu giá trị của con trỏ chỉ tới khối cuối cùng, đồng thời vẫn kiểm soát được nội dung của các khối còn lại không bị thay đổi.

Một số thuật toán

Một số Hash cơ bản như:

  • MD5
  • SHA-1
  • RIPEMD-160
  • Bcrypt
  • Whirlpool
  • SHA-2
  • SHA-3
  • BLAKE2

Trên đây là một số thông tin cơ bản về hàng băm (hash). Hy vọng bài viết hữu ích và giúp bạn có thêm kiến thức về an ninh mạng máy tính. Cảm ơn bạn đã tham khảo trên ttnguyen.net.

Bài viết liên quan:

Nguyễn Tiến Trường

Mình viết về những điều nhỏ nhặt trong cuộc sống, Viết về câu chuyện những ngày không có em