2009년 3월 23일 (4주차) 유 승 석(aviteria@gmail.com) 관용 암호 방식 2009년 3월 23일 (4주차) 유 승 석(aviteria@gmail.com)

관용 암호 방식 암호화와 복호화에 동일한 키를 사용 공통키 암호 방식 또는 암호화와 복호화 과정이 대칭적이어서 대칭 암호 방식 이라고도 호칭함 수 천년 전부터 사용되어 오고 있는 암호 방식 평문의 문자를 다른 문자로 환자(치환)하거나 또는 문자의 위치를 바꾸는 전치과정으로 구성

관용 암호 방식

수업 내용 환자 암호 전치 암호 적 암호(전치+환자) 스트림 암호 암호 해독 Questions & Answers

환자 암호

환자 암호 시프트 암호 단순 환자 암호 Affine 암호 동음이의 환자 암호 다표식 환자 암호 철자 환자 암호 Hill 암호 Playfair 암호

시프트 암호 환자 암호 중에 가장 간단한 방법으로 영문자를 다음과 같이 나열하고 일정 방향으로 일정 간격 시프트(shift) 시키는 방법 특히 시프트 간격을 3으로 한 경우를 Caesar 암호라고 한다.

시프트 암호

시프트 암호 Caesar 암호의 예

시프트 암호 수식 표현

예제 시프트 암호의 키가 K=11일 때, 다음의 평문 M을 암호화해 보자. 평문 s u b s t i t u t i o n c i p h e r

시프트 암호의 안전성 법 26을 이용한 시프트 암호는 안전하지 못하다. 침해자가 K에 0부터 25까지 키를 대입해보면 의미있는 문장을 찾을 수 있음 시프트 암호는 이러한 소모적 공격(exhaustive key search)에 매우 취약함

예제 시프트 암호에 의한 암호문 C가 다음과 같다. 소모적 공격으로 평문 M을 찾아보자. 암호문 R Y G K B O I Y E Q O D D S X Q Y X

단순 환자 암호(simple substitution) 평문 문자를 암호문 문자로 치환하는 방식 평문 영문자를 무작위로 다른 영문자로 치환하여 암호문을 만드는 단순 환자 암호표 p.64 [그림3.3] 참고 단순 환자 암호 복호표 p.65 [그림3.4] 참고

단순 환자 암호의 예

단순 환자 암호의 안전성 시프트 암호보다 전사공격에는 안전 빈도수에 의한 통계적 분석으로 해독 가능 키의 수 = 26!( 약 4 * 1026 개 ) 빈도수에 의한 통계적 분석으로 해독 가능 충분한 길이의 암호문, 암호문의 양이 많을 수록 통계적 성질이 많이 유지되어 암호문 해독이 용이함 p.65 [표3.1], p.66 [표3.2], [표3.3]

Affine 암호 시프트 암호 방식 Affine 암호 C ≡ M +K mod 26 , K = 3 C ≡ K1 M + K2 mod 26 gcd (K1, 26) = 1 ax = b mod m 에서 gcd(a,m)=1 이면 유일한 해 x 존재함 12개의 K1 과 26개의 K2의 조합이 키가 될 수 있으므로 키 숫자는 12*26=312 참고사이트 http://en.wikipedia.org/wiki/Affine_cipher

예제 K1=3, K2=15 일 때 information security를 Affine 암호화 하자.

Affine 암호의 예 K1 = {1,3,5,7,9,11,15,17,19,21,23,25} 중 K1 = 7 K2 = 1

동음이의 환자 암호 단순 환자 암호 방식처럼 언어 통계학적 성질을 이용한 해독에 취약한 것을 보완하기 위해 고안된 방식 암호문의 문자 빈도가 균등하게 분포되도록 만드는 방식

동음이의 환자 암호 미국의 T.J.Beale이 고안한 Beale 암호 방식

동음이의 환자 암호의 예 p.69 [최하단]

예제

다표식 환자 암호 (Vigenere cipher) polyalphabetic substitution pronounced /viːdʒɪnɛəɹ/, "veez-ih-nair" 1553 발간된 책에 기술됨( La cifra del. Sig. Giovan Battista Bellaso ) 19th 세기에 알려져, 현재 "Vigenère cipher“ 로 알려짐 참고사이트 http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher

다표식 환자 암호(Vigenere cipher)표

예제 키워드 SECURITY로 Vigenere 암호 방식에 따라 다음을 암호화 해 보자

철자 환자 암호 Hill 암호 Playfair 암호

철자 환자 암호 – Hill 암호 다형 환자 암호 Polygram substitution cipher 두 문자 이상을 묶어 이들을 다른 문자나 숫자로 변환 Invented by Lester S. Hill in 1929 참고사이트 http://en.wikipedia.org/wiki/Hill_cipher

철자 환자 암호 – Hill 암호 Hill's "Message Protector" patent 참고사이트 http://www.und.nodak.edu/org/crypto/crypto/.hill4.html

철자 환자 암호 – Hill 암호 철자 환자 암호 - Hill 암호

예제 다음 행렬 K로 Hill 암호 및 복호화 하기

철자 환자 암호 - Playfair 암호 Lord Playfair, who heavily promoted its use. 참고사이트 http://en.wikipedia.org/wiki/Playfair_cipher The Playfair system was invented by Charles Wheatstone, who first described it in 1854. Lord Playfair, who heavily promoted its use.

철자 환자 암호 - Playfair 암호 Playfair 암호표의 예 암호표 생성 규칙 키워드의 문자를 테이블에 좌우, 위아래 방향으로 하나씩 채움(단, 중복 문자는 버림) 나머지 남는 공간은 알파벳 순서로 채움 알파벳의 개수(25)를 맞추기 위해 일반적으로 "J" 를 생략(J=I) 또는 많이 사용되지 않는 "Q" 를 생략(Q=Z)

철자 환자 암호 - Playfair 암호 Playfair 암호표의 예2 Using "playfair example" as the key, the table becomes

철자 환자 암호 - Playfair 암호 Playfair 암호화 절차 먼저 평문의 띄어쓰기를 없애면서, 2문자씩 분리하는데 연속되는 문자(예 PP)가 있으면 같은 문자 사이에 X를 삽입(예 PXP)하여 같은 알파벳이 중복되지 않도록 하면서 다시 2문자씩 분리하는 방법을 계속함 전체의 글자 수가 홀수이면 맨 마지막에 X를 추가하여 짝수개로 만듬

철자 환자 암호 - Playfair 암호 Playfair 암호화 절차 1) 동일 행에 m1m2가 있으면 c1c2는 우측문자

예제 아래의 표를 참고하여 평문 informationsecurity를 Playfair암호화 하기

전치 암호

전치 암호(transposition cipher) 평문 문자의 순서를 어떤 특별한 절차에 따라 재배치하여 평문을 암호화하는 방식 scytale 암호 단순전치 암호 Nihilist 암호

scytale 암호

단순 전치 암호 simple transposition cipher 정상적인 평문 배열을 특정한 키의 순서에 따라 평문 배열을 재조정하여 암호화하는 방식

예제 단순 전치 암호의 키가 다음과 같을 때 information security를 암호화 하자

Nihilist 암호 단순 전치 암호의 암호 강도를 높이기 위해 행은 물론 열에 대해서도 전치를 적용한 암호 키워드에 따라 먼저 행을 일정 간격으로 전치시키고 다시 키워드의 순서에 따라 열을 일정 간격으로 전치시킨다. 때로는, 전치를 대각선 방향으로 하는 경우도 있다.

예제 LEMON이라는 키워드를 이용한 Nihilist 암호를 구성해 보자

적 암호

적 암호(product cipher) 암호 강도를 향상시키기 위해 전치와 환자를 혼합한 암호 방식 대표적인 예 제 1차 세계 대전 때 독일군이 사용하던 ADFGVX 암호 대부분의 현대 관용 암호 방식은 적 암호 방식을 이용하고 있음

적 암호 ADFGVX 암호 Feistel DES Rijndael(AES) SEED

ADFGVX 암호 ADFGVX의 여섯 개의 문자를 행과 열로 나열한 다음 36개의 열과 행이 직교하는 위치에 26개의 문자와 10개의 숫자를 무작위로 대입하여 암호화

ADFGVX 암호 ADFGVX 암호 환자표

예제 평문 conventional cryptography를 앞의 표에 따라 전치 키워드 CIPHER로 ADFGVX 암호화해 보자. 중간 암호문 작성(환자) 전치 키워드를 이용한 전치

Feistel 암호 Shannon의 암호 이론을 근거로 전치와 환자를 반복 적용한 적 암호를 구성함

[참고] Claude Shannon Claude Elwood Shannon April 30, 1916 – February 24, 2001 an American electronic engineer and mathematician, is known as "the father of information theory". 정보이론의 아버지 Claude Elwood Shannon (1916-2001) 참고사이트 http://en.wikipedia.org/wiki/Claude_Shannon

Feistel 암호 방식

Feistel 암호 방식 관계식 LE16 = RE15 RE16 = LE15 ⊕ f (RE15, K16)

Feistel 암호 방식의 복호화 과정 복호화 과정 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

스트림 암호

스트림 암호 비트 단위의 암호화를 수행 메시지열과 키계열을 이진합하여 암호화하는 방식 참고사이트 http://en.wikipedia.org/wiki/Linear_feedback_shift_register

스트림 암호 스트림 암호 방식의 암호 강도는 키 계열의 무작위성이 결정한다. 키스트림의 비예측성(unpredictability)을 충족하기 위해서 최대주기, 선형복잡도, 난수성 필요 일반적으로 키 계열은 선형 궤환 시프트 레지스터(linear feedback shift register, LFSR)를 이용하여 생성함

4단 선형 궤환 시프트 레지스터 플립플롭의 초기값은 모두 0이어서는 안됨 왜냐하면, 출력 키 계열은 계속해서 0만 출력함 스트림 암호는 암호문과 평문이 동일하게 됨

예제 [그림3.8]의 선형 궤환 시프트 레지스터의 플립플롭 F/Fi 의 초기값이 1010일 때 키 계열을 구해 보자.

암호 해독 환자 암호의 해독

암호 해독 암호 방식의 정규 참여자가 아닌 제삼자로 암호문으로부터 평문을 찾으려는 시도를 암호 해독 또는 공격이라 함 암호 해독자, 제삼자, 침해자 eavesdropper (사적인 대화를) 엿듣는 사람.

암호 해독 방법 암호문 단독 공격 (Ciphertext-only Attack) 기지 평문 공격 (Known-plaintext Attack) 선택 평문 공격 (Chosen-plaintext Attack) 선택 암호문 공격 (Chosen-ciphertext Attack)

[참고] 환자 암호의 해독 교재 p.90

Questions & Answers