Everything You Ever Wanted To Know About RSA Signatures, But Were Afraid To Ask
Everything You Ever Wanted To Know About RSA Signatures, But Were Afraid To Ask
At the core of digital trust is the usage of digital signatures. With this, we can verify the creator of the data, and also that it has not been modified. We do this using public-key encryption, and in this article, we will look at how we can use the hazmat (Hazardous Material) primitives in the Python cryptography library.
Overall, the three main signatures that we use are: RSA, ECDSA and EdDSA. These are defined in the FIPS 186 standard. RSA signatures are based on the RSA encryption method, and ECDSA and EdDSA are based on elliptic curve methods. And, so, while the encryption keys are typically greater than 2,048 bits, elliptic curve methods use keys that are around 256 bits long. But, while elliptic curve methods are faster and have smaller keys, RSA signing is still one of the most popular methods for proving identity, especially within HTTPs connections. The great thing about RSA is that we can use it for encryption and also for digital signatures (whereas, elliptic curve methods are typically just used for digital signatures in their purest form).
The humble digital signature
With a digital signature, we can prove the integrity of a message, and also the identity of the sender. In this, Bob will take a hash of the message, and then create a signature with his private key. He then sends this signature with the message, and Alice will check the signature with his public key. It is important that we can trust Bob’s public key, so we typically sign it with the private key of Trent, of which Alice will check the signature of Trent for the validity of Bob’s public key.
The hashing method must be the same for Bob and Alice, and will typically be MD5 (128-bit) SHA-1 (160-bit), SHA-256 (256-bit) or SHA3_256 (256-bit). These days, MD5 and SHA-1 are seen as being insecure, so we would typically use SHA-256 (or another hash with 256 bits or more).
For the keys, in RSA, we start with Bob generating two prime numbers (p and q), and then computing a modulus (N). The difficulty of RSA is that it is extremely difficult to factorize N back into its factors. Next, we pick the public exponent (e — typically we use the value of 65,537) and then compute PHI which is (p-1)(q-1). Finally, we compute the private exponent (d) with the inverse of e (mod PHI):
Normally, in RSA public key encryption, we would encrypt with e and decrypt with d, but in signing, we sign with d and verify with e. The public key is (e,N), and the private key is (d,N). To perform a signature, we need:
and to check:
if check is equal to H(M), we have a valid signature.
Coding with Python
In this case, we will use RSA keys to sign a message, and then verify the correct signature, but verify that an incorrect signature will fail. To generate a key we can simply add:
private_key = rsa.generate_private_key(public_exponent=65537,key_size=size)and where size is the number of bits in the public modulus (N), and the public_exponent (e) is typically the value of 65,537. This will then generate a private key and a public key. To extract the public key we can use:
pub = private_key.public_key()To create a signature from a message we use our private key to sign it, along with a salt value and a given hash type (SHA-256):
signature = private_key.sign(message,
padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
salt_length=padding.PSS.MAX_LENGTH),hashes.SHA256())PSS (Probabilistic Signature Scheme) is the most secure method of padding the message. We can also use no padding (PKCS1v15):
signature = key.sign(message.encode(),padding.PKCS1v15(),h)The PSS is by far the most secure, as messages without padding are vulnerable to many attacks. To verify we use the associated public key, and generate an exception if it is incorrect:
try:
rtn=pub.verify(signature,message,padding.PSS(mgf=padding.MGF1(hashes.SHA256()),salt_length=padding.PSS.MAX_LENGTH),hashes.SHA256())
except exceptions.InvalidSignature:
print("A bad signature failed")
else:
print("Good signature verified")Coding
The following is the code to generate a good signature and also check the encryption [here]:
from cryptography.hazmat.primitives import serialization as crypto_serialization
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.backends import default_backend as crypto_default_backend
from cryptography.hazmat.primitives.asymmetric import padding
from Crypto.Util.number import *
import binascii
import base64
import sys
keysize=512
message = "This is a message"
pad=0
hashtype=0
h=hashes.SHA256()
if (len(sys.argv)>1):
message=(sys.argv[1])
if (len(sys.argv)>2):
keysize=int(sys.argv[2])
if (len(sys.argv)>3):
pad=int(sys.argv[3])
if (len(sys.argv)>4):
hashtype=int(sys.argv[4])
key = rsa.generate_private_key(
backend=crypto_default_backend(),
public_exponent=65537,
key_size=keysize
)
public_key = key.public_key()
if (hashtype==0): h=hashes.SHA256()
elif (hashtype==1): h=hashes.SHA1()
elif (hashtype==2): h=hashes.SHA224()
elif (hashtype==3): h=hashes.SHA384()
elif (hashtype==4): h=hashes.SHA3_256()
elif (hashtype==5): h=hashes.MD5()
if (pad==0):
signature = key.sign(message.encode(),padding.PSS( mgf=padding.MGF1(h),salt_length=padding.PSS.MAX_LENGTH), h)
else:
signature = key.sign(message.encode(),padding.PKCS1v15(),h)
rtn=None
if (pad==0):
rtn = public_key.verify(signature,message.encode(),padding.PSS( mgf=padding.MGF1(h),salt_length=padding.PSS.MAX_LENGTH), h)
else:
rtn = public_key.verify(signature,message.encode(),padding.PKCS1v15(),h)
print(f"Message: {message}")
print(f"Signature: {signature.hex()}")
print(f"Signature: {base64.b64encode(signature).decode()}")
if (rtn==None): print("Signature verified\n")
print("Method:\t\t\tRSA")
print(f"Key size:\t\t{keysize}")
print(f"Hash:\t\t\t{h.name}")
if (pad==0): print("PSS padding")
else: print("No padding")
print("\n== Key details ==")
print(f"Private key p: {key.private_numbers().p} ({hex(key.private_numbers().p)})")
print(f"Private key q: {key.private_numbers().q} ({hex(key.private_numbers().q)})")
print(f"Private key d: {key.private_numbers().d} ({hex(key.private_numbers().d)})")
print(f"Private key dmp1: {key.private_numbers().dmp1} ({hex(key.private_numbers().dmp1)})")
print(f"Private key dmq1: {key.private_numbers().dmq1} ({hex(key.private_numbers().dmq1)})")
print(f"Private key iqmp: {key.private_numbers().iqmp} ({hex(key.private_numbers().iqmp)})")
print(f"Public key N: {key.private_numbers().public_numbers.n} ({hex(key.private_numbers().public_numbers.n)})")
print(f"Public key e: {key.private_numbers().public_numbers.e} ({hex(key.private_numbers().public_numbers.e)})")
print("\n\n==Let's try a cipher==")
M= bytes_to_long(message.encode('utf-8'))
N=key.private_numbers().public_numbers.n
e=key.private_numbers().public_numbers.e
d=key.private_numbers().d
print("Message: ",message)
C=pow(M,e,N)
print ("Cipher=M^e (mod N)=",C)
M1=pow(C,d,N)
print ("Decrypt: ",long_to_bytes(M1).decode())Note that we normally use RSA keys of 2,048 bits and above, as the state-of-the-art in factorizing the modulus is approaching 1,024 bits.
A sample run is [here] showing a signature with hex and Base64, and using a 512-bit RSA key with SHA-256:
Message: Hello 123
Signature: 27e3f3e27f5693ef371cfa07f249e7934aa71de51ce443445084d3b192113d96c7f7d253b08bb16a14c040da7413540bd99ca93774215310794adc52d05ff49e
Signature: J+Pz4n9Wk+83HPoH8knnk0qnHeUc5ENEUITTsZIRPZbH99JTsIuxahTAQNp0E1QL2ZypN3QhUxB5StxS0F/0ng==
Signature verified
Method: RSA
Key size: 512
Hash: sha256
PSS padding
== Key details ==
Private key p: 97788552682700715869209516738447253059821264202285988392725653463112813905637 (0xd8325c02c662c0f7886e772e47d69a84030a3263674cbff9b71e1ae1404c06e5)
Private key q: 89430188045794288724766615735736599551962340376375285931735688894611227625447 (0xc5b7b15390e0b5e9ebcaae3dc8e1b066846c90b33673c851c57fb1200ae347e7)
Private key d: 3132767790358445840053354932093026005644087509224832928379992249992497549214608795337704299032146651892487311151094108718957093537118048325035899043953849 (0x3bd0a6657945d485356fd3fde515ffe7073bef4ced0e09f0898c489a8852a8cc17e0844ee9c8abc8f600fa549d917b66d6429cd6770433a33c0a0665d743bcb9)
Private key dmp1: 55297675548482361568471316818390454222759297058710632617214897193081173739153 (0x7a41600ea1a8ce7e2bc46bd8dbfedb39b38e5c98219e2121510fd11b77848691)
Private key dmq1: 38273615122883839817999817479529733497618745485398691118197699042007655407457 (0x549e19363a7af15ffb99f2985eb0b85e27ae8eff23fec96cb5a9c09486145f61)
Private key iqmp: 3254889311453785871164802372720912857961901766416447785355975574380097527106 (0x73233ba89dbe0263eeb22021e10dcbd860893eb5ac746bf13e3972e40fb5d42)
Public key N: 8745248655139986583446638079166019735566578484988195920570752314510299948157013756204932892741519270040466725953785468620308568806892742344098905437944739 (0xa6f9e28f4cf1a89a40697b5b71b83d1e6ca92ccb15da105cdaf7929862faf6ab676bd90e4ee26eed6cb2d7794d50eb6e45665492fff69ff376bde7652992bba3)
Public key e: 65537 (0x10001)Conclusions
Every time you connect to a valid Web site, and where its identity is checked, thank RSA signatures! While ECDSA signatures are on the rise, it is still the RSA workhorse that is behind most of the identity proving on the Web.
And, so, what did we learn here?
- The public modulus (N) is the multiplication of two prime numbers (p and q). It should be extremely difficult to factorize N into its factors.
- RSA keys have 2K bits and above.
- We can use a range of hashing methods to take a hash of the message, but those with less than 256-bits (eg MD5 and SHA-1) are not recommended.
- PSS padding is used to overcome hacks on PKCS1v15.
- The private key signs the message (d,N), and the public key (e,N) proves it.
- The RSA signature method uses the keys in the opposite way to RSA encryption.
If you are interested in digital signatures, try here:
https://asecuritysite.com/signatures
and Hazmat here:
https://asecuritysite.com/hazmat
and RSA here: