▪︎ 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 설정 가능)를 사용, 문자의 위치에 따른 치환 규칙 변화
(암/복호화 시, 비즈네르 표 참조)
+ 애니그마 원리에 이용, 기본적인 통계적 특성은 약화시킴 (빈도수 분포 그래프 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) → 알파벳으로 변환
복호화) 비밀키 설정시, 역함수가 존재하도록 설정 - 암호문(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
+보충) 암호화 통신, 실습 코드
'Convergence Security > Applied Cryptography' 카테고리의 다른 글
- Hash Function (1) | 2024.06.03 |
---|---|
Public key (Asymmetric key) (1) | 2024.05.07 |
Symmetric Key (0) | 2024.04.24 |