pencil-and-paper encryption
Adrian Abbott
pencil-and-paper encryption method I just thought of (and am
probably not the first to have thought of it). After a little
practice it only takes about 2 seconds per letter to encrypt by
hand, and so is not much more taxing than Vigenere. (I was trying to
think of ways that would have been both practical and completely
secure 100 years ago.) Here's how it works, it's a kind of rolling
Vigenere cipher:
An alphabet grid is made according to a keyword or phrase. In the
example I will use a name from a Fielding novel, "Jonathan Wild",
minus duplicates:
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
----------------------------------------------------------
1 j J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
2 o O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
3 n N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
4 a 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
5 t T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
6 h H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
7 w W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
8 i I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
9 l L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
10 d D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
11 e E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
12 f F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
13 g G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
14 k K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
15 m M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
16 p P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
17 q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
18 r R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
19 s S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
20 U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
21 V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
22 X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
23 Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
24 Z Z 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
25 A 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
26 B 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 A
The text to be encrypted for my short example is just "hello".
The first letter of plaintext is encrypted according to the nth
alphabet, where n is one greater than the length of the key phrase.
In this example "jonathwild" has 10 letters so we would use the 11th
alphabet, and so "h" is encrypted as "L".
Then set n := n + x mod 26, where x is the row of the plaintext
letter, in this case "h" which is in the 6th row. We obtain n = 11 +
6 = 17.
Now the next letter of plaintext, "e", is encrypted using the 17th
alphabet and becomes "U". Increment n by the row of "e". Repeat
until the end of the plaintext is reached; we obtain values for n as
follows:
17 + 11 = 2
2 + 9 = 11
11 + 9 = 20
and "l" is encrypted as "Z", "l" is encrypted as "P", and "o" is
encrypted as "I".
The complete ciphertext is "LUZPI"
You will easily see how this can be deciphered, using the same grid
and the operations in reverse.
Is this secure against non-computer methods, if the algorithm is
known but not the keyword? I can't see that the historical method
for beating Vigenere is easily adaptable to work here.
If the cipher can be broken by some clever sort of analysis, would
the addition of a keyword-defined shuffle help:
JONATHWILD, relative to its alphabetised ordering ADIJLNOTW, is 5 8
7 1 9 4 10 3 6 2. Take the ciphertext, divide it into 10-letter
chunks internally numbered 1-10, and reorder it thusly:
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3
5 8 7 1 9 4 10 3 6 2 5 8 7 1 9 4 10 3 6 2 5 8 7 1 9 4 10 3 6 2 1 2 3
So before attempting to decipher, one would have know the length and
relative alphabetical ordering of the keyword.
If someone would like to try beating this method without a keyword,
I can generate some ciphertext as a puzzle.
Thanks, and sorry if such an encryption method is well-known.
AA
Robert Reynard
news:a0erhf$j8l$1...@news.fas.harvard.edu...
> This is a question about the vulnerability of a simple
> pencil-and-paper encryption method I just thought of (and am
> probably not the first to have thought of it).
No, you are not the first.
> practice it only takes about 2 seconds per letter to encrypt by
> hand, and so is not much more taxing than Vigenere. (I was trying to
> think of ways that would have been both practical and completely
> secure 100 years ago.)
Prior to 1850 (about 150 years ago) the standard Vigenere was considered
'unbreakable.'
Your cipher appears to be a mixed cipher alphabet Vigenere. It is indeed
more difficult to break, but not impossible. Hardly much 'fun' considering
the time and effort required, not to mention the amount of ciphertext one
would need. As with breaking a 'standard' Vignere, it is a matter of finding
repeats, which is a function of the key length and plaintext content.
> Is this secure against non-computer methods, if the algorithm is
> known but not the keyword? I can't see that the historical method
> for beating Vigenere is easily adaptable to work here.
No, but breaking a ciphertext created in this manner would require time and
effort. Worth the trouble if you were at war and needed to read the traffic,
but not something a 'puzzler' would care to tackle.
> If the cipher can be broken by some clever sort of analysis, would
> the addition of a keyword-defined shuffle help:
Not really, unless finding the keys is the goal rather than the plaintext.,
since shuffling the key just rearranges the tableau. The underlying
plaintext will still emerge based upon analysis of repeats.
> If someone would like to try beating this method without a keyword,
> I can generate some ciphertext as a puzzle.
Probably not worth the effort. You might encrypt, using a short key, a
single letter plaintext, such as 'e' to see how the repeats occur, or a
simple word phrase such as 'THIS IS A TEST THIS IS A TEST...' and identify
the repeats, which is the entry into the ciphertext that will eventually
yield a solution.
Robert Reynard
Author, Secret Code Breaker series of crypto books for young readers (8-16
yr.)
Secret Code Breaker Online at ==> http://codebreaker.dids.com
Adrian Abbott
: "Adrian Abbott" <im...@really.here.gov> wrote in message
: news:a0erhf$j8l$1...@news.fas.harvard.edu...
:> This is a question about the vulnerability of a simple
:> pencil-and-paper encryption method I just thought of (and am
:> probably not the first to have thought of it).
: No, you are not the first.
Not questioning your answer here, but do you have a reference to the use
of such a scheme (you'll find it upthread, I won't repost it here) any
time in history?
:> practice it only takes about 2 seconds per letter to encrypt by
:> hand, and so is not much more taxing than Vigenere. (I was trying to
:> think of ways that would have been both practical and completely
:> secure 100 years ago.)
: Prior to 1850 (about 150 years ago) the standard Vigenere was considered
: 'unbreakable.'
It may have been *considered* unbreakable, and maybe it was never broken
at the time, but it could have been broken, had someone known how.
: Your cipher appears to be a mixed cipher alphabet Vigenere. It is indeed
: more difficult to break, but not impossible. Hardly much 'fun' considering
: the time and effort required, not to mention the amount of ciphertext one
: would need. As with breaking a 'standard' Vignere, it is a matter of finding
: repeats, which is a function of the key length and plaintext content.
Hmm - how will it be a function of key length? There is no cycling through
the key as in standard Vigenere, rather the key is used to set up the
initial ordering of cipher alphabets, which are then selected as a
function of the last alphabet used and the last letter encrypted.
:> If the cipher can be broken by some clever sort of analysis, would
:> the addition of a keyword-defined shuffle help:
: Not really, unless finding the keys is the goal rather than the plaintext.,
: since shuffling the key just rearranges the tableau. The underlying
: plaintext will still emerge based upon analysis of repeats.
I don't think you understood, it's not a shuffle of the key/tableau, but a
key-defined shuffle of the ciphertext. Eg if the key was "cob", whose
ordering wrt alphabetical is 231, and the initially enciphered text is
WRYHFSVNX, then the shuffled ciphertext to be transmitted is RYWFSHNXV,
where each triplet has been rearranged according to the ordering of the
keyword.
In other words this will certainly alter the structure of the ciphertext
wrt repetition.
I guess I could get across the thrust of my question this way: if you and
I were sent back to 1900, and I wanted to be able to easily encrypt a
large number of messages that you would have absolutely no chance of
deciphering without mechanical/computer aid, even with all cryptanalysts'
knowledge from 2001, would this do the trick for me?
Thanks for your comments and I welcome more.
Douglas A. Gwyn
> ... There is no cycling through
> the key as in standard Vigenere, rather the key is used to set up the
> initial ordering of cipher alphabets, which are then selected as a
> function of the last alphabet used and the last letter encrypted.
Yeah, that's a form of "ciphertext autokey". HMM methods can crack it.
Ferdinando
Only 2 questions:
+++ Why not a "plaintext autokey" ?
Adrian uses the plaintext letters (hello) to find
the next encryption alphabet...
+++ What are HMM methods ?
Thanks
Ferdinando
John A. Malley
>
> "Douglas A. Gwyn" <DAG...@null.net> wrote in message news:<3C2D7EC5...@null.net>...
> > Adrian Abbott wrote:
> > > ... There is no cycling through
> > > the key as in standard Vigenere, rather the key is used to set up the
> > > initial ordering of cipher alphabets, which are then selected as a
> > > function of the last alphabet used and the last letter encrypted.
> >
> > Yeah, that's a form of "ciphertext autokey". HMM methods can crack it.
>
> Only 2 questions:
>
> +++ Why not a "plaintext autokey" ?
Well this came quickly to mind:
Suppose we did use the previous plaintext character as the key for the
simple substitution cipher applied to the current plaintext character (a
Caesar substitution.) The keystream statistics are the plaintext
characters statistics.
The most frequent plaintext character is the most frequent key used to
encipher plaintext characters. The next most frequent plaintext
character is the next most frequent key. And so on.
Plaintext digraphs and trigraphs are key digraphs and trigraphs. The
most frequent pairings and triples of plaintext characters are the most
frequent pairings and triples of key characters in the keystream.
>
> +++ What are HMM methods ?
"Hidden Markov Model" methods.
A Markov chain is like a finite state automaton that recognizes
character strings (an acceptor) or makes character strings (a
generator.) For a Markov chain, though, state transitions get
probabilities. The sum of the probabilities of the state transitions out
of the current state must equal one. (For example, starting in state S1
there's a 50% chance to transition to state S2, a 25% chance to
transition to state S3 and a 25% chance to transition to state S4.)
Use Markov chains to model the plaintext language. Generate the most
probable sub-sequences of plaintext digraphs and trigraphs. Since
plaintext statistics are the keystream statistics, we generate the most
probable key sub-sequences to decrypt the ciphertext. Try some of these
sub-sequences against the ciphertext and look for sensible decrypts. And
then unravel it from there (a cryptanalyst recognizes words in the
partial decrypts and expands out the decryption since the plaintext is
the key sequence.)
I never actually tried this but it looks plausible.
John A. Malley
10266...@compuserve.com
John A. Malley
>
[...]
Doh! I missed something important!
Since the Markov chain model generates probable plaintext character
sequences, we can encipher them (using them as the keystream) and look
directly for matches in the ciphertext.
John A. Malley
10266...@compuserve.com
Douglas A. Gwyn
> +++ Why not a "plaintext autokey" ?
Okay, I was misled by your phrase "the last letter encrypted".
> +++ What are HMM methods ?
HMM = Hidden Markov Model, a standard computational technique
(the first really feasible algorithm for which was devised by
government cryptanalysts). As to how to do it, I don't think
I want to explain that at this time.
Douglas A. Gwyn
> Since the Markov chain model generates probable plaintext character
> sequences, we can encipher them (using them as the keystream) and look
> directly for matches in the ciphertext.
But that's essentially a brute-force search over the space.
There are published efficient algorithms for *fitting* a HMM to the
observed data, which results in estimates of the model parameters.
Adrian Abbott
: Suppose we did use the previous plaintext character as the key for the
: simple substitution cipher applied to the current plaintext character (a
: Caesar substitution.) The keystream statistics are the plaintext
: characters statistics.
: The most frequent plaintext character is the most frequent key used to
: encipher plaintext characters. The next most frequent plaintext
: character is the next most frequent key. And so on.
[OP here again] - I can see how this would work, except in the scheme I
proposed you use the last plaintext letter *added to the last key used* to
find the next alphabet. So it's not the case that the Caesar sub alphabet
used will most often be the one starting with 'e', but rather that the
alphabet used will most often be N alphabets ahead of the last one used,
where N is the number of the row that starts with 'e' in the grid
determined by the keyword. With the keyword used in my example upthread,
'e' was in row 11, so most often the alphabet would move forward by 11. I
don't see how that would help unless you knew the initial ordering of the
grid, which is keyword-defined.
AA
John A. Malley
Mr. Abbott,
Finally got a clear moment to write a cogent response.
Suppose we did use the previous plaintext character added to the
previous key (modulo 26) to make the current key for the simple
substitution cipher to apply to the current plaintext character (a
Caesar substitution). Do the statistics of the plaintext come through in
the ciphertext?
Yes, and in an interesting way.
Let the alphabet be represented by integers [0 - 25] for [A - Z] so C(i)
and P(i) can be represented as integers (modulo 26)
Encrypt P(i) as
C(i) = P(i) + shift(i) (mod 26),
where shift(i) = f(P(i-1)) + shift(i-1) (mod 26).
Now shift(i) is the key for the encryption of the ith letter of the
plaintext, 0 <= shift(i) <= 25, and shift(i) depends on the previous
plaintext character and the previous key value. The function f(P(i-1))
maps every character of the alphabet to another character, one-to-one
and onto. f() is a permutation of the alphabet. The initial key value
(shift(1)) is secret to Alice and Bob.
Look at the difference between successive ciphertext characters values:
C(i) - C(i-1) (mod 26) = P(i) + shift(i) - P(i-1) - shift(i-1) (mod 26),
or
C(i) - C(i-1) (mod 26) = P(i) - P(i-1) + f(P(i-1)) + shift(i-1) -
shift(i-1) (mod 26),
simplifying to
C(i) - C(i-1) (mod 26) = P(i) - P(i-1) + f(P(i-1)) (mod 26).
The difference between successive ciphertext characters is the
difference between successive plaintext characters biased by a value
determined by only the previous plaintext character. Plaintext
statistics show up in the ciphertext differences statistics.
The most frequent value of P(i) - P(i-1) is the difference between the
characters in the most frequent digraph (P(i-1)P(i)) in the plaintext.
That value is biased by f(P(i-1)) and the most frequent bias seen is
driven by the most frequent character in the plaintext. Plaintext
digraph statistics show up as ciphertext digraph statistics. And
correlations between successive digraphs (which typically follow which)
also show up in the ciphertext digraphs (whose values are the ciphertext
differences).
I think a Hidden Markov Model attack works more like this (after
pondering Doug Gwyn's response to my earlier post):
We build a baseline Markov model of the plaintext language using some
corpus of text in the plaintext alphabet. Assume the plaintext language
statistics are ergodic, so any "reasonable" amount of plaintext exhibits
the same statistics (within some error bound.) The ciphertext exhibits
about the same statistics as the plaintext. Train a Hidden Markov Model
on the intercepted ciphertext and compare its parameters to the baseline
HMM's parameters. Corresponding parameters determine the most probable
corresponding ciphertext characters, digraphs, etc. to plaintext
characters, digraphs, etc.
John A. Malley
10266...@compuserve.com
Adrian Abbott
: Finally got a clear moment to write a cogent response.
[snip]
Thanks a lot for this astute analysis!
Best --AA
David Wagner
>Encrypt P(i) as
>C(i) = P(i) + shift(i) (mod 26),
>
>I think a Hidden Markov Model attack works more like this [...]
Huh. I was imagining something totally different.
Recall that a Markov model consists of a statespace S, an output alphabet
O, and a bunch of transitions. Each transition is of the form
s --o--> s' with prob. p,
meaning that in state s, with probability p we output o and change to
state s'. In a Hidden Markov Model, the transition probabilities are
unknown ("hidden"). However, given a long output sequence, the Baum-Welch
algorithm can efficiently estimate these unknown probabilities.
Now maybe you see how I was thinking of modelling this cipher as a HMM.
The statespace is S = {0,1,..,25}, and the state of the process at time
i will be shift(i). We can see that set of all possible transitions
with non-zero probability are exactly those of the form
s --x+s--> f(x)+s,
where s,x in S are arbitary; the probability of this transition is
just the probability that we see the value x as a plaintext symbol (its
unigram frequency in English sources, basically). Consequently, if we
train a HMM on a long ciphertext, we can hope that its parameters will
converge to 0 everywhere except for the transitions of the above form,
and we can also learn the most likely starting state of the process.
Notice that this reveals the key. Notice moreover that this attack
works even if the function f() is unknown to the attacker.
The above attack can perhaps be improved by exploiting higher-order
statistics of the plaintext. In particular, if we have a Markov
model with statespace T that approximates the plaintext source, we can
construct a HMM with statespace S' = {0,1,..,25} x T, where the state
(s,t) represents shift(i) = s and that the plaintext Markov model is in
state t at time i. This might allow us to reduce the amount of ciphertext
required for this style of attack.
Does this work? How does this compare to your proposed approach?
Any comments?
Douglas A. Gwyn
> ... given a long output sequence, the Baum-Welch
> algorithm can efficiently estimate these unknown probabilities.
We often add Eagon as co-author of that algorithm,
which might be briefly described as a forward-backward
recursive reestimation approach. It was better known
among cryppies for decades by the name of its primary
implementation, which you might be able to figure out
from Reeds' 28 Aug 1998 posting to the Voynich mailing
list.
Douglas A. Gwyn
> John A. Malley wrote:
> >I think a Hidden Markov Model attack works more like this [...]
> Huh. I was imagining something totally different.
> Does this work? How does this compare to your proposed approach?
> Any comments?
As I recall I was the one who noted that HMM methods could
be used to solve this; I think John was just guessing what
I had mind. Your (David's) approach is pretty much what I
meant.
Ferdinando
> pencil-and-paper encryption method
[snip]
...what about the possibility that KRYPTOS
could be encoded in such a way ?...
regards
Ferdinando
Douglas A. Gwyn
> ...what about the possibility that KRYPTOS
> could be encoded in such a way ?...
We've already deciphered all but the last little bit of Kryptos.
John A. Malley
>
> David Wagner wrote:
> > John A. Malley wrote:
> > >I think a Hidden Markov Model attack works more like this [...]
> > Huh. I was imagining something totally different.
> > ...
> > Does this work? How does this compare to your proposed approach?
> > Any comments?
>
> As I recall I was the one who noted that HMM methods could
> be used to solve this; I think John was just guessing what
> I had mind.
Yes, that is true. I did not know exactly how HMM methods apply.
I thought in terms of model matching - derive the best-fit model of the
ciphertext to a representative model of the plaintext language. Look for
matching parameters and statistics to figure out the best fit plaintext
substrings or string to ciphertext substrings or string.
I do know I don't understand HMMs well enough for cryptanalysis. :-)
> Your (David's) approach is pretty much what I meant.
David Wagner's demonstration of cryptanalysis of the posted cipher with
the HMM is extremely helpful to me (and other sci.crypt readers, I
expect). I never thought of shift(i) as states in the HMM.
Thanks Prof. Wagner!
John A. Malley
10266...@compuserve.com
Ferdinando
oh yes,
...i was wondering about the last 97 chars....
greetings
Ferdinando