// SPDX-License-Identifier: BSD-2-Clause
/* LibTomCrypt, modular cryptographic library -- Tom St Denis
 *
 * LibTomCrypt is a library that provides various cryptographic
 * algorithms in a highly modular and flexible manner.
 *
 * The library is free for all purposes without any express
 * guarantee it works.
 */

#include "tomcrypt_private.h"

#ifdef LTC_MECC

#ifdef LTC_ECC_SHAMIR

/**
  @file ecc_recover_key.c
  ECC Crypto, Russ Williams
*/

/**
   Recover ECC public key from signature and hash
   @param sig         The signature to verify
   @param siglen      The length of the signature (octets)
   @param hash        The hash (message digest) that was signed
   @param hashlen     The length of the hash (octets)
   @param recid       The recovery ID ("v"), can be -1 if signature contains it
   @param sigformat   The format of the signature (ecc_signature_type)
   @param key         The recovered public ECC key
   @return CRYPT_OK if successful (even if the signature is not valid)
*/
int ecc_recover_key(const unsigned char *sig,  unsigned long siglen,
                    const unsigned char *hash, unsigned long hashlen,
                    int recid, ecc_signature_type sigformat, ecc_key *key)
{
   ecc_point     *mG = NULL, *mQ = NULL, *mR = NULL;
   void          *p, *m, *a, *b;
   void          *r, *s, *v, *w, *t1, *t2, *u1, *u2, *v1, *v2, *e, *x, *y, *a_plus3;
   void          *mu = NULL, *ma = NULL;
   void          *mp = NULL;
   int           err;
   unsigned long pbits, pbytes, i, shift_right;
   unsigned char ch, buf[MAXBLOCKSIZE];

   LTC_ARGCHK(sig  != NULL);
   LTC_ARGCHK(hash != NULL);
   LTC_ARGCHK(key  != NULL);

   /* BEWARE: requires sqrtmod_prime */
   if (ltc_mp.sqrtmod_prime == NULL) {
      return CRYPT_ERROR;
   }

   /* allocate ints */
   if ((err = mp_init_multi(&r, &s, &v, &w, &t1, &t2, &u1, &u2, &v1, &v2, &e, &x, &y, &a_plus3, NULL)) != CRYPT_OK) {
      return err;
   }

   p = key->dp.order;
   m = key->dp.prime;
   a = key->dp.A;
   b = key->dp.B;
   if ((err = mp_add_d(a, 3, a_plus3)) != CRYPT_OK) {
      goto error;
   }

   /* allocate points */
   mG = ltc_ecc_new_point();
   mQ = ltc_ecc_new_point();
   mR = ltc_ecc_new_point();
   if (mR == NULL || mQ  == NULL || mG == NULL) {
      err = CRYPT_MEM;
      goto error;
   }

   if (sigformat == LTC_ECCSIG_ANSIX962) {
      /* ANSI X9.62 format - ASN.1 encoded SEQUENCE{ INTEGER(r), INTEGER(s) }  */
      if ((err = der_decode_sequence_multi_ex(sig, siglen, LTC_DER_SEQ_SEQUENCE | LTC_DER_SEQ_STRICT,
                                     LTC_ASN1_INTEGER, 1UL, r,
                                     LTC_ASN1_INTEGER, 1UL, s,
                                     LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK)                             { goto error; }
   }
   else if (sigformat == LTC_ECCSIG_RFC7518) {
      /* RFC7518 format - raw (r,s) */
      i = mp_unsigned_bin_size(key->dp.order);
      if (siglen != (2*i)) {
         err = CRYPT_INVALID_PACKET;
         goto error;
      }
      if ((err = mp_read_unsigned_bin(r, (unsigned char *)sig,   i)) != CRYPT_OK)                       { goto error; }
      if ((err = mp_read_unsigned_bin(s, (unsigned char *)sig+i, i)) != CRYPT_OK)                       { goto error; }
   }
   else if (sigformat == LTC_ECCSIG_ETH27) {
      /* Ethereum (v,r,s) format */
      if (pk_oid_cmp_with_ulong("1.3.132.0.10", key->dp.oid, key->dp.oidlen) != CRYPT_OK) {
         /* Only valid for secp256k1 - OID 1.3.132.0.10 */
         err = CRYPT_ERROR; goto error;
      }
      if (siglen != 65) { /* Only secp256k1 curves use this format, so must be 65 bytes long */
         err = CRYPT_INVALID_PACKET;
         goto error;
      }
      i = (unsigned long)sig[64];
      if ((i>=27) && (i<31)) i -= 27; /* Ethereum adds 27 to recovery ID */
      if (recid >= 0 && ((unsigned long)recid != i)) {
         /* Recovery ID specified, but doesn't match signature */
         err = CRYPT_INVALID_PACKET;
         goto error;
      }
      recid = i;
      if ((err = mp_read_unsigned_bin(r, (unsigned char *)sig,  32)) != CRYPT_OK)                       { goto error; }
      if ((err = mp_read_unsigned_bin(s, (unsigned char *)sig+32, 32)) != CRYPT_OK)                     { goto error; }
   }
#ifdef LTC_SSH
   else if (sigformat == LTC_ECCSIG_RFC5656) {
      char name[64], name2[64];
      unsigned long namelen = sizeof(name2);

      /* Decode as SSH data sequence, per RFC4251 */
      if ((err = ssh_decode_sequence_multi(sig, siglen,
                                           LTC_SSHDATA_STRING, name, 64,
                                           LTC_SSHDATA_MPINT,  r,
                                           LTC_SSHDATA_MPINT,  s,
                                           LTC_SSHDATA_EOL,    NULL)) != CRYPT_OK)                      { goto error; }


      /* Check curve matches identifier string */
      if ((err = ecc_ssh_ecdsa_encode_name(name2, &namelen, key)) != CRYPT_OK)                                { goto error; }
      if (XSTRCMP(name,name2) != 0) {
         err = CRYPT_INVALID_ARG;
         goto error;
      }
   }
#endif
   else {
      /* Unknown signature format */
      err = CRYPT_ERROR;
      goto error;
   }

   if (recid < 0 || (unsigned long)recid >= 2*(key->dp.cofactor+1)) {
      /* Recovery ID is out of range, reject it */
      err = CRYPT_INVALID_ARG;
      goto error;
   }

   /* check for zero */
   if (mp_cmp_d(r, 0) != LTC_MP_GT || mp_cmp_d(s, 0) != LTC_MP_GT ||
       mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) {
      err = CRYPT_INVALID_PACKET;
      goto error;
   }

   /* read hash - truncate if needed */
   pbits = mp_count_bits(p);
   pbytes = (pbits+7) >> 3;
   if (pbits > hashlen*8) {
      if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, hashlen)) != CRYPT_OK)                  { goto error; }
   }
   else if (pbits % 8 == 0) {
      if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, pbytes)) != CRYPT_OK)                   { goto error; }
   }
   else {
      shift_right = 8 - pbits % 8;
      for (i=0, ch=0; i<pbytes; i++) {
        buf[i] = ch;
        ch = (hash[i] << (8-shift_right));
        buf[i] = buf[i] ^ (hash[i] >> shift_right);
      }
      if ((err = mp_read_unsigned_bin(e, (unsigned char *)buf, pbytes)) != CRYPT_OK)                    { goto error; }
   }

   /* decompress point from r=(x mod p) - BEWARE: requires sqrtmod_prime */
   /* x = r + p*(recid/2) */
   if ((err = mp_set(x, recid/2)) != CRYPT_OK)                                                          { goto error; }
   if ((err = mp_mulmod(p, x, m, x)) != CRYPT_OK)                                                       { goto error; }
   if ((err = mp_add(x, r, x)) != CRYPT_OK)                                                             { goto error; }
   /* compute x^3 */
   if ((err = mp_sqr(x, t1)) != CRYPT_OK)                                                               { goto error; }
   if ((err = mp_mulmod(t1, x, m, t1)) != CRYPT_OK)                                                     { goto error; }
   /* compute x^3 + a*x */
   if ((err = mp_mulmod(a, x, m, t2)) != CRYPT_OK)                                                      { goto error; }
   if ((err = mp_add(t1, t2, t1)) != CRYPT_OK)                                                          { goto error; }
   /* compute x^3 + a*x + b */
   if ((err = mp_add(t1, b, t1)) != CRYPT_OK)                                                           { goto error; }
   /* compute sqrt(x^3 + a*x + b) */
   if ((err = mp_sqrtmod_prime(t1, m, t2)) != CRYPT_OK)                                                 { goto error; }

   /* fill in mR */
   if ((err = mp_copy(x, mR->x)) != CRYPT_OK)                                                           { goto error; }
   if ((mp_isodd(t2) && (recid%2)) || (!mp_isodd(t2) && !(recid%2))) {
      if ((err = mp_mod(t2, m, mR->y)) != CRYPT_OK)                                                     { goto error; }
   }
   else {
      if ((err = mp_submod(m, t2, m, mR->y)) != CRYPT_OK)                                               { goto error; }
   }
   if ((err = mp_set(mR->z, 1)) != CRYPT_OK)                                                            { goto error; }

   /*  w  = r^-1 mod n */
   if ((err = mp_invmod(r, p, w)) != CRYPT_OK)                                                          { goto error; }
   /* v1 = sw */
   if ((err = mp_mulmod(s, w, p, v1)) != CRYPT_OK)                                                      { goto error; }
   /* v2 = -ew */
   if ((err = mp_mulmod(e, w, p, v2)) != CRYPT_OK)                                                      { goto error; }
   if ((err = mp_submod(p, v2, p, v2)) != CRYPT_OK)                                                     { goto error; }

   /*  w  = s^-1 mod n */
   if ((err = mp_invmod(s, p, w)) != CRYPT_OK)                                                          { goto error; }
   /* u1 = ew */
   if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK)                                                      { goto error; }
   /* u2 = rw */
   if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK)                                                      { goto error; }

   /* find mG */
   if ((err = ltc_ecc_copy_point(&key->dp.base, mG)) != CRYPT_OK)                                       { goto error; }

   /* find the montgomery mp */
   if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK)                                                 { goto error; }

   /* for curves with a == -3 keep ma == NULL */
   if (mp_cmp(a_plus3, m) != LTC_MP_EQ) {
      if ((err = mp_init_multi(&mu, &ma, NULL)) != CRYPT_OK)                                            { goto error; }
      if ((err = mp_montgomery_normalization(mu, m)) != CRYPT_OK)                                       { goto error; }
      if ((err = mp_mulmod(a, mu, m, ma)) != CRYPT_OK)                                                  { goto error; }
   }

   /* recover mQ from mR */
   /* compute v1*mR + v2*mG = mQ using Shamir's trick */
   if ((err = ltc_mp.ecc_mul2add(mR, v1, mG, v2, mQ, ma, m)) != CRYPT_OK)                               { goto error; }

   /* compute u1*mG + u2*mQ = mG using Shamir's trick */
   if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, ma, m)) != CRYPT_OK)                               { goto error; }

   /* v = X_x1 mod n */
   if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK)                                                         { goto error; }

   /* does v == r */
   if (mp_cmp(v, r) == LTC_MP_EQ) {
      /* found public key which verifies signature */
      if ((err = ltc_ecc_copy_point(mQ, &key->pubkey)) != CRYPT_OK)                                     { goto error; }
      /* point on the curve + other checks */
      if ((err = ltc_ecc_verify_key(key)) != CRYPT_OK)                                                  { goto error; }

      key->type = PK_PUBLIC;

      err = CRYPT_OK;
   }
   else {
      /* not found - recid is wrong or we're unable to calculate public key for some other reason */
      err = CRYPT_INVALID_ARG;
   }

error:
   if (ma != NULL) mp_clear(ma);
   if (mu != NULL) mp_clear(mu);
   if (mp != NULL) mp_montgomery_free(mp);
   if (mR != NULL) ltc_ecc_del_point(mR);
   if (mQ != NULL) ltc_ecc_del_point(mQ);
   if (mG != NULL) ltc_ecc_del_point(mG);
   mp_clear_multi(a_plus3, y, x, e, v2, v1, u2, u1, t2, t1, w, v, s, r, NULL);
   return err;
}

#endif
#endif

/* ref:         $Format:%D$ */
/* git commit:  $Format:%H$ */
/* commit time: $Format:%ai$ */