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.

We can factor $N$ using the given phi, or just simply look up the number on FactorDB. If the number returned has the form of $c = g ^ {k}$ with some even number $k$, we have the observation that for every factor of $N$, $c$ is a quadratic residue under that base, whereas the randomly generated number almost never generate a number that is a quadratic residue of all factors.