# Why are the random exponents so much bigger in the Socialist Millionaire protocol versus Diffie-Hellman key exchange?

Section 8, Security considerations, of RFC3526, which defines groups used for Diffie-Hellman has a table recommending some random exponent sizes. In particular, it says:

• The strength of a key exchanged using the 1536 bit group has
• about 90 bits strength for a 180 bit random exponent
• about 120 bits of strength for a 240 bit random exponent

On the other hand, the Off-the-Record protocol spec, which uses that 1536 bit DH group, says:

The random exponents are 1536-bit numbers.

I'm not adhering to the OTR spec, because I'm just using the SMP part of it. But I'm interested to find out:

What is the reason to use these comparatively huge random exponents, when a DH key exchange gets what I would call "enough" strength at far lower exponent sizes? I'm interested because 240 bit random numbers make the authentication go a lot quicker.

As a bonus: how does SMP using the 2048, or 4096 bit groups with smaller random exponents compare to using the 1536 bit group with large random exponents?

-

• we work modulo a prime $p$ big enough to resist discrete logarithm (1536 bits are sufficient);
• the order of the subgroup generated by $g$ is a multiple of a big-enough prime integer $q$ ($q$ should have length $2n$ bits to achieve $2^n$ security);
• the private exponents are randomly chosen in a big enough range ($2n$-bit exponents to reach $2^n$ security).
The first two conditions are necessary for the discrete logarithm to be hard. But having hard discrete logarithm is not necessarily sufficient for the security of the cryptographic algorithm which uses that group. Diffie-Hellman appears to be reasonably secure with the conditions above. However, other protocols require a bit more. A prime example is DSA. With DSA, you work in a subgroup of size $q$ (a prime integer) generated by a conventional value $g$ modulo a big prime $p$; whenever you sign, you select a random $k$ modulo $q$ (that's a "secret exponent"). $k$ must be chosen uniformly in the $[1...q-1)]$ range; simply choosing a "big enough" $k$ is not sufficient: any bias in the selection of $k$ can be exploited to rebuild the private key from the observation of several signatures (many signatures, if the bias is slight).