1
$\begingroup$

The problem is simple: I want to be able to spit out 256-bit "tokens" that only I could've produced because I know my secret key $s$, and given any number of these tokens, no one can figure what $s$ is. How could I do this? Or something similar?

Note that I want a "parallel" implementation: e.g. I could give different tokens to different people separately, and they'll all know it's me.

A "serial" implementation (which isn't what I want) would be much easier:

  1. initially, pick a secret phrase $s_1$
  2. Get the SHA digest $d_{i}$ of the current secret phrase, and pick your next secret phrase $s_{i+1}$.
  3. post $(s_{i-1},d_i)$ publicly with the note that only you can produce the $s_i$ that corresponds to this $d_i$, and you will do that with your next post to prove it's you.
  4. Go back to step 2

Ideally, the solution would be some function $F$ such that a token $t=F(s,r)$ can be verified to have come from $s$ no matter what random input $r$. And no one can figure out what $s$ is.

The scenario I'd have in mind is something like this: John Titor wants to post on 4chan, an anonymous forum, and verify that it's him posting every time by including a 256-bit token each time. How can he do this?

I know there's the potential security threat of some malicious entity trying to pass off old tokens, but ignore that (since there's dozens of ways around it).

$\endgroup$
  • 3
    $\begingroup$ You want a "digital signature". $\endgroup$ – SEJPM Sep 17 '18 at 17:11
  • $\begingroup$ Thanks so much, SEJPM, that's exactly what I was looking for. I'll post a simple answer to this question for good measure. $\endgroup$ – chausies Sep 17 '18 at 17:19
3
$\begingroup$

Digital Signatures are the solution.

A very simple algorithm is

  1. Just like RSA, generate a public key $(N, e)$ for everyone, and a private key $d$.
  2. Whatever message $m$ you post, also post a digital signature $\sigma = m^d ~(mod ~ N)$
  3. People can verify the post is by you by checking that $\sigma^e = m ~ (mod ~ N)$

For more rigorous schemes, see Digital Signature and Digital Signature Algorithm

$\endgroup$
  • 3
    $\begingroup$ Also note that in practice you want to use RSA-PSS or RSA-PKCS1v15 for signatures (because plain RSA signatures are insecure). $\endgroup$ – SEJPM Sep 17 '18 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.