Recently a friend of mine showed me a "puzzle" he created with edwards curve ed25519
It is based on adding and multiplying points on the curve
You supply four arguments to the program
- The 'public key'
- The 'private key'
- additional data
- static point value
He considers the puzzle as solved if the following 'equation' applies:
hash = sha512(public key + data)[:32] // first 32 bytes
private key * ed25519 base point == ed25519addpoint(ed25519scalarmult(hash * public key), static point)
It can be represented with the following python code with the usage of nacl cryptography library:
import nacl.bindings
import hashlib
def sha512(data):
h = hashlib.sha512()
h.update(data)
res = h.digest()
return res
data = "additional data in hex".decode("hex")
privkey = "private key in hex".decode("hex")
pubkey = "public key in hex".decode("hex")
static = "static point in hex".decode("hex")
pprim = sha512(pubkey + data)
pprim = pprim[:32]
x = nacl.bindings.crypto_scalarmult_ed25519_base(privkey)
y = nacl.bindings.crypto_core_ed25519_add(nacl.bindings.crypto_scalarmult_ed25519(pprim, pubkey), static)
if x == y:
print "Congratulations, puzzle solved!"
else:
print "Not really"
He claims that he found multiple solutions to this problem. My question is: is this really solvable (and if yes, how?) or is he only trying to trick me into trying to solve an unsolvable problem.
From my cryptographic knowledge of ed25519 curve you cannot solve this from both ways:
if you supply any value as the private key you could subtract the static point and then try to find values of pprim and public key - if it is solvable this is the way I tried to solve it
compute the hash of public key and data and then try to find the value of private key
Both of this ways are impossible for me, because either solution is equal to finding private key from public (d from having P = d*G) on ed25519 which, from my knowledge is impossible.