FIT1093 Chap.7 Digital Signatures and Non-Repudiation
Digital Signatures and Non-Repudiation
Week 6 completes the cryptography half of the unit with digital signatures, the public-key way of protecting integrity and authenticity against impersonation and modification. A signature scheme has three algorithms. Key generation gives the signer a private signing key and a public verification key.
Signing uses the private key to produce a signature on a message, and verification uses the public key to accept or reject it.
The difference from a message authentication code is who can produce the value. A MAC key is shared, so a receiver could have made the tag and cannot use it to convince anyone else.
A signature can only come from the private-key holder, which yields two properties emphasised in Workshop 6. Unforgeability means nobody without the private key can produce a valid signature on a new or altered document. Non-repudiation means the signer cannot later deny a valid signature, because nobody else could have produced it.
Two algorithms are worked in detail.
RSA hash-and-sign raises the hash of the message to the private exponent, and the verifier raises the signature to the public exponent and compares the result with a fresh hash.
ElGamal signatures, like ElGamal encryption, use a fresh secret nonce for every signature: the signature is a pair, one value reduced modulo p and the other modulo p − 1, and verification checks an equation linking the public key, the pair and the hash. The workshop's closing question explains why the hash must be one-way, since otherwise an attacker could pick a signature first and then find a message to match it.
The week also introduces DSA and ECDSA and the sign-then-encrypt combination.
What this chapter covers
- 01
Key generation, signing and verification
- 02
Signatures compared with MACs
- 03
Unforgeability and non-repudiation
- 04
RSA hash-and-sign
- 05
ElGamal signatures and the role of the nonce
- 06
Why the hash used for signing must be one-way
Worked example · free
Verify an RSA signature with the public key (7, 77)
- 2Square 58 modulo 77: 58 squared is 3364 = 43 × 77 + 53, and 53 squared is 2809 = 36 × 77 + 37, so 58 to the 4th ≡ 37.
- 2Since 7 = 4 + 2 + 1, compute 37 × 53 × 58. First 37 × 53 = 1961 ≡ 36, then 36 × 58 = 2088 ≡ 9.
- 1The recovered value 9 equals the hash, so the signature verifies; an altered message with hash 10 would not match and is rejected.
Key terms
- Digital Signature
- A value computed from a message with the signer's private key that anyone can verify with the matching public key.
- Verification Key
- The public half of a signature key pair, used by any recipient to check signatures.
- Signing Nonce
- A fresh secret random value used once in a discrete-log signature such as ElGamal or DSA.
Digital Signatures and Non-Repudiation FAQ
How does a digital signature differ from a MAC?
A MAC uses a key shared by sender and receiver, so either could have produced the tag. A signature uses the signer's private key, so anyone with the public key can verify it and only the signer could have made it.
Which property stops a signer denying a contract?
Non-repudiation. Because only the private-key holder could have produced a signature that verifies, a valid signature on the contract is evidence the signer approved it, even if they later claim otherwise.
Why do we sign the hash instead of the whole message?
Public-key operations are slow, so signing a short fixed-length digest is far cheaper than signing a long document. It relies on the hash being one-way and collision resistant, so a different message cannot share the signed digest.
Why must the ElGamal nonce be coprime to p minus 1?
The signing formula multiplies by the inverse of the nonce modulo p − 1, and that inverse exists only when their greatest common divisor is 1. Workshop 6 checks this condition before computing the signature.
Assessment move
Learn this chapter as a pair of mirror images: encryption uses the receiver's public key and the receiver's private key undoes it, while signing uses the signer's private key and anyone's copy of the public key checks it. Write out both RSA directions side by side until you never mix the exponents.
Then practise one ElGamal signature and verification with small numbers, paying attention to which values are reduced modulo p and which modulo p − 1. For written questions, rehearse the contract-style scenario from Workshop 6: identify who is cheating, then name unforgeability or non-repudiation and explain how the judge would use the public key.
Finally, explain to yourself why a non-one-way hash would let an attacker forge signatures.
Working through Digital Signatures and Non-Repudiation in FIT1093? Sia is AskSia’s AI Cybersecurity tutor — ask any FIT1093 Digital Signatures and Non-Repudiation question and get a clear, step-by-step explanation grounded in how FIT1093 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
