박 종 혁 (parkjonghyuk1@hotmail.com) 2장. 고전 암호 기법 박 종 혁 (parkjonghyuk1@hotmail.com) http://www.parkjonghyuk.net

목 차 대칭 암호 모델 치환 기법 전치 기법 회전자 기계 STEGANOGRAPHY

대칭 암호 모델 대칭 암호 기법 5가지 요소 평 문 입력으로 주어지는 원래의 알아볼 수 있는 메시지 또는 데이터 암호 알고리즘 평 문 입력으로 주어지는 원래의 알아볼 수 있는 메시지 또는 데이터 암호 알고리즘 평문에 대하여 다양한 치환 및 변환을 수행 비밀키 하나의 입력으로 키는 평문에 독립적 다른 키를 사용될 때마다 다른 출력을 생성 암호문 암호 알고리즘의 출력으로 생성된 혼합된 형태의 메시지 알아볼 수 없는 형태 복호알고리즘 암호 알고리즘을 역으로 수행하는 알고리즘은 키의 입력으로 평문 생성

대칭 암호 모델 관용 암호 방식의 단순 모델

대칭 암호 모델 관용 암호 시스템의 모델

대칭 암호 모델 암호 해독 암호 해독(Cryptanalysis) 특정 평문 또는 사용된 키의 추론을 시도하기 위하여 알고리즘의 특성을 활용 전사적 공격(Brute-force attack) 하나의 암호문에 대하여 이해할 수 있는 평문으로 전환될 때까지 가능한 모든 키를 시도 공격 유형 해독자에 알려진 정보 암호문 단독 공격 암호 알고리즘, 해독될 암호문 기지 평문 공격 암호 알고리즘, 해독될 암호문, 하나 이상의 비밀키에 의한 평문-암호문 쌍 선택 평문 공격 암호 알고리즘, 해독될 암호문, 해독자가 선택한 평문 메시지와 비밀키로 생성된 그평문에 대한 암호문 선택 암호문 공격 해독자가 선택한 목적 암호문과 비밀키로 생성된 그 암호문의 해독된 평문 선택 원문 공격 해독자가 선택한 평문 메시지와 비밀키로 생성된 그 평문에 대한 암호문 해독자가 선택한 목적 암호문과 비밀키로 생성된 그 암호문에 해독된 평문

대칭 암호 모델 알고리즘을 개발 기준 암호해독 비용이 암호화된 정보의 가치 초과 암호 해독 시간이 정보의 유효 기간 초과 32 키 크기(비트) 가능한 키의 수 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년

치환 기법 시이저 암호 기법 알파벳 문자를 두문자 건너의 세 번째 문자로 치환하는 방식 예 평문 : meet me after the toga party 암호문 : PHHW PH DIWHU WKH WRJD SDUWB 문자의 치환 수식을 이용한 시이저 암호 알고리즘 분석 평문자 a b c D e f g h i j k l m n o p q r s t u v w x y z 암호문자 E F G H I J K L M N O P Q R S T U V W X Y Z A B C 평문자 a b c d e f g h i j k l m 숫자 1 2 3 4 5 6 7 8 9 10 11 12 평문자 n o p q r s t u v w x y z 숫자 13 14 15 16 17 18 19 20 21 22 23 24 25

치환 기법 시이저 암호 기법 암호 알고리즘 취약점 암호화 및 복호 알고리즘을 알고 있음 가능한 키는 25개 평문의 언어를 알고 있으면 쉽게 인식할 수 있음

치환 기법 시이저 암호문의 전사적 암호 해독 25개의 키 평문 언어 인식

치환 기법 단일 문자 치환 암호 기법 영어 언어의 규칙성을 이용한 해독 임의의 치환을 허용하는 단일문자 치호나 암호 기법 키 공간을 급격히 증가 각 문자 대신 26개 문자를 모두 허용하는 경우 26! 영어 언어의 규칙성을 이용한 해독 상대 문자 빈도

치환 기법 문자 빈도를 이용한 방법 암호문 문자빈도 각 장 높은 P를 E로 변경, Z은 A, T 중 하나로 변경 영어 단어상 THE가 많이 사용됨으로 우선 P앞에 Z이 많이 발견 Z=T로 변경 U Z Q S O V H X M P G E W F D B T A I J P 13.33 Z 11.67 S 8.33 U 8.33 O 7.50 M 6.67 H 5.83 D 5.00 E 5.00 V 4.17 X 4.17 F 3.33 W 3.33 Q 2.50 T 2.50 A 1.67 B 1.67 G 1.67 Y 1.67 I 0.83 J 0.83 C 0.00 K 0.00 L 0.00 N 0.00 R 0.00

치환 기법 문자 빈도를 이용한 방법 위와 같이 문자의 빈도를 구해 지속적으로 적용 암호 U Z Q S O V H X M P G E W F D B T 평문 A I J

치환 기법 Playfair 암호 기법 M O N A R C H Y B D E F G I/J K L P Q S T U V W X 다중문자 치환 암호 기법 암호문 2중자로 번역 5 X 5 문자 행렬에 기초 본 표에서의 키워드 : MONARCHY 문자들을 중복 문자는 제외하고 행렬의 좌에서 우로 상단에서 하단 행렬 여백은 나머지 알파벳 순서대로 채워 감 I와 J는 한 문자로 취급 M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z

치환 기법 다중문자 치환 암호 기법 방식 같은 쌍 내의 반복되는 평문자는 X와 같은 채움 문자로 분리 예 ) balloon -> ba lx lo on으로 처리 행렬의 동일 행 내의 평문자 쌍은 각각 바로 우측에 위치한 문자로 치환 마지막은 다음에 첫 문자 행렬의 어떤 열에 적용하는 경우 바로 아래에 있는 문자로 치환, 최 하단의 문자는 최 상위 문자로 치환 그 외의 경우, 각 평문자는 그 평문자가 있는 행 그리고 다른 평문자가 있는 열의 문자로 치환

치환 기법 다중문자 치환 암호 기법 M O N A R C H Y B D E F G I/J K L P Q S T U V W X 예) balloon -> ba lx lo on으로 1차 변경 행렬에서 ba는 같은 열에 있으므로 아래 문자 치환 : IB 또는 JB 행렬에서 lx는 서로 다른 위치에 있음 : lx -> su 로 치환 행렬에서 lo는 서로 다른 위치에 있음 : lo -> pm로 치환 행렬에서 on은 같은 행에 있으므로 우측 문자 치환 : on -> na로 치환 ba lx lo on -> ibsupmna로 변경 M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z

치환 기법 Hill 암호 기법 C1 = (k11 p1 + k12 p2 + k13 p3 ) mod 26

치환 기법 암호문 형식을 열 벡터와 행렬로 표현 C1 k11 k12 k13 P1 C2 = k21 k22 k23 P2 암호화 사례 평문: 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

치환 기법 암호문 계산 평문을 숫자변환 PAYMOREMONEY: P 15, A  0, Y  24, … 숫자 대입 암호문 치환 K(15 0 24) + (375 819 486) mod 26 = (11 13 18) = LNS C1 = 17 x 15 + 17 x 0 + 5 x 24 = 375 mod 26 = 14 … …11 C2 = 21 x 15 + 18 x 0 + 21 x 24 = 819 mod 26 = 31 … …13 C3 = 2 x 15 + 2 x 0 + 19 x 24 = 486 mod 26 = 18 … …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

치환 기법 복호문 계산 암호문 계산 형식 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

치환 기법 다중 단일 문자 치환 암호 기법 대표적인 Vigenere 암호 방식 관련된 단일 문자 치환 규칙들의 집합을 사용함 주어진 변환에 사용될 특정 규칙은 키에 의해 결정됨 대표적인 Vigenere 암호 방식 행렬표를 구성 키 문자 x와 평문자 y가 주어지면 암호 문자는 x행 y 열의 암호문 V 키 : deceptive 평문 : we are discovered save yourself 평문 길이 만큼 키 크기가 필요 언어의 특징을 모두 없애지 못함 키 d e c p t i v 평문 w a r s o y u l f 암호문 Z I C V T W Q N G R A H Y L M J

현 대 V I G E N R 표 a b c d e f g h i j k l m n o p q r s t u v w x y z

전치 기법 전치 기법 평문자에 대한 일종의 순서 바꿈에 의해 이루어 짐 예 “meet me after the toga party” 깊이 2의 rail fence 기법으로 암호화 암호문 : MEMATRHTGPRYETEFETEOAAT 깊이 2의 경우 해독이 쉽게 될 수 있음 동일한 예로 메시지를 사각형의 행순으로 써놓고 열 순으로 읽되 열의 순서를 키로 바꿈 암호문 : FOTTAERPMTGEEAATYEETMHR M E A T R H G P Y F O 키 4 5 3 2 8 7 6 1 평 문 M E T A F R H O G P Y

전치 기법 한번 전치한 암호문을 동일한 방법으로 두 단계 이상의 전치를 함 키는 동일함 2단계 전치 암호문 평문 : FOTTAERPMTGEEAATYEETMHR 키는 동일함 2단계 전치 암호문 PTTETTGEFMYOTERAREAHAEM 키 4 5 3 2 8 7 6 1 평 문 F O T A E R P M G Y H

회전자 기계 회전자 기계 기본 원리 26개의 입력 핀과 26개의 출력 핀 주기가 26인 다중 단일 문자 치환 알고리즘

회전자 기계 1943년 초, 빌딩 26 (미국 오하이오주 데이턴)에서, 조지프 데쉬가 이끈 NCR 기술팀  군이 요청한 암호 자동 해독기 개발 이후 연합군은 거의 실시간으로 독일군의 암호를 해독 당시 암호작성기는 ‘에니그마(사진)’. 누구도 풀지 못한다고 해서 이름 붙여진 에니그마(enigmaㆍ수수께끼)의 해독을 위해 영국은 암호학교까지 세움. 전쟁 양상을 바꾼 새 암호해독기의 개발과 그 작전 87년 조지프 데쉬가 숨진 지 몇 년 뒤, 비밀해제를 통해 알려짐. 미군은 태평양전쟁에서도 승기를 잡음 당시 일본군은 에니그마 변형 암호작성기를 사용했는데, 미국은 그 90%이상을 해독 함 42년, 미드웨이 해전의 승리, 43년, 진주만 기습을 주도한 야마모토 이로소쿠(山本五十六) 사령관의 피격  일본군 암호를 해독했기에 가능

STEGANOGRAPHY 메시지의 존재 자체를 은폐하는 방식 그림 파일에 일정한 그림이나 문자 혹은 문서를 변환 삽입 문자 마킹 인쇄 또는 타자된 원문의 문자들을 선택하여 연필로 그 위에 덧쓰는 방법, 밝은 빛을 적당한 각도로 비춰야만 보임 보이지 않는 잉크 종이에 열 또는 화학 처리를 해야만 보이는 다양한 종류의 잉크 사용 핀 구멍 빛을 비춰야만 보이는 작은 구멍을 원문의 특정 문자에 넣는 방법 타자 수정 리본 흑색 리본으로 타자된 줄 사이에 강한 빛에서만 보이는 수정 리본을 이용 미국의 테러사건의 빈라덴과 알카에다의 조직원들이 웹의 이미지 사진에 정보를 숨겨서 이용함

STEGANOGRAPHY STEGANOGRAPHY 프로그램 순서도 김태희 사진 실습 : www.stegoarchive.com 개발사 및 프리 소프트웨어 제공 실습 프로그램 : S-tools3를 다운받아 실행 하나의 이미지 안에 다른 이미지를 숨김 아래 김태희 사진에 프로그램 순서도 이미지를 숨길 예정 프로그램 순서도 김태희 사진

STEGANOGRAPHY 그러나 실제로는 앞 사진에 이미 S-tool3를 이용하여 다른 이미지 하나를 미리 숨겨 두었음. 1번은 인터넷 상 실제 이미지 즉 원본 2번은 다른 이미지를 숨긴 앞 피티에서 본 이미지 의식하지 않고 보면 그냥 해상도가 낮은 사진처럼 보임 1번 김태희 사진 2번 김태희 사진