Thinking About Encryption, Part 8


Building on the algorithm from the last post, because I still haven’t had time to add more ciphers to En/De yet, say we just want to use Vigenere, Scytale and Rail Fence. For the moment, let’s just stick with upper case letters in the plaintext, because that’s what Vigenere was designed around. But, there’s nothing that says we have to. It’s trivial to treat the source file as binary, and build up a Vigenere table for the entire 256-character ASCII set. Our key could then be converted to 2-byte hex, and each number (0-255) would point to a row of the table where the ASCII table is shifted left that many positions. Then, for enciphering, we could use straight code instead of a look-up table, as in:

(pseudocode)

for i :=0 to plainText.length – 1 do
chPlain := plainText[i];
chKey := keyText[mod(i, length(keyText))];
chCipher[i] := mod(chPlain + chKey, 255);
next;

Instead, I’ll just use the normal Vigenere table, which is the upper case alphabet Caesar-shifted one position to the left for each row.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
BCDEFGHIJKLMNOPQRSTUVWXYZA
CDEFGHIJKLMNOPQRSTUVWXYZAB
DEFGHIJKLMNOPQRSTUVWXYZABC
… etc.

As a reminder, if the keyword is JACK, then we use the row that starts with “J” to look up the first letter of the plaintext, the row that starts with “A” for the second letter, the “C” row for the third letter, the “K” row for the fourth letter, then cycle back to “J” for the 5th letter, and so on.

To build on this, let’s allow for a key phrase, which can be as many words long as we like. If the word is “A”, or when we hit a space, we just skip it. Otherwise, we can apply the following rules:

1) If the length of the phrase is even, apply the Vigenere cipher before applying transposition; otherwise, apply Vigenere after transposition.
2) Strip out the spaces from the phrase and use the resulting string as the Vigenere key.
3) Step through the key phrase one word at a time.
4) If the word length is even, use the Scytale cipher to transpose the working text; otherwise, use rail fence.
5) Strip out any recurring letters from the current word, and use the resulting length as the transposition key.
6) Apply the transposition to the working text, but only for making the rows/columns.
7) Stepping through the stripped keyword, if the letter is even (b, d, f…) reverse the column; otherwise, leave the order alone (columns for Scytale, rows for rail fence).
8) After step 7 is done, rearrange the stripped keyword so the columns are in alphabetic order.
9) Complete the transposition algorithm now, pulling the columns out and putting the working text into one long string.
10) Go back to step 3 as long as there are words left the key phrase.

This looks kind of wordy and unwieldy. So, we need an example.
Say the plaintext is:
“This is a plaintext message.”
-> “THISISAPLAINTEXTESSAGE”

And the key phrase is “Wish you were here.”
The length is 19 characters, which is odd, so step one says the order will be Vigenere then transpose.

The stripped key is:
“WISHYOUWEREHERE”
which becomes the Vigenere key.

Applying the Vigenere to the plaintext, we get for the working text:
PPAZGGUTCWQFACLNQVOASNC

The first keyphrase word is “WISH”, which is four letters long (even), so we use the Scytale transposition. Let’s use padding (x’s) on the last row for simplicity, only.

WISH
—-
PPAZ
GGUT
CWQF
ACLN
QVOA
SNCX

W: PGCAQS
I: PGWCVN
S: AUQLOC
H: ZTFNAX

Even letters: BDFHJLNPRTVXZ
“H” gets reversed

H: XANFTZ

Sorting the letter order,

HISW: XANFTZPGWCVNAUQLOCPGCAQS
—-

Apply the Vigenere again with the “WISHYOUWEREHERE” key:

TIFMRNJKNYDFHSEFSTLOUHOG

“YOU” is an odd length, so we use rail fence. Again, padding the end of the string isn’t really necessary, but I’ll do it for simplicity.

T—R—N—H—S—U—X
-I-M-N-K-Y-F-S-F-T-O-H-G
–F—J—D—E—L—O

Y:TRNHSUX
O:IMNKYFSFTOHG
U:FJDELO

“YOU” -> “OUY”, and all the letters are odd, so none of the rows are reversed.

OUY: IMNKYFSFTOHGFJDELOTRNHSUX

Apply Vigenere again,

EUFRWTMJKKPYMHRYPFPZFOQIR

Rinse and repeat. “were” and “here” turn into “WER” and “HER”, for two more rail fences. “R” and “H” are both even letters, so those rows get reversed in both cases.

This post is getting long enough, so I’ll stop here. The point is that someone who has the key phrase can just reverse the process and get the plaintext back out (minus spaces and punctuation). Anyone else can never be sure that what they’ve obtained was really the same message.

That is, when you attack this cipher, you have to brute force test everything against the following possible cases:
Vigenere is applied before the transposition.
Vigenere is applied after the transposition.
The key length is unknown and there are no reliable repetitions.
The transposition can be either Scytale or Rail Fence.
The transposition keys can be anything between 2 and cipher length/2.
Any given row of the transposition can be reversed, or not.
Any of the above combinations for the Vigenere and transposition ciphers could be applied anywhere between 1 and 1 million times, depending on the length of the key phrase. (More practically, the phrase might be between 2 and 30 words, the longer the better.)

In a way, this situation calls up the “many worlds interpretation” from quantum mechanics, in that not knowing my original key phrase, someone trying to break my message could get back:

“THISISAPLAINTEXTESSAGE”
“THEEYEOFTHETIGERISBLUE”
“INAREDGALAXYFARFARAWAY”

And any other of an infinite combination of readable English words of the same length, even if they get the number of padding characters right. And in at least one of the many worlds, every single possible output would be correct.

This also relates to one strength of the Vigenere – for very long keys, it’s pretty much unbreakable. If you use a one-time pad with keys made of 1000-2000 randomly selected letters, you only use any given key once before throwing it away, and you keep your plaintext shorter than the key length.

That is, say your key is 13 characters long, and the plaintext is “I like cheese”.
If the key is “BDFHJLNPRTVXZ”, you get:

JONRNNUTVLZ

The key doesn’t cycle, and there’s no combination of cipher characters that repeat. Someone not knowing the key could obtain “theoretical” (also 11 letters), because they can’t be sure that the key WASN’T “QHJDWJBLTLO” (because, maybe you didn’t strip out the duplicated letters from the key – and you wouldn’t if you required a 1,000 character-long key).

Speaking strictly theoretically, of course. As always, the weakness in the above algorithm is in how you get the key phrase to the recipient of your message, and in how you ensure the same key is never used twice.

Advertisements
Previous Post
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: