암호화 기본 - 1

codebook & chiper

code : 어떤 메시지를 암호화하는데 사용하는 방법(단어나 구가 다른 어떤것으로 변환하게 하는 방법)

codebook : 단어나 구절을 암/복호화 하는데 사용하는 문서

cipher : 개별적인 문자, bit 수준에서 메시지 암호화

메세지가 코드에 의해 변환되고 그 뒤 chiper에 의해 변환된다.

chiper : 암호, 암/복호화 시스템/알고리즘

평문 : plaintext, clear text

암호문 : chipertext, cypertogram

Cryptography : 암호기법 (암호화 방법)

Cryptanalysis : 암호해독 (키 없이 복원) => Cryptanalyst (암호문 깸)

Cryptology : 암호학(키로 암/복호화) => Cryptographers (암호문 생성)

Cryptography : 암호기법 (암호화 방법)

메시지를 쉽게 이해할 수 없는 형태로 바꾸고, 다시 원래의 형태로 복원하는 것.

기밀성, 데이터 무결성, 부인방지, 인증을 포함하는 정보보안을 제공하는 수단이나 방법

Symmetric key, Asymmetric key

key => 기밀성, 무결성, 인증 등을 하기위해 사용하는 암호화 알고리즘의 input

키를 안전하게 보관하는 것이 중요 => TPM(trusted platform module), secure co-processor, smartcards...

keyspace

모든 가능한 키들의 집합이다.

keyspace가 크면 안전하지만 bit길이가 길어지고, 그만큼 계산량도 많아진다.

crypto(암호화)

Only the key is secret => 케르크호프스의 원칙

공격자는 시스템에대해 알고 오직 키만 모른다.

암호화 알고리즘은 비밀이 아니며, 오직 키만 비밀이다.

비밀 알고리즘은 노출 되었을때 위험해지고, 언젠가는 노출된다.

따라서 open하여 취약점들을 없앤다.

Substitution(대치,치환)/Transposition(전치(위치를 바꿈))

Substitution(대치, 치환)

1:1 혹은 1:多 대응

하나의 symbol을 또 다른것으로 대체함

예시)

1. caeasar 암호(= shift chiper, Additive cipher)

shift chiper, Additive cipher

k = key만큼 shift함

ex) key = 7

C = (P + k) mod 26

P = (C - k) mod 26

Brute-force attack

위의 방법으로 암호화된 암호문을 Key가 1일때, 2,3,4,5,...26 일때의 경우를 모두 조사하면 평문을 찾을 수 있다.

따라서 위의 암호화 방법은 안전하지 않으므로 keyword를 추가하여 복잡하게 만들 수도 있다.

2. keyword 추가(전수조사 막기위해)

예를 들어 keyword가 ZEBRAS이면

ZEBRAS를 먼저 놓고, Z, E, B, R, A, S를 제외한 알파벳을 놓아 평문을 치환한다.

=> 가능한 keyCaesar 암호화보단 깨기 어려워진다.

또는

알파벳을 순차적으로 대응하지 않고 섞어서 대응하여도 복잡해진다.

하지만, 위의 방식들은 모두 1대1 대응이므로 문자의 빈도수를 세면 유추가능해진다.

항상 고정적으로 하나의 평문 문자가 하나의 암호문 문자로 대응되어 유추하기 쉽다. => 단일문자 치환 암호

(자주나오는 모음이나 diagram(2개문자), tigram(3개문자))

3. 비즈네로 암호 (빈도수 유추 막기위해)

예시) keyword - pascal

먼저 평문의 알파벳을 순서에 맞는 숫자에 대응하고

키워드 문자를 숫자에 대응하여

C = (P + K) mod 26 하여 암호문을 구한다.

s -> H, h- >H

s -> H, s -> S

와 같이 1대1 대응이 아니라 1대多 대응이 된다.

따라서 빈도수 공격을 완화시킬 수 있다.

비즈네로 암호는 이러한 방법을 사용한다.

실제론, 아래와 같이 비즈네르 table을 이용하여

키워드(Darkly)를 대응시켜 (K, P)와 같이 대응되는 문자를 테이블에서 찾아 암호문을 만든다.

하지만 이 방법도 키워드가 반복되므로 주기(키 길이)를 예측 할 수 있어 유추 가능해진다(암호 원리 파악 가능).

(평문 내용과 키워드 위치가 반복된다, 언어구조와 빈도 정보로 유추)

따라서 keyword의 길이를 평문길이만큼으로 하는 one-time-password을 사용하면 해결할 수 있지만, keyword를 관리하는 것이 어렵다.

4. one time pad

깨질 수 없는 안전한 암호 기법이다. 그 이유는 ...

1. 키(s)의 길이가 평문과 같거나 길다. => 암호문은 평문에 대한 어떠한 정보도 제공하지 않는 것처럼 보인다.

2. 키(s) 정보는 두 당사자만 알고 있다.

3. otp는 랜덤 생성해야하며 한번만 사용하므로 이전에 사용한 키는 사용되지 않는다.

하지만 키의 분배가 어려운 문제가 있다. 따라서 이론적으로만 안전하다.

c= m xor s, 평문을 키와 xor연산하여 암호문을 얻는다.

(평문이 8개의 문자를 사용하여 8bit 키를 사용함)

복호화 역시 같은키로 한다.

하지만 여기서 Alice와 Bob이 키를 주고 받을때, 중간에 이중첩자 Charlie가 다른키를 Bob에게 알려준다면, Bob은 복호화문을 이해하기 어렵거나 확인을 위해 Alice에게 직접 찾아가야한다.

혹은 Alice가 포로로 잡혓을때, 적들에게 잘못된 키를 알려준다면 적들은 해당 키로 복호화한 평문이 진짜인지 아닌지 판단할 수 없다.

다른 방법으론,

5. keyword 뒤 평문을 배치하여 키 길이를 맞춘다. (키 = keyword + 평문) (keyword 반복 문제 해결)

현대 암호에서는 이러한 방식을 응용한다.

2bit의 평문을 S-Box(substitution box)를 통하여 4bit로 확장시킨다.

정리하면,

monoalphabetic cipher(단일문자 치환 암호)는 전체 메시지에 대해 고정된 치환(1대1 대응)을 하여 빈도 수 공격으로 유추 가능해진다.

polyalphabeti cipher(복합 문자 치환 암호)는 평문에서 문자의 위치에 따라 대체되는 문자가 다르다 (1:多 대응),

하지만 기본적으로 문자 단위로 처리되므로, 키워드 반복시 주기를 알 수 있고, (모음), (모음은 자음에 의해 분리된다), (diagrams(연속되는 2개의 문자)), (Q뒤에는 U가 따라옴)과 같은 정보로 유추할 수 있다.

6. polygraphic substituion ciper (다중문자 대치) => Hill Cipher => Block 사용

하나의 평문 문자를 또 다른 암호문자 하나로 대응하면 즉, 문자 하나씩 암호문으로 변환할 경우에 빈도수 공격에 취약해진다.

다중문자 대치는 이웃한 문자를 그룹으로 만들어 그룹단위로 취급한다. => block 단위block의 크기를 n이라 하면

_n = 2일 경우) _

평문 : MISSISSIPPI

Block : MI SS IS SI PP IK

(Block 크기를 위해 더미 k를 추가함)

MI -> EQ, SS->GC ....와 같이 치환한다.

n, 즉 block이 커질 수록 빈도수 공격에 강해진다.

Playfiar cihper (n = 2) => 2x2 hill ciper이다.Y = Ax mod26(Y = 암호문, A = 키, x = 평문)다음과 같이 표현할 수 있다.

평문 : AT, Key : CDDG 인 경우)C -> 3, D->4, D->4, G->6

따라서

k를 표현할 수 있고, 평문 AT를 k로 암호화하면(k는 정방행렬로 만들어야한다. 암호화는 행렬의 곱이고 복호화는 역행렬을 만들어 곱을한다. 따라서 계산식을 쉽게 만들 수 있어야한다.)

5, 10 => FK가 나온다.(mod 26인 이유는 알파벳을 숫자로 표현했기 때문)

n을 3으로한 경우)

3x4 즉, 블럭의 크기를 12로 하여도 된다. => block 크기 가변적

복호화는 k의 역행렬을 곱하고 mod26을 하여 평문을 얻을 수 있다.

긴 평문 예시)

예시 - WANT_HELP.

WAN/ T_H/ ELP/ ... (더미 .. 추가)

22 0 13/ 19 28 7/ 4 11 15/ 26 26 26 (알파벳을 숫자로 바꿈)

키 = A

25 23 21/ 23 14 1/ 17 4 14/ 19 11 12

암호문 : ZWV XOB REO TLM

Transposition(전치(위치를 바꿈))

문자들의 순서를 바꾼다.

Columnar Transposition

1. simple

컬럼의 크기를 정하고 그에 맞게 평문을 자른다.

ENEMY TANKS APPROACHING HILL EIGHT SIX THREE

만약 컬럼의 개수의 배수가 아니면 더미를 추가한다.

그후, 컬럼별로 가져온다.

ENOHHR NKAITE ESCLSE MAHLIS YPIEXT TPNITO ARGGHP

만약 block의 크기가 5라면 5씩 잘라 표현한다.

ENOHH RNKAI TEESC LSEMA HLISY PIEXT TPNIT OARGG HPxxx (더미 추가)

2. 컬럼 순서 지정

컬럼에 순서(key)를 지정하여 순서에 따라 컬럼을 읽는다.

혹은 알파벳(key)으로 순서를 줄 수도 있다.,

=> EATI THIH MEXN ETMG MEDT

3. Double Transposition (행과 열 둘다 사용)

평문 : attackxatxdawnx (공백 대신 x를 사용하였다.)

먼저 행을 (3,5,1,4,2)의 순서로 바꾸고 열을 (1,3,2)순으로 바꾼다.

열로 읽었을 경우 : xwaxa txtak antdc

행으로 읽을 경우 : xta wxn att xad akc

4. Route Transposition Cipher

4.1. Rail-Fence Cipher

예시 rail 2개)

평문 = Meet me after the toga party

예시 rail 3개)

평문 = WE ARE DISCOVERED. FLEE AT ONCE

WECRL TEERD SOEEF EAOCA IVDEN

4.2. 위 방법외에 입력위치를 다르게 할 수 도 있다.

ex)

REINFORCEMENTS ARRIVING NOW

NMRGI FEEAR NNEOC NSIIO RRTVW

혹은 삼각형 모양으로도 할 수 있다.

4.3. Triangular Pattern

RMIFE VEONI RIRTN NCSGE ANROW

P- box

현대의 전치암호는 P(permutaiotion) box를 사용한다.

그냥 순서를 바꿔주는 p-box,

압축을 해주는 p-box

확장을 해주는 p-box

현대 암호인 AES는 Pbox를 사용한다.

튜링

튜링 머신

what can be computed. => 실제로 어디까지 계산가능한가?

어떤것, 어디까지 계산을 할 수 있는지 조사하는데 도움을 줄수 잇는 단순한 추상화된 컴퓨팅 기기

컴퓨터가 어디까지 가능한지(computability)를 나타내는 기본적인 모델임.

튜링 테스트

Can Machine think?

기계가 생각을 할 수 있는 가?

A : 기계 (질문시 사람인척 할 것임)

B : 사람

C(사람) : A, B가 사람인지 기계인지 판단(text기반 질문으로)

만약 C가 A, B를 구분하지 못한다면, A(기계)는 인공지능을 가진것으로 판단한다.