I am implementing a timing attack on RSA for school and I need to generate two sets of messages $Y$ and $Z$ for which holds:

$ (Y^d \mod N) \cdot Y < N $ and
$ (Z^d \mod N) \cdot Z > N $

where $d$ and $N$ are known. How can I efficiently find solutions for $Y$ and $Z$?

I have tried using a random function but it takes too long to complete or it doesn't complete at all.

  • 1
    $\begingroup$ I agree with @CodesInChaos . If we assume $d$ is random, then $Y=k$ has probability $1/k$ of working; likely there is a small $Y$ that would work (and starting at the smallest and working your way up seems like the obvious approach (unless, of course, $Y=0$ or $Y=1$ isn't disallowed for some reason). $\endgroup$ – poncho Sep 7 '12 at 19:57
  • 1
    $\begingroup$ Do you have a typo in the condition for $Z$? The $*Z>Z$ part is weird. $\endgroup$ – CodesInChaos Sep 7 '12 at 19:57
  • 2
    $\begingroup$ For Z, try any Z > N/2; that should work. $\endgroup$ – poncho Sep 7 '12 at 20:04
  • 2
    $\begingroup$ You state $d$ is known. By convention, $d$ stands for the private exponent (which is one of the targets if you're trying to recover the private key; if you get that, you've won). Do you really mean the private exponent $d$? Or, do you really mean the public exponent (and are using nonstandard terminology to describe it)? $\endgroup$ – poncho Sep 7 '12 at 20:19
  • 1
    $\begingroup$ Oh, if you've recovered one of the CRT exponents (say, $d \bmod p$), then the rest is easy; see the answer in crypto.stackexchange.com/questions/1890/… $\endgroup$ – poncho Sep 7 '12 at 20:26

Finding a $Z$ is easy. This condition is fulfilled for all $Z>n/2$, and most of the smaller values of $Z$ too. There are only a few values fulfilling the condition for $Y$, and since this is almost the negation of the condition for $Y$, most numbers will fulfill it.

When looking at the condition for $Y$, you can model $Y^d \mod N$ as a random number between 0 and $N$. This leads to a success chance of approximately $ 1/Y $.

Thus a good strategy for finding a $Y$ is starting with $ Y = 2 $ and incrementing by one on each attempt, i.e. trying 2, 3, 4,... This should find a number fulfilling $ (Y^d \mod N) \cdot Y < N $ quite quickly.

Total chance of finding an $ Y \le n$ is:

$1-\Pi^n_{i=2}(1-1/i) = $

$1 - \frac{(n-1)!}{n!} = $

$ 1- 1/n $

Which quickly converges to 1

  • $\begingroup$ sorry there was a typo in the Z condition. For the Y condition - what would be a good increase on each attempt (N is 512bit at least) $\endgroup$ – blejzz Sep 7 '12 at 20:03
  • $\begingroup$ @blejzz The best increase would be 1. You simply want to try the smallest $Y$s first, since those have the highest success chance. $\endgroup$ – CodesInChaos Sep 7 '12 at 20:10

@CodesInChaos gives an excellent answer.

I'll add one more point: if you are not able to find a $Y$ satisfying your condition using CodesInChaos's approach, here is one more approach you can try as a fallback.

Pick a small value $i$, set $Y=i^e \pmod{N}$, and try $Y$. Note that $Y^d \bmod N$ will be equal to $i$, and $Y$ can be modelled as a random number between 0 and $N$. This means that you have a success chance of approximately $1/i$, with this strategy.

So, you can try $i=2$, $i=3$, $i=3$, \dots, in succession until you find the first success. By the same argument CodesInChaos gives, there is likely to be a small $i$ for which this succeeds.

Again, this doesn't really add anything. There is no particular reason to prefer this strategy over CodesInChaos's, if both $e$ and $d$ are known. However, this is available as a fallback if CodesInChaos's method fails. Also, this method is available if $d$ is not known but $e$ is known.


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.