CODEWITHSUNDEEP
cryptographyrsasha
FabioLovi
FabioLovi

Reputation: 41

How SHA-RSA works?

Sorry for my noob question, i'm new in this field (but i'm curious). I've found an xml file with two fields: DATA and SIGNATURE. DATA is an Ascii text, SIGNATURE is an SHA1-RSA1024 string composed by 256 hex characters (128bytes). I don't understand how can bi obtained that signature from the data field: the data is elaborated with the RSA and then with SHA or it is the contrary? I'm studying RSA and i think i should find something like this:

00 01 FF FF .. FF FF 00 DigestInfo MessageDigest

But it is not true: my signature data doesn't contain that string. Can you explain me the procedure used to obtain the signature? Do you have a link with an example (maybe in Python, due to its simplicity)?

Upvotes: 0

Views: 1038

Answers (1)

bartonjs
bartonjs

Reputation: 33266

The security.stackexchange.com answer has pretty good detail, but here's the short form (since they don't seem to quite answer your question.

The first step is EMSA-PKCS1-v1_5, where M is the (unhashed) message and emLen is the size (in bytes) of the RSA key (which is usually expressed in bits).

H = Hash(M). We know Hash is SHA-1 (by the question), so the output is 20 bytes. Let's assume it produced 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20.

Construct T:

// DigestInfo = SEQUENCE(AlgorithmIdentifier, OCTET STRING)
30 21
   // AlgorithmIdentifier = SEQUENCE(OBJECT IDENTIFIER, ANY)
   30 09
      // OBJECT IDENTIFIER(SHA1) => OBJECT IDENTIFIER(1.3.14.3.2.26)
      06 05 2B 0E 03 02 1A
      // NULL (SHA-1 has no parameters)
      05 00
   // OCTET STRING(H)
   04 14 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

Since everything in this structure has fixed values (SHA-1 OID) and/or length (H=20 bytes) T is just (30 21 30 09 06 05 2B 0E 03 02 1A 05 00 04 14 concat H) (for SHA-1).

Let's assume we have a 2048-bit key (256 bytes). Since tLen=35, emLen > tLen + 11, so we're good to proceed.

Now, build PS. It is emLen - tLen - 3 FF. For SHA-1 with RSA-2048 that means a sequence of 218 FFs.

EM = 00 01 PS 00 T

Gluing everything together now, we get (for SHA-1 and a 2048-bit key)

00 01 FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FF FF FF FF FF FF FF FF FF FF FF FF 00 30 21 30
09 06 05 2B 0E 03 02 1A 05 00 04 14 20 20 20 20
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

As you can see, the hash output is still visible, at the very end. The EMSA-PKCS1-v1_5 padded structure seems to be what you expected.

Then, EM gets applied through the RSA private key formula to produce the signature:

`signature` = MODPOW(`EM`, `d`, `n`)

Since the value of signature now depends on d (the private key) no fixed example can be given. But this last step is why a) it's cryptographically sound, and b) you can't find your MessageDigest value within the signature value anymore.

For RSA signatures the signature gets verified as

`candidate` = MODPOW(`signature`, `e`, `n`)
return ConstantTimeSequenceEquals(`candidate`, `EM`);

The new RSA signature algorithm (PSS (Probabilistic Signature Scheme)) works quite differently. And, it's worth noting, DSA and ECDSA work even more quite differently.

Upvotes: 1

Related Questions