0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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))}$.) $\endgroup$
    – Perseids
    Jul 31, 2021 at 22:04
  • $\begingroup$ Ah yes, I just thought that the Decimal would do some nice computation for me. $\endgroup$
    – Flair
    Jul 31, 2021 at 22:29

1 Answer 1

Reset to default
2
$\begingroup$

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
>>>
Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.