Join Log in
Score:0
kmiyazaki avatar Crypto

RSA Digital Signatures Verification

cn flag
kmiyazaki

I am trying to learn about RSA digital signatures, and have a question about the verification process.

My understanding of the set-up is the following:

The signer chooses two secret primes $p$ and $q$, and a verification exponent $e$ satisfying $\gcd(e,(p-1)(q-1))=1$, then publishes $N=pq$ and $e$.

The signer computes the secret signing exponent $d$ such that $$de\equiv1\pmod{(p-1)(q-1)},$$

signs the document $D$ by computing $$S\equiv D^d\pmod N,$$ and sends $D$ and $S$ to the verifier.

Here is what I am having a trouble.

I read that the verifier computes $$S^e \pmod N$$ and compares the result to $D$. If the result is indeed equal to $D$, then the verifier is convinced that the signature is valid. My question is, why is the following supposed to be the case? $$S^e\equiv (D^d)^e\equiv D \pmod{N}$$

I see that if $D$ and $N$ are relatively primes, then Euler's formula can be used. But that means we can only sign a document $D$ that is relatively prime to the modulus $N$?

21
0 + 0
rsa
kelalaka avatar
in flag
kelalaka
This is textbook RSA ( unfortunately decryption is sometimes called signature but it is not). To be secure RSA needs proper padding. RSA function works for any message. Here the dupes ( wait ...)
2
Reply
kelalaka avatar
in flag
kelalaka
Does this answer your question? [Does RSA work for any message M?](https://crypto.stackexchange.com/questions/1004/does-rsa-work-for-any-message-m) and this is RSA-PSS [How does RSA signature verification work?](https://crypto.stackexchange.com/q/9896/18298)
3
Reply
fgrieu avatar
ng flag
fgrieu
$S\equiv D^d\pmod N$ does not uniquely define an integer $S$ from $D$, $d$ and $N$. What does is $S=D^d\bmod N$, adding that $0\le S<N$. In actual RSA signature, $D$ is not the signed document; it's a value in $[0,N)$ reversibly determined from the hash of the document and perhaps a random value (incidentally, that makes it virtually certain $D$ and $N$ are relatively prime). See [RSASSA-PKCS1-v1_5](https://pkcs1.grieu.fr/#page=31) and [RSASSA-PSS](https://pkcs1.grieu.fr/#page=27) for how it's really done.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

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.