net.i2p.crypto.eddsa.math.ed25519
Class Ed25519LittleEndianEncoding

java.lang.Object
  extended by net.i2p.crypto.eddsa.math.Encoding
      extended by net.i2p.crypto.eddsa.math.ed25519.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)


Field Summary
 
Fields inherited from class net.i2p.crypto.eddsa.math.Encoding
f
 
Constructor Summary
Ed25519LittleEndianEncoding()
           
 
Method Summary
 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

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:

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: