Practical 14: Digital Signatures

Get access to whole semester resourcesSemester Pass

Chapter Nineteen

Syllabus topic Module 2, "Digital Signatures: Implement digital signature algorithms such as RSA-based signatures, and verify the integrity and authenticity of digitally signed messages."

Pages 146 to 153 of 206

Aim

To implement an RSA-based digital signature, to verify the integrity and the authenticity of a signed message, and to show what a signature gives that a message authentication code does not.

What you need to know before you start

Practical 13 ended on a limit: a MAC uses one shared key, so a tag proves only that one of the two key holders made it, and neither can prove anything against the other.

A signature removes that limit by using the key pair of Practical 12 the other way round.

Signing uses the private key, which only the signer has.
Verifying uses the public key, which everybody has.

So anybody can check a signature and nobody else can make one. That is non-repudiation: the signer cannot later deny it, because nobody else could have produced it.

Signing is not encrypting backwards, and getting that wrong costs marks. The arithmetic is the same operation with the other exponent, and that is where the confusion comes from, but what it achieves is the opposite:

	Encryption	Signature
Key used to make it	the recipient's public key	the signer's private key
Key used to undo it	the recipient's private key	the signer's public key
Who can read the message	only the recipient	anybody
What it gives	secrecy	authenticity and non-repudiation

A signature provides no secrecy at all. The message travels in the clear beside it.

Why a hash is signed, and not the message

RSA can only act on a number smaller than the modulus. A signature therefore signs the hash of the message, which is a fixed 256 bits however large the message is.

signature = H(message)^d mod n

verify: signature^e mod n = H(message) ?

Three reasons, and an examiner may ask for any of them:

Size. A 10 MB file does not fit in a 2048-bit number.
Speed. Public-key arithmetic is slow; hashing is fast. Sign 32 bytes, not ten million.
Safety. Splitting a long message into blocks and signing each would let an attacker reorder, drop or reuse the blocks. One hash over the whole message cannot be rearranged.

Step 1: signing and verifying, from nothing

"""Practical 14: RSA digital signatures, and why a signature is not encryption."""
import hashlib

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y

def inverse_mod(a, m):
    g, x, _ = egcd(a % m, m)
    if g != 1:
        raise ValueError("no inverse")
    return x % m

def is_prime(n, rounds=40):
    """Miller-Rabin. A key made from numbers that are not prime does not work,
    and it fails SILENTLY: signing and verifying simply disagree."""
    import random
    if n < 2:
        return False
    for small in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % small == 0:
            return n == small
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2
        r += 1
    rng = random.Random(0)
    for _ in range(rounds):
        a = rng.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1):
            continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1:
                break
        else:
            return False
    return True

# Two real 256-bit primes, so n is 512 bits and a SHA-256 digest fits inside it.
p = 0xE1A9B1C3D5E7F9012B4D6F8193A5B7C9DAF3E5D7C9BBAD9F8171635547392BCD
q = 0xC3B5A7998B7D6F615345372918FBEDDFC1B39587796B5D4F41332517F9EBDF7F
assert is_prime(p) and is_prime(q), "p and q must actually be prime"
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = inverse_mod(e, phi)

MESSAGE = b"Pay Rahul 5000 rupees on 30 September 2026"

def sign(message):
    h = int.from_bytes(hashlib.sha256(message).digest(), "big")
    return pow(h, d, n)

def verify(message, signature):
    h = int.from_bytes(hashlib.sha256(message).digest(), "big")
    return pow(signature, e, n) == h

print("the key")
print("  p is prime :", is_prime(p), " q is prime :", is_prime(q))
print("  n has %d bits" % n.bit_length())
print("  e =", e)
print()
print("SIGNING")
print("  message :", MESSAGE.decode())
digest = hashlib.sha256(MESSAGE).hexdigest()
print("  sha256  :", digest)
sig = sign(MESSAGE)
print("  signature = digest^d mod n")
print("  signature :", hex(sig)[:66] + "...")
print("  it is %d bits, always about the size of n (%d bits), whatever the\n  message length" % (sig.bit_length(), n.bit_length()))
print()
print("VERIFYING")
print("  anybody with the PUBLIC key computes signature^e mod n and compares")
print("  it with their own hash of the message.")
print("  original message accepted :", verify(MESSAGE, sig))
TAMPERED = b"Pay Rahul 9000 rupees on 30 September 2026"
print("  tampered message accepted :", verify(TAMPERED, sig))
print("  wrong signature accepted  :", verify(MESSAGE, sig + 1))
print()
print("WHY THE HASH")
print("  RSA can only act on a number smaller than n. A 41-byte message is")
print("  328 bits and would fit here, but a 10 MB file would not, and")
print("  splitting it into blocks would let an attacker reorder them.")
print("  Hashing first gives a fixed 256 bits whatever the message, and any")
print("  change to the message changes it completely.")
print()
print("SIGNING IS NOT ENCRYPTING BACKWARDS")
print("  The arithmetic is the same operation with the other exponent, but")
print("  what it achieves is the opposite:")
print("    encryption with the PUBLIC key   -> only the key holder can read it")
print("    signing   with the PRIVATE key   -> anybody can read it, and")
print("                                        nobody else could have made it")
print("  A signature gives no secrecy at all. The message travels in clear.")
print()
print("WHAT A SIGNATURE GIVES THAT A MAC DOES NOT")
print("  A MAC uses one shared key, so either party could have produced the")
print("  tag. It proves the message came from one of the two of you.")
print("  A signature uses a key only the signer has, so the signer cannot")
print("  later deny it. That is NON-REPUDIATION, and it is why a signature")
print("  and not a MAC is what a contract needs.")

Practical 14: Digital Signatures

the key
  p is prime : True  q is prime : True
  n has 512 bits
  e = 65537

SIGNING
  message : Pay Rahul 5000 rupees on 30 September 2026
  sha256  : 978db1b9d935eee22d341fa6c30513443105d5d68c2137fd8856ea4393b8f4f0
  signature = digest^d mod n
  signature : 0x4885d33113da11f8a4649e0bbd8a947727902be9d493951f867482e899b2994b...
  it is 511 bits, always about the size of n (512 bits), whatever the
  message length

VERIFYING
  anybody with the PUBLIC key computes signature^e mod n and compares
  it with their own hash of the message.
  original message accepted : True
  tampered message accepted : False
  wrong signature accepted  : False

WHY THE HASH
  RSA can only act on a number smaller than n. A 41-byte message is
  328 bits and would fit here, but a 10 MB file would not, and
  splitting it into blocks would let an attacker reorder them.
  Hashing first gives a fixed 256 bits whatever the message, and any
  change to the message changes it completely.

SIGNING IS NOT ENCRYPTING BACKWARDS
  The arithmetic is the same operation with the other exponent, but
  what it achieves is the opposite:
    encryption with the PUBLIC key   -> only the key holder can read it
    signing   with the PRIVATE key   -> anybody can read it, and
                                        nobody else could have made it
  A signature gives no secrecy at all. The message travels in clear.

WHAT A SIGNATURE GIVES THAT A MAC DOES NOT
  A MAC uses one shared key, so either party could have produced the
  tag. It proves the message came from one of the two of you.
  A signature uses a key only the signer has, so the signer cannot
  later deny it. That is NON-REPUDIATION, and it is why a signature
  and not a MAC is what a contract needs.

Practical 14: Digital Signatures

Read the VERIFYING block. The real message is accepted, the tampered message is rejected, and a signature off by one is rejected. Three lines, and between them they are the whole of MU's "verify the integrity and authenticity of digitally signed messages".

Note what verification actually does: it computes signature^e mod n with the public key and compares the result with its own hash of the message it received. If they match, the signature was made by whoever holds d, over exactly that message.

The signature is the size of the key, not the size of the message. 511 bits here for a 512-bit modulus, and it would be the same for a one-line message or a gigabyte file, because in both cases it is a 256-bit digest that was signed.

Practical 14: Digital Signatures

The Miller-Rabin test is in the program on purpose. A first version of it used two hexadecimal numbers that were not in fact prime. Everything still ran: a key was made, a signature was produced, and verification silently returned False for a message that had not been touched. A key built from numbers that are not prime fails without an error message, so the program asserts that they are prime before using them.

Step 2: the same thing with OpenSSL

$ openssl genrsa -out sign.pem 2048 2>/dev/null
$ openssl rsa -in sign.pem -pubout -out sign.pub 2>/dev/null
$ echo -n "Pay Rahul 5000 rupees on 30 September 2026" > contract.txt
$ openssl dgst -sha256 -sign sign.pem -out contract.sig contract.txt
$ wc -c < contract.sig
256
$ openssl dgst -sha256 -verify sign.pub -signature contract.sig contract.txt
Verified OK

256 bytes, which is 2048 bits, the size of the key. And Verified OK, which is what -verify prints when the check passes.

Now tamper with the message and check again.

$ echo -n "Pay Rahul 9000 rupees on 30 September 2026" > forged.txt
$ openssl dgst -sha256 -verify sign.pub -signature contract.sig forged.txt 2>&1 | sed -E 's/^[0-9A-F]{8,}:/<this run>:/'
<this run>:error:02000068:rsa routines:ossl_rsa_verify:bad signature:../crypto/rsa/rsa_sign.c:430:
<this run>:error:1C880004:Provider routines:rsa_verify:RSA lib:../providers/implementations/signature/rsa_sig.c:774:
Verification failure
$ ( openssl dgst -sha256 -verify sign.pub -signature contract.sig forged.txt >/dev/null 2>&1 ); echo "openssl exit status $?"
openssl exit status 1

The long hexadecimal string at the front of each error line identifies that one run, so it is replaced above with a fixed word.

Verification failure, and a non-zero exit status. The exit status matters: a script that checks a signature must test it, because the message on the screen is not something a program can act on.

And one more, which shows the signature is tied to the key as well as to the message.

$ openssl genrsa -out other.pem 2048 2>/dev/null
$ openssl rsa -in other.pem -pubout -out other.pub 2>/dev/null
$ openssl dgst -sha256 -verify other.pub -signature contract.sig contract.txt 2>&1 | sed -E 's/^[0-9A-F]{8,}:/<this run>:/'
<this run>:error:0200008A:rsa routines:RSA_padding_check_PKCS1_type_1:invalid padding:../crypto/rsa/rsa_pk1.c:79:
<this run>:error:02000072:rsa routines:rsa_ossl_public_decrypt:padding check failed:../crypto/rsa/rsa_ossl.c:697:
<this run>:error:1C880004:Provider routines:rsa_verify:RSA lib:../providers/implementations/signature/rsa_sig.c:774:
Verification failure
$ ( openssl dgst -sha256 -verify other.pub -signature contract.sig contract.txt >/dev/null 2>&1 ); echo "openssl exit status $?"
openssl exit status 1

The right message, the right signature, the wrong public key, and it fails. A signature is a statement about one message by one key.

Practical 14: Digital Signatures

Step 3: what the signature actually contains

$ openssl pkeyutl -verifyrecover -pubin -inkey sign.pub -in contract.sig -out recovered.bin
$ xxd recovered.bin | tail -3
00000010: 0004 2097 8db1 b9d9 35ee e22d 341f a6c3  .. .....5..-4...
00000020: 0513 4431 05d5 d68c 2137 fd88 56ea 4393  ..D1....!7..V.C.
00000030: b8f4 f0                                  ...
$ openssl dgst -sha256 contract.txt
SHA2-256(contract.txt)= 978db1b9d935eee22d341fa6c30513443105d5d68c2137fd8856ea4393b8f4f0

The last 32 bytes of the recovered block are the SHA-256 of the contract, and the bytes before them are PKCS #1 v1.5 padding: a leading 00 01, a run of FF bytes, a 00, and a short ASN.1 header naming which hash was used. That header is not decoration: without it, a signature made over a SHA-256 digest could be presented as one made over some other digest.

This is the one place in the book where the inside of a signature is visible, and it is worth a paragraph in the journal.

Step 4: the standing of the schemes

FIPS 186-5, the Digital Signature Standard of February 2023, is the document that says which schemes may be used, and the points a student should be able to state are these.

RSA signatures are approved, in the two forms RFC 8017 defines: the older PKCS #1 v1.5, which is what openssl dgst -sign produces by default and what step 3 took apart, and RSASSA-PSS, which adds randomness and is what new systems should use.

ECDSA and EdDSA are approved, and both give much shorter signatures for the same strength: 64 bytes against RSA-2048's 256.

Plain DSA was withdrawn for signing. FIPS 186-5 keeps it only so that old signatures can still be verified. A student who names DSA as a current choice is out of date, and this is a change recent enough that older textbooks still get it wrong.

Step 5: the comparison MU's two practicals are building towards

	MAC, Practical 13	Signature, Practical 14
Keys	one, shared	a private and a public
Who can produce it	either party	only the private key holder
Who can check it	either party	anybody
Proves to a court	nothing	who signed
Non-repudiation	no	yes
Speed	fast	slow
Size, typical	32 bytes	256 bytes, or 64 for ECDSA
Use it for	a session between two parties	a contract or a certificate

Both practicals end at the same place: integrity and authenticity, by two different routes, and only one of them convinces a third party.

Procedure

Build an RSA key from two primes, and test the primes with Miller-Rabin before using them.
Hash the message with SHA-256 and convert the digest to an integer.
Sign by raising the digest to the private exponent modulo n.
Verify by raising the signature to the public exponent and comparing with your own hash.
Verify the original message, a tampered message and a corrupted signature, and record all three results.
Note the signature length against the message length.
Repeat with openssl dgst -sign and -verify on a 2048-bit key, and record the exit status of a failed verification.
Verify a good signature against a different public key and record that it fails.
Recover the signed block with -verifyrecover and find the digest inside it.

Practical 14: Digital Signatures

Observations

Measured	Value
Key	512-bit modulus from two 256-bit primes, both proved prime
Public exponent	65537
Message	Pay Rahul 5000 rupees on 30 September 2026
SHA-256 of it	978db1b9d935eee2 and onward
Signature length, our key	511 bits, always about the modulus size
Original message verified	accepted
Tampered message verified	rejected
Signature plus one verified	rejected
OpenSSL key	2048-bit
OpenSSL signature length	256 bytes
OpenSSL verify, correct message	Verified OK
OpenSSL verify, altered message	Verification failure, non-zero exit status
OpenSSL verify, wrong public key	fails
Inside the recovered block	PKCS #1 v1.5 padding, a hash identifier, and the 32-byte SHA-256

Result

An RSA digital signature scheme was implemented from nothing over SHA-256. A 512-bit key was built from two numbers proved prime by Miller-Rabin, a contract was signed by raising its digest to the private exponent, and verification by the public exponent accepted the original message and rejected both an altered message and an altered signature. The same operations were performed with OpenSSL on a 2048-bit key: the signature was 256 bytes, verification of the correct message printed Verified OK, verification of an altered message printed Verification failure with a non-zero exit status, and a correct signature checked against a different public key also failed. The signed block was recovered with -verifyrecover and shown to contain PKCS #1 v1.5 padding, a hash identifier and the SHA-256 digest of the contract.

Where marks are lost

Saying a signature encrypts the message. It does not. The message is in the clear and a signature adds no secrecy.

Signing the message instead of its hash. It does not fit, it is slow, and splitting it into blocks lets an attacker reorder them.

Using a key whose factors are not prime. Nothing raises an error; verification simply disagrees with signing. Test the primes.

Not checking the exit status of a verification. The words on the screen are not something a script can act on.

Claiming a MAC gives non-repudiation. It does not. Both parties hold the key.

Naming DSA as a current scheme. FIPS 186-5 withdrew it for signing and keeps it only for verifying old signatures.

Reporting only a successful verification. A verification that never fails proves nothing. Show the tampered message being rejected.

Reusing the signing key for encryption. Use separate keys for separate purposes; a signing oracle and a decryption oracle on one key interact badly.

Practical 14: Digital Signatures

For the journal

Aim; signing against encrypting, as a table; why the hash is signed and not the message, with all three reasons; the program with its key, its primality test and its output; the three verification results; the signature length against the message length; the OpenSSL session with the signature size and Verified OK; the failed verification with its exit status; the verification against a different key; the recovered block with the digest visible inside it; the standing of the schemes from FIPS 186-5; the MAC against signature table; the observation table; the result.

Quick revision

Sign with the private key, verify with the public key. The opposite of encryption.
A signature gives authenticity, integrity and non-repudiation, and no secrecy.
Sign the hash, not the message: size, speed and safety against reordering.
signature = H(m)^d mod n; verification checks signature^e mod n against H(m).
The signature is the size of the key, whatever the message length: 256 bytes for RSA-2048.
openssl dgst -sha256 -sign key.pem -out m.sig m.txt and -verify pub.pem -signature m.sig m.txt.
A failed verification prints Verification failure and exits non-zero. Test the status.
Inside a PKCS #1 v1.5 signature: 00 01, FF padding, 00, a hash identifier, then the digest.
FIPS 186-5: RSA and ECDSA and EdDSA are approved; plain DSA is withdrawn for signing.
RSASSA-PSS is the RSA form to prefer for new systems.
A MAC and a signature both give integrity and authenticity; only the signature convinces a third party.

Questions you must be able to answer

1. Which key signs and which key verifies? The private key signs, the public key verifies. Anybody can check a signature and only the key holder can make one.

2. How is signing different from encryption, given that the arithmetic is the same? Encryption uses the recipient's public key and gives secrecy to one reader. Signing uses the signer's private key and gives authenticity to every reader. A signature keeps nothing secret.

3. Why is the hash signed rather than the message? Because RSA can only act on a number smaller than the modulus, because public-key arithmetic is slow, and because signing a long message in blocks would let an attacker reorder, drop or reuse them.

4. How long is your signature, and what does it depend on? The size of the key, not the message: 256 bytes for a 2048-bit key whether the message is one line or a gigabyte.

5. What is non-repudiation, and why does a MAC not give it? That the signer cannot later deny signing, because nobody else could have produced the signature. A MAC uses one shared key, so either party could have produced the tag and neither can prove anything against the other.

Practical 14: Digital Signatures

6. Your program verified a signature as False on a message nobody had touched. What would you check first? Whether p and q are actually prime. A key built from composite numbers produces a d that is not the inverse of e modulo the true phi, and everything runs without an error while signing and verifying disagree.

7. What is inside a PKCS #1 v1.5 signature block? A leading 00 01, a run of FF bytes as padding, a 00 separator, an ASN.1 header identifying the hash algorithm, and then the digest itself. The hash identifier stops a signature over one digest being presented as one over another.

8. Why check the exit status of openssl dgst -verify? Because a script cannot act on the words printed to the screen, and a verification whose result is ignored is not a verification.

9. Is DSA a reasonable choice for a new system? No. FIPS 186-5 withdrew plain DSA for generating signatures and keeps it only for verifying old ones. RSA with PSS, ECDSA or EdDSA are the current choices.

10. A signature verifies against the message and the public key. What has it proved? That whoever holds the matching private key signed exactly that message, and that the message has not changed since. It has proved nothing about secrecy, and nothing about when it was signed.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself for the same subject.

Syllabus for Computer Science Practical 5

Issue