net.i2p.crypto.eddsa.math.ed25519

Class Ed25519FieldElement

java.lang.Object

net.i2p.crypto.eddsa.math.FieldElement

net.i2p.crypto.eddsa.math.ed25519.Ed25519FieldElement

All Implemented Interfaces:

Serializable

public class Ed25519FieldElement
extends FieldElement

Class to represent a field element of the finite field $p = 2^{255} - 19$ elements.

An element $t$, entries $t[0] \dots t[9]$, represents the integer $t[0]+2^{26} t[1]+2^{51} t[2]+2^{77} t[3]+2^{102} t[4]+\dots+2^{230} t[9]$. Bounds on each $t[i]$ vary depending on context.

Reviewed/commented by Bloody Rookie (nemproject@gmx.de)

See Also:

Serialized Form

Field Summary

Fields inherited from class net.i2p.crypto.eddsa.math.FieldElement

f

Constructor Summary

Constructors

Constructor and Description
Ed25519FieldElement(Field f, int[] t) Creates a field element.

Method Summary

Modifier and Type	Method and Description
FieldElement	add(FieldElement val) $h = f + g$
FieldElement	cmov(FieldElement val, int b) Constant-time conditional move.
boolean	equals(Object obj)
int	hashCode()
FieldElement	invert() Invert this field element.
boolean	isNonZero() Gets a value indicating whether or not the field element is non-zero.
FieldElement	multiply(FieldElement val) $h = f * g$
FieldElement	negate() $h = -f$
FieldElement	pow22523() Gets this field element to the power of $(2^{252} - 3)$.
FieldElement	square() $h = f * f$
FieldElement	squareAndDouble() $h = 2 * f * f$
FieldElement	subtract(FieldElement val) $h = f - g$
String	toString()

Methods inherited from class net.i2p.crypto.eddsa.math.FieldElement

addOne, divide, isNegative, subtractOne, toByteArray

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

Ed25519FieldElement

public Ed25519FieldElement(Field f,
                           int[] t)

Creates a field element.

Parameters:

f - The underlying field, must be the finite field with $p = 2^{255} - 19$ elements

t - The $2^{25.5}$ bit representation of the field element.

Method Detail

isNonZero

public boolean isNonZero()

Gets a value indicating whether or not the field element is non-zero.

Specified by:

isNonZero in class FieldElement

Returns:

1 if it is non-zero, 0 otherwise.

add

public FieldElement add(FieldElement val)

$h = f + g$

TODO-CR BR: $h$ is allocated via new, probably not a good idea. Do we need the copying into temp variables if we do that?

Preconditions:

• $|f|$ bounded by $1.1*2^{25},1.1*2^{24},1.1*2^{25},1.1*2^{24},$ etc.
• $|g|$ bounded by $1.1*2^{25},1.1*2^{24},1.1*2^{25},1.1*2^{24},$ etc.

Postconditions:

• $|h|$ bounded by $1.1*2^{26},1.1*2^{25},1.1*2^{26},1.1*2^{25},$ etc.

Specified by:

add in class FieldElement

Parameters:

val - The field element to add.

Returns:

The field element this + val.

subtract

public FieldElement subtract(FieldElement val)

$h = f - g$

Can overlap $h$ with $f$ or $g$.

TODO-CR BR: See above.

Preconditions:

• $|f|$ bounded by $1.1*2^{25},1.1*2^{24},1.1*2^{25},1.1*2^{24},$ etc.
• $|g|$ bounded by $1.1*2^{25},1.1*2^{24},1.1*2^{25},1.1*2^{24},$ etc.

Postconditions:

• $|h|$ bounded by $1.1*2^{26},1.1*2^{25},1.1*2^{26},1.1*2^{25},$ etc.

Specified by:

subtract in class FieldElement

Parameters:

val - The field element to subtract.

Returns:

The field element this - val.

negate

public FieldElement negate()

$h = -f$

TODO-CR BR: see above.

Preconditions:

• $|f|$ bounded by $1.1*2^{25},1.1*2^{24},1.1*2^{25},1.1*2^{24},$ etc.

Postconditions:

• $|h|$ bounded by $1.1*2^{25},1.1*2^{24},1.1*2^{25},1.1*2^{24},$ etc.

Specified by:

negate in class FieldElement

Returns:

The field element (-1) * this.

multiply

public FieldElement multiply(FieldElement val)

$h = f * g$

Can overlap $h$ with $f$ or $g$.

Preconditions:

• $|f|$ bounded by $1.65*2^{26},1.65*2^{25},1.65*2^{26},1.65*2^{25},$ etc.
• $|g|$ bounded by $1.65*2^{26},1.65*2^{25},1.65*2^{26},1.65*2^{25},$ etc.

Postconditions:

• $|h|$ bounded by $1.01*2^{25},1.01*2^{24},1.01*2^{25},1.01*2^{24},$ etc.

Notes on implementation strategy:

Using schoolbook multiplication. Karatsuba would save a little in some cost models.

Most multiplications by 2 and 19 are 32-bit precomputations; cheaper than 64-bit postcomputations.

There is one remaining multiplication by 19 in the carry chain; one *19 precomputation can be merged into this, but the resulting data flow is considerably less clean.

There are 12 carries below. 10 of them are 2-way parallelizable and vectorizable. Can get away with 11 carries, but then data flow is much deeper.

With tighter constraints on inputs can squeeze carries into int32.

Specified by:

multiply in class FieldElement

Parameters:

val - The field element to multiply.

Returns:

The (reasonably reduced) field element this * val.

square

public FieldElement square()

$h = f * f$

Can overlap $h$ with $f$.

Preconditions:

• $|f|$ bounded by $1.65*2^{26},1.65*2^{25},1.65*2^{26},1.65*2^{25},$ etc.

Postconditions:

• $|h|$ bounded by $1.01*2^{25},1.01*2^{24},1.01*2^{25},1.01*2^{24},$ etc.

See multiply(FieldElement) for discussion of implementation strategy.

Specified by:

square in class FieldElement

Returns:

The (reasonably reduced) square of this field element.

squareAndDouble

public FieldElement squareAndDouble()

$h = 2 * f * f$

Can overlap $h$ with $f$.

Preconditions:

• $|f|$ bounded by $1.65*2^{26},1.65*2^{25},1.65*2^{26},1.65*2^{25},$ etc.

Postconditions:

• $|h|$ bounded by $1.01*2^{25},1.01*2^{24},1.01*2^{25},1.01*2^{24},$ etc.

See multiply(FieldElement) for discussion of implementation strategy.

Specified by:

squareAndDouble in class FieldElement

Returns:

The (reasonably reduced) square of this field element times 2.

invert

public FieldElement invert()

Invert this field element.

The inverse is found via Fermat's little theorem:
$a^p \cong a \mod p$ and therefore $a^{(p-2)} \cong a^{-1} \mod p$

Specified by:

invert in class FieldElement

Returns:

The inverse of this field element.

pow22523

public FieldElement pow22523()

Gets this field element to the power of $(2^{252} - 3)$. This is a helper function for calculating the square root.

TODO-CR BR: I think it makes sense to have a sqrt function.

Specified by:

pow22523 in class FieldElement

Returns:

This field element to the power of $(2^{252} - 3)$.

cmov

public FieldElement cmov(FieldElement val,
                         int b)

Constant-time conditional move. Well, actually it is a conditional copy. Logic is inspired by the SUPERCOP implementation at: https://github.com/floodyberry/supercop/blob/master/crypto_sign/ed25519/ref10/fe_cmov.c

Specified by:

cmov in class FieldElement

Parameters:

val - the other field element.

b - must be 0 or 1, otherwise results are undefined.

Returns:

a copy of this if $b == 0$, or a copy of val if $b == 1$.

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

toString

public String toString()

Overrides:

toString in class Object