tx-signer/src/main/java/com/google/crypto/tink/subtle/Curve25519.java

   1 // Copyright 2017 Google Inc.\r
   2 //\r
   3 // Licensed under the Apache License, Version 2.0 (the "License");\r
   4 // you may not use this file except in compliance with the License.\r
   5 // You may obtain a copy of the License at\r
   6 //\r
   7 //      http://www.apache.org/licenses/LICENSE-2.0\r
   8 //\r
   9 // Unless required by applicable law or agreed to in writing, software\r
  10 // distributed under the License is distributed on an "AS IS" BASIS,\r
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  12 // See the License for the specific language governing permissions and\r
  13 // limitations under the License.\r
  14 //\r
  15 ////////////////////////////////////////////////////////////////////////////////\r
  16 \r
  17 package com.google.crypto.tink.subtle;\r
  18 \r
  19 import com.google.crypto.tink.annotations.Alpha;\r
  20 \r
  21 import java.security.InvalidKeyException;\r
  22 import java.util.Arrays;\r
  23 \r
  24 /**\r
  25  * This class implements point arithmetic on the elliptic curve <a\r
  26  * href="https://cr.yp.to/ecdh/curve25519-20060209.pdf">Curve25519</a>.\r
  27  *\r
  28  * <p>This class only implements point arithmetic, if you want to use the ECDH Curve25519 function,\r
  29  * please checkout {@link X25519}.\r
  30  *\r
  31  * <p>This implementation is based on <a\r
  32  * href="https://github.com/agl/curve25519-donna/blob/master/curve25519-donna.c">curve255-donna C\r
  33  * implementation</a>.\r
  34  */\r
  35 @Alpha\r
  36 final class Curve25519 {\r
  37     // https://cr.yp.to/ecdh.html#validate doesn't recommend validating peer's public key. However,\r
  38     // validating public key doesn't harm security and in certain cases, prevents unwanted edge\r
  39     // cases.\r
  40     // As we clear the most significant bit of peer's public key, we don't have to include public keys\r
  41     // that are larger than 2^255.\r
  42     static final byte[][] BANNED_PUBLIC_KEYS =\r
  43             new byte[][]{\r
  44                     // 0\r
  45                     new byte[]{\r
  46                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  47                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  48                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  49                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  50                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  51                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  52                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  53                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00\r
  54                     },\r
  55                     // 1\r
  56                     new byte[]{\r
  57                             (byte) 0x01, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  58                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  59                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  60                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  61                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  62                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  63                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  64                             (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00,\r
  65                     },\r
  66                     // 325606250916557431795983626356110631294008115727848805560023387167927233504\r
  67                     new byte[]{\r
  68                             (byte) 0xe0, (byte) 0xeb, (byte) 0x7a, (byte) 0x7c,\r
  69                             (byte) 0x3b, (byte) 0x41, (byte) 0xb8, (byte) 0xae,\r
  70                             (byte) 0x16, (byte) 0x56, (byte) 0xe3, (byte) 0xfa,\r
  71                             (byte) 0xf1, (byte) 0x9f, (byte) 0xc4, (byte) 0x6a,\r
  72                             (byte) 0xda, (byte) 0x09, (byte) 0x8d, (byte) 0xeb,\r
  73                             (byte) 0x9c, (byte) 0x32, (byte) 0xb1, (byte) 0xfd,\r
  74                             (byte) 0x86, (byte) 0x62, (byte) 0x05, (byte) 0x16,\r
  75                             (byte) 0x5f, (byte) 0x49, (byte) 0xb8, (byte) 0x00,\r
  76                     },\r
  77                     // 39382357235489614581723060781553021112529911719440698176882885853963445705823\r
  78                     new byte[]{\r
  79                             (byte) 0x5f, (byte) 0x9c, (byte) 0x95, (byte) 0xbc,\r
  80                             (byte) 0xa3, (byte) 0x50, (byte) 0x8c, (byte) 0x24,\r
  81                             (byte) 0xb1, (byte) 0xd0, (byte) 0xb1, (byte) 0x55,\r
  82                             (byte) 0x9c, (byte) 0x83, (byte) 0xef, (byte) 0x5b,\r
  83                             (byte) 0x04, (byte) 0x44, (byte) 0x5c, (byte) 0xc4,\r
  84                             (byte) 0x58, (byte) 0x1c, (byte) 0x8e, (byte) 0x86,\r
  85                             (byte) 0xd8, (byte) 0x22, (byte) 0x4e, (byte) 0xdd,\r
  86                             (byte) 0xd0, (byte) 0x9f, (byte) 0x11, (byte) 0x57\r
  87                     },\r
  88                     // 2^255 - 19 - 1\r
  89                     new byte[]{\r
  90                             (byte) 0xec, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  91                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  92                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  93                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  94                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  95                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  96                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
  97                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0x7f,\r
  98                     },\r
  99                     // 2^255 - 19\r
 100                     new byte[]{\r
 101                             (byte) 0xed, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 102                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 103                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 104                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 105                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 106                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 107                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 108                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0x7f\r
 109                     },\r
 110                     // 2^255 - 19 + 1\r
 111                     new byte[]{\r
 112                             (byte) 0xee, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 113                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 114                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 115                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 116                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 117                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 118                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0xff,\r
 119                             (byte) 0xff, (byte) 0xff, (byte) 0xff, (byte) 0x7f\r
 120                     }\r
 121             };\r
 122 \r
 123     /**\r
 124      * Computes Montgomery's double-and-add formulas.\r
 125      *\r
 126      * <p>On entry and exit, the absolute value of the limbs of all inputs and outputs are < 2^26.\r
 127      *\r
 128      * @param x2     x projective coordinate of output 2Q, long form\r
 129      * @param z2     z projective coordinate of output 2Q, long form\r
 130      * @param x3     x projective coordinate of output Q + Q', long form\r
 131      * @param z3     z projective coordinate of output Q + Q', long form\r
 132      * @param x      x projective coordinate of input Q, short form, destroyed\r
 133      * @param z      z projective coordinate of input Q, short form, destroyed\r
 134      * @param xprime x projective coordinate of input Q', short form, destroyed\r
 135      * @param zprime z projective coordinate of input Q', short form, destroyed\r
 136      * @param qmqp   input Q - Q', short form, preserved\r
 137      */\r
 138     private static void monty(\r
 139             long[] x2,\r
 140             long[] z2,\r
 141             long[] x3,\r
 142             long[] z3,\r
 143             long[] x,\r
 144             long[] z,\r
 145             long[] xprime,\r
 146             long[] zprime,\r
 147             long[] qmqp) {\r
 148         long[] origx = Arrays.copyOf(x, Field25519.LIMB_CNT);\r
 149         long[] zzz = new long[19];\r
 150         long[] xx = new long[19];\r
 151         long[] zz = new long[19];\r
 152         long[] xxprime = new long[19];\r
 153         long[] zzprime = new long[19];\r
 154         long[] zzzprime = new long[19];\r
 155         long[] xxxprime = new long[19];\r
 156 \r
 157         Field25519.sum(x, z);\r
 158         // |x[i]| < 2^27\r
 159         Field25519.sub(z, origx); // does x - z\r
 160         // |z[i]| < 2^27\r
 161 \r
 162         long[] origxprime = Arrays.copyOf(xprime, Field25519.LIMB_CNT);\r
 163         Field25519.sum(xprime, zprime);\r
 164         // |xprime[i]| < 2^27\r
 165         Field25519.sub(zprime, origxprime);\r
 166         // |zprime[i]| < 2^27\r
 167         Field25519.product(xxprime, xprime, z);\r
 168         // |xxprime[i]| < 14*2^54: the largest product of two limbs will be < 2^(27+27) and {@ref\r
 169         // Field25519#product} adds together, at most, 14 of those products. (Approximating that to\r
 170         // 2^58 doesn't work out.)\r
 171         Field25519.product(zzprime, x, zprime);\r
 172         // |zzprime[i]| < 14*2^54\r
 173         Field25519.reduceSizeByModularReduction(xxprime);\r
 174         Field25519.reduceCoefficients(xxprime);\r
 175         // |xxprime[i]| < 2^26\r
 176         Field25519.reduceSizeByModularReduction(zzprime);\r
 177         Field25519.reduceCoefficients(zzprime);\r
 178         // |zzprime[i]| < 2^26\r
 179         System.arraycopy(xxprime, 0, origxprime, 0, Field25519.LIMB_CNT);\r
 180         Field25519.sum(xxprime, zzprime);\r
 181         // |xxprime[i]| < 2^27\r
 182         Field25519.sub(zzprime, origxprime);\r
 183         // |zzprime[i]| < 2^27\r
 184         Field25519.square(xxxprime, xxprime);\r
 185         // |xxxprime[i]| < 2^26\r
 186         Field25519.square(zzzprime, zzprime);\r
 187         // |zzzprime[i]| < 2^26\r
 188         Field25519.product(zzprime, zzzprime, qmqp);\r
 189         // |zzprime[i]| < 14*2^52\r
 190         Field25519.reduceSizeByModularReduction(zzprime);\r
 191         Field25519.reduceCoefficients(zzprime);\r
 192         // |zzprime[i]| < 2^26\r
 193         System.arraycopy(xxxprime, 0, x3, 0, Field25519.LIMB_CNT);\r
 194         System.arraycopy(zzprime, 0, z3, 0, Field25519.LIMB_CNT);\r
 195 \r
 196         Field25519.square(xx, x);\r
 197         // |xx[i]| < 2^26\r
 198         Field25519.square(zz, z);\r
 199         // |zz[i]| < 2^26\r
 200         Field25519.product(x2, xx, zz);\r
 201         // |x2[i]| < 14*2^52\r
 202         Field25519.reduceSizeByModularReduction(x2);\r
 203         Field25519.reduceCoefficients(x2);\r
 204         // |x2[i]| < 2^26\r
 205         Field25519.sub(zz, xx); // does zz = xx - zz\r
 206         // |zz[i]| < 2^27\r
 207         Arrays.fill(zzz, Field25519.LIMB_CNT, zzz.length - 1, 0);\r
 208         Field25519.scalarProduct(zzz, zz, 121665);\r
 209         // |zzz[i]| < 2^(27+17)\r
 210         // No need to call reduceSizeByModularReduction here: scalarProduct doesn't increase the degree\r
 211         // of its input.\r
 212         Field25519.reduceCoefficients(zzz);\r
 213         // |zzz[i]| < 2^26\r
 214         Field25519.sum(zzz, xx);\r
 215         // |zzz[i]| < 2^27\r
 216         Field25519.product(z2, zz, zzz);\r
 217         // |z2[i]| < 14*2^(26+27)\r
 218         Field25519.reduceSizeByModularReduction(z2);\r
 219         Field25519.reduceCoefficients(z2);\r
 220         // |z2|i| < 2^26\r
 221     }\r
 222 \r
 223     /**\r
 224      * Conditionally swap two reduced-form limb arrays if {@code iswap} is 1, but leave them unchanged\r
 225      * if {@code iswap} is 0. Runs in data-invariant time to avoid side-channel attacks.\r
 226      *\r
 227      * <p>NOTE that this function requires that {@code iswap} be 1 or 0; other values give wrong\r
 228      * results. Also, the two limb arrays must be in reduced-coefficient, reduced-degree form: the\r
 229      * values in a[10..19] or b[10..19] aren't swapped, and all all values in a[0..9],b[0..9] must\r
 230      * have magnitude less than Integer.MAX_VALUE.\r
 231      */\r
 232     static void swapConditional(long[] a, long[] b, int iswap) {\r
 233         int swap = -iswap;\r
 234         for (int i = 0; i < Field25519.LIMB_CNT; i++) {\r
 235             int x = swap & (((int) a[i]) ^ ((int) b[i]));\r
 236             a[i] = ((int) a[i]) ^ x;\r
 237             b[i] = ((int) b[i]) ^ x;\r
 238         }\r
 239     }\r
 240 \r
 241     /**\r
 242      * Conditionally copies a reduced-form limb arrays {@code b} into {@code a} if {@code icopy} is 1,\r
 243      * but leave {@code a} unchanged if 'iswap' is 0. Runs in data-invariant time to avoid\r
 244      * side-channel attacks.\r
 245      *\r
 246      * <p>NOTE that this function requires that {@code icopy} be 1 or 0; other values give wrong\r
 247      * results. Also, the two limb arrays must be in reduced-coefficient, reduced-degree form: the\r
 248      * values in a[10..19] or b[10..19] aren't swapped, and all all values in a[0..9],b[0..9] must\r
 249      * have magnitude less than Integer.MAX_VALUE.\r
 250      */\r
 251     static void copyConditional(long[] a, long[] b, int icopy) {\r
 252         int copy = -icopy;\r
 253         for (int i = 0; i < Field25519.LIMB_CNT; i++) {\r
 254             int x = copy & (((int) a[i]) ^ ((int) b[i]));\r
 255             a[i] = ((int) a[i]) ^ x;\r
 256         }\r
 257     }\r
 258 \r
 259     /**\r
 260      * Calculates nQ where Q is the x-coordinate of a point on the curve.\r
 261      *\r
 262      * @param resultx the x projective coordinate of the resulting curve point (short form).\r
 263      * @param n       a little endian, 32-byte number.\r
 264      * @param qBytes  a little endian, 32-byte number representing the public point' x coordinate.\r
 265      * @throws InvalidKeyException   iff the public key is in the banned list or its length is not\r
 266      *                               32-byte.\r
 267      * @throws IllegalStateException iff there is arithmetic error.\r
 268      */\r
 269     static void curveMult(long[] resultx, byte[] n, byte[] qBytes) throws InvalidKeyException {\r
 270         validatePubKeyAndClearMsb(qBytes);\r
 271 \r
 272         long[] q = Field25519.expand(qBytes);\r
 273         long[] nqpqx = new long[19];\r
 274         long[] nqpqz = new long[19];\r
 275         nqpqz[0] = 1;\r
 276         long[] nqx = new long[19];\r
 277         nqx[0] = 1;\r
 278         long[] nqz = new long[19];\r
 279         long[] nqpqx2 = new long[19];\r
 280         long[] nqpqz2 = new long[19];\r
 281         nqpqz2[0] = 1;\r
 282         long[] nqx2 = new long[19];\r
 283         long[] nqz2 = new long[19];\r
 284         nqz2[0] = 1;\r
 285         long[] t = new long[19];\r
 286 \r
 287         System.arraycopy(q, 0, nqpqx, 0, Field25519.LIMB_CNT);\r
 288 \r
 289         for (int i = 0; i < Field25519.FIELD_LEN; i++) {\r
 290             int b = n[Field25519.FIELD_LEN - i - 1] & 0xff;\r
 291             for (int j = 0; j < 8; j++) {\r
 292                 int bit = (b >> (7 - j)) & 1;\r
 293 \r
 294                 swapConditional(nqx, nqpqx, bit);\r
 295                 swapConditional(nqz, nqpqz, bit);\r
 296                 monty(nqx2, nqz2, nqpqx2, nqpqz2, nqx, nqz, nqpqx, nqpqz, q);\r
 297                 swapConditional(nqx2, nqpqx2, bit);\r
 298                 swapConditional(nqz2, nqpqz2, bit);\r
 299 \r
 300                 t = nqx;\r
 301                 nqx = nqx2;\r
 302                 nqx2 = t;\r
 303                 t = nqz;\r
 304                 nqz = nqz2;\r
 305                 nqz2 = t;\r
 306                 t = nqpqx;\r
 307                 nqpqx = nqpqx2;\r
 308                 nqpqx2 = t;\r
 309                 t = nqpqz;\r
 310                 nqpqz = nqpqz2;\r
 311                 nqpqz2 = t;\r
 312             }\r
 313         }\r
 314 \r
 315         // Computes nqx/nqz.\r
 316         long[] zmone = new long[Field25519.LIMB_CNT];\r
 317         Field25519.inverse(zmone, nqz);\r
 318         Field25519.mult(resultx, nqx, zmone);\r
 319 \r
 320         // Nowadays it should be standard to protect public key crypto against flaws. I.e. if there is a\r
 321         // computation error through a faulty CPU or if the implementation contains a bug, then if\r
 322         // possible this should be detected at run time.\r
 323         //\r
 324         // The situation is a bit more tricky for X25519 where for example the implementation\r
 325         // proposed in https://tools.ietf.org/html/rfc7748 only uses the x-coordinate. However, a\r
 326         // verification is still possible, but depends on the actual computation.\r
 327         //\r
 328         // Tink's Java implementation is equivalent to RFC7748. We will use the loop invariant in the\r
 329         // Montgomery ladder to detect fault computation. In particular, we use the following invariant:\r
 330         // q, resultx, nqpqx/nqpqx  are x coordinates of 3 collinear points q, n*q, (n + 1)*q.\r
 331         if (!isCollinear(q, resultx, nqpqx, nqpqz)) {\r
 332             throw new IllegalStateException(\r
 333                     "Arithmetic error in curve multiplication with the public key: "\r
 334                             + Hex.encode(qBytes));\r
 335         }\r
 336     }\r
 337 \r
 338     /**\r
 339      * Validates public key and clear its most significant bit.\r
 340      *\r
 341      * @throws InvalidKeyException iff the {@code pubKey} is in the banned list or its length is not\r
 342      *                             32-byte.\r
 343      */\r
 344     private static void validatePubKeyAndClearMsb(byte[] pubKey) throws InvalidKeyException {\r
 345         if (pubKey.length != 32) {\r
 346             throw new InvalidKeyException("Public key length is not 32-byte");\r
 347         }\r
 348         // Clears the most significant bit as in the method decodeUCoordinate() of RFC7748.\r
 349         pubKey[31] &= (byte) 0x7f;\r
 350 \r
 351         for (int i = 0; i < BANNED_PUBLIC_KEYS.length; i++) {\r
 352             if (Bytes.equal(BANNED_PUBLIC_KEYS[i], pubKey)) {\r
 353                 throw new InvalidKeyException("Banned public key: " + Hex.encode(BANNED_PUBLIC_KEYS[i]));\r
 354             }\r
 355         }\r
 356     }\r
 357 \r
 358     /**\r
 359      * Checks whether there are three collinear points with x coordinate x1, x2, x3/z3.\r
 360      *\r
 361      * @return true if three collinear points with x coordianate x1, x2, x3/z3 are collinear.\r
 362      */\r
 363     private static boolean isCollinear(long[] x1, long[] x2, long[] x3, long[] z3) {\r
 364         // If x1, x2, x3 (in this method x3 is represented as x3/z3) are the x-coordinates of three\r
 365         // collinear points on a curve, then they satisfy the equation\r
 366         //   y^2 = x^3 + ax^2 + x\r
 367         // They also satisfy the equation\r
 368         //   0 = (x - x1)(x - x2)(x - x3)\r
 369         //     = x^3 + Ax^2 + Bx + C\r
 370         // where\r
 371         //   A = - x1 - x2 - x3\r
 372         //   B = x1*x2 + x2*x3 + x3*x1\r
 373         //   C = - x1*x2*x3\r
 374         // Hence, the three points also satisfy\r
 375         //   y^2 = (a - A)x^2 + (1 - B)x - C\r
 376         // This is a quadratic curve. Three distinct collinear points can only be on a quadratic\r
 377         // curve if the quadratic curve has a line as component. And if a quadratic curve has a line\r
 378         // as component then its discriminant is 0.\r
 379         // Therefore, discriminant((a - A)x^2 + (1-B)x - C) = 0.\r
 380         // In particular:\r
 381         //   a = 486662\r
 382         //   lhs = 4 * ((x1 + x2 + a) * z3 + x3) * (x1 * x2 * x3)\r
 383         //   rhs = ((x1 * x2 - 1) * z3 + x3 * (x1 + x2))**2\r
 384         //   assert (lhs - rhs)  == 0\r
 385         //\r
 386         // There are 2 cases that we haven't discussed:\r
 387         //\r
 388         //   * If x1 and x2 are both points with y-coordinate 0 then the argument doesn't hold.\r
 389         //   However, our ECDH computation doesn't allow points of low order (see {@code\r
 390         //   validatePublicKey}). Therefore, this edge case never happen.\r
 391         //\r
 392         //   * x1, x2 or x3/y3 may be points on the twist. If so, they satisfy the equation\r
 393         //     2y^2 = x^3 + ax^2 + x\r
 394         //   Hence, the three points also satisfy\r
 395         //     2y^2 = (a - A)x^2 + (1 - B)x - C\r
 396         //   Thus, this collinear check should work for this case too.\r
 397         long[] x1multx2 = new long[Field25519.LIMB_CNT];\r
 398         long[] x1addx2 = new long[Field25519.LIMB_CNT];\r
 399         long[] lhs = new long[Field25519.LIMB_CNT + 1];\r
 400         long[] t = new long[Field25519.LIMB_CNT + 1];\r
 401         long[] t2 = new long[Field25519.LIMB_CNT + 1];\r
 402         Field25519.mult(x1multx2, x1, x2);\r
 403         Field25519.sum(x1addx2, x1, x2);\r
 404         long[] a = new long[Field25519.LIMB_CNT];\r
 405         a[0] = 486662;\r
 406         // t = x1 + x2 + a\r
 407         Field25519.sum(t, x1addx2, a);\r
 408         // t = (x1 + x2 + a) * z3\r
 409         Field25519.mult(t, t, z3);\r
 410         // t = (x1 + x2 + a) * z3 + x3\r
 411         Field25519.sum(t, x3);\r
 412         // t = ((x1 + x2 + a) * z3 + x3) * x1 * x2\r
 413         Field25519.mult(t, t, x1multx2);\r
 414         // t = ((x1 + x2 + a) * z3 + x3) * (x1 * x2 * x3)\r
 415         Field25519.mult(t, t, x3);\r
 416         Field25519.scalarProduct(lhs, t, 4);\r
 417         Field25519.reduceCoefficients(lhs);\r
 418 \r
 419         // t = x1 * x2 * z3\r
 420         Field25519.mult(t, x1multx2, z3);\r
 421         // t = x1 * x2 * z3 - z3\r
 422         Field25519.sub(t, t, z3);\r
 423         // t2 = (x1 + x2) * x3\r
 424         Field25519.mult(t2, x1addx2, x3);\r
 425         // t = x1 * x2 * z3 - z3 + (x1 + x2) * x3\r
 426         Field25519.sum(t, t, t2);\r
 427         // t = (x1 * x2 * z3 - z3 + (x1 + x2) * x3)^2\r
 428         Field25519.square(t, t);\r
 429         return Bytes.equal(Field25519.contract(lhs), Field25519.contract(t));\r
 430     }\r
 431 }\r