[알고리즘] 7. 암호화 알고리즘

KOCW에서 제공하는 고려대학교 유용재 교수 알고리즘 강의를 듣고 정리한 글 입니다.

7주차 기초 정수론과 암호화 알고리즘

---

7주차. 기초 정수론과 암호화 알고리즘

 

1. 고전적 암호화 방법과 한계

1) 고전적 암호화 방법

(1) 시저 암호 Caesar Cipher

• 암호화 방식
  • ① 알파벳 A를 00으로, B를 01로, ... , Z를 25로 대응시킴
  • ② 평문에 모든 알파벳을 동일한 칸수만큼 미는 방식으로 암호화
  • ③ 알파벳이 26개이므로 26으로 나눈 나머지를 사용
• 예시

평문

K	O	R	E	A
10	14	17	04	00

13칸 미룬 암호문

X	B	E	R	N
23	01	04	17	13

 

(2) 아핀 암호 Affine Cipher

• 암호화 방식
  • 평문 P와 암호문 C에 대응하여 다음 방식으로 암호화
  • C ☰ K1P+K2 (mod 26)
  • K1 = 3, K2 = 2

 

2) 시저, 아핀 암호의 한계

: 시저 암호의 경우 26, 아핀 암호의 경우 26*26번만에 Brute-Force 공격으로 평문 유추 가능

 

2. 소인수분해 기반 암호 체계

1) 소인수분해 기반 암호 체계

(1) RSA 암호

암호화 방식

• 매우 큰 수의 소인수분해가 난해하다는 점에 기반한 암호체계
• 충분히 큰 소수 p와 q를 곱해 공개키 n결정
• e*d ☰ 1 (mod Φ(n))을 만족하는 공개키 e와 개인키 d를 결정
• 평문을 공개키 e로 암호화, 개인키 d로 복호화

 

소인수 분해 (펼치기)

오일러 파이 함수 Euler Phi Function

• 오일러 파이 함수
  • 자연수 n에대해 n보다 작으면서 서로소인 자연수의 개수를 Φ(n)으로 정의
  • 위 정의로부터, 임의의 소수 p에 대해 Φ(p) = p-1임 ( Φ(9) = 6 [1,2,4,5,7,8])
• 오일러 파이 함수 성질
  • 자연수 m과 n이 서로소인 경우 Φ(mn) = Φ(m)Φ(n)
  • 임의의 소수 p에 대해 Φ(p^k) = p^k - p^(k-1) (Φ(15)=Φ(3)Φ(5)=8, Φ(64) = 64-32 = 32)
• 오일러 정리
  • 자연수 a와n이 서로소라면 a^Φ(n)을 n으로 나눈 나머지는 1
  • 자연수 a와 n이 서로소라면 a^Φ(n) ☰ 1 (mod n)

 예시

Φ(9) = 6

17^6 ☰ 1 (mod 9)

 

Q. 오일러 정리를 이용해 17^40000 을 100으로 나눈 너머지를 계산하면?

a=17, n=100, 17과 100은 서로소

17^Φ(100)

Φ(100) = Φ(2^2 * 5^2) = Φ(2^2) * Φ(5^2) = (4-2)*(25-5) = 2*20 = 40

17^40 을 100으로 나눈 나머지 1

(17^40)^100 = 1^100 = 1 

 

RSA 암호

Φ(n) = Φ(pq) = Φ(p)Φ(q) = (p-1)(q-1)

 

예시)

p=3, q=5 -> n=15

Φ(n) = Φ(15) = Φ(3)Φ(5) = 2*4 = 8

e*d를 8로 나눈 나머지가 1이되는 두 조합 결정

e = 3, d = 11

 

예시(펼치기)

① n결정

p=11, q=7, n = 77

 

② e,d 결정

n=77 Φ(77) = Φ(7)Φ(11) = 6*10 = 60

e=37

ed=1(mod 60)  -> d=13

 

③ 암호화

평문 5, 공개키 37

5^37 ☰ 47 (mod 77) -> 암호문 : 47

 

④ 복호화

암호문 47, 개인키 13

47^13 ☰ 5 (mod 77) -> 평문 5

47^13 ☰ (5^37)^13 ☰ 5^481 ☰ 5*5^(60*8) ☰ 5*(5^Φ(77))^8 ☰ 5 mod 77

 

 

 

3. 이산로그 기반 암호 프로토콜 

1) Diffie -Hellman Protocol

• 이산로그 문제가 풀기 어렵다는 점에 기반한 암호체계
• 충분히 큰 소수 p 와 원시근 g를 결정
• 통신 참여자들은 각각 비공개 값 x를 정한 후 g^x mod p 를 상대에게 전송
• 상대로부터 받은 값을 밑으로, 본인이 정한 비공개 값을 지수로 해 모듈로 연산
• 결과적으로 통신에 참여하는 둘은 동일한 비공개 키를 공유하게됨 

 

소수에 대한 원시근 primitive root (펼치기)

원시근

x의 거듭제곱 값을 m으로 나눈 나머지로 가능한 값이 1, 2, ... , m-1일 때, x를 m의 원시근으로 정의 (m은 소수 일 때)

x mod m, x^2 mod m, x^3 mod m, ... , x^(m-1) mod m 이 전부 다른 값이라면 x는 m의 원시근

# Week 7

# Prim Root


def prim_root(num):
    ans = []
    # x
    for i in range(1, num):
        flag = 1
        mods = [0 for i in range(num+1)]
        # x^(1 ~ (m-1))
        for j in range(1, num):
            # print('x : ', i, ' / 지수 : ', j, ' / m = ', num)
            # print(i,'^',j,'mod',num, " : ", (i**j % num))
            if mods[i**j % num] == 1:
                flag = 0
                break
            else:
                mods[i**j % num] = 1
        if flag==1:
            ans.append(i)
    return ans

m = 11       
print(m, '의 원시근 : ', prim_root(m))

 

예시

① 소수 및 원시근 결정. p=23, g = 7. 소수p 와 원시근 g의 값은 모두에게 공개되어있음

② 암호화

A측) 임의의 자연수 선택 x=3

7^3 ☰ 21(mod 23) 이므로 B에게 21 전송

 

B측) 임의의 자연수 선택 y=6

7^6 ☰ 4 (mod 23), 4전송

 

③ 복호화

A측) 4^3 ☰ (7^6)^3 ☰ 18 (mod 23)

B측) 21^6 ☰ (7^3)^6 ☰ 18 (mod 23)

 

 

 

4. 암호 체계에 대한 공격 

1) RSA 암호 허점

• Brute-Force : 암호문 C에 대해 C, C^2, C^3... 시도하는 것 무리
• 소인수 분해 : n의 소인수 분해 성공 시(p, q)  e는 알려져있으므로 개인 키 d 얻을 수 있음. 그러나 p와 q는 매우 큰 수 이므로 성공하기 어려움

 

2) Diffie-Hellman 의 허점

• 이산 로그 공격 : 7^x ☰21인 지수 x를 찾은 경우 A, B의 공유 키 얻을 수 있으나, 이산 로그 풀기 어려움
• 중간자 공격 : A와 B에게 허위 값 전송 -> A와 공격자가 키 공유 +  B와 공격자가 키 공유