How to reverse find "b" in pow(a, b, c)?

199 Views Asked by At
from Crypto.Util.number import *
from Crypto.Util.Padding import *

# TEXT is unkown

a = 2
b = bytes_to_long(pad(TEXT, 256))
c = getStrongPrime(1024) #178421928611071019360267030334948865864898765051649286940999740284901927205871904589008975999166343705176087678836390158248443701521112359395642244010241537603886223197773601996752130369527788156850561634811382810306708743274890833005691607859804295513120809249269263095276488896526807638635252842937565466271
y = pow(a, b, c) #21343660735918737508327032642093044458513430667350324146942601945958232402677794381334538380151928312459028941815432844601005666496537855378093591308495810737072737197378249689765750242912228630158636001591313536255003252774830039438050786246884290993531824792273255248565666477421036484450980164795516106937

How do you find TEXT? It looks like some people have figured this out, but I can't seem to solve this.

I tried brute-forcing, but it takes so long and I can't figure out TEXT.

1

There are 1 best solutions below

0
cryptograthor On

To expand on President's answer, it's not only a hard problem in general, but the hard problem that underlies a large portion of modern cryptography.

The discrete log problem can be expressed, given known values g,p,g**x, find x. The discrete log problem has been around for some time, and was proposed by Whitfield Diffie and Martin Hellman in 1976 as the basis for key-exchange.

Because the DH problem becomes tractable for an adversary with access to a quantum computer capable of running Schnorr's algorithm, there have been efforts for the last several years to formalize Post Quantum primitives not relying on the hardness of discrete logs.

https://en.wikipedia.org/wiki/Discrete_logarithm