使用密碼初始化 PRNG
假設我們有一個安全的 PRNG。使用密碼初始化它是否“安全”，或者基於 SHA256（密碼）等密碼的種子？
如果是，從中生成 RSA 或 DSA 密鑰是否“安全”？
這背後的想法是使用密碼初始化 PRNG，然後使用它來生成 RSA 或 DSA 密鑰。因此，該方案在生成私鑰時將始終生成相同的素數，這意味著您無需將私鑰儲存在任何地方，而是在每次需要時重新生成它。只需要儲存（或記住）密碼。
更新：顯然這種方案會繼承錯誤密碼選擇的一般風險，但是需要合理範圍的字元的密碼怎麼樣。或者，可以使用 2 個密碼，其中系統使用第二個密碼作為 PBKDF2 計算的鹽。
不，使用密碼雜湊為 PRNG 播種，然後從該 PRNG 生成密鑰是不安全的。這對於 DSA 和共享參數來說尤其糟糕 $ (p,q,g) $ , 並且對於 RSA 或帶有每個密鑰參數的 DSA 的不安全性略低一些 $ (p,q,g) $ . 缺少兩個必需品：一些緩慢的步驟和鹽。
如果應用了建議的程序，那麼測試給定密碼是否是正確密碼所要做的一切（以高可信度）歸結為
Check(password)：
- 散列輸入
password。- 使用該雜湊播種 PRNG。
- 按照正常的密鑰生成過程，使用該 PRNG 生成密鑰。
true如果步驟 3 中生成的密鑰的公鑰部分與已知公鑰匹配，則返回；else returnfalse（對於對稱密碼學，使用步驟 3 中生成的密鑰來解密一部分密文，測試結果是否與已知明文匹配；或者，由於缺少大量已知明文，測試候選明文中的字節分佈不均勻，根據卡方檢驗，在有疑問時破譯更多明文）。這些步驟都不是計算密集型的；這是第一個問題。攻擊者可以列舉可能的密碼，直到找到正確的密碼。密碼破解者的基本功能是使用上述程序從最可能到最不可能測試密碼，
Check(password)直到它返回true；此時恢復密鑰的任何非公開部分和任何明文都是微不足道的。如果我們假設實際密碼是隨機選擇的，或者密碼破解者擅長從最有可能到最不可能的順序測試密碼，那麼找到密碼的預期成本為 $ N $ 熵位是 $ C\cdot2^{N-1} $ ， 在哪裡 $ C $ 是上述
Check(password)過程的平均成本。成本可以用貨幣或能源單位表示；或者在核心時間中，在這種情況下，攻擊的預期持續時間是其成本除以平均核心數量。在具有共享參數的 DSA 的特殊情況下 $ (p,q,g) $ , 步驟 3 歸結為生成 $ x $ 和 $ 0<x<q $ （密鑰的私有部分）通過直接呼叫 PRNG，然後計算 $ y=g^x\bmod p $ （公鑰的特徵部分）。如果簡單地執行模冪運算，就會成為
Check(password). 測試並非不現實 $ 10^4 $ 即使使用這種簡單的算法，每秒每個核心的密碼；並且有一個簡單的時間 - 記憶權衡，通過預先計算，我猜可以將冪運算速度提高 10 倍或更多 $ g^u\bmod p $ 為了 $ u $ 形式的 $ u=v·2^{j·w} $ 和 $ 0≤v<2^w $ ，這允許將模乘的數量減少一個因子 $ {3\over2}·w $ 與直接模冪運算相比。因此，我將假設成本 $ 10^{-5} $ core·second（可能需要專門的 CPU 指令用於 PRNG 使用的散列和分組密碼，但這種情況越來越普遍）。XKCD對 4 字密碼熵的估計為 $ N=44 $ 位；讓我們使用它，即使它看起來不僅僅是常見的做法。我們得到一個預期的 $ 2^{44-1}·10^{-5}/3600/24≈10^3 $ 核。幾天才能找到密碼。使用租用的 CPU 時間 $ \$0.2 $ 每核心·天（基於EC2 現貨價格），預期貨幣成本為 $ \$200 $ 加上適應現有的密碼破解程序。對於Sequoia及其 1572864 個核心，這是 $ 2^{44-1}·10^{-5}/1572864/60≈1 $ 分鐘。
使用 RSA 或帶有每個密鑰參數的 DSA，測試密碼的成本可能要高出兩個十進制數量級（因為第 3 步要復雜得多），這將使方案的不安全性相應降低；但這是一個神器，仍然非常不安全。
此外，該過程中只有第 4
Check(password)步取決於密鑰；這是第二個問題。這一事實使攻擊者可以根據多個使用者的密鑰攤銷所有其他成本。所要做的就是將步驟 4 替換為 如果步驟 3 中生成的密鑰的公共部分與任何已知的公共密鑰匹配，則返回該密鑰的標識符；否則返回not_found；該更改引入的額外成本可以忽略不計（對於每個測試的密碼：僅一個索引記憶體訪問的記憶體比儲存公鑰所需的記憶體多一點）。這種微不足道的變化降低了與使用者數量成比例的預期攻擊成本，這對安全來說是一場災難。作為一個相關問題，彩虹表可以計算一次，其成本或延遲僅為查找一個特定密鑰的密碼所需的成本或延遲的幾倍；在最初的努力之後，大多數鑰匙都是易碎的，沒有相當大的成本或延遲。補充一點，對於攻擊者來說，熵更差的密碼通常是最重要的（例如，當限製或考慮使用在多個使用者之間共享的資源時），並且相當大一部分使用者選擇了糟糕的密碼，你會發現一個實用的僅使用商用硬體即可以低成本進行攻擊，並且成功機率很高。
如果要從密碼生成密鑰，正確的技術是通過將密碼（以及如果可能的話，每個使用者的salt ）**拉伸為偽隨機位來替換散列（以及可選的 PRNG），使用適當參數化的基於密碼的密鑰派生函式。典型的 PBKDF 是一個公開的、確定性的、可計算的函式，接受密碼（假定為秘密）、鹽（可能是公開的）和一些控制其評估成本（通常是輸出大小）的參數作為輸入。該 PBKDF 的行為應類似於（至少）其密碼和鹽輸入的偽隨機函式。
PBKDF以高且可參數化的次數迭代地轉換密碼和鹽（或從它們派生的東西） 。這種轉換使得需要較少迭代的捷徑不太可能是可行的。迭代次數應選擇為合法使用所能容忍的最高值。這大大提高了攻擊者的成本，因為它必須在 . 的步驟 1 中評估 PBKDF
Check(password)。最重要的是，後期步驟的優化（如 PRNG、包括模冪運算、素數測試的密鑰生成……）不再顯著幫助攻擊者。最小通用 PBKDF 是PBKDF2，基於迭代散列；一個非常嚴重的缺點是它非常容易受到使用 ASIC 或 GPU 的硬體輔助加速的影響。更好的一個是Bcrypt ，也稱為Eksblowfish，它通過使用 4kiB RAM 使得這種加速變得不那麼經濟。最先進的技術是scrypt：它提供更大且可參數化的 RAM 使用量（進而以相對精確可預測的方式顯著提高攻擊成本）；通過使用Salsa20/8對大規模硬體加速具有結構性保護；可以使用多個核心（如果可用）來減少合法使用者感知的時間損失，並帶有令人信服的安全論據。
鹽可以是（比如說）128 位隨機的（如果可能的話，這是最好的）；或者只是一個唯一標識符（例如使用者的電子郵件與給定伺服器的所有使用者共同的值連接）。每個公鑰的鹽值不同就足夠了，以確保密碼破解者必須評估每個測試的密碼·密鑰組合的 PBKDF，而不是每個測試的密碼；在大多數實際應用中，鹽幾乎是免費的。此外，如果鹽是不可預測的，那麼對手在得到鹽之前就無法開始攻擊。
使用加鹽 PBKDF，測試密碼的預期成本成為可以調整的參數，作為安全性和合法使用成本之間的折衷。將腳本參數化為在每核 1 GB RAM 的 4 核機器上需要 0.5 秒（公平的台式 PC；在成本較低的雙核攜帶式 PC 上可能轉換為 3 秒）；使用與密鑰關聯的電子郵件地址和任意固定字元串作為鹽；並且您可以相當有信心地認為，今天的超級電腦每猜出一個 XKCD 級密碼需要數週時間（忽略紅杉的 1572864 核心之一與台式 PC 中的一個核心之間難以估計的差異，攻擊的預期持續時間是 $ 2^{44-1}·0.5·4/1572864/3600/24>129 $ 天，因此攻擊在不到 2 週內成功的機率小於 36 分之一）。每隔奇數年調整一次參數（當你強制使用者更改密碼和密鑰時），你就有了不錯的長期安全性。
警告：強烈建議將密鑰依賴於密碼以外的秘密，作為鹽的一部分。當使用者被允許選擇他們的密碼並且沒有動機選擇一個好的密碼時，這是一種實際的必要性。
另外：習慣上允許使用者更改密碼，同時保持相同的公鑰。一種簡單的技術是：
- 生成一個真隨機種子 S，例如 256 位，只要使用者保持相同的非對稱密鑰，它就會保持不變。
- 使用適當參數化的 PBKDF 將密碼和鹽擴展為對稱密鑰 K，例如 256 位。
- 儲存 S 和 K 的異或；將用於從密碼重新計算 S，並將調整為更改密碼而不更改 S。
- 用 S 播種 PRNG。
- 使用 PRNG 生成非對稱密鑰（公共和私有）。
實現相同目標的一種常用的、稍微複雜的技術是使用 K 對稱加密非對稱密鑰；這避免了每次輸入密碼時重新生成非對稱密鑰，最重要的是允許各種生成算法和 PRNG 的互操作性。
進一步問：
如果嚴格要求從盡可能少的位中派生密鑰（如果您在某些時候需要加鹽，它會計入這些位），從 N 位播種 PRNG 是否可以接受，或者是否有更好的方法每位輸入的安全級別？
如果鹽被視為與秘密密碼相同的輸入（儘管鹽通常被認為是公開的並且免費提供，例如密鑰持有者的姓名或電子郵件），那麼最好不要加鹽。
再次總結一下，如果輸入熵很低，那麼將寶貴的少量資訊提供給 PRNG（直接或通過標準雜湊）然後使用 PRNG 建立密鑰（無論是非對稱的，還是快速對稱算法）。在輸入和攻擊者可以觀察到的任何東西（公鑰或密文）之間的某個地方，必須有一個固有的昂貴過程，即 PBKDF。如果可能的話，它的鹽輸入對於每個使用者應該是不同的，而不會減少秘密中的熵。如果使用者必須記住整個秘密輸入，不使用 PBKDF 就構成重大過失；如果使用者的任何特徵可用，則不加鹽該 PBKDF 也是如此。