CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A family of algorithms
Basic idea
A framework for algorithms in this family
Dixon’s random squares
RSA security: all about factoring?
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Basic idea
Definition (B-Smooth)
x ! N is said to be B-smooth if all prime factors of x
are ” B.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Basic idea
Definition (B-Smooth)
x ! N is said to be B-smooth if all prime factors of x
are ” B.
We use a factor base, a set B of the primes below
some bound B.
We find a collection of z ! Z such that each z2
(mod n) is B-smooth.
We find a subset of the z2 (mod n) such that each
prime in the factor base is used an even number of
times.
This will give us a congruence of the type x2 # y2
(mod n) as required.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A contrived example
We have n = 1177 and select a factor base B = {2, 3}.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A contrived example
We have n = 1177 and select a factor base B = {2, 3}.
Select values for z, square and reduce modulo n then
try to factor over the factor base:
352 # 48 # 24 $ 3 (mod 1177)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A contrived example
We have n = 1177 and select a factor base B = {2, 3}.
Select values for z, square and reduce modulo n then
try to factor over the factor base:
352 # 48 # 24 $ 3 (mod 1177)
362 # 119 (mod 1177)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A contrived example
We have n = 1177 and select a factor base B = {2, 3}.
Select values for z, square and reduce modulo n then
try to factor over the factor base:
352 # 48 # 24 $ 3 (mod 1177)
362 # 119 (mod 1177)
372 # 192 # 26 $ 3 (mod 1177)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A contrived example
We have n = 1177 and select a factor base B = {2, 3}.
Select values for z, square and reduce modulo n then
try to factor over the factor base:
352 # 48 # 24 $ 3 (mod 1177)
362 # 119 (mod 1177)
372 # 192 # 26 $ 3 (mod 1177)
Now we need to find a subset of the z2 (mod n) such
that each prime in the factor base is used an even
number of times…
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A contrived example
We have n = 1177 and select a factor base B = {2, 3}.
Select values for z, square and reduce modulo n then
try to factor over the factor base:
352 # 48 # 24 $ 3 (mod 1177)
362 # 119 (mod 1177)
372 # 192 # 26 $ 3 (mod 1177)
Now we need to find a subset of the z2 (mod n) such
that each prime in the factor base is used an even
number of times… and use this to derive a congruence
x2 # y2 (mod n).
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A systematic approach
To make this into an algorithm we are missing two
things:
1 A way to select our “auxiliary” numbers z2 so that
they are likely to be B-smooth.
2 A way to produce a subset of the smooth z such
that we produce a square.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Finding dependencies
I already have a dependency but how could we spot this
systematically?
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Finding dependencies
I already have a dependency but how could we spot this
systematically?
1 Write each relation as a vector of exponents
2 Reduce the vectors modulo 2 and find a subset of
vectors which sum to the zero vector modulo 2.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Finding dependencies
I already have a dependency but how could we spot this
systematically?
1 Write each relation as a vector of exponents
2 Reduce the vectors modulo 2 and find a subset of
vectors which sum to the zero vector modulo 2.
Our vectors would be (4, 1) and (6, 1),
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Finding dependencies
I already have a dependency but how could we spot this
systematically?
1 Write each relation as a vector of exponents
2 Reduce the vectors modulo 2 and find a subset of
vectors which sum to the zero vector modulo 2.
Our vectors would be (4, 1) and (6, 1), reduced modulo
2 these are (0, 1) and (0, 1).
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Finding dependencies
I already have a dependency but how could we spot this
systematically?
1 Write each relation as a vector of exponents
2 Reduce the vectors modulo 2 and find a subset of
vectors which sum to the zero vector modulo 2.
Our vectors would be (4, 1) and (6, 1), reduced modulo
2 these are (0, 1) and (0, 1).
Working modulo 2: (0, 1) + (0, 1) = (0, 0)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
How do we use the dependency?
Recall that we are trying to find x2 # y2 (mod n).
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
How do we use the dependency?
Recall that we are trying to find x2 # y2 (mod n). The
vectors in the dependency tell us which relations to use
to make x and y.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
How do we use the dependency?
Recall that we are trying to find x2 # y2 (mod n). The
vectors in the dependency tell us which relations to use
to make x and y. We have that x = 35 $ 37 and
y = 25 $ 3 since
x2 # (35 $ 37)2 # 352 $ 372
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
How do we use the dependency?
Recall that we are trying to find x2 # y2 (mod n). The
vectors in the dependency tell us which relations to use
to make x and y. We have that x = 35 $ 37 and
y = 25 $ 3 since
x2 # (35 $ 37)2 # 352 $ 372
# (24 $ 3) $ (26 $ 3) # 210 $ 32
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
How do we use the dependency?
Recall that we are trying to find x2 # y2 (mod n). The
vectors in the dependency tell us which relations to use
to make x and y. We have that x = 35 $ 37 and
y = 25 $ 3 since
x2 # (35 $ 37)2 # 352 $ 372
# (24 $ 3) $ (26 $ 3) # 210 $ 32
# (25 $ 3)2 # y2 (mod n)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
How do we use the dependency?
Recall that we are trying to find x2 # y2 (mod n). The
vectors in the dependency tell us which relations to use
to make x and y. We have that x = 35 $ 37 and
y = 25 $ 3 since
x2 # (35 $ 37)2 # 352 $ 372
# (24 $ 3) $ (26 $ 3) # 210 $ 32
# (25 $ 3)2 # y2 (mod n)
x # 35 $ 37 # 118 (mod n), y # 96 (mod n) and
gcd(118 % 96, 1177) = 11
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A family of algorithms
Basic idea
A framework for algorithms in this family
Dixon’s random squares
RSA security: all about factoring?
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A framework for algorithms in this family
1 Select the factor base of primes p ” B.
2 Collect relations between elements of the
factor base producing squares
z2j #
!
p
vij
i (mod n) pi in the factor base
Write each relation as a vector
vj = (v1j , . . . , vij, . . .)
3 Find dependencies: reduce vj modulo 2 and use
linear algebra to find a dependency modulo 2. The
dependency will give us a subset S of relations
whose vectors added together produce a vector
with even coordinates, hence
!
j!S
z2j #
!
j!S
p
vij
i # y
2 (mod n)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A family of algorithms
Basic idea
A framework for algorithms in this family
Dixon’s random squares
RSA security: all about factoring?
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Dixon’s random squares
In Dixon’s random squares algorithm we simply
select z at random.
Although, it can be useful to look at integers of the
form j +
“&
kn
#
which tend to be small when
squared and reduced mod n
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A carefully selected example
Let n = 2041 and select the factor base to be
{2,3,5,7}.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A carefully selected example
Let n = 2041 and select the factor base to be
{2,3,5,7}. I need to collect 5 vectors and we consider
the numbers (j = 0): j + ‘
&
n( = 46, 47, 48, . . .:
462 # 75 # 3 $ 52 (mod 2041)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A carefully selected example
Let n = 2041 and select the factor base to be
{2,3,5,7}. I need to collect 5 vectors and we consider
the numbers (j = 0): j + ‘
&
n( = 46, 47, 48, . . .:
462 # 75 # 3 $ 52 (mod 2041)
472 # 168 # 23 $ 3 $ 7 (mod 2041)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A carefully selected example
Let n = 2041 and select the factor base to be
{2,3,5,7}. I need to collect 5 vectors and we consider
the numbers (j = 0): j + ‘
&
n( = 46, 47, 48, . . .:
462 # 75 # 3 $ 52 (mod 2041)
472 # 168 # 23 $ 3 $ 7 (mod 2041)
492 # 360 # 23 $ 32 $ 5 (mod 2041)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A carefully selected example
Let n = 2041 and select the factor base to be
{2,3,5,7}. I need to collect 5 vectors and we consider
the numbers (j = 0): j + ‘
&
n( = 46, 47, 48, . . .:
462 # 75 # 3 $ 52 (mod 2041)
472 # 168 # 23 $ 3 $ 7 (mod 2041)
492 # 360 # 23 $ 32 $ 5 (mod 2041)
512 # 560 # 24 $ 5 $ 7 (mod 2041)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
A carefully selected example
Let n = 2041 and select the factor base to be
{2,3,5,7}. I need to collect 5 vectors and we consider
the numbers (j = 0): j + ‘
&
n( = 46, 47, 48, . . .:
462 # 75 # 3 $ 52 (mod 2041)
472 # 168 # 23 $ 3 $ 7 (mod 2041)
492 # 360 # 23 $ 32 $ 5 (mod 2041)
512 # 560 # 24 $ 5 $ 7 (mod 2041)
532 # 768 # 28 $ 3 (mod 2041)
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
Define !(x, B) to be the numbers less than x
which are B-smooth.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
Define !(x, B) to be the numbers less than x
which are B-smooth.
If the numbers we test are selected at random from
the set {1, .., x} then we need to test x|B|
!(x,B)
numbers.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
Define !(x, B) to be the numbers less than x
which are B-smooth.
If the numbers we test are selected at random from
the set {1, .., x} then we need to test x|B|
!(x,B)
numbers.
Checking if a number is B-smooth takes about |B|
steps by trial division.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
Define !(x, B) to be the numbers less than x
which are B-smooth.
If the numbers we test are selected at random from
the set {1, .., x} then we need to test x|B|
!(x,B)
numbers.
Checking if a number is B-smooth takes about |B|
steps by trial division.
Hence x|B|
2
!(x,B)
is the cost of finding the required
numbers.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
Define !(x, B) to be the numbers less than x
which are B-smooth.
If the numbers we test are selected at random from
the set {1, .., x} then we need to test x|B|
!(x,B)
numbers.
Checking if a number is B-smooth takes about |B|
steps by trial division.
Hence x|B|
2
!(x,B)
is the cost of finding the required
numbers.
In Dixon’s random squares we set x = n.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Counting the cost
B is our factor base. We need ) |B| B-smooth
numbers.
Define !(x, B) to be the numbers less than x
which are B-smooth.
If the numbers we test are selected at random from
the set {1, .., x} then we need to test x|B|
!(x,B)
numbers.
Checking if a number is B-smooth takes about |B|
steps by trial division.
Hence x|B|
2
!(x,B)
is the cost of finding the required
numbers.
In Dixon’s random squares we set x = n.
Dixon gave a heuristic argument that the expected
runtime of the algorithm is
O
$
e3
”
2 ln n ln ln n
%
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Modern algorithms in this family
Continued fraction method
Multiple polynomial quadratic sieve
Number field sieve
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Modern algorithms in this family
Continued fraction method
Multiple polynomial quadratic sieve
Number field sieve
The latter two use a mechanism called a sieve to speed
up the process of selecting “auxilliary” numbers z2
which are likely to be B-smooth.
CM30173:
Cryptography
Part IV
A family of
algorithms
Basic idea
A framework for
algorithms in this
family
Dixon’s random squares
RSA security: all
about factoring?
Further reading
I strongly recommend this paper for anyone even
remotely curious about the modern algorithms and for
some useful revision of what we have just covered. You
don’t have to finish it but do start it!
C. Pomerance. A tale of two sieves, Notices of the
AMS, 43:1473-1485, 1996.
Public-key cryptography
A family of algorithms
Basic idea
A framework for algorithms in this family
Dixon’s random squares
RSA security: all about factoring?