CSS 1타 강사 · CONCEPT 07/25
공개키 암호화와 전자서명은 왜 키 방향과 목표가 다를까요?
Public-key cryptography는 공개키와 개인키를 나눕니다. RSA의 핵심 난제는 큰 수의 factorization, ElGamal은 discrete logarithm 계열 문제입니다. RSA 암호화는 c=m^e mod n, 서명은 s=h^d mod n이며 서명의 목표는 secrecy가 아니라 authenticity와 integrity입니다.
전문 용어를 보기 전에 이 장면부터 잡으세요
공개키는 누구나 넣을 수 있는 우편함 투입구, 개인키는 소유자만 여는 열쇠입니다. 서명은 소유자만 찍을 수 있고 누구나 확인할 수 있는 도장에 가깝습니다.
암호화와 서명은 키 방향과 목표가 다릅니다
00
한 장면으로 문제를 시작해 봅시다
이번 페이지에서 끝까지 따라갈 예시
Bob에게만 읽히는 메시지를 보낼 때와 Alice가 작성자임을 모두에게 증명할 때를 비교합니다.
비유와 실제 시스템을 정확히 연결하기
- 누구나 넣을 수 있지만 Bob만 여는 우편함Bob public key encryption
- Alice만 찍을 수 있고 모두가 확인하는 도장Alice private key signature
- 도장 견본Alice public key verification
이 예시에서 사람·장치·데이터·화살표를 먼저 찾습니다. 아직 용어를 완벽히 몰라도 “누가 무엇을 가지고, 어떤 처리를 거쳐, 무엇이 달라지는가”를 말할 수 있으면 출발점은 충분합니다.
01
긴 이름을 작은 용어로 분리하기
한 제목에 여러 단어가 들어 있어도 같은 기능을 뜻하지 않습니다. 아래 카드를 하나씩 읽고 각 용어의 대상과 역할을 따로 잡으세요.
공개키 암호와 RSA·ElGamal의 수학적 기반
공개키 암호는 누구나 알 수 있는 public key와 소유자만 보관하는 private key를 사용한다. RSA에서는 두 큰 소수를 곱해 n을 만드는 것은 쉽지만 n만 보고 원래 소수들을 찾는 factorization이 어렵다는 점을 이용한다. ElGamal은 g^x mod p를 계산하기는 쉽지만 결과와 g, p만 보고 x를 찾는 discrete logarithm problem이 어렵다는 점을 이용한다.
TERMS FROM ZERO
공개키 암호와 RSA·ElGamal의 수학적 기반 핵심 용어
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Public key
누구나 알아도 되는 key로, 보통 encryption 또는 signature verification에 사용됩니다.
Private key
소유자만 비밀로 가져야 하는 key로, decryption 또는 signing에 사용됩니다.
Hard problem
정상 사용자는 비밀정보로 쉽게 계산하지만 공격자는 현실적 시간에 풀기 어렵다고 가정하는 수학 문제입니다.
Trapdoor
특별한 비밀정보를 알면 어려운 계산을 쉽게 뒤집을 수 있게 하는 정보입니다.
RSA 계산에 필요한 소수·φ·서로소·역원
소수(prime)는 1과 자기 자신으로만 나누어지는 2 이상의 정수다. RSA는 보통 서로 다른 소수 p와 q를 골라 n=pq를 만든다. Euler의 φ(n)는 1부터 n까지 중 n과 서로소인 수의 개수다. p와 q가 서로 다른 소수라면 φ(n)=(p-1)(q-1)이다. 공개 지수 e는 φ(n)과 최대공약수가 1이어야 하고, 개인 지수 d는 ed≡1 mod φ(n)을 만족하는 modular inverse다.
TERMS FROM ZERO
RSA 계산에 필요한 소수·φ·서로소·역원 핵심 용어
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Prime number
1과 자기 자신으로만 나누어지는 1보다 큰 정수입니다.
Euler φ function
n 이하에서 n과 서로소인 수의 개수를 나타내며 RSA key 계산에 사용됩니다.
Coprime
두 수의 최대공약수가 1인 관계입니다.
Modular inverse
`a·b ≡ 1 (mod n)`을 만족하는 b로, modulo 세계에서 나눗셈 역할을 합니다.
Digital signature는 무엇을 증명하는가
Digital signature는 메시지를 숨기는 기술이 아니라 메시지가 private key 소유자에게서 왔고 중간에 바뀌지 않았음을 검증하는 기술이다. 보통 긴 메시지 자체가 아니라 메시지의 hash에 서명한다. RSA의 단순 교재식 표현에서는 서명 s=h^d mod n을 만들고 검증자는 s^e mod n이 h와 같은지 확인한다.
TERMS FROM ZERO
Digital signature는 무엇을 증명하는가 핵심 용어
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
Digital signature
private key 소유자가 특정 메시지에 서명했음을 검증하게 하는 값입니다.
Signing
메시지와 private key로 signature를 만드는 과정입니다.
Verification
메시지, signature, public key로 서명의 유효성을 검사하는 과정입니다.
Authenticity / Integrity
서명은 서명자와 메시지의 진위를 확인하지만 메시지 내용을 숨기는 confidentiality 기능은 아닙니다.
TLS가 대칭키와 공개키를 함께 사용하는 이유
TLS는 HTTPS 연결에서 통신 상대를 확인하고 전송 내용을 보호하는 프로토콜이다. 공개키 암호(asymmetric cryptography)는 공개키와 개인키가 달라 키 교환과 서명에 편리하지만 큰 데이터를 처리하기에는 상대적으로 느리다. 대칭키 암호(symmetric cryptography)는 양쪽이 같은 비밀키를 사용하며 빠르다. 그래서 실제 TLS는 인증과 세션키 합의에 공개키 기술을 사용하고, 이후 데이터에는 빠른 대칭키 암호를 사용하는 hybrid 방식이다.
TERMS FROM ZERO
TLS가 대칭키와 공개키를 함께 사용하는 이유 핵심 용어
아래 단어는 이미 안다고 가정하지 않습니다. 먼저 쉬운 뜻을 읽고, 본문에서 같은 단어가 나오면 이 정의로 다시 바꾸어 읽으세요.
TLS
Browser와 server 사이 통신의 기밀성·무결성 및 server 인증을 제공하는 protocol입니다.
Hybrid encryption
공개키 기법으로 key를 합의하거나 보호하고, 실제 대량 데이터는 빠른 대칭키 암호로 처리하는 조합입니다.
Session key
한 연결이나 제한된 기간 동안 실제 application data 암호화에 사용하는 대칭 key입니다.
Handshake
암호 suite와 key material을 정하고 상대를 인증하는 TLS 연결 초기 단계입니다.
02
실제 시스템에서는 이 순서로 움직입니다
예시를 단계별로 해체하기
- 1단계각 사용자는 공개해도 되는 public key와 비밀인 private key를 만듭니다.
- 2단계기밀성에서는 sender가 recipient의 public key로 암호화합니다.
- 3단계recipient만 자신의 private key로 복호화합니다.
- 4단계서명에서는 signer가 message hash에 자신의 private key를 사용합니다.
- 5단계검증자는 signer의 public key로 signature의 authenticity와 integrity를 확인합니다.
- 6단계RSA는 factorization, ElGamal은 discrete logarithm 계열 난제에 기반합니다.
이 단계들은 시험 답안에서 원인과 결과가 빠지지 않도록 만든 설명 순서입니다.
손으로 따라가는 초보 예제
Bob만 읽게 하기와 Alice가 썼음을 증명하기
메시지 `PAY 10`을 Bob에게 비밀로 보내는 경우와 Alice가 작성자임을 공개적으로 증명하는 경우를 비교합니다.
- 1단계기밀성에서는 Alice가 Bob의 public key로 `PAY 10`을 암호화합니다.
- 2단계Ciphertext는 Bob의 private key를 가진 Bob만 복호화할 수 있어야 합니다.
- 3단계서명에서는 Alice가 자신의 private key로 message 또는 그 hash에 signature를 만듭니다.
- 4단계Bob을 포함한 누구나 Alice의 public key로 signature를 검증할 수 있습니다.
- 5단계Signature는 작성자와 변경 여부를 확인하지만 message 내용을 숨기지 않습니다.
- 6단계실제 scheme은 padding·randomness·parameter 검증이 필요하며 ‘private key로 암호화’라는 단순 문장만으로 설명하면 부족합니다.
그래서 무엇을 배웠나? Encryption은 수신자의 key pair로 confidentiality를, signature는 서명자의 key pair로 authenticity와 integrity를 목표로 합니다.
03
관련 개념도 하나씩 따로 이해하기
공개키 암호와 RSA·ElGamal의 수학적 기반
비유에서 실제 시스템으로 옮겨 보기
먼저 떠올릴 장면 · 두 색의 물감을 섞기는 쉽지만 섞인 색에서 원래 정확한 두 물감을 분리하기는 어려운 것처럼, 한 방향 계산은 쉽고 역방향은 어렵게 만든다.
정확한 뜻 · 공개키 암호는 누구나 알 수 있는 public key와 소유자만 보관하는 private key를 사용한다. RSA에서는 두 큰 소수를 곱해 n을 만드는 것은 쉽지만 n만 보고 원래 소수들을 찾는 factorization이 어렵다는 점을 이용한다. ElGamal은 g^x mod p를 계산하기는 쉽지만 결과와 g, p만 보고 x를 찾는 discrete logarithm problem이 어렵다는 점을 이용한다.
- 1단계Public key는 공개되어도 되고 private key는 비밀이어야 한다.
- 2단계RSA의 대표 난제는 integer factorization이다.
- 3단계ElGamal의 기반은 discrete logarithm과 관련 가정이다.
- 4단계구체적인 parameter 크기와 padding까지 올바르게 써야 실제 시스템이 안전하다.
RSA 계산에 필요한 소수·φ·서로소·역원
비유에서 실제 시스템으로 옮겨 보기
먼저 떠올릴 장면 · e로 자물쇠를 한 방향으로 돌린 뒤 d로 돌렸을 때 바퀴가 정확히 한 바퀴를 돌아 원위치에 오는 조합을 찾는다고 생각할 수 있다.
정확한 뜻 · 소수(prime)는 1과 자기 자신으로만 나누어지는 2 이상의 정수다. RSA는 보통 서로 다른 소수 p와 q를 골라 n=pq를 만든다. Euler의 φ(n)는 1부터 n까지 중 n과 서로소인 수의 개수다. p와 q가 서로 다른 소수라면 φ(n)=(p-1)(q-1)이다. 공개 지수 e는 φ(n)과 최대공약수가 1이어야 하고, 개인 지수 d는 ed≡1 mod φ(n)을 만족하는 modular inverse다.
- 1단계n=pq를 계산하고 p와 q가 유효한 소수인지 확인한다.
- 2단계p≠q이면 φ(n)=(p-1)(q-1)을 사용한다. p=q인 특수 입력은 φ(p²)=p²-p다.
- 3단계gcd(e,φ(n))=1인 e를 고른다.
- 4단계ed mod φ(n)=1이 되는 d를 찾는다.
- 5단계암호화 c=m^e mod n, 복호화 m=c^d mod n을 목적에 맞게 적용한다.
Digital signature는 무엇을 증명하는가
비유에서 실제 시스템으로 옮겨 보기
먼저 떠올릴 장면 · 편지 내용을 가리는 봉투가 encryption이라면 signature는 편지 내용에 연결된 위조하기 어려운 도장이다. 누구나 도장을 검사할 수 있지만 소유자만 새 도장을 만들 수 있어야 한다.
정확한 뜻 · Digital signature는 메시지를 숨기는 기술이 아니라 메시지가 private key 소유자에게서 왔고 중간에 바뀌지 않았음을 검증하는 기술이다. 보통 긴 메시지 자체가 아니라 메시지의 hash에 서명한다. RSA의 단순 교재식 표현에서는 서명 s=h^d mod n을 만들고 검증자는 s^e mod n이 h와 같은지 확인한다.
- 1단계메시지를 hash해 고정 길이 digest h를 만든다.
- 2단계서명자는 private key로 h에 대한 signature를 만든다.
- 3단계검증자는 public key와 원래 메시지로 signature를 확인한다.
- 4단계Selective forgery에서는 공격 전에 정한 특정 새 메시지에 대한 유효 서명을 만드는 것이 목표다.
TLS가 대칭키와 공개키를 함께 사용하는 이유
비유에서 실제 시스템으로 옮겨 보기
먼저 떠올릴 장면 · 처음 만날 때 신분증과 봉인된 절차로 둘만의 회의실 열쇠를 안전하게 정한 다음, 긴 회의 동안에는 그 열쇠로 빠르게 문을 여닫는 것과 같다.
정확한 뜻 · TLS는 HTTPS 연결에서 통신 상대를 확인하고 전송 내용을 보호하는 프로토콜이다. 공개키 암호(asymmetric cryptography)는 공개키와 개인키가 달라 키 교환과 서명에 편리하지만 큰 데이터를 처리하기에는 상대적으로 느리다. 대칭키 암호(symmetric cryptography)는 양쪽이 같은 비밀키를 사용하며 빠르다. 그래서 실제 TLS는 인증과 세션키 합의에 공개키 기술을 사용하고, 이후 데이터에는 빠른 대칭키 암호를 사용하는 hybrid 방식이다.
- 1단계Browser가 server의 certificate와 domain name을 검증한다.
- 2단계Handshake에서 양쪽이 session key를 합의한다.
- 3단계Application data는 합의된 대칭키로 빠르게 보호한다.
- 4단계암호화가 계산 시간을 없애거나 거래 내용을 절대적으로 안전하게 만들지는 않는다.
04
강의 스크립트 원본과 연결하기
RSA key generation·ElGamal·digital signature를 보여 주는 대표 슬라이드입니다. 먼저 위의 초보 설명을 읽고, 원본에서는 같은 개념이 어떤 기호와 독일어·영어 용어로 표현되는지 확인하세요.
Vorlesung/04 Asymmetrische Kryptographie.pdf · p.12, p.17, p.22 · RSA key generation·ElGamal·digital signature04 Asymmetrische Kryptographie.pdf· p.12, p.17, p.22
05
시험 함정과 답안에 적용하기
- 공개키 암호와 RSA·ElGamal의 수학적 기반 · ‘어려운 수학 문제 기반’이라는 말이 모든 작은 숫자 예제나 잘못 구성한 키까지 안전하게 만들지는 않는다.
- RSA 계산에 필요한 소수·φ·서로소·역원 · p=q인데 서로 다른 소수 공식 (p-1)(q-1)을 그대로 쓰거나, e와 d가 역원인지 확인하지 않고 숫자를 고르면 안 된다.
- Digital signature는 무엇을 증명하는가 · 서명은 confidentiality를 제공하지 않는다. 또한 교재의 raw RSA 계산은 개념 연습이며 실제로는 안전한 signature encoding이 필요하다.
- TLS가 대칭키와 공개키를 함께 사용하는 이유 · HTTPS가 오직 asymmetric cryptography만 사용한다거나, certificate가 있는 사이트는 정직한 상점이라고 단정하면 안 된다.
서술형 답안 골격
RSA는 n과 φ(n), gcd(e,φ(n))=1, ed≡1 mod φ(n)을 확인한 뒤 목적에 맞는 exponent를 선택합니다.
정의 → 등장 주체 또는 입력 → 작동 순서 → 보안 효과 → 조건과 한계 순서로 쓰고, 위 단계별 예시에서 필요한 문장을 골라 붙이세요.
책을 덮고 “공개키 암호화와 전자서명은 왜 키 방향과 목표가 다를까요?”에 대해 핵심 용어 두 개, 작동 단계 세 개, 대표 함정 하나를 말해 보세요.
다음 개념으로 넘어가기 전 확인
- Bob에게 비밀로 보낼 때 누구의 public key를 쓰는가?
- Alice의 서명을 검증할 때 어떤 key를 쓰는가?
- Signature가 confidentiality를 제공하지 않는 이유는?