Cryptography and Network Security-Ch5

Chapter 5 Introduction to Modern Symmetric-key Ciphers

5.1 Modern Block Cipher
●modern block cipher分為兩種：transposition cipher 和 substitution cipher
  ○transposition cipher：key長度為⌈log₂ n!⌉  bit
     (n!種對應)
  ○substitution cipher：key長度為⌈log₂ (2ⁿ)!⌉ bit
     (2ⁿ!種對應)

●P-boxes：transposes bits
  ○Straight P-box：input bit = output bit
  ○Compression P-box：input bit > output bit
  ○Expansion P-box：input bit < output bit
     只有Straight P-box為可逆

e.g.
input: a b c d e f g h
P-box: [4 1 2 3 6 7 8 5]
output: d a b c f g h e
  ○invert P-boxes：
     1. 加index
     2. 將內容和index交換
     3.以index做sort

e.g.
1. original： [6 3 4 5 2 1]
2. Add index：[6 3 4 5 2 1]
                          1 2 3 4 5 6
3. Swap index和content：[1 2 3 4 5 6]
                                            6 3 4 5 2 1
4. 根據index做sort：[6 5 2 3 4 1]
                                    1 2 3 4 5 6

●S-boxes： m x n substitution unit
e.g.
y₁ = x₁ + x₂ + x₃
y₂ = x₁

●operation：
  ○XOR
  ○circular shift
  ○swap：circular shift n/2
  ○split and combine

●diffusion：將plaintext 和 ciphertext 的關係藏起

●confusion：將ciphertext和key的關係藏起

●product cipher：a complex cipher 結合substitution, permutation ... other components
  modern block cipher 都是product cipher
  可分為兩種：
  ○Feistel cipher
  ○non-Feistel cipher



5.2modern stream cipher：
●synchronous stream cipher：key和plaintext或ciphertext無關
  ○Feedback shift register(FSR)：產生key
   e.g.
     b₄  =  b₁+ b₀

→LFSR產生的key為pseudo random（有cycle，最大cycle為2^m-1，m為cell數量）
→可以用polynomial 去表示
e.g.   b₄ = b₁ + b₀
可用 x⁴ + x +1  表示

●non-synchronous stream cipher：每一個key stream 裡的key均depend on先前的plaintext或ciphertext

Cryptography and Network Security-Ch4

Mathematics of cryptography Part 2: Algebraic Structure

4.1 Algebraic Structure
●five property:
   ●closure (封閉性)
   ●associativity (結合性)
   ●commutativity (交換性)
   ●existence of identity：和任意element 做運算，結果＝那個element。e.g.：加法下的0
   ●existence of inverse：自己和inverse做運算，結果＝ identity
 1. Groups: set of element + operation   (滿足property 1 2 4 5)
    e.g. G = <Zn, +>
   ●Abelian group：滿足交換性
   ●subgroup：subgroup裡的element均屬於group，operation 結果也相同
   ●cyclic subgroup：可以用element的power產生出來
 

※Lagrange' s theorem：H是G的subgroup，
order of H 是order of G的因數
 ●order of a group：產生cycle的最高項
  e.g. G = <Z10*, x>
    ord(1) = 1
    ord(3) = 4
    ord(7) = 4
    ord(9) = 2
  group order：2


  2. Rings：R = <{}, ├, ┤>
     {}為set
     ├ 為operation 1 滿足property 1 2 4 5
     ┤ 為operation 2 滿足property 1 2


  3. Fields：F = <{}, ├, ┤>
     {}為set
     ├ 為operation 1 滿足property 1 2 4 5
     ┤ 為operation 2 滿足property 1 2 3 4 5
    (├的identity 在┤不可有inverse)
  ●Galois Field：GF(p ^n)
    p is prime



4.2 GF(2^n) fields
  ●可以用n-1 degree 的polynomial 表示
   f(x) = a_n-1 x^n-1  + a _n-2 x^n-2+...+a₀x⁰
   e.g. GF(2²)：f(x) = 1x + 0
                                    0      0
                                    0      1
                                    1      1
  ●addition = subtraction = bit-wise XOR
  ●multiplication：相乘結果需用modulus polynomial (irreducible polynomial)去reduce (除以irreducible polynomial取餘數)
  ●inverse of polynomial：
    利用Euclidean algorithm 或將所有table generate出來
    e.g. inverse of x5 modulo x8 + x4 + x3 + x + 1

  ●相乘algorithm：
    e.g. P1 = 000100110, P2 = 10011110, modulus = 100011010

    P2每次向左shift一次
    當上次結果最高位為1時再和modulus做XOR(較低8位)
,   最後將P1為1的那一個結果做XOR (圖中話底線的)
 
 

  ●利用generator 去定義elements of GF(2ⁿ)
{0, g⁰, g¹, g², ..., g^N}, where N = 2ⁿ-2

匈牙利命名法

命名方式：<scope>_<prefix>_<qualifier>

◎scope前綴：
 ●g：全域變數
 ●m：成員變數
 ●l：區域變數

◎prefix前綴與type：
 ●ch：char
 ●b：bool
 ●n：int
 ●n：unsigned int
 ●w：word
 ●l：long
 ●p：*
 ●st：struct

Cryptography and Network Security-Ch3

Chapter3 traditional symmetric-key cipher

<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

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 13^th 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 (N² -1)(N² - 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.
29⁴ = 707281
b.
 (29² -1)(29² - 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