Need a new function for a recovery(v) for HSM

[drhanlondon]

Hello,

I am building a custodial wallet with AWS KMS for Polkadot blockchain (with ecdsa scheme). This research is motivated from AWS blockchain research (https://aws.amazon.com/blogs/database/part1-use-aws-kms-to-securely-manage-ethereum-accounts/) where a private key is created and stored HSM (Hardware Security Module), a private key never leaves HSM and a transaction payload is signed offline in HSM.

We can see clearly that Polkadot-JS heavily depends on Noble-curves:
https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/sign.ts#L19
https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/verify.ts#L16
https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/recover.ts#L7

So, I have very carefully looked at two Git repositories (here and https://github.com/paulmillr/noble-curves).

To sign a transaction payload offline with AWS KMS, I create a transaction object and pass it to AWS KMS, and then KMS returns "r" and "s" values. Next I need compose a signature from these “r” and "s” values with “recovery (v)” . But here my problem is that I myself have to calculate "v" value.

Using Noble-curves, Polkadot-JS gets "v" as well as “r” and "s” , as we see https://github.com/polkadot-js/common/blob/1f8b573d811ebc00f078cc9ad0a96b0d5476b13d/packages/util-crypto/src/secp256k1/sign.ts#L32

So, I have investigated the process of calculating "recovery" from here ( https://github.com/paulmillr/noble-curves/blob/d5de5d2659d5268f5731579b0cf0f48e3358ad37/src/abstract/weierstrass.ts#L968)

This recovery (v) value should be either 0 or 1. I have defined the function getRecovery which takes three areguments (encodedHash of transaction payload, "r" value and "s" value) where "r" and "s" are already provided by AWS KMS. This function is created from a little modification of the original code

    import { Point } from './noble-secp256k1';
    
    const B256 = 2n ** 256n;                                // secp256k1 is short weierstrass curve
    const N = B256 - 0x14551231950b75fc4402da1732fc9bebfn;  // curve (group) order
    const P = B256 - 0x1000003d1n;                          // curve's field prime
    type Bytes = Uint8Array; type Hex = Bytes | string; type PrivKey = Hex | bigint;
    const padh = (n: number | bigint, pad: number) => n.toString(16).padStart(pad, '0');
    
    const b2h = (b: Bytes): string => Array.from(b).map(e => padh(e, 2)).join(''); // bytes to hex
    
    const b2n = (b: Bytes): bigint => BigInt('0x' + (b2h(b) || '0')); // bytes to number
    
    const bits2int = (bytes: Uint8Array): bigint => {       // RFC6979: ensure ECDSA msg is X bytes.
        const delta = bytes.length * 8 - 256; // RFC suggests optional truncating via bits2octets
        const num = b2n(bytes); // FIPS 186-4 4.6 suggests the leftmost min(nBitLen, outLen) bits, which
        return delta > 0 ? num >> BigInt(delta) : num; // matches bits2int. bits2int can produce res>N.
    };
    
    const mod = (a: bigint, b = P) => { let r = a % b; return r >= 0n ? r : b + r; }; // mod division
    const err = (m = ''): never => { throw new Error(m); }; // error helper, messes-up stack trace
    
    const inv = (num: bigint, md = P): bigint => {          // modular inversion
        if (num === 0n || md <= 0n) err('no inverse n=' + num + ' mod=' + md); // no neg exponent for now
        let a = mod(num, md), b = md, x = 0n, y = 1n, u = 1n, v = 0n;
        while (a !== 0n) {                                    // uses euclidean gcd algorithm
          const q = b / a, r = b % a;                         // not constant-time
          const m = x - u * q, n = y - v * q;
          b = a, a = r, x = u, y = v, u = m, v = n;
        }
        return b === 1n ? mod(x, md) : err('no inverse');     // b is gcd at this point
      };
    
    const { BASE: G, ZERO: I } = Point;                     // Generator, identity points
    
    const lowS = true;
    const moreThanHalfN = (n: bigint): boolean => n > (N >> 1n) // if a number is bigger than CURVE.n/2
    const big = (n: unknown): n is bigint => typeof n === 'bigint'; // is big integer
    const ge = (n: bigint) => big(n) && 0n < n && n < N;    // is group element
    
    export function getRecovery(kBytes: Uint8Array, r_value : bigint, s_value: bigint): number | undefined {
    
        const k = bits2int(kBytes);                         // RFC6979 method.
        if (!ge(k)) return;                                 // Check 0 < k < CURVE.n
       
        const q = G.mul(k).aff();                           // q = Gk
        let r = r_value;                              // r = q.x mod n
        if (r === 0n) return;                               // r=0 invalid
        let s = s_value;   // s = k^-1(m + rd) mod n
        if (s === 0n) return;                               // s=0 invalid
        let normS = s;                                      // normalized S
        let rec = (q.x === r ? 0 : 2) | Number(q.y & 1n);   // recovery bit
        if (lowS && moreThanHalfN(s)) {                     // if lowS was passed, ensure s is always
          normS = mod(-s, N);                               // in the bottom half of CURVE.n
          rec ^= 1;
        }
    
        rec = rec - 2; // before this line, rec is either 2 or 3; but is should be 0 or 1
        return rec
    }

This function returns either 0 or 1. We have a half-and-half chance to get a correct value, either 0 or 1. This function returns a wrong value sometimes, so I have failed to recover a correct a public Key.

I would be very grateful if you could advise me or correct the code above.

Thanks.