2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 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
    Commented Sep 7, 2012 at 19:57
  • 1
    $\begingroup$ Do you have a typo in the condition for $Z$? The $*Z>Z$ part is weird. $\endgroup$
    – CodesInChaos
    Commented Sep 7, 2012 at 19:57
  • 2
    $\begingroup$ For Z, try any Z > N/2; that should work. $\endgroup$
    – poncho
    Commented Sep 7, 2012 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
    Commented Sep 7, 2012 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
    Commented Sep 7, 2012 at 20:26

2 Answers 2

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 7, 2012 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
    Commented Sep 7, 2012 at 20:10
2
$\begingroup$

@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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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