MODULE-1
INTRODUCTION
Introduction. How to Speak Crypto. Classic Crypto. Simple Substitution Cipher. Cryptanalysis of a
Simple Substitution. Definition of Secure. Double Transposition Cipher. One-time Pad. Project
VENONA. Codebook Cipher. Ciphers of the Election of 1876. Modern Crypto History. Taxonomy
of Cryptography. Taxonomy of Cryptanalysis.
How to Speak Crypto
The basic terminology of crypto includes the following.
• Cryptology — the art and science of making and breaking "secret codes."
• Cryptography — the making of "secret codes."
• Cryptanalysis — the breaking of "secret codes."
A cipher or crypto system is used to encrypt data.
The original unencrypted data is known as plaintext, and the result of encryption is ciphertext.
We decrypt the ciphertext to recover the original plaintext. A key is used for encryption and
decryption.
In a symmetric cipher, the same key is used to encrypt and to decrypt.
In public key crypto (Asymmetric cipher), the encryption key is known as the public key,
whereas the decryption key, which must remain secret, is the private key.
In symmetric key crypto, the key is known as a symmetric key.
2.3 Classic Crypto
2.3.1 Simple Substitution Cipher
In the simplest case, the message is encrypted by substituting the letter of the alphabet n places ahead of
the current letter. For example, with n = 3, the substitution—which acts as the key—is
plaintext: abcdefghijklmnopqrstuvwxyz
ciphertext: DEFGHIJKLMNOPQRSTUVWXYZABC
example: fourscoreandsevenyearsago is encrypted as
IRXUVFRUHDAGVHYHABHDUVDIR.
2.3.2 Cryptanalysis of a Simple Substitution
Given a cipher text
According to Figure 2.2, "E" is the most common letter in the English language.
According to Figure 2.3 "F" is the most common letter in the encrypted message
So by replacing F by E in the given cipher text , Since the third plaintext letter appears to be "e," we can
guess that the first word of the plaintext is "the." Making these substitutions into the remaining ciphertext,
we will be able to guess more letters and the puzzle will begin to unravel.
2.3.3 Definition of Secure.
There are several reasonable definitions of a secure cipher. Lacking a proof that a cipher is secure, we
could require that the best known attack on the system is impractical. While this would seem to be the
most crucial property, we'll use a slightly different definition. We say that a cryptosystem is secure if the
best-known attack requires as much work as an exhaustive key search. In other words, no shortcut attack
is known.
In practice, we must select a cipher that is secure and has a large enough key space so that an exhaustive
key search is impractical. Both factors are necessary when choosing a cipher to protect sensitive data.
2.3.4 Double Transposition Cipher
To encrypt with a double transposition cipher, we first write the plaintext into an array of a given size and
then permute the rows and columns accord ing to specified permutations. For example, suppose we write
the plaintext attackatdawn into a 3 x 4 array:
To decrypt (2.3),
the ciphertext is first
put into a 3 x 4
array. Then the
columns are
numbered as
(4,2,1,3) and
rearranged to
(1,2,3,4), and the
rows are
numbered (3,2,1)
and
rearranged into (1,2,3),
Recovered the plaintext, namely, attackatdawn.
2.3.5 One-time Pad. The one-time pad, which is also known as the Vernam cipher, is a provably secure
cryptosystem. For simplicity, let's consider an alphabet with only eight letters. Our alphabet and the
corresponding binary representation of letters appear in Table 2.1
Suppose to use a one time pad to encrypt the plaintext message heilhitler.
First consult Table 2.1 to convert the plaintext letters to the bit string
h e i l h i t l e r
001 000 010 100 001 010 111 100 000 101.
The one-time pad key consists of a randomly selected string of bits that is the same length as the message.
The key is then XORed with the plaintext to yield the ciphertext,
Decryption is accomplished by XOR-ing the same key with the ciphertext.
Suppose key used is
111 101 110 101 111 100 000 101 110 000
Project VENONA.
The so-called VENONA project provides an interesting example of a real-world use of the one-time pad.
In the 1930s and 1940s, spies from the Soviet Union who entered the United States brought with them
one-time pad keys. When it was time to report back to their handlers in Moscow (capital of Soviet
Union), these spies used their one-time pads to encrypt their messages, which could then be safely sent
back to Moscow. Their messages dealt with the most sensitive U.S. government secrets of the time. In
particular, the development of the first atomic bomb was a focus.
The Soviet spies were well trained and never reused the key, yet many of the intercepted ciphertext
messages were eventually decrypted by American cryptanalysts. How can that be, given that the one-time
pad is provably secure? In fact, there was a flaw in the method used to generate the pads, so that, in effect,
long stretches of the keys were repeated.
Codebook Cipher:
A classic codebook cipher is, literally, a dictionary-like book containing (plain text) words and their
corresponding (ciphertext) codewords. To encrypt a given word, the cipher clerk would simply look up
the word in the codebook and replace it with the corresponding codeword. Decryption, using the in verse
codebook, was equally straightforward. Table 2.3 contains an excerpt from a famous codebook used by
Germany during World War I.
To encrypt the German word Februar, the entire word would be replaced with the 5-digit codeword
13605. This codebook was used for encryption, while the corresponding in verse codebook, arranged with
the 5-digit codewords in numerical order, was used for decryption. A codebook is a form of a substitution
cipher.
During World War I in 1917, the German Foreign Minister, Arthur Zimmermann, sent an encrypted
telegram to the German ambassador in Mexico City. The ciphertext message, which appears in Figure 2.4
, was seized by the British. At the time, the British and French were at war with Germany, but the U.S.
was neutral .
The British had got a part of the German code book, through meticulous analyses, the British were able to
fill in the gaps in the codebook and they could decrypt it. The telegram stated that the German
government was planning to begin unrestricted submarine warfare and had concluded that this would
likely lead to war with the United States. As a result, Zimmermann told his ambassador that Germany
should try to recruit Mexico as an ally to fight against the United States. Germans concluded that their
codebook had not been compromised and continued to use it for sensitive messages throughout the war.
The security of a classic codebook cipher depends primarily on the physical security of the book itself.
That is, the book must be protected from capture by the enemy. In addition, statistical attacks analogous
to those used to break a simple When the Zimmermann telegram was released in the U.S., public opinion
turned against Germany the U.S. declared war.
The British were initially hesitant to release the Zimmermann telegram since they feared that the Germans
would realize that their cipher was broken and, presumably, stop using it.
code books needed to be periodically replaced with new codebooks. Since this was an expensive and
risky process, techniques were developed to extend the life of a codebook. To accomplish this, a so-called
additive was generally used.
Ciphers of the Election of 1876.
The U.S. presidential election of 1876 was a virtual dead heat. The contestants in the election were B.
Hayes and Tilden. Tilden had obtained a slight plurality of the popular vote, but it is the Electoral College
that determines the winner of the presidency. In the Electoral College, each state sends a delegation and
for almost every state, the entire delegation is supposed to vote for the candidate who received the
largest number of votes in that particular state. In 1876, the electoral college delegations of four states
were in dispute, The commission decided that all four states should go to Hayes and he became
president of the United States. Tilden's supporters immediately charged that Hayes' people had bribed
officials to turn the vote in his favor, but no evidence was forthcoming. Some months after the election,
reporters discovered a large number of encrypted messages that had been sent from Tilden's supporters
to officials in the disputed states. One of the ciphers used was a partial codebook together with a
transposition on the words.
The codebook was only applied to im portant words and the transposition was a fixed permutation for
all messages of a given length. The allowed message lengths were 10, 15, 20, 25, and 30 words,
The permutation used for a message of 10 words was 9,3,6,1,10,5,2,7,4,8.
One actual ciphertext message was “Warsaw they read all unchanged last are idiots can't situation”
which was decrypted by undoing the permutation and substituting telegram for Warsaw to obtain
Can't read last telegram. Situation unchanged. They are all idiots.
Modern Crypto History.
Taxonomy of Cryptography.
Broad categories of ciphers: Symmetric ciphers, Public key cryptosystems, and Hash functions.
1) Symmetric cipher: can be subdivided into stream ciphers and block ciphers.
Stream ciphers : example -one-time pad.
Stream ciphers are usually most efficient in hardware.
Block ciphers: example- classic codebooks,
Block ciphers are easier to optimize for software implementations,
2) Public key crypto, Encryption keys can be made public. For each public key, there is a
corresponding decryption key that is known as a private key it must remain private.
Suppose a message is "encrypted" with the private key, Since the public key is public, anyone
can decrypt this message. it can serve as a digital form of a handwritten signature—anyone can
verify the signature, but only the signer could have created the signature.
Symmetric key crypto is orders of magnitude faster than public key. As a result, symmetric
crypto is used to encrypt the vast majority of data today.
Public key crypto has several critical roles to play in modern information security.
3) Cryptographic hash functions.
These functions take an input of any size and produce an output of a fixed size.
if the input changes in one or more bits, the output should change in about half of its
bits.
It is computationally infeasible to find any two inputs that hash to the same output.
Taxonomy of Cryptanalysis.
ciphertext only attack
known plain text.
chosen plaintext attack.
lunchtime attack
adaptively chosen plaintext attack
Related key attacks