CODEWITHSUNDEEP
pythonmathrsalargenumber
muke
muke

Reputation: 396

Large integer operation in Python

I'm trying to solve a cryptography CTF challenge which involves taking the building blocks of an RSA key-pair (two large primes) and the encrypted cipher number of a message. In order to decrypt this message, I need to carry out operations which I don't believe are supported by standard crypto libraries, as the public exponent used is unknown, but I do have the values dp and dq, meaning I have to carry out the following operations:

enter image description here

So essentially I'm raising very large integers to the power of very large integers, and the standard option of pow(x,y) causes Python to hang seemingly indefinitely. Without the use of crypto libraries then, how can I carry out these operations in Python?

Edit: Here is the specific code and values causing Python to hang

p = 7901324502264899236349230781143813838831920474669364339844939631481665770635584819958931021644265960578585153616742963330195946431321644921572803658406281
dp = 5540655028622021934429306287937775291955623308965208384582009857376053583575510784169616065113641391169613969813652523507421157045377898542386933198269451
c = 62078086677416686867183857957350338314446280912673392448065026850212685326551183962056495964579782325302082054393933682265772802750887293602432512967994805549965020916953644635965916607925335639027579187435180607475963322465417758959002385451863122106487834784688029167720175128082066670945625067803812970871

m1 = pow(c,dp)%p

Upvotes: 0

Views: 1422

Answers (1)

Francisco
Francisco

Reputation: 11476

pow takes an optional third argument z, that does a modulus operation, but is way faster than using the % operator:

>>> pow(c, dp, p)
49437413074993986257824490238275931180994249527518860068137626874351971280859988288289074

Upvotes: 3

Related Questions