net.i2p.crypto.eddsa.math.ed25519

Class Ed25519LittleEndianEncoding

java.lang.Object

net.i2p.crypto.eddsa.math.Encoding

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

Constructors

Constructor and Description
Ed25519LittleEndianEncoding()

Method Summary

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?

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:

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.

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,\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.