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

[Jan Kara <jack@suse.cz>]

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.

								Honza
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR