HSOC crypto 멘토링 1

동아리 멘토링 할 때도 본인이 멘토면 자료는 직접 만들어서 합시다
이거 혹은 다른 멘토 자료 그대로 본인 블로그에 올리거나 자료로 만들어서 쓰지 말고.. 안 그럴거라 믿을게요

여러 블로그랑 책 등을 참고해서 멘토링에 필요한 내용만 간단하게 정리한거임
문제를 만들거나 풀 때 사용되는 내용만 다룰 예정이고 용어의 정의나 뜻 같은거는 최대한 생략할 예정 (구글링하면 더 잘 설명해줌)
암호학을 공부하면 프로그래밍을 공부할 때 hello world를 치는것과 같이 비슷한게 있는데 보통 송신자(메세지 보내는사람)를 elice라고 부르고 수신자(메세지 받는사람)을 bob이라고 부름

 

암호학 기본 개념

암호의 특성

• 기밀성(Confidentiality): 암호화된 내용이 무엇인지 알 수 없어야 함
• 무결성(Integrity): 원본과 확실한 데이터라는 것
• 인증(Authentication): 권한이 있는 사람만 접근할 수 있음

암복호화 과정

평문(plaintext): 원래 송신자가 전달하려는 원본 메세지
암호문(ciphertext): 송신자와 수신자만 전달 내용을 알 수 있도록 키를 사용해서 알아볼 수 없게 만든 메세지
암호화(encryption): 평문을 암호문으로 바꾸는것
복호화(decryption): 암호문을 평문으로 바꾸는것
키(key): 암복호화에 쓰이는 특정한 값 (자물쇠 열고 잠그는것처럼 키를 사용해서 암복호화를 진행하고 키를 모르면 복호화가 어려움)
 
당연하지만 해커가 중간에 메세지를 가로채서 이상한 메세지로 바꾸거나 메세지 내용을 알게되는것을 방지하기 위해 키는 공개하지 않음
하지만 암호화 알고리즘, 키 길이는 대부분 공개함

 

암복호화 표기법

• 증명 과정이나 암호 알고리즘 설명에 쓰이는 정수론 표기법 같은거는 나중에 설명할 예정

암호 알고리즘이나 원리를 설명할 때 항상 암호화, 복호화, 키, 평문 등 이런식으로 표기하기 번거롭기 때문에 다음과 같이 표기함
$Z_n$ : n이 양의 정수일 때 0부터 n-1까지의 정수 집합임
ex) $Z_{26}$은 0~25까지의 정수 집합으로 총 26가지임. 보통 알파벳 집합을 나타낼 때 이와같이 표기함
$P$ : plaintext
$C$ : ciphertext
$k$ : key
$e_k$ : encrypt key - 암호화할 때 사용하는 키
$d_k$ : decrypt key - 복호화할 때 사용하는 키
 
위 표기법을 이용하면 다음과 같이 수식을 작성할 수 있음
$$ C = e_k(P) \\ P = d_k(C) $$
 

고전암호

치환 암호 (Substitution Cipher)

: 평문의 문자를 다른 문자로 바꾸어서 암호화하는 방식
 

1. 단일 치환 암호

: 평문의 각 문자를 약속된 다른 문자로 바꾸는거
 

1-1. 카이사르 암호 (Caesar cipher)

<암호화>
26개의 알파벳을 나열해서 시프트해주어 암호화를 진행함
예를 들어 a~z 알파벳 배열을 3칸씩 시프트해주면 다음과 같이 됨
그럼 a-d, b-e, c-f, d-g, e-h, f-i 등과 같이 일대일 대응이 됨
$P = C=K=Z_{26}$이라 하면 이때 $0\leqq k \leqq 25$ 에 대하여 암호화 함수는 다음과 같음
 
$$ e_k(x) = x+k\;(mod\;26) $$

 

<복호화>
복호화 할때는 반대로 다시 3칸을 뒤로 밀어주고 평문을 계산하면 됨
복호화 함수는 다음과 같고 x, y도 다음과 같이 정의할 수 있음

 

$$ d_k(y)=y-k\;(mod\;26),\\x, \ y\in Z_{26} $$

 

위 두개의 암호화 함수, 복호화 함수를 통해 $d_k(e_k(x))=d_k(x+k)=x+k-k=x$ 임을 알 수 있음

 
1-2. 곱셈 암호 (Multiplication Cipher)

<키 설정>
(k, 26) = 1이 되는 $k \in Z_{26}$ 값들은 k = 1,3,5,7,9,11,15,17,19,21,23,25 

 

<암호화>
$$ e_k(x)=(x \times k)\;mod\;26 $$

 

아까 카이사르 암호는 덧셈을 사용했지만 여기서는 곱셈을 해준뒤에 26으로 나머지 연산을 해줌
예를 들어 키가 7이라고 하면 다음과 같이 할 수 있음

 
 

<복호화>
$$ d_k(y)=(y\times k^{-1})\;mod\;26 $$

 
1-3. 아핀 암호 (Affine Cipher)

암호화로 따졌을 때 카이사르는 덧셈, 곱셈암호는 곱셈이였는데 아핀암호는 그 두개를 결합한 형태

 

$$ P=C=Z_{26} \\ K= \left\{ (a,b)\in Z_{26} \times Z_{26} \mid (a,\;26)=1 \right\} \\ k=(a,b) \in K,\;x,y \in Z_{26} $$

 

<키 설정>
26 = 2*13이기 때문에 (a, 26) = 1이 되는 $a \in Z_{26}$ 값들은 a = 1,3,5,7,9,11,15,17,19,21,23,25 임
하지만 b는 $Z_{26}$의 어느 값을 가져도 되기 때문에 아핀암호에서 가능한 키 수는 12*26=312개임

 

<암호화>
$$ e_k(x)=ax+b\;(mod\;26) $$
암호화할 때 곱셈에 쓰일 키, 덧셈에 쓰일 키 2개를 지정해야함
예를 들어 k = (7, 3)이면 암호함수는 $e_k(x)=7x+3\;(mod\;26)$임

 

<복호화>
$$ d_k(y)=a^{-1}(y-b)(mod\;26) $$
아까 예시 그대로 k = (7, 3)으로 지정했을 때 복호함수 $d_k(y)$를 구하기 위해서는 먼저 $7^{-1}$을 구해야함
$7 \times 15 = 105 \equiv 1\;(mod\;26)$이므로  $7^{-1} \equiv 15\;(mod\;26)$임
따라서 $d_k(y)=15y+7\;(mod\;26)$

 

2. 다중 문자 치환 암호

: 평문의 한 문자가 암호문에서 여러 종류의 문자로 바뀔 수 있음
 

2-1. 비즈네르 암호

<암호화>
$$ e_k(x_i)=(x_i+k_i)\;mod26 $$
전에 카이사르 암호에서 키가 12였으면 a를 12칸, b를 12칸, c를 12칸 이런식으로 시프트했었음
근데 비즈네르에서는 키가 12일 때 a는 1칸, b는 2칸, c는 1칸, d는 2칸 이런식으로 키 길이를 평문 길이만큼 반복해서 돌림
그래서 다음 사진과 같은 비즈네르 스퀘어를 이용함
 

 

HELLO를 CUP으로 암호화시킨다고 하면
H,C가 만나는 J
E,U가 만나는 Y 이런식으로 할 수 있음

 

<복호화>

 

$$ d_k(y_i)=(y_i-k_i)\;mod26 $$

 

암호화할 때랑 반대로 실행하면 됨
보통은 kasiski test 라는 공격법을 사용하는데 vigenere cipher decode라고 검색하면 복호화 사이트 많이 나옴

 

전치 암호 (Transposition Cipher)

: 전에 치환암호는 a → d, b → e 이런식으로 다른 문자로 대체했었다면 전치 암호는 문자의 순서를 규칙에 따라 무작위로 바꿈
치환암호랑 다르게 암호화함수, 복호화함수 이렇게 정의해서 표현하기가 애매함 (나중에 시간있을 때 책 찾아보거나 해서 있으면 정리해볼 예정)
https://ieatt.tistory.com/27
이 블로그 보고 이런 종류가 있고 이런식으로 하는거구나 정도만 알아두기

 

현대암호

대칭키, 비대칭키, 단방향 이런거는 다음 멘토링때

 

그 외

xor

http://m.blog.naver.com/oidoman/221145674383

base64

https://dokhakdubini.tistory.com/505

 

RSA, AES

RSA

• 유클리드 호제법 (확장 유클리드도)
• 베주 항등식
• 페르마 소정리
• 오일러 정리

AES

• DES
• 행렬
• 갈루아 필드
• 체 이론
• 군 이론