Hashing trong mật mã học

Bạn đang muốn tìm hiểu về hashing (băm) trong Cryptography (mật mã học)? Trong bài viết này, chúng ta sẽ khám phá thêm về hashing nhé.

Hashing là một kỹ thuật khoa học máy tính để xác định các đối tượng hoặc giá trị từ một nhóm đối tượng hoặc nhóm giá trị.

Để dễ hiểu hơn, sau chúng ta sẽ xem xét một ví dụ.

Các trường học cung cấp một số duy nhất tương ứng cho mỗi học sinh của họ. Con số duy nhất này là thứ xác định một học sinh và thông tin liên quan đến học sinh đó.

Phương pháp được sử dụng để tạo số duy nhất là hashing.

Một ví dụ phổ biến khác là các thư viện nơi bạn sẽ tìm thấy hàng tấn sách trên giá. Mỗi cuốn sách ở đó có một số nhận dạng duy nhất để nó có thể được đặt trong thư viện khổng lồ!

Một ví dụ hiện đại về hashing sẽ là những người chơi trò chơi khi đăng ký trò chơi. Valorant là một trò chơi miễn phí do Riot phát hành. Trò chơi miễn phí sẽ thu hút hàng triệu người chơi.

Mỗi người chơi được xác định bằng một giá trị nhận dạng duy nhất được tạo bằng thuật toán hashing.

Hashing là gì?

Như đã nêu ở trên, hashing là phương pháp xác định một đối tượng từ một nhóm. Mỗi đối tượng nhận được một số nhận dạng duy nhất sau khi được hashing.

Nhưng, điều đó có nghĩa là gì về mặt kỹ thuật?

Về mặt kỹ thuật, một hàm toán học tạo ra một đầu ra có độ dài cố định từ bất kỳ chuỗi đầu vào nào có độ dài bất kỳ.

Các giao dịch bitcoin được hashing khi các giao dịch có ID duy nhất.

Nếu bạn đặt “Xin chào, Thế giới!” trong thuật toán hash SHA-256, bạn sẽ nhận được đầu ra sau:

   – Đầu vào: Xin chào, Thế giới!

   – Đầu ra: dffd6021bb2bd5b0af676290809ec3a53191dd81c7f70a4b28688a362182986f

Ở đây SHA256 tạo đầu ra từ đầu vào đã cho. Như bạn có thể thấy, chúng tôi đã sử dụng thuật toán hash an toàn (SHA-256). Đây là một trong những phương pháp hashing phổ biến hiện có, bao gồm Message Direct (MD5) và Hàm hash bảo mật (SHA1).

Các thuộc tính chính của hàm hash làm cho nó đáng tin cậy.

• Tất định: Điều này có nghĩa là đầu ra sẽ giống nhau đối với đầu vào nhất định trong mọi trường hợp.
• Chống tạo ảnh trước: Tính năng chống tạo ảnh trước đảm bảo rằng giá trị hash không hữu ích để tạo giá trị đầu vào.
• Tính toán hiệu quả: Các hàm hash hoạt động hiệu quả và không yêu cầu tài nguyên tính toán lớn để thực thi.
• Không thể đảo ngược kỹ thuật: Hàm hash không thể đảo ngược kỹ thuật.
• Chống va chạm: Chống va chạm đảm bảo rằng không có hai đầu vào nào cho ra cùng một đầu ra.

>> Xem thêm: Hàm băm SHA-256 là gì?

Hàm hash và bảng hash là gì? Và chúng hoạt động như thế nào?

Trong phần này, chúng ta sẽ tìm hiểu chi tiết hơn về hàm hash và bảng hash. Các hàm hash chịu trách nhiệm chuyển đổi các đầu vào lớn thành các đầu vào nhỏ cố định. Các bảng hash lưu trữ các kết quả đầu ra.

Trong quá trình hashing, các đối tượng được phân phối dựa trên các cặp khóa/giá trị của chúng vào danh sách. Vì vậy, nếu bạn chuyển một danh sách các phần tử cho các hàm hash, bạn sẽ nhận được một đầu ra là một danh sách, trong đó mỗi phần tử hiện có một khóa được gắn vào nó.

Để triển khai các hàm hash, bạn có thể thực hiện theo một trong hai cách tiếp cận sau:

• Cách tiếp cận đầu tiên là sử dụng hàm hash để chuyển đổi một phần tử thành một số nguyên. Tiếp theo, đầu ra số nguyên có thể được sử dụng để truy cập phần tử khi đưa vào bảng hash. Một bước khác là đặt phần tử vào bảng hash và sau đó truy xuất nó bằng khóa hash.

Trong phương pháp thứ 2, các chức năng sẽ như sau:

hash = hash_function(key)

index = hash % array_size

Ở đây, hàm hash và kích thước danh sách (array size) độc lập với nhau. Giá trị chỉ mục được tính dựa trên array size. Phép toán tìm số dư (Modulo operator) (%) cho phép tính toán giá trị.

Nói một cách đơn giản, hàm hash có thể được định nghĩa là một hàm có thể ánh xạ tập dữ liệu có kích thước tùy ý thành tập dữ liệu có kích thước cố định. Tập dữ liệu có kích thước cố định thu được có thể được lưu trữ trong bảng hash. Nhiều tên được đặt cho các giá trị được trả về bởi hàm hash. Chúng có thể được gọi là giá trị hash, tổng hash và mã hash.

Viết một hàm hash tốt

Nếu bạn muốn tạo một hàm hoặc cơ chế hash tốt, bạn cần hiểu các yêu cầu cơ bản của việc tạo một hàm hash, cụ thể:

• Hàm hash cần phải được dễ tính toán. Điều đó có nghĩa là nó không cần nhiều tài nguyên để thực thi.
• Hàm hash cần được phân phối đồng đều. Bằng cách đó, các bảng hash được sử dụng để lưu trữ các giá trị hash, từ đó giúp cho việc phân cụm sẽ không xảy ra.
• Yêu cầu cuối cùng là ít va chạm hoặc hoàn toàn không va chạm. Không xung đột có nghĩa là không có đầu ra nào được ánh xạ tới hai đầu vào.

Về mặt kỹ thuật, va chạm là một phần của hàm hash và đơn giản là không thể xóa nó khỏi hàm hash. Mục tiêu là tạo ra một hàm hash có thể cung cấp hiệu suất bảng hash tốt và giải quyết xung đột thông qua các kỹ thuật giải quyết xung đột.

Tại sao chúng ta cần một hàm hash tốt?

Để hiểu sự cần thiết của một hàm hash hữu ích, hãy xem qua một ví dụ bên dưới.

Giả sử rằng chúng ta muốn tạo một bảng hash bằng kỹ thuật hashing trong đó các chuỗi đầu vào sẽ như sau, {“agk”, “kag”, “gak”, “akg”, “kga”, “gka” }

Bây giờ, chúng ta tạo một hàm hash đơn giản cộng giá trị ASCII của a(97), g(103) và k(107) rồi thực hiện một mô-đun của tổng bằng 307.

Rõ ràng, tổng của ba số cũng là 307. Điều này có nghĩa là nếu chúng ta hoán vị tất cả các số và sau đó thực hiện phép toán, chúng ta sẽ nhận được kết quả tương tự. Kết quả cuối cùng sẽ lưu trữ tất cả các chuỗi vào cùng một số chỉ mục. Thời gian thuật toán cho hàm hash cũng sẽ là độ phức tạp O(n). Chúng ta có thể dễ dàng kết luận rằng hàm hash mà chúng ta đã mô tả không tối ưu cho các tình huống thực tế.

Để sửa hàm hash, chúng ta có thể triển khai phép chia tổng các giá trị ASCII của từng phần tử cho một số nguyên tố khác, như 727. Bằng cách đó, chúng ta sẽ nhận được một đầu ra khác cho danh sách chuỗi đầu vào đã cho.

Tìm hiểu về bảng hash

Các bảng hash rất hữu ích trong việc lưu trữ kết quả của một hàm hash, tính toán số mũ và sau đó lưu trữ một giá trị đối với nó. Kết quả cuối cùng sẽ là quá trình tính toán nhanh hơn với độ phức tạp O(1).

Các bảng hash theo truyền thống là một lựa chọn tốt trong việc giải các bài toán yêu cầu thời gian O(n).

Vì vậy, nếu bạn chọn một chuỗi có độ dài cố định, sau đó cố gắng tìm hiểu tần suất ký tự của chuỗi đó và nếu string = “aacddce”, thì cách tiếp cận chung là duyệt qua chuỗi nhiều lần và lưu trữ từng tần số.

# Cung cấp một chuỗi đầu vào và đếm tần suất của các ký tự trong chuỗi đó

# Thuật toán là 0(n) thời gian phức tạp

temp_list = []

start = “a”

str = “ababcddefff”

def alpha_zeta():

    alpha = ‘a’

    for i in range(0,26):

        temp_list.append(alpha)

        alpha = chr(ord(alpha) + 1)

    return temp_list

temp_list = alpha_zeta()

#print (temp_list)

def character_frequency(str, temp_list):

    for each in temp_list:

        freq = 0

        for i in str:

            if (i == each):

                freq = freq + 1

        print (each, freq)

character_frequency(str,temp_list)

Đầu ra của chương trình trên sẽ như sau:

a 2

b 2

c 1

d 2

e 1

f 3

g 0

h 0

i 0

..

..

Bây giờ, hãy triển khai bảng hash trong C++ và đếm tần suất ký tự.

#include <iostream>

using namespace std;

int Frequency[26];

int hashFunc(char c) {

        return (c – ‘a’);

    }

void countFre(string S)

    {

        for (int i = 0; i< S.length(); ++i){

            int index = hashFunc(S[i]);

            Frequency[index]++;

        }

        for (int i = 0; i<26; ++i) {

            cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl;

        }

    }

int main()

{

    cout<<“Hello World”;

    countFre(“abbaccbdd”);

}

Đầu ra sẽ như sau:

a 2

b 3                                                                                                    

c 2

d 2

Độ phức tạp O(N) của thuật toán làm cho nó nhanh hơn so với các phương pháp tuyến tính khác.

Làm sao để giải quyết các trục trặc phát sinh?

Có những cách để giải quyết trục trặc trong hàm hash. Một trong những cách phổ biến là tạo chuỗi riêng biệt, còn được gọi là hash mở. Nó được thực hiện bởi một danh sách được liên kết. Mỗi phần tử trong chuỗi chính là một danh sách được liên kết. Cách tiếp cận này cho phép lưu trữ các phần tử và đảm bảo rằng các phần tử nhất định chỉ là một phần của danh sách được liên kết cụ thể. Điều đó có nghĩa là không có hai giá trị đầu vào nào có thể có cùng giá trị hash đầu ra.

Khám phá hàm hash trong Python

Trong phần này, chúng ta sẽ nhanh chóng xem xét hàm hash trong Python. Lý do chúng tôi chọn Python là nó dễ đọc và bất kỳ ai cũng có thể sử dụng mà không gặp nhiều khó khăn.

Vì hash là một chức năng phổ biến nên nó đã được triển khai trong thư viện Python. Bằng cách sử dụng mô-đun, bạn có thể cung cấp một đối tượng làm đầu vào của nó và sau đó trả về giá trị hash.

Cú pháp của phương thức hash là:

hash (đối tượng)

Như bạn có thể thấy, nó nhận một tham số duy nhất, đó là đối tượng. Đối tượng có thể là số nguyên, float hoặc chuỗi.

Giá trị trả về của phương thức hash() phụ thuộc vào đầu vào. Đối với một số nguyên, nó có thể trả về cùng một số trong khi đối với số thập phân và chuỗi sẽ khác.

Hãy xem một số ví dụ dưới đây.

num = 10

deci = 1.23556

str1= “Nitish”

print (hash(num))

print (hash(deci))

print (hash(str1))

Đầu ra của đoạn mã trên như sau:

Tuy nhiên, hàm hash không thể được áp dụng cho tất cả các loại đối tượng. Ví dụ, nếu bạn còn nhớ rằng chúng ta đã tạo một danh sách từ a đến z trong chương trình đầu tiên của mình. Nếu chúng ta cố gắng hashing nó, cửa sổ đầu ra sẽ thông qua TypeError: unhashable type: ‘list’

Để áp dụng hàm hash cho danh sách đối tượng, bạn cần sử dụng tuple.

vowels = (‘a’, ‘e’,’i’,’o’,’u’)

print (hash(vowels))

Output ⇒ -5678652950122127926

Hashing trong mật mã học

Hashing rất hữu ích cho mật mã học. Bitcoin sử dụng hàm hash để tạo và quản lý cây Merkle.

Ngoài ra, hash đã là một phần của mật mã trong một thời gian khá dài. Tuy nhiên, trường hợp sử dụng hashing tốt nhất là hash mật khẩu và lưu trữ chúng.

Cây Merkle

Cây Merkle là một cấu trúc dữ liệu hữu ích khi thực hiện xác minh dữ liệu an toàn trong một nhóm dữ liệu lớn. Cả Bitcoin và Ethereum đều sử dụng cây Merkle để giải quyết nhiều rào cản công nghệ khi lưu trữ và truy cập dữ liệu trong một mạng mở.

Bất kỳ mạng tập trung nào cũng không phải lo lắng về việc lưu trữ và truy cập dữ liệu vì chỉ có một nguồn để truy cập và lưu trữ dữ liệu. Tuy nhiên, phương trình sẽ thay đổi khi có một mạng phi tập trung vì hiện tại dữ liệu cần được sao chép giữa hàng trăm đồng nghiệp tham gia.

Cây Merkle giải quyết vấn đề bằng cách cung cấp một cách đáng tin cậy và hiệu quả để chia sẻ và xác minh dữ liệu giữa các thiết bị ngang hàng (peer).

Ví dụ cây Merkle

Nhưng, tại sao chúng ta lại thảo luận về cây Merkle ở đây? Cây Merkle sử dụng hàm hash làm chức năng cốt lõi để kết nối các node và khối dữ liệu khác nhau.

Merkle Trees là một cây lộn ngược có thể tóm tắt toàn bộ tập giao dịch.

Quy trình khai thác

Quá trình khai thác cũng tận dụng lợi thế của hash. Khi nói đến khai thác bitcoin, một khối mới sẽ được thêm vào blockchain khi có nhu cầu về nó.

Một phương pháp cần được tuân theo để thêm khối vào blockchain. Giá trị hash được tạo tùy thuộc vào nội dung của khối khi có khối mới. Ngoài ra, nếu hàm hash được tạo nhiều hơn độ khó của mạng, thì quá trình thêm khối vào blockchain sẽ bắt đầu.

Sau khi hoàn thành, tất cả các thiết bị ngang hàng trong mạng thừa nhận việc bổ sung khối mới.

Tuy nhiên, điều đó hiếm khi xảy ra vì trong hầu hết các trường hợp, độ khó của mạng luôn cao hơn so với hàm hash được tạo. Có một khía cạnh khác đóng một vai trò quan trọng trong quá trình khai thác. Nó là nonce.

Nonce được thêm vào hàm hash của khối và là một chuỗi tùy ý. Sau khi hoàn thành, chuỗi được nối sẽ được so sánh với mức độ khó. Nếu mức độ khó thấp hơn chuỗi được nối, thì nonce được thay đổi cho đến khi mức độ khó cao hơn.

Quá trình có thể được tóm tắt trong các bước sau:

• Nội dung được hashing để tạo giá trị hash mới bất cứ khi nào một khối mới được tạo hoặc lấy.
• Một giá trị nonce mới được tạo và thêm vào hàm hash.
• Quá trình hashing diễn ra trên chuỗi liên hệ mới.
• Giá trị cuối cùng của hàm hash sau đó được so sánh với mức độ khó của mạng.
• Nếu giá trị hash cuối cùng thấp hơn nonce, quá trình này sẽ được lặp lại một lần nữa. Quá trình chỉ dừng lại khi giá trị hash lớn hơn nonce.
• Block tham gia chuỗi khi độ khó cao hơn.
• Sau đó, những người khai thác sẽ chịu trách nhiệm khai thác khối mới và chia sẻ phần thưởng với nhau.

Thuật ngữ “Tỷ lệ hash” cũng xuất hiện từ đây. Tỷ lệ hash là tốc độ diễn ra các hoạt động hash. Tỷ lệ hash cao hơn có nghĩa là những người khai thác sẽ cần nhiều sức mạnh tính toán hơn để tham gia vào quá trình khai thác.

Kết luận

Điều này dẫn chúng ta đến phần cuối của quá trình hash trong hướng dẫn chuyên sâu về mật mã. Bài viết đã đề cập chi tiết về hashing và cũng khám phá code đằng sau nó.

Còn bây giờ thì bạn đã muốn thử sức mình trong lĩnh vực này chưa? Bắt tay vào làm ngay thôi nào và cũng đừng quên theo dõi BlockchainWork để cập nhật thêm nhiều thông tin, kiến thức thú vị trong ngành nhé!

BlockchainWork biên dịch

Nguồn: 101 Blockchains

• Tìm hiểu thêm về BlockchainWork tại website: https://blockchainwork.net/
• Ứng viên nắm bắt cơ hội việc làm tại đây: https://blockchainwork.net/candidate-signup
• Nhà tuyển dụng kết nối các tài năng trẻ tại đây: https://blockchainwork.net/employer-signup

>> Xem thêm:

• Hash là gì?
• Hướng dẫn đầy đủ về bảo mật tiền điện tử
• Hashing (hàm băm) là gì – Tìm hiểu về cách thức hoạt động của hàm băm