net.i2p.crypto.eddsa.math.ed25519

## Class Ed25519LittleEndianEncoding

- java.lang.Object
- - net.i2p.crypto.eddsa.math.Encoding
  - - net.i2p.crypto.eddsa.math.ed25519.Ed25519LittleEndianEncoding

- All Implemented Interfaces:
    Serializable

      public class Ed25519LittleEndianEncoding
      extends Encoding

  Helper class for encoding/decoding from/to the 32 byte representation.

  Reviewed/commented by Bloody Rookie (nemproject@gmx.de)

  See Also:
    Serialized Form

- - ### Field Summary

    - ### Fields inherited from class net.i2p.crypto.eddsa.math.Encoding

      `f`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `Ed25519LittleEndianEncoding()`

  - ### Method Summary

    All Methods Static Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `FieldElement` | `decode(byte[] in)` Decodes a given field element in its 10 byte $2^{25.5}$ representation.
    `byte[]` | `encode(FieldElement x)` Encodes a given field element in its 32 byte representation.
    `boolean` | `isNegative(FieldElement x)` Is the FieldElement negative in this encoding?
    `(package private) static int` | `load_3(byte[] in, int offset)`
    `(package private) static long` | `load_4(byte[] in, int offset)`

    - ### Methods inherited from class net.i2p.crypto.eddsa.math.Encoding

      `setField`

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Constructor Detail

    - #### Ed25519LittleEndianEncoding

          public Ed25519LittleEndianEncoding()

  - ### Method Detail

    - #### decode

          public FieldElement decode(byte[] in)

      Decodes a given field element in its 10 byte $2^{25.5}$ representation.
      Specified by:
        `decode` in class `Encoding`
      Parameters:
        `in` - The 32 byte representation.
      Returns:
        The field element in its $2^{25.5}$ bit representation.

    - #### encode

          public byte[] encode(FieldElement x)

      Encodes a given field element in its 32 byte representation. This is done in two steps:
      1. Reduce the value of the field element modulo $p$.
      2. Convert the field element to the 32 byte representation.

      The idea for the modulo $p$ reduction algorithm is as follows:

      #### Assumption:

      - $p = 2^{255} - 19$
      - $h = h_0 + 2^{25} * h_1 + 2^{(26+25)} * h_2 + \dots + 2^{230} * h_9$ where $0 \le |h_i| \lt 2^{27}$ for all $i=0,\dots,9$.
      - $h \cong r \mod p$, i.e. $h = r + q * p$ for some suitable $0 \le r \lt p$ and an integer $q$.

      Then $q = [2^{-255} * (h + 19 * 2^{-25} * h_9 + 1/2)]$ where $[x] = floor(x)$.

      #### Proof:

      We begin with some very raw estimation for the bounds of some expressions:

      $$ \begin{equation} |h| \lt 2^{230} * 2^{30} = 2^{260} \Rightarrow |r + q * p| \lt 2^{260} \Rightarrow |q| \lt 2^{10}. \\ \Rightarrow -1/4 \le a := 19^2 * 2^{-255} * q \lt 1/4. \\ |h - 2^{230} * h_9| = |h_0 + \dots + 2^{204} * h_8| \lt 2^{204} * 2^{30} = 2^{234}. \\ \Rightarrow -1/4 \le b := 19 * 2^{-255} * (h - 2^{230} * h_9) \lt 1/4 \end{equation} $$

      Therefore $0 \lt 1/2 - a - b \lt 1$.

      Set $x := r + 19 * 2^{-255} * r + 1/2 - a - b$. Then:

      $$ 0 \le x \lt 255 - 20 + 19 + 1 = 2^{255} \\ \Rightarrow 0 \le 2^{-255} * x \lt 1. $$

      Since $q$ is an integer we have

      $$ [q + 2^{-255} * x] = q \quad (1) $$

      Have a closer look at $x$:

      $$ \begin{align} x &= h - q * (2^{255} - 19) + 19 * 2^{-255} * (h - q * (2^{255} - 19)) + 1/2 - 19^2 * 2^{-255} * q - 19 * 2^{-255} * (h - 2^{230} * h_9) \\ &= h - q * 2^{255} + 19 * q + 19 * 2^{-255} * h - 19 * q + 19^2 * 2^{-255} * q + 1/2 - 19^2 * 2^{-255} * q - 19 * 2^{-255} * h + 19 * 2^{-25} * h_9 \\ &= h + 19 * 2^{-25} * h_9 + 1/2 - q^{255}. \end{align} $$

      Inserting the expression for $x$ into $(1)$ we get the desired expression for $q$.

      Specified by:
        `encode` in class `Encoding`
      Parameters:
        `x` - the FieldElement to encode
      Returns:
        the $(b-1)$-bit encoding of this FieldElement.

    - #### isNegative

          public boolean isNegative(FieldElement x)

      Is the FieldElement negative in this encoding?

      Return true if $x$ is in $\{1,3,5,\dots,q-2\}$
      Return false if $x$ is in $\{0,2,4,\dots,q-1\}$

      Preconditions:

      - $|x|$ bounded by $1.1*2^{26},1.1*2^{25},1.1*2^{26},1.1*2^{25}$, etc.
      Specified by:
        `isNegative` in class `Encoding`
      Parameters:
        `x` - the FieldElement to check
      Returns:
        true if $x$ is in $\{1,3,5,\dots,q-2\}$, false otherwise.

    - #### load_3

          static int load_3(byte[] in,
                            int offset)

    - #### load_4

          static long load_4(byte[] in,
                             int offset)