Struct curve25519_dalek::field::FieldElement

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

A FieldElement represents an element of the field GF(2²⁵⁵ - 19).

With the radix_51 feature, a FieldElement is represented in radix 2^25.5 as ten i32s, so that 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 zero.

fn one() -> FieldElement

Construct one.

fn minus_one() -> FieldElement

Construct -1.

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

Create a FieldElement by demarshalling an array of 32 bytes.

Example

XXX eliminate limbs

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.

XXX eliminate limbs

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 is_negative_ed25519(&self) -> u8

Determine if this FieldElement is negative, in the sense used in the ed25519 paper: x is negative if the low bit is set.

Return

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

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 square(&self) -> FieldElement

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

XXX limbs: better to talk about headroom?

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.

XXX explain why square2 exists vs square (overflow)

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).

XXX should we add a debug_assert that self is nonzero?

fn pow_p58(&self) -> FieldElement

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

fn sqrt_ratio(u: &FieldElement, v: &FieldElement) -> (u8, FieldElement)

Given FieldElements u and v, attempt to compute sqrt(u/v) in constant time.

It would be much better to use an Option type here, but doing so forces the caller to branch, which we don't want to do. This seems like the least bad solution.

Return

• (1u8, sqrt(u/v)) if v is nonzero and u/v is square;
• (0u8, zero) if v is zero;
• (0u8, garbage) if u/v is nonsquare.

fn invsqrt(&self) -> (u8, FieldElement)

For self a nonzero square, compute 1/sqrt(self) in constant time.

It would be much better to use an Option type here, but doing so forces the caller to branch, which we don't want to do. This seems like the least bad solution.

Return

• (1u8, 1/sqrt(self)) if self is a nonzero square;
• (0u8, zero) if self is zero;
• (0u8, garbage) if self is nonsquare.

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(&self, _index: usize) -> &Limb

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

impl IndexMut<usize> for FieldElement

fn index_mut(&mut self, _index: usize) -> &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.

XXX fixup tests to avoid limb specs XXX_radix_51

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}