[컴퓨터보안] Cryptography Techniques

Terminology

• Cryptography(암호학): 메세지를 읽을 수 없도록 만들기 위해서 인코딩하는 기술
• Cryptanalysis(암호해독학): 읽을 수 없는 형태의 메세지를 다시 읽을 수 있는 형태로 디코딩하는 기술
• Cryptology: Cryptography + Cryptanalysis

Plain Text and Cipher Text

• Plain Text(or Clear Text): 쉽게 이해할 수 있는 언어
• Cipher Text: 쉽게 이해할 수 없는 언어
• Plain text is transformed into cipher text to achieve security

---

Substitution Ciphers (치환 암호)

• 특정 글자를 다른 글자로 치환하는 암호화 기술
  • Monoalphabetic cipher (단일문자 암호): plaintext의 한 문자에 대해서 항상 같은 문자로 치환할 수 있는 암호화 기술 (one-to-one 관계)
    • Additive Cipher (덧셈 암호)
  • Polyalphabetic cipher (다중문자 암호): 하나의 문자가 여러 다른 문자로 치환할 수 있는 암호화 기술 (one-many)
    • Homophonic Substitution Cipher

Additive Cipher (덧셈 암호)

• 가장 간단한 단일 문자 암호화 기술
• Shift cipher나 Caesar cipher라고도 불림 

Plaintext의 문자를 소문자로, Ciphertext의 문자를 대문자로, 각 알파벳을 나타내는 숫자는 가장 아랫줄에 나타냄. 즉, 알파벳의 순서에 맞추어 각 알파벳을 Z26의 원소에 대응시키는 것

• Encryption (암호화): 원래 문자 값에 key 값을 더해 그에 대응하는 문자로 치환하여 암호를 생성
  • C = (P+K) mod 26
  • 예시) plaintext가 a이고, key 값이 10이라면, a의 치환된 문자는 K가 된다.
• Decription (복호화): 암호화된 문자에서 key를 빼서 원래 plaintext의 문자 도출
  • P = (C-K) mod 26
• The ciphertext is easily decrypted using brute-force attack, patterns of alphabets in the ciphertext, and statistical attack(letter frequency)

예제1) key = 15일 경우, 평문 "hello"를 암호화하라

예제2) key = 15일 경우, 암호문 "WTAAD"를 복호화하라

C-K가 음수일 경우, C에 26을 더해줌

Homophonic Substitution Cipher

• 평문의 각 문자가 하나 이상의 암호 문자로 매핑될 수 있는 암호화 기술
• 암호문의 무작위성을 증가시켜 암호 해독을 어렵게 만들기 때문에 단일 치환 암호보다 안전
• 예시) 평문 'A'는  'D', 'H', 'P', 'R'의 암호 집합 중 하나의 문자로 대체될 수 있음

Polygram Substitution Cipher

• Plaintext 블록을 ciphertext 블록으로 변환하는 블록 단위 암호화 기술
• 비슷한 텍스트 패턴은 완전히 다른 암호문 패턴을 생성할 수 있음

Polyalphabetic Substitution Cipher

• 한 plaintext 문자는 다양한 ciphertext 문자로 치환될 수 있음
• Autokey cipher는 polyalphabetic substitution cipher의 한 유형
  • Autokey cipher에서 key는 stream of subkeys이며, 해당 평문 문자를 암호화하는 데 사용됨

• 예시
  • Alice와 Bob이 초기 키 값 k1 = 12를 사용하여 Autokey cipher를 사용하기로 합의했다고 가정하자. 이제 Alice는 "Attack is today"라는 메시지를 Bob에게 보내려고 한다.
  • Autokey cipher는 문자별로 암호화를 수행하는데, 각 평문 문자를 대응하는 subkey를 사용하여 암호화한다.
  • Autokey  cipher의 작동방식:
    1. 평문 문자를 선택하고, 현재 키 값(k1)을 사용하여 암호화
    2. 암호문을 생성하고, 생성된 암호문 문자를 다음 키 값(k2)으로 저장
    3. 다음 평문 문자를 선택하고, 이전 암호문 문자를 k2로 사용하여 암호화
    4. 이 과정을 반복하여 전체 메시지를 암호화

---

Transposition Ciphers

• 심볼을 서로 바꾸지 않고 심볼들의 위치를 변경하여 암호화하는 방식
• Keyless Transposition Ciphers
  • Rail Fence Technique
  • Simple Columnar Transposition Technique
• Keyed Transposition Ciphers
• combining Two Approaches 

Rail Fence Technique

• The ciphertext is created by reading the pattern row by row.
  1. Write down the plain text message as a sequence of diagonals.
  2. Read the plain text written in step1 as a sequence of rows.
• 예시) To send the message “Meet me at the park” to Bob, Alice writes. She then creates the ciphertext “MEMATEAKETETHPR”.

Simple Columnar Transposition Technique

1. Write the plain text message row-by-row in a rectangle of a pre-defined size.
2. Read the message column-by-column. However, it need not be in the order of columns 1, 2, 3 etc. It can be any random order such as 2, 3, 1, etc.
3. The message thus obtained is the cipher text message.

• 예시1) To send the message “Meet me at the park” to Bob, Alice writes row by row in a table of four columns. She then creates the ciphertext “MMTAEEHREAEKTTP”

• 예시2) Or decide the order of columns as some random order, say 2, 3, 1, 4. Then read the text in the order of these columns. She then creates the ciphertext “EEHREAEKMMTATTP”.

Simple columnar transposition technique with multiple rounds

1. Write the plain text message row-by-row in a rectangle of a pre-defined size.
2. Read the message column-by-column. However, it need not be in the order of columns 1, 2, 3 etc. It can be any random order such as 2, 3, 1, etc. 3.
3. The message thus obtained is the cipher text message of round 1.
4. Repeat steps 1 to 3 as many times as desired.

• 예시1) Original plain text message: Come home tomorrow
  1. Write the plain text message row-by-row in a rectangle with six columns.
  2. Read the message column-by-column in random order, 4, 6, 1, 2, 5, 3.
  3. The cipher text thus obtained would be ‘eowoocmroerhmmto’
  4. Repeat 1 to 3.
  5. Final result is 'oeochemmormorwot'

1번 수행 후의 결과

Simple columnar transposition technique with permutation (순열)

• Permutation of each character in the plaintext into the ciphertext based on the positions.
• 예시) 표의 4개 열에서 두 번째 문자는 암호문에서 다섯 번째 위치로 이동하고, 세 번째 문자는 아홉 번째 위치로 이동한다.
• 이 문자들은 순열을 이루며, 이 순열은 column이 4이기 때문에 4씩 증가한다.
• (01, 05, 09, 13), (02, 06, 10, 14), (03, 07, 11, 15), (04, 08, 12)과 같은 패턴을 형성한다.

Vernam Cipher (One-Time Pad)

• 무작위하게 선택된 반복되지 않는 문자 집합을 입력 암호문으로 사용
• 한 번 사용된 입력 암호문은 다시 사용되지 않으므로 "원타임(One-Time)"이라는 이름임
• 동작 단계
  1. 각 평문 알파벳을 증가하는 순서의 번호로 처리. 예를 들어, A = 0, B = 1, ..., Z = 25와 같이 매핑
  2. 입력 암호문의 각 문자에 대해 동일한 작업을 수행
  3. 각 평문 알파벳에 해당하는 번호를 해당 입력 암호문 알파벳 번호에 더함
  4. 이렇게 생성된 합계가 26을 초과하는 경우, 26을 뺌 (모듈로 연산을 수행)
  5. 합계의 각 숫자를 해당 알파벳으로 다시 번역하여 출력 암호문을 얻음

Keyed Transposition Ciphers

• 키를 사용하여 암호화 프로세스를 제어하는 방식
• plaintext를 일정한 block으로 나누어 나눠진 block을 특정한 규칙에 맞게 글자간 순서를 변경하는 것. 즉, permutation을 수행함
• 예시) Encryt "Enemy attacks tonight"
  • Encryption
    • Block의 크기: 5, block의 permutation key: 31452
    • 아래 key 표를 통해 각 block에서 3번째 글자를 1번째로 쓰고, 1번째 글자를 2번째로, 4번째 글자를 3번째로 쓰면서 암호화
    • Ciphertext: EEMYNTAACKTKONSHITZG
  • Decryption
    • 아래 key 표에서 두번째 row로 permutation되어있는 ciphertext를 다시 첫번째 row의 키를 사용하여 1번째 글자를 3번째로, 2번째 글자를 1번째로, 3번째 글자를 4번째로 복호화

Combining Two Approaches

• Keyless transposition ciphers + Keyed transposition ciphers
• Keyless Transpositon Cipher의 Table의 Column을 결정해 Table을 생성한 뒤, Table Column간에 Keyed Transposition Cipher의 Key를 통해서 Permutation을 함
• 예시) Encryt "Enemy attacks tonight"
  • Encryption
    • Block의 크기: 5, column 수(=block 크기): 5, block의 permutation key: 31452
    • 완성된 Table에서 31452 Key를 이용해 Column간 순서를 Permute하고, Column by Column 순서로 읽으면 됨
    • Ciphertext: ETTHEAKIMAOTYCNXNTSG
  • Decryption
    •  Column by Column 순서로 Table에 Ciphertext를 채워넣고, 암호문 순서인 12345를 평문 순서인 31452로 Table의 Column을 Permute하고, 완성된 Table을 Row by Row로 읽으면 Plaintext를 완성할 수 있음

---

Symmetric and Asymmetric Key Cryptography

• 암호화의 안전한 사용을 위한 2가지 요구사항
  • Strong Encryption Algorithm
  • Secret Key known only to sender / receiver
  • 수학적 표현
    • Y: 암호화된 메시지, X: 평문 메시지, K: 비밀 키
    • Y = E(K, X) : 암호화
    • X = D(K, Y) : 복호화
• Kerckhoff’s Principle
  • 암호 시스템이 비밀 키를 제외한 모든 것에 대해 공개 정보로 여겨져도 안전해야 한다는 원칙
  • 즉, 공격자가 암호화 및 복호화 알고리즘을 알고 있다고 가정하며, 암호화의 안전성은 키의 비밀성에만 의존함
• Characteristics of Cryptographic Systems
  • 사용된 암호화 작업 유형
    • Substitution
    • Transposition
    • Product: Multi stages of substitutions and transpositions
  • 사용된 키 수
    • Single-key or secret → Symmetric key
    • Two-key or public → Asymmetric key
  • 평문 처리 방식
    • Block
    • Stream
• Symmetric Key Cryptography
  • Also known as secret key algorithm
  • Use single key on encrypt and decrypt
  • Usually hardware assisted
• Asymmetric Key Cryptography
  • Also known as public-key algorithms
  • Pair of keys (i.e. private and public)
    • Key management is relatively easy
  • Computational intensive
    • Slow (100 times slower than symmetric algorithms of similar strengths!!)
  • Many new algorithms are developed recently
• Key Range and Key Size
  • 암호화 및 복호화 알고리즘은 일반적으로 공개 정보라 공격자가 암호화 및 복호화 알고리즘을 알고 있을 가능성이 높음
  • 따라서 공격자는 무작위로 가능한 모든 키를 시도하여 암호문을 해독하는 Brute-force attack을 시도할 수 있음
  • 키의 길이가 클수록  Brute-force attack이 어려워짐
  • 일반적으로 64, 128, 256 비트와 같은 긴 키가 사용됨
• Possible Types of Attacks