Cryptanalysis
무작위 공격(brute-force)과 달리 암호 알고리즘을 분석해서 효율적인 방식으로 암호화된 값을 찾는 공격 방식
암호화 안전성 판단
Unconditionally Secure
무한한 비용이 주어진다고 하더라도 안전한 보안 체계
존재하지만 실제로 적용하기에 어렵기 때문에 널리 사용되지 않는다.
Computationally Secure
얻어낼 수 있는 정보의 가치보다 공격에 필요한 비용이 더 커지도록 만들어서 안전을 확보하는 방법
고전 암호
Substitution
고전 암호에서 많이 쓰이던 문자 치환 방식
- Ceaser Cipher(시저 암호, 카이사르 암호)
알파벳을 몇 순서 뒤의 알파벳으로 치환- 언어적 특성(반복되는 구문, 자주 등장하는 문자)을 공격 시에 악용할 수 있음
- Monoalphabetic Cipher
모든 알파벳이 동일한 치환 간격을 갖지 않고 랜덤하게 매핑language redundancy
언어마다 자주 쓰이는 알파벳이 있어서 패턴을 파악하기 쉽다. - Playfair Cipher
키가 되는 문자를 테이블에 배열하고 규칙에 따라 암호화하는 방법
예를 들어 같은 알파벳이 두 번 나오면 X로 치환하는 등...- 각 언어의 빈도 문제는 해결했지만 주로 같이 단어를 이루는 문자의 관계가 남아있다.
- Vigenere Cipher(비즈네르 암호)
key문자와 평문의 조합으로 암호화한다. 예를 들어 key=e, p=a라면 e+a에- 반복되는 패턴을 보고 키값의 길이 등을 유추할 수 있는 문제가 있음
- Vernam Cipher
문자를 사용하지 않고 bit단위로 데이터를 암호화하는 방법,key stream generator로 만든 키로 p와 XOR을 수행한다.
문자 대신 숫자를 사용하므로 연산 작업이라는 요소를 추가할 수 있다. - ❗ One-Time Pad
평문과 길이가 동일한 임의 키를 한 번만 사용하고 폐기하는 방법
공격자가 키를 보고 평문인지 암호인지 구분할 수 없음- 키를 전달할 secure channel이 필요함
- 평문과 동일한 키를 사용해야 하므로 용량 증가
Transeposition
문자열을 1대1로 치환하기보다 문자열 순서에 변화를 주는 암호화 방식
- Rail Fence Cipher
문자열의 흐름을 바꿔서 읽을 수 없게 만드는 방법 - Row Transposition
글자를 테이블에 나열한 다음 열 방향으로 읽는 방법. 첫 번째 열부터 순서대로 읽는 것이 아닌, 읽는 순서를 랜덤으로 바꾼다.
Number Theory
Divisibility, Divisibility Algorithm
a = m × b일 때 b | a 로 divisibility를 나타낸다.
a | 1이면 a = ±1
a | b && b | a 이면 a = ±b
0이 아닌 모든 b에 대하여 b | 0
b | g && b | h 면 b | (m×g+n×h)
Euclidean Algorithm
두 수의 GCD(최대공약수) 를 효율적으로 구할 때 쓴다.
gcd(a, 0) = |a| 일 떼
|a|는 a의 약수 중 가장 크고 동시에 0의 약수이므로 gcd=(A
Extended Euclidean Algorithm
확장 유클리드 알고리즘은 GCD 뿐만 아니라 곱셈의 역원을 구할 때 쓰인다.
Modular Arithmatic
a가 n으로 나눠떨어질 때 n을 modulus라고 한다.
a mod n = r, r은 a를 n으로 나눈 나머지다.
a를 n으로 나눈 모든 수가 포함된 집합을 Z(n)라고 한다.
{(a mod n) + (b mod n)} mod n = (a + b) mod n
modular 연산에는 교환, 결합, 분배법칙이 성립한다.
multiplicative inverse
- GCD를 통해 두 가지 원소가 서로소인지 알아본다
페르마 소정리
a^p = a mod p페르마와 오일러 이론
Euler's Phi Function
정수 n보다 작고 n에 prime 한 양수의 개수를 말한다.
Z = {0, 1, 2, ..., (pq-1)} 이라고 하자.
p의 배수는 p, 2p, 3p, ..., (q-1)p
q의 배수는 q, 2q , 3q, ..., (p-1)q
이다.
congruent modulo
a mod n = b mod n 이면 두 수가 합동(congruent)이라고 한다.
a와 n은 서로소
a^(n-1) = 1 mod n이면 n이 소수라고 추측할 수 있음
miller-rabin test
p가 소수면 x^2 = 1(mod p)가 두개의 해를 가짐
(x^2-1 = 0) mod p
-> p가 (x+1)(x-1)의 약수이다
CRT(Chinese remainder theorem)
n1, n2, n3, ..., nk가 있을 때 n은 모두 서로소라고 하자.
Discrete Logarithm Problem(DLP)
y = g^x mod p 일 때 x값의 범위가 0~n이라고 하면 x에 값을 일일히 대입해야만 해를 찾을 수 있다. 따라서 g, y, p가 제공된 상황에서 비트 수가 증가할수록 x값을 찾기 어려워진다.
