Score:1

Edwards curve ed25519 puzzle

ck flag

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

  1. The 'public key'
  2. The 'private key'
  3. additional data
  4. 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:

  1. 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

  2. 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.

Daniel S avatar
ru flag
HINT: Pick arbitrary values in steps 1-3. Can you now find a value for "static"?
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.