[−][src]Struct curve25519_dalek::scalar::Scalar

pub struct Scalar {
    pub(crate) bytes: [u8; 32],
}

The Scalar struct holds an integer $s < 2^{255} $ which represents an element of $\mathbb Z / \ell$.

Fields

bytes: [u8; 32]

bytes is a little-endian byte encoding of an integer representing a scalar modulo the group order.

Invariant

The integer representing this scalar must be bounded above by $2^{255}$, or equivalently the high bit of bytes[31] must be zero.

This ensures that there is room for a carry bit when computing a NAF representation.

Methods

`impl Scalar`[src]

`pub fn from_bytes_mod_order(bytes: [u8; 32]) -> Scalar`[src]

Construct a Scalar by reducing a 256-bit little-endian integer modulo the group order $ \ell $.

`pub fn from_bytes_mod_order_wide(input: &[u8; 64]) -> Scalar`[src]

Construct a Scalar by reducing a 512-bit little-endian integer modulo the group order $ \ell $.

`pub fn from_canonical_bytes(bytes: [u8; 32]) -> Option<Scalar>`[src]

Attempt to construct a Scalar from a canonical byte representation.

Return

Some(s), where s is the Scalar corresponding to bytes, if bytes is a canonical byte representation;
None if bytes is not a canonical byte representation.

`pub fn from_bits(bytes: [u8; 32]) -> Scalar`[src]

Construct a Scalar from the low 255 bits of a 256-bit integer.

This function is intended for applications like X25519 which require specific bit-patterns when performing scalar multiplication.

`impl Scalar`[src]

`pub fn random<R: RngCore + CryptoRng>(rng: &mut R) -> Self`[src]

Return a Scalar chosen uniformly at random using a user-provided RNG.

Inputs

rng: any RNG which implements the RngCore + CryptoRng interface.

Returns

A random scalar within ℤ/lℤ.

Example

extern crate rand_core;
use curve25519_dalek::scalar::Scalar;

use rand_core::OsRng;

let mut csprng = OsRng;
let a: Scalar = Scalar::random(&mut csprng);

`pub fn hash_from_bytes<D>(input: &[u8]) -> Scalar where D: Digest<OutputSize = U64> + Default,` [src]

Hash a slice of bytes into a scalar.

Takes a type parameter D, which is any Digest producing 64 bytes (512 bits) of output.

Convenience wrapper around from_hash.

Example

extern crate sha2;

use sha2::Sha512;

let msg = "To really appreciate architecture, you may even need to commit a murder";
let s = Scalar::hash_from_bytes::<Sha512>(msg.as_bytes());

`pub fn from_hash<D>(hash: D) -> Scalar where D: Digest<OutputSize = U64>,` [src]

Construct a scalar from an existing Digest instance.

Use this instead of hash_from_bytes if it is more convenient to stream data into the Digest than to pass a single byte slice.

Example

extern crate sha2;

use sha2::Digest;
use sha2::Sha512;

let mut h = Sha512::new()
    .chain("To really appreciate architecture, you may even need to commit a murder.")
    .chain("While the programs used for The Manhattan Transcripts are of the most extreme")
    .chain("nature, they also parallel the most common formula plot: the archetype of")
    .chain("murder. Other phantasms were occasionally used to underline the fact that")
    .chain("perhaps all architecture, rather than being about functional standards, is")
    .chain("about love and death.");

let s = Scalar::from_hash(h);

println!("{:?}", s.to_bytes());
assert!(s == Scalar::from_bits([ 21,  88, 208, 252,  63, 122, 210, 152,
                                154,  38,  15,  23,  16, 167,  80, 150,
                                192, 221,  77, 226,  62,  25, 224, 148,
                                239,  48, 176,  10, 185,  69, 168,  11, ]));

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

Convert this Scalar to its underlying sequence of bytes.

Example

use curve25519_dalek::scalar::Scalar;

let s: Scalar = Scalar::zero();

assert!(s.to_bytes() == [0u8; 32]);

`pub fn as_bytes(&self) -> &[u8; 32]`[src]

View the little-endian byte encoding of the integer representing this Scalar.

Example

use curve25519_dalek::scalar::Scalar;

let s: Scalar = Scalar::zero();

assert!(s.as_bytes() == &[0u8; 32]);

`pub fn zero() -> Self`[src]

Construct the scalar $ 0 $.

`pub fn one() -> Self`[src]

Construct the scalar $ 1 $.

`pub fn invert(&self) -> Scalar`[src]

Given a nonzero Scalar, compute its multiplicative inverse.

Warning

self MUST be nonzero. If you cannot prove that this is the case, you SHOULD NOT USE THIS FUNCTION.

Returns

The multiplicative inverse of the this Scalar.

Example

use curve25519_dalek::scalar::Scalar;

// x = 2238329342913194256032495932344128051776374960164957527413114840482143558222
let X: Scalar = Scalar::from_bytes_mod_order([
        0x4e, 0x5a, 0xb4, 0x34, 0x5d, 0x47, 0x08, 0x84,
        0x59, 0x13, 0xb4, 0x64, 0x1b, 0xc2, 0x7d, 0x52,
        0x52, 0xa5, 0x85, 0x10, 0x1b, 0xcc, 0x42, 0x44,
        0xd4, 0x49, 0xf4, 0xa8, 0x79, 0xd9, 0xf2, 0x04,
    ]);
// 1/x = 6859937278830797291664592131120606308688036382723378951768035303146619657244
let XINV: Scalar = Scalar::from_bytes_mod_order([
        0x1c, 0xdc, 0x17, 0xfc, 0xe0, 0xe9, 0xa5, 0xbb,
        0xd9, 0x24, 0x7e, 0x56, 0xbb, 0x01, 0x63, 0x47,
        0xbb, 0xba, 0x31, 0xed, 0xd5, 0xa9, 0xbb, 0x96,
        0xd5, 0x0b, 0xcd, 0x7a, 0x3f, 0x96, 0x2a, 0x0f,
    ]);

let inv_X: Scalar = X.invert();
assert!(XINV == inv_X);
let should_be_one: Scalar = &inv_X * &X;
assert!(should_be_one == Scalar::one());

`pub fn batch_invert(inputs: &mut [Scalar]) -> Scalar`[src]

Given a slice of nonzero (possibly secret) Scalars, compute their inverses in a batch.

Return

Each element of inputs is replaced by its inverse.

The product of all inverses is returned.

Warning

All input Scalars MUST be nonzero. If you cannot prove that this is the case, you SHOULD NOT USE THIS FUNCTION.

Example

let mut scalars = [
    Scalar::from(3u64),
    Scalar::from(5u64),
    Scalar::from(7u64),
    Scalar::from(11u64),
];

let allinv = Scalar::batch_invert(&mut scalars);

assert_eq!(allinv, Scalar::from(3*5*7*11u64).invert());
assert_eq!(scalars[0], Scalar::from(3u64).invert());
assert_eq!(scalars[1], Scalar::from(5u64).invert());
assert_eq!(scalars[2], Scalar::from(7u64).invert());
assert_eq!(scalars[3], Scalar::from(11u64).invert());

`pub(crate) fn bits(&self) -> [i8; 256]`[src]

Get the bits of the scalar.

`pub(crate) fn non_adjacent_form(&self, w: usize) -> [i8; 256]`[src]

Compute a width-$w$ "Non-Adjacent Form" of this scalar.

A width-$w$ NAF of a positive integer $k$ is an expression $$ k = \sum_{i=0}^m n_i 2^i, $$ where each nonzero coefficient $n_i$ is odd and bounded by $|n_i| < 2^{w-1}$, $n_{m-1}$ is nonzero, and at most one of any $w$ consecutive coefficients is nonzero. (Hankerson, Menezes, Vanstone; def 3.32).

The length of the NAF is at most one more than the length of the binary representation of $k$. This is why the Scalar type maintains an invariant that the top bit is $0$, so that the NAF of a scalar has at most 256 digits.

Intuitively, this is like a binary expansion, except that we allow some coefficients to grow in magnitude up to $2^{w-1}$ so that the nonzero coefficients are as sparse as possible.

When doing scalar multiplication, we can then use a lookup table of precomputed multiples of a point to add the nonzero terms $ k_i P $. Using signed digits cuts the table size in half, and using odd digits cuts the table size in half again.

To compute a $w$-NAF, we use a modification of Algorithm 3.35 of HMV:

$ i \gets 0 $
While $ k \ge 1 $:
1. If $k$ is odd, $ n_i \gets k \operatorname{mods} 2^w $, $ k \gets k - n_i $.
2. If $k$ is even, $ n_i \gets 0 $.
3. $ k \gets k / 2 $, $ i \gets i + 1 $.
Return $ n_0, n_1, ... , $

Here $ \bar x = x \operatorname{mods} 2^w $ means the $ \bar x $ with $ \bar x \equiv x \pmod{2^w} $ and $ -2^{w-1} \leq \bar x < 2^w $.

We implement this by scanning across the bits of $k$ from least-significant bit to most-significant-bit. Write the bits of $k$ as $$ k = \sum_{i=0}^m k_i 2^i, $$ and split the sum as $$ k = \sum_{i=0}^{w-1} k_i 2^i + 2^w \sum_{i=0} k_{i+w} 2^i $$ where the first part is $ k \mod 2^w $.

If $ k \mod 2^w$ is odd, and $ k \mod 2^w < 2^{w-1} $, then we emit $ n_0 = k \mod 2^w $. Instead of computing $ k - n_0 $, we just advance $w$ bits and reindex.

If $ k \mod 2^w$ is odd, and $ k \mod 2^w \ge 2^{w-1} $, then $ n_0 = k \operatorname{mods} 2^w = k \mod 2^w - 2^w $. The quantity $ k - n_0 $ is $$ \begin{aligned} k - n_0 &= \sum_{i=0}^{w-1} k_i 2^i + 2^w \sum_{i=0} k_{i+w} 2^i - \sum_{i=0}^{w-1} k_i 2^i + 2^w \\ &= 2^w + 2^w \sum_{i=0} k_{i+w} 2^i \end{aligned} $$ so instead of computing the subtraction, we can set a carry bit, advance $w$ bits, and reindex.

If $ k \mod 2^w$ is even, we emit $0$, advance 1 bit and reindex. In fact, by setting all digits to $0$ initially, we don't need to emit anything.

`pub(crate) fn to_radix_16(&self) -> [i8; 64]`[src]

Write this scalar in radix 16, with coefficients in $[-8,8)$, i.e., compute $a_i$ such that $$ a = a_0 + a_1 16^1 + \cdots + a_{63} 16^{63}, $$ with $-8 \leq a_i < 8$ for $0 \leq i < 63$ and $-8 \leq a_{63} \leq 8$.

`pub(crate) fn to_radix_2w_size_hint(w: usize) -> usize`[src]

Returns a size hint indicating how many entries of the return value of to_radix_2w are nonzero.

`pub(crate) fn to_radix_2w(&self, w: usize) -> [i8; 43]`[src]

Creates a representation of a Scalar in radix 64, 128 or 256 for use with the Pippenger algorithm. For lower radix, use to_radix_16, which is used by the Straus multi-scalar multiplication. Higher radixes are not supported to save cache space. Radix 256 is near-optimal even for very large inputs.

Radix below 64 or above 256 is prohibited. This method returns digits in a fixed-sized array, excess digits are zeroes. The second returned value is the number of digits.

Scalar representation

Radix $2^w$, with $n = ceil(256/w)$ coefficients in $[-(2^w)/2,(2^w)/2)$, i.e., scalar is represented using digits $a_i$ such that $$ a = a_0 + a_1 2^1w + \cdots + a_{n-1} 2^{w*(n-1)}, $$ with $-2^w/2 \leq a_i < 2^w/2$ for $0 \leq i < (n-1)$ and $-2^w/2 \leq a_{n-1} \leq 2^w/2$.

`pub(crate) fn unpack(&self) -> Scalar52`[src]

Unpack this Scalar to an UnpackedScalar for faster arithmetic.

`pub fn reduce(&self) -> Scalar`[src]

Reduce this Scalar modulo $\ell$.

`pub fn is_canonical(&self) -> bool`[src]

Check whether this Scalar is the canonical representative mod $\ell$.

This is intended for uses like input validation, where variable-time code is acceptable.

// 2^255 - 1, since `from_bits` clears the high bit
let _2_255_minus_1 = Scalar::from_bits([0xff;32]);
assert!(!_2_255_minus_1.is_canonical());

let reduced = _2_255_minus_1.reduce();
assert!(reduced.is_canonical());

Trait Implementations

`impl<'a, 'b> Add<&'b Scalar> for &'a Scalar`[src]

`type Output = Scalar`

The resulting type after applying the + operator.

`fn add(self, _rhs: &'b Scalar) -> Scalar`[src]

`impl<'b> Add<&'b Scalar> for Scalar`[src]

`type Output = Scalar`

The resulting type after applying the + operator.

`fn add(self, rhs: &'b Scalar) -> Scalar`[src]

`impl<'a> Add<Scalar> for &'a Scalar`[src]

`type Output = Scalar`

The resulting type after applying the + operator.

`fn add(self, rhs: Scalar) -> Scalar`[src]

`impl Add<Scalar> for Scalar`[src]

`type Output = Scalar`

The resulting type after applying the + operator.

`fn add(self, rhs: Scalar) -> Scalar`[src]

`impl<'b> AddAssign<&'b Scalar> for Scalar`[src]

`fn add_assign(&mut self, _rhs: &'b Scalar)`[src]

`impl AddAssign<Scalar> for Scalar`[src]

`fn add_assign(&mut self, rhs: Scalar)`[src]

`impl Clone for Scalar`[src]

`fn clone(&self) -> Scalar`[src]

`fn clone_from(&mut self, source: &Self)`1.0.0[src]

`impl ConditionallySelectable for Scalar`[src]

`fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self`[src]

`fn conditional_assign(&mut self, other: &Self, choice: Choice)`[src]

`fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice)`[src]

`impl ConstantTimeEq for Scalar`[src]

`fn ct_eq(&self, other: &Self) -> Choice`[src]

`impl Copy for Scalar`[src]

`impl Debug for Scalar`[src]

`fn fmt(&self, f: &mut Formatter) -> Result`[src]

`impl Default for Scalar`[src]

`fn default() -> Scalar`[src]

`impl Eq for Scalar`[src]

`fn assert_receiver_is_total_eq(&self)`1.0.0[src]

`impl From<u128> for Scalar`[src]

`fn from(x: u128) -> Scalar`[src]

`impl From<u16> for Scalar`[src]

`fn from(x: u16) -> Scalar`[src]

`impl From<u32> for Scalar`[src]

`fn from(x: u32) -> Scalar`[src]

`impl From<u64> for Scalar`[src]

`fn from(x: u64) -> Scalar`[src]

Construct a scalar from the given u64.

Inputs

An u64 to convert to a Scalar.

Returns

A Scalar corresponding to the input u64.

Example

use curve25519_dalek::scalar::Scalar;

let fourtytwo = Scalar::from(42u64);
let six = Scalar::from(6u64);
let seven = Scalar::from(7u64);

assert!(fourtytwo == six * seven);

`impl From<u8> for Scalar`[src]

`fn from(x: u8) -> Scalar`[src]

`impl Index<usize> for Scalar`[src]

`type Output = u8`

The returned type after indexing.