Struct curve25519_dalek::field::FieldElement

pub struct FieldElement(pub [Limb; 10]);

FieldElement represents an element of the field GF(2²⁵⁵ - 19). An element t, entries t[0]...t[9], represents the integer t[0]+2²⁶ t[1]+2⁵¹ t[2]+2⁷⁷ t[3]+2¹⁰² t[4]+...+2²³⁰ t[9]. Bounds on each t[i] vary depending on context.

Methods

impl FieldElement

fn negate(&mut self)

Invert the sign of this field element

fn zero() -> FieldElement

Construct the additive identity

fn one() -> FieldElement

Construct the multiplicative identity

fn from_bytes(data: &[u8; 32]) -> FieldElement

Create a FieldElement by demarshalling an array of 32 bytes.

Example

let data: [u8; 32] = [ 1,  2,  3,  4,  5,  6,  7,  8,
                       9, 10, 11, 12, 13, 14, 15, 16,
                      17, 18, 19, 20, 21, 22, 23, 24,
                      25, 26, 27, 28, 29, 30, 31, 32 ];
let fe: FieldElement = FieldElement::from_bytes(&data);
assert_eq!(fe,
           FieldElement([ 197121, -4095679,  21045505,  6840408, 4209720,
                         1249809, -7665014, -12377341, 30523826, 8420472]))

Return

Returns a new FieldElement.

fn to_bytes(&self) -> [u8; 32]

Marshal this FieldElement into a 32-byte array.

Preconditions

• |h[i]| bounded by 1.1*2^25, 1.1*2^24, 1.1*2^25, 1.1*2^24, etc.

Lemma

Write p = 2²⁵⁵ - 19 and q = floor(h/p).

Basic claim: q = floor(2^-255(h + 19 * 2^-25 h9 + 2^-1)).

Proof

Have |h|<=p so |q|<=1 so |19² * 2^-255 * q| < 1/4.

Also have |h-2²³⁰ * h9| < 2²³⁰ so |19 * 2^-255 * (h-2²³⁰ * h9)| < 1/4.

Write y=2^-1-19² 2^-255q-19 2^-255(h-2²³⁰ h9), then 0<y<1.

Write r = h - pq.

Have 0 <= r< = p-1 = 2²⁵⁵ - 20.

Thus 0 <= r + 19 * 2^-255 * r < r + 19 * 2^-255 * 2²⁵⁵ <= 2²⁵⁵ - 1.

Write x = r + 19 * 2^-255 * r + y.

Then 0 < x < 2²⁵⁵ so floor(2^-255x) = 0 so floor(q+2^-255x) = q.

Have q+2^-255x = 2^-255 * (h + 19 * 2^-25 * h9 + 2^-1), so floor(2^-255 * (h + 19 * 2^-25 * h9 + 2^-1)) = q.

Example

Continuing from the previous example in FieldElement::from_bytes:

let data: [u8; 32] = [ 1,  2,  3,  4,  5,  6,  7,  8,
                       9, 10, 11, 12, 13, 14, 15, 16,
                      17, 18, 19, 20, 21, 22, 23, 24,
                      25, 26, 27, 28, 29, 30, 31, 32 ];
let fe: FieldElement = FieldElement([ 197121, -4095679,  21045505,  6840408, 4209720,
                                     1249809, -7665014, -12377341, 30523826, 8420472]);
let bytes: [u8; 32] = fe.to_bytes();
assert!(data == bytes);

fn bytes_equal_less_than(&self, other: &[u8; 32]) -> u8

XXX clarify documentation Determine if this field element, represented as a byte array, is less than or equal to another field element represented as a byte array.

Returns

Returns 1u8 if self.to_bytes() <= other.to_bytes(), and 0u8 otherwise.

fn is_negative_ed25519(&self) -> i32

Determine if this FieldElement is negative, in the sense used in the ed25519 paper.

Return

If negative, return 1i32. Otherwise, return 0i32.

fn is_negative_decaf(&self) -> u8

Determine if this FieldElement is negative, in the sense used by Decaf: x is nonnegative if the least absolute residue for x lies in [0, (p-1)/2], and is negative otherwise.

Return

Returns 1u8 if negative, 0u8 if nonnegative.

Implementation

Uses a trick borrowed from Mike Hamburg's code. Let x \in F_p and let y \in Z be the least absolute residue for x. Suppose y ≤ (p-1)/2. Then 2y < p so 2y = 2y mod p and 2y mod p is even. On the other hand, if y > (p-1)/2 then 2y ≥ p; since y < p, 2y \in [p, 2p), so 2y mod p = 2y-p, which is odd.

Thus we can test whether y ≤ (p-1)/2 by checking whether 2y mod p is even.

fn is_nonnegative_decaf(&self) -> u8

Determine if this FieldElement is nonnegative, in the sense used by Decaf: x is nonnegative if the least absolute residue for x lies in [0, (p-1)/2], and is negative otherwise.

fn is_zero(&self) -> u8

Determine if this FieldElement is zero.

Return

If zero, return 1u8. Otherwise, return 0u8.

fn is_nonzero(&self) -> u8

Determine if this FieldElement is non-zero.

Return

If non-zero, return 1u8. Otherwise, return 0u8.

fn multiply(&self, _rhs: &FieldElement) -> FieldElement

Calculates h = f * g. Can overlap h with f or g.

Preconditions

• |f[i]| bounded by 1.1*2^26, 1.1*2^25, 1.1*2^26, 1.1*2^25, etc.
• |g[i]| bounded by 1.1*2^26, 1.1*2^25, 1.1*2^26, 1.1*2^25, etc.

Postconditions

• |h| bounded by 1.1*2^25, 1.1*2^24, 1.1*2^25, 1.1*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.

fn square(&self) -> FieldElement

Calculates h = f*f. Can overlap h with f.

Preconditions

• |f[i]| bounded by 1.1*2^26, 1.1*2^25, 1.1*2^26, 1.1*2^25, etc.

Postconditions

• |h[i]| bounded by 1.1*2^25, 1.1*2^24, 1.1*2^25, 1.1*2^24, etc.

fn square2(&self) -> FieldElement

Square this field element and multiply the result by 2.

Preconditions

• |f[i]| bounded by 1.65*2^26, 1.65*2^25, 1.65*2^26, 1.65*2^25, etc.

Postconditions

• |h[i]| bounded by 1.01*2^25, 1.01*2^24, 1.01*2^25, 1.01*2^24, etc.

Notes

See fe_mul.c in ref10 implementation for discussion of implementation strategy.

fn invert(&self) -> FieldElement

Given a nonzero field element, compute its inverse. The inverse is computed as self^p-2, since x^p-2x = x^p-1 = 1 (mod p).

fn pow_p58(&self) -> FieldElement

Raise this field element to the power (p-5)/8 = 2²⁵² -3. Used in decoding.

fn invsqrt(&self) -> Option<FieldElement>

Try to compute 1/sqrt(self).

Return

• If self is zero, returns zero.
• If self is square, returns 1/sqrt(self).
• If self is nonsquare, returns None.

fn chi(&self) -> FieldElement

chi calculates self^((p-1)/2).

Return

• If this element is a non-zero square, returns 1.
• If it is zero, returns 0.
• If it is non-square, returns -1.

Trait Implementations

impl Copy for FieldElement

impl Clone for FieldElement

fn clone(&self) -> FieldElement

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Eq for FieldElement

impl PartialEq for FieldElement

fn eq(&self, other: &FieldElement) -> bool

Test equality between two FieldElements by converting them to bytes.

Warning

This comparison is not constant time. It could easily be made to be, but the main use of an Eq implementation is for branching, so it seems pointless.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl CTEq for FieldElement

fn ct_eq(&self, other: &FieldElement) -> u8

Test equality between two FieldElements by converting them to bytes.

Returns

1u8 if the two FieldElements are equal, and 0u8 otherwise.

impl Debug for FieldElement

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Index<usize> for FieldElement

type Output = Limb

The returned type after indexing

fn index<'a>(&'a self, _index: usize) -> &'a Limb

The method for the indexing (container[index]) operation

impl IndexMut<usize> for FieldElement

fn index_mut<'a>(&'a mut self, _index: usize) -> &'a mut Limb

The method for the mutable indexing (container[index]) operation

impl<'b> AddAssign<&'b FieldElement> for FieldElement

fn add_assign(&mut self, _rhs: &'b FieldElement)

The method for the += operator

impl<'a, 'b> Add<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

The resulting type after applying the + operator

fn add(self, _rhs: &'b FieldElement) -> FieldElement

The method for the + operator

impl<'b> SubAssign<&'b FieldElement> for FieldElement

fn sub_assign(&mut self, _rhs: &'b FieldElement)

The method for the -= operator

impl<'a, 'b> Sub<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

The resulting type after applying the - operator

fn sub(self, _rhs: &'b FieldElement) -> FieldElement

The method for the - operator

impl<'b> MulAssign<&'b FieldElement> for FieldElement

fn mul_assign(&mut self, _rhs: &'b FieldElement)

The method for the *= operator

impl<'a, 'b> Mul<&'b FieldElement> for &'a FieldElement

type Output = FieldElement

The resulting type after applying the * operator

fn mul(self, _rhs: &'b FieldElement) -> FieldElement

The method for the * operator

impl<'a> Neg for &'a FieldElement

type Output = FieldElement

The resulting type after applying the - operator

fn neg(self) -> FieldElement

The method for the unary - operator

impl CTAssignable for FieldElement

fn conditional_assign(&mut self, f: &FieldElement, choice: u8)

Conditionally assign another FieldElement to this one.

If choice == 0, replace self with self:

let f     = FieldElement([1,1,1,1,1,1,1,1,1,1]);
let g     = FieldElement([2,2,2,2,2,2,2,2,2,2]);
let mut h = FieldElement([1,1,1,1,1,1,1,1,1,1]);
h.conditional_assign(&g, 0);
assert!(h == f);

If choice == 1, replace self with f:

h.conditional_assign(&g, 1);
assert!(h == g);

Preconditions

• choice in {0,1}