CS计算机代考程序代写 scheme CM30173: Cryptography

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

RSA signature scheme

Definition

Let n = pq, p, q prime.

P = A = Zn
K = {(n, p, q, a, b) | ab ! 1 (mod !(n))}

For k = (n, p, q, a, b) ” K we have

sig
k
(x) = xa (mod n)

and

verk(y) = t # x ! y
b (mod n)

for x, y ” Zn.

sig
k

is private and verk is public

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

Anyone can create a forgery!

Alice has RSA key k. To create a forgery:

1 Choose random y

2 Compute ek(y)

3 y = sig
k
(x) is now a valid signature for 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

Anyone can create a forgery!

Alice has RSA key k. To create a forgery:

1 Choose random y

2 Compute ek(y)

3 y = sig
k
(x) is now a valid signature for x

This is a key-only 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

Multiplicative property

Let x1, x2 be two messages with signatures
y1 = sigk(x1) and y2 = sigk(x2). Notice that

verk(x1x2 (mod n), y1y2 (mod n)) = t

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

Multiplicative property

Let x1, x2 be two messages with signatures
y1 = sigk(x1) and y2 = sigk(x2). Notice that

verk(x1x2 (mod n), y1y2 (mod n)) = t

An attacker can create a valid signature on
message x1x2.

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

Multiplicative property

Let x1, x2 be two messages with signatures
y1 = sigk(x1) and y2 = sigk(x2). Notice that

verk(x1x2 (mod n), y1y2 (mod n)) = t

An attacker can create a valid signature on
message x1x2.

This is a known message 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

A variation on the theme

Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.

1 Oscar finds x1, x2 ” Zn such that

x ! x1x2 (mod n)

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

A variation on the theme

Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.

1 Oscar finds x1, x2 ” Zn such that

x ! x1x2 (mod n)

2 Oscar requests Alice’s signature on x1 and x2. She
sends him y1 = sigk(x1) and y2 = sigk(x2)

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

A variation on the theme

Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.

1 Oscar finds x1, x2 ” Zn such that

x ! x1x2 (mod n)

2 Oscar requests Alice’s signature on x1 and x2. She
sends him y1 = sigk(x1) and y2 = sigk(x2)

3 Oscar now creates a signature y1y2 (mod n) for
x = x1x2 (mod n)

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

A variation on the theme

Oscar wants to forge Alice’s signature on the message
x. Alice will sign messages for Oscar.

1 Oscar finds x1, x2 ” Zn such that

x ! x1x2 (mod n)

2 Oscar requests Alice’s signature on x1 and x2. She
sends him y1 = sigk(x1) and y2 = sigk(x2)

3 Oscar now creates a signature y1y2 (mod n) for
x = x1x2 (mod n)

This is a chosen message 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

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

The process

x ” {0, 1}!

$ z = h(x) ” P

$ y = sig
k
(z) ” A

h a public hash function

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

The process

x ” {0, 1}!

$ z = h(x) ” P

$ y = sig
k
(z) ” A

h a public hash function

(x, y) is then transmitted

Verification is performed by reconstructing
z = h(x) and then checking that verk(z, y) = t

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 do we mean by secure? (Again!)

As well as considering the security of the signature
scheme we now have to consider what properties h
must satisfy to prevent 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

What do we mean by secure? (Again!)

As well as considering the security of the signature
scheme we now have to consider what properties h
must satisfy to prevent attack.

I’ll tell you the attacks, you tell me the required
property…

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 1

Oscar has a valid signature pair (x, y) where
y = sig

k
(h(x)) previously signed by Alice.

Oscar computes h(x) and finds x” %= x such that
h(x”) = h(x)

Oscar has found a valid signature pair (x”, y)

y is now a forgery for 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

Attack 1

Oscar has a valid signature pair (x, y) where
y = sig

k
(h(x)) previously signed by Alice.

Oscar computes h(x) and finds x” %= x such that
h(x”) = h(x)

Oscar has found a valid signature pair (x”, y)

y is now a forgery for x”

What type of attack is this?

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 1

Oscar has a valid signature pair (x, y) where
y = sig

k
(h(x)) previously signed by Alice.

Oscar computes h(x) and finds x” %= x such that
h(x”) = h(x)

Oscar has found a valid signature pair (x”, y)

y is now a forgery for x”

What type of attack is this?

What property of h do we require to avoid this?

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 2

Oscar finds two messages x %= x” such that
h(x) = h(x”)

Oscar gives x to Alice and persuades her to sign
h(x), Alice sends back signature y

Oscar now has a valid signature pair (x”, y)

y is a forgery for 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

Attack 2

Oscar finds two messages x %= x” such that
h(x) = h(x”)

Oscar gives x to Alice and persuades her to sign
h(x), Alice sends back signature y

Oscar now has a valid signature pair (x”, y)

y is a forgery for x”

Type of 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 2

Oscar finds two messages x %= x” such that
h(x) = h(x”)

Oscar gives x to Alice and persuades her to sign
h(x), Alice sends back signature y

Oscar now has a valid signature pair (x”, y)

y is a forgery for x”

Type of attack?

Property of h?

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 3

Alice is using a signature scheme in which it is
possible to forge signatures on random messages z
(e.g. RSA)

That is, the scheme is subject to key-only
existential forgery

Oscar computes a signature on some message
digest z and finds some x such that z = h(x)

Oscar has a valid signature pair (x, y)

y is a forgery for 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

Attack 3

Alice is using a signature scheme in which it is
possible to forge signatures on random messages z
(e.g. RSA)

That is, the scheme is subject to key-only
existential forgery

Oscar computes a signature on some message
digest z and finds some x such that z = h(x)

Oscar has a valid signature pair (x, y)

y is a forgery for x

What property do we need for h?

Signature schemes
What is a digital signature?
What do we mean by secure?
Example: RSA signature scheme
Examples of attacks

Signatures and hashes