# 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/

.

**Follow-Ups**:**Re: Diffie-Hellman key exchange***From:*Bryan

**References**:**Diffie-Hellman key exchange***From:*stevenvh

**Re: Diffie-Hellman key exchange***From:*Scott Fluhrer

**Re: Diffie-Hellman key exchange***From:*Ertugrul Söylemez

**Re: Diffie-Hellman key exchange***From:*Bryan

- Prev by Date:
**gem of a paper** - Next by Date:
**Re: A Modern Reappraisal of the One-Time Pad Cipher.** - Previous by thread:
**Re: Diffie-Hellman key exchange** - Next by thread:
**Re: Diffie-Hellman key exchange** - Index(es):