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 conditional_choose(&mut self, f: &FieldElement, g: &FieldElement, choice: u8)

Overwrite this FieldElement with one of the inputs without branching. Like conditional_assign, but chooses between two inputs instead of one input and the original value.

If choice == 0, replace self with f:

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([0,0,0,0,0,0,0,0,0,0]);
h.conditional_choose(&f, &g, 0);
assert!(h == f);

If choice == 1, replace self with g:

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

Preconditions

• b in {0,1}

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

Conditionally assign the Limbs of another FieldElement to this one. Like conditional_choose, but choosing between one input and the original value.

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}

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

Determine if this FieldElement is negative.

Return

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

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

XXX it would be good to encode constant-time considerations (no data flow from secret information) into Rust's type system.

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

This method tests for !=.

impl Eq for FieldElement

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