3. 암호

암호기초

암호의 등장 및 정의

동기

• 어떻게 하면 메시지(데이터)를 원하는 상대방에게 안전하게 전달/저장할까?
  • 제 3자의 개입에도 메시지를 잘 전달/저장할 수 있게 하는 것이 필요 → 암호의 등장

 

암호학(Cryptography) 이란?

• 정보를 보호하기 위한 수학적, 언어학적인 방법을 다루는 학문

 

생활 속의 암호

• 비밀번호
• 전송 시 암호화 (SSL/TLS)
• 암호화폐 (Cryptocurrency)
• 전자상거래
• 공인인증서
• 개인정보보호법

---

암호 기초 용어

 

 

• 평문 (Plaing Text, P)
• 암호문 (Cipher Text, C)
• 암호화 (Encryption, E())
• 복호화 (Decryption, D())
• 키 (Key, K)
• 암호 알고리즘 (ex. cipher)

 

 

커코프 원칙 (Kerckhoffs's Principle)

• 암호 스키마의 안전성은 알고리즘이 아니라 키의 비밀성에만 의존해야 한다.
  • 키를 제외한 모든 암호체계가 알려지더라도 암호체계는 안전해야 한다.
• 암호 해독을 위해 알아야 하는 정보: 암호(복호) 알고리즘, 키

---

암호의 종류

• 전치 암호 (Substitution Cipher)
  
  • 재배열, 섞기
  • 평문의 문자 순서를 재배열
  • ex) a → b, b → d, c → e
• 치환 암호 (Permutation Cipher)
  • 평문의 어떤 글자 X를 다른 것으로 대체

---

고대 암호

스키테일 암호

• 고대 그리스 스파르타 군대에서 비밀 메시지를 전달하는 데 사용한 암호 기법
• 원 막대를 사용하며, 원통 막대의 지름이 곧 스키테일 암호 알고리즘의 키가 된다.

---

시저 암호 (Caesar Cipher)

• 로마의 황제였던 줄리어스 시저가 사용한 암호, 치환 암호
• 알파벳 3칸씩 뒤로 물려 읽는 방식
  • A→D, B →E,... , Z →C
• 키 = 알고리즘

---

비즈네르 암호 (Vigenere Cipher)

• 시저 암호 유사 알고리즘 + 키
• 알고리즘: 공개
• 키: 비공개
• key에 따라 shift

 

< 고대 암호의 단점 >

• Brute-Force Attack(전사 공격)에 취약 → 보다 정교한 암호기술이 필요하게 됨

---

현대 암호

대칭키 암호

< 대칭키(Symmetric Key) 암호 >

• 암호화 키 == 복호화 키
• 암.복호화 소요 시간 짧음, 간단한 구현 방식
• 비밀키 노출 시 암호화된 정보 해독 가능 → 키 관리 중요
• 데이터를 변환하는 방식에 따라 스트림암호와 블록암호로 나뉨

< XOR (Exclusive OR) 연산>

• 배타적 논리 연산
• 수학 기호: ⊕
• 같으면 0, 다르면 1

---

< 일회용 패드 (One-time Pad, OTP) >

• 절대 해독할 수 없는 암호
• 단순한 원리 : 평문 ⊕ 랜덤비트열
• 평문 P, 난수 생성기로 생성된 키 스트림 B →
  • 암호문 : C = P ⊕ B
  • 복호문:  D = C ⊕ K
• 두 가지 문제점
  • 키 사이즈가 너무 크다
  • 키를 한 번만 쓸 수 있다

→ 스트림 암호: Pseudorandom Keystram와 nonce를 사용하여 단점 보완!

 

< 스트림 암호(Stream Cipher)>

• OTP 단점 보완, 실용적으로 구현할 목적으로 개발
• Keystream을 비트 단위로 순차적으로 처리
  • Keystream: long pseudorandom bit stram
  • Encryption: XOR the keystream with the plaintext
• Key → Key Stram (KS)
  • KS = SC(K,N)
  • K: 짧은 키
  • N: Nonce
• OTP: 난수 스트림(RNG)
• Stream Cipher: 의사난수 스트림(PRNG)

 

---

< 블록 암호 (Block Cipher) >

• 하나의 평문을 블록 단위로 나누어 암호화/복호화 수행
  • 이때, 한 블록의 크기를 n이라고 한다.
• 암호 응용에 있어 가장 보편적으로 사용하고 있는 대칭 암호 알고리즘
  • 종류: DES, Triple DES, AES, ARIA, SEED
• 메커니즘: n 비트의 평문 블록을 m 비트의 매개변수(키)를 이용하여 n 비트의 블록을 출력
  • 구조: ECB, CBC, S-box, P-box, Feistel, SPN(Substitution-Permutation Network)
• P = P1 || P2 || P3 ||.... || Pm
• C = E(k, P), P = D(k, C)
• |P| = |C|

DES	Triple DES	AES
- n=64, k=56 - 16 라운드의 페이스텔 연산 수행	- DES는 1998년에 bruteforce를 사용하여 56시간 만에 해독, 1999년에는 22시간 안에 해독 - 따라서 Triple DES 개발 (암호화 키 2개 사용)	- DES 대체 - Feistel 대신 SPN 연산 사용 - 종류: AES-128, AES-192, AES-256 키 길이: 128, 192, 256 블록 길이: 128 라운드: 10, 12, 14

 

< 대칭키 시스템의 한계: 키 분배 문제 >

• 각 사용자 Pair(송신자 - 수신자)마다 키를 안전하게 공유해야 한다.

 

---

공개키(비대칭키) 암호

< 공개키 암호(Public Key Encryption) >

• 암호화 키 ≠ 복호화 키
• 키 2개: 공개키(Public Key, pk), 비밀키(Secret Key, sk)
  • 암호화 함수: Enc(P, K)
  • 복호화 함수: Dec(C, K)
• 종류: RSA, ElGamal, ECC, 전자서명(Digital signature)

< Certification Authority (CA) >

• Pa가 Alice의 공개키라는 것을 어떻게 보장? → CA
• 키 분배해 주는 공식 기관 → Geotrust 등
• 모두가 신뢰, Trusted organization
• CA로부터 발행한 인증서(Root 인증서)는 우리의 브라우저에, 인증서에 대한 공개키는 인증서 내부에 이미 포함되어 있다.

---

< 디피-헬만 키 교환 (Diffie-Hellman Key Exchange) >

• a와 Bob의 공개키, b와 Alice의 공개키를 이용하여 둘 사이 비밀키(동일)를 각자 계산
• 1976년 제안된 비밀 키 교환 방법 (not encryption scheme)
  • 기초적인 암호학적 통신 방법을 수립
  • 이후 RSA, Elgamal에 영향
• 이산로그문제(Discrete Logarithm Problem)의 어려움 이용
  • g, x, p를 알면 y는 구하기 쉽지만, g, p, y를 알면 x를 구하기는 어렵다.

1. Alice가 Bob에게 소수 p, 1부터 p-1 사이의 정수 g 공개
2. Alice는 임의로 정수 a 선택, 이때 a는 Alice만 알고 있음
3. Bob에게 A = g^a(mod p)를 만족하는 A 전달
4. Bob은 임의로 정수 b 선택, 이때 b는 Bob만 알고 있음
5. Alice에게 B = g^b(mod p)를 만족하는 B 전달
6. Alice는 p와 B, 그리고 자신만 알고 있는 a로부터 Ka = B^a(mod p)를 만족하는 Ka를 계산
7. Bob은 p와 A, 그리고 자신만 알고 있는 b로부터 Kb = A^b(mod p)를 만족하는 Kb를 계산

→ Ka = Kb  = g^ab(mod p)

---

 < RSA >

• By Ronald Rivest, Adi Shamir, Leonard Adleman
• 1977년에 발표된 첫 번째 공개키 암호화 방
• 전자 거래, 금융 거래, 인증서 등 다양한 분야에서 가장 보편적으로 사용
• 안전성: 연산의 복잡성(인수분해 문제의 어려움)에서 기반
  • prime factorization problem
  • 아주 큰 두 소수의 곱으로 이루어진 합성수를 인수분해하기 어렵다
• 연산이 많고 네트워크 통신에서는 잘 사용되지 않음

---

< 타원 곡선 함수 ECC >

• Eliptic Curve Cryptography (타원곡선 암호)
• 타원곡선 이론에 기반한 공개키 암호 방식
• RSA에 비해 작은 키 크기로 비슷한 보안성 제공
  • RSA Key 1024 bit 보안성 := ECC Key 160 bit 보안성
  • 암호화/복호화 속도 빠름
  • 암호화폐, 작은 하드웨어 등에 사용

---

해시 함수(Hash Function)

• 메시지를 길이가 정해진 짧은 값으로 변환/압축한 값
• 입력 메시지 길이에 상관없이, 정해진 고정된 길이의 출력 값
• 입력 메시지가 1bit만 달라도 전혀 다른 해시값을 도출한다.
  • Collision-free
  • Collision-resistance
  • one-wayness
  • preimage resistance
• 종류: MD5, SHA1, SHA-256, SHA-384.... 등
• 메시지의 무결성은 확인 가능하나 인증 문제는 증명 불가

---

< 메시지 인증 코드 (MAC) >

• Message Authentication Code
• Hash + 인증을 위한 Key
  • 결괏값 길이 고정
  • 함수 계산에 추가적인 Key 필요하다
    • 송. 수신자 간 키 공유 사전에 필요

< MAC의 한계 >

• 키 분배 문제 → 대칭키 사용으로 인한 문제
• 제 3자에 대한 증명 및 부인방지 불가
  • 데이터를 주고받는 사람 간 동일한 키를 공유하고 있기 때문

→ 전자 서명(Digital Signature)의 등장

---

전자 서명 (Digital Signature)

• 공개키 기반
• 원본 메시지(의 데이터)를 보내는 사람(서명자)의 개인키로 암호

---

차세대 암호

• Shor 알고리즘 등장 → 공개키 암호 위협
• Grover 알고리즘 등장 → 대칭키 암호, 해시 함수 위협 

▶ 양자 내성 암호, 동형 암호, 양자 암호, 형태보존 암호 등 개발 중

---

양자 내성 암호 (PQC)

• 격자 기반 (Lattice-based)
• 코드 기반 (Code-based)
• 다변수 기반 (Multi-variate)
• 해시 기반 (Hash-based)
• 아이소제니 기반 (Isogeny-based)

---

동형 암호

• Fully Homomorphic Encryption
• 암호문을 이용하여 계산할 수 있게 하는 공개키 암호화 방식
  • 암호화된 데이터로 계산 →  복호화  →  원 데이터로 계산한 값과 일치
• 국내에서 정수 환(Ring) 기반의 동형암호 알고리즘 개발

---

양자 암호

• Quantum Cryptography
• 양자의 특성을 이용한 암호화 방식
  • 불확정성
  • 중첩
  • 얽힘
  • 비가역성

---

형태 보존 암호

• Format Preserving Encryption
• 평문의 형태를 유지한 암호문
  • 동형암호와 비슷 (계산)
• 데이터의 길이 보존
  • 추가적인 저장 공간 구매 불필요
  • DB 스키마 변경 불필요
• 신용카드, 주민등록번호, 사회보장번호(SSN)의 암호화에 사용 가

---

실습

• 드림핵 – Basic_Crypto1 • https://dreamhack.io/wargame/challenges/517

Basic_Crypto1

• H4CKING GAME - ROX • https://h4ckingga.me/challenges#ROX-38

H4CKING GAME

• 드림핵 - ICM2022 • https://dreamhack.io/wargame/challenges/686

ICM2022

---

출처

• 21-1 이화여대 도인실 교수님의 ‘사이버보안개론’ 강의자료 • https://daporang.tistory.com/35

• 윤아람 교수님 현대암호기초 1주 차 강의자료

• 도서

• 히로시 유키, 『알기 쉬운 정보보호개론』, 인피니티북스

• 장삼용, 『화이트해커를 위한 암호와 해킹』, 정보문화사 • 최은미, 『암호론』, 북스힐

• 닐스 퍼거슨 외, 『실용암호학』, 에이콘