Why the size of a DH prime $p$ should be about 6800 bits long to force an attacker to perform $2^{128}$ steps to attack the system?

How is this relationship 6800-128 established?

  • 1
    $\begingroup$ Where did you find that number? Usually it's 3072 for a 128-bit security level. $\endgroup$ – SEJPM May 16 '19 at 15:00
  • $\begingroup$ books.google.com/… $\endgroup$ – user1156544 May 16 '19 at 15:14
  • 1
    $\begingroup$ The classic strategy to establish this is outlined in this paper (PDF) (it should roughly yield 3072 bit as well for 128-bit security). $\endgroup$ – SEJPM May 16 '19 at 18:33

How do we pick a group size for a 128-bit security level?

  1. Estimate the cost of mounting an attack as a function of the group size.
  2. Find the group size that puts that cost estimate above $2^{128}$.

In this case, for appropriately selected groups, without back doors, like the RFC 3526 groups, the best attack algorithm is the general number field sieve, GNFS. The usual (single-target) cost estimate for the GNFS is $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ where $L = e^{(\log p)^{1/3} (\log \log p)^{2/3}}$ and $p$ is the modulus. Where 6800 came from is unclear to me; the usual consensus is that 3072 is plenty for a 128-bit security level, even if the $\sqrt[3]{64/9}$ figure is optimistic. Of course, you can get much better performance, and much better implementation security, if you use X25519 instead.

| improve this answer | |
  • $\begingroup$ It is useful, though I am still unsure where the 6800 came from... $\endgroup$ – user1156544 May 17 '19 at 8:26
  • $\begingroup$ @user1156544 Sadly the book doesn't give any reference for that number, so there's probably no way of knowing short of contacting (one of) the authors and even then it's questionable whether they still remember... $\endgroup$ – SEJPM May 17 '19 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.