DOCSEARCHbyAlgolia
Submit Docs

curve25519-dalek

repository·main·Indexed 22 days ago

https://github.com/dalek-cryptography/curve25519-dalek

A pure-Rust implementation of group operations on ristretto255 and Curve25519, providing high-performance and secure implementations of elliptic curve cryptography including Ristretto, Ed25519, and X25519. Version 5.0.0 features constant-time logic, memory safety, and support for multiple arithmetic backends (serial, fiat, simd, and avx512). It includes specialized tools for SIMD target features and Lizard bytestring-to-point injection for RistrettoPoint.

Tokens
22.6K
Snippets
58
Records
101
Agent score
78%

What's inside curve25519-dalek

  1. Overview of Dalek elliptic curve cryptography crates

    main

    The Dalek repository provides a suite of pure-Rust crates for elliptic curve cryptography. Depending on your requirements, you should choose the crate that matches your specific cryptographic task:

    • curve25519-dalek: Use this for low-level arithmetic over the Curve25519 and Ristretto elliptic curves and their associated scalars.
    • ed25519-dalek: Use this for implementing the EdDSA digital signature scheme over Curve25519.
    • x25519-dalek: Use this for implementing elliptic curve Diffie-Hellman (ECDH) key exchange over Curve25519.
    • curve25519-dalek-derive: A helper crate providing macros to simplify writing code that uses curve25519-dalek.

  2. What is Lizard encoding and when should I use it?

    main

    Lizard encoding provides an injective map into the Ristretto255 group $\mathcal{R}$.

    While the standard Elligator2 map ($E_2$) maps field elements to Ristretto255 points with a nearly uniform distribution, it is not injective (each point can have up to eight distinct field element preimages). Lizard solves this by "tagging" the input to ensure a unique mapping.

    Use Case: Use Lizard when you need to encrypt data where plaintexts are curve points, such as in the ElGamal encryption scheme, and you require an easy-to-compute inverse to decode the points back into plaintexts.

  3. Handle weak public keys in batch verification

    main

    When using verify_batch(), be aware that it does not perform weak key testing to maintain high throughput. Because verify_batch() multiplies verification equations by random coefficients, a weak public key (a low-order point) might cause a failed forgery to appear valid in one batch but fail in another (approximately a 21% chance of inconsistent results across distinct batches containing the same forgery).

    To prevent this behavior and ensure security against weak public keys, you should manually check your inputs using VerifyingKey::is_weak before including them in a batch.

    // Before calling verify_batch, check if keys are weak
if verifying_key.is_weak() {
    // Handle weak key error
}

  4. Understand AVX512-IFMA instructions

    main

    AVX512-IFMA is an extension to AVX-512 that provides specialized instructions for high-performance integer multiplication. It consists of two primary instructions that operate on 64-bit lanes of source vectors, computing 104-bit products from 52-bit unsigned integers and adding the results to 64-bit accumulators:

    • vpmadd52luq: Adds the low 52 product bits to the destination.
    • vpmadd52huq: Adds the high 52 product bits to the destination.

    These instructions are available via the AVX512VL (vector length) extension, allowing them to be used with 128, 256, or 512-bit operands. A key advantage is that they allow vectorized operations to perform $64 imes 64 \rightarrow 128$-bit style multiplication (via 52-bit chunks), which was previously only available in serial code.

  5. Invert the Elligator2 isogeny $\theta$ and its projection $\hat{\theta}$

    main

    The 2-isogeny $\theta$ maps the Jacobi quartic $\mathcal{J}$ to the even points on the Edwards curve $\mathcal{E}$. To invert this for a given Edwards point $(x,y)$:

    1. Calculate $s_0 = \sqrt{\frac{1-y}{1+y}}$ (yielding two values: $s_0$ and $-s_0$).
    2. Calculate $t_0 = \frac{2s_0}{x\sqrt{c}}$, where $c = a-d$ (for Ristretto255, $a=-1$, so $c = -1-d$).

    For projective coordinates $[X:Y:Z]$, the formula is: $$s_0 = \sqrt{\frac{Z-Y}{Z+Y}},\qquad t_0 = \frac{2Z}{X\sqrt{c}}\sqrt{\frac{Z-Y}{Z+Y}}$$

    The projected map $\hat{\theta}$ is 1-to-1. Its inverse $\hat{\theta}^{-1}$ maps an equivalence class in $[2]\mathcal{E}/\mathcal{E}[2]$ back to a coset in $\mathcal{J}/\mathcal{J}[2]$:

    $$\hat{\theta}^{-1}(\lbrace [X:Y:Z], [-X:-Y:Z] \rbrace) = \left\lbrace (s_0, t_0), (-s_0, -t_0), \left(\frac{1}{s_0}, -\frac{t_0}{s_0^2}\right), \left(-\frac{1}{s_0}, \frac{t_0}{s_0^2}\right) \right\rbrace = (s_0,t_0) + \mathcal{J}[2]$$

  6. Avoid overflow in doubling computations via sign flipping

    main

    To perform efficient doubling without intermediate reductions, the implementation manages bit-excesses ($b$) in the field element limbs.

    Constraints:

    • Multiplication routines require one input to be bounded by $b < 1.75$ (to fit a multiplication by 19 into 32 bits) and the other by $b < 2.5$.

    The Strategy: Standard doubling formulas for $(S_5, S_6, S_8, S_9)$ can result in bit-excesses that exceed these bounds (e.g., $S_8$ reaching $b < 2.33$ and $S_9$ reaching $b < 2.01$), making it impossible to satisfy the $b < 1.75$ requirement for one of the multiplicands in the subsequent products ($X_3, Y_3, Z_3, T_3$).

    To solve this, the implementation flips the sign of $S_4 = S_0^2$ during squaring, producing $S_4' = -S_4 \pmod p$. This adjustment reduces the bit-excesses for the resulting coefficients to:

    • $S_5 < 1.01$
    • $S_6 < 1.60$
    • $S_8 < 2.33$
    • $S_9 < 1.60$

    With these bounds, all required products ($X_3, Y_3, Z_3, T_3$) can be computed such that one multiplicand is always $b < 2.5$ and the other is $b < 1.75$, avoiding the need for costly intermediate reductions.

  7. Choosing a radix for IFMA multiplication

    main

    When using IFMA instructions, the choice of radix $r$ (the base used to represent the multiprecision integer) is critical. Since IFMA instructions take 52-bit inputs, the radix must satisfy $r \leq 52$.

    • Native Radix ($r = 52$): This is the optimal choice. The product of two limbs $x_i, y_j$ splits exactly at the 52-bit boundary. The low 52 bits accumulate into $z_{i+j}$ and the high 52 bits accumulate into $z_{i+j+1}$ with no additional shifts or multiplications required.
    • Smaller Radix ($r < 52$): If a smaller radix is used (e.g., $r = 52 - k$), the product bits do not align with the radix boundaries. The high part of the product must be shifted (multiplied by $2^k$) before it can be accumulated into the next limb, adding computational overhead.

  8. Understand the safety and security model

    main

    curve25519-dalek is designed with several security guarantees:

    • Illegal states are unrepresentable: Types like EdwardsPoint and RistrettoPoint are guaranteed to hold valid points on their respective curves/groups.
    • Constant-time logic: Most operations use constant-time logic (no secret-dependent branches or memory accesses) to prevent side-channel attacks. The subtle crate is used to provide optimization barriers.
    • Memory safety: The implementation is memory-safe with minimal unsafe code. The SIMD backend uses unsafe internally for intrinsics, but this is only invoked when appropriate CPU features are detected.
    • Zeroization: Heap-allocated buffers containing potentially secret data are explicitly zeroed before release. Note that the library does not attempt to zero stack data.
    • Formal Verification: A significant portion of the library (including functions used by Signal Messenger) has been formally verified using Verus.

  9. Understand the AVX512-IFMA implementation strategy

    main

    The curve25519-dalek project uses an AVX512-IFMA (Integer Fused Multiply-Add) implementation for vectorized point operations. This implementation optimizes performance by using a specific radix and a doubly-redundant representation to maximize Instruction Level Parallelism (ILP).

    Key Design Choices

    • Radix Selection: Instead of a standard radix (like $2^{52}$), the implementation uses radix $r = 51$. This allows each limb to store a carry bit without requiring a sequential normalization carry chain. This enables parallel computation of carryouts, limb reductions, and carryins.
    • Doubly-Redundant Representation: During multiplication, product terms are accumulated into a representation where each digit has two limbs. This avoids the need to normalize limbs back to a canonical representation after every operation, allowing the implementation to "close the loop" using partial reductions.
    • Reduction Modulo $p$: For the field $p = 2^{255} - 19$, the reduction leverages the identity $2^{255} \equiv 19 \pmod p$. High-order terms ($z_5 \dots z_9$) are reduced onto the lower terms ($z_0 \dots z_4$) using IFMA operations rather than expensive vpmullq instructions, maintaining high throughput.
    • Type-Safe Unreduced Limbs: To prevent errors, the implementation tracks the reduction state using the Rust type system. This ensures that limbs which have not yet been reduced to fit the required bit-width are not accidentally used as inputs to subsequent multiplications.

  10. How batch signature verification works

    main

    When the batch feature is enabled, you can use verify_batch to verify many signatures simultaneously. This is significantly faster than verifying signatures individually.

    Key details:

    • It uses deterministic randomness by hashing inputs (using merlin) to generate random coefficients.
    • Requirement: Batch verification requires heap allocation (alloc), so it cannot be used in no_std environments without an allocator.

  11. Security properties of Lizard encoding

    main

    Lizard encoding is an injection with overwhelming probability.

    Probability of failure:

    • The chance of hitting an input that cannot be decoded is approximately $1$ in $2^{122}$.
    • There are $125$ check bits used to distinguish the correct preimage among at most eight candidates.
    • Even assuming seven other preimages, the probability of one passing the check is approximately $2^{-122.192}$.
    • Statistically, there is a 99.9% probability that there are fewer than 80 "bad" inputs in the entire domain.

  12. How Lizard computes Ristretto preimages

    main

    Lizard implements the inversion of the Elligator2 map for Ristretto255. The process follows these conceptual steps:

    1. Find Jacobi Quartic points: Use to_jacobi_quartic_ristretto to find four non-dual Jacobi points $(s_i, t_i)$ that map to the Ristretto point. These are derived using field operations and a single square root calculation for efficiency.
    2. Derive all eight preimages: The first four points are returned by the initial function; the remaining four are derived via elligator_ristretto_flavor_inverse.
    3. Compute Field Element Preimages: Use JacobiPoint::e_inv() to invert the mapping from the Jacobi Quartic domain back to the field $\mathbb{F}$.

    This implementation is designed to be efficient and constant-time by performing necessary computations (like the two cases for $e^{-1}$) simultaneously.