5 ms·
Low-exponent attack on RSA: an example
- jwilk 4y ago> we can still recover mᵉ = m⁶⁵⁵³⁷, but finding m would be much harder, if possible at all On my (low-end) machine, I can compute 65537th power of a 4096-bit message in ~4 seconds. So just throwing binary search at the problem would give me the answer in 5 hours or so. There are more sophisticated root-finding algorithms that would be likely much faster.
- doomrobo 4y agoNot so simple. You forgot about the fact that it wraps around the modulus. Say c is the 65537th power of m. You try a guess m' and find that its 65537th power is c + 10 (mod N). Will you choose your next guess m'' to be greater than m' or less than m'? It could be either.
- jwilk 4y agoWhat's N? There was no N or modulo in the sentence I quoted.
- doomrobo 4y agoOh, my bad I misunderstood. Yes, you could just construct a system of 65537 equations in 65537 variables. You can't do a binary search though. Remember, all you have access to is c (mod p_i) for i = 1, ..., 65537. To do a binary search, you'd need the integer c (not mod anything).
- jwilk 4y agoBut the gist of this attack is that you can recover integer c with Chinese Remainder Theorem. Then you can use binary search (or another root-finding algorithm) to get m.