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]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77 t[3]+2^102 t[4]+...+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 Modifier and Type Field Description (package private) int[]
t
Variable is package private for encoding.-
Fields inherited from class net.i2p.crypto.eddsa.math.FieldElement
f
-
-
Constructor Summary
Constructors Constructor Description Ed25519FieldElement(Field f, int[] t)
Creates a field element.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description FieldElement
add(FieldElement val)
h = f + gFieldElement
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 * gFieldElement
negate()
h = -fFieldElement
pow22523()
Gets this field element to the power of (2^252 - 3).FieldElement
square()
h = f * fFieldElement
squareAndDouble()
h = 2 * f * fFieldElement
subtract(FieldElement val)
h = f - gString
toString()
-
Methods inherited from class net.i2p.crypto.eddsa.math.FieldElement
addOne, divide, isNegative, subtractOne, toByteArray
-
-
-
-
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 elementst
- 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 classFieldElement
- Returns:
- 1 if it is non-zero, 0 otherwise.
-
add
public FieldElement add(FieldElement val)
h = f + gTODO-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 classFieldElement
- Parameters:
val
- The field element to add.- Returns:
- The field element this + val.
-
subtract
public FieldElement subtract(FieldElement val)
h = f - gCan 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 classFieldElement
- Parameters:
val
- The field element to subtract.- Returns:
- The field element this - val.
-
negate
public FieldElement negate()
h = -fTODO-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 classFieldElement
- Returns:
- The field element (-1) * this.
-
multiply
public FieldElement multiply(FieldElement val)
h = f * gCan 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 classFieldElement
- Parameters:
val
- The field element to multiply.- Returns:
- The (reasonably reduced) field element this * val.
-
square
public FieldElement square()
h = f * fCan 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 classFieldElement
- Returns:
- The (reasonably reduced) square of this field element.
-
squareAndDouble
public FieldElement squareAndDouble()
h = 2 * f * fCan 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 classFieldElement
- 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 congruent a mod p and therefore a^(p-2) congruent a^-1 mod p- Specified by:
invert
in classFieldElement
- 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 classFieldElement
- 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 classFieldElement
- 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.
- Since:
- 0.9.36
-
-