such that ord(g) ~= p), and it might yield less security at
the same efficiency level as when using smaller subgroup (e.g.
ord(g) << p).
The paper by van Oorschot and Wiener does not claim that the problem
with using exponents e << ord(g) to be as strong as e ~= ord(g), in
fact they seem to suggest otherwise.
However, as the draft indicates you suggest using exponent ~= p. Thus
you may lose in efficiency, but also this nullifies the point of my
previous message.
The practical benefits of fixing p to a safe prime might overweight
any (very) theoretical problems.
Best regards,
Mika Kojo
SSH Communications Security Corp
Niels Provos writes:
> In message <200006061728.UAA00391@torni.hel.fi.ssh.com>, Mika Kojo writes:
> >Let F_q denote the usual finite field of q elements. Then we want to
> >apply Diffie-Hellman over its multiplicative group. If q = p, and g
> >\in F_p, we have g^ord(g) == 1 (in F_p^*), that is, ord(g) | p -
> >1. Yet the proposal requires that ord(g) = (p-1)/2, and ord(g) to be
> >prime.
> The draft actually allows the server to use both type of generators.
> It can either be for the whole multiplicative group GF(p) with
> ord(g) = p-1, or for a subgroup of GF(p) with ord(g) = (p-1)/2 and
> ord(g) prime. This is because the draft only allows safe primes.
>
> >In Diffie-Hellman, one is interested in computation of g^e (in F_p^*)
> >for e \in (1, c < ord(g)). In practice we usually select c << ord(g) =
> >(p-1)/2, for performance purposes. And indeed there seems to be no
> >known attack which can utilize this iff log c >= B (where B is a
> >security bound for square root attacks) and log p >= I (where I is a
> >security bound for Index calculus). We have B << I for all reasonable
> >selections of p.
> The cited paper and the security considerations talk about short
> exponents:
>
> [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement
> with short exponents, In Advances in Cryptology - EUROCRYPT'96,
> LNCS 1070, Springer-Verlag, 1996, pp.332-343.
>
> >My current opinion (until someone proves me wrong, or too paranoid) is
> >that there should be a possibility for negotiating also ord(g). This
> This doesnt really make sense since there are only two possible orders,
> either p-1 or (p-1)/2, which are about the size of p. However, if
> you have wording that explains this issue better, I'd be happy to
> include it in a future version of the draft.
>
> Greetings,
> Niels.
From owner-ietf-ssh@clinet.fi Wed Jun 7 19:12:23 2000
Return-Path: