diff options
author | Mihaela Ion <mion@google.com> | 2022-11-18 12:38:53 -0500 |
---|---|---|
committer | Mihaela Ion <mion@google.com> | 2022-11-18 12:38:53 -0500 |
commit | ff5af15595ffae1d2499118622f2933e000765bb (patch) | |
tree | c988785087cbb9074344281154e0c74591874808 | |
parent | 8eafe59e2d5dda4b2f7e5b3498992d7b71fb45d1 (diff) | |
download | private-join-and-compute-ff5af15595ffae1d2499118622f2933e000765bb.tar.gz |
Adds a Java implementation of the EC Commutative Cipher
4 files changed, 604 insertions, 0 deletions
diff --git a/java/README.md b/java/README.md new file mode 100644 index 0000000..f8e7030 --- /dev/null +++ b/java/README.md @@ -0,0 +1,3 @@ +Java implementation of the EcCommutativeCipher, compatible with the C++ version. +It requires Guava https://github.com/google/guava/releases and Bouncycastle +https://www.bouncycastle.org libraries. diff --git a/java/com/google/privacy/private_join_and_compute/encryption/commutative/EcCommutativeCipher.java b/java/com/google/privacy/private_join_and_compute/encryption/commutative/EcCommutativeCipher.java new file mode 100644 index 0000000..03b37e8 --- /dev/null +++ b/java/com/google/privacy/private_join_and_compute/encryption/commutative/EcCommutativeCipher.java @@ -0,0 +1,290 @@ +package com.google.privacy.private_join_and_compute.encryption.commutative; + +import com.google.common.base.Preconditions; +import java.math.BigInteger; +import java.security.interfaces.ECPrivateKey; +import java.security.spec.InvalidKeySpecException; +import org.bouncycastle.asn1.sec.SECNamedCurves; +import org.bouncycastle.asn1.x9.X9ECParameters; +import org.bouncycastle.crypto.params.ECNamedDomainParameters; +import org.bouncycastle.math.ec.ECCurve; +import org.bouncycastle.math.ec.ECCurve.Fp; +import org.bouncycastle.math.ec.ECFieldElement; +import org.bouncycastle.math.ec.ECPoint; + +/** + * Implementation of EcCommutativeCipher using BouncyCastle. + * + * <p>EcCommutativeCipher class with the property that K1(K2(a)) = K2(K1(a)) where K(a) is + * encryption with the key K. + * + * <p>This class allows two parties to determine if they share the same value, without revealing the + * sensitive value to each other. See the paper "Using Commutative Encryption to Share a Secret" at + * https://eprint.iacr.org/2008/356.pdf for reference. + * + * <p>The encryption is performed over an elliptic curve. + * + * <p>Security: The provided bit security is half the number of bits of the underlying curve. For + * example, using curve secp160r1 gives 80 bit security. + */ +public final class EcCommutativeCipher extends EcCommutativeCipherBase { + + @SuppressWarnings("Immutable") + private final ECNamedDomainParameters domainParams; + + private static ECNamedDomainParameters getDomainParams(SupportedCurve curve) { + String curveName = curve.getCurveName(); + X9ECParameters ecParams = SECNamedCurves.getByName(curveName); + return new ECNamedDomainParameters( + SECNamedCurves.getOID(curveName), + ecParams.getCurve(), + ecParams.getG(), + ecParams.getN(), + ecParams.getH(), + ecParams.getSeed()); + } + + private EcCommutativeCipher(HashType hashType, ECPrivateKey key, SupportedCurve ecCurve) { + super(hashType, key, ecCurve); + domainParams = getDomainParams(ecCurve); + } + + /** + * Creates an EcCommutativeCipher object with a new random private key based on the {@code curve}. + * Use this method when the key is created for the first time or it needs to be refreshed. + * + * <p>New users should use SHA256 as the underlying hash function. + */ + public static EcCommutativeCipher createWithNewKey(SupportedCurve curve, HashType hashType) { + return new EcCommutativeCipher(hashType, createPrivateKey(curve), curve); + } + + /** + * Creates an EcCommutativeCipher object with a new random private key based on the {@code curve}. + * Use this method when the key is created for the first time or it needs to be refreshed. + * + * <p>The underlying hash type will be SHA256. + */ + public static EcCommutativeCipher createWithNewKey(SupportedCurve curve) { + return createWithNewKey(curve, HashType.SHA256); + } + + /** + * Creates an EcCommutativeCipher object from the given key. A new key should be created for each + * session and all values should be unique in one session because the encryption is deterministic. + * Use this when the key is stored securely to be used at different steps of the protocol in the + * same session or by multiple processes. + * + * <p>New users should use SHA256 as the underying hash function. + * + * @throws IllegalArgumentException if the key encoding is invalid. + */ + public static EcCommutativeCipher createFromKey( + SupportedCurve curve, HashType hashType, byte[] keyBytes) { + try { + BigInteger key = byteArrayToBigIntegerCppCompatible(keyBytes); + return new EcCommutativeCipher(hashType, decodePrivateKey(key, curve), curve); + } catch (InvalidKeySpecException e) { + throw new IllegalArgumentException(e.getMessage()); + } + } + + /** + * Creates an EcCommutativeCipher object from the given key. A new key should be created for each + * session and all values should be unique in one session because the encryption is deterministic. + * Use this when the key is stored securely to be used at different steps of the protocol in the + * same session or by multiple processes. + * + * <p>The underlying hash type will be SHA256. + * + * @throws IllegalArgumentException if the key encoding is invalid. + */ + public static EcCommutativeCipher createFromKey(SupportedCurve curve, byte[] keyBytes) { + return createFromKey(curve, HashType.SHA256, keyBytes); + } + + // copybara:strip_begin(Remove deprecated functions) + /** + * Creates an EcCommutativeCipher object from the given key. A new key should be created for each + * session and all values should be unique in one session because the encryption is deterministic. + * Use this when the key is stored securely to be used at different steps of the protocol in the + * same session or by multiple processes. + * + * @deprecated This function is incompatible with the C++ implementation. + * @throws IllegalArgumentException if the key encoding is invalid. + */ + @Deprecated + public static EcCommutativeCipher createFromKeyCppIncompatible( + SupportedCurve curve, byte[] keyBytes) { + try { + BigInteger key = new BigInteger(keyBytes); + return new EcCommutativeCipher(HashType.SHA256, decodePrivateKey(key, curve), curve); + } catch (InvalidKeySpecException e) { + throw new IllegalArgumentException(e.getMessage()); + } + } + // copybara:strip_end + + /** + * Checks if a ciphertext (compressed encoded point) is on the elliptic curve. + * + * @param ciphertext the ciphertext that needs verification if it's on the curve. + * @return true if the point is valid and non-infinite + */ + public static boolean validateCiphertext(byte[] ciphertext, SupportedCurve supportedCurve) { + try { + ECPoint point = getDomainParams(supportedCurve).getCurve().decodePoint(ciphertext); + return point.isValid() && !point.isInfinity(); + } catch (IllegalArgumentException ignored) { + return false; + } + } + + /** + * Internal implementation of {@code #hashIntoTheCurve} method. + * + * <p>See the documentation of {@code #hashIntoTheCurve} for details. + */ + @Override + protected java.security.spec.ECPoint hashIntoTheCurveInternal(byte[] byteId) { + ECCurve ecCurve = domainParams.getCurve(); + ECFieldElement a = ecCurve.getA(); + ECFieldElement b = ecCurve.getB(); + BigInteger p = ((Fp) ecCurve).getQ(); + BigInteger x = randomOracle(byteId, p, hashType); + while (true) { + ECFieldElement fieldX = ecCurve.fromBigInteger(x); + // y2 = x ^ 3 + a x + b + ECFieldElement y2 = fieldX.multiply(fieldX.square().add(a)).add(b); + ECFieldElement y2Sqrt = y2.sqrt(); + if (y2Sqrt != null) { + if (y2Sqrt.toBigInteger().testBit(0)) { + return new java.security.spec.ECPoint( + fieldX.toBigInteger(), y2Sqrt.negate().toBigInteger()); + } + return new java.security.spec.ECPoint(fieldX.toBigInteger(), y2Sqrt.toBigInteger()); + } + x = randomOracle(bigIntegerToByteArrayCppCompatible(x), p, hashType); + } + } + + /** + * Hashes bytes to a point on the elliptic curve y^2 = x^3 + ax + b over a prime field. + * + * <p>To hash byteId to a point on the curve, the algorithm first computes an integer hash value x + * = h(byteId) and determines whether x is the abscissa of a point on the elliptic curve y^2 = x^3 + * + ax + b. If so, we take the positive square root of y^2. If not, set x = h(x) and try again. + * + * @param byteId the value to hash into the curve + * @return a point on the curve encoded in compressed form as defined in ANSI X9.62 ECDSA + */ + @Override + public byte[] hashIntoTheCurve(byte[] byteId) { + return convertECPoint(hashIntoTheCurveInternal(byteId)).getEncoded(true); + } + + /** + * Encrypts an ECPoint with the private key. + * + * @param point a point to encrypt + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. + */ + private byte[] encrypt(ECPoint point) { + return point.multiply(privateKey.getS()).getEncoded(true); + } + + /** + * Encrypts an input with the private key, first hashing the input to the curve. + * + * @param plaintext bytes to encrypt + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. + */ + @Override + public byte[] encrypt(byte[] plaintext) { + java.security.spec.ECPoint point = hashIntoTheCurveInternal(plaintext); + return encrypt(convertECPoint(point)); + } + + /** + * Re-encrypts an encoded point with the private key. + * + * @param ciphertext an encoded point as defined in ANSI X9.62 ECDSA + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA + * @throws IllegalArgumentException if the encoding is invalid or if the decoded point is not on + * the curve, or is the point at infinity + */ + @Override + public byte[] reEncrypt(byte[] ciphertext) { + ECPoint point = checkPointOnCurve(ciphertext); + return encrypt(point); + } + + /** + * Decrypts an encoded point that has been previously encrypted with the private key. Does not + * reverse hashing to the curve. + * + * @param ciphertext an encoded point as defined in ANSI X9.62 ECDSA + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA + * @throws IllegalArgumentException if the encoding is invalid or if the decoded point is not on + * the curve, or is the point at infinity + */ + @Override + public byte[] decrypt(byte[] ciphertext) { + ECPoint point = checkPointOnCurve(ciphertext); + BigInteger privateKeyInverse = privateKey.getS().modInverse(privateKey.getParams().getOrder()); + return point.multiply(privateKeyInverse).getEncoded(true); + } + + /** + * Checks that a compressed encoded point is on the elliptic curve. + * + * @param compressedPoint the point that needs verification + * @return a valid ECPoint obtained from the compressed point + * @throws IllegalArgumentException if the encoding is invalid, the point is not on the curve, or + * is the point at infinity + */ + private ECPoint checkPointOnCurve(byte[] compressedPoint) { + ECPoint point = domainParams.getCurve().decodePoint(compressedPoint); + Preconditions.checkArgument(point.isValid(), "Invalid point: the point is not on the curve"); + Preconditions.checkArgument(!point.isInfinity(), "Invalid point: the point is at infinity"); + return point; + } + + /** + * Encodes an ECPoint. + * + * @param point a point to encrypt + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. + */ + @Override + protected byte[] getEncoded(java.security.spec.ECPoint point) { + return convertECPoint(point).getEncoded(true); + } + + /** + * Checks validity of a point. + * + * @param point a point to check + * @return true iff point is valid. + */ + @Override + protected boolean isValid(java.security.spec.ECPoint point) { + return convertECPoint(point).isValid(); + } + + /** + * Checks whether a point is at infinity. + * + * @param point a point to check + * @return true iff point is infinity. + */ + @Override + protected boolean isInfinity(java.security.spec.ECPoint point) { + return convertECPoint(point).isInfinity(); + } + + /** Converts a JCE ECPoint object to a BouncyCastle ECPoint. */ + private ECPoint convertECPoint(java.security.spec.ECPoint point) { + return domainParams.getCurve().createPoint(point.getAffineX(), point.getAffineY()); + } +} diff --git a/java/com/google/privacy/private_join_and_compute/encryption/commutative/EcCommutativeCipherBase.java b/java/com/google/privacy/private_join_and_compute/encryption/commutative/EcCommutativeCipherBase.java new file mode 100644 index 0000000..5a9cc63 --- /dev/null +++ b/java/com/google/privacy/private_join_and_compute/encryption/commutative/EcCommutativeCipherBase.java @@ -0,0 +1,264 @@ +package com.google.privacy.private_join_and_compute.encryption.commutative; + +import com.google.common.annotations.VisibleForTesting; +import com.google.common.hash.Hashing; +import com.google.common.primitives.Bytes; +import java.math.BigInteger; +import java.security.KeyFactory; +import java.security.KeyPairGenerator; +import java.security.NoSuchAlgorithmException; +import java.security.SecureRandom; +import java.security.interfaces.ECPrivateKey; +import java.security.spec.ECParameterSpec; +import java.security.spec.ECPoint; +import java.security.spec.ECPrivateKeySpec; +import java.security.spec.InvalidKeySpecException; + +/** + * EcCommutativeCipher class with the property that K1(K2(a)) = K2(K1(a)) where K(a) is encryption + * with the key K. + * + * <p>This class allows two parties to determine if they share the same value, without revealing the + * sensitive value to each other. See the paper "Using Commutative Encryption to Share a Secret" at + * https://eprint.iacr.org/2008/356.pdf for reference. + * + * <p>The encryption is performed over an elliptic curve. + * + * <p>Security: The provided bit security is half the number of bits of the underlying curve. For + * example, using curve secp160r1 gives 80 bit security. + */ +public abstract class EcCommutativeCipherBase { + /** List of supported underlying hash types for the commutative cipher. */ + public enum HashType { + SHA256(256), + SHA384(384), + SHA512(512); + + private final int hashBitLength; + + private HashType(int hashBitLength) { + this.hashBitLength = hashBitLength; + } + + /** Returns the bit length. */ + public int getHashBitLength() { + return hashBitLength; + } + } + + // EC classes are conceptually immutable even though the class is not annotated accordingly. + @SuppressWarnings("Immutable") + protected final ECPrivateKey privateKey; + + @SuppressWarnings("Immutable") + protected final SupportedCurve ecCurve; + + protected final HashType hashType; + + /** Creates an EcCommutativeCipherBase object with the given private key and curve. */ + protected EcCommutativeCipherBase(HashType hashType, ECPrivateKey key, SupportedCurve ecCurve) { + this.privateKey = key; + this.ecCurve = ecCurve; + this.hashType = hashType; + } + + /** Decodes the private key from BigInteger. */ + protected static ECPrivateKey decodePrivateKey(BigInteger key, SupportedCurve curve) + throws InvalidKeySpecException { + checkPrivateKey(key, curve.getParameterSpec()); + ECPrivateKeySpec privateKeySpec = new ECPrivateKeySpec(key, curve.getParameterSpec()); + try { + KeyFactory keyFactory = KeyFactory.getInstance("EC"); + return (ECPrivateKey) keyFactory.generatePrivate(privateKeySpec); + } catch (NoSuchAlgorithmException e) { + throw new AssertionError(e); + } + } + + /** Creates a new random private key. */ + protected static ECPrivateKey createPrivateKey(SupportedCurve curve) { + try { + KeyPairGenerator generator = KeyPairGenerator.getInstance("EC"); + generator.initialize(curve.getParameterSpec(), new SecureRandom()); + return (ECPrivateKey) generator.generateKeyPair().getPrivate(); + } catch (Exception e) { + throw new AssertionError(e); + } + } + + /** + * Encrypts an input with the private key, first hashing the input to the curve. + * + * @param plaintext bytes to encrypt + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. + */ + public abstract byte[] encrypt(byte[] plaintext); + + /** + * Re-encrypts an encoded point with the private key. + * + * @param ciphertext an encoded point as defined in ANSI X9.62 ECDSA + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA + */ + public abstract byte[] reEncrypt(byte[] ciphertext); + + /** + * Decrypts an encoded point that has been previously encrypted with the private key. Does not + * reverse hashing to the curve. + * + * @param ciphertext an encoded point as defined in ANSI X9.62 ECDSA + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA + */ + public abstract byte[] decrypt(byte[] ciphertext); + + /** + * Hashes bytes to a point on the elliptic curve y^2 = x^3 + ax + b over a prime field. + */ + @VisibleForTesting + abstract ECPoint hashIntoTheCurveInternal(byte[] byteId); + + /** + * Hashes bytes to a point on the elliptic curve y^2 = x^3 + ax + b over a prime field. All + * implementations must match the C++ version: + * + * <p>The resulting point is returned encoded in compressed form as defined in ANSI X9.62 ECDSA. + */ + public abstract byte[] hashIntoTheCurve(byte[] byteId); + + /** + * A random oracle function mapping x deterministically into a large domain. + * + * <p>// copybara:strip_begin(Remove internal comment) + * + * <p>The random oracle is similar to the example given in the last paragraph of Chapter 6 of [1] + * where the output is expanded by successively hashing the concatenation of the input with a + * fixed sized counter starting from 1. + * + * <p>[1] Bellare, Mihir, and Phillip Rogaway. "Random oracles are practical: A paradigm for + * designing efficient protocols." Proceedings of the 1st ACM conference on Computer and + * communications security. ACM, 1993. + * + * <p>Returns a value from the set [0, max_value). + * + * <p>Check Error: if bit length of max_value is greater than 130048. Since the counter used for + * expanding the output is expanded to 8 bit length (hard-coded), any counter value that is + * greater than 512 would cause variable length inputs passed to the underlying + * sha256/sha384/sha512 calls and might make this random oracle's output not uniform across the + * output domain. + * + * <p>The output length is increased by a security value of 256 which reduces the bias of + * selecting certain values more often than others when max_value is not a multiple of 2. + */ + public static BigInteger randomOracle(byte[] bytes, BigInteger maxValue, HashType hashType) { + int hashBitLength = hashType.getHashBitLength(); + int outputBitLength = maxValue.bitLength() + hashBitLength; + int iterCount = (outputBitLength + hashBitLength - 1) / hashBitLength; + int excessBitCount = (iterCount * hashBitLength) - outputBitLength; + BigInteger hashOutput = BigInteger.ZERO; + BigInteger counter = BigInteger.ONE; + for (int i = 1; i < iterCount + 1; ++i) { + hashOutput = hashOutput.shiftLeft(hashBitLength); + byte[] counterBytes = bigIntegerToByteArrayCppCompatible(counter); + byte[] hashInput = Bytes.concat(counterBytes, bytes); + byte[] hashCode; + switch (hashType) { + case SHA256: + hashCode = Hashing.sha256().hashBytes(hashInput).asBytes(); + break; + case SHA384: + hashCode = Hashing.sha384().hashBytes(hashInput).asBytes(); + break; + default: + hashCode = Hashing.sha512().hashBytes(hashInput).asBytes(); + } + hashOutput = hashOutput.add(byteArrayToBigIntegerCppCompatible(hashCode)); + counter = counter.add(BigInteger.ONE); + } + return hashOutput.shiftRight(excessBitCount).mod(maxValue); + } + + /** Checks the private key is between 1 and the order of the group. */ + private static void checkPrivateKey(BigInteger key, ECParameterSpec params) { + if (key.compareTo(BigInteger.ONE) <= 0 || key.compareTo(params.getOrder()) >= 0) { + throw new IllegalArgumentException("The given key is out of bounds."); + } + } + + /** + * Returns the private key bytes. + * + * @return the private key bytes for this EcCommutativeCipher. + */ + public byte[] getPrivateKeyBytes() { + return bigIntegerToByteArrayCppCompatible(privateKey.getS()); + } + + // copybara:strip_begin(Remove deprecated functions) + /** + * Returns the private key bytes. + * + * @deprecated This function is incompatible with the C++ implementation. + * @return the private key bytes for this EcCommutativeCipher. + */ + @Deprecated + public byte[] getPrivateKeyBytesCppIncompatible() { + return privateKey.getS().toByteArray(); + } + // copybara:strip_end + + /** + * This function converts a BigInteger into a byte array in big-endian form without two's + * complement representation. This function is compatible with C++ OpenSSL's BigNum + * implementation. + */ + public static byte[] bigIntegerToByteArrayCppCompatible(BigInteger value) { + byte[] signedArray = value.toByteArray(); + int leadingZeroes = 0; + while (signedArray[leadingZeroes] == 0) { + leadingZeroes++; + } + byte[] unsignedArray = new byte[signedArray.length - leadingZeroes]; + System.arraycopy(signedArray, leadingZeroes, unsignedArray, 0, unsignedArray.length); + return unsignedArray; + } + + /** + * This function converts bytes to BigInteger. The input bytes are assumed to be in big-endian + * form. The function converts the bytes into two's complement big-endian form before converting + * into a BigInteger. This function matches the C++ OpenSSL implementation of bytes to BigNum. + */ + public static BigInteger byteArrayToBigIntegerCppCompatible(byte[] bytes) { + byte[] twosComplement = new byte[bytes.length + 1]; + twosComplement[0] = 0; + System.arraycopy(bytes, 0, twosComplement, 1, bytes.length); + return new BigInteger(twosComplement); + } + + /** + * Encodes a point. + * + * @param point a point to encode + * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. + */ + @VisibleForTesting + abstract byte[] getEncoded(ECPoint point); + + /** + * Checks validity of a point. + * + * @param point a point to check + * @return true iff point is valid. + */ + @VisibleForTesting + abstract boolean isValid(ECPoint point); + + /** + * Checks whether a point is at infinity. + * + * @param point a point to check + * @return true iff point is infinity. + */ + @VisibleForTesting + abstract boolean isInfinity(ECPoint point); +} + diff --git a/java/com/google/privacy/private_join_and_compute/encryption/commutative/SupportedCurve.java b/java/com/google/privacy/private_join_and_compute/encryption/commutative/SupportedCurve.java new file mode 100644 index 0000000..c7e3185 --- /dev/null +++ b/java/com/google/privacy/private_join_and_compute/encryption/commutative/SupportedCurve.java @@ -0,0 +1,47 @@ +package com.google.privacy.private_join_and_compute.encryption.commutative; + +import java.security.AlgorithmParameters; +import java.security.spec.ECGenParameterSpec; +import java.security.spec.ECParameterSpec; + +/** List of supported curves for the commutative cipher. */ +public enum SupportedCurve { + SECP256R1("secp256r1"), + SECP384R1("secp384r1"); + + // These parameter classes are conceptually immutable even though the classes are not annotated + // accordingly. + @SuppressWarnings("Immutable") + private final ECParameterSpec parameterSpec; + + @SuppressWarnings("Immutable") + private final ECGenParameterSpec genParameterSpec; + + private final String curveName; + + private SupportedCurve(String curveName) { + try { + AlgorithmParameters parameters = AlgorithmParameters.getInstance("EC"); + parameters.init(new ECGenParameterSpec(curveName)); + parameterSpec = parameters.getParameterSpec(ECParameterSpec.class); + genParameterSpec = new ECGenParameterSpec(curveName); + this.curveName = curveName; + } catch (Exception e) { + throw new AssertionError(e); + } + } + + /** Returns the generated parameter specs. */ + public ECGenParameterSpec getGenParameterSpec() { + return genParameterSpec; + } + + /** Returns the parameter specs. */ + public ECParameterSpec getParameterSpec() { + return parameterSpec; + } + + public String getCurveName() { + return curveName; + } +} |