a and b is not given, but since we are given the two points, generator G and the public key point P, we can construct two equations in the form of $y ^ 2 = x ^ 3 + ax + b$. Solving the two linear congruent equation should give us $a, b$.
Trying to do E = EllipticCurve(GF(p), [a, b]) lead to an error by Sage that the curve defined is not a elliptic curve, rather a singular curve.
Simple challenge, there are two key point to solve this. First, the order of the curve is smooth, and also the private keys are relatively small ($2 ^ {64}$). My approach is just simply relying on Sage magic to perform the heavy duty work.
Sage Implementation:
from Crypto.Cipher import AES from Crypto.Util.Padding import pad, unpad import hashlib def gen_shared_secret(P, n): S = n * P return S.xy()[0] p = 99061670249353652702595159229088680425828208953931838069069584252923270946291 a = 1 b = 4 E = EllipticCurve(GF(p), [a,b]) ax = 87360200456784002948566700858113190957688355783112995047798140117594305287669 bx = 6082896373499126624029343293750138460137531774473450341235217699497602895121 A = E.
It is ECDSA, except that there is no hashing algorithm in use. Instead, the hashing algorithm just returns the data that it passes in. This makes it trivial to forge messages with the correct signatures.
class HashFunc: def __init__(self, data): self.data = data def digest(self): # return hashlib.sha256(data).digest() return self.data The following is referring to this question on Crypto StackExchange. The answer mentions how the signing of a message is carried out.
A classic example in timing/power analysis of multiplication algorithms. This boils down to how the double-and-add algorithm is implemented, and bears great resemblance to the square-and-multiply method. The following is the pseudocode for the algorithm of computing $sP$, where $P$ is the given point and $s$ is the number we want to multiply.
let bits = bit_representation(s) # the vector of bits (from LSB to MSB) representing s let res = O # point at infinity let temp = P # track doubled P value for bit in bits: if bit == 1: res = res + temp # point add temp = temp + temp return res We can clearly see that if the if branch is taken, an additional addition step is taken.
An elliptic curve $E$ defined over $F_p$ whose cardinality (or order) is also $p$ is an anomalous curve, and the discrete logarithm becomes trivial. We can employ Smart’s attack, which allows us to perform the discrete log of the curve in linear time.
This paper by Novotney goes over the details of why the attack works. At the time of writing, I wish I understand what’s in the paper - some very topics into group theory.