# How to generate large integer private key for creating CTF challenges?

I am trying to create a RSA CTF challenge, exposing $$n$$, $$e$$, $$c$$, and $$d$$.

I have set $$e=65537$$ and $$n = p * q$$ where $$p$$ and $$q$$ are large primes each with 300 digits.

I have determined $$c=m^e \mod n$$

But I have yet to determine a good way to produce $$d=e^{(-1)} \mod [(p-1)*(q-1)]$$. I tried computing the right as is via code, but

from decimal import Decimal

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


returns something like $$0.00001525855623540900559906297040$$, and I want a natural number. What is an efficient way to producing a large $$d$$? Is there tool/website/software/algorithm/calculator/etc. for creating a large $$d$$?

TLDR: Something like this website but works with rather large numbers.

• Btw., the python code calculates e**(-1) over the real numbers, so its the same as what you would get when using a calculator and typed in 1/e. Since the result is between zero and phi the modulo operation % phi does nothing. What you actually need here is the multiplicative inverse modulo $\varphi(n)$, so you need to find a $d$ such that $e\cdot d\equiv 1\mod{\varphi(n)}$. (That is the meaning of $e^{(-1)}$ in $d=e^{(-1)}\mod{((p-1)\cdot (q-1))}$.) Jul 31, 2021 at 22:04
• Ah yes, I just thought that the Decimal would do some nice computation for me. Jul 31, 2021 at 22:29

You can use the extended Euclidean algorithm to calculate $$d$$. Quoting Wikipedia, given $$a$$ and $$b$$, the extended Euclidean algorithm gives you $$x$$ and $$y$$ such that

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

Since $$e$$ is prime, $$\gcd{(e, \varphi(n))}=1$$, so the algorithm gives you $$x$$ and $$y$$ with

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

which means

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

and thus you can use $$x$$ as $$d$$.

For your practical application, the truly marvelous Python standard library has a trinary pow function build in that can calculate the modular multiplicative inverse beginning with Python 3.8

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