path: root/src/main/java/org/gnunet/util/crypto/Ed25519.java

/*
 This file is part of GNUnet.
  (C) 2012, 2013 Christian Grothoff (and other contributing authors)

  GNUnet is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published
  by the Free Software Foundation; either version 3, or (at your
  option) any later version.

  GNUnet is distributed in the hope that it will be useful, but
  WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with GNUnet; see the file COPYING.  If not, write to the
  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  Boston, MA 02111-1307, USA.
 */

package org.gnunet.util.crypto;


import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

/**
 * Java-only implementation of arithmetic on DJBs Ed25519.
 * Very, very slow.
 */
public class Ed25519 {
    /**
     * The curve parameter b.
     */
    public static final int b = 256;
    /**
     * curve parameter q =  2^255-19
     */
    public static final BigInteger q = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564819949");
    /**
     * q-2
     */
    private static final BigInteger qm2 = q.subtract(BigInteger.valueOf(2));
    /**
     * q+3
     */
    private static final BigInteger qp3 = q.add(BigInteger.valueOf(3));
    /**
     * The l parameter (a prime, order of the base point B).
     */
    public static final BigInteger l = new BigInteger("7237005577332262213973186563042994240857116359379907606001950938285454250989");
    /**
     * The d parameter (a field element).
     */
    private static final BigInteger d = new BigInteger("-4513249062541557337682894930092624173785641285191125241628941591882900924598840740");
    /**
     * ???
     */
    private static final BigInteger I = new BigInteger("19681161376707505956807079304988542015446066515923890162744021073123829784752");
    /**
     * x-coordinate of the base point
     */
    private static final BigInteger Bx = new BigInteger("15112221349535400772501151409588531511454012693041857206046113283949847762202");
    /**
     * x-coordinate of the base point.
     * Corresponds to '9' on Curve25519 in montgomery form
     */
    private static final BigInteger By = new BigInteger("46316835694926478169428394003475163141307993866256225615783033603165251855960");
    /**
     * The chosen base point of order l.
     */
    public static final Ed25519 B = new Ed25519(Bx.mod(q),By.mod(q));

    /**
     * Mask where only the first 255 bits are set.
     */
    private static final BigInteger mask255 = BigInteger.ONE.shiftLeft(255).subtract(BigInteger.ONE);

    /**
     * First coordinate (x) of this point.
     */
    BigInteger P0;

    /**
     * Second coordinate (y) of this point.
     */
    BigInteger P1;

    /**
     * Create a curve point from its coordinates.
     * @param P0 x-coordinate
     * @param P1 y-coordinate
     */
    public Ed25519(BigInteger P0, BigInteger P1) {
        this.P0 = P0;
        this.P1 = P1;
    }

    /**
     * Create a curve point from its string representation.
     * Note that returned point is not necessarily a valid
     * point.
     *
     * @param s the string representation
     * @return a curve point corresponsing to 's'
     */
    public static Ed25519 decode(byte[] s) {
        BigInteger y = decodeScalar(s);
        BigInteger x = recoverX(y);
        if ((x.testBit(0)?1:0) != bit(s, b-1)) {
            x = q.subtract(x);
        }
        Ed25519 v = new Ed25519(x, y);
        return v;
    }

    /**
     * Get the i'th bit of a byte array
     *
     * @param h byte array
     * @param i bit index
     * @return value of the i'th bit in h
     */
    private static int bit(byte[] h, int i) {
        return h[i/8] >> (i%8) & 1;
    }

    /**
     * Recover the (positive) x-coordinate from y.
     *
     * @param y the y coordinate
     * @return positive x-coordinate
     */
    public static BigInteger recoverX(BigInteger y) {
        BigInteger y2 = y.multiply(y);
        BigInteger xx = (y2.subtract(BigInteger.ONE)).multiply(inv(d.multiply(y2).add(BigInteger.ONE)));
        BigInteger x = xx.modPow(qp3.divide(BigInteger.valueOf(8)), q);
        if (!x.multiply(x).subtract(xx).mod(q).equals(BigInteger.ZERO))
            x = (x.multiply(I).mod(q));
        if (!x.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO))
            x = q.subtract(x);
        return x;
    }

    /**
     * Computes the multiplicative inverse of x modulo q using Euler's theorem.
     *
     * @param x the group element to invert
     * @return the inverse of x modulo q
     */
    private static BigInteger inv(BigInteger x) {
        return x.modPow(qm2, q);
    }

    /**
     * Twisted edwards curve addition law.
     *
     * @param other other point
     * @return this + other
     */
    public Ed25519 add(Ed25519 other) {
        BigInteger x1 = this.P0;
        BigInteger y1 = this.P1;
        BigInteger x2 = other.P0;
        BigInteger y2 = other.P1;
        BigInteger dtemp = d.multiply(x1).multiply(x2).multiply(y1).multiply(y2);
        BigInteger x3 = ((x1.multiply(y2)).add((x2.multiply(y1)))).multiply(inv(BigInteger.ONE.add(dtemp)));
        BigInteger y3 = ((y1.multiply(y2)).add((x1.multiply(x2)))).multiply(inv(BigInteger.ONE.subtract(dtemp)));
        return new Ed25519(x3.mod(q), y3.mod(q));
    }

    public boolean isIdentity() {
        return P0.mod(q).equals(BigInteger.ZERO) && P1.mod(q).equals(BigInteger.ONE);
    }

    /**
     * Multiply this point by a scalar value.
     *
     * @param e scalar factor
     * @return this*e
     */
    public Ed25519 scalarmult(BigInteger e) {
        if (e.equals(BigInteger.ZERO)) {
            return new Ed25519(BigInteger.ZERO, BigInteger.ONE);
        }
        Ed25519 Q = scalarmult(e.shiftRight(1));
        Q = Q.add(Q);
        if (e.testBit(0)) Q = Q.add(this);
        return Q;
    }

    /**
     * Decode an integer from it's little endian byte array form.
     * Takes a 32-byte array. The highest order bit is masked out.
     *
     * @param s string representation of a scalar
     * @return scalar represented by 's'
     */
    public static BigInteger decodeScalar(byte[] s) {
        if (s.length != 32) {
            throw new AssertionError();
        }
        // convert 's' to big endian
        byte[] out = new byte[s.length];
        for (int i=0; i < s.length;i++) {
            out[i] = s[s.length-1-i];
        }
        return new BigInteger(1, out).and(mask255);
    }

    /**
     * Encode a scalar to little endian byte array form.
     * The resulting array is always 32 bytes large.
     *
     * @param n scalar to encode
     * @return byte representation of 'n'
     */
    public static byte[] encodeScalar(BigInteger n) {
        byte[] in = n.and(mask255).toByteArray();
        if (in.length > 32) {
            throw new AssertionError("size too big: " + in.length);
        }
        byte[] full = new byte[32];
        // reverse 'in' and copy to the beginning of 'full'
        for (int i = 0; i < in.length; i++) {
            full[in.length - i - 1] = in[i];
        }
        return full;
    }

    /**
     * Compress end encode a point on the curve.
     *
     * @return compressed and encoded point
     */
    public byte[] encode() {
        byte[] out = encodeScalar(P1);
        out[out.length-1] |= (P0.testBit(0) ? (byte) 0x80 : 0);
        return out;
    }

    /**
     * Hash the data in m and return 2^h(m)
     *
     * @param m data to hash
     * @return 2^h(m)
     */
    static BigInteger Hint(byte[] m) {
        MessageDigest sha512;
        try {
            sha512 = MessageDigest.getInstance("SHA-512");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("crypto algorithm required but not provided");
        }
        final byte[] h = sha512.digest(m);
        // reverse h
        for (int i = 0; i < 32; i++) {
            byte tmp = h[i];
            h[i] = h[63 - i];
            h[63 - i] = tmp;
        }
        return new BigInteger(1, h);
    }

    /**
     * Check whether this point is on the curve, and thus valid.
     *
     * @return whether is point is on the curve
     */
    public boolean isOnCurve() {
        BigInteger x = P0;
        BigInteger y = P1;
        BigInteger xx = x.multiply(x);
        BigInteger yy = y.multiply(y);
        BigInteger dxxyy = d.multiply(yy).multiply(xx);
        return xx.negate().add(yy).subtract(BigInteger.ONE).subtract(dxxyy).mod(q).equals(BigInteger.ZERO);
    }

    @Override
    public String toString() {
        return "(" + P0.toString() + ", " + P1.toString() + ")";
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Ed25519 ed25519 = (Ed25519) o;

        if (!P0.equals(ed25519.P0)) return false;
        if (!P1.equals(ed25519.P1)) return false;

        return true;
    }

    @Override
    public int hashCode() {
        int result = P0.hashCode();
        result = 31 * result + P1.hashCode();
        return result;
    }
}