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
[email protected]
https://moderncrypto.org/mailman/listinfo/curves
_______________________________________________
Curves mailing list
[email protected]
https://moderncrypto.org/mailman/listinfo/curves
