2022. 4. 5. 14:37ㆍMajor`/정보보호개론
공개키 암호시스템
대칭키 암호시스템의 경우 Encrytpion & Decryption에서 사용되는 key가 동일한 암호시스템이다
하지만 공개키 암호시스템의 경우 Encryption & Decyption에서 사용되는 key가 서로 다른 암호 시스템이다
- Encryption Key : Public Key
- Decryption Key : Private Key
공개키 암호시스템은 "Trap Door - One Way Function"를 기본으로 하고 있다
단방향 함수의 목적은 "한쪽 방향은 쉽게 계산되지만 역으로 계산하려면 굉장히 힘들다"
- 1850 X 3957 = 7320450 : 단순 계산이므로 쉽다
- but 7320450 = A * B ?? 역으로 계산하게 되면 굉장히 힘든 계산이 된다
>> 따라서 역으로 계산 : "Trap Door"는 특별한 Private Key로 계산해야 한다
- 대칭키에서는 (P, C)로 평문/암호문을 표기했는데 공개키에서는 관행적으로 (M, C)로 평문/암호문을 표기한다
전자서명
1. Bob은 자신의 Private Key로 M을 암호화 한다
2. 이 의미는 "해당 메시지 M에 대해 전자서명을 할 수 있다"
3. 이렇게 서명된 암호문은 누구나 Bob의 Public Key로 접근을 할 수 있지만 그 전자서명을 실질적으로 사용할 수 있는 사람은 Bob뿐이다
>> 따라서 전자서명은 Bob의 Private Key가 없으면 읽을 수는 있지만 위조될 수 없다
배낭암호 : Knapsack Problem
배낭 암호시스템은 대표적인 NP-complete문제이다
- NP-Complete : Polynomial Time에 해결이 가능한지는 모르겠고 답의 존재유무의 확인은 가능한 문제
n개의 배낭에 담을 수 있는 무게 : W(0), W(1), ...., W(n)
요구되는 전체 무게 : S
>> 여기서 S를 충족시키기 위해서 배낭 W를 어떻게 조합해야 할까? : SubSet-Sum Problem
Example)
W : {62, 93, 26, 52, 166, 48, 91, 141}
S : 302
>> 62 + 26 + 166 + 48 = 302 :: a = {10101100}
General Knapsack(GK)는 풀기 굉장히 힘든 문제이다
but, Superincreasing Knapsack(SIK)는 꽤 쉽게 풀린다
>> SIK : 배낭의 무게가 오름차순으로 정렬 & 각 무게는 앞의 무게들의 합보다 반드시 크다
Example)
W : {2, 3, 7, 14, 30, 57, 120, 251}
- 배낭의 무게가 오름차순으로 정렬
- 각 무게는 앞의 무게의 합보다 크다
- SIK의 조건을 만족
S : 186
>> 120 + 57 + 7 + 2 = 186 :: a = {10100110}
Knapsack 암호시스템
1. SIK 생성
2. SIK를 GK로 변환
>> Public Key : GK
>> Private Key : SIK + "Conversion Factors"
- GK를 통해서 쉽게 암호화가 된다
- 물론 SIK를 통해서 쉽게 복호화도 가능하다
- but SIK없이 GK를 푸는 계산은 NP-Complete가 된다
일반적으로 GK는 풀기 힘든 문제이다.
따라서 누구나 볼 수 있는 Public Key를 GK로 설정해줌으로써 Public Key를 알아도 원래 M을 유추할 수 없도록 해줘야 한다.
하지만 C를 받는 Receiver입장에서는 C를 M으로 복호화해야하기 때문에 풀 수 있는 SIK + "Conversion Factors"로 복호화를 해주면 풀린다
Example)
1. SIK 생성
SIK : {2, 3, 7, 14, 30, 57, 120, 251}
m : 41
n : 491
- m, n은 서로소
- n은 SIK의 전체 합보다 크다
2. SIK를 GK로 변환
>> SIK[i] × m "mod n"
2 × 41 "mod 491"
- 82 mod 491 = 82
3 × 41 "mod 491"
- 123 mod 491 = 123
7 × 41 "mod 491"
- 287 mod 491 = 287
14 × 41 "mod 491"
- 574 mod 491 = 83
30 × 41 "mod 491"
- 1230 mod 491 = 248
57 × 41 "mod 491"
- 2337 mod 491 = 373
120 × 41 "mod 491"
- 4920 mod 491 = 10
251 × 41 "mod 491"
- 10291 mod 491 = 471
GK = {82, 123, 287, 83, 248, 373, 10, 471}
>> Public Key : GK= {82, 123, 287, 83, 248, 373, 10, 471}
>> Private Key : SIK + "Conversion Factors"
= SIK {2, 3, 7, 14, 30, 57, 120, 251} & "Conversion Factors" : m-1 mod n = 41-1 mod 491 = 12
"Alice의 (공개키, 개인키)를 위에서 구한 (GK, SIK + "12")라고 가정하자"
Bob → Alice에게 보낼 M을 암호화 할 때는 "Alice의 공개키"로 암호화 해야 한다 (상대방의 공개키로 암호화)
M = 10010110
1. 그러면 여기서 Bob은 Alice의 공개키를 통해서 M을 C로 암호화해야 한다
>> 10010110 -- {82, 123, 287, 83, 248, 373, 10, 471}
82 + 83 + 373 + 10 = 548
따라서 Bob은 Alice에게 C = 548을 보내게 된다 (M : 150 → C : 548)
2. C를 받은 Alice는 본인의 개인키 + "Conversion Factors"를 이용해서 복호화를 진행
C · "Conversion Factor" mod n
= 548 · 12 mod 491
= (57 X 12) mod 491 = 193 mod 491
>> 193 = 2 + 14 + 57 + 120
따라서 {2, 3, 7, 14, 30, 57, 120, 251}에서 찾아내면 "10010110"이라는 원래 M을 복호화할 수 있다
>> 하지만 이러한 Knapsack 암호시스템은 이미 "Apple II Computer"에 의해 깨졌기 때문에 안전한 암호 시스템이 아니다 ("Lattice Reduction"를 사용한 공격)
RSA (Rivest & Shamir & Adleman)
RSA의 보안성은 "위의 예시처럼 인수분해가 굉장히 어렵다"라는 사실에 근거하고 있다
- 인수분해는 NP-Complete Problem인지 여부조차 알려져 있지 않다
RSA의 공개키 & 개인키 생성
1. 2개의 큰 "소수 p, q"를 선택하고 N = pq를 계산한다
2. (p-1)(q-1)에 서로 소인 e를 선택하고 "ed = 1 mod (p-1)(q-1)"인 d를 찾기
- d는 e의 modular inverse이다
- ed mod (p-1)(q-1) = 1
>> Public Key : (N, e)
>> Private Key : d
- N : modulo "N"
- e : 암호화 지수
- d : 복호화 지수
1. Bob은 Alice의 Public Key를 이용해서 메시지 M을 암호화 해야 한다
C = Me mod N
2. C를 받은 Alice는 본인의 Private Key를 이용해서 암호문 C를 복호화 해야 한다
M = Cd mod N
Example RSA)
p = 11 & q = 3
→ N = 33 & (p-1)(q-1) = 20
그리고 e = 3이라고 가정하자
e × d = 3 × d = 1 mod 20
따라서 d = 7이 된다
>> Public Key = (N, e) = (33, 3)
>> Private Key = d = 7
M = 8이라고 가정
디피-헬먼 : Diffie-Hellman
Key Exchange 알고리즘
- 어떠한 암호 알고리즘이 아니라 "키를 교환할 때 사용하는 알고리즘"이다
- 일반적으로 대칭키 암호를 공유할 때 사용한다
DH의 보안성은 "이산 로그"문제의 계산 난이도에 의존한다
g, x = gk가 주어졌다고 가정하자
우리는 k를 찾기 위해서 logg(x)를 계산해야 한다
이러한 계산은 이산을 기반으로 하고 이산 로그문제는 인수분해 문제처럼 풀기 굉장히 어렵다
과연 Attacker는 K를 찾을 수 있을까?
Attacker는 ga mod p & gb mod p는 알 수 있다
하지만 두개를 곱해도 gabmod p가 아닌 ga+b mod p가 나오기 때문에 이산 로그 문제를 풀기는 상당히 힘들다
하지만 DH 알고리즘은 "Man In The Middle (MITM)"공격에 취약하다
중간에서 Attacker가 이상한 값을 만들어서 전달해버리면 원래 전달하려던 키가 전달이 안되고 이상한 키가 전달이 된다.
이러한 MITM공격을 방지하는 방법은 다음과 같다
- 대칭키로 DH 교환을 암호화
- 공개키로 DH 교환을 암호화
- 개인키로 DH값 서명 (전자서명)
타원곡선 암호 : Elliptic Curve Crypto (ECC)
ECC도 마찬가지로 암호 시스템이 아니라, 공개키 암호 시스템에서 요구되는 복잡한 수학 연산을 수행하는 또 다른 방법 중 하나이다
- DH-ECC / RSA-ECC / .....
- ECC는 같은 수준의 보안성을 위해 필요한 비트 수가 적지만, 굉장히 복잡한 연산을 해줘야 한다
y2 = x3 + 2x + 3 (mod 5)라고 하고 (x, y)쌍을 찾아보자
1) x = 0
y = 0 → 0 mod 5 = 0
y = 1 → 1 mod 5 = 1
y = 2 → 4 mod 5 = 4
y = 3 → 9 mod 5 = 4
y = 4 → 16 mod 5 = 1
>> 해가 없다
2) x = 1
y = 0 → 0 mod 5 = 0
y = 1 → 1 mod 5 = 1
y = 2 → 4 mod 5 = 4
y = 3 → 9 mod 5 = 4
y = 4 → 16 mod 5 = 1
>> (x, y) : (1, 1) & (1, 4)
3) x = 2
y = 0 → 0 mod 5 = 0
y = 1 → 1 mod 5 = 1
y = 2 → 4 mod 5 = 4
y = 3 → 9 mod 5 = 4
y = 4 → 16 mod 5 = 1
>> (x, y) : (2, 0)
4) x = 3
y = 0 → 0 mod 5 = 0
y = 1 → 1 mod 5 = 1
y = 2 → 4 mod 5 = 4
y = 3 → 9 mod 5 = 4
y = 4 → 16 mod 5 = 1
>> (x, y) : (3, 1) & (3, 4)
5) x = 4
y = 0 → 0 mod 5 = 0
y = 1 → 1 mod 5 = 1
y = 2 → 4 mod 5 = 4
y = 3 → 9 mod 5 = 4
y = 4 → 16 mod 5 = 1
>> (x, y) : (4, 0)
결과에 의한 타원 곡선 상의 점 : (1, 1), (1, 4), (2, 0), (3, 1), (3, 4), (4, 0) ∞
Alice는 A = 15, Bob은 B = 22를 선정했다고 하자
## 공개정보 ##
y2 = x3 + 11x + 19 (mod 167), 점(2, 7)
EC상에서의 두 점을 더하는 방법을 알고 있으므로 덧셈을 반복함으로써 곱셈도 가능하다
이런식으로 반복해서 계산을 하게 되면
15(2,7) = (102, 88)
22(2,6) = (9, 43)
이 나오게 된다
따라서 Alice는 Bob이 보낸 (9, 43)에 본인의 비밀 승수 15를 곱한 15(9, 43)을 계산하면 (131, 140)이 나온다
Bob은 Alice가 보낸 (102, 88)에 본인의 비밀 승수 22를 곱한 22(102, 88)을 계산하면 (131, 140)이 나온다
따라서 계산 결과가 동일하므로 동일한 대칭키를 이용해서 적절한 비밀정보를 공유하게 된다
공개키 표기법
암호화 : {}
복호화 : []
Alice의 Public Key를 통해서 메시지 M을 암호화
>> C = {M}Alice
Alice의 Private Key를 통해서 암호문 C를 복호화
>> M = [C]Alice
>> M = [{M}Alice]Alice = {[M]Alice}Alice
공개키 암호 - 기밀성 & 무결성
Confidentiality : Public Key를 사용해서 Encrypt
Integrity : Private Key를 사용해서 Sign >> Digital Signature
전자 서명 (Digital Signature)
- Integrity 보장
- Non-Repudiation (부인 봉쇄)
Non-Repudiation
- 대칭키 암호에서는 제공할 수 없었던 공개키 암호만의 장점이다
- A가 전자서명을 본인의 private key로 생성해냈고 이 전자서명을 중요한 서류의 인증에 대해서 사용을 했는데 갑자기 A가 서류의 인증에 대한 증거가 어디있냐고 갑자기 부인을 한다
- 하지만 "전자서명"은 반드시 private key를 이용해서 생성이 되고 private key는 본인만 아는 key이므로 서류의 인증에 대한 부인은 절대 할 수 없다
Example 1)
Alice가 Bob에게 주식 100주를 사기 위해서 일종의 "주문서"를 제출했다
→ 여기서 Alice는 주문에 대한 Integrity를 확보하기 위해 "MAC"을 대칭키를 사용해서 계산했다고 가정
그러나 1주일이 지나고 주식 가치가 떨어지자 갑자기 Alice는 "나는 주문서를 제출하지 않았습니다"라고 주장한다
>> 여기서 Bob은 Alice가 주문서를 제출했음을 증명할 수 있을까?
No
왜냐하면 Alice가 보유하고 있는 대칭키는 Bob도 보유하고 있고, 그에 따라서 Bob이 해당 주문서를 위조했을 가능성도 존재할 수 있기 때문에 Bob은 증명할 수 없다
Example 2)
Alice가 Bob에게 주식 100주를 사기 위해서 일종의 "주문서"를 제출했다
→ 여기서 Alice는 주문에 대한 Integrity를 확보하기 위해 "전자서명"을 대칭키를 사용해서 계산했다고 가정
그러나 1주일이 지나고 주식 가치가 떨어지자 갑자기 Alice는 "나는 주문서를 제출하지 않았습니다"라고 주장한다
>> 여기서 Bob은 Alice가 주문서를 제출했음을 증명할 수 있을까?
Yes
왜냐하면 일단 전자서명이 존재한다는 의미는 어떤 사람이 본인의 Private Key를 통해서 전자서명을 생성했다는 의미이고, 따라서 Alice의 전자서명이 존재하고 전자서명은 Alice 본인이 직접 본인의 Private Key로 생성해야 하기 때문에 Bob은 Alice가 주문서를 제출했다고 증명할 수 있다
만약 Alice가 "Confidentiality + Non-Repudiation" 둘다 원한다고 하면
- Alice → Bob 메시지 전달
1. Sign → Encrypt
{[M]Alice}Bob
2. Encrypt → Sign
[{M}Bob]Alice
대칭키 vs 공개키
대칭키 암호 특징
- 속도가 빠르다
- PKI (Public Key Infrastructure)가 필요 없다
공개키 암호 특징
- 전자서명 : Non-Repudiation
- Private Key 공유 X
PKI : Public Key Infrastructure
공개키 암호를 안전하게 사용하는데 필요한 모든 것을 모아 놓은 것이다
전자인증서 (Digital Certificate) --- (공개키 인증서 or 단순 인증서)
사용자의 Public Key + 사용자의 이름을 포함
대부분의 인증서는 3rd party에서 활동하는 인증기관에 의해 서명되어야 한다
인증기관 (CA : Certificate Authority)
전자 인증서는 (TTP :Trusted 3rd Party)로 활동하는 CA에 의해서 서명되어야 한다
CA가 인증서에 서명을 한다는 의미는 해당 인증서에 존재하는 사용자가 인증서에 해당하는 Private Key를 보유하고 있다는 의미이다
하지만 인증서는 Public이므로, CA가 해당 인증서를 보유하고 있는 신원을 보증하는 것은 아니다
따라서 인증서를 받게되면 반드시 서명을 확인해야 한다
PKI Trust Models
1) Monopoly Model : 완전 독점 모델
모든 조직은 하나의 CA만을 사용한다
Monopoly Mode의 가장 중요한 단점은 "CA 자체가 매우 큰 공격목표가 된다"라는 사실이다
만약 독점적인 CA에 손상이 발생하거나 user가 CA를 신뢰하지 않으면 이러한 체계는 아무런 쓸모가 없어진다
2) Oligarchy : 소수 독점 모델
신뢰성 있는 CA가 여러 개있고 각 조직은 각각의 CA를 여럿이서 사용한다
3) Anarchy Model : 완전 자유 모델
이 모델은 "누구나 CA가 될 수 있다"
