Q

提取PRNG的初始種子值？

2011-10-06 24 views 2 likes

2

最近，我讀，你可以預測PRNG的結果，如果你：提取PRNG的初始種子值？

知道正在使用哪種算法。
有連續的數據點。

是否可以從數據點中計算出用於PRNG的種子？

2011-10-06 Blender

+0

理論上，是的。實際上，可能不是。根據種子值的可能範圍和數據點的可能值，您需要將搜索範圍縮小到一個特定種子的數據點數量非常大。 – geoffspear

A

回答

2

我設法找到Kelsey et al的論文，詳細描述了不同類型的攻擊，並總結了一些真實世界的例子。似乎大多數攻擊依賴於類似技術來對付密碼系統，並且在大多數情況下實際上利用了PRNG被用於密碼系統的事實。

2011-10-06 14:34:14

+0

謝謝，我正在閱讀本文。 – Blender

1

肯定的是，「足夠」的數據點是由PRNG生成的絕對第一個數據點，沒有間隙。大多數PRNG功能都是可逆的，所以只需反向工作，就可以獲得種子。

例如，典型的return seed=(seed*A+B)%N具有return seed=((seed-B)/A)%N的倒數。

2011-10-06 14:32:32 Blindy

+0

但在現實生活中，您很少會獲得連續的數據點。連續的數據點塊（按照輸出順序而言，它們之間距離不會太遠）是否可能？ – Blender

+1

也許吧，但是你必須以不同的方式來做，即從每一個可能的種子開始，並試着看看你是否可以按正確的順序生成每個塊。可行但費時，而且您需要一個非常大的樣本來避免誤報。 – Blindy

0

如果你「允許」強行推測種子的所有可能值，並且如果你有足夠的數據點，只有一個種子可以產生該輸出，那麼總是在理論上是可能的。如果PRNG隨時間播種，並且大致知道發生了什麼時，那麼這可能會非常快，因爲沒有太多合理的值可供嘗試。如果PRNG用來自具有64位熵的真正隨機源的數據播種，則這種方法在計算上是不可行的。

是否還有其他技術取決於算法。例如，對Blum Blum Shub這樣做相當於整數因子分解，這通常被認爲是一個難以計算的問題。其他更快的PRNG在這個意義上可能不太「安全」。任何用於加密目的的PRNG，例如流密碼，幾乎都不需要知道可行的方法。

2011-10-06 15:55:41

相關問題