1

To use RSA for signing, Alice takes a hash of the message, encrypts the hash using her own private key, and appends the result (this is the signature) to the message. Eve can of course still decrypt this using Alice's public key. However, Bob can decrypt the signature using Alice's public key and see if it matches. If it does, it must have been encrypted using Alice's private key, which only she has, so it must have come from Alice.

How is the hash derived, and how is it secure? Do 2 identical messages "hello bob 12" have the same signature? And if they are different, how so?

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
Breakhty
  • 367
  • 1
  • 4
  • 13

3 Answers3

3

You don't use a hash function to encrypt things. You use an encryption algorithm.

You don't use an encryption algorithm to sign things. You use a signature algorithm.

The text you quote uses to traditional explanation of signatures as "encryption with a private key", which is a very confusing way of stating things, and works only for a specific signature algorithm (RSA), and in fact is wrong and does not work at all for RSA. You'd better forget it altogether.

Instead, let's see how RSA signatures work. The main signature algorithm that is called RSA follows the PKCS#1 standard, and more precisely the "old-style v1.5" method that PKCS#1 calls "RSASSA-PKCS1-v1_5". That method looks like this:

  • The message to sign is m (a sequence of bits).

  • The RSA key pair uses modulus n whose length is k bytes. For instance, if the key is said to have length "2048 bits", then this means that 22047 < n < 22048, and k = 256 (2048 bits are encoded over 256 bytes).

  • To sign the message m, first hash it with a hash function, e.g. SHA-256. This yields a sequence of bytes with a fixed length, 32 bytes in the case of SHA-256. Hash functions are public (no secret parameter) and deterministic (for the same input you always get the same output).

  • The hash value h(m) is then padded: a sequence of exactly k bytes is built as follows:

        0x00 0x01 0xFF 0xFF ... 0xFF 0x00 id h(m)

    In plain words, you take one byte of value 0x00, then one byte of value 0x01, then some bytes of value 0xFF, then one byte of value 0x00, then a fixed header (id) that identifies the hash function, then the hash value. The number of 0xFF bytes is adjusted so that the total length (in bytes) is exactly k. This padding process is described in section 9.2 of PKCS#1.

  • The padded hash value is then converted into a big integer x by interpreting it with big-endian encoding convention. Since the padded value has length exactly k bytes (the same as n) and begins with a byte of value 0x00, it is guaranteed that x will be lower than n (numerically).

  • The signer uses the private key to compute a number y which is the e-th root of x modulo n, where e is the public exponent (a part of the public key). That is, y is such that:

        ye = x mod n

    The private key contains some values that make that computation feasible.

  • The signature s is an encoding of y into a sequence of exactly k bytes, there again using big-endian convention.

To verify the signature, one decodes s into y, uses n and e to recompute x, re-encodes x into bytes, and checks that the resulting string contains a correctly padded hash value, and that the hash value matches that of the purportedly signed message m.

All of the above is deterministic, so if the signer tries to sign the same message again, with the same key, then the exact same signature will be obtained. However, note that:

  • If a distinct private key is used, then the signature will be different. This is expected: a signature value is specific to a given signed message and to a given signer; otherwise, it would not prove anything.

  • Though the old-style PKCS#1 v1.5 signature scheme explained above is deterministic, not all signature schemes have that characteristic. Even PKCS#1 includes a "new-style" signature scheme (RSASSA-PSS), that still relies on the RSA modular exponentiation, but with a different padding that includes random bytes. With PSS, the same signer using the same key to sign the same message twice will get two distinct (but equally valid) signature values.

RSA encryption is a different beast, but it is also described in PKCS#1 (in different sections; search "RSAES"). At its core, the same mathematical operation (modular exponentiation) is used for both encryption and signatures, but the padding methods differs a lot, and the padding is crucial for security. RSA signatures really are not a kind of encryption. Also, while RSA signatures and RSA encryption appear to be able to use the same kind of public/private key pairs, there are good reasons not to actually use the same key for signatures and for encryption.

Community
  • 1
Tom Leek
  • 168,808
  • 28
  • 337
  • 475
  • Ok so the private key plays a particular role in signing for RSA that is not necessarily encryption? In the RSASSA-PSS, how does validation take into account the random bytes? Is it to do with knowing the real hash value of the message and then comparing it to the hash+padding value in the signature? – Breakhty May 16 '15 at 12:50
1

Here's a link to a related question.

The general answer is that before the message is signed with Alice's private key, it will be hashed with a hash function of Alice's choice. RSA is not tied to any specific hash function. Alice will include in the header of the message which combination of hash function + signing algorithm she used.

For example: in TLS 1.2, the string 

TLS_RSA_WITH_AES_128_CBC_SHA256 (shortened as AES128-SHA256)

in the header indicates that RSA was used as the singing algorithm, AES 128 was used as the encryption algorithm, and SHA256 was used as the hash function.

You can see a full list of [key exchange]_[signature alg]_[encryption alg]_[hash alg] cipher suite strings accepted by OpenSSL at this link.

As for

Do 2 identical messages "hello bob 12" have the same signature?

Yes, yes they will. For this reason secure network protocols typically include a one-time-use random number in messaged called a nonce to prevent replay attacks.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • A TLS/SSL ciphersuite with plain _RSA_ doesn't sign anything; it RSA-encrypts the premaster secret, and authentication is implicit in getting the shared keys and Finished correct. Suites using _DHE_RSA_ or _ECDHE_RSA_ do RSA-sign the ServerKeyExchange, but in protocol versions through 1.1 using a hash defined by the protocol with no choice by the server. PKCS#7/CMS/SMIME or PGP would be a better example where the signer can choose the hash, possibly constrained by capabilities of the recipients if known. – dave_thompson_085 Oct 23 '15 at 01:06
1

How is the hash derived, and how is it secure?

The hash is derived using a cryptogaphic hash function. Hash function usually have the following three properties:

  1. Preimage resistance: From a given hash you can't (easily) find out the corresponding input to the function
  2. 2nd Preimage resistance: From a given hash and a given input you can't (easily) construct another input having the same hash.
  3. Collision resistance: You can't (easily) find any two inputs resulting in the same hash.

The usual constructions for this are SHA-1(not recommended), SHA-256 and SHA-3.

Do 2 identical messages "hello bob 12" have the same signature?

I have to say you that depends on the circumstances.
If you use a reasonably new padding scheme for RSA they'll have different signatures because randomness is inserted before the "reverse encryption" operation. A verifier can they check if the random string is placed consistencly.
If you're using an older padding scheme for RSA there's no randomness and the this will result in the same signature.

The reason, why there are only PKI tags is because there's a dedicated cryptography stack exchange. (I think)

SEJPM
  • 9,500
  • 5
  • 35
  • 66