[Cfrg] How rigid is rigid enough?
David Leon Gil <coruus@gmail.com> Thu, 08 January 2015 06:49 UTC
Return-Path: <coruus@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 87B0B1A885A for <cfrg@ietfa.amsl.com>; Wed, 7 Jan 2015 22:49:40 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.7
X-Spam-Level:
X-Spam-Status: No, score=0.7 tagged_above=-999 required=5 tests=[BAYES_50=0.8, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id X_jebuokFYbL for <cfrg@ietfa.amsl.com>; Wed, 7 Jan 2015 22:49:38 -0800 (PST)
Received: from mail-ie0-x22a.google.com (mail-ie0-x22a.google.com [IPv6:2607:f8b0:4001:c03::22a]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2FF201A887B for <cfrg@irtf.org>; Wed, 7 Jan 2015 22:49:38 -0800 (PST)
Received: by mail-ie0-f170.google.com with SMTP id rd18so8043058iec.1 for <cfrg@irtf.org>; Wed, 07 Jan 2015 22:49:37 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:from:date:message-id:subject:to:content-type; bh=Z3E02v7EAKGynLXguMLI6wHx2jeV5Twv/RnlzieHHOo=; b=nS0K57aWjVJ9hjFLkeDKUgTuuAVXWwcWdOSP/4Bawwqp0tg9ja63l/0p57wyRLmajf plgohburdgsRkeyfuHeNhunIkw3XRaxoC7ytDkzN5SrRWlSKfAcTPKV1HN7hjCcelFW9 GJZCTYuqbdrodQhtIaOFoiADHj2Um14xatzCCZp+zI7j1t+9eqRpETCKGA8fWFpsiHQF KnO5Geoq95cbK2MmEFr9bSnT2zX/a4Qh2IRHr/ED9O3n7uFOsxDRFT9mGQBBBVRE2qyS rVg3KBuzuupdkyNfnZInj1dc+4xXYT5OgFFEqy0LwWDyI3hG0dcY+CSEniC6YZikljzi 02JQ==
X-Received: by 10.50.117.68 with SMTP id kc4mr26446695igb.25.1420699777270; Wed, 07 Jan 2015 22:49:37 -0800 (PST)
MIME-Version: 1.0
Received: by 10.107.132.211 with HTTP; Wed, 7 Jan 2015 22:49:16 -0800 (PST)
From: David Leon Gil <coruus@gmail.com>
Date: Wed, 07 Jan 2015 22:49:16 -0800
Message-ID: <CAA7UWsVi+TszTYxKd4KSGYNryV24Bq+0FpxN2GO5LWA5khdqjg@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/LQIyeCFGgoROzsx_UBf9cjlsS-A
Subject: [Cfrg] How rigid is rigid enough?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Thu, 08 Jan 2015 06:49:40 -0000
# How rigid are rigid curves? (About 138 reasonable choices of curve for the range 2^300 to 2^521.) ## Rigid fast primes in the range 2^300 to 2^521 Mersennes: 2^521 - 1 == 3 mod 4 M521 (Granger-Scott have presented a fast algorithm for platforms where the number of limbs is too small for FFT-based multiplication to be efficient.) A minimal Crandall is a prime of the form: 2^n - c, !E c' < c : is_prime(2^n - c) Crandalls are fast when log2(c) <<< limb_bits. If we want a Crandall that's fast on any platform, this effectively restricts us to c < 32. (LCD platform: JavaScript, where bignums typically use 12/24 limbs.) Crandalls: 2-bit: 2^336 - 3 == 1 mod 4 2^452 - 3 == 1 mod 4 C452 (???) 4-bit: 2^321 - 9 == 3 mod 4 2^322 - 11 == 1 mod 4 2^338 - 15 == 1 mod 4 5-bit: 2^414 - 17 == 3 mod 4 C414 (djb) 2^444 - 17 == 3 mod 4 2^468 - 17 == 3 mod 4 2^488 - 17 == 3 mod 4 2^379 - 19 == 1 mod 4 2^389 - 21 == 3 mod 4 C389 (rr?) 2^413 - 21 == 3 mod 4 2^489 - 21 == 3 mod 4 2^324 - 23 == 1 mod 4 2^369 - 25 == 3 mod 4 C369 (???) 2^383 - 31 == 1 mod 4 C383 (NUMS) 2^401 - 31 == 1 mod 4 2^495 - 31 == 1 mod 4 Define an `m`-splitting `Ridinghood` as a prime of the form: 2^n - 2^(n/2) - 1, n|2 /\ (n/2)|2^m There is at most one Ridinghood per `n`. (And these are, in fact, extremely rare primes.) (Michael Hamburg has described how multiplication modulo these primes can take advantage of their Karatsuba-friendly shape.) Ridinghoods: 5-splitting: 2^448 - 2^224 - 1 == 3 mod 4 R448 (mh) 4-splitting: 2^480 - 2^240 - 1 == 3 mod 4 R480 (mh) 2^416 - 2^208 - 1 == 3 mod 4 1-splitting: 2^322 - 2^161 - 1 == 3 mod 4 2^450 - 2^225 - 1 == 3 mod 4 So, in total: 22 plausible fast primes. (There are really fewer than this, even; some of these are not sufficiently larger than 2^255-19 to be interesting.) ## Minimal-cost curve parameters and corresponding basepoints Minimal curve parameters. Let `c(x)` be a cost function, and choose the value of a free parameter `x` such that there does not exist another `x' != x` with `c(x') <= c(x)`. Safe curves. Set `c(x) == \inf` if `#E/h` and `#Et/ht` are not prime, or if some set of safety criteria are not satisfied. (Insert SafeCurves criteria here.) Choosing basepoints. Choose the unique point of order `#E/h` whose single-coordinate representation in the chosen curve model is minimal in value. Choosing curve parameters. Suppose that we want an Edwards curve; so we have a cofactor != 1. Choose the cofactor to be minimal consistent with safety. Then: q == 1 mod 4: h = 8, ht = 4 q == 3 mod 4: h = 4, ht = 4 Curve form and parameter, *x*: - Proposed: BLE form, a=-1: d BLE form, a=+1: d Montgomery form: A - Possible: Weierstrass, a=-3: b - For mathematicians, mainly: Legendre form: lambda j-invariant Cost functions, *c(x)*: - Proposed: min(x) min(abs(x)) - Possible: min( (hamming(x), x) ) Am I missing any plausible proposals? This gives 6 proposed methods of choosing Edwards curves. Several of these are always equivalent up to isogeny, but for the choice of basepoint. # How rigid is rigid enough? One way we might answer this is by asking whether there are any cryptographically interesting properties of curves that we know of that occur with probability on the order of 1/132. There's at least one, now historical, example: Only about 1/50 prime-order Weierstrass curves at this bitlength is twist-secure. (See, e.g., traces for the prime Salinas384; available at https://github.com/coruus/sally) (Or, had CFRG then been in the business of choosing curves, there would have been -- assuming that the CFRG process is an effective means of selecting a curve uniformly at random -- a < 0.2% chance of getting P384 right.) So...is rigidity good? Yes. Do we know that a "rigid" choice is, in fact, rigid enough to prevent an adversary from selecting a curve with a chosen, cryptographically interesting property? . . . . ? Perhaps we can now hope -- with all of our problems for the moment solved -- for an end to the rigider-than-thou holy wars, and a return to collaborating to make ECC safer. - dlg
- [Cfrg] How rigid is rigid enough? David Leon Gil
- Re: [Cfrg] How rigid is rigid enough? David Leon Gil