Home | History | Annotate | Download | only in securegcm 
      1 /* Copyright 2018 Google LLC
      2  *
      3  * Licensed under the Apache License, Version 2.0 (the "License");
      4  * you may not use this file except in compliance with the License.
      5  * You may obtain a copy of the License at
      6  *
      7  *     https://www.apache.org/licenses/LICENSE-2.0
      8  *
      9  * Unless required by applicable law or agreed to in writing, software
     10  * distributed under the License is distributed on an "AS IS" BASIS,
     11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12  * See the License for the specific language governing permissions and
     13  * limitations under the License.
     14  */
     15 package com.google.security.cryptauth.lib.securegcm;
     16 
     17 import static java.math.BigInteger.ONE;
     18 import static java.math.BigInteger.ZERO;
     19 
     20 import com.google.common.annotations.VisibleForTesting;
     21 
     22 import java.math.BigInteger;
     23 
     24 /**
     25  * Implements the Ed25519 twisted Edwards curve.  See http://ed25519.cr.yp.to/ for more details.
     26  */
     27 public class Ed25519 {
     28 
     29   // Don't instantiate
     30   private Ed25519() { }
     31 
     32   // Curve parameters (http://ed25519.cr.yp.to/)
     33   private static final int HEX_RADIX = 16;
     34   private static final BigInteger Ed25519_P =
     35       new BigInteger("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", HEX_RADIX);
     36   private static final BigInteger Ed25519_D =
     37       new BigInteger("52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3", HEX_RADIX);
     38 
     39   // Helps to do fast addition k = 2*d
     40   private static final BigInteger Ed25519_K =
     41       new BigInteger("2406D9DC56DFFCE7198E80F2EEF3D13000E0149A8283B156EBD69B9426B2F159", HEX_RADIX);
     42 
     43   // Identity point in extended representation (0, 1, 1, 0)
     44   static final BigInteger[] IDENTITY_POINT = new BigInteger[] {ZERO, ONE, ONE, ZERO};
     45 
     46   // Helps for reading coordinate type in point representation
     47   private static final int X = 0;
     48   private static final int Y = 1;
     49   private static final int Z = 2;
     50   private static final int T = 3;
     51 
     52   // Number of bits that we need to represent a point.  Realistically, we only need 255, but using
     53   // 256 doesn't hurt.
     54   private static final int POINT_SIZE_BITS = 256;
     55 
     56   /**
     57    * Returns the result of multiplying point p by scalar k. A point is represented as a BigInteger
     58    * array of length 2 where the first element (at index 0) is the X coordinate and the second
     59    * element (at index 1) is the Y coordinate.
     60    */
     61   public static BigInteger[] scalarMultiplyAffinePoint(BigInteger[] p, BigInteger k)
     62       throws Ed25519Exception {
     63     return toAffine(scalarMultiplyExtendedPoint(toExtended(p), k));
     64   }
     65 
     66   /**
     67    * Returns the sum of two points in affine representation. A point is represented as a BigInteger
     68    * array of length 2 where the first element (at index 0) is the X coordinate and the second
     69    * element (at index 1) is the Y coordinate.
     70    */
     71   public static BigInteger[] addAffinePoints(BigInteger[] p1, BigInteger[] p2)
     72       throws Ed25519Exception {
     73     return toAffine(addExtendedPoints(toExtended(p1), toExtended(p2)));
     74   }
     75 
     76   /**
     77    * Returns the result of subtracting p2 from p1 (i.e., p1 - p2) in affine representation. A point
     78    * is represented as a BigInteger array of length 2 where the first element (at index 0) is the X
     79    * coordinate and the second element (at index 1) is the Y coordinate.
     80    */
     81   public static BigInteger[] subtractAffinePoints(BigInteger[] p1, BigInteger[] p2)
     82       throws Ed25519Exception {
     83     return toAffine(subtractExtendedPoints(toExtended(p1), toExtended(p2)));
     84   }
     85 
     86   /**
     87    * Validates that a given point in affine representation is on the curve and is positive.
     88    * @throws Ed25519Exception if the point does not validate
     89    */
     90   public static void validateAffinePoint(BigInteger[] p) throws Ed25519Exception {
     91     checkPointIsInAffineRepresentation(p);
     92 
     93     BigInteger x = p[X];
     94     BigInteger y = p[Y];
     95 
     96     if (x.signum() != 1 || y.signum() != 1) {
     97       throw new Ed25519Exception("Point encoding must use only positive integers");
     98     }
     99 
    100     if ((x.compareTo(Ed25519_P) >= 0) || (y.compareTo(Ed25519_P) >= 0)) {
    101       throw new Ed25519Exception("Point lies outside of the expected field");
    102     }
    103 
    104     BigInteger xx = x.multiply(x);
    105     BigInteger yy = y.multiply(y);
    106     BigInteger lhs = xx.negate().add(yy).mod(Ed25519_P);                           // -x*x + y*y
    107     BigInteger rhs = ONE.add(Ed25519_D.multiply(xx).multiply(yy)).mod(Ed25519_P);  // 1 + d*x*x*y*y
    108 
    109     if (!lhs.equals(rhs)) {
    110       throw new Ed25519Exception("Point does not lie on the expected curve");
    111     }
    112   }
    113 
    114   /**
    115    * Returns the result of multiplying point p by scalar k
    116    */
    117   static BigInteger[] scalarMultiplyExtendedPoint(BigInteger[] p, BigInteger k)
    118       throws Ed25519Exception {
    119     checkPointIsInExtendedRepresentation(p);
    120     if (k == null) {
    121       throw new Ed25519Exception("Can't multiply point by null");
    122     }
    123 
    124     if (k.bitLength() > POINT_SIZE_BITS) {
    125       throw new Ed25519Exception(
    126           "Refuse to multiply point by scalar with more than " + POINT_SIZE_BITS + " bits");
    127     }
    128 
    129     // Perform best effort time-constant accumulation
    130     BigInteger[] q = IDENTITY_POINT;
    131     BigInteger[] r = IDENTITY_POINT;
    132     BigInteger[] doubleAccumulator = p;
    133     for (int i = 0; i < POINT_SIZE_BITS; i++) {
    134       if (k.testBit(i)) {
    135         q = addExtendedPoints(q, doubleAccumulator);
    136       } else {
    137         r = addExtendedPoints(q, doubleAccumulator);
    138       }
    139       if (i < POINT_SIZE_BITS - 1) {
    140         doubleAccumulator = doubleExtendedPoint(doubleAccumulator);
    141       }
    142     }
    143 
    144     // Not needed, but we're just trying to fool the compiler into not optimizing away r
    145     r = subtractExtendedPoints(r, r);
    146     q = addExtendedPoints(q, r);
    147     return q;
    148   }
    149 
    150   /**
    151    * Returns the doubling of a point in extended representation
    152    */
    153   private static BigInteger[] doubleExtendedPoint(BigInteger[] p) throws Ed25519Exception {
    154     // The Edwards curve is complete, so we can just add a point to itself.
    155     // Note that the currently best known algorithms for doubling have the same order as addition.
    156     // https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
    157     checkPointIsInExtendedRepresentation(p);
    158 
    159     BigInteger c = p[T].pow(2).multiply(Ed25519_K);
    160     BigInteger d = p[Z].pow(2).shiftLeft(1);
    161     BigInteger e = p[Y].multiply(p[X]).shiftLeft(2);
    162     BigInteger f = d.subtract(c);
    163     BigInteger g = d.add(c);
    164     BigInteger h = p[Y].pow(2).add(p[X].pow(2)).shiftLeft(1);
    165 
    166     return new BigInteger[] {
    167         e.multiply(f).mod(Ed25519_P),
    168         g.multiply(h).mod(Ed25519_P),
    169         f.multiply(g).mod(Ed25519_P),
    170         e.multiply(h).mod(Ed25519_P)
    171     };
    172   }
    173 
    174   /**
    175    * Returns the result of subtracting p2 from p1 (p1 - p2)
    176    */
    177   static BigInteger[] subtractExtendedPoints(BigInteger[] p1, BigInteger[] p2)
    178       throws Ed25519Exception {
    179     checkPointIsInExtendedRepresentation(p1);
    180     checkPointIsInExtendedRepresentation(p2);
    181 
    182     return addExtendedPoints(p1, new BigInteger[] {p2[X].negate(), p2[Y], p2[Z], p2[T].negate()});
    183   }
    184 
    185   /**
    186    * Returns the sum of two points in extended representation
    187    * Uses: https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3
    188    */
    189   static BigInteger[] addExtendedPoints(BigInteger[] p1, BigInteger[] p2)
    190       throws Ed25519Exception {
    191     checkPointIsInExtendedRepresentation(p1);
    192     checkPointIsInExtendedRepresentation(p2);
    193 
    194     BigInteger a = p1[Y].subtract(p1[X]).multiply(p2[Y].subtract(p2[X]));
    195     BigInteger b = p1[Y].add(p1[X]).multiply(p2[Y].add(p2[X]));
    196     BigInteger c = p1[T].multiply(Ed25519_K).multiply(p2[T]);
    197     BigInteger d = p1[Z].add(p1[Z]).multiply(p2[Z]);
    198     BigInteger e = b.subtract(a);
    199     BigInteger f = d.subtract(c);
    200     BigInteger g = d.add(c);
    201     BigInteger h = b.add(a);
    202 
    203     return new BigInteger[] {
    204         e.multiply(f).mod(Ed25519_P),
    205         g.multiply(h).mod(Ed25519_P),
    206         f.multiply(g).mod(Ed25519_P),
    207         e.multiply(h).mod(Ed25519_P)
    208     };
    209   }
    210 
    211   /**
    212    * Converts a point in affine representation to extended representation
    213    */
    214   @VisibleForTesting
    215   static BigInteger[] toExtended(BigInteger[] p) throws Ed25519Exception {
    216     checkPointIsInAffineRepresentation(p);
    217 
    218     return new BigInteger[] {p[X], p[Y], ONE, p[X].multiply(p[Y]).mod(Ed25519_P)}; // x, y, 1, x*y
    219   }
    220 
    221   /**
    222    * Converts a point in extended representation to affine representation
    223    */
    224   @VisibleForTesting
    225   static BigInteger[] toAffine(BigInteger[] p) throws Ed25519Exception {
    226     checkPointIsInExtendedRepresentation(p);
    227 
    228     return new BigInteger[] {p[X].multiply(p[Z].modInverse(Ed25519_P)).mod(Ed25519_P), // x = X / Z
    229         p[Y].multiply(p[Z].modInverse(Ed25519_P)).mod(Ed25519_P)};                     // y = Y / Z
    230   }
    231 
    232   /**
    233    * Checks that a given point is in the extended representation
    234    * @throws Ed25519Exception if the point is not in the extended representation
    235    */
    236   @VisibleForTesting
    237   static void checkPointIsInExtendedRepresentation(BigInteger[] p) throws Ed25519Exception {
    238     if (p == null || p.length != 4 || p[X] == null || p[Y] == null || p[Z] == null
    239         || p[T] == null) {
    240       throw new Ed25519Exception("Point is not in extended representation");
    241     }
    242   }
    243 
    244   /**
    245    * Checks that a given point is in the affine representation
    246    * @throws Ed25519Exception if the point is not in the affine representation
    247    */
    248   @VisibleForTesting
    249   static void checkPointIsInAffineRepresentation(BigInteger[] p) throws Ed25519Exception {
    250     if (p == null || p.length != 2 || p[X] == null || p[Y] == null) {
    251       throw new Ed25519Exception("Point is not in affine representation");
    252     }
    253   }
    254 
    255   /**
    256    * Represents an unrecoverable error that has occurred while performing a curve operation.
    257    */
    258   public static class Ed25519Exception extends Exception {
    259     public Ed25519Exception(String message) {
    260       super(message);
    261     }
    262 
    263     public Ed25519Exception(Exception e) {
    264       super(e);
    265     }
    266 
    267     public Ed25519Exception(String message, Exception e) {
    268       super(message, e);
    269     }
    270   }
    271 }
    272