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