Tham gia Đăng nhập
Điểm:1
Tom avatar Crypto

Làm cách nào để đo độ dài của chu kỳ PRNG 128-bit?

lá cờ tf
Tom

Tôi đã khóa PRNG 128 bit. Nó đã vượt qua các bài kiểm tra PractRand và Dieharder, nhưng tôi không biết chiều dài chu kỳ dự kiến ​​của nó là bao nhiêu (đối với các khóa khác nhau và các hạt giống khác nhau).

Có cách nào để ước tính nó, thông qua kết quả phân tích của trình tạo này không? Tôi đang cố gắng phân tích các chu kỳ ở các phần 16 bit của đầu ra 128 bit. Các số 16 bit lặp lại trong các phần 16 bit bị cắt ngắn của đầu ra 128 bit ở mức trung bình trong mỗi $6331708$ các bước. Ví dụ số $14649$ xảy ra ở 16 bit thấp bất thường sau:

$1385856, 6793856, 4734720, 4043776, 17823744, 3705088, 5609216, 1174784, 3718656, 181504, 14063616, 13729024, 10346880, 15782016, 1561088, 1996672, 988544$

các bước (và có vẻ tương tự khi chúng tôi kiểm tra mọi số 16 bit khác, bằng các phím khác). Nhưng trên cơ sở phân tích các bộ phận của bộ tạo 16 bit liên tiếp như vậy, có thể rút ra kết luận nào về chu kỳ của toàn bộ bộ tạo không?

Nhân tiện, chẳng phải chúng ta mong đợi một số 16-bit ngẫu nhiên xuất hiện một lần trong mỗi $2^{16}$ bước? Lúc đầu, các số 16 bit được chọn ngẫu nhiên xảy ra rất hiếm đối với tôi hay tôi đang hiểu nhầm điều gì đó?

64
0 + 0
fgrieu avatar
lá cờ ng
fgrieu
Có thể chứng minh bằng thực nghiệm rằng PRNG không an toàn hoặc có thời gian ngắn. Không có phương pháp nào kiểm tra đầu ra của nó có thể xác định rằng nó an toàn hay có thời gian dài. Đối với điều này, cần kiểm tra cách thức hoạt động của PRNG.
3
Hồi đáp
Tom avatar
lá cờ tf
Tom
Ok, tôi phải cân nhắc rằng tôi không có lý thuyết nào về chu kỳ. Vì vậy, không có cách nào để biết bất cứ điều gì về thời gian của PRNG? Vì vậy, nó không thành vấn đề nếu nó chuyển PractRand thành 2^42 byte, nó có thể đi vào chu kỳ dài $2^{50}$ hoặc $2^{100}$ và chúng tôi không thể tìm ra nó như thế nào, chỉ bằng cách phân tích đầu ra?
0
Hồi đáp
Maarten Bodewes avatar
lá cờ in
Maarten Bodewes
Theo định nghĩa (?), đầu ra của RNG sẽ không cho bạn biết bất cứ điều gì về trạng thái của PRNG. Vì vậy, chỉ nhìn vào các phần của đầu ra, bạn sẽ không thu được nhiều thông tin chi tiết nếu có bất kỳ hiểu biết nào về khả năng xảy ra một chu kỳ. Bạn chỉ có thể tìm thấy những điểm bất thường, nhưng những điểm bất thường đó sẽ xuất hiện trong quá trình thử nghiệm. Nếu các bài kiểm tra thất bại thì tôi đoán rằng đó có phải là một chu kỳ hay không thì không quan trọng :)
2
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
Chính xác. Trừ khi khoảng thời gian thấp hơn (với một chút biên độ) so với độ dài được kiểm tra, kiểm tra thống kê hoạt động trên đầu ra của PRNG không thể tìm thấy khoảng thời gian. Một lần nữa, các bài kiểm tra thống kê chỉ hữu ích để chứng minh rằng các PRNG xấu là xấu hoặc/và có thời gian ngắn. Khi thử nghiệm không tìm thấy lỗi/trong thời gian ngắn, chúng tôi không thể đưa ra kết luận nào về PRNG đã thử nghiệm. Giống như sau khi nhìn thấy một con kiến ​​đi qua cây cầu một cách an toàn, chúng ta không thể đưa ra kết luận tích cực nào về cây cầu. Chúng ta cần xem sơ đồ thiết kế của nó và kiểm tra cấu trúc của nó.
3
Hồi đáp
kodlu avatar
lá cờ sa
kodlu
tuyên bố của bạn là không chính xác. nếu đó là các bản phân phối khoảng cách cho một âwindowâ 16 bit cụ thể, bạn đã kiểm tra *tất cả* các cửa sổ 16 bit chưa? phân phối khoảng cách đó có phải là điển hình cho toàn bộ cửa sổ 16 bit không?
0
Hồi đáp
Tom avatar
lá cờ tf
Tom
@kodlu Tôi đã làm sai, không thể có khoảng cách lớn như vậy và không có (tôi đã viết sai mã Python).
0
Hồi đáp
user2357 avatar
lá cờ us
user2357
@fgrieu còn lfsr thì khoảng thời gian dài nhất được tính toán và nó có thể đạt được bằng cách xem xét các đa thức nguyên thủy thì sao? Tôi vừa đọc về một thứ như thế trong cuốn sách có tựa đề hiểu về mật mã.
0
Hồi đáp
Điểm:3
poncho avatar Crypto
lá cờ my
poncho

Có cách nào để ước tính nó, thông qua kết quả phân tích của trình tạo này không?

Như các bình luận đã nói, không thực sự (trừ khi máy phát điện thực sự tồi tệ).

Tôi đang cố gắng phân tích các chu kỳ ở các phần 16 bit của đầu ra 128 bit. Nhân tiện, chẳng phải chúng ta mong đợi một số 16-bit ngẫu nhiên xuất hiện một lần trong mỗi $2^{16}$ bước?

Điều mà một PRNG tốt nên làm là khuấy tất cả các bit của trạng thái lại với nhau, do đó, việc xem xét các đoạn 16 bit bị cắt ngắn sẽ không cho bạn biết bất cứ điều gì.

Mặt khác, bạn dường như liệt kê các khoảng trống trong các lần xuất hiện của một giá trị 216 bit cụ thể (14649) và những khoảng trống đó trông khá kỳ quặc. Nếu PRNG tốt, chúng tôi hy vọng khoảng cách giữa các lần xuất hiện sẽ tuân theo phân phối theo cấp số nhân (với giá trị trung bình là 65536, như bạn đã nói); mặc dù đôi khi bạn sẽ thấy khoảng cách lớn hơn đáng kể so với giá trị trung bình, nhưng hầu như bạn sẽ không bao giờ thấy khoảng cách gấp 100 lần giá trị trung bình (và bạn thậm chí còn hiển thị khoảng cách lớn hơn) - đây là kiểu 'trúng xổ số nhiều lần' biến cố. Thực tế là bạn dường như cho thấy a) Tôi không diễn giải dữ liệu chính xác, b) bạn không đo lường khoảng cách một cách chính xác hoặc c) PRNG không đồng nhất nghiêm trọng.

Việc kiểm tra tính không đồng nhất rất đơn giản - chỉ cần chạy PRNG và đếm số lần bạn nhìn thấy từng giá trị - nếu bạn thấy các giá trị có số lần đếm là bội số lớn của độ lệch chuẩn so với giá trị trung bình (theo bất kỳ hướng nào), thì bạn đang gặp vấn đề nghiêm trọng. vấn đề.

Tất nhiên, nếu đây được coi là một trình tạo số ngẫu nhiên an toàn bằng mật mã, thì các yêu cầu đối với điều đó nghiêm ngặt hơn đáng kể ...

0 + 0
Tom avatar
lá cờ tf
Tom
Bạn nói đúng, tôi đã sai mã và đo sai các lần lặp lại này. Với độ lệch như vậy, máy phát điện này chắc chắn sẽ thất bại trong các bài kiểm tra. Dù sao đi nữa, tôi phải nghiên cứu lý thuyết về chu kỳ của máy phát điện này.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.