Có cách tiêu chuẩn nào để tạo số ID lần lượt sao cho:
- Bạn có thể đảm bảo, hoặc gần như đảm bảo, rằng bạn tránh va chạm. (Theo "gần như đảm bảo", ý tôi là ví dụ: nếu bạn tạo các số có 24 chữ số hoàn toàn ngẫu nhiên và bạn "chỉ" tạo ra 1 triệu trong số đó, thì ngay cả với nghịch lý ngày sinh, tỷ lệ va chạm sẽ rất nhỏ.)
- Bạn muốn số ID ngắn gọn, không khó sử dụng - cụ thể là bạn đừng muốn dựa vào độ dài của số ID (và chọn các giá trị ngẫu nhiên) để tránh xung đột, như được mô tả trong dấu đầu dòng trước đó. Bạn phải làm điều đó một số cách khác.
- Bạn không muốn tránh xung đột mỗi khi tạo một giá trị mới bằng cách xem tất cả các giá trị có sẵn để xem giá trị đó đã được sử dụng chưa. Đây sẽ chỉ là tra cứu nhật ký (n) mỗi lần trong danh sách được sắp xếp, nhưng giả sử tôi muốn tránh điều này.
- Bạn không muốn số ID tiết lộ bất kỳ thông tin nào về thời điểm tạo hoặc số lượng ID được tạo giữa số ID X và số ID Y. Không có điều kiện này, vấn đề là tầm thường; bạn chỉ có thể sử dụng thời gian của đồng hồ (cộng với một số giá trị ngẫu nhiên đủ lớn để tránh xung đột giữa các số được tạo trong cùng một giá trị thời gian của đồng hồ) hoặc bạn chỉ có thể sử dụng các số nguyên tuần tự (ngoại trừ bây giờ kẻ tấn công biết rằng nếu ai đó tạo giá trị ID 5000 trên Ngày 1 tháng 3 và giá trị ID 6000 vào ngày 1 tháng 4, có 1000 giá trị khác được tạo trong khoảng thời gian đó).
Tôi đã cố gắng tìm một câu trả lời tầm thường, nhưng không có câu trả lời nào tôi thử có vẻ hiệu quả. Bạn chỉ có thể lấy hàm băm SHA-256 của các số 1, 2, 3, v.v. (cộng với một số khóa bí mật), nhưng điều này có cùng vấn đề với việc chỉ chọn các số ngẫu nhiên từ không gian có sẵn -- nếu bạn đang dựa vào độ dài của hàm băm (ví dụ: SHA-256) để tránh xung đột, số ID thu được sẽ dài và khó sử dụng, đồng thời nếu bạn tạo hàm băm ngắn hơn, bạn sẽ tăng khả năng xảy ra xung đột.
Hoặc bạn có thể tạo ID mới bằng cách tăng mỗi lần một giá trị ngẫu nhiên trong khoảng từ 1 đến n, thay vì luôn tăng theo 1. Vấn đề là tùy thuộc vào những gì kẻ tấn công có thể làm, chúng có thể tìm ra n là gì -- nếu chúng có khả năng tạo hai ID theo thứ tự và thực hiện lặp đi lặp lại, họ có thể tìm ra n hoặc nếu họ có khả năng kiểm tra ID nào hợp lệ, họ có thể kiểm tra mọi số trong một số phạm vi nhỏ, để xem mức độ dày đặc của ID hợp lệ ID là, và tìm ra n từ đó.
Loại giải pháp duy nhất tôi có thể tìm thấy như sau: Trước tiên, hãy chuẩn bị trước một số công việc. Tuy nhiên, đối với nhiều giá trị ID mà bạn muốn tạo (giả sử 1 triệu), hãy lấy tất cả các số nguyên từ 1 đến 1 triệu và theo thứ tự, bắt đầu tính hàm băm của mỗi số nguyên cộng với một khóa bí mật. Cắt bớt hàm băm thành bất kỳ giá trị nào bạn cho là đủ ngắn. Tuy nhiên, với một khoảng thời gian cắt đủ ngắn, bạn sẽ thấy các xung đột. Vì vậy, mỗi khi bạn tạo một hàm băm cắt ngắn mới cho một số nguyên nhất định, hãy kiểm tra nó với các giá trị được tạo trước đó và nếu có xung đột, hãy thêm số nguyên đó vào danh sách L các số nguyên trong đó hàm băm của số nguyên đó xung đột với hàm băm của một số nguyên nhỏ hơn. (Vì vậy, trên thực tế, nếu kế hoạch của bạn là tạo 1 triệu ID, thì trong quá trình chuẩn bị của anh ấy, bạn sẽ phải sử dụng một chút 1 triệu số nguyên cuối cùng để bù cho những số nguyên mà bạn đã bỏ qua.)
Sau đó, trong thời gian chạy khi bạn tạo ID của mình, bạn chỉ cần bắt đầu với một bộ đếm số nguyên. Mỗi lần bạn tạo một ID mới, bạn tăng số nguyên và kiểm tra xem nó có trong danh sách L của bạn không, nếu có, bạn bỏ qua và chuyển sang số nguyên tiếp theo. (Điều này liên quan đến "tra cứu nhật ký", dường như vi phạm một trong các quy tắc đã nêu của tôi, nhưng điều tôi thực sự muốn làm là tránh phải kiểm tra từng giá trị ID mới với mọi giá trị được tạo cho đến nay; việc kiểm tra L sẽ nhanh hơn nhiều.) Và bạn có thể tinh chỉnh điều này để cân bằng (bạn thực hiện các giá trị băm bị cắt ngắn càng lâu thì L sẽ càng ngắn và do đó, lần kiểm tra sẽ càng ngắn mỗi khi bạn tạo ID mới; nhưng giá trị ID dài hơn có thể không được mong muốn).
Nhưng điều này cảm thấy giống như một hack. Có một cách tiêu chuẩn? Nếu không, bạn có thể nghĩ ra một cách tốt hơn?
