0
$\begingroup$

In RSA, signing the hash of a message is doing the operation $h^{d} \bmod N$ where $d$ is the private key.

Given that the size of $d$ is usually 2048 bits and $h$ is a quite big number, the exponentiation will take too much time.

For example in python raising a number of 9 digits to the power of a number of 8 digits took 600s on my laptop. And the execution time multiplies by about 40 everytime I add a digit to the exponent.

And I don't think we can make use of Euler's theorem here because $Φ(N)=(p-1)\times(q-1)$ may still leave us with a large exponent.

What do I miss here ? How do we sign the hash value ?

$\endgroup$
2
  • 2
    $\begingroup$ See en.wikipedia.org/wiki/…. Python is trying to compute the exponentiation without the modulus which is slow because the numbers get extremely big. Here you only need the result mod N so there are much faster methods. $\endgroup$
    – eesiraed
    Aug 1 at 22:15
  • 4
    $\begingroup$ pow has 3 parameters in Python, the third one is optional... $\endgroup$
    – Maarten Bodewes
    Aug 1 at 22:33

1 Answer 1

2
$\begingroup$

In RSA, signing the hash of a message is doing the operation $h^{d} \bmod N$ where $d$ is the private key. Given that the size of $d$ is usually 2048 bits and $h$ is a quite big number, the exponentiation will take too much time.

Three misconceptions here:

  1. We can compute $s:=h^d\bmod N$ with no intermediate result exceeding $N^2$, and in reasonable time, growing at worse as as $\mathcal O(\log(b)\log(N)^2)$. In Python, s = pow(h,d,N) will do. The basic techniques are "square an multiply", and modular reduction modulo $N$ after each multiplication or squaring. The full algorithm can go (for $d>0$):

    • $s:=h$
    • for each bit $b$ in the binary expression of $d$, from 2nd most significant bit to the least significant bit
      • $s:=s^2\bmod N$
      • if $b\ne0$ then $s:=s\,h\bmod N$

    Note: implementations often use Montgomery arithmetic, which eases modular reduction. Independently, it's possible to perform modular reduction while multiplying, reducing the size of intermediate results to the size of $N$ and one or two computer words.

  2. But, that's not how most actual implementations perform this computation, for performance reasons. It's used the Chinese Remainder Theorem to speed up this by a factor like 3.5. The private key is expressed in a form with $p$, $q$, $n=p\,q$, $d_p=e^{-1}\bmod(p-1)$, $d_q=e^{-1}\bmod(q-1)$, $q_{\text{inv}}=q^{-1}\bmod p$, and the computation goes

    • $s_p:=h^{d_p}\bmod p$ (by the methods in 1)
    • $s_q:=h^{d_q}\bmod q$ (same)
    • $s:=((s_p-s_q)\,q_{\text{inv}}\bmod p)\,q+s_q$

    Note: implementations often have extra steps to thwart side channel attacks.

  3. And then, $h$ is usually not just a standard hash of the message $M$ to sign. In particular, using $h=\operatorname{SHA-256}(M)$ allows an existential forgery attack, see this. This can be avoided:

    • In RSASSA-PKCS1-v1_5, by hashing then appending fixed constants (that must be checked on signature verification) to reach nearly the full width of $N$. That's heuristically secure, but we don't have a proof of that.
    • In RSASSA-PSS, by using a randomized padding to nearly the full width of $N$. That allows a security reduction to the RSA problem, and is the best practice.
    • In Full Domain Hash, by using a wide hash. This is simpler than PSS, and is proven satisfactorily secure; but that proof came too late to become standard practice.
$\endgroup$
1
  • $\begingroup$ Actually, it's possibly to do 1. without exceeding $c \cdot N$ ($c$ is a constant) if we don't use Montgomery multiplication: like this $\endgroup$
    – DannyNiu
    Aug 2 at 5:26

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.