How to make authenticity of text verifiable without third party services?

Question

There is a person who wants to establish a system which allows her/him to publish texts anywhere and make it verifiable that s/he is the true origin of that text. Only the first message is not verifiable but will establish the system.

Example:

"Hi, I am Mrs X and I am going to whistle you some interesting stuff. To prevent compromitation and proove that a text you might find anywhere on the web is from me I will use the following method .... "

Something that comes to my mind is this:

1) Create key pair

2) Publish the private one and keep the public key secret

3) Announce: the next text will have the Base64 of the encrypted text "what a wonderful day" below it.

4) Next time: publish message - announce the next to be found verification text - encrypt the text "what a wonderful day" using public key and base it on 64 - put it below the message.

Now if somebody wants to verify they will decrypt the verfication text using the known private key and so on.

Would something like this work? Or is there a simple established method?

Possible attack vectors: - exchange of published private key - use Base64(Encrypted(TEXT)) seconds after true published text and make it indistinguishable which one is true

Answer 1

You are using the "encrypt with the private key" analogy. Don't do that, it will trigger only confusion.

What you want is a digital signature scheme. Such a scheme consists of three algorithms:

• Key generation: this algorithm produces a new key pair, with a public key K_p and a private key K_s. The public key, as its name says, can be made public, i.e. revealed to the world at large, and this does not disclose the private key (though the private key is still mathematically linked to the public key).

• Signature generation: given a message m, a signature s is produced, using the private key K_s.

• Signature verification: given a message m, a signature value s and the public key K_p, the verification algorithm returns "true" or "false", depending on whether the signature matches the message for that public key, or not.

The signature is sound if what the signature generation algorithm produces is indeed declared valid by the signature verification algorithm. The signature is secure if it is not feasible, without knowing K_s, to produce a pair (m,s) that the verification algorithm will declare valid for public key K_p.

Unfortunately, when the first workable signature algorithm was described, the idea of the algorithm was said to be "asymmetric encryption in reverse": the signature was generated by "encrypting the message with the private key" (or, equivalently, by swapping private and public keys, i.e. making the private key public and vice-versa). This was unfortunate because:

• Not all signature algorithms can be seen as "reversed asymmetric encryption". This analogy works only for RSA.
• In fact, the analogy does not work for RSA either; it works only for the mathematical core of RSA, but not with the "full RSA" which also include things like padding, which are crucial for security but break the "reverse encryption" analogy.

The "encryption in reverse" description is a widespread way to "explain signatures" and, in doing so, mostly spreads confusion. Don't fall in that trap.

---

A signature algorithm seems to map well to what you are envisioning. The author would include his public key in the first message. Then each ulterior message would be signed with the corresponding private key, and everybody could verify that signature relatively to the public key in the first message.

However, note that authorship is the combination of two concepts:

• Responsibility: "Yes, I am willing to assert that I wrote these words and will be bound by them."
• Exclusivity: "All other people who claim having written these words are filthy liars."

A signature will ensure both only if people have a way to make sure that what they see as "first message" is indeed the true first message, i.e. contains the correct public key. Another person Y wanted to claim authorship of the same texts could publish his own "first message" with his own public key, and sign (with his own private key) whatever X publishes. The public at large would have a hard time finding out who wrote the text first. In order to establish true authorship (in that sense), timestamps may be used (in addition to signatures, not replacing them).

Answer 2

You can use commitment schemes such as the one way hash chains or Merkle trees for this purpose to provide authentication.

Answer 3

It seems there is a considerable misunderstanding here.
In asymmetric encryption, the private key MUST be kept private (by definition), and the public key should be publicized (again, by definition).

It sounds like what you are looking for is a digital signature, which works based on that simple scheme.

In a nutshell, a digital signature takes a hash of the data you want to sign, then performs an asymmetric "encryption" on the hash, using the private key. For validation, anyone else can decrypt the encrypted hash, using the author's public key, take a new hash of the received data, and compare the hashes.
This ensures both that the data was not changed since it left the author (integrity), and that the author is the owner of the corresponding private key (authenticity).

From Wikipedia:

A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, such that the sender cannot deny having sent the message (authentication and non-repudiation) and that the message was not altered in transit (integrity).

So, assuming you have a way to bootstrap this scenario, by securely publishing your public key (and yes, this is the tricky part), it is very straightforward to implement the scheme you're looking for. (Just remember to use a standard algorithm, do not try to implement this yourself....)