1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ HINT: Pick arbitrary values in steps 1-3. Can you now find a value for "static"? $\endgroup$
    – Daniel S
    Commented Jun 19, 2023 at 14:11

0

Browse other questions tagged or ask your own question.