Rsa

如何從公鑰和私鑰計算 RSA CRT 參數

  • May 25, 2015

給定公鑰 ( n , e ) 和私鑰 ( d ),如何計算這個 RSA 密鑰對的CRT 參數 ( p , q , dP , dQqInv )?

第一步(也是最難的)是考慮因素 $ n $ ; 最簡單的方法(給定 $ e $ 和 $ d $ ) 採用這個隨機程序:

  • 選擇一個隨機值 $ z $ 從範圍 $ (2, n-2) $

  • 計算值 $ \lambda = (ed-1)/2^k $ , 在哪裡 $ k $ 是那個整數 $ \lambda $ 一個奇數。

  • 計算 $ t = z^\lambda \bmod n $ . 如果 $ t = 1 $ 或者 $ t = n-1 $ ,我們在這個選擇上失敗了 $ z $ .

  • 重複執行此操作,最多 $ k $ 次:

    • 計算 $ u = t^2 \bmod n $ .
    • 如果 $ u = -1 $ ,我們在這個選擇上失敗了 $ z $ .
    • 如果 $ u = 1 $ ,我們成功了(我們有分解 $ p = gcd(n,t-1) $ , $ q = gcd(n, t+1) $ )
    • 否則,設置 $ t = u $ , 並繼續下一個循環
  • 如果我們執行上面的循環 $ k $ 幾次都沒有成功或失敗,那麼我們碰巧選擇了一個 $ z $ 這不是相對重要的 $ n $ , 或者 $ d, e $ 不是有效的 RSA 指數對。

的隨機值 $ z $ 最多會失敗一半;所以我們執行這個程序(選擇不同的隨機 $ z $ values) 直到它成功,並給我們分解。

一旦我們有了因式分解 $ n $ ,計算其餘的 CRT 參數是直截了當的。

引用自:https://crypto.stackexchange.com/questions/25907