Remove ads

Introducing the LemonFools Personal Finance Calculators

Secret message

jfgw
Lemon Slice
Posts: 608
Joined: November 4th, 2016, 3:36 pm
Has thanked: 88 times
Been thanked: 109 times

Secret message

#83367

Postby jfgw » September 25th, 2017, 2:54 pm

I am a secret agent and I have a secret message that must be delivered intact to another secret agent. It is important that no part of the message falls into the hands of the enemy so I must encrypt the message and send the ciphertext and any keys separately. Three messengers from the other secret agent will come to collect them. However, it is known that one of these messengers is a double-agent who will send copies of everything he is given to the enemy. It is also known that the enemy will send one of their own messengers who will deliver whatever I give him to the enemy but not to the other secret agent. I have no way of knowing which messenger is whom.

How can I reliably send the message without the enemy being able to read any of it?

Julian F. G. W.

UncleEbenezer
Lemon Quarter
Posts: 2371
Joined: November 4th, 2016, 8:17 pm
Has thanked: 217 times
Been thanked: 295 times

Re: Secret message

#83375

Postby UncleEbenezer » September 25th, 2017, 3:29 pm

Ferchrissake, PGP is 25 years old. This is a long-solved problem!

My first thought was that it looks like the "roads to heaven and hell", where you get to ask yes/no questions, but it isn't that. The problem you have posed lacks any kind of asymmetry onto which a logical solution could be hooked. You really need some (pre-existing) shared secret, so if you're disallowing that and ruling out a public key infrastructure (or some wheeze like sending a decoy message to elicit a reaction) you're stuffed.

Unless I'm going even more senile than I realised ...

jfgw
Lemon Slice
Posts: 608
Joined: November 4th, 2016, 3:36 pm
Has thanked: 88 times
Been thanked: 109 times

Re: Secret message

#83388

Postby jfgw » September 25th, 2017, 4:33 pm

UncleEbenezer wrote:Ferchrissake, PGP is 25 years old. This is a long-solved problem!

My first thought was that it looks like the "roads to heaven and hell", where you get to ask yes/no questions, but it isn't that. The problem you have posed lacks any kind of asymmetry onto which a logical solution could be hooked. You really need some (pre-existing) shared secret, so if you're disallowing that and ruling out a public key infrastructure (or some wheeze like sending a decoy message to elicit a reaction) you're stuffed.

Unless I'm going even more senile than I realised ...


I do have a solution. There is no pre-shared secret or public key. There is no two-way conversation at all. I can send a description of the method in plaintext so that the other secret agent can read the message and this will not allow the enemy to read it.

Four messengers will collect what I have prepared for them. Two will deliver straight to the other secret agent, one will deliver to the other secret agent after making a copy to send to the enemy, and the other will deliver straight to the enemy.

I could have posed a similar but simpler problem but have taken into account the intelligence of readers of this board.

Julian F. G. W.

Rover110
Posts: 11
Joined: November 6th, 2016, 4:06 pm
Has thanked: 2 times
Been thanked: 2 times

Re: Secret message

#83391

Postby Rover110 » September 25th, 2017, 4:45 pm

This was written before jfgw's follow-up.

As I see it, 4 messengers will come to me.
2 are trustworthy and will only pass their given message to my fellow agent.
1 is a double-agent who will pass his given message to my fellow agent but also to the enemy
1 is a fake who will only pass his given message to the enemy.

So of the 4 messages I hand out, 3 will get to my fellow agent and 2 will get to the enemy.

I have no way of knowing who will get what. But I need to ensure that my fellow agent will be able to recover the original message from the three-out-of-four messages he gets, but the enemy will not be able to recover the original message from his two-out-of-four.

Suppose each message I give is in two parts: encryption-key and encrypted-message.
Then in message 1 I could put Key_A and Key_B(Key_C(message))
message 2 could have Key_B and Key_C(Key_D(message))
message 3 could have Key_C and Key_D(Key_A(message))
message 4 could have Key_D and Key_A(Key_B(message))
where Key(Message) is the result of encrypting Message by Key.

My fellow agent will end up with three keys and 3 encrypted messages. And by applying the appropriate keys will be able to decode the message.
But the enemy will not have enough to decrypt.

- Rover

jfgw
Lemon Slice
Posts: 608
Joined: November 4th, 2016, 3:36 pm
Has thanked: 88 times
Been thanked: 109 times

Re: Secret message

#83396

Postby jfgw » September 25th, 2017, 5:05 pm

Correct answer Rover110.

There are other methods but that may well be the neatest.

Julian F. G. W.

UncleEbenezer
Lemon Quarter
Posts: 2371
Joined: November 4th, 2016, 8:17 pm
Has thanked: 217 times
Been thanked: 295 times

Re: Secret message

#83459

Postby UncleEbenezer » September 25th, 2017, 8:15 pm

jfgw wrote:Four messengers will collect what I have prepared for them. Two will deliver straight to the other secret agent, one will deliver to the other secret agent after making a copy to send to the enemy, and the other will deliver straight to the enemy.

Aha! That's different. Last time it was the classic three messengers, one being the enemy and one being both. At least as I read it: perhaps there was a bit of prejudiced expectation there, from a culture where puzzles conventionally involve three agents.

With 2+1+1 it's far too easy: any solution that relies on the recipient getting any three of the messages works. A robust solution would be to send each messenger with an individual elliptic curve encryption of the message, and a two-part M-Pin decryption key split across each other pair of messengers. Thus the agent receiving three messages has (three times over for a bit of redundancy) the message and both parts of a key to unlock it, whereas the enemy receiving two messages only has one half of each key.

davidmichaels
Posts: 4
Joined: June 13th, 2018, 8:10 am

Re: Secret message

#145372

Postby davidmichaels » June 13th, 2018, 8:19 am

Can any one explain this to me :p :o

Rover110
Posts: 11
Joined: November 6th, 2016, 4:06 pm
Has thanked: 2 times
Been thanked: 2 times

Re: Secret message

#145390

Postby Rover110 » June 13th, 2018, 9:12 am

davidmichaels wrote:Can any one explain this to me :p :o

I'm sure there are people who are willing to explain it. But it's not easy unless you expand on what the "this" is that you'd like explaining. And it would be helpful if you could also describe your level of knowledge and what understanding you're after.

For example, I don't know what "elliptic curve" encryption is, and I wouldn't be surprised if how it works couldn't easily be explained without reference to degree-level mathematics. You might get a feel of it by reading the Wikipedia page.

Regards,
Rover

Gengulphus
Lemon Quarter
Posts: 2083
Joined: November 4th, 2016, 1:17 am
Been thanked: 909 times

Re: Secret message

#148839

Postby Gengulphus » June 29th, 2018, 2:59 pm

davidmichaels wrote:Can any one explain this to me :p :o

Very briefly, an encryption system involves taking a message you want to send and a 'key', which is some extra information which doesn't convey any message, and combining them in some way to form an encrypted message that is what you actually send. As a very simple example, the key might be an English word or phrase with no repeated letters, such as "THE QUICK BOARS", and the encryption method might be to write down the alphabet, then below it the phrase followed by all the letters of the alphabet that are not in the phrase in reverse alphabetical order:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
T H E Q U I C K B O A R S Z Y X W V P N M L J G F D

Then take the message you want to send (which had better be written in a form that makes sense with all its spaces and other non-letters omitted, and doesn't care about the difference between capital and lower-case letters) and change each letter to the letter that is below where it appears in the top row. For example, suppose the message you want to send is "The enemy will land at 1:30 pm tomorrow". You'd better change the numerals to words and check that it's still readable when written without spaces or the colon, and all in capitals "THEENEMYWILLLANDATONETHIRTYPMTOMORROW" (it's not ideal, but the recipient should be able to work out e.g. that "ATONE" is supposed to be "at one" and not "a tone" because one makes a sensible message and the other doesn't!). Then translate it according to the table to produce "NKUUZUSFJBRRRTZQTNYZUNKBVNFXSNYSYVVYJ".

As long as the recipient knows the key "THE QUICK BOARS", they can easily write down the same table and decrypt the encrypted message by changing each letter to the letter that is above where it appears in the bottom row. Anyone else has a harder job...

The problem is making certain the recipient knows the key! Sometimes that's easy, but this problem supposes they don't and have got to be told it. Rover110's solution involves producing four different keys, encrypting the message first with one key and then encrypting the encrypted message again using a different key, in four different ways, and giving each doubly-encrypted message to one of the messengers along with one of the keys that wasn't used for either of its encryptions. Furthermore, the exact scheme is chosen in such a way that the enemy, who gets two of the doubly-encrypted messages and two of the keys, never gets the right two to decrypt either of their doubly-encrypted messages, but the recipient, who gets three of the doubly-encrypted messages and three of the keys, always gets the right two to decrypt at least one (and in fact always exactly one) of their doubly-encrypted messages.

I should probably add that I've selected the example encryption technique I've used above to be easily explained, not to be a good encryption technique! It most definitely isn't a good encryption technique: just the knowledge that it's a simple letter-for-letter substitution and that the encrypted message is "NKUUZUSFJBRRRTZQTNYZUNKBVNFXSNYSYVVYJ" (i.e. without knowledge of the key) is enough to allow a suitably-programmed computer with a comprehensive list on English words to decrypt it by systematically checking the possibilities: the first word must be a one-letter word, or a two-letter word made up of two different letters, or a three-letter word made up of three different letters, or a four-letter word that starts with three different letters and then repeats the third of them, etc. For each of those possibilities, it can run through its dictionary looking for words that match; for each such match, it can then work similarly with a more restricted set of possibilities for the second word (for example, on what is in fact the correct for word "THE", the possibilities for the second word are the one-letter (non-)word "E", the two-letter words consisting of "E" followed by a letter that isn't in "THE", the three-letter words starting and ending with "E" and with a letter that isn't in "THE" in the middle, etc. The list of possible first words is quite long (probably tens of thousands, I would guess), but the list of possible second words for any particular one of them will generally be a lot shorter, the list of possible third words shorter still, etc, and so on: overall, the number of possibilities it needs to explore is probably only in the millions to billions range, which means such a computer can come up with a short list of possible messages in a matter of seconds to minutes.

As an example, try feeding "NKUUZUSFJBRRRTZQTNYZUNKBVNFXSNYSYVVYJ" to https://quipqiup.com/, which is a publicly available solver for such simple letter-for-letter encryptions (I don't think it works in quite the way I describe above, by the way, but there are plenty of methods for breaking such encryption techniques). It doesn't get the message quite right, guessing that there's a space where there isn't, but the enemy would have no trouble seeing what it was intended to be and deciding to change the time of their landings!

But modern encryption techniques are much more sophisticated, able to deal with arbitrary messages (rather than just all-capital-letters ones) and highly resistant to computer attacks. Or at least, to all known attacks after serious attempts by experts to break them (an encryption technique won't be generally adopted until after an extended period of expert attacks) on existing types of computer hardware (new types such as quantum computers will be a different matter if they can be developed sufficiently - some modern encryption techniques are quite vulnerable to them in principle and may well have to be made obsolete in practice in due course).

Gengulphus

ReformedCharacter
Lemon Slice
Posts: 512
Joined: November 4th, 2016, 11:12 am
Has thanked: 122 times
Been thanked: 97 times

Re: Secret message

#148914

Postby ReformedCharacter » June 29th, 2018, 6:52 pm

UncleEbenezer wrote:Ferchrissake, PGP is 25 years old. This is a long-solved problem!

Unless I'm going even more senile than I realised ...


It's older than that, originally conceived by James Ellis and Clifford Cocks at GCHQ between 1970-1973, although kept secret until 1997 by which time some folk at the Massachusetts Institute of Technology had taken the credit.

RC


Return to “Games, Puzzles and Riddles”

Who is online

Users browsing this forum: No registered users and 1 guest