[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