[Cryptography] New attacks on discrete logs?

[Hanno Böck]

On Fri, 23 May 2014 14:03:01 -0700
Bear <bear at sonic.net> wrote:

> On Thu, 2014-05-22 at 11:14 +0200, Hanno Böck wrote:
> 
> > Okay, to clear this up:
> > There's been an algorithm improvement on discrete logs in so-called
> > finite fields with small characteristics. However, it's not that
> > "new", it's from early 2013, it just has been presented at the
> > eurocrypt conference recently.
> 
> Would anyone like to clarify what exactly they mean by 
> "small" and "large" characteristic here?  Please?

This involves some math, I hope I got everything correct and no
mathematician will beat me for this:

Finite fields are mathematical structures where you can do certain
calculations with certain rules involving addition and multiplication.

Finite fields exist with a number of elements if that number is
[a prime]^[some number]

So you can e.g. have a finite field with 5 elements (because 5 is
prime) or with 2^4=16 elements (because 2 is a prime).

Finite fields with large characteristics means finite fields with a
large prime as the number of elements.

Finite fields with small characteristics means finite fields with a
small prime to the power of a large number of elements.

E.g. a diffie hellman key exchange works like this:
Choose a large prime p and a small number g
A calculates g^a mod p and sends it to B
B calculates g^b mod p and sends it to A
A calculates g^b^a mod p, B calculates g^a^b, both have a shared secret.

Our finite field here is the finite field with p elements, which is
everything calculated mod p. As p is a large prime it's a finite field
with large characteristics.

You could also use not a prime but e.g. 2^[large number] or 3^[large
number]. But that's no good idea, because that'd be insecure according
to this new algorithm.

-- 
Hanno Böck
http://hboeck.de/

mail/jabber: hanno at hboeck.de
GPG: BBB51E42
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140523/162c218c/attachment.pgp>