CM30173: Cryptography
eserved@d =[@let@token art IV
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
Given a public-key cryptosystem…
Given a public-key cryptosystem in which P = C we
might define a mechanism to allow secure digital
signatures:
Alice wishes to sign a message x before sending it
to Bob. She “decrypts” x using her private
decryption function: y = dAlice
k
(x) and sends y to
Bob.
Bob can then “encrypt” y with Alice’s public
encryption function: eAlice
k
(y) = x.
Only Alice could have computed y such that
eAlice
k
(y) = x hence Bob is convinced that Alice
signed the message.
Anyone could have checked Alice’s signature, not
just Bob.
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 practical scheme
Finally Di!e and Hellman gave a new technique for two
people, without the aid of a trusted authority, to
establish a shared secret key using an insecure channel.
The technique employs the apparent di!culty of
computing logarithms in finite fields.
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
1977: Rivest, Shamir and Adleman, RSA
A method for obtaining digital signatures and public-key
cryptosystems:
Rivest, Shamir and Adleman invented the RSA
cryptosystem, providing an implementation of
Di!e and Hellman’s ideas
A similar system was proposed inside GCHQ in
1973 by Cli”ord Cocks in a paper entitled “A note
on non-secret encryption”
RSA is the first public-key cryptosystem we will
study.
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
1977: Rivest, Shamir and Adleman, RSA
A method for obtaining digital signatures and public-key
cryptosystems:
Rivest, Shamir and Adleman invented the RSA
cryptosystem, providing an implementation of
Di!e and Hellman’s ideas
A similar system was proposed inside GCHQ in
1973 by Cli”ord Cocks in a paper entitled “A note
on non-secret encryption”
RSA is the first public-key cryptosystem we will
study.
In order to study RSA we need some 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
Directed reading
W. Di!e and M. E. Hellman. New directions in
cryptography, IEEE Transactions on Information Theory,
IT-22(6):644-654, 1976.
Use the background sections of the paper to check
your understanding of earlier parts of the course.
Start writing short summaries of each section of
the paper
You won’t be able to complete this reading until we
have studied discrete logarithms
Next lecture we will continue with the mathematical
background.
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