비대칭키 암호화란?
대칭키 암호화의 한계
대칭키 암호화에는 두 가지 근본적인 문제가 존재한다.
1. 키의 개수 문제
대칭키 암호화는 두 당사자 간에 비밀 키를 공유해야 한다. n명의 사용자가 서로 통신하려면 n(n-1)/2개의 키가 필요하다.
2. 키 분배 문제
비밀 키는 송신자와 수신자 모두 알아야 한다. 따라서 안전한 키 분배 프로토콜이 반드시 필요하다.
이러한 문제를 해결하기 위해 등장한 것이 바로 **비대칭키 암호화(Asymmetric Key Cryptography)**이다.
비대칭키 암호화의 원리
비대칭키 암호화는 **개인 키(Private Key)**와 공개 키(Public Key), 두 개의 서로 다른 키를 사용한다.
은행과 고객의 예시를 보면 이해가 쉽다.
- 고객들은 은행의 공개 키로 메시지를 암호화
- 은행은 자신의 개인 키로 메시지를 복호화
비대칭키 암호화는 **공개키 암호화(Public Key Cryptography)**라고도 불린다. 1976년 스탠퍼드 대학의 Whitfield Diffie와 Martin Hellman이 "New Directions in Cryptography" 논문에서 처음 소개했으며, 이들은 2015년 튜링상을 수상했다.
대칭키 vs 비대칭키
두 방식은 서로 대체 관계가 아닌 보완 관계이다. 실제로 두 방식을 함께 사용하는 것이 가장 효율적이다.
하이브리드 암호화: Digital Envelope
실무에서는 대칭키와 비대칭키의 장점을 결합한 하이브리드 방식을 사용한다.
송신 과정
- 평문을 대칭키로 암호화 (속도가 빠름)
- 대칭키를 수신자의 공개키로 암호화 (키 분배 문제 해결)
- 암호화된 메시지와 암호화된 키를 묶어서 Digital Envelope 생성
수신 과정
- 수신자의 개인키로 대칭키 복호화
- 복호화된 대칭키로 원본 메시지 복호화
RSA 알고리즘
RSA는 세계에서 가장 널리 사용되는 비대칭키 암호화 알고리즘이다. 1977년 Ron Rivest, Adi Shamir, Leonard Adleman 세 사람이 발표했으며, 이름은 이들 성의 첫 글자를 딴 것이다. 소수 이론(Prime Numbers)에 기반한다.
RSA에서 P와 Q는 최소 512비트, N은 최소 1024비트 이상이어야 한다.
간단한 예시로, P=7, Q=17이면 N=PxQ=119가 된다.
모듈러 연산
RSA를 이해하려면 모듈러 연산에 대한 이해가 필요하다. 모듈러 연산에서는 나머지 r만 관심 대상이다.
예시 풀이:
- c. -18 = -2 x 14 + 10
- d. -7 = -1 x 10 + 3
합동(Congruence)
암호학에서는 등호 대신 합동 개념을 자주 사용한다. 두 정수가 합동임을 나타낼 때는 합동 연산자(≡)를 사용한다.
합동의 성질은 다음과 같다.
오일러 파이 함수
오일러 파이 함수(Euler's Phi-Function) φ(n)은 암호학에서 매우 중요한 역할을 한다. **오일러 토션트 함수(Euler's Totient Function)**라고도 불린다.
이 함수는 n보다 작으면서 n과 서로소인 정수의 개수를 구한다.
n을 소인수분해하여 n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ로 표현하면:
φ(n) = (p₁^e₁ − p₁^(e₁-1)) × (p₂^e₂ − p₂^(e₂-1)) × ... × (pₖ^eₖ − pₖ^(eₖ-1))
매우 큰 합성수 n에 대해 φ(n)을 계산하려면 n을 소인수분해해야 한다. 즉, φ(n)을 구하는 어려움은 n의 소인수분해 난이도에 의존한다.
예제
- φ(13) = ? → 13은 소수이므로 φ(13) = 13 - 1 = 12
- φ(10) = ? → φ(10) = φ(2) × φ(5) = 1 × 4 = 4 (2와 5는 소수)
- φ(240) = ? → 240 = 2⁴ × 3¹ × 5¹이므로
- φ(240) = (2⁴ − 2³) × (3¹ − 3⁰) × (5¹ − 5⁰) = 64
- φ(49) = φ(7) × φ(7) = 36? → 아니다. 7과 7은 서로소가 아니다.
- φ(49) = φ(7²) = 7² - 7¹ = 42
오일러 정리
오일러 정리는 **페르마 소정리(Fermat's Little Theorem)**의 일반화이다.
- 첫 번째 버전: a와 n이 서로소이면 a^φ(n) ≡ 1 (mod n)
- 두 번째 버전 (RSA에서 사용): n = p × q, a < n, k가 정수일 때 a^(k×φ(n)+1) ≡ a (mod n)
두 번째 버전의 증명은 세 가지 경우로 나뉜다.
Case 1: a가 p의 배수도 아니고 q의 배수도 아닌 경우 → a와 n은 서로소
Case 2: a가 p의 배수이지만 q의 배수가 아닌 경우 (a = i × p)
Case 3: a가 q의 배수이지만 p의 배수가 아닌 경우 → Case 2와 동일한 방법, p와 q의 역할만 바뀜
오일러 정리를 활용한 거듭제곱 계산 예제
모듈러 역원 구하기
오일러 정리를 사용하면 모듈러 역원을 구할 수 있다. n과 a가 서로소이면:
a⁻¹ mod n = a^(φ(n)−1) mod n
RSA 알고리즘 상세
Step 4에서 개인키 D는 다음 조건을 만족하도록 선택한다:
(D × E) mod (P - 1) × (Q - 1) = 1
RSA 증명
오일러 정리의 두 번째 버전을 사용한다.
RSA 예제
Jennifer가 키 쌍을 생성한다.
- p = 397, q = 401
- n = 159197
- φ(n) = 158400
- e = 343, d = 12007
Ted가 Jennifer에게 "NO"라는 메시지를 보내려고 한다. (A=0일 때 N=13, O=14)
참고: ElGamal 암호화
ElGamal 암호화와 타원곡선 암호화(ECC)에 대한 내용은 교재를 참고하라.
메시지 다이제스트
메시지 무결성
암호화 시스템에서 기밀성(Confidentiality)은 중요한 목표이다. 하지만 때로는 기밀성보다 **무결성(Integrity)**이 더 중요한 경우가 있다.
문서의 무결성을 보존하는 한 가지 방법은 **지문(Fingerprint)**을 사용하는 것이다.
현실에서 직인 날인, 계인, 간인 등이 문서 위변조 방지에 사용되는 것과 같은 원리이다.
메시지 다이제스트 개념
문서/지문 쌍의 전자적 등가물이 메시지/다이제스트 쌍이다. 메시지 다이제스트는 **해시(Hash)**라고도 불리며, 메시지의 고유한 표현이다.
메시지의 무결성을 보존하기 위해 메시지를 **암호학적 해시 함수(Cryptographic Hash Function)**에 통과시킨다. 이 함수는 지문처럼 사용할 수 있는 메시지의 압축된 이미지를 생성한다.
두 쌍의 차이점:
- 문서와 지문은 물리적으로 연결되어 있다
- 메시지와 다이제스트는 분리되어 전송될 수 있다
- 가장 중요한 것은 메시지 다이제스트가 변경되지 않도록 보호해야 한다는 점
메시지 다이제스트의 원리
간단한 예시로 다이제스트 생성 과정을 이해할 수 있다.
해싱 연산을 통해 원본 메시지보다 크기가 작은 다이제스트를 생성한다.
메시지 다이제스트의 요구사항
- 메시지가 주어지면 다이제스트를 쉽게 계산할 수 있어야 하고, 항상 동일한 결과가 나와야 한다
- 다이제스트가 주어졌을 때 원본 메시지를 찾기 매우 어려워야 한다
- 서로 다른 두 메시지의 다이제스트는 서로 달라야 한다
다이제스트의 민감성
원본 메시지가 아주 조금만 달라도 다이제스트는 완전히 다른 값이 된다. 이것이 유일성을 보장하는 기반이다.
해시 함수
해시 함수의 특징:
- 임의 길이의 메시지를 고정 크기로 압축: h = H(M)
- 입력에 비밀 키가 필요 없음
- 일반적으로 해시 함수는 공개
암호학적 해시 함수의 요구사항:
- 일방향성(One-way property): 특정 해시에 매핑되는 데이터를 찾는 것이 계산적으로 불가능
- 충돌 저항성(Collision-free property): 동일한 해시를 갖는 두 데이터를 찾는 것이 계산적으로 불가능
역상 저항성 (Preimage Resistance)
Eve가 다이제스트 h(M)을 가로채고 메시지 M'을 생성한다면, Eve는 M'을 M인 척 Bob에게 보낼 수 있다.
제2역상 저항성 (Second Preimage Resistance)
Eve가 메시지 M과 다이제스트 h(M)을 가로챈다. Eve는 M' ≠ M이지만 h(M) = h(M')인 다른 메시지 M'을 생성한다. Eve는 위조된 메시지를 Bob에게 보낼 수 있다.
충돌 저항성 (Collision Resistance)
Eve가 동일한 다이제스트를 가진 두 개의 메시지를 처음부터 생성할 수 있다면? 예를 들어 유언장을 두 개 만들어서 나중에 위조된 유언장을 제출해도 다이제스트가 일치하므로 위조가 탐지되지 않는다.
해시 함수에 대한 공격
- 무차별 대입 공격과 암호분석이 존재
- 역상 또는 제2역상 공격: 주어진 해시 값과 같은 H(y)를 만족하는 y 찾기
- 충돌 저항성: H(x) = H(y)인 두 메시지 x, y 찾기
- 2^(m/2) 값이 무차별 대입 공격에 대한 해시 코드의 강도를 결정
- 128비트는 불충분, 160비트도 의심스러움
반복 해시 함수
암호학적 해시 함수는 임의 길이의 메시지를 고정 길이의 다이제스트로 만든다. 이를 구현하는 가장 좋은 방법은 **반복(Iteration)**을 사용하는 것이다.
Merkle-Damgard 구조
압축 함수의 두 가지 유형
1. 처음부터 설계된 해시 함수
- Message Digest (MD)
- SHA
2. 블록 암호 기반 해시 함수
- Rabin scheme
- Whirlpool (AES 기반)
Rabin Scheme
Merkle-Damgard 구조 기반이다. 압축 함수 대신 암호화 알고리즘을 사용한다. 메시지 블록이 키로 사용되고, 이전에 생성된 다이제스트가 평문으로 사용된다.
Whirlpool
Miyaguchi-Preneel 구조 기반의 반복 암호학적 해시 함수이다. 압축 함수 대신 대칭키 블록 암호를 사용하며, 이 블록 암호는 AES를 변형한 것이다.
SHA (Secure Hash Algorithm)
SHA는 1993년 NIST와 NSA가 설계했으며, 1995년 SHA-1로 개정되었다.
- DSA 서명 체계와 함께 사용하는 미국 표준
- 표준: FIPS 180-1 1995, Internet RFC3174
- MD4 설계를 기반으로 함
- 160비트 해시 값 생성
- 2005년 보안 결과로 인해 향후 사용에 대한 우려 제기
SHA 개정판
NIST가 2002년 FIPS 180-2 개정판 발표. SHA-256, SHA-384, SHA-512 세 가지 버전이 추가되었다.
- AES 암호가 제공하는 향상된 보안과 호환되도록 설계
- SHA-1과 구조와 세부사항이 유사
- 보안 수준은 더 높음
SHA-512 상세
개요
해시 함수는 역변환이 필요 없으므로 Invertibility가 필요하지 않다.
메시지 준비
- SHA-512는 원본 메시지 길이가 2^128 비트 미만이어야 한다
- 2^128 비트 메시지를 2^64 bps로 전송하려면 수년이 걸리므로 실질적인 제한이 아님
Step 1 & 2: 길이 필드와 패딩
예제:
- 원본 메시지가 2590비트일 때 패딩 비트 수는? → 354비트
- 패딩의 최소/최대 비트 수는?
- 최소 0비트: 마지막 블록이 896비트일 때. 128비트 길이 필드만 추가하면 됨
- 최대 1023비트: 마지막 블록이 897비트일 때. 897비트 패딩 후 새 블록 생성 필요
Step 3: 1024비트 블록으로 분할
SHA-512의 워드 확장
Step 4: 체이닝 변수 초기화
Step 5: 압축 함수
이것이 알고리즘의 핵심이다.
- 1024비트 블록 단위로 처리
- 80라운드로 구성
- 512비트 버퍼 업데이트
- 현재 메시지 블록에서 유도된 64비트 값 Wₜ 사용
- 처음 80개 소수의 세제곱근 기반 라운드 상수
각 라운드의 구조
Majority 함수 예제
버퍼 A, B, C에 Majority 함수를 적용한다. 최상위 16진수가 각각 0x7, 0xA, 0xE일 때 결과의 최상위 숫자는?
풀이: 이진수로 0111, 1010, 1110이다.
Conditional 함수 예제
버퍼 E, F, G에 Conditional 함수를 적용한다. 최상위 16진수가 각각 0x9, 0xA, 0xF일 때 결과는?
풀이: 이진수로 1001, 1010, 1111이다.
SHA-512 분석
512비트 다이제스트를 사용하는 SHA-512는 충돌 공격을 포함한 모든 공격에 저항성을 가질 것으로 예상된다.
MAC (Message Authentication Code)
메시지 다이제스트의 한계
메시지 다이제스트는 발신자를 인증하지 못한다. 발신자 인증을 제공하려면 본인임을 증명해야 한다.
암호학적 해시 함수로 생성된 다이제스트는 보통 **MDC(Modification Detection Code)**라고 부른다. 메시지 인증에는 **MAC(Message Authentication Code)**이 필요하다.
MAC의 개념
MAC은 메시지 다이제스트와 유사하지만, 추가로 암호화/복호화를 포함한다. 송신자와 수신자는 공유 비밀 키를 알아야 한다.
메시지 인증
메시지 인증이 다루는 것:
- 메시지의 무결성 보호
- 발신자의 신원 검증
메시지 인증은 메시지 변조와 같은 능동적 공격에 대응한다. 메시지의 적시성(지연 없음, 재전송 없음)도 검증할 수 있다.
대칭 암호화 단독으로는 데이터 인증에 적합하지 않다. 예를 들어 ECB 모드에서 블록 재정렬 공격이 가능하다.
기밀성 없이 메시지 인증만 필요한 경우:
- 브로드캐스트 메시지 (예: 네트워크 불가 메시지)
- 한쪽에 과부하가 걸려 모든 수신 메시지를 복호화할 시간이 없는 경우
- 평문 상태의 컴퓨터 프로그램 인증
MDC (Modification Detection Code)
MDC는 메시지의 무결성을 증명할 수 있는 다이제스트이다.
Alice가 Bob에게 메시지를 보낼 때, MDC를 생성하여 메시지와 함께 전송한다. Bob은 메시지에서 새 MDC를 생성하고 수신된 MDC와 비교한다. 동일하면 메시지가 변경되지 않은 것이다.
MAC (Message Authentication Code)
메시지의 무결성과 발신자 인증을 모두 보장하려면 MDC를 MAC으로 변경해야 한다. MDC와 MAC의 차이는 MAC에 Alice와 Bob 사이의 비밀이 포함된다는 것이다.
MAC이 보장하는 것:
- 메시지가 변조되지 않음
- 메시지가 발신자로부터 온 것임
- 메시지에 시퀀스 번호가 포함되어 있으면 적절한 순서 보장
- 인증 알고리즘은 역변환이 필요 없음 (암호화 알고리즘과 다름)
메시지 인증 방법
세 가지 방법이 있다.
1. 대칭 암호화 사용
2. 공개키 암호화 사용
3. 비밀 값 사용
비밀 값 방식의 장점:
- 암호화 소프트웨어는 상당히 느림
- 암호화 하드웨어 비용이 무시할 수 없음
- 암호화 하드웨어는 대용량 데이터에 최적화됨
- 암호화 알고리즘이 특허로 보호될 수 있음
Keyed Hash Functions as MACs
해시 함수 기반 MAC을 원하는 이유:
- 해시 함수가 일반적으로 더 빠름
- 암호학적 해시 함수 코드가 널리 사용 가능
초기 제안: KeyedHash = Hash(Key | Message)
하지만 이 방식에서 약점이 발견되어 결국 HMAC 개발로 이어졌다.
Nested MAC
HMAC
설계 목표:
- 해시 함수를 수정 없이 사용
- 내장된 해시 함수를 쉽게 교체 가능
- 해시 함수의 원래 성능을 크게 저하시키지 않고 유지
- 키를 간단하게 사용하고 처리
- 인증 메커니즘 강도에 대한 잘 이해된 암호학적 분석
HMAC은 인터넷 표준 RFC2104로 지정되어 있다.
HMAC_K(M) = Hash[(K+ XOR opad) || Hash[(K+ XOR ipad) || M)]
- **K+**는 크기에 맞게 패딩된 키
- opad, ipad(internal padding)는 지정된 패딩 상수
- 오버헤드는 메시지 단독으로 필요한 것보다 몇 번의 해시 계산만 더 필요
- MD5, SHA-1, RIPEMD-160, Whirlpool 등 어떤 해시 함수든 사용 가능
HMAC 개념
HMAC 단계별 과정
Step 1: K의 길이를 b와 같게 만들기
Step 2: K와 ipad를 XOR하여 S1 생성
Step 3: S1에 M 추가
Step 4: 메시지 다이제스트 알고리즘 적용
Step 5: K와 opad를 XOR하여 S2 생성
Step 6: S2에 H 추가
Step 7: 메시지 다이제스트 알고리즘 적용
HMAC 동작
디지털 서명
디지털 서명의 개념
송신자가 메시지 또는 그 지문을 자신의 개인키로 암호화한다. 이는 오직 송신자만이 이 메시지를 생성할 수 있음을 보장한다.
이것이 **부인 방지(Non-repudiation)**의 기반이다.
MAC의 한계와 디지털 서명
대칭키 또는 Alice와 Bob 사이의 비밀 값이 메시지 인증에 사용될 때, Alice가 MAC과 함께 메시지를 Bob에게 보내면 Bob은 Alice로부터 온 것이고 변조되지 않았음을 안다. 하지만 Alice는 메시지 전송을 부인할 수 있다. 부인 방지가 없다.
디지털 서명이 제공하는 기능:
- 작성자, 서명 날짜와 시간 검증
- 메시지 내용 인증
- 제3자에 의해 검증되어 분쟁 해결
디지털 서명은 발신자 신원 검증, 메시지 무결성, 부인 방지를 직접 제공한다. 메시지 기밀성을 위해서는 여전히 암호화/복호화가 필요하다.
신뢰할 수 있는 센터를 통한 부인 방지
부인 방지는 신뢰할 수 있는 제3자를 통해 제공될 수 있다.
디지털 서명에 기밀성 추가
디지털 서명은 프라이버시를 제공하지 않는다. 프라이버시가 필요하면 암호화/복호화 레이어를 추가해야 한다.
디지털 서명 과정
Step 1: 메시지 다이제스트 계산
Step 2: 디지털 서명 생성
Step 3: 메시지와 서명 전송
Step 4: 수신자가 자체 MD 계산
Step 5: 수신자가 송신자의 MD 추출
Step 6: 디지털 서명 검증
RSA 디지털 서명
RSA 디지털 서명 체계의 키 생성은 RSA 암호화와 동일하다. d는 비공개, e와 n은 공개이다.
HGU 전산전자공학부 고윤민 교수님의 24-2 컴퓨터 보안 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.