CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
Part IV
The key distribution problem
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
A key predistribution scheme (PKS)
A session key distribution scheme (SKDS)
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
The problem:
Throughout the course we have assumed that Alice and
Bob have previously exchanged keys using a secure
channel.
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
The problem:
Throughout the course we have assumed that Alice and
Bob have previously exchanged keys using a secure
channel. This implies:
That Alice and Bob are already known to each
other
That Alice and Bob have foreseen that they will
wish to communicate securely in the future
That Alice and Bob are able to store the key
information securely
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
The problem:
Throughout the course we have assumed that Alice and
Bob have previously exchanged keys using a secure
channel. This implies:
That Alice and Bob are already known to each
other
That Alice and Bob have foreseen that they will
wish to communicate securely in the future
That Alice and Bob are able to store the key
information securely
This is unrealistic for widespread business or personal
use.
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
Distributing private keys
We will consider two ways that an organisation might
distribute keys:
1 A key predistribution scheme
2 A session key distribution scheme
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
A key predistribution scheme (PKS)
A session key distribution scheme (SKDS)
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
A key predistribution scheme (PKS)
Definition
A trusted authority distributes keying information
in advance
Keying information is distributed using secure
channels
Keying information might be long lived keys or
secret information that can later be used to
produce keys
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
A key predistribution scheme (PKS)
A session key distribution scheme (SKDS)
CM30173:
Cryptography
Part IV
The problem:
A key
predistribution
scheme (PKS)
A session key
distribution scheme
(SKDS)
A session key distribution scheme (SKDS)
Definition
A session key scheme involves a trusted authority
and two users, Alice and Bob, who wish to
communicate.
The objective is the production of a session key
known only to Alice and Bob (and possibly the TA).
Session keys are used to encrypt information for a
specified, short period of time.
Often each network user will share a di!erent long
lived key with the TA.
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
New directions in cryptography
Idea 1: A public-key cryptosystem
Idea 2: A signature scheme
Idea 3: Public-key distribution scheme
RSA
Mathematical background
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
1976: Di!e and Hellman
“We stand today on the brink of a
revolution in cryptography.”
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
1976: Di!e and Hellman
“We stand today on the brink of a
revolution in cryptography.”
Gave an abstract way of providing secure
communication between two people who had not
met or exchanged securely a secret key.
Argued how such a system could also provide
secure digital signatures.
Gave a practical method by which two people,
without the aid of a trusted authority, can establish
a shared secret key using an insecure channel.
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
New directions in cryptography
Idea 1: A public-key cryptosystem
Idea 2: A signature scheme
Idea 3: Public-key distribution scheme
RSA
Mathematical background
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
A public-key cryptosystem
Definition
A public-key cryptosystem is a cryptosystem
(P, C,K, E ,D) where
1 For every k ! K, ek is the inverse of dk
2 For every k ! K and for every x ! P or y ! C,
ek(x) and dk(y) are easy to compute
3 It is computationally infeasible (for almost all
k ! K) to derive dk from ek
4 For every k ! K it is feasible to compute ek and dk
from k
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
Recall Alice and Bob
Alice Bob
Oscar
PlaintextPlaintext
Encryption Decryption
Unsecured channel
ek(x) = y dk(y) = x
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
Private-key cryptosystems
Alice Bob
Oscar
PlaintextPlaintext
Encryption Decryption
Unsecured channel
Secure channel
ek(x) = y dk(y) = x
k
k
xx
Key source
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
Public-key cryptosystem
Alice Bob
Oscar
PlaintextPlaintext
Encryption Decryption
Unsecured channel
Unsecured channel
ek(x) = y dk(y) = x
ek
dk
xx
Key source
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
Trap-door one-way function
Definition (One-way function)
A one-way function is a function f : X ” Y such that
for all x ! X it is easy to compute f(x) but for
(almost) all y ! Y it is computationally infeasible to
find an x such that f(x) = y.
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
Trap-door one-way function
Definition (One-way function)
A one-way function is a function f : X ” Y such that
for all x ! X it is easy to compute f(x) but for
(almost) all y ! Y it is computationally infeasible to
find an x such that f(x) = y.
Definition (Trap-door one-way function)
A trap-door one-way function is a one-way function
f : X ” Y such that given some additional trap-door
information it becomes feasible, for all y ! Y to find
x ! X such that y = f(x).
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
And what about security?
Task: Recall the definitions from lecture 2 and consider
if they are still relevant.
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
And what about security?
Task: Recall the definitions from lecture 2 and consider
if they are still relevant.
Clearly a public-key cryptosystem can never be
unconditionally secure.
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
And what about security?
Task: Recall the definitions from lecture 2 and consider
if they are still relevant.
Clearly a public-key cryptosystem can never be
unconditionally secure.
Alice looks up Bob’s public key function ek and
encrypts x: y = ek(x).
Oscar encrypts each possible message in turn until
he finds the unique x such that y = ek(x).
CM30173:
Cryptography
Part IV
New directions in
cryptography
Idea 1: A public-key
cryptosystem
Idea 2: A signature
scheme
Idea 3: Public-key
distribution scheme
RSA
Mathematical
background
And what about security?
Task: Recall the definitions from lecture 2 and consider
if they are still relevant.
Clearly a public-key cryptosystem can never be
unconditionally secure.
Alice looks up Bob’s public key function ek and
encrypts x: y = ek(x).
Oscar encrypts each possible message in turn until
he finds the unique x such that y = ek(x).
Note that Oscar can always launch a chosen-plaintext
attack.
The key distribution problem
A key predistribution scheme (PKS)
A session key distribution scheme (SKDS)
Public-key cryptography
New directions in cryptography
Idea 1: A public-key cryptosystem
Idea 2: A signature scheme
Idea 3: Public-key distribution scheme
RSA
Mathematical background