[crypto] Cracking di Xevron

Per far passare tranquille vacanze pasquali a tutti coloro che col fiato
sospeso attendevano che io o Teo facessimo i conticini... un americano
li ha fatti per noi ;)

La dimostrazione e' di Daniel Bleichenbacher, e a una prima lettura fila
alquanto.

---------

Not sure, what you tried, but LLL works well here.
I.e. we need to find x,y, such that
x*sh  == midA * M  + z (mod N),
where in the example above M = 10^11 and N = 10^67

First you generate a basis for all solutions (x,y,z) for
x*sh  == y*midA*M + z (mod N)
E.g.  we get the following matrix (using column vectors)

 |1          0           0|
 |0          1           0|
 |sh    -midA*M    N|

The target column vector we want to find is (idA , 1, idA*sh-midA*M)
is a
linear combination of
the column vectors of the matrix.
Next we multipy the rows of this matrix by 1, N/M and N/M^2.
This gives the matrix

| 1                       0                      0 |
| 0                     N/M                    0 |
| sh*N/M^2    -midA*N/M     N^2/M^2 |

Now (idA, N/M, (idA*sh-midA*M)*N/M^2) is a linear combination of the
column vectors of this matrix.
Moreover, we can hope it is the shortest one.
Thus we may try to find it using LLL.
That is indeed what I tried with Pari, and Pari had no problem finding
idA (and also idB) in the example given above.

> I keep thinking that continued fraction convergents might also point
> to a solution - have you considered that at all?

Continued fraction works too.
Again we try to find a solution to
x*sh == midA*M + z (mod N).
Use Euclid to find sh == u*v^(-1) (mod N) where u is approx M.
Hence v should be no larger than N/M.
Thus
x*u == midA*M*v + z*v (mod N).
Since x*u and z*v are both smaller than N we know that
x*u - z*v = (midA*M*v) + delta *N
where delta = 0 or 1.
Thus we can in fact guess x*u - z*v.
Let R=x*u-z*v.
Next we can compute x (mod v) by x==R*u^(-1) (mod v).
If everything went well then x should be idA.
However, I haven't tried this in an experiment yet.

--------

Tralascero' ogni commento sul fatto che questo fosse prevedibile, e in
effetti sia piu' o meno la cosa che indicava Teo (o almeno, quella che
ho capito io dalla mail di Teo, non oserei mai essere esegeta del
Maestro ;-)

-- 
Cordiali saluti,
Stefano Zanero

Politecnico di Milano - Dip. Elettronica e Informazione
Via Ponzio, 34/5 I-20133 Milano - ITALY
Tel.    +39 02 2399-4010
Fax.    +39 02 2399-3411
E-mail: zanero@xxxxxxxxxxxxxx
Web:    www.elet.polimi.it/upload/zanero