[고려대 정보보호대학원] 암호수학

목차

 

1. 암호학 개론

2. 정수론

3. 암호수학과 암호 응용

4. 대수학

---

중점분야

• 소수, 서로소, mod 연산, 합동
• 유클리드 알고리즘
• 페르마 정리/오일러 함수
• 중국인의 나머지 정리
• 유한체 연산 : 다항식 간의 사칙연산

※필자의 경험결과, 암호수학은 정수론과 관련이 깊다.

---

Algebric (대수학) : 수학 구조의 일반적 성질을 연구하는 분야

 

정수의 표현방법 ( b 진법 )

1.공약수

(Def)

e|a, e는 a의 약수이다.

 

2.Euclidean Algorithm

(Theorem)

만일 A,B가 정수이고 A=BQ+R (Q,R은 정수) 이면,
gcd(A,B)=gcd(B,R) 이다.

gcd(작은 피제수,나머지)
나머지가 0이 될 때의 피제수 = gcd(A,B)이다

 

(Proof)

①gcd(A,B)= G
②gcd(B,R)=G' 이라하고
G=G' 임을 보이자.

①gcd(A,B)=G 에 따라, A=aG, B=bG 라고 하자. (a,b는 서로소)
이 때, A=BQ+R 이므로, aG=bGQ+R 이다.
R=G(a-bQ) 이고, ②gcd(B,R)=G' 에 따라서, 
G=G'임을 보이기 위해, b와 a-bQ는 서로소임을 보이면 된다.

귀류법을 활용하여, b=mk , a-bQ=nk라고 하자 (k≠1).
이 때 a-bQ=a-mkQ=nk 이므로, a=k(mQ+n)이다.

a,b가 서로 공약수 k를 가지는데 k≠1 이므로, ①의 a,b는 서로소라는 가정에 모순이다.
따라서 k=1이고, b와 a-bQ는 서로소이다. 그 결과 G=G'이 된다.

 

3.Extended Euclidean Alogrithm

(Theorem)
gcd(a,b) = G =  sa + tb 를 만족하는 , s와 t 찾기

확장 유클리드 알고리즘을 이해하기 위해서는 먼저 베주항등식(Bézout's Identity) 을 알아야 한다.

베주 항등식

적어도 둘 중 하나는 0이 아닌 정수 a,b가 있다.
gcd(a,b)=d 라고 할때, 아래 3 명제가 성립한다.

1. ax+by=d=gcd(a,b)를 성립하게 하는 x,y가 반드시 존재한다.
2. d=gcd(a,b)는 ax+by로 표현할 수 있는 가장 작은 자연수 이다.
3. ax+by로 표현되는 모든 정수는 d의 배수이다.

 

베주항등식 Proof

1. ax+by 로 표현 할 수 있는 가장 작은 자연수가 존재함을 밝힌다. 그것을 d라고 한다.
2. d는 a와 b의 공약수임을 보인다.
3. a와 b의 공약수는, d의 약수가 되어야 함을 보인다.

먼저 둘 중 하나는 0이 아닌 정수 a,b에 대하여
집합 S를 다음과 같이 정의한다.
S= ax+by >0 | x,y ∈Z

집합 S는 위 정의에 따라 자연수의 부분집합이고, S가 공집합이 아니라면
자연수의 정렬성에 따라 가장 작은 값의 원소를 가진다.

※자연수의 정렬성(Well Ordering Principle)
쉽게 말하면, 공집합이 아니면 S 안에는 원소가 있다.
원소가 1개 있으면 그 1개가 가장 작은 값이 될 것이고,
2개 있으면 min(a,b) 해서 둘중 하나는 반드시 가장 작은 값이 될 것이다.
이런 식으로 공집합이 아닌 S에 대해 반드시 가장 작은 값의 원소가 존재한다는 것이다.
증명은 귀류법으로 가능하다.

다시 1로 돌아와서, S가 공집합이 아님을 제일먼저 보여준다.
S= ax+by >0 | x,y ∈Z 이므로,

if a>0:
    a*1+b*0=a ∈ S (x=1,y=0)
if a<0:
   a*-1+b*0=|a| ∈ S (x=-1,y=0)
 if a==0:
    b !=0, b∈ S (S는 >0 인 집합 이므로)

이렇게 |a| 또는 |b| 적어도 한개는 S의 원소이다.

2.이제부터, ax+by로 표현될 수 있는 가장 작은 자연수를 d 라고 하고 d가 a,b의 공약수임을 보인다.
S 집합의 정의에 의해 d=ak+bl 이라고 표현될 수 있다.

S 내 임의의 원소를 x 라고하면, 나눗셈 정리에 의해
x = dq + r (0≤r＜d) 라고 표현 될 수있다.
이 때, x는 d의 배수가 아니라고 가정하고 (귀류법, r==0)
x 또한 S내 임의의 원소이므로, x=au+bv 로 표현 될 수 있다.

r==0이라는 가정에 따라, 위의 식들을 r에 대해서 정리해준다.
r= x-dq = (au+bv)-dq = (au+bv)-(ak+bl)q
 = a(u-kq)+b(v-lq) ∈ S

r을 ax+by 형태로 나타낼 수 있고 그 결과, r은 S의 원소가 된다.
그런데, (0≤r＜d) 이 조건과, 가장작은 자연수는 d 라는 조건에 따라서
본 가정은 모순이다.
따라서 r!=0 이 되고, x는 d의 배수가 된다.
따라서, 집합 S에는 |a|또는|b|가 반드시 존재하고, 가장 작은 자연수인 d 또한 존재한다.
가장 작은 자연수인 d와, x는 d의 배수라는 점에서 |a|또는|b|는 반드시 d의 배수가 된다.
따라서 d는 a와 b의 공약수이다.

3. gcd(a,b)=G 일 때, a=Gz , b=Gx 이라 하면, (최대공약수가 존재할때)
d=ak+bl = Gzk+Gxl = G(zk+xl) 이므로, d는 G의 배수가 된다.
d는 G의 배수이면서, 동시에 a,b의 공약수이고, 가장작은 자연수인 d 이므로
d는 G가 된다.

정렬성의 원리

(Proof) 확장유클리드 호제법

유클리드 호제법은 a=bq+r 일 때, gcd(a,b)=q = gcd(b,r) 을 정의했다.

이에 따라서 a=bq+r
b=rq_1+r_2
......
r_(n-1) = r_n * q_n + r_(n+1) 이며, r_(n+1) 일때 알고리즘이 종료된다.

여기서 gcd(a,b)=G=r_n 이며
베주항등식에 따라 , d=ax+by 인 수가 집합 S 내에존재하고,

우리는 집합 S 내의 새로운 수 w_0 = a*1+b*0 = a , w_1= a*0+b*1=b 를 정의 할 수 있다.
이 때, w_0과 w_1 은 모두 가장 작은수 d의 배수이며, d는 동시에 최대공약수 G이자, r_n이므로

r_n=a*s_n + b*t_n 으로 표현 될 수있다.

알고리즘 종료 조건에 따라, r_(n+1) =r_(n-1) - r_n * q_n 를 정의할 수 있으며
이를 s_n과 t_n으로 풀어낼 수 있다.

r_(n+1) = a*s_(n+1) + b*t_(n+1)    ... (좌식)
r_(n-1) - r_n * q_n = a* { s_(n-1) - s_(n)*q_n } + b*{ t_(n-1) - t_(n)*q_n } ... (우식)

좌식과 우식에 따라서
r_(n+1) =r_(n-1) - r_n * q_n
s_(n+1) =s_(n-1) - s_n * q_n
t_(n+1) =t_(n-1) - t_n * q_n
이고, 초기조건에 따라
w_0 = a , s_0=1 , t_0=0
w_1 = b,  s_1=0 , t_1=0
이다.
iteration을 돌려서 G 값을 찾을 수 있다.

 

 

4. 서로소

gcd(a,b)=1 일 때, a와 b는 서로소(coprime) 이라고 한다.

5. 소수

양의 정수 p가 p>1 이고, p의 약수가 1과 자기자신 밖에 없을 때 p를 prime number 라고 한다.

 

6. Modular 연산

Mod 연산이 만든 집합 = 잉여계

• Z_n (완전잉여계) : S={r|r , 0≤r＜n}
• Z_n*(기약잉여계) : n과 서로소인 , 0이 아닌 정수 집함

Mod연산은 덧셈과 곱셈에 대해 닫혀있다.

곱셈의 경우, b^(-1)≡a mod(n) 이 되기 위한 필요 충분 조건은 gcd(n,a)=1이다.

 

7. 페르마의 정리

p 가 소수 일 때
a^(p-1) ≡ 1 (mod p)
a^p≡a (mod p)

 

8. 오일러의 정리

오일러 함수 φ(n) : len( Z_n* ) : 기약잉여계의 길이 : n과 서로소인 0이 아닌 집합의 길이

[성질]
* 소수 p 에 대해 φ(p) = p-1
* n=pq인 합성수에 대해 ,φ(n) = φ(p) * φ(q) 

[오일러의 정리와 페르마의 정리를 합치면]
a^φ(p) ≡ 1 (mod p)

 

9. 행렬

• Linear function :
                     - f(x+y)=f(x)+f(y)
                     - f(ax) =af(x) , f(0)=0 (원점을 지나야한다)
• Affine function : f(x) = ax+b (b=0 일때, linear 하다)

 

• Determinant : 행렬식의 역행렬 존재 여부에 대한 판별값을 함.
                     기하학 적으로 det(A)의 값은 Linear Transform의 Scale 을 의미한다.
                     따라서, det(A)=0 이 될 경우, 행렬 A 의 차원(dimension)은 감소하게 된다.

---

암호수학

 

1. 비대칭키(공개키)암호 (DES,AES 등등 ,,)

• 공개키 암호의 필요성 :  송신자와 수신자가 같이 쓰는 대칭키 암호를 사용하면, Sniffing 위협이 있음
• 대칭키 암호의 문제 해결하기 위한 수단으로
  - 1. 키 사전 공유 : nC2의 비밀키 개수가 많아지는 문제점
  - 2. 키 배포 센터(KDC) : n이 증가 될 수록 KDC의 부하가 증대됨

1. KDC는 난수 생성기로 세션키를 생성한다.
2. KDC는 DB에서 앨리스와 밥의 키를 꺼낸다
3. KDC는 앨리스와 밥의 키를 사용해 세션키를 암호화 하여 보낸다.
4. 앨리스와 밥은 각각 받은 암호화세션키를 복호화 한다.

• 
  - 3. 디피-헬만 키 교환
  - 4. 공개키 암호 사용
  이 있음
  
  

---

공개키 암호 : 암호화 키 와 복호화 키가 다름

• 인수분해문제 (IFP) : RSA, Rabin
• 이산대수문제 (DLP) : ElGamal
• 타원곡선 이산대수문제 (ECDLP) : ECC

 

 1. RSA 방식 

• 공개키 n ,e
• 개인키(비밀키) d

1. 서로다른 두 소수 p,q 선택
2. n=pq 계산
3. 공개키 e 선택 : gcd(φ(n),e)=1 
4. 개인키 d 계산 : de≡1 mod φ(n)


암호문 : c = m^e (mod n)
복호문(평문) : m = c^d (mod n)

--------------------------------
ed= kφ(n)+1

m^φ(n)≡ 1 ( mod n)
m^(kφ(n)+1) ≡ m (mod n)
--------------------------------

RSA는 매우 느리므로 효율적인 e는 3,17,65537 이 있다.
n의 비트수는 적어도 2048 비트가 되어야 한다 (p,q각각 1024비트)

 

 

2. ElGamal 방식

• y= g^x mod p 는 계산하기 쉬움
• x = log_g y mod p 는 계산하기 어려움

소수 p 와 generator g 선택
개인키 : x
공개키 : p,g,y

메시지 m , 난수 k 에 대해
암호문 C1 : g^k mod p
암호문 C2 : m y^k mod p
복호문 m = C2(C1^x)^(-1) mod p

---

대수학 : 군 , 환 ,체

• 군 : 아래 4가지의 성질을 만족하는 집합
  - 닫힘
  - 결합
  - 항등원
  - 역원
• Abelian group(Commutative Group) 가환군
  - 군(Group) + 교환 법칙 성립