Understanding RSA digital signatures

This article explains how RSA digital signatures work by describing the principles and intuitions behind them, and breaking down the signature creation and validation steps. The reader can try the commands in a ludic way using OpenSSL.

Principles and intuitions

RSA digital signatures use mathematical techniques to guarantee data (messages or documents) integrity. The key principles are described below.

Signature creation key principles

Signature validation key principles

This article does not intent to describe in deep the cryptography operations, algorithms, schemes used but gives some intuitions behind them.

RSA key pair generation

• Randomly choose 2 distinct prime numbers p and q
• Compute n = pq
• Compute λ(n) where λ is the Carmichael’s totient
• Choose an integer e such that 1 < e < λ(n) and gcd(e, λ(n)) = 1
• Determine d as ed ≡ 1 (mod λ(n))
• The public key contains n known as the modulus and e known as the public exponent. The public key is shared with everyone
• The private key contains d known as the private exponent. The private key is kept secret by the signer

Hash

• Hash is a one way operation that computes the message digest
• Hash algorithms: MD2, MD5, SHA-1, SHA-224, SHA-256, SHA-384, SHA-512

PKCS#1 v1.5 padding scheme

• For some security reasons, RSA encryption is not computed directly on the hash value but on the padded hash value
• PKCS#1 v1.5 padding scheme is 0x00 || 0x01 || PS || 0x00 || A || H where PS is the padding string (0xFF..FF), A is the hash algorithm representation, and H is the hash value

RSA signature

• RSA encryption: s ≡ m^d (mod n) where s is the signature, m is the message, d is the private exponent, and n is the modulus
• RSA decryption: m ≡ s^e (mod n) where s is the signature, m is the message, e is the public exponent, and n is the modulus
• Signature creation consists in creating s ≡ m^d (mod n)
• Signature validation consists in validating that m ≡ s^e (mod n)

Let’s now create and validate a signature step by step in practice using:

• RSA key size: 1024 bits
• Hash algorithm: SHA-256
• Encryption algorithm: RSA
• Padding scheme: PKCS#1 v1.5

Note that in this article we use PKCS#1 v1.5 padding scheme (published in November 1993) to ease our understanding since it is easier to implement. There is a newer padding scheme called PSS (published in June 2002).

Prerequisites

Create the message

! echo "This is the message" > message.txt
! cat message.txt
This is the message

Create the signer key pair (private key and public key)

! openssl genrsa -out private_key.pem 1024
! openssl rsa -in private_key.pem -outform PEM -pubout -out public_key.pem
Generating RSA private key, 1024 bit long modulus (2 primes)
..........+++++
.................................................+++++
e is 65537 (0x010001)
writing RSA key

View the public key

! openssl rsa -in public_key.pem -pubin -text -noout
RSA Public-Key: (1024 bit)
Modulus:
    00:b9:b2:7e:e5:e5:c7:4f:e2:ff:81:98:58:34:29:
    2a:d7:05:ff:07:b5:19:3f:97:a1:82:59:a8:95:ef:
    d7:f1:fd:d4:41:92:8b:d1:69:17:bd:c5:44:57:0f:
    4e:9d:d9:37:a2:35:2e:b3:a0:a1:58:a1:4a:0f:4d:
    29:73:4a:ec:9b:3e:96:ff:bb:72:ee:b4:a5:89:3e:
    de:db:4c:cc:13:e4:56:de:4a:57:ef:2c:3c:1b:7d:
    6b:23:ea:64:18:fd:81:65:2c:f3:35:42:be:26:57:
    6b:76:cc:0f:3f:f0:22:c7:a7:ef:f5:e9:16:9d:e5:
    ac:75:e4:13:25:98:f5:d9:73
Exponent: 65537 (0x10001)

Extract the modulus

modulus = ! openssl rsa -in public_key.pem -pubin -text -noout | sed -n "3, 11p" | tr -cd [:alnum:]
modulus = int(modulus[0], 16)
modulus
130401042714550198680323152223836602700614338254158583099498242994430632521550597557943990480605959203870786025736129199341746157763030376599929178590624188605069475481610457830508892793244277149636028650889393771751410209321899089887823996360701456716564516725007778068921620001728430060176813722407565384051

Extract the public exponent

public_exponent = ! openssl rsa -in public_key.pem -pubin -text -noout | sed -n "12, 13p" | cut -d ' ' -f2
public_exponent = int(public_exponent[0])
public_exponent
65537

View the private key

! openssl rsa -in private_key.pem -text -noout
RSA Private-Key: (1024 bit, 2 primes)
modulus:
    00:b9:b2:7e:e5:e5:c7:4f:e2:ff:81:98:58:34:29:
    2a:d7:05:ff:07:b5:19:3f:97:a1:82:59:a8:95:ef:
    d7:f1:fd:d4:41:92:8b:d1:69:17:bd:c5:44:57:0f:
    4e:9d:d9:37:a2:35:2e:b3:a0:a1:58:a1:4a:0f:4d:
    29:73:4a:ec:9b:3e:96:ff:bb:72:ee:b4:a5:89:3e:
    de:db:4c:cc:13:e4:56:de:4a:57:ef:2c:3c:1b:7d:
    6b:23:ea:64:18:fd:81:65:2c:f3:35:42:be:26:57:
    6b:76:cc:0f:3f:f0:22:c7:a7:ef:f5:e9:16:9d:e5:
    ac:75:e4:13:25:98:f5:d9:73
publicExponent: 65537 (0x10001)
privateExponent:
    45:ef:8d:8f:33:cc:ae:af:85:1e:df:ab:48:69:c0:
    b2:9e:95:7f:e7:9a:8c:b2:a4:a7:1c:f1:3b:16:cb:
    33:5e:2f:54:4a:c6:d1:a5:4c:c5:b1:c7:9d:2a:2c:
    a7:92:29:3b:b3:df:d4:d2:c8:31:42:fd:4b:69:fa:
    14:6b:c1:53:c9:f1:94:5c:ef:bc:79:30:18:d0:37:
    5e:11:1a:a0:60:ad:31:fe:ee:2e:04:58:17:df:58:
    a7:4b:76:11:ca:56:21:58:b5:41:cf:e3:8f:fb:e4:
    74:6c:47:c0:27:55:1a:4f:d6:d0:33:01:fc:c2:5e:
    52:bb:fd:67:b6:0f:72:d1
prime1:
    00:e6:6c:4b:a7:62:96:3e:27:43:e5:73:92:fa:5d:
    17:d6:50:fe:19:6f:56:c5:98:a6:ad:24:c0:62:a7:
    8d:13:d8:71:63:a5:ad:76:f7:f0:10:28:4d:53:0f:
    53:fe:1a:73:e2:97:81:f9:2e:30:e4:e4:80:33:c3:
    84:76:2b:17:bd
prime2:
    00:ce:4f:45:8c:ba:d8:71:62:64:21:43:78:db:95:
    b2:b0:e3:2f:5e:7b:24:10:5d:17:43:ba:d6:93:11:
    ba:85:1d:83:ed:3e:e6:90:14:75:8d:84:6b:3e:6a:
    cf:6e:a0:bc:6f:44:7f:33:f2:22:e6:fc:39:0a:71:
    12:57:38:70:ef
exponent1:
    3c:fd:9f:4c:d0:00:9a:b5:03:f8:c1:0d:bf:6d:52:
    b8:ec:b9:45:7c:3e:08:91:6e:54:d8:2c:80:30:7f:
    5c:28:67:63:0b:e0:8d:63:f5:4c:21:8e:ce:14:79:
    94:01:e6:78:ac:c7:bf:70:25:8b:00:9c:9a:96:ff:
    01:d4:48:35
exponent2:
    00:c7:43:b3:96:48:85:73:86:27:d6:24:f8:1f:86:
    c8:0f:a7:6e:82:20:07:e6:32:33:9d:3c:61:b1:ac:
    e6:ed:59:63:aa:0b:1d:e0:3d:92:88:bc:44:65:05:
    ff:12:07:f7:d8:b4:5c:f4:0c:43:ff:bb:cf:50:31:
    84:18:70:30:4b
coefficient:
    48:72:09:b5:8e:8a:81:67:f1:87:0e:70:be:7b:aa:
    91:63:96:99:30:8a:4d:8a:08:4f:06:bb:73:53:bc:
    39:34:a8:cd:7b:43:60:6c:90:aa:10:3b:8b:70:00:
    46:90:b0:ec:e8:b3:e0:61:f3:d5:68:1f:8b:45:d5:
    f3:49:81:ca

Extract the private exponent

private_exponent = ! openssl rsa -in private_key.pem -text -noout | sed -n "14, 22p" | tr -cd [:alnum:]
private_exponent = int(private_exponent[0], 16)
private_exponent
49110556422792132746810748786009964262272656618233091964261648131414878189372596379528717717355330348809660812780858765249446551809010417859216198269279729901970577710071558159833880427935898523502791520091166312125490319116564290835871894128578736263206013297840068902959183356055612038492172959506511131345

Signature creation using OpenSSL

Sign the message using the signer private key

! pip install hexdump
! openssl dgst -sha256 -sign private_key.pem -out signature.bin message.txt

View the signature

! python -m hexdump signature.bin
00000000: 0F 1D 93 A6 18 A5 09 D6  AC 12 27 EB 64 AC DC 14  
00000010: 1C A0 5A 16 C2 4C 38 E2  00 1E A7 08 65 E0 4A 71  
00000020: 5C 0A 8E 05 4A 20 D2 6D  B6 C6 E5 99 B6 B2 B5 FA
00000030: BA FC A5 59 EE E1 D8 0A  0D 06 ED AB 11 86 78 84  
00000040: EB DF F5 AA F8 82 7B CE  47 0B 33 30 65 16 6C EA
00000050: CC 54 ED CB 0C 4F DC 1C  09 BB A4 24 52 F8 F3 07  
00000060: 2A D1 7A 67 FD C2 87 EE  A8 0F DD EF 39 23 3A 35  
00000070: A9 5E 44 C3 4C E2 E2 EF  ED 1E 7E 38 CE 15 DD 67

Signature validation using OpenSSL

Validate the signature using the signer public key

! openssl dgst -sha256 -verify public_key.pem -signature signature.bin message.txt
Verified OK

The signature is valid

Breaking down the signature creation steps

Compute the message hash

hash = ! openssl dgst -sha256 message.txt | cut -d ' ' -f2
hash = hash[0]
hash
'7900e98b91235a38e42fe996421bd090feeb232c6d6d34f219ae8250bbc5859f'

Add the padding to the hash as below

padding_string = "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
algorithm_representation = "3031300d060960864801650304020105000420"
padded_hash = "0001" + padding_string + "00" + algorithm_representation + hash
padded_hash
'0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d0609608648016503040201050004207900e98b91235a38e42fe996421bd090feeb232c6d6d34f219ae8250bbc5859f'

Sign the padded hash with private exponent and modulus

# (a ** b) % c is optimized by pow(a, b, c)
signature = hex(pow(int(padded_hash, 16), private_exponent, modulus))[2:]
signature
'f1d93a618a509d6ac1227eb64acdc141ca05a16c24c38e2001ea70865e04a715c0a8e054a20d26db6c6e599b6b2b5fabafca559eee1d80a0d06edab11867884ebdff5aaf8827bce470b333065166ceacc54edcb0c4fdc1c09bba42452f8f3072ad17a67fdc287eea80fddef39233a35a95e44c34ce2e2efed1e7e38ce15dd67'

The signature has the same value as the one created with OpenSSL

Breaking down the signature validation steps

Compute the padded hash with public exponent and modulus

# (a ** b) % c is optimized by pow(a, b, c)
padded_hash = hex(pow(int(signature, 16), public_exponent, modulus))
padded_hash
'0x1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d0609608648016503040201050004207900e98b91235a38e42fe996421bd090feeb232c6d6d34f219ae8250bbc5859f'

Extract the hash by removing the padding

hash_received = padded_hash[-64:]
hash_received
'7900e98b91235a38e42fe996421bd090feeb232c6d6d34f219ae8250bbc5859f'

Validate the signature by comparing the received hash with the expected hash

hash_received == hash
True

The signature is valid

Links

• Corresponding Jupyter notebook: https://github.com/bntan/rsa-signature
• RSA: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• PKCS#1: https://en.wikipedia.org/wiki/PKCS_1
• PKCS#1 v1.5 (RFC-2313): https://tools.ietf.org/html/rfc2313