3

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

6
  • 1
    Why not just sign messages? The signature proves identity, and it won't be valid if the signed text has been altered.
    – mirimir
    Commented Dec 16, 2013 at 4:53
  • 1
    "Publish the private one " !!@@@ & keep the public key secret ??!!!! -- seriously . "PRIVATE"=secret "PUBLIC"=know to all .. I just hope it was a typo .. @mirimir is right a digital signature is much better . use a self signed CA to issue the certs and perform digital signature.
    – Arun
    Commented Dec 16, 2013 at 5:32
  • @Arun: with all due respect but if you don't understand the intention behind then you didn't understand how encryption with key works in the first place. the trick is that you cannot (practically) create a public key that matches the private key - so if somebody is able to encrypt with the unknown public key it must be the originator of the known private key for decryption.
    – Raffael
    Commented Dec 16, 2013 at 9:13
  • @Яaffael sorry, but in this case you are the one with the misunderstanding (harsh tones notwithstanding). The point is, private key MUST be kept private (by definition), and the public key can be publicized (again, by definition). Digital signatures work based on that simple scheme, and it seems to be exactly what you're looking for - please read up on that. If it doesn't meet your needs, please explain why not, and what is missing.
    – AviD
    Commented Dec 16, 2013 at 9:41
  • 2
    @Яaffael Asymmetric key generation tends to provide you a set of keys which is useless without the other . The key you choose to keep with you is called private key and the one you choose to distribute is called the public key . Which is why "Publish the private one and keep the public key secret" your intuitive understanding seems wrong to me ..
    – Arun
    Commented Dec 16, 2013 at 10:53

3 Answers 3

2

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 Kp and a private key Ks. 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 Ks.

  • Signature verification: given a message m, a signature value s and the public key Kp, 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 Ks, to produce a pair (m,s) that the verification algorithm will declare valid for public key Kp.

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

3

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .