path: root/src/main/java/org/gnunet/util/CryptoECC.java

package org.gnunet.util;

import org.gnunet.construct.FixedSizeIntegerArray;
import org.gnunet.construct.Message;
import org.gnunet.construct.ProtocolViolationException;
import org.gnunet.construct.UInt32;

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

/**
 * Implementation of the Ed25519 public-key signature system.
 * Original version written and placed into the public domain by k3d3 (https://github.com/k3d3/ed25519-java).
 * See also http://ed25519.cr.yp.to/.
 */
public class CryptoECC {

    /**
     * Private ECC key.
     */
    public static final class PrivateKey implements Message {
        /**
         * Value of the private key, represents a number modulo q.
         * The number is stored as little endian.
         */
        @FixedSizeIntegerArray(bitSize = 8, signed = false, length = 32)
        public byte[] d;
    }

    /**
     * Public ECC key.
     */
    public static final class PublicKey implements Message {
        /**
         * x-coordinate of the point on the curve.
         * The number is stored as little endian.
         */
        @FixedSizeIntegerArray(bitSize = 8, signed = false, length = 32)
        public byte[] x;

        /**
         * y-coordinate of the point on the curve.
         * The number is stored as little endian.
         */
        @FixedSizeIntegerArray(bitSize = 8, signed = false, length = 32)
        public byte[] y;

    }

    /**
     * ECC Signature.
     */
    public static final class Signature implements Message {
        /**
         * R-value of the signature.
         * The number is stored as little endian.
         */
        @FixedSizeIntegerArray(bitSize = 8, signed = false, length = 32)
        public byte[] r;

        /**
         * S-value of the signature.
         * The number is stored as little endian.
         */
        @FixedSizeIntegerArray(bitSize = 8, signed = false, length = 32)
        public byte[] s;
    }

    // curve parameter b
    private static final int b = 256;
    // curve parameter q
    private static final BigInteger q = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564819949");
    // q-3
    private static final BigInteger qm2 = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564819947");
    // q-3
    private static final BigInteger qp3 = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564819952");
    private static final BigInteger l = new BigInteger("7237005577332262213973186563042994240857116359379907606001950938285454250989");
    private static final BigInteger d = new BigInteger("-4513249062541557337682894930092624173785641285191125241628941591882900924598840740");
    private static final BigInteger I = new BigInteger("19681161376707505956807079304988542015446066515923890162744021073123829784752");
    private static final BigInteger By = new BigInteger("46316835694926478169428394003475163141307993866256225615783033603165251855960");
    private static final BigInteger Bx = new BigInteger("15112221349535400772501151409588531511454012693041857206046113283949847762202");
    private static final BigInteger[] B = {Bx.mod(q),By.mod(q)};
    // 2^255
    private static final BigInteger un = new BigInteger("57896044618658097711785492504343953926634992332820282019728792003956564819967");

    static final private MessageDigest sha512;
    static {
        try {
            sha512 = MessageDigest.getInstance("SHA-512");
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("SHA-512 not available");
        }
    }

    /**
     * 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);
    }

    /**
     * Compute the x-component of a point on our curve from
     * the y-coordinate.
     *
     * @param y the y-coordinate of a point
     * @return the x-coordinate of the point (x,y) on the curve
     */
    private static BigInteger xrecover(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;
    }

    /**
     * Implements the group operation (twisted Edwards addition) on our curve.
     *
     * @param P a point on the curve
     * @param Q another point on the curve
     * @return P+Q
     */
    private static BigInteger[] edwards(BigInteger[] P, BigInteger[] Q) {
        BigInteger x1 = P[0];
        BigInteger y1 = P[1];
        BigInteger x2 = Q[0];
        BigInteger y2 = Q[1];
        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 BigInteger[]{x3.mod(q), y3.mod(q)};
    }

    /**
     * Multiply a point on the curve with a constant.
     *
     * @param P point on the curve
     * @param e constant
     * @return eP
     */
    private static BigInteger[] scalarmult(BigInteger[] P, BigInteger e) {
        if (e.equals(BigInteger.ZERO)) {
            return new BigInteger[]{BigInteger.ZERO, BigInteger.ONE};
        }
        BigInteger[] Q = scalarmult(P, e.shiftRight(1));
        Q = edwards(Q, Q);
        if (e.testBit(0)) Q = edwards(Q, P);
        return Q;
    }

    /**
     * Encode an integer to binary format.
     *
     * @param y integer to encode
     * @return encoded integer as byte array
     */
    private static byte[] encodeint(BigInteger y) {
        byte[] in = y.toByteArray();
        // reverse the array
        for (int i = 0; i < in.length / 2; i++) {
            byte tmp = in[i];
            in[i] = in[in.length - i - 1];
            in[in.length - i - 1] = tmp;
        }
        return in;
    }

    /**
     * Encode a point to binary format.
     *
     * @param P point to encode
     * @return encoded point as byte array
     */
    private static byte[] encodepoint(BigInteger[] P) {
        BigInteger x = P[0];
        BigInteger y = P[1];
        byte[] out = encodeint(y);
        out[out.length-1] |= (x.testBit(0) ? 0x80 : 0);
        return out;
    }

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

    static private BigInteger computePublicKeyCoefficient(PrivateKey sk) {
        byte[] h = sha512.digest(sk.d);
        BigInteger a = BigInteger.valueOf(2).pow(b-2);
        for (int i=3; i < (b - 2); i++) {
            BigInteger apart = BigInteger.valueOf(2).pow(i).multiply(BigInteger.valueOf(bit(h,i)));
            a = a.add(apart);
        }
        return a;
    }

    /**
     * Derive the public key from the private key 'sk',
     *
     * @param sk private key
     * @return public key derived from 'sk'
     */
    static public PublicKey computePublicKey(PrivateKey sk) {
        BigInteger a = computePublicKeyCoefficient(sk);
        BigInteger[] A = scalarmult(B, a);
        PublicKey publicKey = new PublicKey();
        publicKey.x = encodeint(A[0]);
        publicKey.y = encodeint(A[1]);
        return publicKey;
    }

    /**
     * Hash the data in m and return 2^h(m)
     *
     * @param m data to hash
     * @return 2^h(m)
     */
    static private BigInteger Hint(byte[] m) {
        final byte[] h = sha512.digest(m);
        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);
    }

    /**
     * Sign a message.
     *
     * @param m the message to sign
     * @param sk the private (secret) key
     * @param pk the public key, derived from 'sk', but passed as a
     *           parameter for performance reasons
     * @return a signature on m
     */
    public static Signature sign(byte[] m, PrivateKey sk, PublicKey pk) {
        byte[] compressed_pk = encodepoint(new BigInteger[]{decodeint(pk.x), decodeint(pk.y)});
        byte[] h = sha512.digest(sk.d);
        BigInteger a = BigInteger.valueOf(2).pow(b-2);
        for (int i = 3; i < (b - 2); i++) {
            a = a.add(BigInteger.valueOf(2).pow(i).multiply(BigInteger.valueOf(bit(h,i))));
        }
        ByteBuffer rsub = ByteBuffer.allocate((b/8)+m.length);
        rsub.put(h, b/8, b/4-b/8).put(m);
        BigInteger r = Hint(rsub.array());
        BigInteger[] R = scalarmult(B,r);

        Signature sig = new Signature();
        sig.r = encodepoint(R);

        ByteBuffer buf = ByteBuffer.allocate(32 + compressed_pk.length + m.length);
        buf.put(encodepoint(R)).put(compressed_pk).put(m);

        BigInteger S = r.add(Hint(buf.array()).multiply(a)).mod(l);
        sig.s = encodeint(S);

        return sig;
    }

    /**
     * Check if a point is on the curve.
     *
     * @param P point to check
     * @return whether the point P is on the curve
     */
    private static boolean isoncurve(BigInteger[] P) {
        BigInteger x = P[0];
        BigInteger y = P[1];
        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);
    }

    /**
     * Decode an integer from its binary form.
     *
     * @param s the binary form if the integer
     * @return the decoded integer
     */
    private static BigInteger decodeint(byte[] s) {
        byte[] out = new byte[s.length];
        for (int i=0;i<s.length;i++) {
            out[i] = s[s.length-1-i];
        }
        return new BigInteger(out).and(un);
    }

    /**
     * Decode a curve point from its compressed form.
     *
     * @param s the compressed point data
     * @return the uncompressed point, null if not a valid point
     */
    private static BigInteger[] decodepoint(byte[] s) {
        byte[] ybyte = new byte[s.length];
        for (int i=0;i<s.length;i++) {
            ybyte[i] = s[s.length-1-i];
        }
        BigInteger y = new BigInteger(ybyte).and(un);
        BigInteger x = xrecover(y);
        if ((x.testBit(0)?1:0) != bit(s, b-1)) {
            x = q.subtract(x);
        }
        BigInteger[] P = {x,y};
        if (!isoncurve(P))
            return null;
        return P;
    }

    /**
     * Verify the validity of a signature on a message.
     *
     * @param sig signature
     * @param m message
     * @param pk public key of the signature creator
     * @return whether the signature is valid
     */
    public static boolean verify(Signature sig, byte[] m, PublicKey pk) {
        BigInteger[] R = decodepoint(sig.r);
        BigInteger[] A = new BigInteger[]{decodeint(pk.x), decodeint(pk.y)};
        BigInteger S = decodeint(sig.s);
        ByteBuffer Stemp = ByteBuffer.allocate(32 + 32 + m.length);
        Stemp.put(encodepoint(R)).put(encodepoint(A)).put(m);
        BigInteger h = Hint(Stemp.array());
        BigInteger[] ra = scalarmult(B,S);
        BigInteger[] rb = edwards(R,scalarmult(A,h));
        return ra[0].equals(rb[0]) && ra[1].equals(rb[1]);
    }

    /**
     * Derive key material from a public and a private ECC key.
     *
     * @param privateKey private key to use for the ECDH (x)
     * @param publicKey public key to use for the ECDH (yG)
     * @return key material (xyG)
     */
    public static HashCode ecdh(PrivateKey privateKey, PublicKey publicKey) {
        BigInteger[] publicPoint = new BigInteger[]{decodeint(publicKey.x), decodeint(publicKey.y)};
        BigInteger coeff = computePublicKeyCoefficient(privateKey);
        BigInteger[] R = scalarmult(publicPoint, coeff);
        // FIXME: this is *not* equivalent to the GNUnet C implementation, which hashes an s-expr
        sha512.update(R[0].toByteArray());
        return new HashCode(sha512.digest(R[1].toByteArray()));
    }
}