0
$\begingroup$

In RSA, if we use Square and always Multiply algorithm in decryption, how does decrypting the ciphertext $c=n-1$, while our public key is $(n,e)$, cause the private key $d$ to reveal due to side-channel attack?

$\endgroup$
7
  • $\begingroup$ What is the origin of this question and what did you try? $\endgroup$
    – kelalaka
    Commented Jan 28, 2022 at 22:17
  • $\begingroup$ Hello. Side-channel attack, and specifically Square and always Multiply algorithm in decryption. I did not get anything. $\endgroup$ Commented Jan 28, 2022 at 22:54
  • 1
    $\begingroup$ Like this one crypto.stackexchange.com/a/75419/18298 and hint: $n-1 \equiv -1 \bmod n$ this just make easier, nothing more. $\endgroup$
    – kelalaka
    Commented Jan 28, 2022 at 22:55
  • $\begingroup$ For decrypting $c=n-1$ by square and always multiply algorithm, according to bits of $d$, we have to handle $1$ or $-1$ in every step; if current bit of $d$ is 1, our output in that step is $-1$ and if current bit of $d$ is $0$ we will have $1$. But I don't understand the relation of this to side-channel attack. Does the power consumption change? $\endgroup$ Commented Jan 29, 2022 at 6:26
  • 1
    $\begingroup$ "Square and always multiply" is not well-known: I had to Google it to get a relevant link. In short, it's square and multiply modified to perform multiplication and discard it's result when the exponent bit is 0. $\endgroup$
    – fgrieu
    Commented Jan 29, 2022 at 8:30

0

Your Answer

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

Browse other questions tagged or ask your own question.