[Ksummit-discuss] [TECH TOPIC] Firmware signing

James Bottomley James.Bottomley at HansenPartnership.com
Thu Aug 13 14:01:09 UTC 2015


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 at 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




More information about the Ksummit-discuss mailing list