Topic: ECDSA math questions (Read 937 times)

export function retrieve(publicKeyCompressed: bigint): string {
const yOdd = publicKeyCompressed.toString(16).substring(0, 1) === "3";
const x = BigInt("0x" + publicKeyCompressed.toString(16).substring(1));
const p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fn;
const x3 = modPow(x, 3n, p);
const y2 = modPow(x3 + 7n, 1, p);
let y = modPow(y2, (p + 1n) / 4n, p);
if (yOdd) {
y = p - y;
}

return "0x04" + bigIntToHex(x) + bigIntToHex(y);
}

function bigIntToHex(value: bigint): string {
var hex = value.toString(16);
if (hex.length % 2) {
hex = '0' + hex;
}
return hex;
}

/** taken from npm package bigint-mod-arith */

/**
 * Modular exponentiation b**e mod n. Currently using the right-to-left binary method
 *
 * @param b base
 * @param e exponent
 * @param n modulo
 *
 * @throws {RangeError}
 * Exception thrown when n is not > 0
 *
 * @returns b**e mod n
 */
export function modPow(b: number | bigint, e: number | bigint, n: number | bigint): bigint {
if (typeof b === 'number') b = BigInt(b)
if (typeof e === 'number') e = BigInt(e)
if (typeof n === 'number') n = BigInt(n)

if (n <= 0n) {
throw new RangeError('n must be > 0')
} else if (n === 1n) {
return 0n
}

b = toZn(b, n)

if (e < 0n) {
return modInv(modPow(b, abs(e), n), n)
}

let r = 1n
while (e > 0) {
if ((e % 2n) === 1n) {
r = r * b % n
}
e = e / 2n
b = b ** 2n % n
}
return r
}

/**
 * Finds the smallest positive element that is congruent to a in modulo n
 *
 * @remarks
 * a and b must be the same type, either number or bigint
 *
 * @param a - An integer
 * @param n - The modulo
 *
 * @throws {RangeError}
 * Exception thrown when n is not > 0
 *
 * @returns A bigint with the smallest positive representation of a modulo n
 */
export function toZn(a: number | bigint, n: number | bigint): bigint {
if (typeof a === 'number') a = BigInt(a)
if (typeof n === 'number') n = BigInt(n)

if (n <= 0n) {
throw new RangeError('n must be > 0')
}

const aZn = a % n
return (aZn < 0n) ? aZn + n : aZn
}

/**
 * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0
 *
 * @param a
 *
 * @returns The absolute value of a
 */
export function abs(a: number | bigint): number | bigint {
return (a >= 0) ? a : -a
}
/**
 * Modular inverse.
 *
 * @param a The number to find an inverse for
 * @param n The modulo
 *
 * @throws {RangeError}
 * Exception thrown when a does not have inverse modulo n
 *
 * @returns The inverse modulo n
 */
export function modInv(a: number | bigint, n: number | bigint): bigint {
const egcd = eGcd(toZn(a, n), n)
if (egcd.g !== 1n) {
throw new RangeError(`${a.toString()} does not have inverse modulo ${n.toString()}`) // modular inverse does not exist
} else {
return toZn(egcd.x, n)
}
}
export interface Egcd {
g: bigint
x: bigint
y: bigint
}
/**
 * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm.
 * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
 *
 * @param a
 * @param b
 *
 * @throws {RangeError}
 * This exception is thrown if a or b are less than 0
 *
 * @returns A triple (g, x, y), such that ax + by = g = gcd(a, b).
 */
export function eGcd(a: number | bigint, b: number | bigint): Egcd {
if (typeof a === 'number') a = BigInt(a)
if (typeof b === 'number') b = BigInt(b)

if (a <= 0n || b <= 0n) throw new RangeError('a and b MUST be > 0') // a and b MUST be positive

let x = 0n
let y = 1n
let u = 1n
let v = 0n

while (a !== 0n) {
const q = b / a
const r: bigint = b % a
const m = x - (u * q)
const n = y - (v * q)
b = a
a = r
x = u
y = v
u = m
v = n
}
return {
g: b,
x: x,
y: y
}
}

console.log(retrieve(0x02a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aean));

console.log(retrieve(0x0378D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71n));

>>> n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 (this is the group order)
>>>
>>> d=0x0caecf01d74102a28aed6a64dcf1cf7b0e41c4dd6c62f70f46febdc32514f0bd (the private key)
>>> e=0x5fda68729a6312e17e641e9a49fac2a4a6a680126610af573caab270d232f850 (the double hash of the tx/message)
>>>
>>> r=0x2cb265bf10707bf49346c3515dd3d16fc454618c58ec0a0ff448a676c54ff713 (the first part of the signature)
>>> s=0x6c6624d762a1fcef4618284ead8f08678ac05b13c84235f1654e6ad168233e82 (the second part of the signature)

>>> s_inv=pow(s,n-2,n)  --> we are using the Fermat's little theorem to compute 1/s
>>> hex(s_inv)
'0x947f7b9fc41f37348c3a53a146757b9759e79da5fe039a35a9024bec1fb0ea0cL'
>>>
>>> hex((s_inv * s) % n)  --> we check that s_inv * s = 1
'0x1L'
>>>
>>> k=(s_inv * (e + r*d)) % n
>>> hex(k)
'0x4526b5ab1973ab68afd06517996d22823441dd9ef52663a57de11d6642e961e7L'

04
X = 2CB265BF10707BF49346C3515DD3D16FC454618C58EC0A0FF448A676C54FF713
Y = B317A494AB75813F8737AC779BDF68AC5235C683A0FF92AEB81655DE137FB862

y=pow(y2,(p+1)/4,p)  --> this line computes sqrt(y^2) = y

> p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
>
> x=0x78D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71
>
> x3=pow(x,3,p)    --> x^3 = x^3 mod p
>
> y2=(x3+7) % p   --> y^2 = x^3 + 7 mod p
>
> y=pow(y2,(p+1)/4,p)  --> this line computes sqrt(y^2) = y
>
> hex(y)
'0x5eae7f9cdbc532b201694991c0d137fec371f8d32f64c7cb5e607e08a633c7da'
>
 because this y is even, we compute -y = p-y (if y is even, p-y is always odd and viceversa)
>
> hex(p-y)
>'0xa1518063243acd4dfe96b66e3f2ec8013c8e072cd09b3834a19f81f659cc3455'

0478D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71A1518063243ACD4DFE96B66E3F2EC8013C8E072CD09B3834A19F81F659CC3455