Re: [Ksummit-discuss] [TECH TOPIC] Firmware signing

[James Bottomley <James.Bottomley@HansenPartnership.com>]

On Thu, 2015-08-13 at 09:03 +0200, Jan Kara wrote:
> On Wed 12-08-15 12:59:51, James Bottomley wrote:
> > On Wed, 2015-08-12 at 12:45 -0700, Andy Lutomirski wrote:
> > > On Wed, Aug 12, 2015 at 12:43 PM, James Bottomley
> > > <James.Bottomley@hansenpartnership.com> wrote:
> > > > On Wed, 2015-08-12 at 12:25 -0700, Andy Lutomirski wrote:
> > > >> All that's moot, though.  IMO the only reason we should support RSA
> > > >> here is if there are vendor keys already out there (or Authenticode,
> > > >> sigh) that use RSA.  RSA keys and signatures are rather large.
> > > >
> > > > In either case security rests on the discrete log problem.
> > > 
> > > RSA is based on factoring, not discrete log.
> > 
> > Security is based on the discrete log:  RSA relates the private to the
> > public key via an inverse operation:  if you can solve the discrete log
> > problem, you can recover the private key from just the public key.  If
> > you can factor n in RSA, you can also recover the public key.  It is a
> > theorem that these two problems are effectively equivalent.
> 
> As the reference Andy gave explains, it depends on the exact definition of
> the "discrete log problem". Discrete log operation can be defined for
> arbitrary group. Knowing how to solve discrete log problem for some groups
> (e.g. for Z_p where p is a prime) doesn't easily give you a way to infer
> private RSA key from a public one. If you can solve discrete log for
> Z_{p*q}, then yes, you can break RSA as well.

The conjecture is that the discrete log problem is solved for a prime
ring. (Solved means algorithmically feasible with current computers and
ring sizes).  The ring used for RSA, as you point out is p*q, which is
actually a composite Z_p \otimes Z_q  (RSA chooses p and q to be
similarly sized).  All the currently known algorithms are exponential
(or worse) in the ring order (well, except Shor's algorithm which
depends on the invention of a quantum computer; Shor's algorithm, by the
way, is polynomial in log order, so the size of the ring becomes a lot
less material, which is why the invention of a quantum computer signals
a disaster in all our current security systems).

It's possible there's an undiscovered classical algorithm that only
works for primes with certain characteristics, but that's speculation.

James