1
$\begingroup$

With an RSA key pair, from my understanding, Alice who holds the private key is able to encrypt a message into a signature. She would then send the signature together with her original message to Bob. Bob would then be able to use Alice's public key to decrypt the signature which would then return the message. The decrypted message would then be compared with the original message. If they are the same, this proves to Bob that the message was indeed from Alice.

On the other hand, with an ECDSA key pair, is the verification process the same with in RSA key pairs? That is, by comparing the decrypted message with the original message to see if they are the same?

What is confusing me is that, based on what I've understood how ECDSA is used in blockchain contracts, for example, instead of comparing the decrypted message from the public key and the original message, the ECDSA appears to be comparing the public key instead. It is able to recover the public key from the signature and to verify. Bob would compare that the recovered public key from the signature is the same as Alice's public key.

Is the verification process in ECDSA the same as RSA? Or is the verification process different from RSA and it's like how it's used in smart contract on blockchains?

$\endgroup$
4
$\begingroup$

TL;DR: the signature verification process in ECDSA is very different from the one in RSA. The question's description of these signature schemes is incorrect for ECDSA, approximate for RSA.


Alice who holds the private key is able to encrypt a message into a signature.

That's incorrect terminology. Alice who holds the private key is able to sign a message, or transform a message. She does not encrypt, because encryption aims to make the message unintelligible to adversaries, but in RSA the transformation $m\mapsto s=m^d\bmod n$ Alice did using the private key $(n,d)$ can be undone using $s\mapsto m=s^e\bmod n$ by anyone with the public key $(n,e)$, that is anyone from a standard cryptographic standpoint. Thus the transformation done for signature does not qualify as encryption.

Bob would then be able to use Alice's public key to decrypt the signature which would then return the message. The decrypted message would then be compared with the original message. If they are the same, this proves to Bob that the message was indeed from Alice.

Again that's incorrect terminology. Instead of decrypt there should be transform back, and the overall intend is to verify the message against the signature and Alice's public key.

Terminology aside, the above two quotes do not match how RSA signature is practiced. With the method outlined the message size is limited, and the overall procedure is unsafe. Examples among many attacks:

  • The messages $0$, $1$ and $n-1$ have trivial signatures (the message itself), which allows messages that Alice never signed to be accepted by Bob when they really came from an adversary.
  • It's easy to take any $s$ and the public key, and forge a (typically meaningless) message $m$ which signature is $s$, to the same effect.
  • If an adversary crafts messages $m_1$, $m_2$, $m_3$, $m_4$ with $m_1\cdot m_2=m_3\cdot m_4$, the later meaningful, and the three former meaningful enough to convince Alice to produce the signatures $s_1$, $s_2$, $s_3$ of $m_1$, $m_2$, $m_3$, then the adversary can compute the signature $s_4$ of meaningful $m_4$ as $s_4=s_1\cdot s_2\cdot{s_3}^{-1}\bmod n$. That's sometime possible.

For this reason, RSA signature is not practiced as in the question. It's typically used RSASSA-PSS or RSASSA-PKCS1-v1_5. And then signature generation and signature verification no longer works like en/decryption do (be it in textbook RSA encryption, or RSA encryption as practiced, like RSAES-OAEP, RSA-KEM, or hybrid encryption).

What's correct is that in RSA signature verification (with appendix) as practiced, it's computed a function of the signature and public key, then compared the result to the message (or some hash thereof; in the case of RSASSA-PSS, a multi-level hash with the optional salt added).

On the other hand, with an ECDSA key pair, is the verification process the same with in RSA key pairs? That is, by comparing the decrypted message with the original message to see if they are the same?

No, in ECDSA signature verification, it's not computed some function of the signature and public key, then compared the result to the message (or some hash thereof). It works another way: the hash of the message is an input to a calculation also involving the signature and the public key, rather than compared to in the end.

…ECDSA appears to be comparing the public key…

Neither the normal nor alternate ECDSA signature verification methods fit this.

(ECDSA) is able to recover the public key from the signature…

Sort of: with ECDSA, it possible to recover a working public key from a signature and it's associated message or hash thereof. That's public key recovery. But that operation is not part of how signature verification is normally performed. And it has limitations:

Potentially, several candidate public keys can be recovered from a signature. At a small cost, the signer can generate the ECDSA signature in such a way that only one of the candidate public keys is viable, and such that the verifier has a very small additional cost of determining which is the correct public key.

I can't tell for sure if ECDSA public key recovery, followed by comparing the recovered public key to the true public key, would be a robust equivalent of normal verification, and for which curves. That's a question of theoretical interest only, since we have standard signature verification.

Note: for RSA signature schemes, public key recovery is not a typical feature. It's possible with RSASSA-PKCS1-v1_5 or other deterministic signatures, a few message/signature pairs, and common choices of $e$; but not possible with some other RSASSA-PSS or other randomized signatures.

$\endgroup$
0
1
$\begingroup$

Alice... encrypt a message into a signature.

Strictly speaking, signing is different to encryption! E.g. for RSA, you use public key to encrypt a message, but to sign you use private key.

What's more, verification of ECC is totally different to RSA, since they have different mathematic characteristics. One example is that for RSA you must use a good padding scheme to avoid various types of attacks. But ECDSA doesn't need it.

$\endgroup$
0

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.