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