암호학 기본(개론... 이랄까)

암호학(cryptology)

◈기본 용어

평문 : 사람이 이해할 수 있는 일반 형태의 문장

암호문 : 사람이 (또는 송신자, 수신자 외의 제 3자) 이해할 수 없는 형태로 변형된 문장

암호화 : 평문을 일반적인 알아보지 못하게 암호문으로 만드는 과정

복호화 : 암호문을 다시 읽을 수 있는 평문으로 만드는 과정

송신자 : 정보를 보내는 사람. 일반적으로 송신자가 암호화를 해서 정보를 보내게된다.

수신자 : 정보를 받는 사람. 일반적으로 수신자가 복호화를 하게된다.

키(key) : 암호화 하거나 복호화 하는데 사용되는 값, 파라미터

암호키 : 암호화를 위해 사용되는 키값

복호키 : 복호화를 위해 사용되는 키값

◈보안서비스의 목표(ITU-T X.800)

1. Authentication(인증) : 전송된 데이터가 요구된 데이터가 맞음을 확인하는 것. 불법자가 정당한 사용자로 오인되선 안된다. 전자상거래가 발달하면서 개인정보에 대한 인증은 더욱 부각받는 사항이다.

2. Access control(접근 제어) : 인증되지 않은 행동에 대해 정보(또는 자원 등의) 이용을 제한하는것. 리눅스의 사용자권한도 접근제어의 한 예라고 할 수 있다.

3. Confidentiality(기밀성) : 암호화를 하는 이유. 정보가 제 3자에게 노출되어선 안된다.

4. Integrity(무결성) : 정보가 제 3자에 의해 변경될 수 없어야함.

5. Non-repudiation(부인 봉쇄) : 어떤 정보에 관한 행위를 증명할 수 있는 증거를 수집, 유지, 확보하여 부인할 수 없도록 하는것.

6. Availability(가용성) : 권한을 가진 사람이 원하는 때에 정보를 얻을 수 있어야함.

◈해커의 암호공격방법

1.보안공격

-수동적 공격 : 스니핑, 트래픽 분석

-능동적 공격 : 스푸핑, 인젝션공격, 삭제공격, 재생공격..

2. 공격방식

-암호단독공격(ciphertext only attack) : 오로지 암호문 만을 가지고 평문이나 키값을 찾아내는 방법으로, 평문의 통계적 성질, 문장의 특성 등을 추정하여 해독

-기지평문공격(known plaintext attack) : 공격자가 일정한 평문에 대한 암호문을 알고있을 때, 스니핑한 암호문에 대해서 암호화 방식을 추론하여 공격하는 방법.

-선택평문공격(chosen plaintext attack) : 암호방식을 알고있을 때, 평문을 추측하여 암호화 해본 뒤 비교해가며 실제 평문을 추정해가는 공격방식. 

-선택암호문공격(chosen ciphertext attack) : 복호화 방식을 알 때 키값을 추정하여 복호화 하는 방법(공개키 암호화의 경우 이 방식이 쓰임)

◈고전, 현대 암호화 방식들을 보기전에..  알아야할 기본적인 정수론 (선택사항)

1. Divisibility and the Greatest Common Divisor(gcd)

 두 정수 a와 b가 있을 때 b = a·c인 정수 c가 존재하면 a는 b의 약수(divisor)라 하고, b를 a의 배수라고 한다. 이를 

                                             a|b

라고 표현한다.

  정수 d가 a와 b의 약수라면 (d|b and d|a) d를 a와 b의 공약수(common divisor)라고 하며, 이때 가장 큰 정수 d를 최대공약수(the Greatest common divisor)라고 한다. 이때 d를 d=gcd(a,b) 혹은 간단하게 d = (a,b)라고 표현한다. 그런데 이때 d가 1이라면 a와 b를 '서로소' 라고 표현한다.

 정수론에서는 소수의 활용이 중요한데, 소수(prime)란 1과 자기자신 외엔 약수를 가지지 않는 수이다. 반대로 소수가 아닌 수를 합성수(composite)라고 하고 모든 합성수는 소수들의 곱으로 표현할 수 있다.

 gcd를 구하는 방법으로는 유클리드의 호제법이 가장 일반적이다.(그냥 유클리드 알고리즘이라 말하기도 한다.)

두 정수 a, b가 있을 때, a>b라면,

a = q₁*b + r₁

b = q₂*r₁ + r₂

r₁ = q₃*r₂ + r₃

       .........

r(n-2) = qn*r(n-1) + rn //이때 rn = gcd(a,b) 이다.

r(n-1) = q(n+1)*rn + 0 //괄호안의 수는 밑첨자임..  밑첨자 n은 어떻게하는지 모르겠다.)

2.modulo & congruences

...
 

그 외에 몇가지 더 있지만, 정수론 포스팅이 아니니.. 정보의 바다를 이용하길 바란다.(꼭 필요한 사항은 아니니): ∮(), modulo & congruences, chinese remainder, successive squaring, 등등..

◈암호화의 큰 분류

1. 블럭 암호 : 블럭단위로 잘라서 암호화하는..

2. 스트링 암호 : 스트링 그대로 암호화 하는..

3. 대칭키 암호 : 암호키와 복호키가 같은..

4. 비대칭키 암호 : 암호키와 복호키가 다른..

◈고전 암호화 방식들(간략하게..)

▶전치암호(transpose cipher) : n*m개의 문자열을 m개씩 끊어서 n x m 행렬을 만들어 세로로 읽는(전치시키는) 암호화 방식.

 대표적인 예로는 가장 오래된 암호화 방식인 Scytale암호법이 있다.

▶치환암호(permutation cipher) : 문자열을 일정한 갯수만큼 나눈 후, 그 속에서 일정한 방식으로 뒤섞는 암호화방식.

▶덧셈암호(additive cipher) : 평문의 문자들에 일정한 수 만큼 더한 문자로 대치시키는 암호법. 문자를 움직이기때문에 shift cipher라고도 한다.

 a=1, b=2, c=3...  이라고 했을 때, 2씩 더해서 a=3, b=4, c=5...이런식으로 변한다. 수식으로 표현하면, 평문 S, 암호문 C, 키값 n 이라 할때 C = (S + n)(mod d) (여기서 d는 문자 종류의 수). 합암호는 복호화를 위해서 암호키인 n의 d시계 상에서의 역원인 -n(mod d) 를 구하면 된다. 

 대표적인 예로는 시저암호가 있다. 

▶곱셈암호(multiplicative cipher) : 덧셈암호와 비슷한 방식이지만, 더하는게 아니라 곱해주는 방식. 조금 복잡한 점은 복호화를 위한 키값을 구해야 하는것인데..  곱셈암호에 사용한 암호키의 역원이 복호키가 되는것이다. 덧셈암호의 경우 역원을 구하기 쉬웠지만, 곰셈암호의 경우 살짝 길다.

 먼저 암호키 n 과 모듈시계를 결정하는 문자의 종류 d가 있다고 하자.(d의 경우 알파벳이라면 26이겠죠.) 그렇다면, 덧셈암화와 비슷하게 암호문 C는 평문 S에 대해서 C = S*n(mod d)라는 식을 갖는다. 여기서 n의 d시계상에서의 역원인 m을 구하면, S = C*m(mod d) 가 된다.

 그럼 m을 구해보자. 우선 n에 대해서 gcd(d,n) = 1이 성립해야 d시계상에서 n의역원이 존재할 수 있다. 그 후 역원인 m을 찾으면 n*m = 1(mod d) 라는 식으로 역원임을 확인할 수 있을것이다. m은 gcd(d,n)을 구하기 위한 유클리드 알고리즘 과정을 역탐색 하여보면,,  1 = (d*x) + (m*n)  (단 x는 임의의 정수) 이라는(혹은 비슷한) 식을 구할 수 있고, 이때 이 식을 d시계상에 적용해보면, 1(mod d) = m*n 이라는 결과를 얻을 수 있다.

 과정 자체는 덧셈암호보다 복잡해 보이지만, 암호키에 의한 복호키의 범위가 덧셈암호보다 훨씬 적기때문에 오히려 덜 안전한게 단점이다.

◈현대 암호화 방식들

◇대칭키 : 

1, 대칭키 블럭암호 : DES, AES

....(추후정리)

◇비대칭키 :

1. 공개키 암호화 방식 : RSA

서로다른 개인키와 공개키를 사용해서 암호화 및 복호화를 하는방식.

공개키로 암호화를 하고, 개인키로 복호화를 한다.

1. p와 q라고 하는 두 개의 서로 다른 (p≠q) 소수를 고른다.

2. 두 수를 곱하여 N = pq을 찾는다.

3. φ(N) = (p-1)(q-1) 를 구한다.

4. φ(N) 보단 작고, φ(N)와 서로 소인 정수 e를 찾는다.

5. 유클리드 호제법을 이용하여 de≡1(modφ(N)) 을 만족시키는 d를 구한다.

이때 공개키는 N과 e가되고, 개인키는 d가된다.

암호화 

메세지 M을 N보다 작은 수로 변환하고(이건 공유하는 정보), 암호문 c는

 c = M^e (mod N)

인 c를 보내게된다.

복호화

M = c^d (mod N) 한 후 변환법의 역변환으로 평문을 구할 수 있다.