Search code examples
encryptionkeyintprivate

Finding private Key x Big integers

Well is it possible to find private key x for this equation y=g^x mod p of course big integers if you have p ,g, y, q?. What method can be used if there is method to find it out? ..........Note:These are big Integers

Solution

  • This is called the discrete logarithm problem. You seem to be interested in the prime field special case of this problem.

    For properly chosen fields with sufficiently large p this is infeasible. I expect this to be reasonably cheap (100$ or so) for 512 bit p and extremely expensive at 1024 bit p. Going beyond that it quicky becomes infeasible even for state level adversaries.

    For some fields it's much cheaper. For example solving DL in binary fields (not prime fields as in your example) produced quite a few recent papers. For example Discrete logarithm in GF(2^809) with FFS and On the Function Field Sieve and the Impact of Higher Splitting Probabilities: Application to Discrete Logarithms in F_2^1971.