Score:0

RSA private key revealing by decrypting c=n-1

at flag

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?

kelalaka avatar
in flag
What is the origin of this question and what did you try?
Mohammadsadeq Borjiyan avatar
at flag
Hello. Side-channel attack, and specifically Square and always Multiply algorithm in decryption. I did not get anything.
kelalaka avatar
in flag
Like this one https://crypto.stackexchange.com/a/75419/18298 and **hint:** $n-1 \equiv -1 \bmod n$ this just make easier, nothing more.
Mohammadsadeq Borjiyan avatar
at flag
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?
kelalaka avatar
in flag
Well, you got it. start from coding on which you measure the time. Use preferable C++ and Chrono timing. _Does the power consumption change?_ Yes. if $d=1$ then squaring and multiplication with 1 is free? You need to investigate the cases..
fgrieu avatar
ng flag
"Square and always multiply" is not well-known: I had to [Google it](https://www.google.com/search?q="Square+and+always+Multiply") to get a [relevant link](https://orenlab.sise.bgu.ac.il/AttacksonImplementationsCourseBook/03_Temporal_SC_2). In short, it's square and multiply modified to perform multiplication and discard it's result when the exponent bit is 0.
kelalaka avatar
in flag
@fgrieu isn't it the second version on my answer. Now, I've named it, thanks.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.