[Cryptography] RSA equivalent key length/strength

[Manuel Pégourié-Gonnard]

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.