<3.1> Introduction
名詞解釋
ciphertext：密文
plaintext：明文
encryption(加密)： C = Ek(P)
decryption(解密)： P = Dk(C)
cryptography：create secret code的科學
cryptanalysis：break codes的科學
1. ciphertext-only attack：只知道密文
2. known-plaintext attack：有歷史密文明文對，但不能選擇
3. chosen-plaintext attack：有密文，可以選擇明文
4. chosen-ciphertext attack：有密文，可以選擇密文
※Kerckhoff's principle：
(假設adversary 知道encryption/ decryption algorithm)
防止cipher attack只能根據key的secrecy
<3.2>substitution cipher
1. monoalphabetic cipher：明文中相同的符號只有一種對應
(e.g. 所有b -> a)
(1).additive cipher(shift cipher)：C = P + K
※frequency analysis：計算密文中的字元或字串出現次數，猜測對應的明文
(2)multiplication cipher：C = P * K
P = C * K^(-1)
(3)Affine cipher：先用key1做乘法，再用key2做加法
C = P * k1 + k2
(4)自己定義對應
2. polyalphabetic cipher：明文中相同字母會有不同密文
(1). auto key：key 為前一位的明文
Ci = Pi + Ki
Pi = Ci - Ki
ki = (k, P1, P2, P3, ...)
(2) play fair：
| L | G | D | B | A |
| Q | M | H | E | C |
| U | R | N | I/J | F |
| X | V | S | O | K |
| Z | Y | W | T | P |
同行：右移
同列：下移
不同行不同列：對角
e.g he -> EC
lx -> QZ
lo -> BX
(3)Vigenere cipher：Ci = Pi + k
(m組 additive) Pi = Ci - k
k = [(k1, k2, ,kn), (k1, k2, ,kn), ...]
e.g. PASCALPASCALPA...
(4) Hill cipher：use matrix
C = P * K
P = C * K ^ (-1)
(5) one time pad：key 為 random
(6) rotor cipher：rotor轉一次有新的substitution
(7) Enigma machine：
<3.3>transposition cipher：
1. keyless transposition：
(1) 類似rail fence：分兩行寫
明文：meet me at the...
m e a h...
e t t e
密文：
meah....ette
(2) write row by row, transfer column by coulmn
2. keyed transposition：將plaintext分為groups，用key去排列字元
e.g. 3 1 2
3表示原本的位子為3
所以 abc -> cab
※key inversion in transposition cipher：將index寫出來，根據原陣列做sorting，新的index陣列極為inversion
e.g
2 6 3 1 4 7 5 (key)
1 2 3 4 5 6 7 (index)
↓
1 2 3 4 5 6 7
4 1 3 5 7 2 6
inversion為4 1 3 5 7 2 6
※可以用matrix表達過程
※兩次transposition 和一次transposition效果一樣
<3.4>
※stream cipher：一個plaintext即可對應出一個ciphertext
※block cipher：需等一個block才可加密(e.g. play fair)
練習題：
1.
In each of the
following ciphers, what is the maximum number of characters that will be
changed in the ciphertext if only a single character is changed in the
plaintext?
a.
Additive
b.
Multiplicative
c.
Affine
d.
Vigenere
e.
Auto-key
f.
One-time pad
g.
Rotor
h. Enigma
h. Enigma
2. Use a brute-force
attack to decipher the following message enciphered by Alice using an additive
cipher. Suppose that Alice always uses a key that is close to her birthday,
which is on the 13th of the month:
NCJAEZRCLASJLYODEPRLYZRCLASJLCPEHZDTOPDZQLNZTY
3.
Use a one-letter
frequency attack to decipher the following message. Assume that you know it is
enciphered using monoalphabetic substitution cipher.
ONHOVEJHWOBEVGWOCBWHNUGBLHGBGR
4.
Assume that
punctuation marks (periods, question marks, and spaces) are added to the
encryption alphabet of a Hill cipher, then a 2*2 key matrix in Z29 can be used for
encryption and decryption.
a.
Find the total number of possible
matrices.
b.
It has been proved
that the total number of invertible matrices is (N2 -1)(N2 - N), where N is
the number of alphabet size. Find the key domain of a Hill cipher using this
alphabet.
5.
Use a Kasiski test
and single-frequency attack to break the following ciphertext. You know that is
has been created with Vigenere cipher
MPYIGOBSRMIDBSYRDIKATXAILFDFKXTPPSNTTJIGTHDELT
TXAIREIHSVOBSMLUCFIOEPZIWACRFXICUVXVTOPXDLWPENDHPTSI
DDBXWWTZPHNSOCLOUMSNRCCVUUXZHHNWSVXAUHIK
LXTIMOICHTYPBHMHXGXHOLWPEWWWWDALOCTSQZELT
NOTE:五行要分開計算
Ans
1.
a. 1
b. 1
c. 1
d. 1
e. 2
f. 1
g. 1
h. 1
2.
key = 11
ans : cryptography and steganography are two sides of a coin
3.
plaintext： One of the most famous men was Ceasar
4.
a.
294 = 707281
b.
(292 -1)(292 - 29) = 62080
5.
key = a poet
MAKE NO MENTION OF ROUGH TIMES FORGET ABOUT EVENTS PAST
TIME YET TO COME IS UNREVEALED AND BEING REVEALED WILL NOT LAST
DONT DWELL ON DAYS OF YOUR NOR BUILD ON HERE AFTER
LIFE TO TODAY AND THIS TOO WILL WHISK AWAY AS BLAST
可以參考網站：
http://www.richkni.co.uk/php/crypta/freq.php
http://www.counton.org/explorer/codebreaking/frequency-analysis.php
沒有留言:
張貼留言