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 參數是直截了當的。