How to generate tokens from a secret key?

Question

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

Answer 1

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