RDSA implementation on sage

Question

First of all I must say my knowledge with using Sage math is really very limited, but I really want to improve an to be able to solve these problems I am having. I have been asked to implement the following:

1 - Read in FIPS 186-4 (http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf) the definition of ECDSA and implement using Sage math with:

  (a) prime eliptic curves (P-xxx)

  (b) binary eliptic curves (B-xxx)

I tried solving (a) by looking around the internet a lot and ended up with the following code:

Exercise 1, a)

class ECDSA_a:

def __init__(self):
    #Parameters for Curve p-256 as stated on FIPS 186-4 D1.2.3
    p256 = 115792089210356248762697446949407573530086143415290314195533631308867097853951
    a256 = p256 - 3
    b256 = ZZ("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16)
    ## base point values
    gx = ZZ("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16)
    gy = ZZ("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16)

    self.F = GF(p256)
    self.C = EllipticCurve ([self.F(a256), self.F(b256)])
    self.G = self.C(self.F(gx), self.F(gy))

    self.N = FiniteField (self.C.order()) # how many points are in our curve

    self.d = int(self.F.random_element()) # privateKey
    self.pd = self.G*self.d               # our pubkey
    self.e = int(self.N.random_element()) # our message

#sign
def sign(self):
    self.k = self.N.random_element()
    self.r = (int(self.k)*self.G).xy()[0]
    self.s = (1/self.k)*(self.e+self.N(self.r)*self.d)

#verify
def verify(self):
    self.w = 1/self.N(self.s)
    return self.r == (int(self.w*self.e)*self.G + int(self.N(self.r)*self.w)*self.pd).xy()[0]

#mutate
def mutate(self):
    s2 = self.N(self.s)*self.N(-1)
    if not (s2 != self.s) : return False
    self.w = 1/s2
    return self.r == (int(self.w*self.e)*self.G + int(self.N(self.r)*self.w)*self.pd).xy()[0]  # sign flip mutant

#TESTING
#Exercise 1 a)
print("Exercise 1 a)\n")

print("Elliptic Curve defined by y^2 = x^3 -3x +b256*(mod p256)\n")
E = ECDSA_a()
E.sign()
print("Verify signature  = {}".format(E.verify()))
print("Mutating          = {}".format(E.mutate()))

But now I wonder, Is this code really what I have been asked for?

I mean, I got the values for p and all that from the link mentioned above.

But is this eliptic curve I made a prime one? (whatever that really means).

In order words is this code I glued together the answer? And what is the mutate function actually doing? I understand the rest but don't see why it needs to be here...

Also, what could I do about question (b)? I have looked all around the internet but I can't find a single understandable mention about binary eliptic curves in sage...

Could I just reuse the above code and simply change the curve creation to get the answer?

Answer 1

(a.) Is this code really what I have been asked for?

No.

The sign() method has the wrong signature: it does not accept an argument to sign.

It would be very helpful to write unit tests for your code based on published test vectors, perhaps these, cf this Secp256k1 ECDSA test examples question.

You might consider doing the verification methods described in D.5 & D.6 (pp 109 ff).

(b.) binary elliptic curves

The FIPS publication you cited offers some advice on implementing such curves, and yes you could leverage your current code. But there's probably less practical advantage to implementing them, compared to the P-xxx curves, as strength of B-xxx curves is on rockier footing. They have an advantage for hardware implementations such as FPGA, but that's not relevant for your situation.