0
$\begingroup$

Key Generation Method: Take $s \le n/2$ bits.

  1. Generate two distinct random $n / 2$-bit prime numbers $p$ and $q$ with $\operatorname{gcd}(p-1, q-1)=2$ and calculate $N= p*q$;
  2. Generate two $s$-bits random numbers $d_p$ and $d_q$,
    such that $\gcd(d_p, p-1)=1$, $\gcd(d_q, q-1)=1$
    and $d_p= d_q \bmod p-1$.
  3. Calculate one $d$ such that $d= d_p \bmod p-1$ and $d= d_q \bmod q-1$.
  4. Calculate $e=d^{-1} \bmod \varphi(N)$,
    Public key= $(N, e)$,
    Private key= $(p, q, d_p, d_q)$.

On the 3rd step of key generation, do I need to select between $d= d_p \bmod p-1$ and $d= d_q \bmod q-1$ or do I make the $d_p$ and $d_q$ to make same $d$ result?

It is okay to use small prime because I use $p = 41$ and $q = 59$ for study purposes.

Please help me to find the $d$.

$\endgroup$
  • $\begingroup$ here is the paper I study from sir ccis2k.org/iajit/PDF/vol.12,no.6/5492.pdf $\endgroup$ – meh96 May 29 '17 at 8:09
  • $\begingroup$ See the explanation for Steps 3 and 4 in the key generation for rebalanced RSA in the Boneh / Shacham survey article crypto.stanford.edu/~dabo/pubs/abstracts/fastrsa.html. You compute one $d$ based on the fact that $(p-1)/2$ and $(q-1)/2$ are relative prime. $\endgroup$ – gammatester May 29 '17 at 9:21
  • $\begingroup$ @gammatester On step 2 there is r1 = r2 mod 2, so r1 is beetwen 1 and 0 only ? $\endgroup$ – meh96 May 29 '17 at 10:05
  • $\begingroup$ Whatever it is, I suggest to change the process that led to selection as a reference of the paper on which the question is based. That paper restates some earlier work with typos and variants, then proceeds to its main point: combining a technique of its reference [17] with 3-primes RSA. Security claims are poorly justified, sometime wrong (including that RSA with 3 primes is safer than with 2 primes at constant modulus size, about 1024-bit). The two graphs (fig. 8 and 9) use lines to join unrelated points. The public RSA exponent proposed at end of section 5 is even... $\endgroup$ – fgrieu May 29 '17 at 14:21
2
$\begingroup$

The paper on which the question is based describes Rebalanced RSA-CRT with $d_p=d_q\bmod(p-1)$ as stated in the question's step 2, but is wrong in doing so. Notice that when $s<n/2$, that condition implies $d_p=d_q$, and that goes squarely against generate two $s$-bits random numbers $d_p$ and $d_q$ also in step 2 (further step 3 can become $d=d_p$, ans $d$ is $s$-bit only).

That's confirmed by looking at the paper's source: M. J. Wiener's Cryptanalysis of RSA with short secret exponents (IEEE ToIT, 1990), which section 8 open problems states [emphasis added]:

A useful technique for reducing the secret key exponentiation time is to take advantage of the knowledge of $p$ and $q$ (rather than just the product $pq$). Using this technique, two half-sized exponentiations are performed. The first exponentiation gives the result modulo $p$ using exponent $d_p=d\bmod(p-1)$, and the second gives the result modulo $q$ using exponent $d_q=d\bmod(q-1)$. These two results can be combined easily using the Chinese Remainder Theorem to obtain the final result modulo $pq$. One could reduce the secret key exponentiation time further by choosing $d$ so that $d_p$ and $d_q$ are short. An interesting open problem is whether there is an attack on RSA when $d_p$ and $d_q$ are short, but not equal.

Wiener clearly knew that short $d_p=d_q$ would be unsafe (his paper conclusively proves it when $s\le 0.125n$).

I thus suggest that the key generation procedure for Rebalanced RSA-CRT should be:

  1. Generate two random $n/2$-bit primes $p$ and $q$ (that are nearly certainly distinct for sensible choice of $n$), optionally such that $\gcd(p-1,q-1)=2$ ;
    calculate $N=p\cdot q$ (which will be $n$-bit or one bit less).
  2. Generate two $s$-bits random integers $d_p$ and $d_q$ (that are nearly certainly distinct for sensible choice of $s$), such that $\gcd(d_p, p-1)=1$ and $\gcd(d_q, q-1)=1$.
  3. Calculate (using the CRT) one $e$ (possibly: the lowest) such that $e\equiv d_p^{-1}\pmod{p-1}$, $e\equiv d_q^{-1}\pmod{q-1}$, and $0<e<(p-1)(q-1)$.
    [or we could explicitly compute $d$ then deduce $e$ as in the question]
    Public key = $(N,e)$,
    Private key = $(p,q,d_p,d_q)$.

but I caution against using it:

  • We know that it would be insecure to use $s<0.146n$, thanks to D. Boneh and G. Durfee's Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$ (first version in proceedings of Eurocrypt 1999)
  • These authors caution the bound could further be improved to $d<N^{0.5}$, thus $s<0.25n$; so we should probably stick to prudently larger $s$, and a conservative Rebalanced RSA-CRT is thus bound to a speed improvement smaller than a factor of two.
  • Further, when using RSA-CRT (rebalanced or not) to compute $x\to x^d\bmod N=y$ , it is customary and useful to check that $y^e\bmod N=x$ in order to guard against fault injection; in which case having a large $e$ (as in Rebalanced RSA-CRT) much more than offsets any speed gain achievable by lowering $d_p$ and $d_q$.

Example with $n=40$, $s=13$ (which are too small to be sensible choices)

  1. $p=768941$, $q=825443$, $N=634716965863$
  2. $d_p=4231$, $d_q=6779$
  3. $d_p^{-1}\bmod(p-1)=634271$, $d_q^{-1}\bmod(q-1)=670801$
    $e=303057573891$.
$\endgroup$
1
$\begingroup$

Since in your construction, $\gcd(p-1,q-1) = 2$, one has $\lambda(N) = (p-1)(q-1)/2$. Private decryption key $d$ is defined modulo $\lambda(N)$. The condition $\gcd(p-1,q-1)=2$ implies that at least $(p-1)/2$ or $(q-1)/2$ is odd. In what follows, we assume without loss of generality that $(q-1)/2$ is odd.

From $d_p$ and $d_q$ do the following:

  1. Define $q' := (q-1)/2$ and $d_{q'} := d_q \bmod q'$ [Remember that $q'$ is supposed to be odd; reverse $p$ and $q$ if not.]
  2. Define $I_{q'} := 1/q' \bmod (p-1)$
  3. Compute $d = d_{q'} + q'\left[I_{q'}(d_p - d_{q'}) \bmod (p-1)\right]$

The correctness follows by observing that the so-computed $d$ satisfies $d \equiv d_{q'} \pmod {q'}$ and $d \equiv d_p \pmod {(p-1)}$ since $q' \cdot I_{q'} \equiv 1 \pmod {(p-1)}$.


Example. With $p=41$ and $q = 59$, we have $q' = 29$ and $I_{q'} = 29^{-1} \bmod 40 = 29$. Hence, $d = d_{q'} + 29\left[29(d_p - d_{q'}) \bmod 40\right]$ where $d_{q'} = d_q \bmod 29$.

$\endgroup$
  • $\begingroup$ +1 for using $\gcd(p-1,q-1)=2$ in order to make the CRT straightforward. Notice that further simplifications are possible (including just $d=d_p=d_q$ when $s\ne n/2$, which is the aim) if we keep $d_p=d_q\bmod(p-1)$ as stated in the question (erroneously, according to my understanding). $\endgroup$ – fgrieu May 30 '17 at 19:12
-1
$\begingroup$

For RSA key generation, one usually first selects $e$ and generates primes $p$ and $q$ such that $\gcd(e,p-1)=\gcd(e,q-1) = 1$. The advantage of doing so is that one can use a small value for $e$. Common values for $e$ are $e = 3$, $e = 17$, or $e = 2^{16}+1$.

If you insist to first generate the decryption key then, upon generation of primes $p$ and $q$, you need to choose a random $n$-bit integer $d$ such that $\gcd(d, p-1) = \gcd(d,q-1) = 1$. Next, define $d_p := d \bmod (p-1)$ and $d_q := d \bmod (q-1)$.

$\endgroup$
  • $\begingroup$ I think its diferent type of rsa sir because I need to make invers modulo to get e, and i cant achive it because they are not coprime from that way $\endgroup$ – meh96 May 29 '17 at 8:07
  • $\begingroup$ ccis2k.org/iajit/PDF/vol.12,no.6/5492.pdf this is the paper of rebalanced rsa, maybe you want to take a look $\endgroup$ – meh96 May 29 '17 at 8:07

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.