如何生成用於創建 CTF 挑戰的大整數私鑰？

我正在嘗試創建一個 RSA CTF 挑戰，公開 $ n $ , $ e $ , $ c $ ， 和 $ d $ .

我已經設定 $ e=65537 $ 和 $ n = p * q $ 在哪裡 $ p $ 和 $ q $ 是大素數，每個都有 300 位數字。

我已經確定 $ c=m^e \mod n $

但我還沒有確定一個好的生產方式 $ d=e^{(-1)} \mod [(p-1)*(q-1)] $ . 我嘗試通過程式碼按原樣計算權利，但是

from decimal import Decimal

print(Decimal(e**(-1)) % phi)

返回類似的東西 $ 0.00001525855623540900559906297040 $ ，我想要一個自然數。什麼是大批量生產的有效方法 $ d $ ? 是否有工具/網站/軟體/算法/計算器/等。用於創建一個大 $ d $ ?

TLDR：類似於這個網站的東西，但適用於相當大的數字。

您可以使用擴展歐幾里得算法來計算 $ d $ . 引用維基百科，給出 $ a $ 和 $ b $ ，擴展歐幾里得算法給你 $ x $ 和 $ y $ 這樣

$$ ax+by = \gcd{(a,b)}. $$

自從 $ e $ 是素數， $ \gcd{(e, \varphi(n))}=1 $ ，所以算法給你 $ x $ 和 $ y $ 和

$$ ex+\varphi(n)\cdot y=1 $$

意思是

$$ ex \equiv 1 \mod{\varphi(n)} $$

因此你可以使用 $ x $ 作為 $ d $ .

---

對於您的實際應用，真正了不起的 Python 標準庫具有內置的三元 pow 函式，可以計算從 Python 3.8 開始的模乘逆

>>> p=17125458317614137930196041979257577826408832324037508573393292981642667139747621778802438775238728592968344613589379932348475613503476932163166973813218698343816463289144185362912602522540494983090531497232965829536524507269848825658311420299335922295709743267508322525966773950394919257576842038771632742044142471053509850123605883815857162666917775193496157372656195558305727009891276006514000409365877218171388319923896309377791762590614311849642961380224851940460421710449368927252974870395873936387909672274883295377481008150475878590270591798350563488168080923804611822387520198054002990623911454389104774092183
>>> pow(3,-1,p)
5708486105871379310065347326419192608802944108012502857797764327214222379915873926267479591746242864322781537863126644116158537834492310721055657937739566114605487763048061787637534174180164994363510499077655276512174835756616275219437140099778640765236581089169440841988924650131639752525614012923877580681380823684503283374535294605285720888972591731165385790885398519435242336630425335504666803121959072723796106641298769792597254196871437283214320460074950646820140570149789642417658290131957978795969890758294431792493669383491959530090197266116854496056026974601537274129173399351334330207970484796368258030728
>>>

引用自：https://crypto.stackexchange.com/questions/93345