1 package com.google.privacy.private_join_and_compute.encryption.commutative; 2 3 import com.google.common.base.Preconditions; 4 import java.math.BigInteger; 5 import java.security.interfaces.ECPrivateKey; 6 import java.security.spec.InvalidKeySpecException; 7 import org.bouncycastle.asn1.sec.SECNamedCurves; 8 import org.bouncycastle.asn1.x9.X9ECParameters; 9 import org.bouncycastle.crypto.params.ECNamedDomainParameters; 10 import org.bouncycastle.math.ec.ECCurve; 11 import org.bouncycastle.math.ec.ECCurve.Fp; 12 import org.bouncycastle.math.ec.ECFieldElement; 13 import org.bouncycastle.math.ec.ECPoint; 14 15 /** 16 * Implementation of EcCommutativeCipher using BouncyCastle. 17 * 18 * <p>EcCommutativeCipher class with the property that K1(K2(a)) = K2(K1(a)) where K(a) is 19 * encryption with the key K. 20 * 21 * <p>This class allows two parties to determine if they share the same value, without revealing the 22 * sensitive value to each other. See the paper "Using Commutative Encryption to Share a Secret" at 23 * https://eprint.iacr.org/2008/356.pdf for reference. 24 * 25 * <p>The encryption is performed over an elliptic curve. 26 * 27 * <p>Security: The provided bit security is half the number of bits of the underlying curve. For 28 * example, using curve secp160r1 gives 80 bit security. 29 */ 30 public final class EcCommutativeCipher extends EcCommutativeCipherBase { 31 32 @SuppressWarnings("Immutable") 33 private final ECNamedDomainParameters domainParams; 34 getDomainParams(SupportedCurve curve)35 private static ECNamedDomainParameters getDomainParams(SupportedCurve curve) { 36 String curveName = curve.getCurveName(); 37 X9ECParameters ecParams = SECNamedCurves.getByName(curveName); 38 return new ECNamedDomainParameters( 39 SECNamedCurves.getOID(curveName), 40 ecParams.getCurve(), 41 ecParams.getG(), 42 ecParams.getN(), 43 ecParams.getH(), 44 ecParams.getSeed()); 45 } 46 EcCommutativeCipher(HashType hashType, ECPrivateKey key, SupportedCurve ecCurve)47 private EcCommutativeCipher(HashType hashType, ECPrivateKey key, SupportedCurve ecCurve) { 48 super(hashType, key, ecCurve); 49 domainParams = getDomainParams(ecCurve); 50 } 51 52 /** 53 * Creates an EcCommutativeCipher object with a new random private key based on the {@code curve}. 54 * Use this method when the key is created for the first time or it needs to be refreshed. 55 * 56 * <p>New users should use SHA256 as the underlying hash function. 57 */ createWithNewKey(SupportedCurve curve, HashType hashType)58 public static EcCommutativeCipher createWithNewKey(SupportedCurve curve, HashType hashType) { 59 return new EcCommutativeCipher(hashType, createPrivateKey(curve), curve); 60 } 61 62 /** 63 * Creates an EcCommutativeCipher object with a new random private key based on the {@code curve}. 64 * Use this method when the key is created for the first time or it needs to be refreshed. 65 * 66 * <p>The underlying hash type will be SHA256. 67 */ createWithNewKey(SupportedCurve curve)68 public static EcCommutativeCipher createWithNewKey(SupportedCurve curve) { 69 return createWithNewKey(curve, HashType.SHA256); 70 } 71 72 /** 73 * Creates an EcCommutativeCipher object from the given key. A new key should be created for each 74 * session and all values should be unique in one session because the encryption is deterministic. 75 * Use this when the key is stored securely to be used at different steps of the protocol in the 76 * same session or by multiple processes. 77 * 78 * <p>New users should use SHA256 as the underying hash function. 79 * 80 * @throws IllegalArgumentException if the key encoding is invalid. 81 */ createFromKey( SupportedCurve curve, HashType hashType, byte[] keyBytes)82 public static EcCommutativeCipher createFromKey( 83 SupportedCurve curve, HashType hashType, byte[] keyBytes) { 84 try { 85 BigInteger key = byteArrayToBigIntegerCppCompatible(keyBytes); 86 return new EcCommutativeCipher(hashType, decodePrivateKey(key, curve), curve); 87 } catch (InvalidKeySpecException e) { 88 throw new IllegalArgumentException(e.getMessage()); 89 } 90 } 91 92 /** 93 * Creates an EcCommutativeCipher object from the given key. A new key should be created for each 94 * session and all values should be unique in one session because the encryption is deterministic. 95 * Use this when the key is stored securely to be used at different steps of the protocol in the 96 * same session or by multiple processes. 97 * 98 * <p>The underlying hash type will be SHA256. 99 * 100 * @throws IllegalArgumentException if the key encoding is invalid. 101 */ createFromKey(SupportedCurve curve, byte[] keyBytes)102 public static EcCommutativeCipher createFromKey(SupportedCurve curve, byte[] keyBytes) { 103 return createFromKey(curve, HashType.SHA256, keyBytes); 104 } 105 106 // copybara:strip_begin(Remove deprecated functions) 107 /** 108 * Creates an EcCommutativeCipher object from the given key. A new key should be created for each 109 * session and all values should be unique in one session because the encryption is deterministic. 110 * Use this when the key is stored securely to be used at different steps of the protocol in the 111 * same session or by multiple processes. 112 * 113 * @deprecated This function is incompatible with the C++ implementation. 114 * @throws IllegalArgumentException if the key encoding is invalid. 115 */ 116 @Deprecated createFromKeyCppIncompatible( SupportedCurve curve, byte[] keyBytes)117 public static EcCommutativeCipher createFromKeyCppIncompatible( 118 SupportedCurve curve, byte[] keyBytes) { 119 try { 120 BigInteger key = new BigInteger(keyBytes); 121 return new EcCommutativeCipher(HashType.SHA256, decodePrivateKey(key, curve), curve); 122 } catch (InvalidKeySpecException e) { 123 throw new IllegalArgumentException(e.getMessage()); 124 } 125 } 126 // copybara:strip_end 127 128 /** 129 * Checks if a ciphertext (compressed encoded point) is on the elliptic curve. 130 * 131 * @param ciphertext the ciphertext that needs verification if it's on the curve. 132 * @return true if the point is valid and non-infinite 133 */ validateCiphertext(byte[] ciphertext, SupportedCurve supportedCurve)134 public static boolean validateCiphertext(byte[] ciphertext, SupportedCurve supportedCurve) { 135 try { 136 ECPoint point = getDomainParams(supportedCurve).getCurve().decodePoint(ciphertext); 137 return point.isValid() && !point.isInfinity(); 138 } catch (IllegalArgumentException ignored) { 139 return false; 140 } 141 } 142 143 /** 144 * Internal implementation of {@code #hashIntoTheCurve} method. 145 * 146 * <p>See the documentation of {@code #hashIntoTheCurve} for details. 147 */ 148 @Override hashIntoTheCurveInternal(byte[] byteId)149 protected java.security.spec.ECPoint hashIntoTheCurveInternal(byte[] byteId) { 150 ECCurve ecCurve = domainParams.getCurve(); 151 ECFieldElement a = ecCurve.getA(); 152 ECFieldElement b = ecCurve.getB(); 153 BigInteger p = ((Fp) ecCurve).getQ(); 154 BigInteger x = randomOracle(byteId, p, hashType); 155 while (true) { 156 ECFieldElement fieldX = ecCurve.fromBigInteger(x); 157 // y2 = x ^ 3 + a x + b 158 ECFieldElement y2 = fieldX.multiply(fieldX.square().add(a)).add(b); 159 ECFieldElement y2Sqrt = y2.sqrt(); 160 if (y2Sqrt != null) { 161 if (y2Sqrt.toBigInteger().testBit(0)) { 162 return new java.security.spec.ECPoint( 163 fieldX.toBigInteger(), y2Sqrt.negate().toBigInteger()); 164 } 165 return new java.security.spec.ECPoint(fieldX.toBigInteger(), y2Sqrt.toBigInteger()); 166 } 167 x = randomOracle(bigIntegerToByteArrayCppCompatible(x), p, hashType); 168 } 169 } 170 171 /** 172 * Hashes bytes to a point on the elliptic curve y^2 = x^3 + ax + b over a prime field. 173 * 174 * <p>To hash byteId to a point on the curve, the algorithm first computes an integer hash value x 175 * = h(byteId) and determines whether x is the abscissa of a point on the elliptic curve y^2 = x^3 176 * + ax + b. If so, we take the positive square root of y^2. If not, set x = h(x) and try again. 177 * 178 * @param byteId the value to hash into the curve 179 * @return a point on the curve encoded in compressed form as defined in ANSI X9.62 ECDSA 180 */ 181 @Override hashIntoTheCurve(byte[] byteId)182 public byte[] hashIntoTheCurve(byte[] byteId) { 183 return convertECPoint(hashIntoTheCurveInternal(byteId)).getEncoded(true); 184 } 185 186 /** 187 * Encrypts an ECPoint with the private key. 188 * 189 * @param point a point to encrypt 190 * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. 191 */ encrypt(ECPoint point)192 private byte[] encrypt(ECPoint point) { 193 return point.multiply(privateKey.getS()).getEncoded(true); 194 } 195 196 /** 197 * Encrypts an input with the private key, first hashing the input to the curve. 198 * 199 * @param plaintext bytes to encrypt 200 * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. 201 */ 202 @Override encrypt(byte[] plaintext)203 public byte[] encrypt(byte[] plaintext) { 204 java.security.spec.ECPoint point = hashIntoTheCurveInternal(plaintext); 205 return encrypt(convertECPoint(point)); 206 } 207 208 /** 209 * Re-encrypts an encoded point with the private key. 210 * 211 * @param ciphertext an encoded point as defined in ANSI X9.62 ECDSA 212 * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA 213 * @throws IllegalArgumentException if the encoding is invalid or if the decoded point is not on 214 * the curve, or is the point at infinity 215 */ 216 @Override reEncrypt(byte[] ciphertext)217 public byte[] reEncrypt(byte[] ciphertext) { 218 ECPoint point = checkPointOnCurve(ciphertext); 219 return encrypt(point); 220 } 221 222 /** 223 * Decrypts an encoded point that has been previously encrypted with the private key. Does not 224 * reverse hashing to the curve. 225 * 226 * @param ciphertext an encoded point as defined in ANSI X9.62 ECDSA 227 * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA 228 * @throws IllegalArgumentException if the encoding is invalid or if the decoded point is not on 229 * the curve, or is the point at infinity 230 */ 231 @Override decrypt(byte[] ciphertext)232 public byte[] decrypt(byte[] ciphertext) { 233 ECPoint point = checkPointOnCurve(ciphertext); 234 BigInteger privateKeyInverse = privateKey.getS().modInverse(privateKey.getParams().getOrder()); 235 return point.multiply(privateKeyInverse).getEncoded(true); 236 } 237 238 /** 239 * Checks that a compressed encoded point is on the elliptic curve. 240 * 241 * @param compressedPoint the point that needs verification 242 * @return a valid ECPoint obtained from the compressed point 243 * @throws IllegalArgumentException if the encoding is invalid, the point is not on the curve, or 244 * is the point at infinity 245 */ checkPointOnCurve(byte[] compressedPoint)246 private ECPoint checkPointOnCurve(byte[] compressedPoint) { 247 ECPoint point = domainParams.getCurve().decodePoint(compressedPoint); 248 Preconditions.checkArgument(point.isValid(), "Invalid point: the point is not on the curve"); 249 Preconditions.checkArgument(!point.isInfinity(), "Invalid point: the point is at infinity"); 250 return point; 251 } 252 253 /** 254 * Encodes an ECPoint. 255 * 256 * @param point a point to encrypt 257 * @return an encoded point in compressed form as defined in ANSI X9.62 ECDSA. 258 */ 259 @Override getEncoded(java.security.spec.ECPoint point)260 protected byte[] getEncoded(java.security.spec.ECPoint point) { 261 return convertECPoint(point).getEncoded(true); 262 } 263 264 /** 265 * Checks validity of a point. 266 * 267 * @param point a point to check 268 * @return true iff point is valid. 269 */ 270 @Override isValid(java.security.spec.ECPoint point)271 protected boolean isValid(java.security.spec.ECPoint point) { 272 return convertECPoint(point).isValid(); 273 } 274 275 /** 276 * Checks whether a point is at infinity. 277 * 278 * @param point a point to check 279 * @return true iff point is infinity. 280 */ 281 @Override isInfinity(java.security.spec.ECPoint point)282 protected boolean isInfinity(java.security.spec.ECPoint point) { 283 return convertECPoint(point).isInfinity(); 284 } 285 286 /** Converts a JCE ECPoint object to a BouncyCastle ECPoint. */ convertECPoint(java.security.spec.ECPoint point)287 private ECPoint convertECPoint(java.security.spec.ECPoint point) { 288 return domainParams.getCurve().createPoint(point.getAffineX(), point.getAffineY()); 289 } 290 } 291