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

Flair

11/30/22, 8:29 PM

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.

132

1 + 2

rsa

attack

Perseids

11/30/22, 10:04 PM

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))}$.)

Flair

11/30/22, 10:29 PM

Ah yes, I just thought that the `Decimal` would do some nice computation for me.

Score:2

Crypto

Perseids

11/30/22, 9:55 PM

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
>>>

0 + 1

Flair

11/30/22, 10:28 PM

I did some investigating after posting. That algorithm is tangent to the algorithm that will find $d$/$x$ for me: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse Thank you tho!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

TH: จะสร้างคีย์ส่วนตัวจำนวนเต็มขนาดใหญ่สำหรับสร้างความท้าทาย CTF ได้อย่างไร

RO: Cum se generează o cheie privată întregă mare pentru a crea provocări CTF?

RU: Как сгенерировать большой целочисленный закрытый ключ для создания задач CTF?

VI: Làm cách nào để tạo khóa riêng số nguyên lớn để tạo thử thách CTF?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.