[curves] The Pareto frontiers of sleeveless primes
David Leon Gil
coruus at gmail.com
Sun Oct 26 14:15:28 PDT 2014
# Introduction
So. Motivated by prior posts by Michael Hamburg and Daniel Bernstein,
I made up a list of "good primes" for ECC.
## 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.)
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)
[^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?
## 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.
## 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
More information about the Curves
mailing list