CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
Obvious approach: factor n, compute !(n) and
compute a just as Bob himself did.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
Obvious approach: factor n, compute !(n) and
compute a just as Bob himself did.
Hence, if factoring is computationally feasible RSA
is insecure.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
Obvious approach: factor n, compute !(n) and
compute a just as Bob himself did.
Hence, if factoring is computationally feasible RSA
is insecure.
Is RSA as strong as factorisation?
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
Obvious approach: factor n, compute !(n) and
compute a just as Bob himself did.
Hence, if factoring is computationally feasible RSA
is insecure.
Is RSA as strong as factorisation?
Computing !(n) is no easier than factoring
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
Obvious approach: factor n, compute !(n) and
compute a just as Bob himself did.
Hence, if factoring is computationally feasible RSA
is insecure.
Is RSA as strong as factorisation?
Computing !(n) is no easier than factoring
Knowing a enables you to factor n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA and factoring
Oscar, listening to communications will try to recover x
given xb (mod n), n and b.
This is called the RSA problem.
There is no e!cient algorithm known to solve this
problem.
Obvious approach: factor n, compute !(n) and
compute a just as Bob himself did.
Hence, if factoring is computationally feasible RSA
is insecure.
Is RSA as strong as factorisation?
Computing !(n) is no easier than factoring
Knowing a enables you to factor n
But it is possible that breaking RSA is easier
than factoring.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Computing !(n) is no easier than
factoring
If I know
n = pq (1)
!(n) = (p ! 1)(q ! 1) (2)
then I can compute p and q.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Computing !(n) is no easier than
factoring
If I know
n = pq (1)
!(n) = (p ! 1)(q ! 1) (2)
then I can compute p and q.
Substitute q = n
p
into equation 2:
p2 ! (n ! !(n) + 1)p + n = 0
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Computing !(n) is no easier than
factoring
If I know
n = pq (1)
!(n) = (p ! 1)(q ! 1) (2)
then I can compute p and q.
Substitute q = n
p
into equation 2:
p2 ! (n ! !(n) + 1)p + n = 0
This is one equation in one unknown (I know n and
!(n)). The roots will be p and q.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Security of RSA
How fast can we factor n?
Are there attacks that do not involve factoring?
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The integer factorisation problem
FACTORING
The integer factorisation problem (FACTORING) states:
given a positive integer n find its prime factorisation
n = pe11 p
e2
2 · · · p
ek
k
where pi are distinct primes and ei ” 1.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The integer factorisation problem
FACTORING
The integer factorisation problem (FACTORING) states:
given a positive integer n find its prime factorisation
n = pe11 p
e2
2 · · · p
ek
k
where pi are distinct primes and ei ” 1.
Definition (Splitting)
It su!ces to study algorithms which split n, that is,
find 1 < a < n, 1 < b < n such that n = ab. a and b
are said to be non-trivial factors of n.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Trial division
Before using a more expensive method on n we would
usually trial divide by “small” primes.
“small” is considered as a function of the size of n
In the extreme case we trial divide with all primes
p # $
%
n&
In the worst case n is a product of two primes of
roughly the same size
Perfectly reasonable method if n < 1012
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
There are two categories of factoring algorithm:
Special purpose factoring algorithms
General purpose factoring algorithms
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
There are two categories of factoring algorithm:
Special purpose factoring algorithms
General purpose factoring algorithms
Special purpose algorithms include
Pollard’s p ! 1 method
William’s p + 1 method
The elliptic curve factoring method
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
There are two categories of factoring algorithm:
Special purpose factoring algorithms
General purpose factoring algorithms
Special purpose algorithms include
Pollard’s p ! 1 method
William’s p + 1 method
The elliptic curve factoring method
General purpose algorithms include
The quadratic sieve
The general number field sieve
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Special purpose factoring algorithms and
RSA?
Many authors have recommended that p, q be chosen to
be strong primes.
Definition (Strong prime)
p prime is strong if
1 p ! 1 has a large prime factor (denoted r)
2 p + 1 has a large prime factor
3 r ! 1 has a large prime factor
However, strong primes o"er no protection against the
Elliptic Curve Method...
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Asymptotic runtimes
Quadratic sieve O
!
e(1+o(1))
!
ln n ln ln n
"
Elliptic curve method O
!
e(1+o(1))
!
2 ln p ln ln p
"
Number field sieve O
!
e(1.92+o(1))(ln n)
1/3(ln lnn)2/3
"
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
Factorisation records
Factorisation records
Year
D
ec
im
al
d
ig
it
s
20052000199519901985198019751970
200
180
160
140
120
100
80
60
40
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA200
= 2799783391 1221327870 8294676387 2260162107
0446786955 4285375600 0992932612 8400107609
3456710529 5536085606 1822351910 9513657886
3710595448 2006576775 0985805576 1357909873
4950144178 8631789462 9518723786 9221823983
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
RSA200
= 2799783391 1221327870 8294676387 2260162107
0446786955 4285375600 0992932612 8400107609
3456710529 5536085606 1822351910 9513657886
3710595448 2006576775 0985805576 1357909873
4950144178 8631789462 9518723786 9221823983
= 3532461934 4027701212 7260497819 8464368671
1974001976 2502364930 3468776121 2536794232
0005854795 6528088349
' 7925869954 4783330333 4708584148 0059687737
9758573642 1996073433 0341455767 8728181521
3538140930 4740185467
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
An idea due to Fermat
Di"erence of two squares
To factor n look for x, y ( Z such that
x2 ! y2 = n
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
An idea due to Fermat
Di"erence of two squares
To factor n look for x, y ( Z such that
x2 ! y2 = n
If such x, y can be found then d = gcd(x ! y, n) is a
non trivial factor of n.
CM30173:
Cryptography
Part IV
The RSA
cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring
algorithms
Factoring with
congruent squares
Given a we may factor
n
A more practical idea
In the 1920’s Kraitchik modified the idea of di"erence
of two squares:
Congruent squares
To factor n look for x, y ( Z such that
x2 ) y2 (mod n)
Public-key cryptography
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n