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