Re: Requesting some help

David Wagner <daw@xxxxxxxxxxxxxxxxxxxxxxxx>:
Kristian Gjøsteen wrote:
David Wagner <daw-usenet@xxxxxxxxxxxxxxxxxxxxxxxx> wrote:

I don't follow. I thought your original attack was valid. The attack
doesn't need to know phi(n); the matrix inversion is over the integers.

I always thought this attack would work, so I was confused when I could
not explain to myself why it worked. I guess I am missing a trick
here. Why should the matrix be invertible over the integers?

To be more precise, it only has to be invertible modulo e, where e
is the public modulus.

I guess you mean "public exponent", but actually it isn't about
invertibility modulo e or modulo n. Invertibility modulo phi(n)
went into the right direction, we just luckily don't *need* to know
phi(n) (if we knew it, this way of attack would be pointless).

Let me repeat Kristian's attack sketch:

(find enough smooth hashes
to get the RSA-decryptions of smooth primes, then you can fake signatures
of new smooth hashes;

"Smooth primes" here means small primes below some smoothness bound, B.
We need the matrix step to obtain RSA decryptions of these primes
from the RSA decryptions of smooth hashes: Every smooth hash h_i is
a multiplicative linear combination h_i = \prod p_j^{e_ij} where
p_1, ..., p_b denotes the primes up to B. Applying column
transformations to the matrix (e_ij) corresponds to obtaining some
multiplicative linear combinations of the h_i, and this is where
we arrive at the issue of a matrix inversion (take up to b rows of the
matrix, keep the same number of columns of this; if you can invert
this quadratic matrix, then you know how to get a subset of p_1, ..., p_b
as multiplicative linear combinations of the h_i; thus, given the
e-th roots modulo n of the h_i, you similarly can compute the
roots of the p_j as linear combinations).

Since ultimately this is about computations mudulo n, you could
consider this is a matrix with elements modulo phi(n). Well,
in that case even a 1x1 matrix would usually be invertible, since you
can invert its only element modulo phi(n) unless it is zero or has a
common divisor with phi(n). But for this attack, we don't need any
modular reduction of the matrix elements -- considering the matrix as
a matrix of integers is fine. We can multiply modulo n, we can invert
modulo n, and that's all we need.
.

Relevant Pages

  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... What's the difference between primes in sequences and above? ... for those primes congruent 1 mod 3. ...
    (sci.math)
  • Re: Mod 2011
    ... and work in the ring of integers modulo q. ... The sequence always starts: ... What's the difference between primes in sequences and above? ... for those primes congruent 1 mod 3. ...
    (sci.math)
  • Re: About random, primes and statistics
    ... explain a simple area where mathematicians routinely ... modulo 3--perfect regularity: ... researchers as you have primes and you have ... composites and composites ...
    (sci.math)
  • Re: Quadratic residue method for finding primes
    ... Note that we know exactly which primes have 2 as a quadratic residue: ... those which are congruent to 1 or -1 modulo 8. ...
    (sci.crypt)
Loading