Băm trong mật mã

Bạn đang muốn tìm hiểu về băm trong mật mã? Nếu bạn làm vậy, thì bạn đã đến đúng nơi.

Trong bài viết này, chúng ta sẽ khám phá thêm về băm.

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 giá trị.

Nghe khó hiểu?

Hãy thử hiểu bằng ví dụ.

Vâng, các trường cao đẳng và trường học cung cấp một con số được chỉ định duy nhất cho mỗi sinh viên của họ. Số duy nhất này là số xác định một sinh viên và thông tin liên quan đến anh ta. Phương pháp được sử dụng để tạo số duy nhất là băm.

Một ví dụ phổ biến khác là 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ó số nhận dạng duy nhất để nó có thể nằm trong thư viện khổng lồ!

Một ví dụ hiện đại về băm sẽ là những người chơi trò chơi đăng ký trò chơi. Valorant là một trò chơi miễn phí do Riot tung ra. Chơi miễn phí có nghĩa là hàng triệu người sẽ chơi trò chơi.

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

Hãy cố gắng hiểu nó chi tiết hơn bên dưới.

 

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 băm.

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 đầ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 băm trong đó các giao dịch nhận được ID duy nhất.

Nếu bạn nhập “Hello, World!” trong một Thuật toán băm SHA-256, bạn sẽ nhận được kết quả sau:

Đầu vào: 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 băm Hàm băm an toàn (SHA-256). Đây là một trong những phương pháp băm phổ biến hiện có, bao gồm Message Direct (MD5) và Hàm băm an toàn (SHA1).

Các thuộc tính chính của hàm băm làm cho nó đáng tin cậy. Hãy liệt kê chúng bên dưới.

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

Chúng tôi đã giới thiệu về Cryptographic Hashing cho người mới bắt đầu ở đây. Hãy khám phá tại đó: Băm mật mã: Hướng dẫn cho người mới bắt đầu. 

Nhưng, nếu bạn ở đây để mua những thứ cao cấp, bạn sẽ không phải thất vọng.

 

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

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

Trong quá trình băm, 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 mảng. Vì vậy, nếu bạn truyền một mảng các phần tử cho các hàm băm, bạn sẽ nhận được đầu ra mảng trong đó mỗi phần tử bây giờ có một khóa được gắn vào nó. Cặp khóa / giá trị rất hữu ích khi truy cập các phần tử trong thời gian thực vì nó cung cấp thời gian O (1) ấn tượng.

Để triển khai các hàm băm, bạn có thể thực hiện hai cách tiếp cận ưa thích.

  • Cách tiếp cận đầu tiên là sử dụng một hàm băm để 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 băm.
  • Một bước khác là đặt phần tử vào bảng băm và sau đó truy xuất nó bằng cách sử dụng khóa băm.

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

băm = hàm băm (khóa) index = hash% array_size

Ở đây, kích thước băm và kích thước mảng là độc lập với nhau. Giá trị chỉ mục được tính dựa trên kích thước mảng. Toán tử modulo (%) cho phép chúng tôi tính toán giá trị.

Nói một cách dễ hiểu, hàm băm 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 băm. Nhiều tên được đặt cho các giá trị được trả về bởi hàm băm. Chúng có thể được gọi là giá trị băm, giá trị băm, tổng băm và mã băm.

 

Viết một hàm băm tốt

Nếu bạn muốn tạo một hàm hoặc cơ chế băm 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 hoặc cơ chế. Hãy liệt kê chúng bên dưới:

  • Hàm băm cần phải dễ tính toán. Điều đó có nghĩa là nó sẽ không mất nhiều tài nguyên để thực thi.
  • Hàm băm cần được phân phối đồng đều. Bằng cách đó, bảng băm được sử dụng để lưu trữ các giá trị băm để việc phân nhóm sẽ không xảy ra.
  • Yêu cầu cuối cùng là ít hoặc không có va chạm. Không có xung đột có nghĩa là không có đầu ra duy nhất 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 băm, và nó đơn giản là không thể bị xóa khỏi hàm băm. Mục đích là tạo ra một hàm băm có thể cung cấp hiệu suất bảng băm 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 băm tốt?

Để hiểu sự cần thiết của một hàm băm 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 bảng Hash bằng kỹ thuật băm 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 băm chỉ cần thêm giá trị ASCII của a (97), g (103) và k (107) và sau đó 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 một phép toán modulo, chúng ta sẽ nhận được cùng một kết quả. Kết quả cuối cùng sẽ là 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 băm cũng sẽ là độ phức tạp O (n), điều này không mong muốn. Chúng tôi có thể dễ dàng kết luận rằng hàm băm mà chúng tôi đã mô tả không phải là tối ưu cho các tình huống thực tế.

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

 

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

Các bảng băm rất hữu ích trong việc lưu trữ kết quả của một hàm băm, tính toán chỉ mục và sau đó lưu trữ một giá trị dựa vào 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).

Bảng băm theo truyền thống là một lựa chọn tốt để giải các bài toán đòi hỏi thời gian O (n).

Vì vậy, nếu bạn chọn một chuỗi có độ dài cố định và sau đó cố gắng tìm hiểu tần suất ký tự của chuỗi.

Vì vậy, nếu string = “aacddce”, thì một cách tiếp cận chung là xem 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 có độ phức tạp 0 (n) thời gian

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)

Kết quả 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 băm trong C ++ và đếm tần suất ký tự.

#include sử dụng không gian tên std; int Tần số [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]); Tần suất [chỉ số] ++; } For (int i = 0; i<26; ++ i) {cout << (ký tự) (i + ‘a’) << ” << Tần suất [i]<< endl; }} Int main () {cout<<"Chào thế giới"; countFre ("abbaccbdd"); }

Đầu ra của chương trình 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 tiếp cận tuyến tính khác.

Cách giải quyết va chạm

Có những cách độc đáo để giải quyết các xung đột trong các hàm băm. Một trong những cách phổ biến là chuỗi riêng biệt còn được gọi là băm mở. Nó được thực hiện với một danh sách được liên kết trong đó mỗi phần tử trong chuỗi 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 liên kết cụ thể, giải quyết xung đột. Điều đó có nghĩa là không có hai giá trị đầu vào nào có thể có cùng giá trị băm đầu ra.

 

Khám phá băm bằng Python

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

Vì băm là một hàm phổ biế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ị băm.

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

băm (đố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 string.

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ụ bên dưới.

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

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

nguyên âm = (‘a’, ‘e’, ​​’i’, ‘o’, ‘u’) print (băm (nguyên âm)) Đầu ra ⇒ -5678652950122127926

Băm trong mật mã

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

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

Merkle Trees

Merkle tree 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ạ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 duy nhất cho cả việc truy cập và lưu trữ dữ liệu. Tuy nhiên, phương trình thay đổi khi có một mạng lưới phi tập trung như bây giờ dữ liệu cần được sao chép giữa hàng trăm đồng nghiệp tham gia.

Merkle tree 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 đồng nghiệp.

Ví dụ về 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 băm làm chức năng cốt lõi để kết nối các nút 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ộ giao dịch.

Nếu bạn muốn tìm hiểu thêm về cây Merkle và cách nó sử dụng băm trong mật mã, hãy xem hướng dẫn chi tiết của chúng tôi:

Hướng dẫn về Merkle Trees. Ở đó, chúng tôi đã thảo luận về cách các cây Merkle triển khai được thực hiện bằng bitcoin và các trường hợp sử dụng khác.

Quy trình khai thác

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

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

Sau khi hoàn tất, tất cả các đồng nghiệp trong mạng đều thừa nhận việc bổ sung khối mới.

Tuy nhiên, điều đó hiếm khi xảy ra vì độ khó mạng, trong hầu hết các trường hợp, luôn cao hơn so với hàm băm đượ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 băm của khối và là một chuỗi tùy ý. Sau khi thực hiện xong, chuỗi nối sau đó 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 này có thể được tóm tắt theo các bước sau:

  • Nội dung được băm để tạo giá trị băm mới bất cứ khi nào 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 băm
  • Quá trình băm diễn ra trên chuỗi liên hệ mới 
  • Giá trị cuối cùng của hàm băm sau đó được so sánh với mức độ khó của mạng
  •  nếu giá trị băm cuối cùng thấp hơn nonce, quá trình sẽ được lặp lại một lần nữa. Quá trình chỉ dừng lại khi giá trị băm lớn hơn giá trị băm.
  • Block tham gia chuỗi khi mức độ khó cao hơn
  • Các thợ đào sau đó 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ệ băm” cũng bắt nguồn từ đây. Tỷ lệ băm là tốc độ diễn ra các hoạt động băm. Tỷ lệ băm cao hơn có nghĩa là các thợ đào sẽ yêu cầu nhiều sức mạnh tính toán hơn để tham gia vào quá trình khai thác.

 

Phần kết luận

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

Vậy bạn nghĩ sao về điều đó? Bình luận bên dưới và hãy cho chúng tôi biết.

 

#FAQ

Băm trong mật mã là gì?

Trong mật mã, băm là một phương pháp để chuyển đổi dữ liệu thành một chuỗi văn bản duy nhất bằng một phương pháp hiệu quả. Ngoài ra, không có giới hạn về loại dữ liệu hoặc kích thước của nó – băm hoạt động trên tất cả chúng.

Cách băm được sử dụng trong mật mã?

Mật mã học sử dụng phép băm để băm mật khẩu hoặc tạo số nhận dạng duy nhất.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map