RSA sign and verify using Openssl : Behind the scene

Jupyter (IPython) notebook version of this page: openssl_sign_verify

Digital signature and verification

• A digital signature is a mathematical scheme for presenting the authenticity of digital messages or documents.
• Message / file to be sent is signed with private key.
• Message received by the recipient is authenticated using public key.

RSA sign and verify using OpenSSL

Create sample data file, private key and public key

# Create a file containing all lower case alphabets
$ echo abcdefghijklmnopqrstuvwxyz > myfile.txt
# Generate 512 bit Private key
$ openssl genrsa -out myprivate.pem 512
# Separate the public part from the Private key file.
$ openssl rsa -in myprivate.pem -pubout > mypublic.pem
# Cat the contents of private key
$ cat myprivate.pem
-----BEGIN RSA PRIVATE KEY-----
MIIBOwIBAAJBAMv7Reawnxr0DfYN3IZbb5ih/XJGeLWDv7WuhTlie//c2TDXw/mW
914VFyoBfxQxAezSj8YpuADiTwqDZl13wKMCAwEAAQJAYaTrFT8/KpvhgwOnqPlk
NmB0/psVdW6X+tSMGag3S4cFid3nLkN384N6tZ+na1VWNkLy32Ndpxo6pQq4NSAb
YQIhAPNlJsV+Snpg+JftgviV5+jOKY03bx29GsZF+umN6hD/AiEA1ouXAO2mVGRk
BuoGXe3o/d5AOXj41vTB8D6IUGu8bF0CIQC6zah7LRmGYYSKPk0l8w+hmxFDBAex
IGE7SZxwwm2iCwIhAInnDbe2CbyjDrx2/oKvopxTmDqY7HHWvzX6K8pthZ6tAiAw
w+DJoSx81QQpD8gY/BXjovadVtVROALaFFvdmN64sw==
-----END RSA PRIVATE KEY-----

Sign using Openssl

• Message digest algorithm : SHA1
• Padding scheme : PCKS#1 v1.5

# Sign the file using sha1 digest and PKCS1 padding scheme
$ openssl dgst -sha1 -sign myprivate.pem -out sha1.sign myfile.txt
# Dump the signature file
$ hexdump sha1.sign
0000000 91 39 be 98 f1 6c f5 3d 22 da 63 cb 55 9b b0 6a
0000010 93 33 8d a6 a3 44 e2 8a 42 85 c2 da 33 fa cb 70
0000020 80 d2 6e 7a 09 48 37 79 a0 16 ee bc 20 76 02 fc
0000030 3f 90 49 2c 2f 2f b8 14 3f 0f e3 0f d8 55 59 3d
0000040

Verify sign using Openssl

• Openssl decrypts the signature to generate hash and compares it to the hash of the input file.

# Verify the signature of file
$ openssl dgst -sha1 -verify mypublic.pem -signature sha1.sign myfile.txt
Verified OK

RSA signature generation : Behind the scene

Signature using OPENSSL : Behind the scene

Step 1: Message digest (hash)

• Message (data) goes through a cryptographic-hash function to create a hash of message.
• SHA1 generates 160 bit (20 byte) hash.
• SHA224, SHA256, SHA384, SHA512, MD4, MD5 are few other message digest algorithms available in openssl.

# Calculate SHA1 hash value
# In MAC OS use shasum (with option -a 1) and use sha1sum in linux
$ shasum -a 1 myfile.txt
8c723a0fa70b111017b4a6f06afe1c0dbcec14e3  myfile.txt

Step 2: Padding the hash value

• hash value (20 byte in case of SHA1) is extended to RSA key size by prefixing padding.
• Default padding scheme in openssl is PKCS1.
• PKCS#1v1.5 padding scheme: 00||01||PS||00||T||H
• PS: Octet string with FF such that length of message is equal to key size.
• T: Identifier of signature scheme (Each scheme has its MAGIC bytes).
• H: Hash value of the message.

PKCS#1v1.5 padding scheme for SHA1:

PKCS1 padding scheme for SHA1 digest algorithm

$ PADDING=0001ffffffffffffffffffffffffffffffffffffffffffffffffffff00
$ ANS1_SHA1_MAGIC=3021300906052b0e03021a05000414
$ SHA1_HASH=`shasum -a 1 myfile.txt | cut -d ' ' -f1`
$ echo $PADDING$ANS1_SHA1_MAGIC$SHA1_HASH
0001ffffffffffffffffffffffffffffffffffffffffffffffffffff003021300906052b0e03021a050004148c723a0fa70b111017b4a6f06afe1c0dbcec14e3

Step 3: Get modulus and private exponent from private key

View the contents of private key:

# Get the private exponent and modulus from private key
$ openssl rsa -in myprivate.pem -text -noout
Private-Key: (512 bit)
modulus:
    00:cb:fb:45:e6:b0:9f:1a:f4:0d:f6:0d:dc:86:5b:
    6f:98:a1:fd:72:46:78:b5:83:bf:b5:ae:85:39:62:
    7b:ff:dc:d9:30:d7:c3:f9:96:f7:5e:15:17:2a:01:
    7f:14:31:01:ec:d2:8f:c6:29:b8:00:e2:4f:0a:83:
    66:5d:77:c0:a3
publicExponent: 65537 (0x10001)
privateExponent:
    61:a4:eb:15:3f:3f:2a:9b:e1:83:03:a7:a8:f9:64:
    36:60:74:fe:9b:15:75:6e:97:fa:d4:8c:19:a8:37:
    4b:87:05:89:dd:e7:2e:43:77:f3:83:7a:b5:9f:a7:
    6b:55:56:36:42:f2:df:63:5d:a7:1a:3a:a5:0a:b8:
    35:20:1b:61
prime1:
    00:f3:65:26:c5:7e:4a:7a:60:f8:97:ed:82:f8:95:
    e7:e8:ce:29:8d:37:6f:1d:bd:1a:c6:45:fa:e9:8d:
    ea:10:ff
prime2:
    00:d6:8b:97:00:ed:a6:54:64:64:06:ea:06:5d:ed:
    e8:fd:de:40:39:78:f8:d6:f4:c1:f0:3e:88:50:6b:
    bc:6c:5d
exponent1:
    00:ba:cd:a8:7b:2d:19:86:61:84:8a:3e:4d:25:f3:
    0f:a1:9b:11:43:04:07:b1:20:61:3b:49:9c:70:c2:
    6d:a2:0b
exponent2:
    00:89:e7:0d:b7:b6:09:bc:a3:0e:bc:76:fe:82:af:
    a2:9c:53:98:3a:98:ec:71:d6:bf:35:fa:2b:ca:6d:
    85:9e:ad
coefficient:
    30:c3:e0:c9:a1:2c:7c:d5:04:29:0f:c8:18:fc:15:
    e3:a2:f6:9d:56:d5:51:38:02:da:14:5b:dd:98:de:
    b8:b3

Format the output to print modulus and private exponent:

# Store the output of private key info in a variable
$ PRKEY_INFO=`openssl rsa -in myprivate.pem -text -noout`
# Grep and format string to output Modulus
$ MODULUS=`echo "$PRKEY_INFO" | grep modulus: -A 5 | tail -5`
$ echo `echo $MODULUS | tr -cd [:alnum:]`
00cbfb45e6b09f1af40df60ddc865b6f98a1fd724678b583bfb5ae8539627bffdcd930d7c3f996f75e15172a017f143101ecd28fc629b800e24f0a83665d77c0a3
# Grep and format string to output privateExponent
$ PREXP=`echo "$PRKEY_INFO" | grep privateExponent: -A 5 | tail -5`
$ echo `echo $PREXP | tr -cd [:alnum:]`
61a4eb153f3f2a9be18303a7a8f964366074fe9b15756e97fad48c19a8374b870589dde72e4377f3837ab59fa76b55563642f2df635da71a3aa50ab835201b61

Step 4: Sign the padded hash with private exponent and modulus

Encrypt message with modulus and private exponent to get signature

# Signing is done in python which supports big number arithmetic
# Convert padded hash (calculated in step 2) to integer
[python]$ padded_hash = int('0001ffffffffffffffffffffffffffffffffffffffffffffffffffff003021300906052b0e03021a050004148c723a0fa70b111017b4a6f06afe1c0dbcec14e3', 16)
# Convert modulus (calculated in step 3) to integer
[python]$ modulus = int('00cbfb45e6b09f1af40df60ddc865b6f98a1fd724678b583bfb5ae8539627bffdcd930d7c3f996f75e15172a017f143101ecd28fc629b800e24f0a83665d77c0a3', 16)
# Convert private exponent (calculated in step 3) to integer
[python]$ private_exp = int('61a4eb153f3f2a9be18303a7a8f964366074fe9b15756e97fad48c19a8374b870589dde72e4377f3837ab59fa76b55563642f2df635da71a3aa50ab835201b61', 16)
# Sign the message: (padded_hash ** private_exp) % modulus
# (a**b)%c is efficiently caluclated by pow(a, b, c)
[python]$ sign = hex(pow(padded_hash, private_exp, modulus))[2:]
# Format and the signature
[python]$ slist = list(sign)
[python]$ for i in range(len(sign) - 2, 0, -2) : slist.insert(i,' ')
[python]$ slist[len(slist) - 48 : 0 : -48] = ['\n']*(len(slist)//48)
[python]$ print("".join(slist))
91 39 be 98 f1 6c f5 3d 22 da 63 cb 55 9b b0 6a
93 33 8d a6 a3 44 e2 8a 42 85 c2 da 33 fa cb 70
80 d2 6e 7a 09 48 37 79 a0 16 ee bc 20 76 02 fc
3f 90 49 2c 2f 2f b8 14 3f 0f e3 0f d8 55 59 3d

RSA Signature verification : Behind the scene

Signature verification using OPENSSL : Behind the scene

Step 1: Get modulus and public exponent from public key

View the contents of public key:

• Pubic key contains Modulus, public exponent and key size.
• 65537 (0x10001) is widely accepted default public exponent.

# Get modulus and public exponent from public key
$ openssl rsa -pubin -inform PEM -text -noout < mypublic.pem
Public-Key: (512 bit)
Modulus:
    00:cb:fb:45:e6:b0:9f:1a:f4:0d:f6:0d:dc:86:5b:
    6f:98:a1:fd:72:46:78:b5:83:bf:b5:ae:85:39:62:
    7b:ff:dc:d9:30:d7:c3:f9:96:f7:5e:15:17:2a:01:
    7f:14:31:01:ec:d2:8f:c6:29:b8:00:e2:4f:0a:83:
    66:5d:77:c0:a3
Exponent: 65537 (0x10001)

Format the output to print modulus and public exponent:

# Store the output of public key info in a variable
$ PBKEY_INFO=`openssl rsa -pubin -inform PEM -text -noout < mypublic.pem`
# Grep and format string to output Modulus
$ MODULUS=`echo "$PBKEY_INFO" | grep Modulus: -A 5 | tail -5`
$ echo `echo $MODULUS | tr -cd [:alnum:]`
00cbfb45e6b09f1af40df60ddc865b6f98a1fd724678b583bfb5ae8539627bffdcd930d7c3f996f75e15172a017f143101ecd28fc629b800e24f0a83665d77c0a3
# Grep to print public exponent
$ echo "$PBKEY_INFO" | grep Exponent:
Exponent: 65537 (0x10001)

Step 2: Format and print signature file

• Signature is a binary file which is converted to a big integer and used in authentication.

# sha1.sign is the signature file sent along with data file.
$ echo `hexdump sha1.sign | cut -c 9- | tr -cd [:alnum:]`
9139be98f16cf53d22da63cb559bb06a93338da6a344e28a4285c2da33facb7080d26e7a09483779a016eebc207602fc3f90492c2f2fb8143f0fe30fd855593d

Step 3: Convert sign to padded hash

Decrypt signature using modulus and public exponent to get message

# Convert signature file to integer (Obtained in step 2)
[python]$ signature = int('9139be98f16cf53d22da63cb559bb06a93338da6a344e28a4285c2da33facb7080d26e7a09483779a016eebc207602fc3f90492c2f2fb8143f0fe30fd855593d', 16)
# Convert modulus to integer (Obtained in step 1)
[python]$ modulus = int('00cbfb45e6b09f1af40df60ddc865b6f98a1fd724678b583bfb5ae8539627bffdcd930d7c3f996f75e15172a017f143101ecd28fc629b800e24f0a83665d77c0a3', 16)
# Set the public_exp
[python]$ public_exp = 65537
# Convert sign to hash: (sign ** public_exp) % modulus
# (a**b)%c is efficiently caluclated by pow(a, b, c)
[python]$ padded_hash = hex(pow(signature, public_exp, modulus))
[python]$ padded_hash
'0x1ffffffffffffffffffffffffffffffffffffffffffffffffffff003021300906052b0e03021a050004148c723a0fa70b111017b4a6f06afe1c0dbcec14e3'

Padded hash in verification matches the padded hash in signing.

Step 4: Remove padding to obtain the hash of message

# Remove the padded hash to slice the hash of message
[python]$ padded_hash[-40:]
'8c723a0fa70b111017b4a6f06afe1c0dbcec14e3'

Hash obtained above is the SHA1 hash of data file.

References:

1. Cryptography and coding
2. RSA public key
3. Digital signature
4. MAGIC bytes (used in padding) for various digest algorithms:

Magic bytes (padding) for digest algorithms