crypto: ecc: add vli and ecc ops

Add functions to copy vli from buffers, to print vli in
big endian format, for vli mod and mod multiplication ops,
ecc point addition and ecc pub key validation.

Bug 1804937

Change-Id: I1a32a429eb4a35f29f146caf56cf496783edf01c
Signed-off-by: Nitin Kumbhar <nkumbhar@nvidia.com>
Reviewed-on: http://git-master/r/1298777
Reviewed-by: Automatic_Commit_Validation_User
Reviewed-by: Mallikarjun Kasoju <mkasoju@nvidia.com>
GVS: Gerrit_Virtual_Submit

diff --git a/crypto/ecc.c b/crypto/ecc.c
index a8c10e725138fe9c669c23cc4750f6e842e82cc8..1b8e8d24885943770bca2b596e0bc7a2f70ce619 100644 (file)
--- a/crypto/ecc.c
+++ b/crypto/ecc.c
@@ -208,6 +208,42 @@ static void vli_set(u64 *dest, const u64 *src, unsigned int ndigits)
                dest[i] = src[i];
 }
 
+/* Copy from vli to buf.
+ * For buffers smaller than vli: copy only LSB nbytes from vli.
+ * For buffers larger than vli : fill up remaining buf with zeroes.
+ */
+void vli_copy_to_buf(u8 *dst_buf, unsigned int buf_len,
+                    const u64 *src_vli, unsigned int ndigits)
+{
+       unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+       u8 *vli = (u8 *)src_vli;
+       int i;
+
+       for (i = 0; i < buf_len && i < nbytes; i++)
+               dst_buf[i] = vli[i];
+
+       for (; i < buf_len; i++)
+               dst_buf[i] = 0;
+}
+
+/* Copy from buffer to vli.
+ * For buffers smaller than vli: fill up remaining vli with zeroes.
+ * For buffers larger than vli : copy only LSB nbytes to vli.
+ */
+void vli_copy_from_buf(u64 *dst_vli, unsigned int ndigits,
+                      const u8 *src_buf, unsigned int buf_len)
+{
+       unsigned int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+       u8 *vli = (u8 *)dst_vli;
+       int i;
+
+       for (i = 0; i < buf_len && i < nbytes; i++)
+               vli[i] = src_buf[i];
+
+       for (; i < nbytes; i++)
+               vli[i] = 0;
+}
+
 /* Returns sign of left - right. */
 static int vli_cmp(const u64 *left, const u64 *right, unsigned int ndigits)
 {
@@ -440,6 +476,83 @@ static void vli_mod_sub(u64 *result, const u64 *left, const u64 *right,
                vli_add(result, result, mod, ndigits);
 }
 
+/* Computes result = input % mod.
+ * Assumes that input < mod, result != mod.
+ */
+void vli_mod(u64 *result, const u64 *input, const u64 *mod,
+            unsigned int ndigits)
+{
+       if (vli_cmp(input, mod, ndigits) >= 0)
+               vli_sub(result, input, mod, ndigits);
+       else
+               vli_set(result, input, ndigits);
+}
+
+/* Print vli in big-endian format.
+ * The bytes are printed in hex.
+ */
+void vli_print(char *vli_name, const u64 *vli, unsigned int ndigits)
+{
+       int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+       int buf_size = 2 * ECC_MAX_DIGIT_BYTES + 1;
+       unsigned char *c, buf[buf_size];
+       int i, j;
+
+       c = (unsigned char *)vli;
+
+       for (i = nbytes - 1, j = 0; i >= 0 && j < buf_size; i--, j += 2)
+               snprintf(&buf[j], 3, "%02x", *(c + i));
+
+       buf[j] = '\0';
+
+       pr_info("%20s(BigEnd)=%s\n", vli_name, buf);
+}
+
+/* Computes result = (left * right) % mod.
+ * Assumes that left < mod and right < mod, result != mod.
+ * Uses:
+ *     (a * b) % m = ((a % m) * (b % m)) % m
+ *     (a * b) % m = (a + a + ... + a) % m = b modular additions of (a % m)
+ */
+void vli_mod_mult(u64 *result, const u64 *left, const u64 *right,
+                 const u64 *mod, unsigned int ndigits)
+{
+       u64 t1[ndigits], mm[ndigits];
+       u64 aa[ndigits], bb[ndigits];
+
+       vli_clear(result, ndigits);
+       vli_set(aa, left, ndigits);
+       vli_set(bb, right, ndigits);
+       vli_set(mm, mod, ndigits);
+
+       /* aa = aa % mm */
+       vli_mod(aa, aa, mm, ndigits);
+
+       /* bb = bb % mm */
+       vli_mod(bb, bb, mm, ndigits);
+
+       while (!vli_is_zero(bb, ndigits)) {
+
+               /* if bb is odd i.e. 0th bit set then add
+                * aa i.e. result = (result + aa) % mm
+                */
+               if (vli_test_bit(bb, 0))
+                       vli_mod_add(result, result, aa, mm, ndigits);
+
+               /* bb = bb / 2 = bb >> 1 */
+               vli_rshift1(bb, ndigits);
+
+               /* aa = (aa * 2) % mm */
+               vli_sub(t1, mm, aa, ndigits);
+               if (vli_cmp(aa, t1, ndigits) == -1)
+                       /* if aa < t1 then aa = aa * 2 = aa << 1*/
+                       vli_lshift(aa, aa, 1, ndigits);
+               else
+                       /* if aa >= t1 then aa = aa - t1 */
+                       vli_sub(aa, aa, t1, ndigits);
+       }
+}
+
 /* Computes p_result = p_product % curve_p.
  * See algorithm 5 and 6 from
  * http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf
@@ -878,6 +991,61 @@ static void xycz_add_c(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime,
        vli_set(x1, t7, ndigits);
 }
 
+/* Point addition.
+ * Add 2 distinct points on elliptic curve to get a new point.
+ *
+ * P = (x1,y1)and Q = (x2, y2) then P + Q = (x3,y3) where
+ * x3 = ((y2-y1)/(x2-x1))^2 - x1 - x2
+ * y3 = ((y2-y1)/(x2-x1))(x1-x3) - y1
+ *
+ * Q => P + Q
+ */
+void ecc_point_add(u64 *x1, u64 *y1, u64 *x2, u64 *y2, u64 *curve_prime,
+                  unsigned int ndigits)
+{
+       /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
+       u64 t5[ndigits];
+       u64 t6[ndigits];
+       u64 t7[ndigits];
+
+       /* t6 = x2 - x1 */
+       vli_mod_sub(t6, x2, x1, curve_prime, ndigits);
+       /* t6 = (x2 - x1)^2 = A */
+       vli_mod_square_fast(t6, t6, curve_prime, ndigits);
+       vli_mod_inv(t7, t6, curve_prime, ndigits);
+       /* t5 = x2 - x1 */
+       vli_mod_sub(t5, x2, x1, curve_prime, ndigits);
+       /* t5 = (x2 - x1)^2 = A */
+       vli_mod_square_fast(t5, t5, curve_prime, ndigits);
+       /* t1 = x1*A = B = x1*(x2-x1)^2*/
+       vli_mod_mult_fast(x1, x1, t5, curve_prime, ndigits);
+       /* t3 = x2*A = C = x2*(x2-x1)^2*/
+       vli_mod_mult_fast(x2, x2, t5, curve_prime, ndigits);
+       /* t4 = y2 - y1 */
+       vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
+       /* t5 = (y2 - y1)^2 = D */
+       vli_mod_square_fast(t5, y2, curve_prime, ndigits);
+
+       /* t5 = D - B = (y2 - y1)^2 - x1*(x2-x1)^2 */
+       vli_mod_sub(t5, t5, x1, curve_prime, ndigits);
+       /* t5 = D - B - C = x3 = (y2 - y1)^2 - x1*(x2-x1)^2 - x2*(x2-x1)^2*/
+       vli_mod_sub(t5, t5, x2, curve_prime, ndigits);
+
+       /* t3 = C - B = x2*(x2-x1)^2 - x1*(x2-x1)^2 */
+       vli_mod_sub(x2, x2, x1, curve_prime, ndigits);
+       /* t2 = y1*(C - B) = y1*(x2*(x2-x1)^2 - x1*(x2-x1)^2)*/
+       vli_mod_mult_fast(y1, y1, x2, curve_prime, ndigits);
+       /* t3 = B - x3 = x1*(x2-x1)^2 - x3*/
+       vli_mod_sub(x2, x1, t5, curve_prime, ndigits);
+       /* t4 = (y2 - y1)*(B - x3)  = (y2 - y1)*(x1*(x2-x1)^2 - x3)*/
+       vli_mod_mult_fast(y2, y2, x2, curve_prime, ndigits);
+       /* t4 = y3 = ((y2 - y1)*(x1*(x2-x1)^2 - x3)) - y1*/
+       vli_mod_sub(y2, y2, y1, curve_prime, ndigits);
+
+       vli_mod_mult_fast(t5, t5, t7,  curve_prime, ndigits);
+       vli_set(x2, t5, ndigits);
+}
+
 static void ecc_point_mult(struct ecc_point *result,
                           const struct ecc_point *point, const u64 *scalar,
                           u64 *initial_z, u64 *curve_prime,
@@ -965,3 +1133,24 @@ int ecc_is_key_valid(unsigned int curve_id, unsigned int ndigits,
 
        return 0;
 }
+
+int ecc_is_pub_key_valid(unsigned int curve_id, unsigned int ndigits,
+                        const u8 *pub_key, unsigned int pub_key_len)
+{
+       const struct ecc_curve *curve = ecc_get_curve(curve_id);
+       int nbytes = ndigits << ECC_DIGITS_TO_BYTES_SHIFT;
+       struct ecc_point p;
+
+       if (!pub_key || pub_key_len != 2 * nbytes)
+               return -EINVAL;
+
+       p.x = (u64 *)pub_key;
+       p.y = (u64 *)(pub_key + ECC_MAX_DIGIT_BYTES);
+       p.ndigits = ndigits;
+
+       if (vli_cmp(curve->p, p.x, ndigits) != 1 ||
+           vli_cmp(curve->p, p.y, ndigits) != 1)
+               return -EINVAL;
+
+       return 0;
+}