CM30173: Cryptography
eserved@d =[@let@token art VI
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Part VI
Signature schemes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Confidentiality: Keeping information a secret
from those not authorised to have it.
Data integrity: Ensuring information has not
been altered by those not authorised to do so.
Authentication: Confirmation of the identity of
an entity.
Message authentication: Confirmation of the
source of information.
Signature: A way of binding information to an
entity.
Certification: Endorsement of information by a
trusted entity.
Non-repudiation: Preventing an entity from
denying previous actions or commitments.
Revocation: Retracting certification or
authorisation.
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Conventional vs digital
1 A conventional signature is physically attached to a
message.
2 A conventional signature is verified by comparing
to other authentic signatures.
3 A copy of a signed conventional document can
usually be distinguished from the original.
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Two classes of signature
1 Digital signature with appendix
2 Digital signature with message recovery
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Definition
Definition (Signature scheme)
A signature scheme is a five-tuple (P,A,K,S,V)
P, a finite set of possible messages
A, a finite set of possible signatures
K, a keyspace, the finite set of possible keys.
For each key k there is a signing algorithm
sig
k
: P ! A and a corresponding verification
algorithm verk : P “A ! {t, f} such that for all
messages x and all signatures y:
verk(x, y) =
!
t if y = sig
k
(x)
f if y #= sig
k
(x)
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Informal requirements
What do we need for this to make sense?
For each key sig
k
and verk need to be polynomial
time functions
Given a message x, it should be computationally
infeasible for someone other than Alice to sign x
with Alice’s signature function
If we have a pair (x, y) such that verk(x, y) = t
verifies Alice signed x, produced by someone other
than Alice and where x was not previously signed
by Alice then we call y a forgery.
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Comparison with MACs
Digital signatures:
simplify key management
are publically verifiable
are transferable
allow non-repudiation
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Comparison with MACs
Digital signatures:
simplify key management
are publically verifiable
are transferable
allow non-repudiation
However, we need certain infrastructure to gain these
advantages.
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Comparison with MACs
Digital signatures:
simplify key management
are publically verifiable
are transferable
allow non-repudiation
However, we need certain infrastructure to gain these
advantages.MACs:
don’t require infrastructure (just some shared
secret information)
are considerably more e!cient
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack models
Key-only attack
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack models
Key-only attack
Known message attack
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Attack models
Key-only attack
Known message attack
Chosen message attack
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Goals
There are several goals an attacker might have:
Total break
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Goals
There are several goals an attacker might have:
Total break
Selective forgery
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Goals
There are several goals an attacker might have:
Total break
Selective forgery
Existential forgery
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Signing and encrypting?
What if I want confidentiality as well?
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Signing and encrypting?
What if I want confidentiality as well?
Given a message x Alice wishes to sign and encrypt for
Bob she has two choices:
1 Compute her signature on x, y = sigAlice(x) then
encrypt both x and y for Bob, z = eBob(x, y) or
2 Encrypt x for Bob, z = eBob(x) and sign the result,
y = sigAlice(z)
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Signing and encrypting?
What if I want confidentiality as well?
Given a message x Alice wishes to sign and encrypt for
Bob she has two choices:
1 Compute her signature on x, y = sigAlice(x) then
encrypt both x and y for Bob, z = eBob(x, y) or
2 Encrypt x for Bob, z = eBob(x) and sign the result,
y = sigAlice(z)
Which one is the right way round?
CM30173:
Cryptography
Part VI
What is a digital
signature?
What do we mean
by secure?
Example: RSA
signature scheme
Examples of attacks
Signatures and
hashes
Signing and encrypting?
What if I want confidentiality as well?
Given a message x Alice wishes to sign and encrypt for
Bob she has two choices:
1 Compute her signature on x, y = sigAlice(x) then
encrypt both x and y for Bob, z = eBob(x, y) or
2 Encrypt x for Bob, z = eBob(x) and sign the result,
y = sigAlice(z)
Which one is the right way round?
Why?
Signature schemes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks
Signatures and hashes