diff options
Diffstat (limited to 'app/src/main/java/com/wireguard/crypto')
| -rw-r--r-- | app/src/main/java/com/wireguard/crypto/Curve25519.java | 628 | ||||
| -rw-r--r-- | app/src/main/java/com/wireguard/crypto/KeyEncoding.java | 46 |
2 files changed, 330 insertions, 344 deletions
diff --git a/app/src/main/java/com/wireguard/crypto/Curve25519.java b/app/src/main/java/com/wireguard/crypto/Curve25519.java index 5d27c3e3..0956c4fb 100644 --- a/app/src/main/java/com/wireguard/crypto/Curve25519.java +++ b/app/src/main/java/com/wireguard/crypto/Curve25519.java @@ -26,16 +26,16 @@ import java.util.Arrays; /** * Implementation of the Curve25519 elliptic curve algorithm. - * + * <p> * This implementation is based on that from arduinolibs: * https://github.com/rweather/arduinolibs - * + * <p> * This implementation is copied verbatim from noise-java: * https://github.com/rweather/noise-java - * + * <p> * Differences in this version are due to using 26-bit limbs for the * representation instead of the 8/16/32-bit limbs in the original. - * + * <p> * References: http://cr.yp.to/ecdh.html, RFC 7748 */ @SuppressWarnings("ALL") @@ -44,47 +44,148 @@ public final class Curve25519 { // Numbers modulo 2^255 - 19 are broken up into ten 26-bit words. private static final int NUM_LIMBS_255BIT = 10; private static final int NUM_LIMBS_510BIT = 20; - private int[] x_1; - private int[] x_2; - private int[] x_3; - private int[] z_2; - private int[] z_3; private int[] A; + private int[] AA; private int[] B; + private int[] BB; private int[] C; + private int[] CB; private int[] D; - private int[] E; - private int[] AA; - private int[] BB; private int[] DA; - private int[] CB; + private int[] E; private long[] t1; private int[] t2; + private int[] x_1; + private int[] x_2; + private int[] x_3; + private int[] z_2; + private int[] z_3; /** * Constructs the temporary state holder for Curve25519 evaluation. */ - private Curve25519() - { + private Curve25519() { // Allocate memory for all of the temporary variables we will need. - x_1 = new int [NUM_LIMBS_255BIT]; - x_2 = new int [NUM_LIMBS_255BIT]; - x_3 = new int [NUM_LIMBS_255BIT]; - z_2 = new int [NUM_LIMBS_255BIT]; - z_3 = new int [NUM_LIMBS_255BIT]; - A = new int [NUM_LIMBS_255BIT]; - B = new int [NUM_LIMBS_255BIT]; - C = new int [NUM_LIMBS_255BIT]; - D = new int [NUM_LIMBS_255BIT]; - E = new int [NUM_LIMBS_255BIT]; - AA = new int [NUM_LIMBS_255BIT]; - BB = new int [NUM_LIMBS_255BIT]; - DA = new int [NUM_LIMBS_255BIT]; - CB = new int [NUM_LIMBS_255BIT]; - t1 = new long [NUM_LIMBS_510BIT]; - t2 = new int [NUM_LIMBS_510BIT]; + x_1 = new int[NUM_LIMBS_255BIT]; + x_2 = new int[NUM_LIMBS_255BIT]; + x_3 = new int[NUM_LIMBS_255BIT]; + z_2 = new int[NUM_LIMBS_255BIT]; + z_3 = new int[NUM_LIMBS_255BIT]; + A = new int[NUM_LIMBS_255BIT]; + B = new int[NUM_LIMBS_255BIT]; + C = new int[NUM_LIMBS_255BIT]; + D = new int[NUM_LIMBS_255BIT]; + E = new int[NUM_LIMBS_255BIT]; + AA = new int[NUM_LIMBS_255BIT]; + BB = new int[NUM_LIMBS_255BIT]; + DA = new int[NUM_LIMBS_255BIT]; + CB = new int[NUM_LIMBS_255BIT]; + t1 = new long[NUM_LIMBS_510BIT]; + t2 = new int[NUM_LIMBS_510BIT]; } + /** + * Conditional swap of two values. + * + * @param select Set to 1 to swap, 0 to leave as-is. + * @param x The first value. + * @param y The second value. + */ + private static void cswap(int select, int[] x, int[] y) { + int dummy; + select = -select; + for (int index = 0; index < NUM_LIMBS_255BIT; ++index) { + dummy = select & (x[index] ^ y[index]); + x[index] ^= dummy; + y[index] ^= dummy; + } + } + + /** + * Evaluates the Curve25519 curve. + * + * @param result Buffer to place the result of the evaluation into. + * @param offset Offset into the result buffer. + * @param privateKey The private key to use in the evaluation. + * @param publicKey The public key to use in the evaluation, or null + * if the base point of the curve should be used. + */ + public static void eval(byte[] result, int offset, byte[] privateKey, byte[] publicKey) { + Curve25519 state = new Curve25519(); + try { + // Unpack the public key value. If null, use 9 as the base point. + Arrays.fill(state.x_1, 0); + if (publicKey != null) { + // Convert the input value from little-endian into 26-bit limbs. + for (int index = 0; index < 32; ++index) { + int bit = (index * 8) % 26; + int word = (index * 8) / 26; + int value = publicKey[index] & 0xFF; + if (bit <= (26 - 8)) { + state.x_1[word] |= value << bit; + } else { + state.x_1[word] |= value << bit; + state.x_1[word] &= 0x03FFFFFF; + state.x_1[word + 1] |= value >> (26 - bit); + } + } + + // Just in case, we reduce the number modulo 2^255 - 19 to + // make sure that it is in range of the field before we start. + // This eliminates values between 2^255 - 19 and 2^256 - 1. + state.reduceQuick(state.x_1); + state.reduceQuick(state.x_1); + } else { + state.x_1[0] = 9; + } + + // Initialize the other temporary variables. + Arrays.fill(state.x_2, 0); // x_2 = 1 + state.x_2[0] = 1; + Arrays.fill(state.z_2, 0); // z_2 = 0 + System.arraycopy(state.x_1, 0, state.x_3, 0, state.x_1.length); // x_3 = x_1 + Arrays.fill(state.z_3, 0); // z_3 = 1 + state.z_3[0] = 1; + + // Evaluate the curve for every bit of the private key. + state.evalCurve(privateKey); + + // Compute x_2 * (z_2 ^ (p - 2)) where p = 2^255 - 19. + state.recip(state.z_3, state.z_2); + state.mul(state.x_2, state.x_2, state.z_3); + + // Convert x_2 into little-endian in the result buffer. + for (int index = 0; index < 32; ++index) { + int bit = (index * 8) % 26; + int word = (index * 8) / 26; + if (bit <= (26 - 8)) + result[offset + index] = (byte) (state.x_2[word] >> bit); + else + result[offset + index] = (byte) ((state.x_2[word] >> bit) | (state.x_2[word + 1] << (26 - bit))); + } + } finally { + // Clean up all temporary state before we exit. + state.destroy(); + } + } + + /** + * Adds two numbers modulo 2^255 - 19. + * + * @param result The result. + * @param x The first number to add. + * @param y The second number to add. + */ + private void add(int[] result, int[] x, int[] y) { + int index, carry; + carry = x[0] + y[0]; + result[0] = carry & 0x03FFFFFF; + for (index = 1; index < NUM_LIMBS_255BIT; ++index) { + carry = (carry >> 26) + x[index] + y[index]; + result[index] = carry & 0x03FFFFFF; + } + reduceQuick(result); + } /** * Destroy all sensitive data in this object. @@ -105,107 +206,82 @@ public final class Curve25519 { Arrays.fill(BB, 0); Arrays.fill(DA, 0); Arrays.fill(CB, 0); - Arrays.fill(t1, 0L); - Arrays.fill(t2, 0); + Arrays.fill(t1, 0L); + Arrays.fill(t2, 0); } /** - * Reduces a number modulo 2^255 - 19 where it is known that the - * number can be reduced with only 1 trial subtraction. + * Evaluates the curve for every bit in a secret key. * - * @param x The number to reduce, and the result. + * @param s The 32-byte secret key. */ - private void reduceQuick(int[] x) - { - int index, carry; - - // Perform a trial subtraction of (2^255 - 19) from "x" which is - // equivalent to adding 19 and subtracting 2^255. We add 19 here; - // the subtraction of 2^255 occurs in the next step. - carry = 19; - for (index = 0; index < NUM_LIMBS_255BIT; ++index) { - carry += x[index]; - t2[index] = carry & 0x03FFFFFF; - carry >>= 26; - } + private void evalCurve(byte[] s) { + int sposn = 31; + int sbit = 6; + int svalue = s[sposn] | 0x40; + int swap = 0; + int select; - // If there was a borrow, then the original "x" is the correct answer. - // If there was no borrow, then "t2" is the correct answer. Select the - // correct answer but do it in a way that instruction timing will not - // reveal which value was selected. Borrow will occur if bit 21 of - // "t2" is zero. Turn the bit into a selection mask. - int mask = -((t2[NUM_LIMBS_255BIT - 1] >> 21) & 0x01); - int nmask = ~mask; - t2[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; - for (index = 0; index < NUM_LIMBS_255BIT; ++index) - x[index] = (x[index] & nmask) | (t2[index] & mask); - } + // Iterate over all 255 bits of "s" from the highest to the lowest. + // We ignore the high bit of the 256-bit representation of "s". + for (; ; ) { + // Conditional swaps on entry to this bit but only if we + // didn't swap on the previous bit. + select = (svalue >> sbit) & 0x01; + swap ^= select; + cswap(swap, x_2, x_3); + cswap(swap, z_2, z_3); + swap = select; - /** - * Reduce a number modulo 2^255 - 19. - * - * @param result The result. - * @param x The value to be reduced. This array will be - * modified during the reduction. - * @param size The number of limbs in the high order half of x. - */ - private void reduce(int[] result, int[] x, int size) - { - int index, limb, carry; + // Evaluate the curve. + add(A, x_2, z_2); // A = x_2 + z_2 + square(AA, A); // AA = A^2 + sub(B, x_2, z_2); // B = x_2 - z_2 + square(BB, B); // BB = B^2 + sub(E, AA, BB); // E = AA - BB + add(C, x_3, z_3); // C = x_3 + z_3 + sub(D, x_3, z_3); // D = x_3 - z_3 + mul(DA, D, A); // DA = D * A + mul(CB, C, B); // CB = C * B + add(x_3, DA, CB); // x_3 = (DA + CB)^2 + square(x_3, x_3); + sub(z_3, DA, CB); // z_3 = x_1 * (DA - CB)^2 + square(z_3, z_3); + mul(z_3, z_3, x_1); + mul(x_2, AA, BB); // x_2 = AA * BB + mulA24(z_2, E); // z_2 = E * (AA + a24 * E) + add(z_2, z_2, AA); + mul(z_2, z_2, E); - // Calculate (x mod 2^255) + ((x / 2^255) * 19) which will - // either produce the answer we want or it will produce a - // value of the form "answer + j * (2^255 - 19)". There are - // 5 left-over bits in the top-most limb of the bottom half. - carry = 0; - limb = x[NUM_LIMBS_255BIT - 1] >> 21; - x[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; - for (index = 0; index < size; ++index) { - limb += x[NUM_LIMBS_255BIT + index] << 5; - carry += (limb & 0x03FFFFFF) * 19 + x[index]; - x[index] = carry & 0x03FFFFFF; - limb >>= 26; - carry >>= 26; - } - if (size < NUM_LIMBS_255BIT) { - // The high order half of the number is short; e.g. for mulA24(). - // Propagate the carry through the rest of the low order part. - for (index = size; index < NUM_LIMBS_255BIT; ++index) { - carry += x[index]; - x[index] = carry & 0x03FFFFFF; - carry >>= 26; + // Move onto the next lower bit of "s". + if (sbit > 0) { + --sbit; + } else if (sposn == 0) { + break; + } else if (sposn == 1) { + --sposn; + svalue = s[sposn] & 0xF8; + sbit = 7; + } else { + --sposn; + svalue = s[sposn]; + sbit = 7; } } - // The "j" value may still be too large due to the final carry-out. - // We must repeat the reduction. If we already have the answer, - // then this won't do any harm but we must still do the calculation - // to preserve the overall timing. The "j" value will be between - // 0 and 19, which means that the carry we care about is in the - // top 5 bits of the highest limb of the bottom half. - carry = (x[NUM_LIMBS_255BIT - 1] >> 21) * 19; - x[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; - for (index = 0; index < NUM_LIMBS_255BIT; ++index) { - carry += x[index]; - result[index] = carry & 0x03FFFFFF; - carry >>= 26; - } - - // At this point "x" will either be the answer or it will be the - // answer plus (2^255 - 19). Perform a trial subtraction to - // complete the reduction process. - reduceQuick(result); + // Final conditional swaps. + cswap(swap, x_2, x_3); + cswap(swap, z_2, z_3); } /** * Multiplies two numbers modulo 2^255 - 19. * * @param result The result. - * @param x The first number to multiply. - * @param y The second number to multiply. + * @param x The first number to multiply. + * @param y The second number to multiply. */ - private void mul(int[] result, int[] x, int[] y) - { + private void mul(int[] result, int[] x, int[] y) { int i, j; // Multiply the two numbers to create the intermediate result. @@ -223,10 +299,10 @@ public final class Curve25519 { // Propagate carries and convert back into 26-bit words. v = t1[0]; - t2[0] = ((int)v) & 0x03FFFFFF; + t2[0] = ((int) v) & 0x03FFFFFF; for (i = 1; i < NUM_LIMBS_510BIT; ++i) { v = (v >> 26) + t1[i]; - t2[i] = ((int)v) & 0x03FFFFFF; + t2[i] = ((int) v) & 0x03FFFFFF; } // Reduce the result modulo 2^255 - 19. @@ -234,113 +310,31 @@ public final class Curve25519 { } /** - * Squares a number modulo 2^255 - 19. - * - * @param result The result. - * @param x The number to square. - */ - private void square(int[] result, int[] x) - { - mul(result, x, x); - } - - /** * Multiplies a number by the a24 constant, modulo 2^255 - 19. * * @param result The result. - * @param x The number to multiply by a24. + * @param x The number to multiply by a24. */ - private void mulA24(int[] result, int[] x) - { + private void mulA24(int[] result, int[] x) { long a24 = 121665; long carry = 0; int index; for (index = 0; index < NUM_LIMBS_255BIT; ++index) { carry += a24 * x[index]; - t2[index] = ((int)carry) & 0x03FFFFFF; + t2[index] = ((int) carry) & 0x03FFFFFF; carry >>= 26; } - t2[NUM_LIMBS_255BIT] = ((int)carry) & 0x03FFFFFF; + t2[NUM_LIMBS_255BIT] = ((int) carry) & 0x03FFFFFF; reduce(result, t2, 1); } /** - * Adds two numbers modulo 2^255 - 19. - * - * @param result The result. - * @param x The first number to add. - * @param y The second number to add. - */ - private void add(int[] result, int[] x, int[] y) - { - int index, carry; - carry = x[0] + y[0]; - result[0] = carry & 0x03FFFFFF; - for (index = 1; index < NUM_LIMBS_255BIT; ++index) { - carry = (carry >> 26) + x[index] + y[index]; - result[index] = carry & 0x03FFFFFF; - } - reduceQuick(result); - } - - /** - * Subtracts two numbers modulo 2^255 - 19. - * - * @param result The result. - * @param x The first number to subtract. - * @param y The second number to subtract. - */ - private void sub(int[] result, int[] x, int[] y) - { - int index, borrow; - - // Subtract y from x to generate the intermediate result. - borrow = 0; - for (index = 0; index < NUM_LIMBS_255BIT; ++index) { - borrow = x[index] - y[index] - ((borrow >> 26) & 0x01); - result[index] = borrow & 0x03FFFFFF; - } - - // If we had a borrow, then the result has gone negative and we - // have to add 2^255 - 19 to the result to make it positive again. - // The top bits of "borrow" will be all 1's if there is a borrow - // or it will be all 0's if there was no borrow. Easiest is to - // conditionally subtract 19 and then mask off the high bits. - borrow = result[0] - ((-((borrow >> 26) & 0x01)) & 19); - result[0] = borrow & 0x03FFFFFF; - for (index = 1; index < NUM_LIMBS_255BIT; ++index) { - borrow = result[index] - ((borrow >> 26) & 0x01); - result[index] = borrow & 0x03FFFFFF; - } - result[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; - } - - /** - * Conditional swap of two values. - * - * @param select Set to 1 to swap, 0 to leave as-is. - * @param x The first value. - * @param y The second value. - */ - private static void cswap(int select, int[] x, int[] y) - { - int dummy; - select = -select; - for (int index = 0; index < NUM_LIMBS_255BIT; ++index) { - dummy = select & (x[index] ^ y[index]); - x[index] ^= dummy; - y[index] ^= dummy; - } - } - - /** * Raise x to the power of (2^250 - 1). * * @param result The result. Must not overlap with x. - * @param x The argument. + * @param x The argument. */ - private void pow250(int[] result, int[] x) - { + private void pow250(int[] result, int[] x) { int i, j; // The big-endian hexadecimal expansion of (2^250 - 1) is: @@ -378,10 +372,9 @@ public final class Curve25519 { * Computes the reciprocal of a number modulo 2^255 - 19. * * @param result The result. Must not overlap with x. - * @param x The argument. + * @param x The argument. */ - private void recip(int[] result, int[] x) - { + private void recip(int[] result, int[] x) { // The reciprocal is the same as x ^ (p - 2) where p = 2^255 - 19. // The big-endian hexadecimal expansion of (p - 2) is: // 7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFEB @@ -400,136 +393,129 @@ public final class Curve25519 { } /** - * Evaluates the curve for every bit in a secret key. + * Reduce a number modulo 2^255 - 19. * - * @param s The 32-byte secret key. + * @param result The result. + * @param x The value to be reduced. This array will be + * modified during the reduction. + * @param size The number of limbs in the high order half of x. */ - private void evalCurve(byte[] s) - { - int sposn = 31; - int sbit = 6; - int svalue = s[sposn] | 0x40; - int swap = 0; - int select; - - // Iterate over all 255 bits of "s" from the highest to the lowest. - // We ignore the high bit of the 256-bit representation of "s". - for (;;) { - // Conditional swaps on entry to this bit but only if we - // didn't swap on the previous bit. - select = (svalue >> sbit) & 0x01; - swap ^= select; - cswap(swap, x_2, x_3); - cswap(swap, z_2, z_3); - swap = select; - - // Evaluate the curve. - add(A, x_2, z_2); // A = x_2 + z_2 - square(AA, A); // AA = A^2 - sub(B, x_2, z_2); // B = x_2 - z_2 - square(BB, B); // BB = B^2 - sub(E, AA, BB); // E = AA - BB - add(C, x_3, z_3); // C = x_3 + z_3 - sub(D, x_3, z_3); // D = x_3 - z_3 - mul(DA, D, A); // DA = D * A - mul(CB, C, B); // CB = C * B - add(x_3, DA, CB); // x_3 = (DA + CB)^2 - square(x_3, x_3); - sub(z_3, DA, CB); // z_3 = x_1 * (DA - CB)^2 - square(z_3, z_3); - mul(z_3, z_3, x_1); - mul(x_2, AA, BB); // x_2 = AA * BB - mulA24(z_2, E); // z_2 = E * (AA + a24 * E) - add(z_2, z_2, AA); - mul(z_2, z_2, E); + private void reduce(int[] result, int[] x, int size) { + int index, limb, carry; - // Move onto the next lower bit of "s". - if (sbit > 0) { - --sbit; - } else if (sposn == 0) { - break; - } else if (sposn == 1) { - --sposn; - svalue = s[sposn] & 0xF8; - sbit = 7; - } else { - --sposn; - svalue = s[sposn]; - sbit = 7; + // Calculate (x mod 2^255) + ((x / 2^255) * 19) which will + // either produce the answer we want or it will produce a + // value of the form "answer + j * (2^255 - 19)". There are + // 5 left-over bits in the top-most limb of the bottom half. + carry = 0; + limb = x[NUM_LIMBS_255BIT - 1] >> 21; + x[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; + for (index = 0; index < size; ++index) { + limb += x[NUM_LIMBS_255BIT + index] << 5; + carry += (limb & 0x03FFFFFF) * 19 + x[index]; + x[index] = carry & 0x03FFFFFF; + limb >>= 26; + carry >>= 26; + } + if (size < NUM_LIMBS_255BIT) { + // The high order half of the number is short; e.g. for mulA24(). + // Propagate the carry through the rest of the low order part. + for (index = size; index < NUM_LIMBS_255BIT; ++index) { + carry += x[index]; + x[index] = carry & 0x03FFFFFF; + carry >>= 26; } } - // Final conditional swaps. - cswap(swap, x_2, x_3); - cswap(swap, z_2, z_3); + // The "j" value may still be too large due to the final carry-out. + // We must repeat the reduction. If we already have the answer, + // then this won't do any harm but we must still do the calculation + // to preserve the overall timing. The "j" value will be between + // 0 and 19, which means that the carry we care about is in the + // top 5 bits of the highest limb of the bottom half. + carry = (x[NUM_LIMBS_255BIT - 1] >> 21) * 19; + x[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; + for (index = 0; index < NUM_LIMBS_255BIT; ++index) { + carry += x[index]; + result[index] = carry & 0x03FFFFFF; + carry >>= 26; + } + + // At this point "x" will either be the answer or it will be the + // answer plus (2^255 - 19). Perform a trial subtraction to + // complete the reduction process. + reduceQuick(result); } /** - * Evaluates the Curve25519 curve. + * Reduces a number modulo 2^255 - 19 where it is known that the + * number can be reduced with only 1 trial subtraction. * - * @param result Buffer to place the result of the evaluation into. - * @param offset Offset into the result buffer. - * @param privateKey The private key to use in the evaluation. - * @param publicKey The public key to use in the evaluation, or null - * if the base point of the curve should be used. + * @param x The number to reduce, and the result. */ - public static void eval(byte[] result, int offset, byte[] privateKey, byte[] publicKey) - { - Curve25519 state = new Curve25519(); - try { - // Unpack the public key value. If null, use 9 as the base point. - Arrays.fill(state.x_1, 0); - if (publicKey != null) { - // Convert the input value from little-endian into 26-bit limbs. - for (int index = 0; index < 32; ++index) { - int bit = (index * 8) % 26; - int word = (index * 8) / 26; - int value = publicKey[index] & 0xFF; - if (bit <= (26 - 8)) { - state.x_1[word] |= value << bit; - } else { - state.x_1[word] |= value << bit; - state.x_1[word] &= 0x03FFFFFF; - state.x_1[word + 1] |= value >> (26 - bit); - } - } + private void reduceQuick(int[] x) { + int index, carry; - // Just in case, we reduce the number modulo 2^255 - 19 to - // make sure that it is in range of the field before we start. - // This eliminates values between 2^255 - 19 and 2^256 - 1. - state.reduceQuick(state.x_1); - state.reduceQuick(state.x_1); - } else { - state.x_1[0] = 9; - } + // Perform a trial subtraction of (2^255 - 19) from "x" which is + // equivalent to adding 19 and subtracting 2^255. We add 19 here; + // the subtraction of 2^255 occurs in the next step. + carry = 19; + for (index = 0; index < NUM_LIMBS_255BIT; ++index) { + carry += x[index]; + t2[index] = carry & 0x03FFFFFF; + carry >>= 26; + } - // Initialize the other temporary variables. - Arrays.fill(state.x_2, 0); // x_2 = 1 - state.x_2[0] = 1; - Arrays.fill(state.z_2, 0); // z_2 = 0 - System.arraycopy(state.x_1, 0, state.x_3, 0, state.x_1.length); // x_3 = x_1 - Arrays.fill(state.z_3, 0); // z_3 = 1 - state.z_3[0] = 1; + // If there was a borrow, then the original "x" is the correct answer. + // If there was no borrow, then "t2" is the correct answer. Select the + // correct answer but do it in a way that instruction timing will not + // reveal which value was selected. Borrow will occur if bit 21 of + // "t2" is zero. Turn the bit into a selection mask. + int mask = -((t2[NUM_LIMBS_255BIT - 1] >> 21) & 0x01); + int nmask = ~mask; + t2[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; + for (index = 0; index < NUM_LIMBS_255BIT; ++index) + x[index] = (x[index] & nmask) | (t2[index] & mask); + } - // Evaluate the curve for every bit of the private key. - state.evalCurve(privateKey); + /** + * Squares a number modulo 2^255 - 19. + * + * @param result The result. + * @param x The number to square. + */ + private void square(int[] result, int[] x) { + mul(result, x, x); + } - // Compute x_2 * (z_2 ^ (p - 2)) where p = 2^255 - 19. - state.recip(state.z_3, state.z_2); - state.mul(state.x_2, state.x_2, state.z_3); + /** + * Subtracts two numbers modulo 2^255 - 19. + * + * @param result The result. + * @param x The first number to subtract. + * @param y The second number to subtract. + */ + private void sub(int[] result, int[] x, int[] y) { + int index, borrow; - // Convert x_2 into little-endian in the result buffer. - for (int index = 0; index < 32; ++index) { - int bit = (index * 8) % 26; - int word = (index * 8) / 26; - if (bit <= (26 - 8)) - result[offset + index] = (byte)(state.x_2[word] >> bit); - else - result[offset + index] = (byte)((state.x_2[word] >> bit) | (state.x_2[word + 1] << (26 - bit))); - } - } finally { - // Clean up all temporary state before we exit. - state.destroy(); + // Subtract y from x to generate the intermediate result. + borrow = 0; + for (index = 0; index < NUM_LIMBS_255BIT; ++index) { + borrow = x[index] - y[index] - ((borrow >> 26) & 0x01); + result[index] = borrow & 0x03FFFFFF; } + + // If we had a borrow, then the result has gone negative and we + // have to add 2^255 - 19 to the result to make it positive again. + // The top bits of "borrow" will be all 1's if there is a borrow + // or it will be all 0's if there was no borrow. Easiest is to + // conditionally subtract 19 and then mask off the high bits. + borrow = result[0] - ((-((borrow >> 26) & 0x01)) & 19); + result[0] = borrow & 0x03FFFFFF; + for (index = 1; index < NUM_LIMBS_255BIT; ++index) { + borrow = result[index] - ((borrow >> 26) & 0x01); + result[index] = borrow & 0x03FFFFFF; + } + result[NUM_LIMBS_255BIT - 1] &= 0x001FFFFF; } } diff --git a/app/src/main/java/com/wireguard/crypto/KeyEncoding.java b/app/src/main/java/com/wireguard/crypto/KeyEncoding.java index 92e03230..ba867668 100644 --- a/app/src/main/java/com/wireguard/crypto/KeyEncoding.java +++ b/app/src/main/java/com/wireguard/crypto/KeyEncoding.java @@ -13,10 +13,10 @@ public final class KeyEncoding { public static final int KEY_LENGTH_HEX = 64; private static final String KEY_LENGTH_BASE64_EXCEPTION_MESSAGE = "WireGuard base64 keys must be 44 characters encoding 32 bytes"; - private static final String KEY_LENGTH_HEX_EXCEPTION_MESSAGE = - "WireGuard hex keys must be 64 characters encoding 32 bytes"; private static final String KEY_LENGTH_EXCEPTION_MESSAGE = "WireGuard keys must be 32 bytes"; + private static final String KEY_LENGTH_HEX_EXCEPTION_MESSAGE = + "WireGuard hex keys must be 64 characters encoding 32 bytes"; private KeyEncoding() { // Prevent instantiation. @@ -82,23 +82,6 @@ public final class KeyEncoding { return key; } - public static String keyToBase64(final byte[] key) { - final char[] output = new char[KEY_LENGTH_BASE64]; - if (key.length != KEY_LENGTH) - throw new IllegalArgumentException(KEY_LENGTH_EXCEPTION_MESSAGE); - int i; - for (i = 0; i < KEY_LENGTH / 3; ++i) - encodeBase64(key, i * 3, output, i * 4); - final byte[] endSegment = { - key[i * 3], - key[i * 3 + 1], - 0, - }; - encodeBase64(endSegment, 0, output, i * 4); - output[KEY_LENGTH_BASE64 - 1] = '='; - return new String(output); - } - public static byte[] keyFromHex(final String str) { final char[] input = str.toCharArray(); final byte[] key = new byte[KEY_LENGTH]; @@ -110,7 +93,7 @@ public final class KeyEncoding { for (int i = 0; i < KEY_LENGTH_HEX; ++i) { c = input[i]; c_num = c ^ 48; - c_num0 = (c_num - 10) >>8; + c_num0 = (c_num - 10) >> 8; c_alpha = (c & ~32) - 55; c_alpha0 = ((c_alpha - 10) ^ (c_alpha - 16)) >> 8; if ((c_num0 | c_alpha0) == 0) @@ -119,19 +102,36 @@ public final class KeyEncoding { if (state == 0) c_acc = c_val * 16; else - key[i / 2] = (byte)(c_acc | c_val); + key[i / 2] = (byte) (c_acc | c_val); state = ~state; } return key; } + public static String keyToBase64(final byte[] key) { + final char[] output = new char[KEY_LENGTH_BASE64]; + if (key.length != KEY_LENGTH) + throw new IllegalArgumentException(KEY_LENGTH_EXCEPTION_MESSAGE); + int i; + for (i = 0; i < KEY_LENGTH / 3; ++i) + encodeBase64(key, i * 3, output, i * 4); + final byte[] endSegment = { + key[i * 3], + key[i * 3 + 1], + 0, + }; + encodeBase64(endSegment, 0, output, i * 4); + output[KEY_LENGTH_BASE64 - 1] = '='; + return new String(output); + } + public static String keyToHex(final byte[] key) { final char[] output = new char[KEY_LENGTH_HEX]; if (key.length != KEY_LENGTH) throw new IllegalArgumentException(KEY_LENGTH_EXCEPTION_MESSAGE); for (int i = 0; i < KEY_LENGTH; ++i) { - output[i * 2] = (char)(87 + (key[i] >> 4 & 0xf) + ((((key[i] >> 4 & 0xf) - 10) >> 8) & ~38)); - output[i * 2 + 1] = (char)(87 + (key[i] & 0xf) + ((((key[i] & 0xf) - 10) >> 8) & ~38)); + output[i * 2] = (char) (87 + (key[i] >> 4 & 0xf) + ((((key[i] >> 4 & 0xf) - 10) >> 8) & ~38)); + output[i * 2 + 1] = (char) (87 + (key[i] & 0xf) + ((((key[i] & 0xf) - 10) >> 8) & ~38)); } return new String(output); } |