- Any machine with Python 3. I used a Mac.

Each elliptic curve we'll use is defined by the two
parameters * a* and

All calculations are made modulusy^{ 2}=x^{ 3}+ax+modbp

On your Mac or Linux machine, in a Terminal window, execute these commands:

wget https://gist.githubusercontent.com/sambowne/d8a3984f3ee987facae1133afee55648/raw/64306798a03a5340dc30889622c629416895debf/ecc.py python3 -m pip install numpy

= 1**a**= 2**b**= 5**p**

Consider the casey^{ 2}=x^{ 3}+x+ 2

One solution is (y^{ 2}= 0

We can say the **Point** (4, 0) is *on the curve*.

We can determine whether a point is on the curve using the onCurve() function.

On your Mac or Linux machine, in a Terminal window, execute the commands below. Press Enter twice after the last command.

The point (4, 0) is on the curve, as shown below.

python3 from ecc import * a = 1 b = 2 p = 5 Px = 4 Py = 0 if onCurve(Px, Py, a, b, p): print("(", Px, Py, ") is on the curve") else: print("(", Px, Py, ") is not on the curve")

Let's find all the points on the curve.

On your Mac or Linux machine, in a Terminal window, execute the commands below. Press Enter twice after the last command.

There are three points on the curve, as shown below. There's also a point at infinity, bringing the total to 4. This number is called the

from ecc import * a = 1 b = 2 p = 5 for Px in range(p): for Py in range(p): if onCurve(Px, Py, a, b, p): print(Px, Py, "is on the curve")

Let's change * b*
to 1.

On your Mac or Linux machine, in a Terminal window, execute the commands below. Press Enter twice after the last command.

Now there are eight points on the curve (plus the point at infinity), as shown below.

The number of points on an elliptic
curve varies, but it's never very
far away from * p*,
as explained

## C 524.1: Secp256k1 (5 pts)

This is the curve used by Bitcoin, (with a higher):pHow many points are on this curve, not including the point at infinity? That number is the flag.

= 0a= 7b= 11p

## C 524.2: Secp256k1 with Larger p (10 pts)

Use this curve:What is the largest

= 0a= 7b= 6199pyof any point on the curve, excluding the point at infinity? That number is the flag.

eccScalarMult(k, Px, Py, a, b, p)As we saw before, here are the points on this curve:

= 1**a**= 1**b**= 5**p**

Execute these commands to see various multiples of (0, 1):

All eight points are generated, as shown below, as well as (None, None), the "point at infinity". (0, 1) is a

from ecc import * a = 1 b = 1 p = 5 Px = 0 Py = 1 for k in range(15): print(k, "*", "(", Px, ",", Py, ") =", eccScalarMult(k, Px, Py, a, b, p))

Execute these commands to list multiples of all eight points on the curve:

As shown below, (2, 1) is

from ecc import * a = 1 b = 1 p = 5 for Px, Py in [(0,1), (0,4), (2,1), (2,4), (3,1), (3,4), (4,2), (4,3)]: for k in range(10): print(k, "*", "(", Px, ",", Py, ") =", eccScalarMult(k, Px, Py, a, b, p)) print()

## C 524.3: Generators (5 pts)

Use the curve defined below:How many points on this curve are

= 2a= 3b= 7pgenerators? That number is the flag.

## C 524.4: More Generators (10 pts)

Use the curve defined below:How many points on this curve are

= 2a= 3b= 101pgenerators? That number is the flag.

Execute the code below to confirm that there are
17 points on this curve (not including
the point at infinity), and that (15, 4) is a
*generator*.

from ecc import * a = 0 b = 7 p = 17 P = [] for Px in range(p): for Py in range(p): if onCurve(Px, Py, a, b, p): P.append((Px, Py)) print("Number of points:", len(P), P) Px = 15 Py = 4 for k in range(20): Q = eccScalarMult(k, Px, Py, a, b, p) print(k, "*", "(", Px, ",", Py, ") =", Q)

As shown below,
they agree on a curve (Secp256k1),
* p*, and a generator

Cueball picks a random number
** α**, between
1 and

Cueball calculates his

Meghan chooses a *private key* of ** β**,
calculates her

Each of them multiplies their *private key* and the other
person's *public key* to find a *Shared Secret*,
as shown below.

Unlike RSA, ECC does not provide any way to encrypt or decrypt with the public or private keys.

Instead,
the *Shared Secret* can be used to determine an
encryption key
using PBKDF2 or some other algorithm, and the data
can be encrypted with AES.

GivenThis problem is very difficult if a good elliptic curve is chosen, with a large enough value of, findAsuch thatα=AαG

## C 524.5: ECDH (5 pts)

Use the curve defined below:Cueball 's

= 0a= 7b= 761p= (3, 107)Gprivate keyis 94. What is hispublic key? That's the flag.

## C 524.6: DLP (10 pts)

Use the same curve as in the previous challenge.Megan's

public keyis (744, 52).Find her

private key. That's the flag.

Cueball has:

- A
*private key***α** - A
*public key*=**A****αG** - A message
to sign**m**

- Calculate the hash
of the message**h**(mod**m**for this small-number example)**n** - Pick a random number
**k** - Calculate
= the x-coordinate of**r**mod**kG****n** - Calculate signature
=**s****(**mod*h + rα*)*k*^{-1}**n** - Publish the signature as
**(**,*r**s*)

The result is (10, 15) as shown in the image above.

from ecc import * from hashlib import * a = 0 b = 7 p = 17 n = 18 Gx = 15 Gy = 4 Ax = 12 Ay = 16 alpha = 4 m = b"HELLO" h = int( sha256(m).hexdigest(), 16 ) % n k = 11 P = eccScalarMult(k, Gx, Gy, a, b, p) r = int( P[0] ) kinv = inverse(k, n) s = ( (h + r * alpha) * kinv ) % n print("Signature: (", r, ",", s, ")")

- Calculate
=**w**mod**s**^{-1}**n** - Calculate
=**u****wh** - Calculate
=**v****wr** - Calculate
=**Q**(*uG*+*vA*is the signer's public key)**A** - The x-coordinate of
should equal**Q****r**

Execute these commands to verify Cueball's signature:

The result is (10, 15) as shown in the image above.

from ecc import * from hashlib import * a = 0 b = 7 p = 17 n = 18 Gx = 15 Gy = 4 Ax = 12 Ay = 16 r = 10 s = 5 m = b"HELLO" h = int( sha256(m).hexdigest(), 16 ) % n w = inverse(s, n) u = w * h v = w * r P1 = eccScalarMult(u, Gx, Gy, a, b, p) P2 = eccScalarMult(v, Ax, Ay, a, b, p) Q = eccFiniteAddition(P1[0], P1[1], P2[0], P2[1], a, b, p) if (Q[0] == r): print("Signature matches!") else: print("Signature does not match!")

## C 524.7: Meghan's ECDSA Signature (5 pts)

Megan wants to sign the same message, "HELLO". As shown in the image above, her private and public keys are:Use a= 7β= (10, 2)Bof 7, and the same curve as in the figure above.kCalculate Megan's signature. That's the flag.

## C 524.8: Validate Meghan's ECDSA Signature (5 pts)

Validate Megan's signature. The flag is the valueQ

Here's how Cueball creates a signature, as shown in the image below:

- Pick a random nonce
**r** - Calculate a public key
=**R****rG** - Calculate a
*challenge*combining all the public information:**e**= H(**e**||**R**||**A**), where H is a hash function and || indicates concatenation.**m** - Construct the signature using your private information:
=*s*+*r**α**e* - Publish (
,*s*)*R*

- Calculate
=**c****sG** - Calculate
= H(**e**||**R**||**A**)**m** - Calculate
=**d**+**R****A****e** - If
=**c**, the signature is valid.**d**

The signature is (15, (10, 15)), as shown below.

from ecc import * from hashlib import * a = 0 b = 7 p = 17 n = 18 Gx = 15 Gy = 4 Ax = 12 Ay = 16 Abytes = bytes(hex(Ax) + hex(Ay), 'utf-8') alpha = 4 m = b"HELLO" r = 11 R = eccScalarMult(r, Gx, Gy, a, b, p) Rbytes = bytes(hex(R[0]) + hex(R[1]), 'utf-8') e = int( sha256(Rbytes + Abytes + m).hexdigest(), 16 ) % n s = r + alpha * e print("Signature: (", s, ",", R, ")")

Execute these commands to verify Cueball's signature:

The signature is valid, as shown below.

from ecc import * from hashlib import * a = 0 b = 7 p = 17 n = 18 Gx = 15 Gy = 4 Ax = 12 Ay = 16 Abytes = bytes(hex(Ax) + hex(Ay), 'utf-8') m = b"HELLO" R = (10, 15) Rbytes = bytes(hex(R[0]) + hex(R[1]), 'utf-8') s = 15 c = eccScalarMult(s, Gx, Gy, a, b, p) e = int( sha256(Rbytes + Abytes + m).hexdigest(), 16 ) % n Ae = eccScalarMult(e, Ax, Ay, a, b, p) d = eccFiniteAddition(R[0], R[1], Ae[0], Ae[1], a, b, p) if c==d: print("Signature is valid!") else: print("Signature is not valid!")

## C 524.9: Meghan's Schnorr Signature (5 pts)

Megan wants to sign the same message, "HELLO". Her private and public keys are:Use a= 7β= (10, 2)Bof 5, and the same curve as in the figure above.rCalculate Megan's Schnorr signature. That's the flag.

## C 524.10: Validate Meghan's Schnorr Signature (5 pts)

Validate the signature you found above. The flag is thevalue.d

Cueball and Meghan both want to sign a message.

Here's how they do it:

- Cueball has a known public key
and Meghan has a known public key**A****B** - These are added together to produce the aggregate public key
=**P**_{AB}+**A****B** - Cueball picks a random nonce
and calculates another public key from it**r**_{A}=**R**_{A}**r**_{A}G - Meghan picks a random nonce
and calculates another public key from it**r**_{B}=**R**_{B}**r**_{B}G - These public keys are added to produce the aggregate public key:
=**R**_{AB}+**R**_{A}**R**_{B} - They both calculate the same
*challenge*combining all the public information:**e**= H(**e**||**R**_{AB}||**P**_{AB}), where H is a hash function and || indicates concatenation.**m** - Cueball constructs a signature using his private information:
=*s*_{A}+*r*_{A}*α*and publishes it*e* - Methan constructs a signature using her private information:
=*s*_{B}+*r*_{B}*β*and publishes it*e* - The aggregate signature
=*s*_{AB}+*s*_{A}*s*_{B} - The aggregate signature is published as (
,*s*_{AB})*R*_{AB}

- Calculate
=**c****s**_{AB}G - Calculate
= H(**e**||**R**_{AB}||**P**_{AB}))**m** - Calculate
=**d**+**R**_{AB}**P**_{AB}**e** - If
=**c**, the signature is valid.**d**

The signature is (156, (5, 9)), as shown below.

from ecc import * from hashlib import * a = 0 b = 7 p = 17 n = 18 G = (15, 4) A = (12, 16) B = (10, 2) PAB = eccFiniteAddition(A[0], A[1], B[0], B[1], a, b, p) PABbytes = bytes(hex(PAB[0]) + hex(PAB[1]), 'utf-8') rA = 11 RA = eccScalarMult(rA, G[0], G[1], a, b, p) rB = 13 RB = eccScalarMult(rB, G[0], G[1], a, b, p) RAB = eccFiniteAddition(RA[0], RA[1], RB[0], RB[1], a, b, p) RABbytes = bytes(hex(RAB[0]) + hex(RAB[1]), 'utf-8') m = b"HELLO" e = int( sha256(RABbytes + PABbytes + m).hexdigest(), 16 ) % n alpha = 4 sA = rA + alpha * e beta = 7 sB = rB + beta * e sAB = sA + sB print("Signature: (", sAB, ",", RAB, ")")

Execute these commands to verify the aggregate signature:

The signature is valid, as shown below.

from ecc import * from hashlib import * a = 0 b = 7 p = 17 n = 18 G = (15, 4) A = (12, 16) B = (10, 2) PAB = eccFiniteAddition(A[0], A[1], B[0], B[1], a, b, p) PABbytes = bytes(hex(PAB[0]) + hex(PAB[1]), 'utf-8') sAB = 156 RAB = (5, 9) c = eccScalarMult(sAB, G[0], G[1], a, b, p) RABbytes = bytes(hex(RAB[0]) + hex(RAB[1]), 'utf-8') m = b"HELLO" e = int( sha256(RABbytes + PABbytes + m).hexdigest(), 16 ) % n PABe = eccScalarMult(e, PAB[0], PAB[1], a, b, p) d = eccFiniteAddition(RAB[0], RAB[1], PABe[0], PABe[1], a, b, p) if c==d: print("Signature is valid!") else: print("Signature is not valid!")

## C 524.11: Aggregate Schnorr Signature (5 pts)

Add Ponytail, shown below, to the aggregate signature above, so there are three signers.Use an

of 3.rThe composite Schnorr signature is the flag.

## C 524.12: Validate the Aggregate Schnorr Signature (5 pts)

Validate the signature you found above. The flag is thevalue.d

Elliptic Curve Cryptography (ECC)

Elliptic Curve Calculator

Elliptic Curve scalar multiplication

Schnorr Signature

Introduction to Schnorr Signatures

Posted 11-21-21