Ethkit Toolkit

To speed up divsteps_n_matrix when constant-time execution is not required (i.e., not computing modular inverses of secret data), you can implement variable-time optimizations. This involves consolidating multiple iterations of the divstep loop by:

1. Counting trailing zeros: Use count_trailing_zeros to identify how many bits can be shifted out of g at once.
2. Canceling multiple bits: Instead of processing one bit at a time, find a multiple w such that g + w*f has multiple trailing zero bits. This is done by computing w = -g/f mod 2^L, where L is the number of bits to cancel.

This approach significantly reduces the number of loop iterations by processing blocks of bits simultaneously.

# Example of canceling up to 4 bits per step
NEGINV16 = [15, 5, 3, 9, 7, 13, 11, 1] # NEGINV16[n//2] = (-n)^-1 mod 16, for odd n
i = N
while True:
    zeros = min(i, count_trailing_zeros(g))
    eta -= zeros
    g >>= zeros
    i -= zeros
    if i == 0:
        break
    if eta < 0:
        eta, f, g = -eta, g, -f
    
    limit = min(min(eta + 1, i), 4)
    w = (g * NEGINV16[(f & 15) // 2]) % (2**limit)
    g += w * f
    assert g % (2**limit) == 0

The Jacobi symbol $(x | M)$ can be calculated by tracking an extra variable $j$ during the divstep process, where $(x | M) = j imes (g | f)$.

Key Implementation Details:

• Posdivsteps: Because the Jacobi symbol is defined for positive odd integers $M$, but the standard safegcd algorithm allows $f$ and $g$ to be negative, a modified step called posdivstep is used. Instead of (g - f) // 2, it uses (g + f) // 2 when $\delta > 0$ and $g$ is odd.
• Convergence: While posdivstep is empirically observed to converge in logarithmic steps, it lacks a formal proof of convergence. To handle potential non-convergence, the implementation performs a bounded number of steps before falling back to a square-root based Jacobi calculation.
• Constraints:
  • $\text{gcd}(x, M) = 1$ must hold.
  • $x \neq 0$.
  • The termination condition is updated from $g=0$ to $f=1$.

Updates: The updates to $j$ depend on $f$ and $g$ modulo 4 or 8.

To optimize the safegcd algorithm, multiple divsteps can be batched into a single matrix multiplication. Instead of updating the full-size f, g, d, and e variables at every step, the algorithm computes a transition matrix t for N steps using only the bottom N bits of the variables.

The Batching Process:

1. Compute Transition Matrix: Use divsteps_n_matrix to find the combined transition matrix t (scaled by $2^N$) and the new delta based on the bottom $N$ bits of f and g.
2. Update Integers (f, g): Apply the matrix to f and g and perform a single bit-shift (>> N) to account for the $2^N$ scaling. This is efficient because the result is guaranteed to be a multiple of $2^N$.
3. Update Modular Variables (d, e): Apply the matrix to d and e modulo M. This requires a specialized division function div2n which uses a precomputed value Mi = 1/M mod 2^N to perform division by $2^N$ modulo M efficiently.

This approach allows using 64-bit integer arithmetic for the matrix computation (with $N ext{ up to } 62$) while only performing expensive big-integer or modular arithmetic once every $N$ steps.

def modinv(M, Mi, x):
    """Compute the modular inverse of x mod M, given Mi=1/M mod 2^N."""
    assert M & 1
    delta, f, g, d, e = 1, M, x, 0, 1
    while g != 0:
        # Compute the delta and transition matrix t for the next N divsteps
        delta, t = divsteps_n_matrix(delta, f % 2**N, g % 2**N)
        # Apply the transition matrix t to [f, g]:
        f, g = update_fg(f, g, t)
        # Apply the transition matrix t to [d, e]:
        d, e = update_de(d, e, t, M, Mi)
    return (d * f) % M

The safegcd implementation computes the GCD of an odd integer f and any integer g using a series of "division steps" (divsteps). The algorithm maintains a state variable delta (starting at 1) and iteratively transforms f and g until g reaches 0. At that point, |f| is the GCD.

Key properties:

• Constant-time potential: The algorithm only looks at the low-order bits of f and g to decide the next step, making it suitable for constant-time implementations.
• Convergence: The algorithm is guaranteed to converge to g=0.
• Divsteps: Each step involves either making g even (if it is odd) and then dividing g by 2, or simply dividing g by 2 if it is already even.
• Stability: Performing extra divsteps after g=0 does not change the value of f.

def gcd(f, g):
    """Compute the GCD of an odd integer f and another integer g."""
    assert f & 1  # require f to be odd
    delta = 1     # additional state variable
    while g != 0:
        assert f & 1  # f will be odd in every iteration
        if delta > 0 and g & 1:
            delta, f, g = 1 - delta, g, (g - f) // 2
        elif g & 1:
            delta, f, g = 1 + delta, f, (g + f) // 2
        else:
            delta, f, g = 1 + delta, f, (g    ) // 2
    return abs(f)

While ElligatorSwift is often used for x-only encoding, it can be extended to encode full $(x, y)$ coordinates by using the sign of the encoded value $t$ to represent the sign of the y-coordinate. This is useful when both the x and y coordinates must remain unpredictable.

General Approach

To encode the sign of $y$ in the sign of $Y$:

1. Decoding: Use Decode(u, t) to find $(X, Y) = P_u(t)$, then identify the correct $x$ from the set $(u + 4Y^2, \frac{-X}{2Y} - \frac{u}{2}, \frac{X}{2Y} - \frac{u}{2})$ where $g(x)$ is a square. The final $y$ is returned as $(x, y)$ or $(x, -y)$ depending on whether $sign(y) = sign(Y)$.
2. Encoding: Use a $G_{c,u}(x, y)$ function where the sign of $w'$ is decided based on the sign of $y$.

Warning: Do not use this method for x-only points where the y-coordinate is already implicitly defined (e.g., implicitly even). For those cases, use the standard x-only encoder to avoid reintroducing bias.

To achieve fast constant-time operation and avoid side-channel attacks, branches in the divsteps algorithm must be replaced with bitwise operations. This prevents the execution flow from depending on secret input data.

Key Techniques:

1. Conditional Negation: Use the two's complement property ($-v = (v \oplus -1) - (-1)$) to negate values without branching. If $c$ is a mask of $0$ or $-1$, then $(v \oplus c) - c$ results in $v$ if $c=0$ and $-v$ if $c=-1$.
2. Mask Generation: Generate masks using right shifts. For a 64-bit integer, x >> 63 results in $-1$ if $x < 0$ and $0$ if $x \ge 0$.
3. Conditional Addition: Use bitwise AND with a mask to conditionally add a value. For example, g += x & c2 where c2 is $-1$ if a condition is met and $0$ otherwise.

Constant-time divsteps pattern (using $\eta = -\delta$ substitution):

Instead of tracking $\delta$, track $\eta$ to simplify the logic. Incrementing $\delta$ becomes decrementing $\eta$.

# Compute a mask c1 for eta < 0, and compute the conditional negation x of f:
c1 = eta >> 63
x = (f ^ c1) - c1

# Compute a mask c2 for odd g, and conditionally add x to g:
c2 = -(g & 1)
g += x & c2

# Compute a mask c for (eta < 0) and odd (input) g, and conditionally negate eta,
# and add g to f:
c3 = c1 & c2
eta = (eta ^ c3) - c3
f += g & c3

# Incrementing delta corresponds to decrementing eta.
eta -= 1
g >>= 1

The ellswift module introduces a 64-byte public key format designed so that (uniformly random) public keys can be encoded as 64-byte arrays that are computationally indistinguishable from uniform byte arrays.

Key Properties:

• Structure: The encoding is a concatenation of two 32-byte big-endian field elements, $u$ and $t$.
• Content: Together, $u$ and $t$ encode either an x-coordinate on the curve or a full $(x, y)$ point on the curve.
• Functionality: The module provides functions to convert public keys to/from this format, as well as convenience functions for key generation and ECDH that operate directly on these encoded keys.

Conceptual Workflow:

• Decoding: Decodes $u$ and $t$ (applying modulo $p$ if values exceed the field size) and evaluates $F_u(t)$ to produce a valid x-coordinate.
• Encoding: Conceptually involves picking a random field element $u$ and finding a $t$ such that $F_u(t) = x$.