[정보보호] 암호 기법 종류

※2장: 치환 기법(cont.) - 다른 글자로 바꾸는 것

#Playfair 암호

- 다중 문자 치환 암호 기법(Multiple-Letter Encryption)

    > 단일 문자가 아닌 다중 문자를 암호화 하여 안전도 높임

    > 특정 키워드를 기반으로 하여 5x5 matrix 만듦

    > 해당 키워드를 사용하여 matrix를 채우고 해당 키워드를 구성하는 문자가 아닌 다른 문자로 나머지 공간을 채움

- Ex) 키워드가 Monarchy인 경우:

'

#Playfair 암호화 방법

1. 한 쌍이 반복된 글자라면, 'x'같은 filler를 삽입. ex) "ballooon" -> "ba lx lo on"

2. 두 글자가 같은 행이라면, 오른쪽으로 민다. ex) "ar" -> "RM"

3. 같은 열이라면, 밑으로 민다. ex) "mu" -> "CM"

4. 또는 거울처럼 뒤집기. ex) hs -> bp, ea -> im/jm

 

#Playfair 암호 분석

- 보안 수준: 26 * 26 = 676

- 단일 문자 암호보다 상대적으로 공격 어려움

- 1차 세계대전 및 2차 세계대전 때 사용

 

#Hill 암호

- 동작 원리

    > m개의 평문을 m개의 암호문으로 치환

    > 이때, m개의 선형방정식에 의해 치환됨

    > m=3인 경우 다음과 같은 선형 방정식을 생각할 수 있음

#Hill 암호 알고리즘 예

★Playfair를 Hill암호처럼 일반화 할 수 있을까? 해보자

 

#다중 문자 암호

- 평문에 대해 서로 다른 방식의 단일 문자 치환 기법 사용

- ex: Vigenere 암호 기법

#Vernam 암호(대충 넘어감)

- 암호학적 공격에 안전하기 위해선 평문과 동일한 길이의 키를 가져야 하며, 평문과 통계적 연관성이 없어야 함

#One Time Pad 암호

- random key사용(반복 없음), 메시지 길이와 동일한 key를 가정함 -> Perfect secrecy

    > Vernam에서는 key 생성시 특정 key를 반복적으로 사용하는 것으로 가정함

- One time pad는 perfect security를 제공하지만, 다음과 같은 문제점

    > 대용량의 random key를 다루기 어려움

    > key 분배 및 보호의 문제

 

＠전치 기법 - 순서를 바꾸는 것

#Rail fence 기법

- 평문을 대각선으로 쓰고 열로 읽음

#Row Transposition 기법

- 열 순으로 읽으면서, 열의 순서를 바꿈(열의 순서: 키)

#Rotor machine

- 2차대전때 사용

- 가변적 치환 기법

- 다수의 실린더로 구성, 각 실린더는 한 문자에 대한 치환을 수행

- 세 개의 실린더 사용시 : 26^3 = 17576개의 다른 알파벳 치환 가능

 

@스테가노그라피

#보안 기술의 범주

- 보안(security): 정보를 보호하는 방법

- 첩보(Intelligence): 정보를 탐지하는 방법

 

#평문 메시지의 은닉 방법

- Steganography 방법: 메시지의 존재 자체를 은폐(워터마크를 숨겨두는 것 등)

- Cryptography 방법: 다양한 원문의 변환에 의해 외부인이 의미를 모르도록 변형

 

#특징

- 메시지의 존재 자체를 은폐

- 원문 내의 단어나 문자를 적절히 발췌하여 조합배열 함으로써 실제 메시지를 나타냄

 

※3장: 블록 암호

#핵심 정리

- 블록 암호는 평문 블록 전체를 가지고 동일한 길이의 암호문 블록을 생성하는 암/복호화 방식

- 많은 블록암호가 Feistel 구조를 띔

    > 동일한 라운드 수로 구성되어 동작

    > 각 라운드는 데이터의 절반이 치환으로 수행, 이후 데이터의 두 개의 반을 교환하는 순열 수행

    > 원본의 키는 확장되어 각 라운드마다 다르게 사용

- DES는 최근까지 가장 널리 사용되는 암호 알고리즘(2000년대) - but 전사적 공격에 약함(56비트이기 때문)

- 차등 암호분석과 선형 암호분석은 암호 분석의 중요한 두 가지 방법

    > DES는 위 두 가지 공격 유형에 매우 강함을 보임

 

#블록 암호의 원리

- 스트림 암호

    > 한 번에 1비트 혹은 1바이트의 디지털 데이터 스트림을 암호화

    > 키 스트림(Ki)은 평문 비트 스트림(Pi)만큼의 길이를 가짐

#블록 암호

- 평문 블록 전체를 가지고 같은 크기의 암호문 블록 생성

- 전형적으로 64비트 또는 128비트를 사용

#Feistel 암호 구조의 동기

- 블록 암호는 n비트 암호문 블록을 생성하기 위해 n비트 평문 블록을 이용해 연산

- 2^n가지의 서로 다른 평문 블록 존재

#n비트-n비트 블록 치환(n=4인 경우)

- 4비트 입력으로 16개 값 중 하나 선택하고, 내부 치환에 의해 16개 출력값 중 하나 대응하여 4비트 출력

#블록 암호의 원리

- 두 개 이상의 기본 암호 연속적 수행(치환, 순열 번갈아)

- 치환: 평문의 각 원소 또는 원소의 그룹을 다른 원소에 매핑

- 순열: 평문 원소의 순서는 순열의 순서대로 재배치

- 확산과 혼돈: 통계적 분석에 기초한 암호 해독 방지(Claude Shannon)

- Shannon: "매우 이상적 암호는 암호문에 대한 모든 통계적 정보가 사용된 키와 독립적이어야 한다"

- 확산: 평문의 통계적 구조가 암호문에 광범위하게 분산(평문과 암호문 관계 복잡), 각 평문 숫자가 다수의 암호문 숫자 값에 영향

- 혼돈: 암호문의 통계적 구조와 암호 키 값 사이의 관계 복잡, 키를 이용한 암호문 생성 방법 복잡(키 추론 어려움)

 

#Feistel 암호 구조

#Feistel 암호 설계 고려사항

1. 빠른 소프트웨어 암/복호화

- 어플리케이션 또는 유틸리티 함수에 내재

- 알고리즘 실행 속도 중요

2. 분석의 용이성

- 암호 해독의 취약성에 대한 알고리즘의 분석이 쉬움

- 고도의 신뢰성과 보안 강도를 위한 개발 용이

 

#설계 특성

1. 블록 크기(64비트)

- 큰 블록은 보안을 강화하지만 암/복호화 속도 저하

- 암/복호 속도를 고려 64비트 일반적

2. 키 크기(128비트)

- 큰 블록은 보안을 강화하지만 암/복호화 속도 저하

- 암/복호 속도를 고려 128비트 일반적(64비트 이하는 해독 용이)

3. 반복 수

- 다중 반복은 보안성 강화

- 16회 반복이 일반적

4. 서브키 생성 알고리즘

- 복잡할수록 강력

5. 반복 함수

- 적용되는 반복함수가 복잡할수록 강력

 

#Feistel 복호 알고리즘

- 암호화와 복호화에 같은 키 사용을 위해 서브키 ki를 역순으로 사용

#DES(Data Encryption Standard)

- 64비트 블럭 암호 알고리즘

- 56비트 키 -> 64비트 중 8비트는 parity check

- 기본 구조

    > round 수: 16

    > 복호화는 암호화의 역순

- 최근에는 DES를 세 개의 키로 세 번 반복 -> 암호 강도 강화 -> Triple-DES

* 완전 최근에는 AES 사용

- 치환과 전치 혼합, 블럭 암호, 관용암호방식

행, 열을 뽑는 규칙이 정해져 있음

-> 해당 표에서는 첫, 마지막 비트가 행(01), 가운데가 열(1101) -> 둘다 0부터 센다

 

#DES의 쇄도효과: 평문 변화

- 평문이나 키의 작은 변화가 암호문에 대해 중요한 변화를 일으키는 효과

- 평문이나 키를 1비트 바꿀 때 암호문의 여러 비트가 변함

-> 1비트 바뀔 때 반정도는 바뀌어야 안전해짐(Avalache effect)

+ 키 변화 ↓

#DES의 강점

1. 56비트 키 사용

- usec당 하나의 암호를 수행하는 장치 백만개로 구성된 병렬기계 구성 -> 평균 탐색시간 10시간으로 축소

2. DES알고리즘 자체 성질을 이용한 해독 가능성

3. 8개의 치환 표 또는 S-box

4. S-box의 경우

- 전체 알고리즘에 대한 설계 기준 공개x

- S-box의 약점에 대해 아는 공격자가 해독할 수 있게 설계됐을 가능성에 대한 의혹 제기

- 수년간 S-box의 수많은 정규성과 예측 못할 동작이 발견

- 그럼에도 S-box에 대해 치명적 약점을 발견한 사람은(적어도 발견이 공개된 적은) 아직 없다.

5. Timing 공격

- 암호문을 복호화 하는데 걸리는 시간을 관측하여 키 또는 평문의 정보 획득

- 입력에 따라 처리시간이 다르다는 것을 이용

- 아직은 성공사례 없으나 흥미로운 연구

 

#차분 및 선형 암호 해독(종류만 알고 있자)

1. 차분 암호 해독(Differential Cryptanalysis)

- DES에 적용해 널리 알려짐

- 2^55 미만의 복잡도로 DES 해독

- 2^47의 선택 평문을 가지고 2^47차수로 DES 해독

2. 선형 암호 해독(Linear Cryptanalysis)

- 2^47 기지 평문으로 해독가능

- 기지 평문이 선택 평문보다 구하기 쉽지만 DES 공격으로서의 선형 암호해독은 가능성 없음

- 선형 암호 해독의 타당성 주장 약함

 

*DES는 지나간 아이돌 -> AES가 대체했음

 

※4장: 정수론의 기본 개념과 유한체

#핵심 정리

- 모듈러 연산은 정수 연산의 한 종류

    > 모든 숫자를 어떤 숫자 n에 대한 하나의 집합으로 단축

- 두 정수의 최대공약수란 두 정수를 나누는 가장 큰 양의 정수

- 유한체 이론은 암호학의 여러 분야에서 매우 중요

    > 유한체: 유한개의 원소를 가지는 체, 유한체의 위수는 n이 양의 정수일 때, 소인수의 멱승인 p^n

 

#가분성과 호제법

#유클리드 호제법(gcd)

- 정수론의 기본 기술 -> 최대공약수 결정 위한 수행 절차

 

#모듈러 연산(법 - the modulus)

- a mod n -> 나머지 구하기(%)

- a mod n = b mod n이면, a ≡ b (mod n) 이라 할 수 있음

    > 이 경우 a, b는 법n에 대해 합동이라 함

    > 만약 a ≡ 0 (mod n)이면, n | a