Rsa
如何從公鑰和私鑰計算 RSA CRT 參數
給定公鑰 ( n , e ) 和私鑰 ( d )，如何計算這個 RSA 密鑰對的CRT 參數 ( p , q , dP , dQ和qInv )？
第一步（也是最難的）是考慮因素 $ 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 參數是直截了當的。