Reading notes Extending Wiener's Attack in the Presence of Many Decrypting Exponents

introduction

the purpose of this paper is given only several public exponents for a given modulus and the know-ledge of the corresponding private being quiet small.

Low Private Exponent Attacks on RSA

Wiener’s Approach

The Wiener’s Attack in this paper not the same as I had learnt before.

Let then we have

Dividing both side of equation (1) by

Because and , we have , hence

Then we need to quote an important conclusion:

if

then is a continued fraction approximant of

so if

then will be a continued fraction approximant of

Condition can convert to gm

and g will be small under the assumption that (but since p,q is odd)
when we get , we can factor N so that break the RSA cryptosystem.

Guo’s Approach

This approach assumes that one has more than one for a given N, and each of these has a relatively small .

For 2 encryption exponents, we have following relations:

Multiplying the first by and the second by , and Subtraction of two formulas gives

Dividing both sides of equation 3 by

and assuming that the are at most , so the right-hand side is about
if we want the fraction could be a continued fraction approximant of , we must have

and with the assumption that and are at most and the g is small this condition will be true where with

But known the and can not break the RSA cryptosystem for two reason.
The solution is omitted here ….

Overview of our Extension Approach

This approach also assumes that we have more than one and each of these has a relatively small and the bounds of is:

The can as large as where

For some reason , the attack is only practical for small (the number of , not the modulus ).

An Extension in the Presence of Many Small Decryption Exponents

Preliminaries

Let us refer to the relations of the form

we shall also assume, for a given , that the and are at most , the is very small, the is about

RSA in the presence of 2 Small Decryption Exponents

If we have two small decryption exponents,then the following relations hold: or more explicitly: (这部分英文没看懂, 把原句抄下来了)

Multiplying the first by , we may write these equations in the matrix form below.

The sizes of the entries of the vectors on the right-hand side are at most respectively

Multiplying the first three columns of the matrix by respectively, which gives following matrix:

In this case the vector will be such that

if the Lattice is pretty “random” , there are almost no lattice points of shorter than the Minkowski bounds . Under this assumptions, then is the shortest point in , if

for some small , which is true if

So, if, the vector can be found via Lattice basis reduction algorithms(e.g. LLL), so that we can calculate . Then we can factor N via wiener’s approach.

RSA in the presence of 3 Small Decryption Exponents

Just like the last section(RSA in the presence of 2 Small Decryption Exponents), the Lattice is:

where is:

RSA in the presence of 4 Small Decryption Exponents

The matrix is too big…..