7. Public Key Cryptography

Symmetric Key Cryptography의 문제점

사용자 그룹의 사람이 많아지면 많아질수록 소유하고 있어야 하는 키의 개수가 점점 많아지게 된다. n명의 사용자가 있는 그룹의 경우 각 n(n-1)/2개의 키를 가지고 있어야 한다.

그렇기에 나온게 Asymmetric Cryptography

Asymmetric Cryptography

Public-Key Cryptography

2개의 키가 존재한다. public key(pk) and private key(=scret key, sk)
encryption과 decryption, signature generation과 signature verification을 할 때 키가 사용이 된다.

Public key: 제 3자에게 공개가 가능한 키.
Private key: 소유자 자신만 알고 있어야 하는 키.

Pk로 data를 encryption하고 data를 Sk로 decryption이 가능하다.

Sk로 data를 encrytpion과 같은 과정을 걸치고 그것을 Pk로 아무나 무슨과정을 했을 때 Sk로 했구나 ~ 아는 것이 signature이다.

그냥 실제로 우리가 하는 서명이라고 생각하면 편하다. 내가 서명한것을 누군가 무언가를 가지고 내가 했구나 인증이 가능한것과 비슷한것이다.

Public Key Infrastructure

공개키 암호 시스템이 잘 동작하기 위해서는 PKI가 잘 제공되어야 한다.
policies, processes, and software, certificates 포함

Certificate: 어떠한 한 사용자가 Pk, SK를 가지고 있을때 다른 사람에게 Pk를 공유 가능하고, 해당 키를 공유할 때 인증서와 함께 공유함으로써 자신의 Pk임을 인증, 증명이 가능하다. (유효기간 존재)
즉, 어떠한 사용자가 보낸 Pk인지 확인하기 위한것이 인증서이다.
어떤키가 엘리스로부터 온 키인지 확인하기 위한 것.

Digital Certificate

인증서를 발급해주는 기관을 신뢰함으로써 해당 기관에서 Pk의 주인을 엘리스다 라고 인증서를 통해 제공

인증서값들.
Issuer Name: 인증서를 발급해주는 기관
Subject Name: 엘리스
Public Key Information: 엘리스의 Public key
Signature: Issuer의 서명
과정: 기관을 신뢰하는 사람은 인증서를 검증할 때, 기관의 Pk를 미리 가지고 있고, Pk를 통해 Signature을 검증했을 때, 서명이 valid 할 경우, 그것을 통해 Subject Name, Public Key Information에 들어있는게 맞구나 하고 사용.
인증서: 어떤 Pk가 주어졌을 때, 이 공개키가 누구의 것인지 보장(보증)하기 위해서 사용되는 데이터 구조

공개키 암호기법을 통해 기밀성을 보장 가능 (Confidentiality)

Pk를 가진 누구나 암호화를 할 수 있지만, 암호화된 데이터를 풀 수 있는 사람은 오직 공개키에 대응되는 Sk를 가진 사람만 암호문을 해독 할 수 있다. (computationally infeasible)
그렇기에 데이터에 대한 Confidentiality를 보장하기 위해서 공개키 암호 기법을 사용할 때는 데이터를 공개키로 encryption을하고 Private Key로 decryption을 해야된다.

Authentication 인증

시그니처
Encryption과정에 Public key가 아닌 Private key를 사용하고 Decryption할 때 Private key에 대응하는 Public key를 사용하였을때 Plaintext가 같은 경우 정말 해당 시그니처는 해당 Private key로 만들어졌구나, 해당 사람이 보낸거구나 검증 가능.
시그니처를 만들 때는 Private key를 사용하고, 시그니처를 검증할 때는 Public key를 사용한다.

공개키 암호 시스템 (Public-Key Cryptosystem)

암호화/복호화:
송신자가 수신자의 공개키로 메시지를 암호화합니다.
수신자는 자신의 개인키로 복호화합니다.

전자 서명 (Digital Signature):
송신자가 자신의 개인키로 메시지에 서명을 합니다.
수신자는 송신자의 공개키로 서명의 유효성을 검증할 수 있습니다.

키 교환 (Key Exchange):
두 당사자가 협력하여 세션 키(일시적으로 사용하는 대칭 키)를 안전하게 교환합니다.

알고리즘의 적용성:
어떤 알고리즘은 위의 세 가지 기능 모두에 적합하고,
어떤 알고리즘은 한두 가지 기능에만 사용할 수 있습니다.

Pulbic-Key Requirements

Computationally easy:

• Public key를 통해 데이터를 암호화하는 것이 쉬워야 된다.
• Private key를 통해 데이터를 복호화 하는 것이 쉬워야 한다.

Computationally infeasible(불가능)

• 공격자에 대해서 Public key를 알고 있더라도 Private key를 구하는것이 불가능 해야된다.
• 공격자에 대해서 Public key + ciphertext를 알더라도 평문을 알아내기 어려워야 한다.

Need a trap-door one-way function
One-way function: Encryption을 하는것은 쉽고 Decryption하는 것은 어려워야 하는데
Trap-door (개구멍 같은 느낌): Private key를 알고있을 경우 평문을 구하기 쉽고, Private key를 알지 못 할 경우 평문을 구하기 어렵다.
전체적으로 한 방향은 쉽지만 다른 방향은 어렵다. 하지만 Trap-door을 통해 반대 방향도 쉽게 가능하게 할 수 있다.
여기서 Trap-door = Private Key

RSA

Factoring problem

n이 주어졌을 때 굉장히 큰 2개의 소수 곱으로 이루어져 있고, n이 어떤 2개 소수의 곱으로 이루어져 있는지 찾는 게 Factoring problem이다.
즉, RSA는 factoring problem에 대해서 안전성을 가진다.
-> n = p x q로 one-way function이다.
p,q가 주어졌을 때 n을 구하는 것은 쉽지만, n이 주어졌을 때, p와q를 구하는것은 어렵다.

RSA Algorithm

M = n보다 작음, e = Public key, d = Private key
n = p x q
Public key가 공개 될 때 n도 공개.

Exponentiation in Modular Arithmetic

Square-and-Multiply

a = 7인 상태임. 0일때 7 x 7 = 49 (mod 11)로 5임.
그렇기에 마지막 5 x 5 mod 11 = 5 x 5 = 25, 25 x 7 = 175, 175 mod 11 = 10임
binary값에 따라 1이면 Squre + multiply, 0이면 Square (log n 정도로 효율적)
bit 수만큼 연산 + 1인것 만큼 연산 즉, 7^560 (mod 561)경우 559번 연산을 해야되는것을 10 0011 0000 이니까 10 + 3(1인것) = 13번만에 계산 가능

Efficient Operation with Public Key

Public Key를 활용한 RSA algorithm의 속도를 증가 시키기 위해 사용되는데
Encryption, decryption 할 때, m^e mod n에서 e를 binary로 변경하고 1은 없는것이 이득이니 공개키를 미리 65537(2^16+1)과 같이 미리 세팅을 한다. 공개키를 먼저 알려주어도 d = e^-1 mod pi(n)으로 pi(n)값을 모르기에 상관이 없다.

RSA Problem

Public Key의 쌍 N과 e와 Ciphertext C = mod^e (mod n)이 주어졌을 때, 소인수분해를 하지 않고도 효율적으로 평문을 알아낼 수 있는지

Security of RSA

CCA attack: Chosen Ciphertext Attack으로 내가 원하는 Ciphertext를 가져왔을 때 그것을 평문으로 바꿔주는 오라클이 존재하고 그 오라클을 활용해서 하는 공격
이것을 RSA 알고리즘에서의 Homomorphism 활용해서 공격을 한다.
Homomorphism: 전체에 대한 연산의 값이 각각의 연산의 값과 동일하다

1. 랜덤 r (0 ~ n-1)값을 가지고 바로 c를 오라클에 넣을수는 없으니 r^e(공개키) x c 값 y를 오라클에 넣음
2. 오라클은 y에 대한 평문 y^d(비밀키)를 리턴
3. 보이는 것과 같음
4. 비밀키 없이 C에 대한 평문 m을 얻음. Textbook RSA -> CCA 공격에 취약
   
   OAEP를 활용해서 Textbook RSA를 안전하게 만듦
   RSA는 원천적으로 determinstic하다. C = m^e mod n 인데 e,n이 항상 동일하기에 동일한 Plaintext에 대해서 항상 일정한 Ciphertext가 나온다.
   OAEP를 활용하면 determinstic과 CCA 해결이 가능하다.

Message를 만들때 Message에 Padding을 추가하는 방법이다.
Seed값이 determinstic한 알고리즘에 Probabilistic 확률적특성을 부여.
encryption, decryption 모두 가능하다.

Diffie-Hellman Key Exchange

• 두 사용자가 안전하게 키를 교환할 수 있게 하는 것
  이렇게 받은 키는 나중에 대칭키 암호(Symmetric encryption)에 사용 됨.
• 이 알고리즘은 오직 비밀값을 교환하는 데에만 사용
  메시지를 암호화하거나 직접 보내는 역할은 하지 않는다.
• DLP의 안전성에 기반함.
  컴퓨터로 계산하기 매우 어려워서 보안이 유지된다.
  즉, 공개된 값만으로는 키를 알아내기 어렵다.
  
  비밀키는 각자 가지고 있고, 비밀키로 부터 공개키를 만듦.
  g^a mod p, g^b mod p를 서로 교환해서 각자 알고있는 비밀키로 지수승을해서 공통된 값을 얻어내는게 Diffie-Hellman Key Exchange이다.

가장 큰 문제는 Man-in-the-middle Attack(중간자 공격)

해결하기 위해서는 Bob이 뭔가를 받았을 때 엘리스의 공개키인지 아닌지 확인할 수 있으면 됨.
-> PKI에서 처음 나온 인증서의 역할.

ElGamal

Used in the digital signature standard(DSS)
RSA같은 경우에는 C = m^e 이런식이였지만,
ElGamal은 C = (c1,c2)와 같은 pair로 관리하는 매커니즘
DLP문제의 안전성을 기반으로 둠.

비밀키: d,
공개키 : p, e1, e2
e1 = generator
r은 랜덤값임. (like seed값)
이 알고리즘도 지수승을 하기에 determinstic한 특성을 가지고 있다. Probabilistic한 특성을 주기위해 Ciphertext를 pair로 보이는 매커니즘 사용.
c1, c2가 RSA에서의 OAEP에서 masking하는 느낌? (random값 = seed값)
Plaintext m = c2 x (c1^d)^-1 mod p

KPA attack

Known-plaintext attack
평문, 암호문 쌍을 미리 알고 있을 때 가능한 공격
공개키와 Random r 값이 동일한 경우
평문을 알아낼 수 있다.
=> 반드시 r값을 랜덤하게 사용해야 된다.

Elliptic Curve Arithmetic(ECC)

타원곡선
그룹연산으로 항등원과 역원이 반드시 존재해야 됨.

P + Q:
P,Q라는 점이 타원곡선 위에 주어졌을 때, 서로 다른 값에 대해 덧셈연산은 P,Q를 지나는 직선의 방정식을 그어서 만나는 점에 X축 대칭한 것이 P,Q의 연산 결과이다.


P + P:
P에서의 접선을 구하고 그것을 X축 대칭한 값이 P + P의 값이 된다.
기울기: y^2 = x^3 + ax + b을 미분.

O: 무한원점
항등원: 덧셈 연산을 했을 때 자기자신이 나오게 만드는 값
역원도 존재함.
만약에 10P를 구해야 되는 경우 쉽게 10P를 구할 수 없고, P + P 를 통해 2P, 2P + 2P = 4P, 4P + 4P = 8P, 8P + 2P = 10P를 통해 10P를 구할 수 있다.
어떠한 점 P가 주어졌을때 10 x P해서 10P를 구하는것이 아닌, P점에서 접선의 방정식을 통해 만나는 점에 X축 대칭, 또 거기서 X축 대칭 ~ 이런 과정을 통해 10P를 구할 수 있다.

이것을 point addition에서의 DLP이라고 한다. (Elliptic Curve Discrete Logarithm Problem, ECDLP)

ECDLP: Q, P가 주어졌을 때, Q = dP(P = (x,y))로 P를 d번 더하는것으로 d를 구하는 것이 ECDLP 문제이다. Q를 몇 번 더해야 Q가 되냐?
-> 진짜 P를 Q가 나올때 까지 계속 돌려봐야 한다.
-> BF밖에 효율적인 알고리즘이 없다.
-> Computationally Secure하다.
-> ECDH가 TLS에서 그렇고 키교환 알고리즘에서 많이 사용됨. 일일이 하나하나 다 하지 않을 경우 효율적으로 할 수 없는 방법이 없음.

192 = 비밀키가 192bit. 2^192번 공격해야 뚫을 수 있음.
동일한 레벨에 대해 RSA의 경우 모듈러 n사이즈가 7680bit여야 하지만 ECC에서는 384bit만으로도 안전성을 제공할 수 있음.
임베디드나 리소스가 부족한 경우 메모리 공간이 부족한 경우 384bit만으로도 키를 저장할 수 있음.
-> RSA대비 공간적인 측면에서 효율적이고 연산적인 측면에서도 효율적이다.

mod는 x좌표의 원소를 유한하게 제한 하기 위한 것이다.