密码学基础
(Foundation of Cryptography)
李发根
(Fagen Li)
E-mail:fagenli@[Link]
Homework 10%
Quiz 10%
Final 80%
Textbook.
Cryptography: An Introduction (3rd Edition)
Nigel Smart
Chapter 3 ： Historical Ciphers
Chapter 1 and Chapter 2 are mathematical
foundation of information security, we do
not discuss it in this course
Outline
Introduction a number of historical ciphers.
To show a number of attack techniques, such as
chosen plaintext attacks.
The basic cipher components: substitution and
permutation
Secure Communication Model
Oscar
Alice
Bob
x y
Encrypt Decrypt
K K
Secret Key Secret Channel
K
Introduction
A cryptosystem is a 5-tuple (E,D,M,K,C),where
M — a set of plaintexts;
K — a set of keys;
C — a set of ciphertexts;
E — a set of encryption algorithm;
D — a set of decryption algorithm;
Encryption : C = Ek(M)
Decryption : M= Dk(C)
Note : M = Dk(C) = Dk(Ek(M))
Shift Cipher
Define : Encryption is performed by replacing
each letter by the letter a certain number of
places on in the alphabet.
More formally:
Encrypt(Letter, Key) = (Letter + Key) (mod 26)
Decrypt(Letter, Key) = (Letter － Key) (mod 26)
For example: (where Key = 3)
Shift Cipher
plaintext letter: ABCDEF...UVWXYZ
ciphtertext letter: DEF...UVWXYZABC
Shift Cipher
• P=C=K=Z26.
• Encrypt ： Ek(x)=x+k mod 26
• Decrypt ： Dk(c)=c-k mod 26
Plaintext WEAREINCRYPTOCLASS.
+10
=Ciphertext
GOKBOSXMBIZDYMWCC
-10
=Plaintext
WEAREINCRYPTOCLASS
Affine Cipher
• P=C=Z26. K=Z262
• Encrypt ： E(a,b)(x)=ax+b mod 26
Condition ： gcd(a, 26)=1. Why ？
• Decrypt ： D(a,b)(c)=(c-b)a-1 mod 26
Plaintext WEAREINCRYPTOCLASS.
K=(3, 4)
Ciphertext SQEDQCRKDYXJUKLEGG
K=(3, 4)
WEAREINCRYPTOCLASS
Plaintext
Shift Cipher
Attack:
1 、 brute force
There are only 26 possible keys.
2 、 statistical technique
using the statistics of the underlying
language
Note :When this cipher is used with the key
three, it is often called the Caesar cipher.
Substitution Cipher
Each letter gets mapped to another letter
For Example:
Plaintext alphabet ABCDEFGHI J K LMNOP QRSTUVWXYZ
Ciphertext alphabet GOYDSI P ELUAV C RJWXZNHBQ FTMK
Hence, the plaintext word HELLO would
encrypt to the ciphertext ESVVJ if we used the
substitution given above.
Key space: 26!
Z q*
Substitution Cipher
Attack steps:
Firstly, let’s compute frequencies for single
letters in the ciphertext;
Secondly,we should find that the most common
letter which occurs as a single ciphertext letter
in the ciphertext;
After analysis,we can obtain the plaintext
correspondding to the ciphertext.
Vigenère Cipher
Polyalphabetic substitution cipher : which have a
number of substitution alphabets and then
encrypt each letter with a different alphabet.
Shortcoming: the key is too hard to remember
when have more substitution alphabets.
Vigenère Cipher, invented in 1533 by Giovan
Batista Belaso,was a variant of polyalphabetic
substitution cipher, but the key was easy to
remember.
Vigenère Cipher
The secret key is a short sequence of letters
which is repeated again and again to form a
keystream. For example, the key is SESAME,
encryption works as follows:
Plaintext TH I S I S A T E S T ME S S AG E
⊕
Key SE SAME S E S AM E S E S AME
Ciphertext LLAS UWS XWS F QWWKA S I
we notice that A will encrypt to a different letter
depending on where it appears in the message.
Vigenère Cipher
Attack :
Vigenère cipher is still easy to break using the
underlying statistics of English.
Firstly, we have found the length of the
keyword;
Then, breaking the ciphertext is the same as
breaking the shift cipher;
Permutation Cipher
Permutation Cipher is to rearrange letters
instead of substituting them.
Here we just use a permutation δ∈ Sn. Sn
is a permutation group.
For example:
1 2 3 4 5
δ= = (1243) = S5
2 4 1 3 5
Permutation Cipher
1. Firstly we take some plaintext: Once upon a time there
was a little girl called snow white.
2. We break the text into chunks of 5 letters, then we
swap the letters around according to our secret
permutation δ.
3. We will obtain the ciphertext as follows:
coenu npaot eitmh eewra lsiat etgli crall dlsdn wohwi
atheb.
Attack:we can break a permutation cipher is easy with
a chosen plaintext attack.
Cryptanalysis ： Attacks
• Goal ： Compute the secret key k.
Ciphertext only attack ： Given ciphertext C, find the
secret key k, so that Dk(C) =M is the correct plaintext.
Known plaintext attack ： Given C and its plaintext M,
find the secret key k, so that Dk(C) =M.
Chosen plaintext attack ： Attacker can choose any
plaintext M ， for which she can obtain the corresponding
ciphertext C 。 Then ， the attacker needs to find the secret key
k, so that Dk(C) =M. Here the attacker may request many
plaintext/ciphertext pairs. Notice that in the known plaintext
attack, the attacker has no right to choose the plaintext of his
choices. Here she might choose the plaintext so that the 19
provided the ciphertext allow her to easily derive the secret
Chosen ciphertext attack:The attacker can choose any
ciphertext C ， then she can ask to get the corresponding
plaintext M 。 Then, she is required to find the secret key k, so
that Dk(C) =M. Here the attacker may ask many pairs
ciphertext/plaintext.
20
Frequencies of Letters
21
Cyptanalysis by Frequency: Affine Cipher
• Encryption ： C=aX+b, （ a, b) is the secret key 。
• The frequency of X is plaintext space is identical to that
of C in the ciphertext space.
• Ciphertext ：
FMVEDKAPHFERBNDKRXRSREFMORUDSDKDVSHV
UFEDKAPRKDLYEVLRHHRH
• Brute Force Search of (a, b) needs 26*26=676 times 。
• Frequency ： R ， 8times ； D ， 7times ；
E ， H ， K ， each 5times ；
F ， S, V, each 4times;
• Guess: R is the ciphertext of e; D is cipher of t, so
4a+b=17, 19a+b=3. so, a=6, b=19. As gcd(6, 26)=2, (6, 19)22
is impossible.
•Guess: e - R; t- E, so
4a+b=17, 19a+b=4. so, a=13. As gcd(13, 26)=13, a=13, impossible.
•Guess: e R; tH, so
4a+b=17, 19a+b=7. so, a=8. As gcd(8, 26)=2, a=8, impossible.
•Guess: eR; tK,so
4a+b=17, 19a+b=10. so, a=3, b=5. decrypt other ciphertexts gives
algorithms are quite general definitions of arithmetic processes
Conclusion
1. Statistical technique can break the Historical
Ciphers.
2. Important principles behind early ciphers are
those of substitution and permutation.
3. Ciphers can either work on blocks or keystream.
4. Historical Ciphers turned out to be weaker either
due to design flaw or due to bad key
management.