Stream Cipher, Random Number Generator

Seungyun Lee·2026년 1월 27일

Cybersecurity

목록 보기

3/13

1. 스트림 암호 (Stream Cipher) 개요

개념: 데이터를 비트(Bit) 단위로 하나씩 암호화하는 방식입니다.
원리: 평문(xi)과 키 스트림(si)을 XOR(Modular 2 addition) 연산하여 암호문(yi)을 생성합니다.
수식:
- Encry 암호화: yi = xi ⊕ si (mod z)
- Decry 복호화: xi = yi ⊕ si (mod z)
특징:
- 복호화에서는 xi = yi - si (mod z)되야 하는거 아닌가?
  답: Modular z 연산에서는 더하기와 빼기가 동일하므로 암/복호화 구조가 같습니다.
- 하드웨어(FPGA, Verilog 등)에서 XOR 게이트만으로 구현 가능하여 속도가 매우 빠릅니다.

XOR 연산의 3가지 마법 같은 성질
스트림 암호의 핵심인 XOR(Exclusive OR)은 다음 성질을 가집니다.
성질 1: 자기 자신과 XOR하면 0이 된다. ( $A \oplus A = 0$ )
성질 2: 어떤 수에 0을 XOR하면 변하지 않는다. ( $A \oplus 0 = A$ )
성질 3: 순서를 바꿔도 결과가 같다. ( $A \oplus B = B \oplus A$ )

[과정 1: 암호화 (Alice)]
- 평문(Message): M
- 키(Key): K
- 암호문(Ciphertext) C = M ⊕ K

[과정 2: 복호화 (Bob)]
- 암호문 C를 받은 Bob은 다시 똑같은 키 K를 XOR합니다.
- 복호화 식: C ⊕ K
- 식 전개: (M ⊕ K) ⊕ K  <-- C 자리에 (M ⊕ K)를 대입
- 결합 법칙: M ⊕ (K ⊕ K)
- 성질 1 적용: M ⊕ 0      <-- 같은 키 K끼리 만나서 0이 됨
- 성질 2 적용: M          <-- 원래 메시지 복구!

왜 더하기/빼기가 아니고 XOR인가?(Modular 2)
교수님이 수업 시간에 Modular 2 (2로 나눈 나머지) 이야기를 하셨을 거예요. 이진수(0과 1) 세계에서는 더하기와 빼기가 사실상 똑같습니다.
더하기: $1 + 1 = 2 \equiv 0 \pmod{2}$
빼기: $1 - 1 = 0 \equiv 0 \pmod{2}$
즉, $1$ 에 $1$ 을 더하나 빼나 결과는 똑같이 $0$ 이 됩니다. 이 "더해도 0, 빼도 0"이 되는 논리가 바로 XOR 연산이며, 이 덕분에 "암호화할 때 키를 한 번 섞고(XOR), 복호화할 때 똑같은키를 한 번 더 섞으면(XOR) 원래대로 돌아오는" 구조가 만들어지는 것입니다.

[스트림 암호의 암/복호화가 동일한 이유]

1. XOR 연산의 가역성(Invertibility):
   - 특정 값에 똑같은 값을 두 번 XOR하면 원래 자기 자신으로 돌아옵니다.
   - 공식: (Data ⊕ Key) ⊕ Key = Data

2. 이진 연산(Modular 2)의 특성:
   - 0과 1만 사용하는 체계에서는 '더하기'와 '빼기' 연산 결과가 동일합니다.
   - 따라서 암호화 시 적용한 연산을 복호화 시 한 번 더 반복하는 것만으로 
     원래 데이터를 추출할 수 있습니다.

3. 하드웨어적 이점:
   - 암호화 칩과 복호화 칩을 따로 만들 필요가 없습니다. 
   - 동일한 XOR 게이트 회로를 공유하므로 설계가 매우 경제적입니다.

2. Random Number Generator(RNG)

TRNG (True Random Number Generator)
- True: 진정한 / Random Number: 난수 / Generator: 생성기
- 의미: 인위적인 알고리즘이 아니라 자연계의 무작위성(물리적 현상)에서
  직접 값을 가져오기 때문에 '진정한(True)' 난수라고 부릅니다.
PRNG (Pseudo Random Number Generator)
- Pseudo: 가짜의, 의사의(Pseudo-) / Random Number: 난수 / Generator: 생성기
- 의미: 겉보기에는 무작위 같지만 실제로는 수학 공식에 의해 계산된
  '가짜(Pseudo)' 난수입니다. 시작점(Seed)이 같으면 항상 같은 결과가 나옵니다.
CSPRNG (Cryptographically Secure Pseudo Random Number Generator)
- Cryptographically Secure: 암호학적으로 안전한 / Pseudo Random Number: 난수
- 의미: PRNG의 일종이지만, 공격자가 다음 숫자를 예측할 수 없도록
  수학적으로 훨씬 더 복잡하고 강력하게 만든 '암호학적 안전성'이 추가된 생성기입니다.

3. One-Time Pad, OTP

1. OTP (One-Time Pad)란?

이름 그대로 "딱 한 번만 사용하는 메모장(Pad)"이라는 뜻입니다. 암호화하려는 메시지(평문)와 완벽하게 동일한 길이의 무작위 키를 생성하여 딱 한 번만 쓰고 버리는 방식입니다.

작동 원리
키 생성: 메시지가 100글자라면, 키도 100글자의 완전한 난수(TRNG)로 만듭니다.
암호화: 평문 $\oplus$ 키 = 암호문.
복호화: 암호문 $\oplus$ 키 = 평문.
파기: 사용한 키는 즉시 세상에서 삭제합니다.

2. 왜 OTP는 절대 깨지지 않는가? (무조건적 안전성)

암호학에서는 이를 Unconditional Security(무조건적 안전성)라고 부릅니다. 공격자가 무한한 컴퓨팅 파워를 가져도 못 푼다는 뜻인데, 이유는 다음과 같습니다.

완전 무작위성: 키 자체가 물리적 현상(TRNG)으로 만든 완전한 난수라 수학적 패턴이 아예 없습니다.

모든 가능성 존재: 암호문 LJQZ를 해독하려고 할 때, 키가 무엇이냐에 따라 평문은 LOVE가 될 수도, HATE가 될 수도, KILL이 될 수도 있습니다. 즉, 공격자가 모든 키를 다 대입해 봐도 어떤 게 진짜 메시지인지 구별할 방법이 물리적으로 존재하지 않습니다.

3. 왜 현실에서는 잘 안 쓰나? (실용성의 한계)

교수님이 스크립트에서 "Not practical"이라고 강조하신 부분입니다.

키 길이의 문제: 10GB짜리 영화를 암호화하려면 10GB짜리 난수 키가 필요합니다. 배보다 배꼽이 더 커지죠.
키 분배의 문제: Alice가 Bob에게 10GB 키를 안전하게 전달할 수 있다면, 그냥 그 경로로 메시지를 보내는 게 빠릅니다. (키를 전달하는 과정 자체가 이미 보안 문제임)
재사용 금지: 실수로라도 같은 키를 두 번 쓰면, 두 암호문을 XOR 하는 순간 키가 사라지고 메시지의 관계가 드러나버립니다.

4. LCG (Linear Congruential Generator)와 취약점

LCG(Linear Congruential Generator)**는 아주 오래된 난수 생성 방식입니다. 수학 공식 하나로 "난수처럼 보이는 숫자"들을 계속 만들어내는 공장이라고 생각하면 쉬워요.

공식: $S_{i+1} = (A \cdot S_i + B) \pmod{M}$

왜 LCG는 암호학에서 "나쁜" 방식인가?
교수님이 수업에서 "LCG는 안전하지 않다"고 강조하신 이유입니다. 보안 시스템은 공격자가 다음에 뭐가 나올지 절대 몰라야 하는데, LCG는 수학적으로 너무 단순해서 금방 들통나기 때문입니다.

공격 방법 (기지 평문 공격, Known Plaintext Attack):
- 공격자가 연속된 평문(x1, x2, x3)과 암호문(y1, y2, y3)을 알면 XOR을 통해 s1, s2, s3를 구할 수 있습니다.
- s2 = (As1 + B) mod M, s3 = (As2 + B) mod M 이라는 두 연립 방정식을 세웁니다.
- 이를 통해 미지수 A와 B를 계산해낼 수 있으므로, 이후의 모든 키 스트림이 노출됩니다.