cryptography_new.pdf

(219 KB) Pobierz
An Introduction to Traditional Cryptography
and Cryptanalysis for Amateurs
Chris Spackman
August 2003
1
Table of Contents
1 Introduction...................................................................................................3
Conventions Used in this Book..................................................................3
Warning: Randomness...............................................................................3
2 Simple Substitution Ciphers.........................................................................4
The Caesar Cipher......................................................................................4
Key Words..................................................................................................5
Mixed Alphabets........................................................................................6
Letter Frequencies......................................................................................8
Solving Simple Substitution.....................................................................10
3 Not So Simple Substitution.........................................................................12
Still Not Good Enough.............................................................................13
4 Transposition Ciphers.................................................................................14
Columnar Transposition...........................................................................14
What It Does and Doesn't Do...................................................................16
2
1 Introduction
This book is about traditional cryptography – the use and analysis of tradi-
tional, pre-computer ciphers. We will start with simple substitution and intro-
duce progressively more advanced ciphers.
Conventions Used in this Book
Ciphers and codes are different. However, I am not going to deal with codes
in this book at all, so if I occasionally use the words `code', `encode', or `de-
code' please understand them to refer to ciphers, not codes. For most lay-
men there is no difference between ciphers and codes so I shall use them
interchangably.
Plaintext will be in
typewriter
text.
Ciphertext will be in
 
text.
Warning: Randomness
Random is a loaded word in cryptography. It has a very specific meaning to
specialists but is widely used by non-specialists in ways that invite confu-
sion. True randomness is very difficult for humans to generate. Computers
also cannot really do it, although they are great at creating as many pseudo-
random letters or numbers as you like.
3
2 Simple Substitution Ciphers
Substitution is one of the easiest ways of “hiding” text – you simply replace
one letter with another letter or perhaps a number or symbol. Sounds simple,
but the catch is in how you replace each letter. It has to be done in a way
that lets both the sender and the receiver encipher / decipher accurately
(quickly would be nice to, but accuracy is more important). In other words,
both sides must know the algorithm (a fancy way of saying “process”) for re-
placing each letter. As a practical matter, encoding / decoding algorithms
that involve remembering huge charts or going through 20 separate steps
are no good – people just won't do it. So the method has to be easy to use.
There are a huge number of potential substitution ciphers. Using the let-
ters of a different alphabet to encode is one way. The Japanese language
does this with something called “romaji” – the Japanese language written in
the Latin (Roman, hence “roma”) alphabet. Romaji is theoretically a part of
the Japanese language (something bolted on to the language some might
say) but for many Japanese people, romaji is a cipher they have to deal with
on a daily basis. In this chapter, we will use English for both the plain text
and the cipher alphabet.
Another method of substitution is to convert the letters (of whatever al-
phabet) into numbers. This in turn opens up a host of opportunities for fur-
ther encipherment, because you can do math on numbers much more easily
than on letters. Historically, this was a huge step forward for ciphers and its
importance is not limited to substitution ciphers. We will look at these ciphers
in a later chapter.
One of the earliest recorded ciphers is the one named for Julius Caesar –
the Caesar Cipher. It is very easy to use, but is also very easy to break.
The Caesar Cipher
The Caesar Cipher is a very simple mono-alphabetic substitution. Mono-al-
phabet means what it sounds like, namely that there is only one alphabet
used for enciphering the plain text. Every plain text letter has one and only
one corresponding cipher text letter.
In the case of the Caesar cipher, the alphabet is simply shifted three
spaces and each letter of the plain text is replaced by the new letter. So
a
becomes
and
p
becomes
.
Plain text
Cipher text
Plain text
Cipher text
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
The only things to remember with the Caesar cipher are the number of
letters to rotate the alphabet and the direction of rotation. In this case, the
plaintext is rotated three letters clockwise. The number must be agreed upon
4
by both parties in advance, but can be any number from 1 to 25 (26 would
result in the plaintext and ciphertext being the same). Note that the amount
of rotation, whether three (as in the example above), 12, 17, or 25, has no
affect on the difficulty of unauthorized decryption.
Since there are no charts or other difficult processes to remember, this
system is easy to use. In a time of widespread illiteracy, it might have even
been secure. Today it is trivial and not worth the time it takes to encode and
decode. It won't stop anyone who really wants to read you're mail. It will stop
casual observers from reading it if they aren't willing or able to expend a
small amount of effort.
There are many ways to make a substitution cipher like the Caesar
stronger (ie harder for the bad guy to break) while keeping the basic usage
the same. One way is the use of keywords to scramble the alphabet before
substituting.
Key Words
One problem with the Caesar cipher is that the letters of the alphabet are all
still in order – `a' comes right before `b' and `o' comes right after `n'. This is a
big weakness because it gives the bad guys some information. For example,
this Caeser cipher text \tpt{wklv} tells us a lot about the plaintext. Because
`w' and `v' are next to one another in the alphabet, we know that the plain
-
text letters in those positions must also be next to each other. The same is
true for `k' and `l'. Further, we know that the the plaintext of the cipher `w'
and `k' must be the same distance apart, specifically twelve places. This in-
formation won't tell us what word is encoded by

but it does tell us what
,
words aren't, as well as what words it
might
be. It cannot be the name
`Mark', for example, since the letters `m' `a' `r' and `k' do not have the char-
acteristics that the ciphertext has.
A simple way to avoid giving away so much information, is to use a key-
word. Suppose we use the word, `saturday'. Write out the alphabet normally
and then below it write the keyword, each letter only once, (drop the second
`a' in `saturday'). After the keyword, continue the alphabet, skipping any let-
ter that is in the keyword. It would look like this:
Plain text
Cipher text
Plain text
Cipher text
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
Assuming that the keyword is easy to remember, this system is a little
more secure than a regular Caesar cipher because it gives the enemy less
information, but is not significantly harder to use. Unfortunately, anything en-
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin