The most secure form of cryptography, indeed, the only provably secure form is the One Time Pad.

Pedantically the one time pad is not a single algorithm, but in general it is applying pre-agreed randomness to each letter.

The fundamental problem with the One Time Pad is the Key Distribution Problem, how do two people on opposite sides of the world pre agree the same randomness in a secure fashion?

It is for this reason that Embassies use the Diplomatic Pouch and Courier, and illegal agents carried physical pads into the field with them.

The next problem, as far as the agents are concerned, is how messages are sent without compromising the agent, without making the counter espionage people wonder ‘why is THAT person receiving apparently random messages?’

Where messages were to go one way only (e.g. control to agent) this problem could be solved by the so called ‘number stations’. At pre agreed times, a mechanical voice would read out a string of apparently random numbers. It didn’t matter who heard this as to decode the message one needed to subtract the randomness, and only the agent (listening in private) would have the correct sequence of randomness.

Numbers stations still exist today, you can listen to some recordings from the 80s and 90s online (link spotted via Dirk)

A nice little paper project for people who want a visual representation of Enigma.

Is it possible to play poker by post or email?

Yes, if we assume that there is a trusted ‘know all’ dealer who tells each player their cards. However, is it popssible without such a trusted person.

Let’s summarise the problem. First we must shuffle the cards. Then the cards must be dealt, and no player must be able to tell what cards have been dealt.

Then we must allow the players to see their cards.

Finally we need to allow the various players to verify the cards of others.

The following discussion assumes an algorithm which is commutative. I.e. Suppose that we encode a message, M, using key K1, e.g. C1=E(M,K1), (this just means Encode M with K1), and then encode with K2 to get E(C1,K2), or C2=E(E(M,K1),K2). We can then decode in any order, i.e. Decrypt1=D(C2,K1), M=D(Decrypt1, K2) or Decrypt2=D(C2,K2), M=D(Decrypt2, K1). Whichever order we decode, we get the same M.

The shuffling problem, first of all. Imagine that we have 52 cards. Each card is represented by a short message, M(card). Each of these messages is digitally signed by each player to avoid tampering. The card message includes a timestamp, so a card can only be used in a particular game.

The first player encodes each of the messages. The algorithm must be strong enough to withstand known plaintext attacks, as well as attacks due to the key being repeatedly used.

The first player shuffles these messages and sends them to player 2.

Player 2 encrypts all of these messages again using their key. Mixes them up and sends them back. Each card is now: C=E(E(M,K1),K2)

Player 1 picks his hand from the messages, and sends these cards to player 2. Player 2 decrypts these cards to produce E(M,K1). He sends the cards to player 1 who decrypts to give M, the value of each card.

Player 1 then picks some random cards for player 2’s hand. He decrypts these. C=E(E(M,K1),K2) is decrypted to D(E(E(M,K1),K2),K1). As the encryption is commutative, the result is the original card encrypted by player 2 alone. E(M,K2). Player 2 can then decrypt these to find their hand. The remaining cards are still encrypted by both keys.

When the game is played, and it becomes neccesary to show the cards the card may be published. Each player can verify the digital signatures (not only their own, but those of other people). The timestamp within the card message confirms that the player isn’t simply publishing a card which they had a copy of from an earlier game (the timestamp will have been signed).

Of course, all of this can be done by software quite quickly, and so in practice would not be as cumbersome as it sounds.

By post, one could do a similar thing using padlocks and putting cards in boxes. There will be one box per card, and each box can have a padlock per player on it. Encrypting equates to putting your padlock on, decrypting to taking it off again.

Over the past few days we have been looking at how we might solve:

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

By various means we discovered that the key was 6 letters long, and by two methods we determined what that key was. The key turned out to be ‘Womble’.

BEAUF ORTAN DVIGE NEREB ECOME MUCHE ASIER
TOANA LYSEW HENTH EREIS ALOTO FTEXT TOWOR
KWITH THISA LLOWS USTOU SETHE REPEA TINGN
ATURE OFTHE KEYTO OBTAI NMANY VALUA BLEST
ATIST ICSON CETHE LENGT HOFTH EKEYI SASCE
RTAIN EDORP ERHAP SGUES SEDAT THENG ROUPS
OFLET TERSA KEYLE NGTHA PARTC ANBEA NALYS
EDASI FTHEY WEREA CAESA RCIPH ER

Reformatting this, we get: "Beaufort and Vigenere become much easier to analyse when there is a lot of text to work with. This allows us to use the repeating nature of the key to obtain many valuable statistics. Once the length of the key is ascertained or perhaps guessed at, then groups of letters a key length apart can be analysed as if they were a caesar cipher"

Actually, with Beaufort the groups of letters are a combination of atbash and caesar.

Over the past few days we’ve been working on this puzzle:

VKMHG QFVMO IJOII OHNSN IZXSS CSZEA WWEXU
LIOZB AGEKQ UHRDH IKHWE OBNSQ RVIES LISYK
BIOVF IEWEO BQXIE UUIXK EKTUH NSZIB SWJIZ
BSKFK YWSXS EIDSQ INTBD RKOZD QELUM AAAEV
MIDMD GKJXR UKTUH TSBGI EQRVF XBAYG UBTCS
XTBDR SLYKW AFHMM TYCKU JHBWV TUHRQ XYHWM
IJBXS LSXUB BAYDI OFLPO XBULU OZAHE JOBDT
ATOUT GLPKO FHNSO KBHMW XKTWX SX

We established that the key was 6 letters long, and the first letter of the key was ‘W’

Is there some other way we can crack this?

There is always the known plaintext attack.

You may have noticed that I have a tendency to refer to the cipher itself in the message. So an astute observer might have tried assuming that the plaintext contained ‘BEAUFORT’, and slid this along the message in order to try and work out what the key is.

 Ciphertext: VKMHG QFVMO IJOII OHNSN...
     Groups: BEAUF ORT...
Implied Key: WOMBL EWO...

In the first position we find that a key of ‘WOMBLEWO’ is applied, or ‘WOMBLE’ repeating after six characters.

The message may be easily found from here!