Class Ed25519LittleEndianEncoding


  • public class Ed25519LittleEndianEncoding
    extends Encoding
    Helper class for encoding/decoding from/to the 32 byte representation.

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

    • Constructor Detail

      • Ed25519LittleEndianEncoding

        public Ed25519LittleEndianEncoding()
    • Method Detail

      • encode

        public byte[] encode​(FieldElement x)
        Encodes a given field element in its 32 byte representation. This is done in TWO steps. Step 1: Reduce the value of the field element modulo p. Step 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 = h0 + 2^25 * h1 + 2^(26+25) * h2 + ... + 2^230 * h9 where 0 <= |hi| < 2^27 for all i=0,...,9.
        • h congruent r modulo p, i.e. h = r + q * p for some suitable 0 <= r < p and an integer q.

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

        Proof:

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

        |h| < 2^230 * 2^30 = 2^260 ==> |r + q * p| < 2^260 ==> |q| < 2^10.
         ==> -1/4 <= a := 19^2 * 2^-255 * q < 1/4.
         |h - 2^230 * h9| = |h0 + ... + 2^204 * h8| < 2^204 * 2^30 = 2^234.
         ==> -1/4 <= b := 19 * 2^-255 * (h - 2^230 * h9) < 1/4
        Therefore 0 < 1/2 - a - b < 1.

        Set x := r + 19 * 2^-255 * r + 1/2 - a - b then 0 <= x < 255 - 20 + 19 + 1 = 2^255 ==> 0 <= 2^-255 * x < 1. Since q is an integer we have

        [q + 2^-255 * x] = q        (1)

        Have a closer look at x:

        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 * h9)
           = 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 * h9
           = h + 19 * 2^-25 * h9 + 1/2 - q^255.

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

        Specified by:
        encode in class Encoding
        Returns:
        the (b-1)-bit encoding of this FieldElement.
      • load_3

        static int load_3​(byte[] in,
                          int offset)
      • load_4

        static long load_4​(byte[] in,
                           int offset)
      • 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.
      • isNegative

        public boolean isNegative​(FieldElement x)
        Is the FieldElement negative in this encoding?

        Return true if x is in {1,3,5,...,q-2}
        Return false if x is in {0,2,4,...,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
        Returns:
        true if x is in {1,3,5,...,q-2}, false otherwise.