# Re: Diffie-Hellman key exchange

• From: Ertugrul Söylemez <es@xxxxxxxx>
• Date: Thu, 13 May 2010 06:33:38 +0200

ggr@xxxxxxxxxxxxx (Greg Rose) wrote:

In article <d5be07db-9929-4c15-8415-f0185fea33bd@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Bryan <bryanjugglercryptographer@xxxxxxxxx> wrote:
Ertugrul Söylemez wrote:
In general, it's considered best to pick the largest subgroup.

No, currently practice is to pick a base that generates a subgroup
of large prime order. When the modulus is safe prime 'p',
cryptographers tend to choose a base that generates a subgroup of
prime order q=(p-1)/ 2. That said, I don't know of any security
problem with your advice to pick a safe prime and a generator of the
entire group.

I guess it depends what you want to do with the answer, and I don't
think the OP actually said. If it is for Diffie-Hellman, though, there
is a reason to prefer using the prime-order subgroup. Note that it's
straightforward to figure out which subgroups a group element is in,
and that for a safe prime the order q subgroup is exactly elements
that are squares. Suppose you use a generator of the entire group, in
general. Alice intentionally chooses a square, and does D-H with
Bob. Now if the result of the D-H is a square, Alice knows that Bob
chose a square too; otherwise he didn't. This is one bit of
information that Alice shouldn't have, and can't be concealed. Worse,
if the D-H is in the clear, anyone can tell that one bit of
information about both Alice and Bob's choices.

[...]

Basically, it's always safest to use the
large-prime-order subgroup in this and most other
contexts.

I already noted that a modulus of b bits gives a strength of b - 1 bits
effectively, so I took that into account. You lose that bit, no matter
what you do. If you use the prime order subgroup, you reach only half
of all elements. If you use the full group, the above attack is
applicable.

Greets,
Ertugrul

--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/

.