# ECDSA

Signature algorithm
• Use the secret scalar
$e$
to compute the public point
$P$
, by doing a scalar multiplication with
$G$
:
$eG = P$
.
• Pick a random (secret) scalar
$k$
, and perform a scalar multiplication with
$G$
to get a random point
$R$
.
$kG = R$
• Use the above variables in the general equation of ECDSA is:
$uG + vP = R$
, where,
$u = z/s$
,
$v=r/s$
• Simplify the resulting equation to get the
$s$
component of the signature:
$s = (z + re) / k$
from random import randint
@dataclass
class PrivateKey:
secret: int
def sign(self, z: int) -> Signature:
e = self.secret
k = randint(0, N)
R = k * G
r = R.x.value
k_inv = pow(k, -1, N) # Python 3.8+
s = ((z + r*e) * k_inv) % N
return Signature(r, s)
Apart from the fact that e is a secret number, the security of ECDSA also relies on the condition that k is also very random and secret.
We'll learn about the consequences of not having a random kin the next section.
Verification algorithm
• Given: (r, s) is the signature, z is the 256 bit message being signed, and P is the public key of the signer.
• Calculate:
$u = z/s$
,
$v=r/s$
.
• Calculate
$uG + vP = R$
.
• Signature is valid is
$Rx$
is equal to
$r$
.
@dataclass
class Signature:
r: int
s: int
def verify(self, z: int, pub_key: Point) -> bool:
s_inv = pow(self.s, -1, N) # Python 3.8+
u = (z * s_inv) % N
v = (self.r * s_inv) % N
return (u*G + v*pub_key).x.value == self.r

#### Testing our ECDSA implementation

pub = Point(
x=0x887387E452B8EACC4ACFDE10D9AAF7F6D9A0F975AABB10D006E4DA568744D06C,
y=0x61DE6D95231CD89026E286DF3B6AE4A894A3378E393E93A0F45B666329A0AE34,
curve=secp256k1
)
# Test case 1: verify authenticity
r = 0xAC8D1C87E51D0D441BE8B3DD5B05C8795B48875DFFE00B7FFCFAC23010D3A395
s = 0x68342CEFF8935EDEDD102DD876FFD6BA72D6A427A3EDB13D26EB0781CB423C4
assert Signature(r, s).verify(z, pub)
# Test case 2: verify authenticity for different signature w/ same P
z = 0x7C076FF316692A3D7EB3C3BB0F8B1488CF72E1AFCD929E29307032997A838A3D