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
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Mathematical background
Arithmetic modulo n
The Euclidean algorithm
The extended Euclidean algorithm
The Chinese remainder theorem
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
Mathematical background
Arithmetic modulo n
The Euclidean algorithm
The extended Euclidean algorithm
The Chinese remainder theorem
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
Reminder of some definitions
A group,
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
Reminder of some definitions
A group, an Abelian group
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
Reminder of some definitions
A group, an Abelian group
A ring
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
Reminder of some definitions
A group, an Abelian group
A ring
A field
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
Reminder of some definitions
A group, an Abelian group
A ring
A field
An important example:
Arithmetic modulo n
CM30173:
Cryptography
Part IV
Mathematical
background
Arithmetic modulo n
The Euclidean
algorithm
The extended
Euclidean algorithm
The Chinese remainder
theorem
When is there a multiplicative inverse?
Proposition
Let n ! Z, n > 0, b ! Zn has a multiplicative inverse if
and only if gcd(b, n) = 1
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
Euler phi-function
Definition
The number of integers less than n and relatively prime
to n is denoted !(n). This function is called the Euler
phi-function.
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
Euler phi-function
Fact (Properties of the Euler phi-function)
1 If p is prime then !(p) = p ! 1.
2 The Euler phi-function is multiplicative, that is, if
gcd(m, n) = 1 then !(n · m) = !(n) · !(m).
3 If n = pe1
1
p
e2
2
· · · p
ek
k
is the prime factorisation of n
then
!(n) = n
!
1 !
1
p1
” !
1 !
1
p2
”
· · ·
!
1 !
1
pk
”
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