암호 알고리즘을 이해하려면 정의를 읽는 것과 함께 직접 계산해 보는 과정이 필요하다. 키 재사용의 문제부터 AES의 바이트 연산, RSA와 전자서명까지 대표적인 문제로 확인해 보자.
1. 대칭키 암호와 RSA 연습
문제 1: CIA Triad
정보보호의 세 가지 목표는 무엇이며, 각각 무엇을 보호하는가?
기밀성(Confidentiality)은 허가되지 않은 정보 열람을 막고, 무결성(Integrity)은 허가되지 않은 변경을 막는다. 가용성(Availability)은 정당한 사용자가 필요한 자원을 제때 이용할 수 있게 하는 성질이다.
문제 2: One-Time Pad(OTP)
비밀키 와 평문 을 XOR하여 암호문 를 만드는 OTP에서 키스트림 재사용 시 메시지 관계가 드러나는지 분석한다.
독립적인 한 번짜리 키라면 각각 완전비밀성 조건을 만족한다. 그러나 동일한 키를 공유하여 재사용했다면 이고, 알려진 한 평문에서 다른 평문을 복원할 수 있다. 세 메시지에 각각 , , 를 사용하면 다음과 같다.
세 암호문을 XOR하면 키 항이 모두 소거된다.
공격자는 암호문만으로 세 평문의 관계를 알 수 있으므로, 세 메시지를 함께 보았을 때 완전비밀성이 성립하지 않는다.
문제 3: Feistel Round
Feistel 구조의 한 라운드에서 왼쪽과 오른쪽 블록이 어떻게 바뀌는지 식으로 표현해 보자.
Feistel 구조에서 F는 역함수가 없어도 복호화할 수 있으며, 복호화는 역순 키를 적용한다.
문제 4: PRNG 기반 XOR 암복호화
로 생성한 난수열 R을 이용할 때
을 도식화한다. 송수신자가 동일한 키스트림을 생성할 수 있어야 한다.
문제 5: Triple DES
DES의 암호화 와 복호화 로 EDE 암호화/복호화를 나타내고, 세 키가 같은 경우 DES와 같아지는지 확인한다.
문제 6: DES와 AES 비교
| 요구 사항 | DES | AES |
|---|---|---|
| Block size | 64비트 | 128비트 |
| Key size | 유효 56비트 | 128/192/256비트 |
| Rounds | 16 | 10/12/14 |
| Round structure | Feistel | SPN |
| Round key size | 48비트 | 128비트 |
AES의 SubBytes, ShiftRows, MixColumns, AddRoundKey와 DES의 Expansion, XOR, Substitution, Permutation 절차도 설명할 수 있어야 한다.
문제 7: AES SubBytes와 ShiftRows
주어진 4x4 바이트 State에 S-box를 적용하고 ShiftRows를 적용하는 문제다.
풀이 원칙
-
각 바이트의 상위 16진수 한 자리는 S-box의 행, 하위 한 자리는 열
-
네 행을 각각 왼쪽으로 0, 1, 2, 3바이트 회전
-
바이트를 십진수로 읽지 않고 16진수 바이트 표기를 유지
문제 8: AES 유한체와 MixColumns
먼저 의 법 다항식에 대응하는 비트열을 쓰고, 그 체 위에서 MixColumns 행렬 곱셈 일부를 계산한다.
계산은 다항식 곱셈 후 에 대한 나머지를 취한다. 자리올림 없는 XOR 연산과 기약다항식에 의한 환원 과정을 차례로 적는 방식으로 풀이한다.
문제 9: Left-to-Right Modular Exponentiation
를 Left-to-Right 방법으로 계산하기 위한 경로를 쓰고 모듈러 곱셈 횟수를 구하는 문제.
첫 1비트에서 초기화하는 left-to-right 방식에서는 제곱 6회와 일반 곱셈 4회, 총 10회가 필요하다. ‘전체 7비트의 각 반복에서 1번씩 곱한다’는 구현과는 연산 횟수 계산 관례가 다를 수 있으니 초기화 방식과 연산 횟수의 기준을 명시해야 한다.
문제 10: OFB Mode
OFB의 암호화/복호화 그림과 수식을 직접 그리는 문제.
OFB의 피드백은 CFB와 달리 암호문이 아니라 이전 암호화 함수 출력이다.
문제 11: Public Key Encryption과 IND-CPA
PKE를 구성하는 세 알고리즘을 정의하고, 결정적 공개키 암호가 IND-CPA 안전성을 만족할 수 없는 이유를 설명해 보자.
공격자가 공개키로 후보 을 직접 암호화할 수 있으므로 결정적 암호화에서는 challenge ciphertext와 비교해서 어느 메시지인지 맞힐 수 있다.
문제 12: RSA 계산 전체
에 대해 , d, 평문 M을 계산한다.
확장 유클리드:
검산: , .
2. 공개키 암호, 서명과 인증 연습
문제 1: RSA-OAEP Decoding
RSA 개인키 d로 암호문 에서 인코딩된 메시지 을 얻은 후, 두 단계 mask 제거를 통해 원래 Message를 복원해야 한다.
-
계산
-
에서 maskedSeed, maskedDB를 위치에 따라 분리
-
-
-
-
-
Label 해시, padding, 0x01 구분자를 검증해 메시지 M 추출
주의: MGF의 입력과 출력 길이를 구분하고, 디코딩 후 패딩 구조와 해시를 모두 검증해야 한다.
문제 2: Diffie-Hellman, MITM, Authentication
DH 공개값과 공유 비밀, 중간자 공격, 방어 방법까지 단계별로 묻는다.
MITM 공격에서는 Eve가 Alice와 Bob에게 자신의 공개값을 대신 전달하므로 Alice, Bob은 서로가 아닌 Eve와 각각 다른 키를 공유한다. 방어 예시는 서명과 공개키 검증을 이용한 당사자 인증이다.
문제 3: ElGamal 암호와 Additive Notation
(a) 암호문 복호화의 실제 계산: 라고 주어진다.
(b) 임의 길이 비트 메시지로 확장: 일 때 해시 함수 를 쓰는 구성은
(c) ECC 등 Additive Group에서도 구성 가능: 표현을 곱셈에서 덧셈으로 바꾸면 표기 대신 , 대신 를 이용한다. 유한체 크기 대비 키와 암호문 길이가 작아질 수 있다는 장점이 있다.
문제 4: RSA Signature, Forgery, PSS
RSA Sign 및 Verify, textbook RSA Signature existential forgery, EMSA-PSS의 인코딩 및 서명 검증 절차까지 묻는다.
Existential forgery: 임의 를 고르고 이라 하면 검증에 성공한다. 즉 raw RSA 서명은 안전하지 않다. PSS에서는 Salt, Hash, MGF, DB, maskedDB, trailer를 구분해야 한다. 서명 생성 결과로부터 을 추출하고 인코딩 구조 및 해시 일치성을 검증한다.
문제 5: Elliptic Curve에서 실제 점 계산
유한체 위 곡선 에 대해 점들을 나열하고 , 를 구한다. 곡선 점:
(b)
따라서 .
(c)
따라서 이다.
문제 6: Cryptographic Hash Properties
(a) Collision Resistance: 서로 다른 두 메시지로
를 찾기 어려워야 한다.
(b) 반례: 가 입력의 마지막 비트만 출력하고 나머지는 0으로 패딩한다고 하자. 이 함수가 충돌 저항성을 갖지 않는 이유는 입력이 달라도 마지막 비트가 같으면 결과가 동일하기 때문이다. 예를 들어 마지막 비트가 모두 0인 두 입력을 쉽게 찾을 수 있다.
문제 7: CBC-MAC
CBC Mode를 이용하여 마지막 암호문 블록을 태그로 만드는 CBC-MAC 생성 알고리즘과 검증 과정을 묻는다.
검증자는 공유키로 같은 연산을 다시 수행하고 전달받은 태그와 비교한다. 일반 IV 표기를 사용하지만, 안전한 기본 CBC-MAC에서는 고정 IV(보통 0), 고정 길이 메시지 가정 등이 중요하다.
3. 추가 복습
| 문제 | 출제 주제 | 핵심 풀이 또는 확인사항 |
|---|---|---|
| 1 | 컴퓨터 보안 및 DES/AES/RC4의 T/F | 기밀성 vs 무결성, DES와 AES 구조, ECB/CBC/CFB/OFB |
| 2 | Permutation 및 Substitution Cipher | 문자 값 치환과 위치 순열을 구별 |
| 3 | Affine Cipher의 키 a,b 복원 | 두 평문/암호문 쌍의 연립합동식 |
| 4 | OTP의 Perfect Secrecy | 균등 무작위, 키 1회 사용, 메시지 길이의 키 |
| 5 | Symmetric vs Public-Key | 키 종류, 키 공유, 속도, 키 개수 |
| 6 | Block Cipher vs Stream Cipher | 블록 단위와 요소 단위 처리 |
| 7 | Feistel Round의 도식과 복호화 | 좌우 교환, XOR, 라운드 키 역순 |
| 8 | DES S-box 입력에서 4비트 출력 | 바깥 2비트 = row, 가운데 4비트 = col |
| 9 | Right-to-Left Modular Exponentiation | 지수의 이진 비트, 제곱 및 곱셈 횟수 |
| 10 | AES SubBytes 및 ShiftRows | 4x4 State 처리, S-box lookup |
| 11 | AES 와 MixColumns | 모듈러 다항식, Shift/XOR와 reduction |
| 12 | LFSR 키스트림과 XOR 복호화 | 점화식으로 12비트 생성, 암호문 XOR |
| 13 | CTR Mode 암복호화 및 장점 | Counter 블록 암호화, 병렬/사전 계산 |
| 14 | RSA 비밀 지수와 인수분해 | , Euler 함수, 모듈러 역원 |
문제 1: 참과 거짓 판별
| 주장 | 판정과 이유 |
|---|---|
| 암호화만으로 데이터 무결성을 보장한다. | 거짓. 기밀성과 무결성은 별개의 목표다. |
| DES의 각 라운드는 같은 구조를 사용한다. | 참. 같은 Feistel 라운드 구조에 서로 다른 라운드 키를 넣는다. |
| AES의 모든 라운드는 같은 구조다. | 거짓. 마지막 라운드에는 MixColumns가 없다. |
| RC4와 ChaCha는 스트림 암호다. | 참. 다만 암호의 분류와 실제 사용 시의 안전성은 구별해야 한다. |
| ECB, CBC, OFB는 모두 키스트림을 XOR하는 방식이다. | 거짓. OFB는 키스트림을 생성하지만 ECB와 CBC는 평문 블록을 블록암호에 입력한다. |
문제 2: 위치 순열과 문자 치환
알파벳 집합을 로 두고 순열을 다음처럼 정의하자.
위치 순열 암호에서 라는 규칙을 사용하면 평문 24531은 , 즉 43152가 된다. 반면 문자 치환은 각 문자에 를 적용하므로 평문 12345가 24531이 된다. 순열의 표가 같아도 위치를 바꾸는지, 문자 값을 바꾸는지에 따라 계산이 달라진다.
문제 3: Affine Cipher 복습 예시
선택 평문 N과 O가 각각 T와 Y에 대응한다면
빼면 , 따라서 . **키는 (5,6)**이다. 정합성: .
문제 8: DES S-box의 행과 열
입력 비트의 첫 비트와 마지막 비트로 행을 정하고, 가운데 네 비트로 열을 정한다. 행과 열은 0부터 센다. S-box 는 다음과 같다.
행\열 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
- 입력 101000: 행은 , 열은 . 출력은 다.
- 입력 001110: 행은 , 열은 . 출력은 다.
문제 9: Right-to-Left 거듭제곱
를 계산해 보자. 지수를 이진수로 쓰면 이다. 낮은 비트부터 처리할 때 누적값은 다음처럼 바뀐다. 모든 연산은 로 나눈 나머지로 수행한다.
처음의 를 대입으로 처리하고 마지막 비트 이후의 불필요한 제곱을 생략하면, 제곱 7회와 누적 곱셈 4회로 총 11회의 모듈러 곱셈이 필요하다. 초기값과 반복문의 범위가 다른 구현에서는 연산 횟수도 달라질 수 있다.
문제 10: AES SubBytes와 ShiftRows
다음 State에 SubBytes와 ShiftRows를 차례로 적용하자. 행렬의 모든 값은 16진수 바이트다.
ShiftRows는 첫 번째 행을 그대로 두고 나머지 행을 각각 왼쪽으로 1, 2, 3바이트 순환 이동한다.
문제 11: 유한체 환원과 MixColumns
AES의 기약다항식은 이다. 따라서 의 나머지는 이며, 바이트 표현은 00011011, 즉 1B다.
다음 State에 MixColumns를 적용한 결과의 성분을 구하자. 여기서는 행과 열을 1부터 센다.
두 번째 행의 계수는 이므로 두 번째 열과 곱하면 다음과 같다. 곱셈은 의 연산이다.
에서는 왼쪽 이동으로 넘친 최고 비트를 제거한 뒤 1B를 XOR해 CB를 얻는다. 다.
문제 12: LFSR 키스트림과 복호화
점화식과 초기 비트가 다음과 같다고 하자.
초기 비트를 포함해 12비트를 생성하면 1000 1001 1010이다. 암호문이 1110 0011 1100이면 같은 길이의 키스트림을 XOR한다.
암호문 1110 0011 1100
키스트림 1000 1001 1010
평문 0110 1010 0110
문제 14: RSA 비밀 지수 계산
이고 공개 지수가 라면 이다. 비밀 지수 는 을 만족해야 한다.
확장 유클리드 알고리즘으로 를 얻으므로
실제로 이다.
확장: RSA에서 과 소인수분해
서로 다른 두 소수의 곱인 RSA 모듈러스 N과 이 함께 주어졌다고 하자. 이 두 값으로 p와 q를 구할 수 있다.
왜냐하면 이기 때문이다. 따라서 p,q는 다음 이차방정식의 근이다.
판별식이 제곱수가 되어야 하며, 두 근이 소수인지 검산한다.
4. 연습할 계산 유형
-
Affine/Shift/Permutation: 숫자와 문자의 치환 및 알려진 평문 공격.
-
DES/Feistel: 라운드 식과 S-box row/column 선택.
-
AES: SubBytes, ShiftRows, MixColumns의 중간 행렬과 비트 계산.
-
: 기약다항식 환원 및 역원.
-
Modular Exponentiation: Left-to-Right/Right-to-Left 알고리즘의 곱셈 횟수.
-
RSA: Euler, Euclidean, modular inverse, KeyGen, Enc/Dec, OAEP.
-
DH/ElGamal: 공유 비밀, MITM, 인증, 모듈러 역원 복호화.
-
ECDSA/ECC: Point Addition, Doubling, x좌표와 mod.
-
Hash/MAC: collision resistance와 MAC 검증 알고리즘.
Comments