addchain

package module
v0.4.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Oct 30, 2021 License: BSD-3-Clause Imports: 5 Imported by: 0

README

addchain
Build Status go.dev Go Report Card

Cryptographic Addition Chain Generation in Go

addchain generates short addition chains for exponents of cryptographic interest with results rivaling the best hand-optimized chains. Intended as a building block in elliptic curve or other cryptographic code generators.

  • Suite of algorithms from academic research: continued fractions, dictionary-based and Bos-Coster heuristics
  • Custom run-length techniques exploit structure of cryptographic exponents with excellent results on Solinas primes
  • Generic optimization methods eliminate redundant operations
  • Simple domain-specific language for addition chain computations
  • Command-line interface or library
  • Code generation and templated output support

Table of Contents

Background

An addition chain for a target integer n is a sequence of numbers starting at 1 and ending at n such that every term is a sum of two numbers appearing earlier in the sequence. For example, an addition chain for 29 is

1, 2, 4, 8, 9, 17, 25, 29

Addition chains arise in the optimization of exponentiation algorithms with fixed exponents. For example, the addition chain above corresponds to the following sequence of multiplications to compute x29

 x2 = x1 * x1
 x4 = x2 * x2
 x8 = x4 * x4
 x9 = x1 * x8
x17 = x8 * x9
x25 = x8 * x17
x29 = x4 * x25

An exponentiation algorithm for a fixed exponent n reduces to finding a minimal length addition chain for n. This is especially relevent in cryptography where exponentiation by huge fixed exponents forms a performance-critical component of finite-field arithmetic. In particular, constant-time inversion modulo a prime p is performed by computing xp-2 (mod p), thanks to Fermat's Little Theorem. Square root also reduces to exponentiation for some prime moduli. Finding short addition chains for these exponents is one important part of high-performance finite field implementations required for elliptic curve cryptography or RSA.

Minimal addition chain search is famously hard. No practical optimal algorithm is known, especially for cryptographic exponents of size 256-bits and up. Given its importance for the performance of cryptographic implementations, implementers devote significant effort to hand-tune addition chains. The goal of the addchain project is to match or exceed the best hand-optimized addition chains using entirely automated approaches, building on extensive academic research and applying new tweaks that exploit the unique nature of cryptographic exponents.

Results

The following table shows the results of the addchain library on popular cryptographic exponents. For each one we also show the length of the best known hand-optimized addition chain, and the delta from the library result.

Name This Library Best Known Delta
Curve25519 Field Inversion 266 265 +1
NIST P-256 Field Inversion 266 266 +0
NIST P-384 Field Inversion 397 396 +1
secp256k1 (Bitcoin) Field Inversion 269 269 +0
Curve25519 Scalar Inversion 283 284 -1
NIST P-256 Scalar Inversion 294 292 +2
NIST P-384 Scalar Inversion 434 433 +1
secp256k1 (Bitcoin) Scalar Inversion 293 290 +3

See full results listing for more detail and results for less common exponents.

These results demonstrate that addchain is competitive with hand-optimized chains, often with equivalent or better performance. Even when addchain is slightly sub-optimal, it can still be considered valuable since it fully automates a laborious manual process. As such, addchain can be trusted to produce high quality results in an automated code generation tool.

Usage

Command-line Interface

Install a pre-compiled release binary:

curl -sSfL https://git.io/addchain | sh -s -- -b /usr/local/bin

Alternatively build from source:

go install github.com/mmcloughlin/addchain/cmd/addchain@latest

Search for a curve25519 field inversion addition chain with:

addchain search '2^255 - 19 - 2'

Output:

addchain: expr: "2^255 - 19 - 2"
addchain: hex: 7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeb
addchain: dec: 57896044618658097711785492504343953926634992332820282019728792003956564819947
addchain: best: opt(runs(continued_fractions(dichotomic)))
addchain: cost: 266
_10       = 2*1
_11       = 1 + _10
_1100     = _11 << 2
_1111     = _11 + _1100
_11110000 = _1111 << 4
_11111111 = _1111 + _11110000
x10       = _11111111 << 2 + _11
x20       = x10 << 10 + x10
x30       = x20 << 10 + x10
x60       = x30 << 30 + x30
x120      = x60 << 60 + x60
x240      = x120 << 120 + x120
x250      = x240 << 10 + x10
return      (x250 << 2 + 1) << 3 + _11

Next, you can generate code from this addition chain.

Library

Install:

go get -u github.com/mmcloughlin/addchain

Algorithms all conform to the alg.ChainAlgorithm or alg.SequenceAlgorithm interfaces and can be used directly. However the most user-friendly method uses the alg/ensemble package to instantiate a sensible default set of algorithms and the alg/exec helper to execute them in parallel. The following code uses this method to find an addition chain for curve25519 field inversion:

func Example() {
	// Target number: 2²⁵⁵ - 21.
	n := new(big.Int)
	n.SetString("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeb", 16)

	// Default ensemble of algorithms.
	algorithms := ensemble.Ensemble()

	// Use parallel executor.
	ex := exec.NewParallel()
	results := ex.Execute(n, algorithms)

	// Output best result.
	best := 0
	for i, r := range results {
		if r.Err != nil {
			log.Fatal(r.Err)
		}
		if len(results[i].Program) < len(results[best].Program) {
			best = i
		}
	}
	r := results[best]
	fmt.Printf("best: %d\n", len(r.Program))
	fmt.Printf("algorithm: %s\n", r.Algorithm)

	// Output:
	// best: 266
	// algorithm: opt(runs(continued_fractions(dichotomic)))
}

Algorithms

This section summarizes the algorithms implemented by addchain along with references to primary literature. See the bibliography for the complete references list.

Binary

The alg/binary package implements the addition chain equivalent of the basic square-and-multiply exponentiation method. It is included for completeness, but is almost always outperformed by more advanced algorithms below.

Continued Fractions

The alg/contfrac package implements the continued fractions methods for addition sequence search introduced by Bergeron-Berstel-Brlek-Duboc in 1989 and later extended. This approach utilizes a decomposition of an addition chain akin to continued fractions, namely

(1,..., k,..., n) = (1,...,n mod k,..., k) ⊗ (1,..., n/k) ⊕ (n mod k).

for certain special operators ⊗ and ⊕. This decomposition lends itself to a recursive algorithm for efficient addition sequence search, with results dependent on the strategy for choosing the auxillary integer k. The alg/contfrac package provides a laundry list of strategies from the literature: binary, co-binary, dichotomic, dyadic, fermat, square-root and total.

References

Bos-Coster Heuristics

Bos and Coster described an iterative algorithm for efficient addition sequence generation in which at each step a heuristic proposes new numbers for the sequence in such a way that the maximum number always decreases. The original Bos-Coster paper defined four heuristics: Approximation, Divison, Halving and Lucas. Package alg/heuristic implements a variation on these heuristics:

  • Approximation: looks for two elements a, b in the current sequence with sum close to the largest element.
  • Halving: applies when the target is at least twice as big as the next largest, and if so it will propose adding a sequence of doublings.
  • Delta Largest: proposes adding the delta between the largest two entries in the current sequence.

Divison and Lucas are not implemented due to disparities in the literature about their precise definition and poor results from early experiments. Furthermore, this library does not apply weights to the heuristics as suggested in the paper, rather it simply uses the first that applies. However both of these remain possible avenues for improvement.

References

Dictionary

Dictionary methods decompose the binary representation of a target integer n into a set of dictionary terms, such that n may be written as a sum

n = ∑ 2ei di

for exponents e and elements d from a dictionary D. Given such a decomposition we can construct an addition chain for n by

  1. Find a short addition sequence containing every element of the dictionary D. Continued fractions and Bos-Coster heuristics can be used here.
  2. Build n from the dictionary terms according to the sum decomposition.

The efficiency of this approach boils down to the decomposition method. The alg/dict package provides:

  • Fixed Window: binary representation of n is broken into fixed k-bit windows
  • Sliding Window: break n into k-bit windows, skipping zeros where possible
  • Run Length: decompose n into runs of 1s up to a maximal length
  • Hybrid: mix of sliding window and run length methods
References

Runs

The runs algorithm is a custom variant of the dictionary approach that decomposes a target into runs of ones. It leverages the observation that building a dictionary consisting of runs of 1s of lengths l1, l2, ..., lk can itself be reduced to:

  1. Find an addition sequence containing the run lengths li. As with dictionary approaches we can use Bos-Coster heuristics and continued fractions here. However here we have the advantage that the li are typically very small, meaning that a wider range of algorithms can be brought to bear.
  2. Use the addition sequence for the run lengths li to build an addition sequence for the runs themselves r(li) where r(e) = 2e-1. See dict.RunsChain.

This approach has proved highly effective against cryptographic exponents which frequently exhibit binary structure, such as those derived from Solinas primes.

I have not seen this method discussed in the literature. Please help me find references to prior art if you know any.

Optimization

Close inspection of addition chains produced by other algorithms revealed cases of redundant computation. This motivated a final optimization pass over addition chains to remove unecessary steps. The alg/opt package implements the following optimization:

  1. Determine all possible ways each element can be computed from those prior.
  2. Count how many times each element is used where it is the only possible way of computing that entry.
  3. Prune elements that are always used in computations that have an alternative.

These micro-optimizations were vital in closing the gap between addchain's automated approaches and hand-optimized chains. This technique is reminiscent of basic passes in optimizing compilers, raising the question of whether other compiler optimizations could apply to addition chains?

I have not seen this method discussed in the literature. Please help me find references to prior art if you know any.

Citing

If you use addchain in your research a citation would be appreciated. Citing a specific release is preferred, since they are archived on Zenodo and assigned a DOI. Please use the following BibTeX to cite the most recent 0.4.0 release.

@misc{addchain,
    title        = {addchain: Cryptographic Addition Chain Generation in Go},
    author       = {Michael B. McLoughlin},
    year         = 2021,
    month        = oct,
    howpublished = {Repository \url{https://github.com/mmcloughlin/addchain}},
    version      = {0.4.0},
    license      = {BSD 3-Clause License},
    doi          = {10.5281/zenodo.5622943},
    url          = {https://doi.org/10.5281/zenodo.5622943},
}

If you need to cite a currently unreleased version please consider filing an issue to request a new release, or to discuss an appropriate format for the citation.

Thanks

Thank you to Tom Dean, Riad Wahby, Brian Smith and str4d for advice and encouragement. Thanks also to Damian Gryski and Martin Glancy for review.

Contributing

Contributions to addchain are welcome:

License

addchain is available under the BSD 3-Clause License.

Documentation

Overview

Package addchain provides addition chain types and operations on them.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Chain 

type Chain []*big.Int

Chain is an addition chain.

func Int64s 

func Int64s(xs ...int64) Chain

Int64s builds a chain from the given int64 values.

func New 

func New() Chain

New constructs the minimal chain {1}.

func Plus 

func Plus(a Chain, x *big.Int) Chain

Plus adds x to the addition chain. This is the "o plus" operator defined in [efficientcompaddchain] Section 2.

func Product 

func Product(a, b Chain) Chain

Product computes the product of two addition chains. The is the "o times" operator defined in [efficientcompaddchain] Section 2.

func (*Chain) AppendClone 

func (c *Chain) AppendClone(x *big.Int)

AppendClone appends a copy of x to c.

func (Chain) Clone 

func (c Chain) Clone() Chain

Clone the chain.

func (Chain) End 

func (c Chain) End() *big.Int

End returns the last element of the chain.

func (Chain) IsAscending added in v0.3.0 

func (c Chain) IsAscending() bool

IsAscending reports whether the chain is ascending, that is if it's in sorted order without repeats, as defined in [knuth] Section 4.6.3 formula (11). Does not fully validate the chain, only that it is ascending.

func (Chain) Op 

func (c Chain) Op(k int) (Op, error)

Op returns an Op that produces the kth position.

func (Chain) Ops 

func (c Chain) Ops(k int) []Op

Ops returns all operations that produce the kth position. This could be empty for an invalid chain.

func (Chain) Produces 

func (c Chain) Produces(target *big.Int) error

Produces checks that c is a valid chain ending with target.

func (Chain) Program 

func (c Chain) Program() (Program, error)

Program produces a program that generates the chain.

func (Chain) Superset 

func (c Chain) Superset(targets []*big.Int) error

Superset checks that c is a valid chain containing all the targets.

func (Chain) Validate 

func (c Chain) Validate() error

Validate checks that c is in fact an addition chain.

type Op 

type Op struct{ I, J int }

Op is an instruction to add positions I and J in a chain.

func (Op) IsDouble 

func (o Op) IsDouble() bool

IsDouble returns whether this operation is a doubling.

func (Op) Operands 

func (o Op) Operands() []int

Operands returns the indicies used in this operation. This will contain one or two entries depending on whether this is a doubling.

func (Op) Uses 

func (o Op) Uses(i int) bool

Uses reports whether the given index is one of the operands.

type Program 

type Program []Op

Program is a sequence of operations.

func (*Program) Add 

func (p *Program) Add(i, j int) (int, error)

Add appends an operation that adds indices i and j. Returns the index of the result.

func (Program) Adds 

func (p Program) Adds() int

Adds returns the number of adds in the program.

func (Program) Count 

func (p Program) Count() (doubles, adds int)

Count returns the number of doubles and adds in the program.

func (Program) Dependencies 

func (p Program) Dependencies() []*big.Int

Dependencies returns an array of bitsets where each bitset contains the set of indicies that contributed to that position.

func (*Program) Double 

func (p *Program) Double(i int) (int, error)

Double appends an operation that doubles index i. Returns the index of the result.

func (Program) Doubles 

func (p Program) Doubles() int

Doubles returns the number of doubles in the program.

func (Program) Evaluate 

func (p Program) Evaluate() Chain

Evaluate executes the program and returns the resulting chain.

func (Program) ReadCounts 

func (p Program) ReadCounts() []int

ReadCounts returns how many times each index is read in the program.

func (*Program) Shift 

func (p *Program) Shift(i int, s uint) (int, error)

Shift appends a sequence of operations that bitwise shift index i left by s, equivalent to s double operations. Returns the index of the result.

Source Files

View all Source files

Directories

Path Synopsis
acc
Package acc implements the "addition chain calculator" language: a domain-specific language (DSL) for addition chain computation.
 Package acc implements the "addition chain calculator" language: a domain-specific language (DSL) for addition chain computation.
ast
Package ast declares abstract syntax tree types for acc programs.
 Package ast declares abstract syntax tree types for acc programs.
ir
Package ir declares an intermediate representation for acc programs.
 Package ir declares an intermediate representation for acc programs.
parse
Package parse implements a parser for acc programs.
 Package parse implements a parser for acc programs.
parse/internal/parser
pass
Package pass implements analysis and processing passes on acc programs.
 Package pass implements analysis and processing passes on acc programs.
printer
Package printer implements printing of acc AST nodes.
 Package printer implements printing of acc AST nodes.
alg
Package alg provides base types for addition chain and addition sequence search algorithms.
 Package alg provides base types for addition chain and addition sequence search algorithms.
algtest
Package algtest provides algorithm test suites.
 Package algtest provides algorithm test suites.
binary
Package binary implements generic binary addition chain algorithms.
 Package binary implements generic binary addition chain algorithms.
contfrac
Package contfrac implements addition sequence algorithms based on continued-fraction expansions.
 Package contfrac implements addition sequence algorithms based on continued-fraction expansions.
dict
Package dict implements dictionary and run-length addition chain algorithms.
 Package dict implements dictionary and run-length addition chain algorithms.
ensemble
Package ensemble provides a collection of addition chain algorithms intended for target integers of cryptographic interest.
 Package ensemble provides a collection of addition chain algorithms intended for target integers of cryptographic interest.
exec
Package exec implements addition chain algorithm execution.
 Package exec implements addition chain algorithm execution.
heuristic
Package heuristic implements heuristic-based addition sequence algorithms with the Bos-Coster Makesequence structure.
 Package heuristic implements heuristic-based addition sequence algorithms with the Bos-Coster Makesequence structure.
opt
Package opt implements generic optimizations that remove redundancy from addition chains.
 Package opt implements generic optimizations that remove redundancy from addition chains.
cmd
addchain
Command addchain generates addition chains.
 Command addchain generates addition chains.
internal
assert
Package assert provides concise functions for common testing assertions.
 Package assert provides concise functions for common testing assertions.
bigint
Package bigint provides common functions for manipulating multi-precision integers.
 Package bigint provides common functions for manipulating multi-precision integers.
bigints
Package bigints provides helpers for slices of multi-precision integers.
 Package bigints provides helpers for slices of multi-precision integers.
bigvector
Package bigvector implements operations on vectors of immutable multi-precision integers.
 Package bigvector implements operations on vectors of immutable multi-precision integers.
calc
Package calc evaluates simple arithmetic expressions.
 Package calc evaluates simple arithmetic expressions.
cli
Package cli provides utilities for building subcommand-based command line interfaces.
 Package cli provides utilities for building subcommand-based command line interfaces.
container/heap
Package heap implements a heap on specific types.
 Package heap implements a heap on specific types.
errutil
Package errutil implements common error types and helper functions.
 Package errutil implements common error types and helper functions.
examples/fp25519
gen
Package gen provides templated output generation from addition chain programs.
 Package gen provides templated output generation from addition chain programs.
metavars
Package metavars allows manipulation of "meta variables" stored as variable declarations in Go files.
 Package metavars allows manipulation of "meta variables" stored as variable declarations in Go files.
polynomial
Package polynomial provides a polynomial type.
 Package polynomial provides a polynomial type.
prime
Package prime provides representations of classes of prime numbers.
 Package prime provides representations of classes of prime numbers.
print
Package print provides helpers for structured output printing.
 Package print provides helpers for structured output printing.
results
Package results stores results of this library on popular cryptographic exponents for testing and documentation purposes.
 Package results stores results of this library on popular cryptographic exponents for testing and documentation purposes.
test
Package test provides testing utilities.
 Package test provides testing utilities.
tools/docgen
tools/release
zenodo
Package zenodo provides a client for the Zendodo API.
 Package zenodo provides a client for the Zendodo API.
Package meta defines properties about this project.
 Package meta defines properties about this project.
Package rand provides random addition chain generators.
 Package rand provides random addition chain generators.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.