Overview of Applied Cryptography

▪︎ Intro

 

Kerckhoffs's principle, 'La CryptographieMilitaire' - 군사용 암호의 필수 조건 서술

The security of the password depends only on the secrecy of the key, not the encryption/decryption process.

(Under the assumption that the algorithm specifications of the ciphers & protocols are all disclosed)

 

Enigma - 글자마다 서로 다른 치환 사용, 회전자 3개는 다르게 움직임 (암복호화를 위해 설정값을 알아야함)

+ 같은 글자를 넣어도 반사판을 거치며 다른 글자가 나옴 (따라서, 반대로 안 나오는 글자가 존재하는 취약점 존재)   

 

OTP, One-time Pad(메시지 길이 == 키의 길이인 만큼 완벽한 암호이지만, 키 길이가 길어 비 효율적이고 보안 전송이 어려움)

C = P ⊕ K (메시지와 같은 길이의 키로 암호화) 0 0 = 0 / 0 1 = 1 / 1 0 = 1 / 1 1 = 0 와 같이 XOR 연산 후 랜덤한 숫자가 나옴

 

# 키 길이 설정 (무차별 대입 공격-Brute force attack 기준으로 공격비용/효율성 판단)

→ 현재 컴퓨터 연산속도상, 최소 128비트 길이의 키 사용

---

▪︎ 고전 암호

 

[기본 기법] - 전치암호(선형): ROT 연산  /  치환암호(비선형): XOR 연산

※ Modular Arithmetic, 모듈러 덧셈이란? - 경우, mod 숫자로 나눈 나머지 + mod 숫자 // + 경우, mod 숫자로 나눈 나머지를 의미

덧셈 암호 (COA, KPA, CPA 가능): 암호화 x → x+k (mod 26) / 복호화 Y → x-k (mod 26) •• 가능한 키 = 26개

곱셈 암호: m → m x k(비밀) (mod 26) / k는 26과 서로소여야 조건 성립<같은 알파벳-다른 대응 암호 필요> •• 가능한 키 = 12개

암호화 표현식 = 결과 * 모듈러 연산 (mod26 사용 이유? 알파벳 범위내로 만들기 위함)

즉, k가 25를 넘어가면 처음으로 돌아감 (0~25)

 

곱셈암호 예시) x * k = 1 (mod 26)에서 x를 찾기 위해서는?

# Euclidean Algorithm (유클리드 호제법) - 최대 공약수 알고리즘

 정수 s, t 에 대해, 정수 a, b의 최대공약수 집합

(나머지가 0이 나올때까지, 연속적 숫자 분해)

⇒ 유클리드 호제법을 이용해, k와 26에대한 최대-공약수 (x)를 찾음

---

- monoalphabetic substitution cipher (단일 문자 치환 암호 - 알파벳 1:1 대응)

+letter frequency analysis (문자 빈도 분석)과 같은 통계적 분석에 취약

 

◻︎ 시저 암호 - 단순 이동 암호, 철자 빈도 & 자주 사용되는 단어/형태로 유추 가능 (키가 없으므로, 케르크호프스 원리에 어긋남)

[시저 암호 - 안전한 변형 예시]

▫︎ 비밀키 설정 (범위: 0~25)

▫︎ 비밀키를 Table로 만들어 불규칙하게 변환

▫︎ if 비밀키(편의상, 비밀키 배열) == N개의 숫자, 비밀키 배열[0~N]을 이용하여 각각 다른 치환법 사용

즉, 비밀키 배열의 길이(치환 블록 단위) 최댓값은 메시지의 길이이다. 또한 비밀키 배열[n]은 0~9까지의 임의의 숫자이다.

= 비밀키 배열 길이(0~N)을 반복문에 삽입하여, 단위마다 잘린 메시지를 평행 이동시키는(0~9번) 무차별 대입공격으로 쉽게 해독 가능

또는 문자 빈도에 따른 통계적 분석을 사용할 수 있음

 

덧셈 암호 & 곱셈 암호 (각각 중복 적용 의미 X)는 모두 전수조사 공격에 취약

◻︎ 아핀 암호 - 곱셈 & 덧셈 복합 암호: x → αx + β (mod 26)  /  26*12= 312 키 가능

+ KPA (두 쌍의 평문, 암호문 있으면 연립방정식으로 풀이 가능)

+ CPA (암호화 질의(0 대입)를 던지면 β 파악 가능, 암호화 질의(1 대입)를 던지면 α + β 파악 가능 → α 산출

+ CCA (KPA와 유사하게 두 번 질의로 연립방정식 풀이 - 키 획득)

---

- polyalphabetic substitution cipher (복수 문자 치환 암호 - 평문 블록 단위 치환)

+ 통계적 특성은 약화되나, 블록의 크기를 알면 KPA 공격 취약

 

◻︎ 비즈네르 암호 - 덧셈암호 키 여러 개(키 집합 개수 N 설정 가능)를 사용, 문자의 위치에 따른 치환 규칙 변화

비밀 키 K 설정

비즈네르 암호의 암/복호화 수식

(암/복호화 시, 비즈네르 표 참조)

+ 애니그마 원리에 이용, 기본적인 통계적 특성은 약화시킴 (빈도수 분포 그래프 Smooth)

+ 암호문이 충분히 길면, 카지스키 테스트 + 통계적 분석 = 해독 가능 (COA 공격 취약)

COA 해독)

1. 카지스키 테스트: 평문-암호문 반복 구문 -> 반복 주기(이내이므로)의 약수로 키 길이 추론 가능

2. 도수 분석(frequency analysis) 수행: 키 길이보다 충분히 긴 암호문 확보시, 통계적 분석 방법으로 해독 가능

KPA(충분한 길이 평문,암호문 쌍-차이로 파악 가능), CPA(aaaa.. 대입), CCA(AAAA... 대입)

 

◻︎ 힐 암호

예시) 평문: Egg is white, 블록 크기: 2 라고 가정, (블록 크기 N → 비밀키 행렬 N*N)

암호화) eg / gi / sw / hi / te * 비밀키 2x2 행렬 M (mod 26) → 알파벳으로 변환

eg가 (4, 6) 이므로, 비밀키 행렬과의 곱셈 후 mod 26을 취하면 결과 값 = (16,16) &rarr; 즉, QQ

복호화) 비밀키 설정시, 역함수가 존재하도록 설정 - 암호문(x, y)에  역함수를 곱해주면 복호화

*KPA에 취약 - (평문, 암호문)의 쌍을 알고 있는 공격으로, 각각을 행렬로 만들어 역행렬(복호화 키)이 나올때까지 관계 연산 시행

 

◻︎ 아핀 힐 암호

키 설정) 2 x 2 행렬 M  &  2 x 1 벡터 b

암호화) 블록 * 행렬 M (힐 암호) + 벡터 b (아핀 암호)

---

- 공격 모형 (공격자의 능력에 따른 모형)

• Black-box model: 연산 도중 내부 관찰 불가 & 알고리즘 입/출력만 확인 가능

  ㄴ Encryption Query & Decryption Query => 평문/암호문 추출

• Gray-box model: Black-box + 부채널 정보 (연산 시간, 전력 소비량, 자기장 등) 

• White-box model: Gray-box + 소프트웨어 실행 중 연산이 이루어지는 장비 내부 모든 계산과정 관찰 및 메모리 접근/변경 가능

 

- Ciphertext Only Attack (암호문만 아는 상태)

- Known Plaintext Attack (암호문, 평문 쌍을 얻을 수 있지만 평문 선택 불가)

- Chosen Plaintext Attack (선택한 평문에 대한 암호화 질의 수행 가능)

- Chosen Ciphertext Attack (선택한 평문 및 암호문에 대한 암호화/복호화 질의 수행 가능)

~이전 공격은 평문의 "make sense" 판별, 그렇다면 복호화 후에도 알 수 없는 메시지가 나올 경우?

= *Improved COA(자동화 공격): 정해진 알파벳 빈도를 계산한 수식 이용 -> 비밀키를 찾음

 

pi = i-th 알파벳의 빈도(0 ≤ 𝑝𝑖 ≤ 1) 

 

 

qi := 암호문에서 i-th 알파벳의 빈도(0 ≤ 𝑞𝑖 ≤ 1)  / j = {0,...,25}

 

(* 𝑖-th integer denotes the peg on which the disk of radius 𝑖 is present in the initial configuration)

단, 통계적 특성을 사용하여 문자 빈도를 분석해야하므로, 충분한 길이의 암호문 필요

 

---

▪︎ 현대 암호

고전 암호의 경우, 군 정부에서 주로 사용 및 메시지 보호를 위한 Encryption에 초점

현대 암호의 경우, 인터넷 통신 프로토콜, 전자 결제, OS 업데이트, 패스워드 등에 사용

 

- 현대암호 4가지 목표

1) Confidentiality (기밀성): Prevention of inappropriate exposure. Content must not be accessible to anyone other than authorized users. <공개키/대칭키>

2) Integrity (무결성): Preventing errors during transmission and inappropriate changes by attackers. & Content must not be changed by anyone other than authorized users. <해시 함수>

3) Authentication (인증): Verifying the identity of someone or something (before transmission) <전자 서명>

4) Non-repudiation (부인방지): The person delivering or receiving the message must not be able to deny that the message was delivered or received. <전자 서명>

 

Examples)

• Digital Signature & Identification (Password/Biometrics) - Login, Electronic_Payment/Passport/Voting

• Key Exchange

• Internet Transmission - Security Protocol (TLS)

 

• Electronic Money/Cryptocurrency

• Homomorphic Encryption

 

 

[References]

Applied Cryptography, (Apr 25, 2024), University of Sungshin (Joohee Lee)

https://math.stackexchange.com/questions/405172/what-does-i-th-mean

---

+보충) 암호화 통신, 실습 코드