[curves] The Pareto frontiers of sleeveless primes
Mike Hamburg
mike at shiftleft.org
Sun Oct 26 23:57:26 PDT 2014
On 10/26/2014 2:15 PM, David Leon Gil wrote:
> # Introduction
>
> So. Motivated by prior posts by Michael Hamburg and Daniel Bernstein,
> I made up a list of "good primes" for ECC.
Wow, thanks for putting this together, David.
> ## Criteria for primes
>
> General criteria: 80 <= n = ceil(log2(p)) <= 1024.[^bitlen] The prime
> must be 3 mod 4, so that all Montgomery curves are isogenous to an
> untwisted Edwards curve. (Note: this criterion excludes 2^255-19,
> which is 1 mod 4.)
>
> I considered all ridinghood primes and all Crandall primes with c < 64
> in this range; there are 10 ridinghood primes and 52 Crandall primes
> with minimal c in this range.
>
> [^bitlen]: For regular ECC: need b >> 160; for hyperelliptic crypto:
> need b > 80; for some exotic stuff (using, e.g., large cofactors or
> constructed curves), the bitlengths > 521 may be of some use.
>
> (The choice of nail-length is debatable, of course, as well as
> considering Ridinghoods that require irrational/split radices
> relatively quickly.)
Right. In my try, I had calculated it by multiplication not requiring
internal carry propagation, which depends on c as well as nail length.
This can be computed by expanding the prime into polynomial P in the
radix, and comparing the largest coefficient of ((x^limbs - 1) /
(x-1))^2 mod P to 2^(2*wordsize - 2*radix - extra). Here extra is some
small amount (0.1) to account for not having reduced perfectly the first
time; + 1 if the polynomial is signed; + 2 if you want to be able to do
one add to each factor without reducing; +1 or 2 more (I don't remember)
if you want to be able to subtract and are using unsigned nails. But
just fixing it to 28 or 58 or 60 should be OK for an approximation.
I think the biggest difference is that Ed480-Ridinghood itself works
well with no carries on 64-bit, with 60-bit limbs.
> The (very messy) script I used to generate these results can be found
> at: https://gist.github.com/coruus/da494f6b77f65946332b
>
> -dlg
>
> # Results
>
> I calculated the Pareto frontiers[^pareto] for security strength
> versus three quantities:
>
> - number of nailed limbs, as ceil(n / 58)
> - number of quadwords in a compressed representation, ceil((n-3)/64)
> - number of bytes in a compressed representation, ceil((n-3)/8)
Why n-3?
> [^pareto]: Pareto frontier here means the hull of a two-dimensional
> cost function.
>
> ## Pareto frontier for strength versus number of 58-bit limbs
>
> Pareto frontier: n, #limbs=ceil(n/58)
>
> 2^114 - 2^57 - 1 #limbs= 2 len= 14
> 2^174 - 17 #limbs= 3 len= 22
> 2^226 - 5 #limbs= 4 len= 28
> 2^285 - 9 #limbs= 5 len= 36
> 2^336 - 17 #limbs= 6 len= 42
> 2^389 - 21 #limbs= 7 len= 49
> 2^450 - 2^225 - 1 #limbs= 8 len= 56
> 2^521 - 1 #limbs= 9 len= 65
> 2^563 - 9 #limbs=10 len= 70
> 2^607 - 1 #limbs=11 len= 76
> 2^664 - 17 #limbs=12 len= 83
> 2^729 - 9 #limbs=13 len= 91
> 2^810 - 5 #limbs=14 len=101
>
> These results lend support to djb's assertion that top performance is
> a fairly rigid criterion, taking the number of limbs as a rough proxy
> for performance.
>
> #limbs is obviously a very rough proxy; is there a decent generic
> formula for number of ops for Crandalls and Ridinghoods?
Depends on how much Karatsuba you want to do. The ridinghoods are
designed around at least 1 level of Karatsuba, costing (#limbs) adds,
3#limbs^2/4 wide multiplies with accumulation, possibly a few extra adds
for pipelining reasons, and #limbs+1 carry propagates.
Crandalls can be done with no Karatsuba, requiring #limbs^2 wide
multiplies with accumulation, #limbs narrow multiplies by c, and #limbs
carry propagation. But you can apply Karatsuba or Chung-Hasan or that
fancy irrational base transform suggested by Granger and Scott. I think
Karatsuba for example requires an extra #limbs adds and #limbs narrow
multiplies by c compared to a ridinghood.
This is all assuming an integer radix. Fractional radix requires some
extra doubles, which sometimes don't matter (eg, on NEON with VQDMLAL).
I don't have enough experience with fractional radix to say exactly how
many.
> ## Pareto frontier for strength versus quad-aligned length
>
> Pareto frontier: n, ceil((n-3) / 64)
> 2^130 - 5 #limbs= 3 qrlen= 16 len= 16
> 2^189 - 25 #limbs= 4 qrlen= 24 len= 24
> 2^251 - 9 #limbs= 5 qrlen= 32 len= 31
> 2^322 - 2^161 - 1 #limbs= 6 qrlen= 40 len= 40
> 2^369 - 25 #limbs= 7 qrlen= 48 len= 46
> 2^450 - 2^225 - 1 #limbs= 8 qrlen= 56 len= 56
> 2^489 - 21 #limbs= 9 qrlen= 64 len= 61
> 2^563 - 9 #limbs=10 qrlen= 72 len= 70
> 2^607 - 1 #limbs=11 qrlen= 80 len= 76
> 2^706 - 5 #limbs=13 qrlen= 88 len= 88
> 2^729 - 9 #limbs=13 qrlen= 96 len= 91
> 2^810 - 5 #limbs=14 qrlen=104 len=101
>
> The Pareto frontier for storing Edward curve keys, assuming a
> compressed representation, and an 8-byte alignment requirement.
>
> The ridinghood 2^450 - 2^225 - 1 comes out well here as well; I'm
> curious whether it is any slower than 2^448-2^224-1.
That's a good question. I haven't tried to implement it, largely
because I didn't want to deal with fractional radix, and because the
carry handling is already tight on 32 bits. Also, I liked the aligned
size. But it should work fine at least on 64-bit.
Cheers,
-- Mike
> ## Pareto frontier for strength versus length
>
> Pareto frontier: n, ceil((n-3)/8)
> 2^90 - 2^45 - 1 len= 11
> 2^96 - 17 len= 12
> 2^107 - 1 len= 13
> 2^114 - 2^57 - 1 len= 14
> 2^118 - 5 len= 15
> 2^130 - 5 len= 16
> 2^137 - 13 len= 17
> 2^141 - 9 len= 18
> 2^152 - 17 len= 19
> 2^166 - 5 len= 21
> 2^174 - 17 len= 22
> 2^189 - 25 len= 24
> 2^198 - 17 len= 25
> 2^206 - 5 len= 26
> 2^216 - 2^108 - 1 len= 27
> 2^226 - 5 len= 28
> 2^243 - 9 len= 30
> 2^251 - 9 len= 31
> 2^285 - 9 len= 36
> 2^322 - 2^161 - 1 len= 40
> 2^336 - 17 len= 42
> 2^369 - 25 len= 46
> 2^389 - 21 len= 49
> 2^416 - 2^208 - 1 len= 52
> 2^450 - 2^225 - 1 len= 56
> 2^468 - 17 len= 59
> 2^480 - 2^240 - 1 len= 60
> 2^489 - 21 len= 61
> 2^521 - 1 len= 65
> 2^537 - 9 len= 67
> 2^550 - 5 len= 69
> 2^563 - 9 len= 70
> 2^607 - 1 len= 76
> 2^664 - 17 len= 83
> 2^699 - 9 len= 87
> 2^706 - 5 len= 88
> 2^708 - 2^354 - 1 len= 89
> 2^717 - 25 len= 90
> 2^729 - 9 len= 91
> 2^810 - 5 len=101
>
> This is the Pareto frontier for Edwards curve key bytelengths,
> assuming a compressed representation, and no alignment requirement.
> (As, e.g., is common for internet protocols.)
>
> This obviously constrains choice of primes relatively little; still,
> there are only 40 good byte-lengths.
>
> ## Efficiency of used limbs, by byte-length
>
> And, finally, a list based on the efficiency with which 58-bit limbs
> are used for a given quadword-length:
>
> len: prime eff=(n/(ceil(n/58)*58), eff >= 0.9
> 2*8: 2^114 - 2^57 - 1 (0.98)
> 3*8: 2^174 - 17 (1.00)
> 4*8: 2^226 - 5 (0.97)
> 5*8: 2^285 - 9 (0.98)
> 6*8: 2^336 - 17 (0.97)
> 7*8: 2^450 - 2^225 - 1 (0.97)
> 8*8: 2^489 - 21 (0.94)
> 9*8: 2^521 - 1 (1.00)
>
> And bytelength:
>
> len: prime eff=(n/(ceil(n/58)*58), eff >= 0.9
> 13: 2^107 - 1 (0.92)
> 14: 2^114 - 2^57 - 1 (0.98)
> 21: 2^166 - 5 (0.95)
> 22: 2^174 - 17 (1.00)
> 27: 2^216 - 2^108 - 1 (0.93)
> 28: 2^226 - 5 (0.97)
> 36: 2^285 - 9 (0.98)
> 40: 2^322 - 2^161 - 1 (0.93)
> 42: 2^336 - 17 (0.97)
> 46: 2^369 - 25 (0.91)
> 49: 2^389 - 21 (0.96)
> 56: 2^450 - 2^225 - 1 (0.97)
> 60: 2^480 - 2^240 - 1 (0.92)
> 61: 2^489 - 21 (0.94)
> 65: 2^521 - 1 (1.00)
>
> Again, further support for performance being a fairly rigid criterion.
>
> # Appendix
>
> The complete list of Crandall and Hamburg primes considered:
>
> Ridinghoods:
> p = 2^n - 2^n/2 - 1
> 2^90 - 2^45 - 1
> 2^100 - 2^50 - 1
> 2^114 - 2^57 - 1
> 2^216 - 2^108 - 1
> 2^322 - 2^161 - 1
> 2^416 - 2^208 - 1
> 2^448 - 2^224 - 1
> 2^450 - 2^225 - 1
> 2^480 - 2^240 - 1
> 2^708 - 2^354 - 1
>
> Crandalls:
> p = 2^n - c, c < 256 && p%4==3, !E(c' < c && is_prime(2^n-c'))
> 2^89 - 1
> 2^93 - 25
> 2^96 - 17
> 2^104 - 17
> 2^105 - 13
> 2^107 - 1
> 2^110 - 21
> 2^118 - 5
> 2^125 - 9
> 2^127 - 1
> 2^129 - 25
> 2^130 - 5
> 2^137 - 13
> 2^141 - 9
> 2^150 - 5
> 2^152 - 17
> 2^165 - 25
> 2^166 - 5
> 2^174 - 17
> 2^189 - 25
> 2^198 - 17
> 2^206 - 5
> 2^212 - 29
> 2^226 - 5
> 2^243 - 9
> 2^251 - 9
> 2^285 - 9
> 2^321 - 9
> 2^336 - 17
> 2^369 - 25
> 2^389 - 21
> 2^413 - 21
> 2^414 - 17
> 2^444 - 17
> 2^468 - 17
> 2^488 - 17
> 2^489 - 21
> 2^521 - 1
> 2^537 - 9
> 2^550 - 5
> 2^563 - 9
> 2^607 - 1
> 2^664 - 17
> 2^699 - 9
> 2^706 - 5
> 2^717 - 25
> 2^729 - 9
> 2^808 - 17
> 2^810 - 5
> 2^848 - 17
> 2^869 - 21
> _______________________________________________
> Curves mailing list
> Curves at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/curves
More information about the Curves
mailing list