Why does ECDSA produce different signatures for the same data, whereas RSA doesn't?

Question

Consider the following code using RSA...

Example:

byte[] raw = Encoding.Default.GetBytes("Hello, World!");
RSA key = RSA.Create();

for (int index = 0; index < 5; index++)
{
    byte[] signed = key.SignData(raw, HashAlgorithmType.SHA256, RSASignaturePadding.Pkcs1);
    string hashed = signed.ToSha256String();
    Console.WriteLine(hashed);
}

Output:

043a718774c572bd8a25adbeb1bfcd5c0256ae11cecf9f9c3f925d0e52beaf89 043a718774c572bd8a25adbeb1bfcd5c0256ae11cecf9f9c3f925d0e52beaf89 043a718774c572bd8a25adbeb1bfcd5c0256ae11cecf9f9c3f925d0e52beaf89 043a718774c572bd8a25adbeb1bfcd5c0256ae11cecf9f9c3f925d0e52beaf89 043a718774c572bd8a25adbeb1bfcd5c0256ae11cecf9f9c3f925d0e52beaf89

Now consider the same code, except using ECDSA...

Example:

byte[] raw = Encoding.Default.GetBytes("Hello, World!");
ECDsa key = ECDsa.Create();

for (int index = 0; index < 5; index++)
{
    byte[] signed = key.SignData(raw, HashAlgorithmType.SHA256);
    string hashed = signed.ToSha256String();
    Console.WriteLine(hashed);
}

Output:

043a718774c572bd8a25adbeb1bfcd5c0256ae11cecf9f9c3f925d0e52beaf89 a31fe9656fc8d3a459e623dc8204e6d0268f8df56d734dac3ca3262edb5db883 a871c47a7f48a12b38a994e48a9659fab5d6376f3dbce37559bcb617efe8662d d7ef0a04f3c8055644677299a9414a75adcb15916eb48417416c9317ace2ff4f 779f5dd63960abda52a7da70464b92eedd47f84a8dffda2d672e6a99de1bab95

RSA's signature output I expected; ECDSA's, I didnt. Why does ECDSA produce different signatures for the same data?

Answer 1

Elliptic Curve Digital Signature Algorithm (ECDSA), that is an adaptation of the classical DSA algorithm, relies on a cryptographically secure random number generator. For example: ECDSA signing algorithm calculates a message's hash, then generates a random integer k and calculates the signature (a pair of integers {R, S} ). R is calculated from k, and S is calculated using the message hash + the private key + the random number k. So, the signature is non-deterministic due to a randomness.

You can experiment with an Elliptic Curve here.

Answer 2

The signature of ECDSA consists of a combination of R and S, where R is a value that is dependent of random parameter k which is in turn input into the ECDSA algorithm. S in turn depends on that value. If R would be a static value then it would allow an attacker to calculate the private key (!).

The fact that signature generation using PKCS#1 v1.5 padding is deterministic makes it the odd one out. Actually, RSA with PSS padding is randomized using an explicit salt, so the deterministic behavior is not tied to RSA in any way; you could even say that it is an unwanted property as it does expose information about the message / data that has been signed, potentially to other parties than the verifier.

It is however possible to calculate k using a deterministic scheme based on the message itself and the private key if you must. This may have some advantages in particular protocols; for instance it means that no random number generator needs to be present. Generally it is recommended to the non-deterministic / randomized version of ECDSA.

In the end, the proof is in the pudding: if verification with the public key succeeds then your signature generation procedure was according to specification. For the scheme to be secure the public key must of course be validated and trusted, among other requirements.