[147461] in cryptography@c2.net mail archive
Re: [Cryptography] RSA equivalent key length/strength
daemon@ATHENA.MIT.EDU (=?ISO-8859-1?Q?Manuel_P=E9gouri=E9)
Wed Oct 2 11:04:50 2013
X-Original-To: cryptography@metzdowd.com
Date: Wed, 02 Oct 2013 16:22:36 +0200
From: =?ISO-8859-1?Q?Manuel_P=E9gouri=E9-Gonnard?= <mpg@elzevir.fr>
To: Peter Fairbrother <zenadsl6186@zen.co.uk>
In-Reply-To: <524B08BF.8090402@zen.co.uk>
Cc: =?ISO-8859-1?Q?Kristian_Gj=F8steen?= <kristian.gjosteen@math.ntnu.no>,
Cryptography Mailing List <cryptography@metzdowd.com>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
Hi,
On 01/10/2013 19:39, Peter Fairbrother wrote:
> Also, the method by which the generators (and thus the actual groups in
> use, not the curves) were chosen is unclear.
>
If we're talking about the NIST curves over prime fields, they all have cofactor
1, so the actual group used is E(F_p), the (cyclic) group of all rational points
over F_p: there is no choice to be made here. Now, for the curves over binary
fields, the cofactor is 2 or 4, which again means the curve only has one
subgroup of large prime order. No room for choice either.
On another front, the choice of the generator in a particular group is of no
importance to the security of the discrete log problem. For example, assume you
know how to efficiently compute discrete logs with respect to some generator
G_1, and let me explain how you can use that to efficiently compute discrete
logs with respect to another base G_2.
First, you compute the n_21 such that G_2 = n_21 G_1, that is the discrete log
of G_2 in base G_1. Then you compute n_12, the modular inverse of n_21 modulo r,
the order of the group (which is known), so that G_1 = n_12 G_2. Now given a
random point P of which you want the log with base G_2, you first compute l_1,
its log in base G_1, that is P = l_1 G_1 = l_1 n_12 G_2, and tadam, l_1 n_12
(modulo r if you want) is the desired log in base G_2.
(The last two paragraphs actually hold for any cyclic group, though I wrote them
additively with elliptic curves in mind.)
So, really the only relevant unexplained parameters are the seeds to the
pseudo-random algorithm.
Manuel.
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
