-1
$\begingroup$

I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than with brute force.

I have been checking some stuff like index calculus and baby steps, but I don’t see any apparent difference (there is but not for standard computers).

$\endgroup$
0
$\begingroup$

I have been given a task to explain if - given a public key and a portion of a private key (over 300bits) with a remain unknown of 80 bits - the private key can be broken with an algorithm faster than with brute force.

Check out the Baby Step/Giant Step algorithm - and figure out how it could be adjusted to handle your situation (with the known key bits)

$\endgroup$
4
  • $\begingroup$ Hello, thanks for your response. I have checked it, and still don’t see how it would help. Basically baby steps is based on the assumption that x = im + j but for a bounded x there is still nearly infinte possibilites for i and j knowing that m is the square root of p. If you have any thought or extra clue it would be highly appreciated $\endgroup$ – honte Dec 18 '20 at 21:49
  • $\begingroup$ @honte: with the known key bits, we already know $x = ay + b$ (where $b$ are the known key bits, and $a$ depends on where the unknown key bits are, and $0 \le y < 2^{80}$. How can you modify baby step/giant step to search through that? $\endgroup$ – poncho Dec 18 '20 at 22:28
  • $\begingroup$ Okay I will check, thanks for that. Just for the record, the remaining bits are located at the end so, thet are the 80 LSB bits $\endgroup$ – honte Dec 18 '20 at 22:33
  • $\begingroup$ @honte: "end == lsbits" assumes that the encoding is bigendian, which is not universal. On the other hand, having the unknown bits being the lsbits makes $a=1$, which makes things conceptually easier (even if it doesn't make any difference in the complexity of the attack) $\endgroup$ – poncho Dec 19 '20 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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