[컴퓨터 보안] Classical Encryption Techniques

Definitions

• Plaintext
  • 암호화하려는 대상(숨기려는 대상)
• Ciphertext (암호문)
  • 암호화가 된 결과물
  • 그냥 봐서는 내용을 알아볼 수 없다
• Enciphering/encryption (암호화)
  • plaintext를 ciphertext로 변환하는 과정
• Deciphering/decryption (복호화)
  • ciphertext로부터 plaintext를 복구하는 것
• Cryptography
  • 암호화 기술을 연구하는 학문
• Cryptographic system/cipher
  • 암호화하는 알고리즘, 논리
• Cryptanalysis
  • 암호화된 것들을 공격하는 것
  • enciphering 지식이 없이 메시지를 deciphering하는 데 사용되는 기술
  • 예: Ciphertext로부터 plaintext를 얻거나, 암호화할 때 사용한 key를 알아냄
• Cryptology
  • cryptography와 cryptanalysis를 합친 영역

 

 

Symmetric Cipher Model

-> 암호화하는 key와 복호화하는 key가 동일한 모델

 

• 암호화를 안전하게 사용하기 위해서는 두 가지 조건이 있다.
  • 강한 암호화 알고리즘
    • 다른 사람이 암호문을 보고 쉽게 이해하면 안됨.
  • 암호 메시지를 보내고 받는 사람이 안전하게 secret key를 공유해야 한다.

 

 

Substitution Technique

• Plaintext를 다른 문자나 숫자로 치환하여 ciphertext를 만드는 기술
• 만약 plaintext가 bit sequence였다면 다른 bit pattern으로 치환

 

Caesar Cipher

• substitution cipher의 가장 간단하고 쉬운 사용
• 글자를 치환하는데, 그 규칙이 매우 단순함
• 예:

• a -> D, b-> E, c->F, ..., z->C
  • 이렇게 3칸 뒤에 문자로 치환함.
  • 보통 plaintext는 소문자로, ciphertext는 대문자로 작성한다.
• 즉, 다음과 같이 정의할 수 있다.
  • c = E(3, p) = (p+3) mod 26
• 일반화하면 다음과 같다.
  • c = E(k, p) = (p+k) mod 26
  • k: secret key
  • 여기서 k를 3으로 고정한 알고리즘을 Caesar Cipher라고 하고
  • k를 임의의 수로 쓰는 것을 Shift Cipher라고 한다.
• k의 범위는 [0, 25]로 경우의 수가 적기 때문에 들키기 쉽다.

 

 

Monoalphabetic Cipher

• : key가 정해져 있을 때, 어떤 한 글자는 항상 같은 글자로 치환된다.
• Permutation Cipher
  
  • plaintext의 문자 a, b, c, ..., z가 문자들이 임의의 순열로 매칭 된다.
  • key(순열)가 나올 수 있는 경우의 수는 26!
• permutation cipher처럼 경우의 수가 많아 보여도 깨지기 쉽다.
  • 각 문자들이 사용되는 빈도로 매칭을 쉽게 유추할 수 있기 때문이다.
  • 보통 e, t, a가 많이 쓰인다. 그렇다면 ciphertext에서 가장 많이 쓰인 문자 몇 개를 e, t, a라고 가정하고 key를 유추해나갈 수 있다.
  • Digram
    • 두 문자의 조합
    • th를 많이 쓴다.
  • Trigram
    • 세 문자의 조합
    • the를 많이 쓴다.
  • 문제점:
    1. 같은 문자는 항상 같은 문자로 바뀐다.
    2. th, the처럼 짝지어 나오는 문자가 많다.
• 공격을 막으려면 어떻게 해야 할까? (대응책)
  • 통계적인 정보를 없애자!!
    • 문자를 묶어서 변환하자. plaintext를 덩어리로 나눠서 변환하자
    • 같은 문자도 상황에 따라 다른 문자로 치환되게 하자

 

 

Playfair Cipher

-> 첫 번째 대응책

• Symmetric Cipher이다.
• 주로 두 글자를 다른 두 글자로 치환 
• keyword를 사용해서 key를 구성하며, 5x5 행렬을 사용한다.
• Playfair Cipher의 규칙:
  • keyword가 MONARCHY라고 하자.
  • 먼저 5x5 행렬을 채워야 한다.
    1. keyword를 순서대로 먼저 채운다.
    2. 그 이후는 A~Z순으로 순서대로 채우는데, keyword에 포함된 문자는 생략하고 채워나간다.
    3. 이렇게 하면, 한 칸이 모자라다. 그래서 어떤 두 문자를 같은 칸에 넣어야 하기 때문에 I와 J를 같은 칸에 넣어준다.

• Playfair Cipher에서 plaintext를 변환하는 규칙:
  • 규칙 1.
    • ex) ba ll oo n
    • 두 글자씩 나누다 보면 위 예시처럼 같은 문자 두 개가 묶을 수 있다(ll, oo)
    • 이때, filer(x)를 채워 같은 문자가 묶이지 않도록 한다.
    • -> ba lx lo on
  • 규칙 2.
    • ex) ar -> RM
    • 두 글자가 같은 행상에 있으면 각각 오른쪽 글자로 치환한다. 
    • 행에서 순환 r->M
  • 규칙 3.
    • ex) mu -> cm
    • 두 글자가 같은 열에 있으면 각각 밑 글자로 치환
    • 열에서 순환 u->M
  • 규칙 4.
    • ex1) hs -> BP 
    • ex2) ea -> IM or JM
    • 두 글자를 꼭짓점으로 하는 직사각형을 찾는다. 각 문자를 그 직사각형의 나머지 꼭지점으로 치환한다.
      • 이때, 각 문자는 같은 행에 있는 문자로 치환된다.
• 이렇게 변환하다 보면, filer(x)가 추가되거나 I/J 둘 중 어떤 것으로 변환되었는지 모르는 문제가 있을 수 있다.
  • 이 경우, 문맥을 보고 판단해야 한다.

 

 

• 좌측의 그래프는 해당 문자열에서 각 문자들의 빈도를 나타낸 것이다.

 

• Playfair를 사용함으로써 일반적인 문자열보다 빈도 차가 줄어든 모습을 볼 수 있다.

 

 

 

 

 

 

 

Polyalphabetic Cipher

-> 두 번째 대응책

• 단순한 monoalphabetic 기술의 업그레이드 버전
• 한 글자씩 대응하되, 대응 규칙을 여러 개 사용한다.

 

 

Vigenere Cipher

• 간단한 polyalphabetic Cipher로 알려진 방법
• 26개의 Caesar Cipher를 사용하는 느낌
• 메시지를 암호화하려면, 메시지(plaintext)와 동일한 길이의 key가 필요하다.
  • 보통, key는 keyword를 반복해서 사용한다.
• 예: keyword가 "deceptive"

• 변환될 문자 = ( p + k ) mod 26
  • p: plaintext의 문자
  • k: keyword의 사이클에 따라 다름 
  • 예: plaintext의 맨 처음 글자는 w이다. key에서 같은 위치에 있는 문자는 d이다. d는 3(a가 0)이므로 k는 3이 된다. 결과적으로, 변환될 문자는 w에서 3칸 다음에 나오는 문자인 Z가 된다.
• Vigenere Cipher는 안전한가?
  • 문제점: key라는 유한한 것을 사이클에 두고 반복해서 사용한다.
    • 이 경우, plaintext에서 특정 글자들과, keyword의 사이클이 우연히 맞아떨어질 수 있다.
    • 예:
      • keyword 길이: 9
      • plaintext에서 "red" 사이의 거리: 9
      • cipherText에서도 다음처럼(VTW) 반복될 수 있다.

• Vigenere Cipher 공격 방법
  1. Cycle 길이 알아내기 -> 길이를 추측하는 것
  2. Cycle 길이에 따른 통계 분석
     1. 가정한 cycle 길이로 ciphertext를 자르기
     2. 각 cycle의 앞 문자들을 모은다. -> 집합으로 묶음. 예: {Z, R, H}
     3. 이 집합으로 통계를 낸다.

 

 

Vigenere Autokey System

• keyword 뒤에 plaintext를 붙인 문자열을 key로 사용한다.
• 예:

• 이렇게 해도, keyword와 plaintext에서 자주 나오는 문자들을 통계적으로 찾을 수 있다 ㅠㅠ

 

 

Vernam Cipher

• 알파벳을 그대로 사용하지 않고, bit sequence로 변환하여 사용한다. 그리고, 이 bit sequence와 keyword에 해당하는 다른 bit sequence와 XOR 시켜서 ciphertext를 구한다.
• 일부 key 반복해서 사용
• 하나의 문자가 bit sequence로 변환되면 길이가 길어진다. 
  • 즉, key stream cycle의 길이를 길게 만들 수 있다.
• [(p+k) mod 2]라고 말할 수 있는데, 이는 p XOR k와 같다.
• [p = (p XOR k) XOR k] 이 성질을 이용해 암호문을 복호화할 수 있다.
• Encryption: $p_i$ XOR $k_i$ = $c_i$
• Decryption: $c_i$ XOR $k_i$ = $p_i$

 

 

One-Time Pad

• Plaintext 길이와 동일한 길이의 key stream을 만들어 cycle을 없애자. 
• 즉, keyword를 반복하는 것이 아니라 plaintext 길이의 랜덤한 key를 만들자.
• 이렇게 하면, 통계적인 반복을 사용할 수 없어, 공격이 불가능하다. (unbreakable)
• One-Time Pad의 문제점:
  • 긴 랜덤한 키를 안전하게 공유하기 힘들다.
  • plaintext와 동일한 길이의 키를 안전하게 수신자와 공유할 방법이 있다면, 암호화 안 하고 처음부터 거기로 메시지(plaintext)를 보내면 된다.
  • 즉, 실용적이지 않다.
• One-Time Pad를 사용하는 경우:
  • 전송 양이 적지만 굉장히 안전하게 전송해야 하는 경우
• One-Time Pad는 완벽하게 비밀이 지켜지는 유일한 암호 시스템이다! (실용적이지 않을 뿐...)

 

 

Transposition Cipher

Rail Transposition Cipher

• 가장 간단한 transposition cipher
• Cyphertext: plaintext를 대각선으로 쓰고 가로로 읽는다. 
• 예: 
  • plaintext: "meet me after the toga party"
  • depth: 2

 

Row Transposition Cipher

• 길이에 맞춰 가로로 순서대로 plaintext를 쓴다.(직사각형 모양) 세로로 읽는 순서(순열)가 key로 주어진다.
• 암호문: key에 작성된 순서대로 해당 열을 읽는다.
• 예:

 

 

 

 

 

Steganography vs Encryption

• Steganography:
  • '숨기려는 데이터'의 존재 자체를 숨김
• Encryption
  • 데이터의 존재 자체는 밝혀지나, 해당 데이터가 암호화되어 있어서 다른 사람이 알아볼 수 없다.

 

 

 

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]