Classical Cryptography & Modular Arithmetic

1.Substitution Cipher (치환 암호)와 보안성 분석

개념: 평문의 각 문자를 고정된 다른 문자로 1:1 대응하여 변환하는 방식.
수신자는 송신자가 수행한 치환의 역과정을 통해 복호화한다.

Brute Force Attack에 대한 안전성:

• 가능한 키(Key)의 조합은 $26! \approx 2^{88}$가지입니다.
• 현대 컴퓨터의 연산 능력 한계(Upper bound)를 대략 $2^{80}$으로 볼 때, $2^{88}$은 훨씬 크므로 Brute Force 공격에는 안전합니다.

Frequency Analysis Attack(빈도 분석 공격):

• 영어 알파벳은 특정 문자(e.g., 'E'는 약 13%, 'T' 등)가 자주 등장하는 빈도 특성이 있습니다.
• 치환 암호는 문자의 매핑이 고정되어 있으므로, 암호문의 문자 빈도를 분석하면 쉽게 해독됩니다. 따라서 치환 암호는 안전하지 않습니다.

2. 공격 유형 분류 (Classification of Attacks)

A. Brute Force: 모든 가능한 키를 다 시도해보는 방식.
B. Analytic Attack: 수학적 분석을 통한 공격 (예: 머신러닝의 Membership Inference Attack).
Membership Inference Attack: 공격자가 특정 데이터 샘플을 가지고 있을 때, 이 샘플이 머신러닝 모델의 학습 데이터셋에 포함되었는지("멤버") 여부를 알아맞히는 공격
C. Social Engineering: 피싱(Phishing) 등 사람의 심리나 실수를 이용하는 공격.
D. Implementation/Side Channel Attack: 암호 알고리즘 자체보다는 물리적 신호(전력 소모, 전자파 등)를 분석하는 공격 (예: 드론의 전자파 파형 분석).

3. Modular Arithmetic (모듈러 연산)

1. 기본 개념: Finite Set

우리가 평소에 쓰는 수는 무한히 커질 수 있지만, 모듈러 연산은 수가 뱅글뱅글 도는 닫힌 세계입니다.
비유: 시계 (Clock)

• 시계는 12가 지나면 다시 1로 돌아옵니다.
• 모듈러 24 ($\pmod{24}$): 16시간 후 + 20시간 후 = 36시간 후가 아니라, 시계에서는 12시간 후가 됩니다.
• 즉, $16 + 20 \equiv 12 \pmod{24}$ 입니다.

2. 수학적 정의와 '나머지'의 진짜 의미

정의: $A \equiv R \pmod M$
의미: $A$와 $R$의 차이($A - R$)가 $M$의 배수이다. ($M$이 $A-R$을 나누어 떨어지게 한다.)

EX)
($17 \equiv 2 \pmod 5$)
$a = 17$, $r = 2$, $m = 5$

왜 이렇게 정의할까요?
단순히 "나눗셈의 나머지"라고만 생각하면 $R$은 무조건 $0$보다 크고 $M$보다 작은 수여야 한다고 착각하기 쉽습니다.
하지만 이 정의에 따르면 음수나 큰 수도 나머지가 될 수 있습니다.
음수 나머지?: $42 = 5 \times 9 + \mathbf{(-3)}$ (나머지 -3?)
확인: $42 - (-3) = 45$ (9의 배수 맞음. OK)

3. Equivalence Class(동치류)

위의 예시에서 본 것처럼, $\pmod 9$ 세상에서는 6, 15, 24, -3 등이 모두 같은 수 취급을 받습니다.
동치류(Equivalence Class)란?

• $M$으로 나누었을 때 나머지가 같은 수들의 그룹(집합)입니다.
• 이 그룹 안에 있는 어떤 수를 꺼내서 계산해도 결과는 똑같습니다.
  핵심 꿀팁 (Computational Trick):복잡한 계산을 할 때, 동치류 안에서 가장 작고 다루기 쉬운 수로 바꿔치기해서 계산해도 됩니다.

4. 계산 효율화 예제 (시험/과제용 중요 테크닉)

교수님이 강조한 "계산기 없이 큰 수 계산하기"입니다. 동치류 성질을 이용합니다.

예제 1: $(13 \times 16 - 8) \pmod 5$

모듈러 성질 이용 (Smart Way):

• 각 숫자를 $\pmod 5$ 세상의 작은 수로 먼저 바꿉니다.
• $13 \to \mathbf{3}$ ($13 \div 5$ 나머지)
• $16 \to \mathbf{1}$ ($16 \div 5$ 나머지)
• $8 \to \mathbf{3}$ ($8 \div 5$ 나머지)
• 바뀐 식: $(3 \times 1 - 3) = 0$
• 정답: 0 (훨씬 쉽죠?)

예제 2: 거듭제곱 $3^8 \pmod 7$

무식한 방법: $3^8 = 6561$. $6561 \div 7$... (계산기 없으면 힘듭니다.)

모듈러 성질 이용:

• $3^8 = 3^4 \times 3^4$
• 먼저 $3^4$을 쪼개봅니다. $3^4 = 81$.
• $81 \pmod 7$을 구합니다. ($7 \times 11 = 77$이므로 나머지는 4)
• 이제 $3^4$ 대신 4를 대입합니다.
• $4 \times 4 = 16$.
• $16 \pmod 7$은 ($7 \times 2 = 14$이므로) 나머지는 2.
• 정답: 2

4.Ring and Multiplicative Inverse

이 부분이 가장 어렵고 중요합니다. 일반 수학과 다릅니다.

(1) 정수 링 (Integer Ring, $\mathbb{Z}_m$)의 정의

링은 다음 세 가지 요소로 구성된 시스템입니다.
집합 (Set): $\{0, 1, 2, ..., m-1\}$

• $m$으로 나누었을 때 나올 수 있는 나머지들의 모임입니다.
  연산자 1 (덧셈): $+$ (단, 결과에 $\pmod m$ 적용)
  연산자 2 (곱셈): $\times$ (단, 결과에 $\pmod m$ 적용)
  즉, "0부터 $m-1$까지의 숫자들만 가지고 덧셈과 곱셈을 하는 세계"입니다.

(2) 링의 주요 성질 (Properties)

교수님은 링이 성립하기 위한 조건들을 하나씩 나열하셨습니다. 이 조건들이 곧 암호학적 연산의 규칙이 됩니다.

① 닫혀있다 (Closure / Closeness)

• 가장 중요한 개념 중 하나입니다.
• 이 집합 안의 어떤 수 두 개를 더하거나 곱해도, 그 결과는 반드시 다시 그 집합 안에 있어야 합니다.
• 예: $\pmod 5$ 세상($\{0, 1, 2, 3, 4\}$)에서 $3+4=7$이지만, $\pmod 5$를 하면 $2$가 됩니다. $2$는 집합 안에 있으므로 '닫혀있다'고 합니다.

② Associativity (결합 법칙)

$(a+b)+c = a+(b+c)$
순서를 바꿔서 계산해도 결과가 같다는, 우리가 아는 일반 수학 규칙이 적용됩니다.

③ Neutral Element / Identity (항등원)

계산을 해도 자기 자신이 나오게 하는 숫자입니다.
덧셈의 항등원: 0 ($a + 0 = a$)
곱셈의 항등원: 1 ($a \times 1 = a$)

④ Inverse (역원)

이 부분이 시험과 암호학 이해의 핵심입니다. "어떤 수와 연산했을 때 항등원이 나오게 하는 수"입니다.

1) 덧셈의 역원 (Additive Inverse):

• $a + (-a) \equiv 0 \pmod m$
• 모든 수에 대해 항상 존재합니다.

2) 곱셈의 역원이란?

일반 수학: $2$의 역원은 $1/2$ (0.5)입니다. 곱해서 1이 되는 수니까요.
모듈러 수학: 분수나 소수가 없습니다. 오로지 정수만 존재합니다.

정의: $A \times B \equiv 1 \pmod M$ 일 때, $B$를 $A$의 역원($A^{-1}$)이라고 부릅니다.

교수님 경고: 답안지에 $2^{-1} = 1/2$ 혹은 $0.5$라고 쓰면 0점 처리됩니다. 반드시 정수 집합 안에서 찾아야 합니다.

(3) 역원 찾기 예시 ($\pmod 9$ 에서)

문제 1: 2의 역원을 구하시오.
$2 \times X \equiv 1 \pmod 9$ 인 $X$를 찾습니다.
$X$에 0부터 넣어봅니다.
$2 \times 1 = 2$
$2 \times 2 = 4$
$2 \times 3 = 6$
$2 \times 4 = 8$
$2 \times 5 = 10 \equiv 1 \pmod 9$ (딩동댕!)
정답: 2의 역원은 5입니다.

문제 2: 3의 역원을 구하시오.
$3 \times X \equiv 1 \pmod 9$
$3 \times 1 = 3$
$3 \times 2 = 6$
$3 \times 3 = 9 \equiv 0$
$3 \times 4 = 12 \equiv 3$(아무리 곱해도 1이 나오지 않습니다.)
정답: 3의 역원은 존재하지 않습니다 (Does not exist).

(4) 역원이 존재할 조건

언제 역원이 존재하고, 언제 없을까요?
조건: $GCD(A, M) = 1$ 이어야 합니다. = (최대공약수가 1)
링($\mathbb{Z}_m$): 모든 수에 역원이 있는 것이 아닙니다.

조건: $\text{gcd}(a, m) = 1$ 일 때만 $a$의 역원이 존재한다.
(즉, $a$와 $m$이 서로소일 때만 역원이 있음)

$GCD(3, 9) = 3$ (1이 아님) 이므로 역원 없음.
$GCD(6, 9) = 3$ 이므로 6도 역원 없음.

($\mathbb{Z}_9$ : $\{0, 1, ..., 8\}$)
2의 역원은?
$\text{gcd}(2, 9) = 1$ (서로소임) $\rightarrow$ 역원 존재함.
$2 \times 5 = 10 \equiv 1 \pmod 9$
따라서 2의 역원은 5.

1. 계산 팁: 큰 수가 나오면 무조건 $\pmod M$을 해서 작은 수로 줄인 뒤 계산하세요. (동치류 활용)
2. 역원 개념: $A^{-1}$은 $1/A$가 아닙니다. 곱해서 나머지가 1이 되게 하는 정수입니다.
3. 역원 존재 조건: $A$와 $M$의 최대공약수가 1일 때만 역원이 있습니다. (아핀 암호의 키 개수를 구할 때 이 원리가 사용됨)

5. 시프트 암호와 아핀 암호 (Shift & Affine Cipher)

특히 Affine Cipher의 키 공간(Key Space) 계산은 시험에 함정 문제로 자주 나오므로, 교수님의 설명 흐름을 따라 논리적으로 이해하는 것이 중요합니다.

1. Shift Cipher (시프트 암호 / Caesar Cipher)

(1) 배경 및 개념

• 역사: 로마의 장군 율리우스 카이사르(Julius Caesar)가 전쟁터에서 장군들과 통신할 때 사용했습니다. 당시 적들은 이 암호를 해독하지 못해 카이사르가 승리할 수 있었습니다.

• 원리: 알파벳 순서에서 $K$만큼 오른쪽으로 이동(Shift)하여 문자를 바꿉니다. 끝까지 가면 다시 앞으로 돌아옵니다(Wrap-around).

(2) 수학적 정의 (Mod 26)

알파벳이 26개니까 mod 26
알파벳 A~Z를 0~25의 숫자로 매핑합니다. ($A=0, B=1, ..., Z=25$)

• 키 ($K$): 이동할 칸의 수 ($0 \le K \le 25$)
• 암호화 (Encryption):
  $y = (x + K) \pmod{26}$
• 복호화 (Decryption):
  $x = (y - K) \pmod{26}$
  (만약 $y-K$가 음수가 되면 26을 더해서 양수로 만듭니다.)

(3) 보안성 분석 (Security Analysis)

질문: 이 암호는 안전한가?
답변: 아니요 (No).
이유: 키 공간(Key Space)이 너무 작습니다
.가능한 키 $K$의 개수는 0부터 25까지 총 26개입니다. (사실 0은 암호화가 안 되므로 의미 있는 키는 25개뿐).
공격자가 25번만 시도해보면(Brute Force) 즉시 해독 가능합니다.

2. Affine Cipher (아핀 암호)

Shift Cipher의 발전된 형태로, 곱셈과 덧셈을 결합한 방식입니다.

(1) 암호화 (Encryption)

단일 키 대신 $(a, b)$라는 키 쌍(Key Pair)을 사용합니다.

$y = (a \cdot x + b) \pmod{26}$

• $x$: 평문 (Plaintext)
• $y$: 암호문 (Ciphertext)
• $a, b$: 키 (Key)

(2) 복호화 (Decryption) - ★중요★

암호화 식을 $x$에 대해 정리해야 합니다. 여기서 역원(Inverse) 개념이 등장합니다.

식 변형: $y - b \equiv a \cdot x \pmod{26}$
양변에 $a$의 역원($a^{-1}$)을 곱함:

$x = a^{-1} \cdot (y - b) \pmod{26}$

교수님 강조: 여기서 $a^{-1}$은 $1/a$가 아닙니다! $a$와 곱해서 $\pmod{26}$에서 1이 되는 정수입니다.

(3) 키 공간(Key Space) 분석 - ★시험 출제 포인트★

"Affine Cipher의 가능한 키의 총개수는 몇 개인가?"

오답: $a$도 26개, $b$도 26개니까 $26 \times 26 = 676$개? (땡!)

정답 분석:

• $b$ (덧셈 키): 제한이 없습니다. 0~25 모두 가능합니다. $\rightarrow$ 26가지
• $a$ (곱셈 키): 제한이 있습니다. 복호화를 하려면 반드시 $a^{-1}$가 존재해야 합니다.

앞서 배웠듯 역원이 존재하려면 $\text{gcd}(a, 26) = 1$이어야 합니다.

즉, 26과 서로소(Coprime)인 수만 $a$가 될 수 있습니다.
26은 $2 \times 13$이므로, 2의 배수와 13의 배수는 제외됩니다.
가능한 $a$의 목록:$\{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25\}$(짝수 제외, 13 제외) $\rightarrow$ 총 12가지

최종 키 공간 크기:

$(\text{가능한 } a \text{의 개수}) \times (\text{가능한 } b \text{의 개수}) = 12 \times 26 = 312$

결론: 키의 개수가 312개로 늘어났지만, 여전히 컴퓨터로 1초도 안 걸려서 뚫리기 때문에 안전하지 않습니다.

3. 추가 설명 (심화 이해를 위해)

Q1. 왜 $a$는 26과 서로소여야 하나요?
만약 $a$와 26이 서로소가 아니라면(예: $a=2$), 1대1 대응(One-to-One Mapping)이 깨집니다.

• 예: $a=2, b=0$ 일 때
  $x=0$ (A) $\rightarrow 2 \times 0 = 0 \pmod{26}$ $\rightarrow$ A
  $x=13$ (N) $\rightarrow 2 \times 13 = 26 \equiv 0 \pmod{26}$ $\rightarrow$
  A보시다시피 A와 N이 둘 다 A로 암호화됩니다. 이렇게 되면 나중에 A를 보고 원래 이게 A였는지 N이었는지 복호화할 수가 없게 됩니다. 그래서 반드시 역원이 존재하는(서로소인) $a$만 써야 합니다.

Q2. 복호화 식 $x = a^{-1}(y-b)$ 계산은 어떻게 하나요?
예를 들어, 키가 $(a=3, b=5)$라고 합시다. 암호문 $y=10$을 복호화해 볼까요?

1. $a^{-1}$ 구하기: $3 \times ? \equiv 1 \pmod{26}$
   $3 \times 9 = 27 \equiv 1$.
   따라서 $a^{-1} = 9$입니다.

2. 공식 대입:
   $x = 9 \times (10 - 5) \pmod{26}$
   $x = 9 \times 5 = 45$
   $45 \pmod{26} = 19$
   따라서 평문 $x$는 19 (알파벳 T)가 됩니다.

Affine Cipher의 수학적 원리와 키 개수 계산 함정을 이해하는 데 도움이 되셨나요? 이 부분은 계산 문제로 나오기 딱 좋으니 $12 \times 26 = 312$라는 수치를 꼭 기억해 두세요!