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
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
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)
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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are 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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are non trivial factors of n.
Proof.
x2 # y2 (mod n) % x2 ” y2 # 0 (mod 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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are non trivial factors of n.
Proof.
x2 # y2 (mod n) % x2 ” y2 # 0 (mod n)
% n|(x2 ” y2)
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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are non trivial factors of n.
Proof.
x2 # y2 (mod n) % x2 ” y2 # 0 (mod n)
% n|(x2 ” y2)
% n|(x ” y)(x + y)
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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are non trivial factors of n.
Proof.
x2 # y2 (mod n) % x2 ” y2 # 0 (mod n)
% n|(x2 ” y2)
% n|(x ” y)(x + y)
x $# ±y (mod n) % x ” y $# 0 (mod 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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are non trivial factors of n.
Proof.
x2 # y2 (mod n) % x2 ” y2 # 0 (mod n)
% n|(x2 ” y2)
% n|(x ” y)(x + y)
x $# ±y (mod n) % x ” y $# 0 (mod n)
and x + y $# 0 (mod 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
Factoring with congruent squares
Proposition
If we also have x $# ±y (mod n) then gcd(x ” y, n)
and gcd(x + y, n) are non trivial factors of n.
Proof.
x2 # y2 (mod n) % x2 ” y2 # 0 (mod n)
% n|(x2 ” y2)
% n|(x ” y)(x + y)
x $# ±y (mod n) % x ” y $# 0 (mod n)
and x + y $# 0 (mod n)
% n $ |(x ” y), n $ |(x + y)
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
Given a we may factor n
Imagine Oscar has Bob’s public key (n, b) and his
decryption exponent a. Oscar can 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
Given a we may factor n
Imagine Oscar has Bob’s public key (n, b) and his
decryption exponent a. Oscar can factor n. By
definition ba # 1 (mod !(n)) and so
ba ” 1 = k!(n) for some k ! 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
Given a we may factor n
Imagine Oscar has Bob’s public key (n, b) and his
decryption exponent a. Oscar can factor n. By
definition ba # 1 (mod !(n)) and so
ba ” 1 = k!(n) for some k ! N
Hence, for all x ! Z!n:
xba”1 # 1 (mod 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
Given a we may factor n
Imagine Oscar has Bob’s public key (n, b) and his
decryption exponent a. Oscar can factor n. By
definition ba # 1 (mod !(n)) and so
ba ” 1 = k!(n) for some k ! N
Hence, for all x ! Z!n:
xba”1 # 1 (mod n)
Take the square root: y1 =
&
xba”1 = x(ba”1)/2 and
then use
y21 # 1 (mod n)
to try to recover a factor from 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
Given a we may factor n
If y1 # 1 (mod n) then we take the square root of y1:
y2 =
&
y1 = x
(ba”1)/4
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
Given a we may factor n
If y1 # 1 (mod n) then we take the square root of y1:
y2 =
&
y1 = x
(ba”1)/4
We already have that
y22 # y1 # 1 (mod n)
so we can again attempt 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
Given a we may factor n
If y1 # 1 (mod n) then we take the square root of y1:
y2 =
&
y1 = x
(ba”1)/4
We already have that
y22 # y1 # 1 (mod n)
so we can again attempt to factor n.
Continue process until either
You find a non trivial factor of n
(ba ” 1)/2s is not divisible by 2
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
Given a we may factor n
If y1 # 1 (mod n) then we take the square root of y1:
y2 =
&
y1 = x
(ba”1)/4
We already have that
y22 # y1 # 1 (mod n)
so we can again attempt to factor n.
Continue process until either
You find a non trivial factor of n
(ba ” 1)/2s is not divisible by 2
We factor n with probability 1/2.
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
Example
n = 437 = 19 ‘ 23
b = 7
a # b”1 # 7″1 # 283 (mod !(n) = 396)
Assume we know a.
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
Example
n = 437 = 19 ‘ 23
b = 7
a # b”1 # 7″1 # 283 (mod !(n) = 396)
Assume we know a.
Find (ba ” 1)/2 = (7 ‘ 283 ” 1)/2 = 990
Try x = 2
y1 # x(ba”1)/2 # 2990 (mod 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
Example
n = 437 = 19 ‘ 23
b = 7
a # b”1 # 7″1 # 283 (mod !(n) = 396)
Assume we know a.
Find (ba ” 1)/2 = (7 ‘ 283 ” 1)/2 = 990
Try x = 2
y1 # x(ba”1)/2 # 2990 (mod n)
We want
y21 # 1 (mod n) and y1 $# 1 (mod 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
Example
n = 437 = 19 ‘ 23
b = 7
a # b”1 # 7″1 # 283 (mod !(n) = 396)
Assume we know a.
Find (ba ” 1)/2 = (7 ‘ 283 ” 1)/2 = 990
Try x = 2
y1 # x(ba”1)/2 # 2990 (mod n)
We want
y21 # 1 (mod n) and y1 $# 1 (mod n)
But y1 # 2990 # 1 (mod 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
Example
So we need to continue by finding the square root of y1
modulo n:
y2 # x(ba”1)/4 # 2495 # 208 (mod 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
Example
So we need to continue by finding the square root of y1
modulo n:
y2 # x(ba”1)/4 # 2495 # 208 (mod n)
y2 $# 1 (mod n)
y22 # y1 # 1 # 1
2 (mod 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
Example
So we need to continue by finding the square root of y1
modulo n:
y2 # x(ba”1)/4 # 2495 # 208 (mod n)
y2 $# 1 (mod n)
y22 # y1 # 1 # 1
2 (mod n)
Hence we try to factor n:
gcd(y2 ” 1, n) = gcd(208 ” 1, n) = gcd(207, 437) = 23
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
Where are we?
Computing !(n) is no easier than factoring
Knowing a enables you to factor n
But this does not rule out the possibility 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
Where are we?
Computing !(n) is no easier than factoring
Knowing a enables you to factor n
But this does not rule out the possibility that
breaking RSA is easier than factoring
We study factoring so we can select appropriate
parameters for RSA
We can’t study the modern factoring algorithms in
this course, they are far too complicated!
We will look at an ancestor
Public-key cryptography
The RSA cryptosystem
RSA and factoring
Factoring
Overview
Modern factoring algorithms
Factoring with congruent squares
Given a we may factor n