제2장 관용암호: 고전암호 기법 2007. 9.

목 차 2.1 암호학 개요 2.2 관용암호 모델 (Symmetric Cipher Model) 2.1.1 암호화 정의 2.1.2 암호 방식의 분류 2.2 관용암호 모델 (Symmetric Cipher Model) 2.2.1 치환[환자] 암호 기법 (Substitution Techniques) 2.2.2 전치[변환] 암호 기법 (Transposition Techniques) 회전기 암호 (Rotor Machines) 2.2.3 적 암호 (치환+전치) 2.3 스테가노그래피 (Steganography) 2.4 암호 공격 2

2.1 암호학 개요 암호학 역사 암호학 분류 라이산더 암호(그리스 BC. 400) 시저 암호(로마 BC. 100~44) ENIGMA 암호 ADFGVX 암호 무라사끼 암호 (97식) DES (1974) 공개키 암호 방식 (Diffie-Hellman, 1976) RSA (1978) 암호학 분류 고대 암호 치환 암호 전치 암호 근대 암호 암호기 사용 현대 암호 현대 대수학 3

2.1.1 암호의 정의 암호 통신 당사자들끼리만 아는 비밀스런 신호나 부호 암호학 암호화와 복호화하기 위한 원리, 수단, 방법 등을 다루는 기술 및 과학 평문(Plaintext): 이해하기 쉬운 일반 메시지 암호문(Ciphertext): 이해할 수 없도록 변형된 메시지 4

2.1.1 암호의 정의 암호시스템 3가지 영역 평문을 암호화하기 위한 연산자의 유형 사용된 키의 수 평문 처리 방법 치환(置換, Substitution) : 평문의 각 원소를 다른 원소로 사상 전치(轉置, Transposition) : 평문의 각 원소를 재배열 사용된 키의 수 관용키 : single-key, symmetric, secret-key 송수신자가 같은 키를 사용 공개키 : two-key, asymmetric, public-key 송수신자가 다른 키를 사용 평문 처리 방법 블록 암호화 (Block cipher) : 연산을 블록 단위로 처리 스트림 암호화 (Stream cipher) : 입력을 연속적으로 처리 5

2.1.1 암호의 정의 E D 암호화 복호화 평문 M 키 Ke 키 Kd 암호문 C 송신자 제3의 해독자 수신자 평문 : M Eke(M) = C Dkd(C) = M Dkd(Eke(M)) = M DkdEke = 1 6

2.1.2 암호 방식의 분류 관용 암호 방식 공개키 암호 방식 환자식 암호 방식 Caesar 암호 방식, Vigenere cipher 전치식 암호 방식 Scytale 암호, Nihilist 암호 적 암호 ADFGVX 암호 , DES, FEAL, LOK1, SKIPJACK Rijndael (AES) 소인수 분해 문제 이용 RSA, Rabin, LUC 이산대수 문제 이용 ElGamal 부분합 문제 이용 Knapsack 7

2.2 관용암호 모델 암호화 과정 특정한 방식의 알고리즘 비밀 유지되는 키를 적용 평문  암호문으로 변환 동일한 메시지도 키에 따라서 결과가 다르게 출현 8

2.2 관용암호 모델 관용암호방식의 안전성 특징 키 없이 암호문 자체만으로 해독 불가 안전성은 알고리즘이 아니라 키의 비밀성에 의존 암호문과 알고리즘이 알려져도 해독은 불가하다고 가정 키만을 비밀 유지 필요 저가의 칩으로 개발 유용(알고리즘을 비밀유지 비용 없다) 다양한 알고리즘 DES, RC5, SKIPJACK, IDEA, SEAL, RC4, SEED, AES 등 9

2.2 관용암호 모델 장점 알고리즘 수행속도 빠르다 단점 키 관리 및 키 분배와 디지털 서명의 어려움 그림 2.1 관용암호방식의 단순 모델 10

2.2.1 치환 암호 단순 전치 암호 방식 Caesar 암호 방식 Affine 암호 방식 동음이의 전치 암호 Vigenere cipher playfair cipher 11

2.2.1 치환 암호 단순 치환 암호 평 문(M) 암호문(C) 12

2.2.1 치환 암호 Caesar 암호 C = M + K mod 26 알파벳을 숫자로 생각 K = 3 인 시저 암호 13

2.2.1 치환 암호 Caesar 암호 예 평문 M 암호문 C 문자 P를 C로 암호화 C = E ( P ) = (P+3) mod (26) P = D ( C ) = (C–3) mod (26) 평문 M 암호문 C 14

2.2.1 치환 암호 Affine 암호 Caesar 암호 C  M + K mod 26 K = 3 C  K1 M + K2 mod 26 gcd (K1, 26) = 1 gcd : 최대공약수 gcd(a,b)=1 : a,b가 서로소 15

2.2.1 치환 암호 Affine 암호 예 K1 = 3, K2 = 5 평 문(M) 암호문(C) 26과 서로소 집합 = {1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25} 예 K1 = 3, K2 = 5 평 문(M) 암호문(C) 16

2.2.1 치환 암호 동음이의 치환 암호 예 i n f o r m a t s e c u y 17 27 89 21 67 13 50 44 65 42 41 84 77 48 11 8 66 07 55 26 17

2.2.1 치환 암호 동음이의 치환 암호 18

2.2.1 치환 암호 다표식 치환 암호 (Vigenere cipher) 키워드 SECURITY 평 문 키워드 암호문 t h i o s y s t e m i s n o t s e c u r e S E C U R I T Y S E C U R I T Y S E C U R I T Y S E C L L K M T Z R N L S U S J B X K A W P I K A X A M V G 19

2.2.1 치환 암호 다표식 치환 암호 (Vigenere cipher) 20

2.2.1 치환 암호 Hill 암호 1929년 미국 수학교수 Laster Hill 제안 n-gram 치환 암호방식 M개의 연속적인 평문자를 m개의 암호문자로 치환 M = 3일 경우 암호문 치환 C1 = (k11 p1 + k12 p2 + k13 p3 ) mod 26 C2 = (k21 p1 + k22 p2 + k23 p3 ) mod 26 C3 = (k31 p1 + k32 p2 + k33 p3 ) mod 26 C: 암호문 P: 평문 k: 키 21

2.2.1 치환 암호 Hill 암호 암호문 형식을 열 벡터와 행렬로 표현 암호화 사례 C1 k11 k12 k13 P1 평문: PAYMOREMONEY 암호 키 C1 k11 k12 k13 P1 C2 = k21 k22 k23 P2 C3 k31 k32 k33 P3 17 17 5 K = 21 18 21 2 2 19 22

2.2.1 치환 암호 Hill 암호 암호문 계산 숫자 대입 암호문 치환 평문을 숫자변환 PAYMOREMONEY: P 15, A  0, Y  24, … 숫자 대입 암호문 치환 K(15 0 24) + (375 819 486) mod 26 = (11 13 18) = LNS C1 = 17 * 15 + 17 * 0 + 5 * 24 = 375 mod 26 = 11 C2 = 21 * 15 + 18 * 0 + 21 * 24 = 819 mod 26 = 13 C3 = 2 * 15 + 2 * 0 + 19 * 24 = 486 mod 26 = 18 C1 k11 k12 k13 P1 C2 = k21 k22 k23 P2 C3 k31 k32 k33 P3 C1 17 17 5 15 C2 = 21 18 21 0 mod 26  C3 2 2 19 24 11 13 18 L N S 23

2.2.1 치환 암호 Hill 암호 복호문 계산 암호문 계산 형식 C = EK(P) = KP에서 평문 P = DK(C) = K-1C = K-1KP = P; K-1는 역행열: K-1K = I 역행렬 계산 P1 4 9 15 11 P2 = 15 17 6 13 mod 26  P3 24 0 7 18 15 24 P A Y 17 17 15 4 9 15 443 442 442 1 0 0 21 18 2 15 17 6 = 858 495 780 mod 26  0 1 0 2 2 19 24 0 7 494 52 365 0 0 1 24

2.2.1 치환 암호 playfair 암호 암호화 방법 반복되는 평문은 X와 같은 채움 문자로 분리 예)ballow : ba lx ow로 분리 같은 행 경우 우측 문자로 치환 같은 열 경우 바로 밑에 문자로 치환 다른 행,열 경우 대각선에 위치한 문자로 치환 평 문 i n f o r m a t s e c u y x 암호문 T O H N D U S I A W V F C L Z G Y 25

2.2.1 치환 암호 playfair 암호 특징 2중자의 빈도수 분석은 1중자보다 어려움 단점 평문의 원래 구조가 많이 드러남 1차 대전 중 영국 육군 야전 표준 시스템 사용 2차 대전 중 미국 육군 및 연합군에서 사용 단점 평문의 원래 구조가 많이 드러남 수 백자의 암호문자로 구조를 알 수 있다. 암호기법은 평문보다 일정한 분포를 갖지만 해독이 용이함. 26

2.2.1 치환 암호 단일문자 치환 암호기법의 단점 문자 출현 빈도수를 이용해 평문 유추가능 암호문에서의 평문에 대응 문자가 같은 빈도로 나타남 27

2.2.2 전치 암호 전치 암호: 평문자 나 비트의 순서를 절차에 따라 위치를 재조정 단순전치 암호 복잡한 전치기법 28

2.2.2 전치 암호 단순 전치 암호 암호화 복호화 1 2 3 4 5 6 1 2 3 4 5 6 평 문 암호문 i n f o r 암호화 복호화 1 2 3 4 5 6 1 2 3 4 5 6 i n f o r m a t s e c u y x z b F R I M O N A S T U E C Y B Z X 평 문 암호문 29

2.2.2 전치 암호 scytale 암호: (기원전 400년경 고대 그리스인이 사용) as bc cy dt ea fl ge a 30

2.2.2 전치 암호 rail fence : 깊이 2 평문 : meet me after the toga party 암호문 : mematrhtgpryetefeteoaat mematrhtgpry etefeteoaat 31

2.2.2 전치 암호 평 문 암호문 t h i s g o d f r e c u p G S O D H T I F R E P U 평 문 암호문 t h i s g o d f r e c u p G S O D H T I F R E P U C 32

2.2.2 전치 암호 복잡한 전치기법 메시지를 행렬의 행 순서로 쓰고 열 순서로 판독 n x m 행렬로 평문구성 평문 : a t t a c k p o s t p o n e d u n t i l t w o a m x y z 키 : 4 3 1 2 5 6 7 평문 : a t t a c k p o s t p o n e d u n t i l t w o a m x y z 암호화 : TTNAAPTMTSUOAODWCOIXKNIYPETZ 문자가 바뀌는 일정한 주기 발견 33

2.2.2 전치 암호 회전자 기계 (Rotor Machine) 다단계 재암호화의 원리를 적용 특징 독립적으로 회전 순환하는 실린더 집합으로 사용 각 실린더는 26개의 입력핀과 출력핀 보유 주기가 26인 다중 단일문자 치환 (26주기 polyalphabetic substitution) 저/ 중/ 고속의 3단계 실린더로 다중 치환방식을 수행 사용 예(2차 세계대전 사용) 영국: Typex; 미국: Sigaba(M-134); 독일: Enigma; 일본: Purple 34

그림 2.8 번호 연결 회로를 갖는 3-실린더 회전자 기계 35

3. 적 암호 방식 36

2.2.3 적 암호 치환과 전치기법을 혼합하여 사용 ADFGVX 암호 Feistel 37

2.2.3 적 암호 ADFGVX 암호 치환 과정 예 c o n v e t i a l XA DX DA GX VG GV VX AF DG r y p g h XV GG XX DD FV 38

2.2.3 적 암호 ADFGVX 암호 ADFGVX 표 구성 A D F G V X f x a 9 u 1 n g l d o 5 b l d o 5 b k 2 h z m j s y t v 7 4 3 e 8 i c w q 6 r p 39

2.2.3 적 암호 ADFGVX 암호 전치 과정 예 암호문 XGGDXXDX DDDD GDAG XGXFVVVV C I P H E R 1 4 5 3 2 6 X A D G V F 암호문 XGGDXXDX DDDD GDAG XGXFVVVV AXVAAXDX DVVA XGXF AAXGFXFG 40

2.2.3 적 암호 Feistel 암호 평문(2w) LE0(w) RE0(w) K1 f LEi(w) REi(w) K i f LEn–1(w) REn–1(w) K n f LEn(w) REn(w) REn(w) LEn(w) 암호문(2w) 41

2.2.3 적 암호 Feistel 암호 관계식 복호화 과정 A  B  B = A LD1 = RD0 = LE16 = RE15 RE16 = LE15  f (RE15, K16) 복호화 과정 LD1 = RD0 = LE16 = RE15 RD1 = LD0  f (RD0, K16) = RE16  f (RD0, K16) = [LE15  f (RE15, K16)]  f (RE15, K16) = LE15 LD16 = RE0 RD16 = LE0 A  B  B = A 42

2.3 Steganograhpy 보안기술의 범주 평문 메시지의 은닉 방법 특징 보안(Security): 정보를 보호하는 방법 첩보(Intelligence): 정보를 탐지하는 방법 평문 메시지의 은닉 방법 Steganograhpy 방법: 메시지의 존재 자체를 은폐 cryptography 방법 다양한 원문의 변환에 의해 외부인이 그 의미를 알지 못하도록 메시지를 변형 특징 원문내의 단어나 문자를 적절히 발췌하여 조합배열 함으로써 실제 메시지를 나타냄 43

2.3 Steganograhpy 사용 예 문자 마킹 (Character marking) 원문의 문자에 연필로 덧써서 표시를 빛을 적당한 각도로 비추어야만 보임 보이지 않는 잉크 (Invisible ink) 종이에 열이나 화학 처리를 해야만 보이는 잉크를 사용 핀 구멍 (Pin punctures) 빛을 비춰야만 보이는 작은 구멍을 원문에 넣는 방법 타자 수정 리본 (Typewriter correction ribbon) 흑색 리본으로 타자된 줄 사이에 강한 빛에서만 보이는 수정리본을 이용하여 타자하는 방법 44

2.3 Steganograhpy Steganography의 장점 Steganography의 단점 비밀통신에 대한 사실이 발견되면 안 되는 사용자들에 의해 이용 암호화의 경우의 문제점 암호화 한다는 사실이 통신 메시지가 중요하거나 비밀임을 암시 즉, 암호화는 송수신자간에 무언가 감출게 있다고 생각하게 함 Steganography의 단점 상대적으로 적은 정보비트를 은닉하는데 많은 오버헤드 요구 방법 노출시 재사용 불가 (키를 적용하는 기법을 추가하여 단점 극복) (메시지를 먼저 암호화 한 후에 Steganography을 이용하여 은닉가능) 45

2.4 암호 공격 Cryptanalysis Brute-Force Attack 안전성 평문이나 키 또는 이 두 가지를 모두 발견하려는 시도 과정 Brute-Force Attack 가능한 모든 경우의 수를 시도(전사적 탐색, 전사 공격) Probable-Word Attack 안전성 절대 안전성: 비용과 시간이 충분하여도 복호하기가 불가능 계산상 안전성 해독 비용 > 정보의 가치; 해독시간 > 정보유효시간 46

2.4 암호 공격 암호 메시지에 대한 공격의 유형 암호문 단독 공격 (Ciphertext only) 암호 알고리즘, 해독할 암호문 기지 평문 공격 (Known plaintext) 하나 또는 그 이상의 알고 있는 평문에 대한 암호문을 인지 선택 평문 공격 (Chosen plaintext) 해독자가 선택한 평문 메시지와 해당 암호문을 인지 선택 암호문 공격 (Chosen ciphertext) 해독자가 선택한 암호문과 해독된 평문을 인지 선택 원문 공격 (Chosen text) 47

2.4 암호 공격 표2.2 모든 키 탐색을 위해 요구되는 평균시간 32 56 128 26문자 permutation 키 크기(비트) 가능한 키의 수 s당 1 암호화 s당 106 암호화 32 232 =4.3 x 109 231 s = 35.8분 2.15 ms 56 256 =7.2 x 1016 255 s = 1142년 10.01 h 128 2128 = 3.4 x 1038 2127 s = 5.4 X 1024년 5.4 x 1018년 26문자 permutation 26 ! =4 X 1026 2 X 1026 s = 6.4 X 1012년 6.4 x 106년 48