[암호학] Public Key Crypto (공개키 암호) (1)

Public Key Cryptography

두 개의 키

• 모두에게 open 하는 공개 키 (public key): 송신자가 사용한다. 상대방의 public key를 이용하여 암호화.
• 나만 아는 개인 키 (private key): 수신자가 사용한다. 자신의 private key를 이용하여 복호화.

trap door, one way function을 활용

• trap door: 비밀 정보를 아는 사람은 hard한 계산 과정이 가능해지고 비밀 정보를 모르면 hard함
• one way function: 한 쪽 방향 계산은 쉽지만 반대 방향 계산은 어려운 것. 예를 들면 소인수 분해.

공개키 방식을 이용하면 대칭키 방식에서 문제가 되던 키 공유 문제 해결!

전자 서명 제공

• 자신의 private key로 서명한다.
• private key로 만들어진 전자 서명을 public key로 검증한다.

Knapsack Problem

Knapsack

• 서로 다른 무게의 금괴를 최대한으로 가져오는 조합을 찾는 문제

주어진 금괴들 중 몇 개를 선택하여 합이 302가 되는 조합을 찾아야 한다.
푸는 방법: 모든 조합을 계산한다 -> 계산이 어려움!!

Superincreasing knapsack

• 4번째 금괴의 무게가 앞의 금괴 합보다 크면 Superincreasing knapsack 문제이다. -> 풀기 쉬워짐!

• 4번째 금괴인 30까지 합이 51보다 작다! -> Superincreasing knapsack 문제!
• 푸는 방법: 큰 것부터 넣는다.
• 251은 186을 초과해서 패스 그 다음 120, 57, 7, 2 이렇게 조합을 완성한다.

Knapsack Cryptosystem

Knapsack 알고리즘을 이용한 암호화 예시!
1) 앨리스는 superincreasing knapsack을 생성
2) 그게 private key가 된다.
3) 그것을 그냥 knapsack처럼 보이게 변환한다.
4) 변환한 게 publci key가 된다. 풀기 어려우니까!!

Modular Inverses

• mod 연산은 한정된 값으로 mapping 한다고 볼 수 있다.
• 예를 들면, mod 6 연산의 값으로는 0~5까지 있으니까 결국 0~5 중 하나의 값과 매핑한다고 볼 수 있다.

modular inverses

• 
• 3이랑 곱해서 mod 7을 하면 1이되는 수를 찾아야 한다 -> 5
• x, y가 서로소 관계면 modular inverse가 존재한다.
• 어케 구함? 최대공약수 알고리즘

Knapsack Example

1. 앨리스는 superincreasing knapsack인 weight를 쭉 만든다. -> private key
2. m과 n을 생성: n은 weight를 다 더한 것보다 크게, m은 n과 서로소가 되게 생성한다. m과 n도 private key 정보이다.
3. weight를 변환: w * m mod n = w'
   
4. 바뀐 weight가 public key가 된다. 일반적인 knapsack 문제처럼 보임! 즉 풀기 어려움!

구체적인 예시를 들어보자~

1) 위에서 말한 것처럼 앨리스는 private key인 가중치와 m, n을 생성했다.
2) 생성한 가중치를 변환한 것과 n이 public key가 된다.

3) 밥이 보내고 싶은 데이터(8bit)는 P = 10010110이다.
4) 앨리스의 public key 1, 4, 6, 7번 값을 더한다 -> 82 + 83 + 373 + 10 = 548
5) 548을 앨리스에게 전송한다.
6) 앨리스는 밥에게 받은 548이 대체 어떤 값들을 더해서 나온 것인지 풀어야 한다! 이렇게 끝나면 일반적인 knapsack 문제처럼 보여서 풀기 어렵지만 앨리스는 이 문제를 superincreasing 문제로 바꿀 수 있다! (trap door)
7) 푸는 방법: w * m mod n = w'
이뒤에이해가안감...............................질문하기

Knapsack Weakness

1. Trapdoor: 밥이 문제를 내는 건 쉽지만 트루디가 푸는 건 어렵다.
2. One-way: 트루디는 못 풀지만 앨리스는 superincreasing으로 풀 수 있다. 값을 아니까!
3. knapsack cryptosystem is insecure. 많이 쓰진 않았다. 나중에 lattice reduction 공격을 당했다.
4. 결론: general knapsck으로는 충분하지 않다!!

RSA

• 소인수분해 문제 기반 알고리즘
• N = pq 라고 할 때 pq로 N을 구하는 건 쉽지만 N을 보면서 pq를 구하는 것은 어렵다 -> 소인수분해는 풀기 어려움

과정을 살펴보자~
1. 앨리스의 키를 생성한다. 두 개의 소수 p와 q를 선택한다.
2. pq = N (이 때 p와 q는 외부 노출되면 안 되지만 private key는 아니다.)
3. (p-1)(q-1) 계산
4. 랜덤하게 e 선택. 이 때 e는 (p-1)(q-1)과 서로소여야 한다. modular inverse 존재를 위해!
5. e·d = 1 mod (p-1)(q-1) 가 되는 d 값을 찾자!

• public key is (N, e)
• private key is d

RSA 암호화 과정

• 밥은 메시지를 앨리스 public key를 이용하여 암호화 (C = M^e mod N)
• 앨리스는 자신의 private key로 복호화 (M = C^d mod N)

자자 과연 RSA는 트루디가 풀 수 있을까???

• 일단 트루디는 d 값을 알아야 메시지를 풀 수 있다. 근데 d 값을 알려면?

• e·d = 1 mod (p-1)(q-1) 이걸 풀어야 한다.

• 그러면 p랑 q를 알아야 한다. 근데 p랑 q를 알려면?

• N = p·q 즉, N으로부터 p와 q를 알아내야 한다. 이건 소인수분해 문제임! 따라서 N으로부터 p, q를 구하는 것은 어렵다 그래서 RSA는 굉장하다~

• 이건 오일러 정리로 증명할 수 있는데 넘어가자

RSA 예제

1. 키 생성

1) 앨리스는 두 개의 소수 p = 11, q = 3을 선택한다.
2) N = pq = 33
3) (p-1)(q-1) = 20
4) 20과 서로소가 되는 e = 3
5) e·d = 1 mod 20이 되는 d값을 구한다.
6) (3 * d) mod 20 = 1, d = 7이다.
7) 앨리스의 public key = (N,e) = (33, 3)이다. private key = d = 7이다.

2. 암호화

1) 메시지 M = 8
2) C = M^e mod N = 8^3 mod 33 = 17
3) 암호화된 메시지 17을 앨리스에게 전달한다.
4) 앨리스는 복호화를 진행한다.
5) C^d mod N = 17^7 mod 33 = 8 -> 원래 메시지와 일치한다!

More Efficient RSA

1. 차수가 커지게 되면 계산이 폭발적이게 된다 -> repeated squaring 알고리즘 사용하면 효율적으로 계산할 수 있다.
2. e = 3으로 정하면 너무 작아서 cube root attack이 가능하다. e가 드러날 수 있음. 되도록 3보다 크게 정한다. 보통 e = 2^16 + 1 을 사용한다.

RSA padding

• RSA만 사용하면 동일한 input에 대해 동일한 output이 나온다. 흠 조금 다르게 바꾸자 -> RSA padding 적용

• 메시지 뒤에 랜덤 숫자를 붙인다! 그러면 output이 다르게 나온다.
• padding은 OAEP 방식을 사용한다.