I am trying to understand fault attack on RSA-CRT, and I found some example, which I don't know how to solve it.

I know public modulus $N$, public exponent $e$, a value of faulty signature (where one of the two partial signatures was incorrect) and the value of correct signature. The message $m$ is signed by RSASSA-PKCS1-v1_5 (signature transformation is RSASP1).

I have already read the documentation of RSASSA and RSASP1, and I have also read some articles about how to attack this problem. However, I don't understand how to get a message which I need for calculating $p$, because I should get $p = \operatorname{gcd}(\text{faultySignature}^{exponent} - m, N)$

Could someone help me?

  • $\begingroup$ e.g. this article cryptologie.net/article/371/fault-attacks-on-rsas-signatures , no exponent is $e$ it is public. d I don't know ($d = e^{-1} mod \quad phi(n)$) because I am not able calculate $phi(n)$ $\endgroup$
    – Max
    Nov 5 '18 at 10:50
  • $\begingroup$ In this case m is the hash of the message (computed according to RASP1, i.e., don't forget the padding) $\endgroup$
    – mephisto
    Nov 5 '18 at 12:02

In order to have a successful fault attack on RSA-CRT, you need to work with known values of $e, N$ and of the message $m$, but you should be knowing them already, since you cannot verify the signature without knowing these values.

So, at first you should be knowing the public key of the signer: $(e,N)$. Then the signer signs a message $m$, which you should know in order to verify it. But if the signer instead issues a faulty signature, you can try and recover its private key as you said using the following method.

You can first recover the value $p$ as you mentioned using $$p = \operatorname{gcd}(\text{faultySignature}^{e} - m, N)$$ once this is done, you can get the second prime $q$ by dividing $N$ by $p$: $$q=\frac{N}{p}$$ and you can finally compute the value $d$ by computing $\phi(N)=(p-1)(q-1)$ (assuming we are working with a 2 prime factors RSA modulus) and by finally computing $$d=e^{-1}\mod{\phi(N)}$$

Now, when using RSASSA-PKCS1-v1_5, what you are signing is not directly the message, to avoid the malleability issues and such, but instead the padded hash thereof. You can see the exact process of deriving the signed hash from the message in RFC3447 section 8.2.1 and following. But basically, what you need to do is to:

  1. Convert the message M into its encoded form of length k octets EM = EMSA-PKCS1-V1_5-ENCODE (M, k).

  2. Convert the encoded message EM to an integer which can be used with RSA: m = OS2IP (EM)

  3. Use this integer value m as being your value $m$ in your computations.


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.