[암호학 4강] 대칭키 암호(3)

1. 난수 (Random Numbe)

• 임의의 수
• 암호학에서 중요하게 사용됨.
  • 특히 다양한 상황에서의 키에 활용
• 예)
  • One-Time-Pad의 키
    • 평문의 길이와 동일하며 반복되지 않는 랜덤 키
    • 한 번 사용된 키는 다시 사용하지 않고 버림

Random Number Generator

• 무작위성 (randomness)
  • 균일 분포
    • 생성된 수열의 비트 분포가 균일해야함
  • 독립성
    • 수열의 부분 수열로부터 다른 부분 수열을 추정할 수 없음.
• 예측 불가성 (unpredictability)
  • 수열에서 다음 수의 예측이 불가해야함

TRNG (True Random Number Generator)

• 마이크 잡음, 공기의 난류 등을 입력으로 사용
• 0과 1의 분포가 균일하지 않을 수 있음

PRNG (Pseudorandom Number Generator)

• TRNG의 출력을 입력으로 사용 (seed)
• Seed가 동일하면 동일한 수열 생성

	TRNG	PRNG
효율성	비효율적	효율적
결정성	비결정적	결정적
주기성	비주기적	주기적

PRNG 성질

• 짧은 난수로부터 긴 난수를 생성함
• 빠른 속도로 난수 생성
• 생성되는 난수의 분표가 균일
• Seed를 모르면, 이전 비트 정보로 당므 비트를 에상할 수 없음
• 생성된 비트 정보로 Seed를 알아낼 수 없음
• Seed가 동일하면, 매번 동일한 난수 생성

PRNG 종류

• Blum Blum Shub Generator
• 블록암호 기반 PRNG
• LFSR
  • 단독으로 사용하지는 않음
• NFSR

2. Blum Blum Shub Generator (BBS)

Seed를 제곱한 후 최하위 bit를 새로운 bit로 취함

• 생성단위: 1bit

• $x_0 = seed^2 \quad mod \quad n$
• $x_i = (x_{i-1})^2 \quad mod \quad n$
• $x_i \quad mod \quad 2$
  • pseudorandom bit

3. 블록암호 기반 PRNG

블록암호와 CTR 또는 OFB 모드를 이용하여 새로운 bits를 얻음

• 생성단위 : 1블록

4. LFSR PRNG (Linear Feedback Shift Register)

직전 m개의 값을 선형 결합하여, 새로운 bit를 얻음

• 생성단위 : 1bit
• 주기 : $2^m - 1$

5. 스트림 암호

평문과 같은 길이의 키 스트림을 생성하여,
평문과 키 스트림을 XOR하여, 암호문을 얻는 암호화 방식

• 키 스트림을 어떻게 만드느냐가 관건

키 스트림

• 임의의 길이의 평문에 대해 항상 생성 가능
• 규칙성이 없어 예측 불가능한 랜덤 수열이 가장 안전
  • 하지만 재생성이 불가능하면 복호화 불가능
• PRNG로 생성
  • 자동화된 생성이 가능하면서도 예측 불가성 보장

분류

동기식 스트림 암호

• 키 스트림 생성은 평문 또는 암호문과 무관
• 암호화와 복호화에서 상호 동기화가 필수
• 전송 도중 변조되어도 후속 암호문에 오류의 영향이 파급되지 않는다.

비동기식 스트림 암호

• 키 스트림 생성에 평문 또는 암호문의 일부가 이용됨
• 변조된 암호문은 후속 암호문 일부의 복호화에서만 사용되어
  오류 파급이 제한적

암호 종류

• RC4
• Salsa20
• A5/1
  • LFSR + $\alpha$
• A5/2
  • LFSR + $\alpha$
• Grain - 128a
  • LFSR + NFSR
• Spritz
• ChaCha

RC4

• 1987년 Rivest가 개발
• TLS, WEP 등 다양한 응용에 널리 사용됨
• 취약점이 드러나 현재는 사용되지 않음
• 8 bits 단위로 키 스트림을 생성
  • 00000000부터 11111111까지 256개의 수를 permutation하며 선택
• 키 (seed)
  • Keylen bytes ($1 \leq Keylen \leq 256 $)