Khi chúng tôi tạo bất kỳ loại PRNG nào, chúng tôi có thể có dữ liệu không đồng nhất về entropy của nó. Ví dụ: có thể nguồn ngẫu nhiên an toàn bằng mật mã duy nhất của chúng tôi là một tập hợp UUID dạng chuỗi ngẫu nhiên. Tuy nhiên, trong hầu hết các triển khai PRNG, chúng tôi muốn tính ngẫu nhiên của mình đồng nhất và có kích thước cố định. Để có được điều đó, chúng tôi cần một số cách để chắt lọc đầu vào thành kích thước phù hợp và hàm băm là một cách dễ dàng để làm điều đó
Khi chúng tôi có PRNG không mã hóa, đầu vào mà người dùng cung cấp thường có thể có kích thước bất kỳ và việc cho phép người dùng cung cấp hạt giống tùy ý thường hữu ích. Ví dụ: một số trò chơi điện tử cho phép bạn tạo PRNG của chúng bằng văn bản tùy ý để phát lại cùng một trò chơi và điều đó sẽ cần được chắt lọc thành đầu vào phù hợp, trong đó hàm băm phù hợp. Muối trong trường hợp này sẽ không hữu ích vì mục tiêu là tạo ra kết quả xác định
Khi chúng tôi sử dụng CSPRNG, thuật toán chúng tôi sử dụng là xác định, nhưng chúng tôi muốn tạo nó với các đầu vào có đủ entropy để đảm bảo đầu ra của nó là không thể đoán được. Đó là, mục tiêu của chúng tôi là đầu ra không xác định. Một số thiết kế chọn buộc các đầu vào có entropy đồng nhất, nhưng hầu hết các thiết kế sử dụng một số loại hàm dẫn xuất, giống như hàm được sử dụng bởi CTR_DRBG, để cho phép các đầu vào không đồng nhất. Đôi khi các thuật toán đó dựa trên hàm băm và đôi khi chúng không. Ví dụ: CTR_DRBG sử dụng hàm dẫn xuất dựa trên mật mã khối để làm cho toàn bộ thuật toán có thể thực hiện được chỉ bằng một triển khai AES. HMAC_DRBG sử dụng HMAC trong vai trò này, dựa trên hàm băm
Các thiết kế DRBG cho phép sử dụng chuỗi muối hoặc chuỗi cá nhân hóa và điều này thường được khuyến nghị. Một loại muối cố định hoặc không ngẫu nhiên sẽ không cải thiện tính bảo mật nếu không đủ entropy, vì chúng tôi cho rằng muối là công khai, nhưng có những bối cảnh mà nó có thể hữu ích, chẳng hạn như nếu nhiều DRBG phải được tạo từ cùng một đầu vào entropy
Có một số trường hợp chúng tôi sử dụng thiết kế CSPRNG cho đầu ra xác định không thể phân biệt được với ngẫu nhiên và muối rất hữu ích ở đó. Ví dụ: trong RFC 6979, mô tả DSA và ECDSA xác định, chúng tôi sử dụng HMAC_DRBG để tạo giá trị ngẫu nhiên $k $. Khóa riêng là đầu vào entropy của chúng tôi và hàm băm của tin nhắn là muối và cả hai đều cần thiết để bảo mật
Trên các phiên bản trước của Python, tùy chọn này bật ngẫu nhiên hàm băm, để các giá trị hàm băm [] của str, byte và datetime được "muối" với một giá trị ngẫu nhiên không thể đoán trước. Mặc dù chúng không đổi trong một quy trình Python riêng lẻ, nhưng chúng không thể dự đoán được giữa các lần gọi Python lặp đi lặp lại
Ngẫu nhiên hóa băm nhằm cung cấp sự bảo vệ chống lại sự từ chối dịch vụ gây ra bởi các đầu vào được lựa chọn cẩn thận nhằm khai thác hiệu suất trong trường hợp xấu nhất của cấu trúc chính tả, độ phức tạp O[n^2]
Theo mặc định, hàm băm của Python thêm một số ngẫu nhiên vào đầu vào băm để ngăn kẻ tấn công lợi dụng các xung đột đã biết. Băm cùng một cụm từ sẽ không trả về cùng một giá trị nếu bạn gọi chương trình vào các thời điểm khác nhau. Khi gọi tập lệnh python trong dòng lệnh, hãy thêm PYTHONNHASHSEED=0 trước lệnh để tắt tính năng này. Thí dụ. "PYTHONHASHSEED=0 python3 /users/austinvernon/desktop/scripts/python_hash_function. py"
Hàm băm chung
Xác minh các tính năng cơ bản của hàm băm
Băm một đầu vào nhất định luôn dẫn đến cùng một giá trị băm
Giá trị băm được tính toán nhanh
Đầu vào khác nhau có giá trị băm khác nhau
import time start = time.time[] print[hash["susan"]] print[hash["charlie"]] print[hash["susan"]] end = time.time[] print["elapsed time: ",end-start," seconds"]
đầu ra
">-5124793730868099537"
">-7631605457190692542"
">-5124793730868099537"
">elapsed time: 6.99x10^-5" seconds
Các giá trị băm cho "susan" giống nhau, trong khi "charlie" thì khác. Thời gian đã trôi qua để chạy cả ba lần băm là một phần giây
Phục hồi dữ liệu
Từ điển Python sử dụng bảng băm để lưu trữ giá trị. Chúng tôi sẽ so sánh tra cứu danh sách [tìm kiếm tuyến tính] với. một tra cứu từ điển [bảng băm]
Đoạn script sau có một danh sách ngắn và từ điển
import time
dictionary = {"charlie":3, "susan":4, "beth":5 }
list = ["sally", "bob", "joe", "charlie", "susan", "beth"]
#lookups
start = time.time[]
print[dictionary["beth"]]
end = time.time[]
print["Dictionary Lookup Time: ",end-start, " seconds"]
start = time.time[]
print[list.index["beth"]]
end = time.time[]
print["List Lookup Time: ",end-start, " seconds"]
Khi tôi chạy tập lệnh nhiều lần, việc tra cứu danh sách sẽ nhanh hơn. Chi phí băm đầu vào lấn át lợi thế về tốc độ của tra cứu bảng băm đối với các tập dữ liệu ngắn
Hãy thử lại với một danh sách dài hơn. Tôi đã thêm mã để tạo danh sách mới [nhớ thụt vào thân vòng lặp nếu sao chép/dán làm hỏng nó]
import time
import random
import string
#set variables
dictionary = {}
list = []
i=0
#loop to create random list and dictionary
while i < 10000: #change list size here
letters = string.ascii_lowercase
phrase = ''.join[random.choice[letters] for j in range[10]]
list.append[phrase]
dictionary[phrase] = i
i += 1
#append our targets to end of list and dictionary
list.append["beth"]
dictionary["beth"] = i
#lookups
start = time.time[]
print[dictionary["beth"]]
end = time.time[]
print["Dictionary Lookup Time: ",end-start, " seconds"]
start = time.time[]
print[list.index["beth"]]
end = time.time[]
print["List Lookup Time: ",end-start, " seconds"]
Tôi đã tăng dần kích thước danh sách lên gấp 10 lần cho đến khi tôi tìm thấy điểm giao nhau ở mức 10.000. Khi kích thước danh sách tăng lên, thời gian tra cứu từ điển vẫn giữ nguyên trong khi thời gian tra cứu danh sách tăng lên. Đặt các giá trị x khác nhau cho "i < x" để thay đổi kích thước danh sách và khám phá mối quan hệ
Sự chính trực
Ý tưởng cơ bản của việc kiểm tra một tệp hoặc cụm từ vốn có đối với các hàm băm chung, như được trình bày trong phần "Hàm băm chung"
Cây Merkle
Chúng tôi sẽ băm một tập hợp các khối dữ liệu thành Cây Merkle, sau đó thay đổi một khối để xem nó lan truyền qua cây như thế nào. Để tham khảo, cấu trúc Merkle Tree
cây đầu tiên
#Pair 1
#data block 1
hash_value_00 = hash['bob']
print["Hash Value 00: ",hash_value_00]
#data block 2
hash_value_01 = hash['alice']
print["Hash Value 01: ",hash_value_01]
#Pair 2
#data block 3
hash_value_10 = hash['sam']
print["Hash Value 10: ",hash_value_10]
#data block 4
hash_value_11 = hash['charlie']
print["Hash Value 11: ",hash_value_11]
#Level2 Hash Values
hash_value_0 = hash[str[hash_value_00] + str[hash_value_01]]
print["Hash Value 0: ",hash_value_0]
hash_value_1 = hash[str[hash_value_10] + str[hash_value_11]]
print["Hash Value 1: ",hash_value_1]
#root hash/top hash/ Merkle Root
top_hash_value = hash[str[hash_value_1] + str[hash_value_0]]
print["Top Hash Value: ",top_hash_value]
đầu ra
Hash Value 00: -4208795585541223758
Hash Value 01: 8512114763159807471
Hash Value 10: 1019084245346364989
Hash Value 11: -7631605457190692542
Hash Value 0: -4765654072729701387
Hash Value 1: -4212900652853811053
Top Hash Value: -8281923323636112442
Hãy sử dụng cùng một mã, ngoại trừ thay đổi chuỗi trong "khối dữ liệu 2" từ "alice" thành "alicia"
đầu ra
Hash Value 00: -4208795585541223758
Hash Value 01: -4059417228946341628
Hash Value 10: 1019084245346364989
Hash Value 11: -7631605457190692542
Hash Value 0: 2860753682179309060
Hash Value 1: -4212900652853811053
Top Hash Value: 3683710842423746868
Để tìm khối dữ liệu xấu được cung cấp giá trị băm trên cùng, bạn yêu cầu lớp tiếp theo của cây băm. Vì chỉ khác "giá trị băm 0" nên bạn có thể bỏ qua việc kiểm tra nhánh "giá trị băm 1" của cây. Tiếp theo, yêu cầu hai giá trị băm tạo thành "giá trị băm 0". Bạn sẽ nhận ra rằng "giá trị băm 01" là thủ phạm. Cây Merkle giúp cuộc săn này nhanh hơn vì bạn có thể bỏ qua các bộ phận của cây. Tìm kiếm cây Merkle là một biến thể của chủ đề tìm kiếm nhị phân trong khoa học máy tính. Giống như sử dụng bảng băm, tập dữ liệu gốc càng lớn thì Merkle Trees càng có nhiều lợi thế
Hàm băm mật mã
Một trong những hàm băm mật mã được sử dụng phổ biến nhất là SHA-256, một phần của họ hàm băm SHA-2. Python có một thư viện để sử dụng các hàm SHA-2, nhưng nó không thân thiện với người dùng bằng cách gọi hàm "hash[]" đơn giản
Hàm SHA256 yêu cầu đầu vào phải được mã hóa vì nó không băm trực tiếp văn bản gốc. Các đầu ra được chuyển đổi trở lại thành định dạng mà con người có thể đọc được
import hashlib
input = "sally sells seashells"
# encoding then hashing
result = hashlib.sha256[input.encode[]]
# To print, we have to convert the sha256 object to hexadecimal
print[result.hexdigest[]]
Kết quả
________số 8_______Lưu ý rằng giá trị băm dài hơn nhiều và chứa các ký tự không phải là số. Phạm vi của các giá trị có thể giúp ngăn ngừa va chạm
Bằng chứng làm việc
Hãy thực hiện một bài tập bằng chứng công việc tương tự như những gì Bitcoin sử dụng. Bitcoin sử dụng SHA-256 làm hàm băm của nó. Ý tưởng là tìm một giá trị băm với một số số 0 đứng đầu nhất định. Đầu vào của hàm băm là giá trị băm của tất cả các khối trước đó cộng với một nonce. Số nonce là số ngẫu nhiên chỉ được sử dụng một lần. Đây là đoạn mã [hãy nhớ thụt lề thân vòng lặp nếu sao chép/dán làm hỏng nó]
import hashlib
transaction = "Alice sends 10 AliceCoins to Bob"
transaction_hash = hashlib.sha256[transaction.encode[]]
print["transaction hash: ",transaction_hash.hexdigest[]]
#loop to hash the transaction hash with nonces, using i as nonce
i = 0
while i < 11:
pow_input = transaction_hash.hexdigest[] + str[i]
pow_hash = hashlib.sha256[pow_input.encode[]]
print["PoW Hash ",i, ": ",pow_hash.hexdigest[]]
i += 1
Kết quả
">-5124793730868099537"
">-7631605457190692542"
">-5124793730868099537"
">elapsed time: 6.99x10^-5" seconds
Chúng tôi nhận được số 0 đứng đầu đầu tiên bằng cách sử dụng nonce 10 cho giá trị băm đầu vào cụ thể này. Bạn có thể thay đổi các lần lặp lại giao dịch, nonces hoặc vòng lặp để xem các kết quả khác nhau