Cryptography Reference
In-Depth Information
A ( x ) x l
deg( B ( x ))
=
d B
b and define C ( x )
=
+
B ( x ). In practice, one restricts to pairs
( A ( x ) ,B ( x )) such that gcd( A ( x ) ,B ( x ))
=
1. The crucial observation is that
C ( x ) 2 k
A ( x 2 k )
( x 2 k ) l
B ( x 2 k )
A ( x 2 k ) x 2 k l n F 1 ( x )
B ( x 2 k )(mod F ( x )) . (15.9)
=
·
+
+
Write D ( x ) for the right-hand side of equation ( 15.9 ). We have deg( C ( x ))
max
{
d A +
n 2 / 3 log( n ) 1 / 3
2 k d A +
(2 k l
l,d B }≈
l
and
deg( D ( x ))
max
{
n )
+
deg( F 1 ( x )) ,
2 k d B }≈
2 k b
n 2 / 3 log( n ) 1 / 3 .
x 9
x 7
x 6
x 3
Example 15.5.19 (Thom´e[ 546 ]) Let n
=
607 and F 1 ( x )
=
+
+
+
+
x
+
1.
28, 2 k
Let b
=
23, d A =
21 ,d B =
=
4, l
=
152. The degrees of C ( x ) and D ( x ) are 173
and 112 respectively.
n 2 / 3
We have two polynomials C ( x ) ,D ( x )ofdegree
that we wish to be b -smooth
n 1 / 3 log( n ) 2 / 3 . We will sketch the complexity later under the heuristic assumption
that, from the point of view of smoothness, these polynomials are independent. We will
also assume that the resulting relations are essentially random (and so with high probability
there is a non-trivial linear dependence once #
where b
1 relations have been collected).
Having generated enough relations among elements of the factor base, it is necessary
to find some relations involving the elements g and h of the DLP instance. This is not
trivial. All DLP algorithms having complexity L q (1 / 3 ,c
B +
o (1)) feature a process called
special q -descent that achieves this. The first step is to express g (respectively, h )asa
product i G i ( x ) of polynomials of degree at most b 1 =
+
n 2 / 3 log( n ) 1 / 3 ; this can be done
by multiplying g (respectively, h ) by random combinations of elements of
and factoring
(one can also apply the Blake et al. trick as in Exercise 15.5.10 ). We now have a list of
around 2 n 1 / 3 <n polynomials G i ( x )ofdegree
B
n 2 / 3 that need to be “smoothed” further.
Section VII of [ 130 ] gives a method to do this: essentially one performs the same sieving
as earlier except that A ( x ) and B ( x ) are chosen so that G i ( x )
B ( x ) (not
necessarily with the same value of l or the same degrees for A ( x ) and B ( x )). Defining
D ( x )
|
C ( x )
=
A ( x ) x l
+
C ( x ) 2 k (mod F ( x )) (not necessarily the same value of k as before) one hopes that
C ( x ) /G ( x ) and D ( x )are b -smooth. After sufficiently many trials, one has a relation that
expresses G i ( x ) in terms of elements of
=
. Repeating for the polynomially many values
G i ( x ) one eventually has the values g and h expressed in terms of elements of
B
. One can
then do linear algebra modulo the order of g to find integers Z 1 ,Z 2 such that g Z 1 h Z 2
B
=
1
and the DLP is solved.
Example 15.5.20 We give an example of Coppersmith's method for
F 2 15
= F 2 [ x ] / ( F ( x ))
x 15
F 2 15 of order r
where F ( x )
=
+
x
+
1. We consider the subgroup of
=
151 (note that
(2 15
x 11
x 7
x 5
x 2
x 14
x 11
x 10
1) /r
=
7
·
31
=
217). Let g
=
+
+
+
+
1 and h
=
+
+
+
x 9
+
1 be the DLP instance.
First, note that n 1 / 3
2 . 5 and n 2 / 3
1 ,x 2
6 . 1. We choose b
=
3 and so
B ={
x,x
+
+
1 ,x 3
1 ,x 3
x 2
x
+
+
x
+
+
+
1
}
. We hope to be testing polynomials of degree around 6 to
8 for smoothness.
Search WWH ::




Custom Search