dreamhack [머릿말] [고전암호] 정리

https://dreamhack.io/lecture/courses/69

https://dreamhack.io/lecture/courses/70

를 바탕으로 작성했습니다

 

 

<머리말>

1.   커리큘럼 소개

-커리큘럼의 목표와 대상

 컴퓨터에 대한 의존도가 높아지면서 네트워크를 통한 정보 공유가 늘어났고, 컴퓨터 환경에서 암호학은 중요 해졌다. 이 강의를 통해 실제 상용 프로그램에 쓰이는 암호 알고리즘의 특징을 이해하고, 안전한 서비스를 개발하기 위해 어떤 암호 기술을 사용해야 하는지 알게 된다.

 

-커리큘럼의 주제

암호학(cryptography) : 제 삼자로부터 정보를 보호하는 방법에 대한 연구

키 생성(Key generation) : 암호화 및 복호화에서 사용할 키를 만듦

암호화(Encryption) : 키를 이용해 평문을 암호문으로 변환

복호화(Decryption) : 키를 이용해 암호문을 평문으로 변환

암호화와 복호화로 정보가 전달되는 체계 : 암호시스템(Crypyosystem)

 

* 암호화 / 인코딩 (공통점 : 데이터를 다른 형태로 변환하는 것)

인코딩 - 데이터의 기밀성을 고려X, 누구나 디코딩해 원문 구하기 가능 (크기 줄이기, 컴퓨터가 이해하기 쉬운 형식으로 변형하기 ex:압축)

암호화 – 데이터 숨기기 위해 사용

 

2.   배타적 논리합과 합동식

배타적 논리합 (eXclusive OR, XOR)

              : 입력으로 들어온 두 인자가 ‘서로 다를 때’ 참(1)을 반환하는 연산

                0&0->0        0&1->1       1&0->1       1&1->0

합동식

    : 정수 a,b를 각각 정수 m으로 나눴을 때 나머지가 같은지 판별하는 식

     같을 때 ,a와 b가 mod m에 대해 합동(congruent)라고 표현

     Ex) 7,17은 10으로 나눈 나머지가 같음 -> 7≡17(mod 10)

* a,b가 mod m에 대해 합동일 경우 a,b가 나머지를 제외한 사칙연산을 해도 합동

* a≡b(mod m) -> a+x≡b+x(mod m), a-x≡b-x(mod m), ax≡bx(mod m)

합동식에서 곱셈의 역원

   정수 a,m에 대해 a x b ≡1(mod m)을 만족하는 b를 mod m에 대한 a의 곱의 역원이라 부르고, 로 표기한다. (역원은 a와 m이 서로소일 때에만 존재 가능)

3. 마치며

      퀴즈 답 : 13, 4,인코딩

 

 

 

<고전암호>

1. 들어가며

-서론

고전 암호 : 기계와 손 등으로 간단하게 암복호화를 수행하던 암호 (현대엔 사용X)

단순한 고전 암호 : 치환 암호, 전치 암호 (한 가지 원리만 사용)

복잡한 고전 암호 : 두 원리 모두 사용

고전 암호 설계 방법 1.치환(Substitution) 2.전치(Transposition)

1. 치환 : 평문의 문자를 다른 문자로 바꾸는 것

단일문자치환암호(Monoalphabetic Substitution), 다중문자치환암호(Polyalphabetic Substitution)

2. 전치 : 평문 문자들의 위치를 바꾸는 것

 

2. 고전 암호

-단일 문자 치환 암호

평문의 각 문자를 약속된 다른 문자로 치환하는 암호 (치환 대응 관계 : 일대일 대응)

(1) 카이사르 암호 (Caesar Cipher)

각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 치환(복호화는 원래 위치로 밀어서 구함)

주의! 송신자와 수신자가 몇 칸을 밀지 사전 합의 필요->알파벳을 밀어낸 횟수(키Key)만 알면 해결 가능

키 공간(key space) : 가능한 모든 키의 집합, 키 공간의 크기 : 26 (알파벳 총 26자)

* 수식으로 표현한 카이사르 암호

 

(2) 춤추는 인형과 코드북 암호

카이사르 암호보다 더 복잡한 단일 치환 암호. 사람 한 명이 글자 하나에 대응됨.

모든 알파벳을 서로 다른 기호와 무작위로 일대일대응시켜 치환 -> 키 공간의 크기 : 26!

단일 치환 암호의 단점 : 언어가 지닌 통계적 특성이 유지됨.

가장 많이 사용되는 알파벳=e  -> 암호문에서 b가 가장 많이 등장 -> b는 e가 치환된 것

난수표, 코드북을 이용한 단일 치환 암호

X:책의 페이지, Y:단어의 인덱스

ex) 21537,21529,21406,21402 => 215p 37번째 단어,215p 29번째 단어, … 단어들 이어붙이기

 

-다중 문자 치환 암호

평문의 한 문자가 암호문에서 여러 종류의 문자로 치환될 수 있음.

(1) 비제네르 암호 (Vigenere Cipher)

미리 정해진 키워드를 통해 암호화 복호화 진행. (비제네르 표 사용)

* 비제네르 암호

 

-전치 암호

평문을 구성하는 문자들의 순서를 재배열해 암호문을 제작

정해진 길이의 블록들로 평문을 나누고, 규칙을 적용해 불록 안의 문자들을 재배치

ex DREAM HACK => E(3)D(1)R(2)HA MKAX

(1) 스키테일 암호 (Scytale Cipher) 나무봉(Scytale)을 이용한 암호

송신자: 나무봉에 종이 테이프를 감고, 그 위에 세로로 메시지를 기입해 암호문을 만듦

수신자: 같은 나무봉에 테이프를 감아서 해석

 

-고전 암호 공격

고전 암호들은 기술의 발달로 쉽게 분석되었음.

공격 방법

(1) 전수 키 탐색 공격(Exhaustive key Search Attack)

키 공간을 전부 탐색해 주어진 암호문과 같은 암호문을 생성하는 키 탐색.

(평문, 암호문 알아야 함. 단순한 공격 방법. 키 공간 크기 작으면 빠른 시간 내 가능)

(카이사르 암호(단일치환암호)는 키 공간 26 => 전수 키 탐색 공격에 취약)

(2) 빈도수 분석(Frequency Analysis)

대상 언어의 특성을 안다면 추측을 바탕으로 암호문을 복구.

단일 치환 암호는 평문의 통계적 특성이 유지됨 (일대일 대응이기 때문)

(다중 치환 암호는 통계적 특성이 사라져, 빈도수 공격으로부터 비교적 안전)

 

3. 마치며 (summary)

치환(Substitution) : 평문의 각 문자를 다른 문자로 치환하는 기법. 단일 치환 암호, 다중 치환 암호 (대응 관계로 구분)

전치(Transposition) : 평문을 구성하는 문자들의 순서를 바꾸는 기법.

전수 키 탐색 공격(Exhaustive key Search Attack) : 키 공간을 전부 탐색. 키 공간 수 적으면 효과적. (현대 암호는 키 공간 크기 넒음->어려움)

빈도수 분석(Frequency Analysis) : 단어 빈도를 분석해 통계적으로 복호화하는 공격. 특수 경우에서만 사용 가능

퀴즈 답 : 어렵다,유효한