현대 암호학 개론

컴퓨터 보안의 세 가지 핵심 목표는 기밀성(Confidentiality), 무결성(Integrity), 가용성(Availability)이며, 이를 CIA 삼원칙이라고 합니다.

  • 데이터 기밀성: 비인가된 사용자에게 비밀 정보가 노출되지 않도록 보장하고, 비인가된 사용자가 이를 사용할 수 없도록 하는 것을 의미합니다.

OSI 보안 아키텍처는 보안 공격, 보안 서비스, 보안 메커니즘에 초점을 맞춥니다.

  • 보안 공격: 정보 시스템의 보안을 위협하는 모든 활동을 말합니다.
    • 수동적 공격: 시스템의 정보를 획득하거나 이용하려 하지만 시스템 자원에는 영향을 주지 않는 공격입니다. 정보 내용 누설, 트래픽 분석 등이 포함됩니다. 수동적 공격은 데이터 변경을 수반하지 않아 탐지가 어렵습니다. 주로 암호화를 통해 방지하며, 예방에 중점을 둡니다.
    • 능동적 공격: 시스템 자원을 변경하거나 시스템 작동에 영향을 주려는 공격입니다. 위장(Masquerade), 재현(Replay), 메시지 수정(Message Modification), 서비스 거부(Denial of Service) 공격으로 나뉩니다.
      • 위장: 어떤 개체가 다른 개체로 가장하는 것입니다.
      • 재현: 공격자가 가로챈 정보를 무단으로 다시 사용하는 것입니다.
      • 메시지 수정: 합법적인 메시지의 일부를 무단으로 변경하거나, 메시지 전송을 지연시키거나, 메시지 순서를 변경하는 것입니다.
      • 서비스 거부: 시스템의 정상적인 작동을 방해하여 사용자에게 서비스를 제공할 수 없게 만드는 것입니다.
  • 보안 서비스: 정보 보안을 강화하기 위한 처리 과정 또는 통신 서비스입니다. 보안 메커니즘을 사용하여 공격에 대응하는 것을 목표로 합니다.
  • 보안 메커니즘: 공격을 탐지, 차단하거나 공격 상태에서 정상 상태로 복구하는 메커니즘입니다.

공격 표면(Attack Surface)은 시스템에서 접근 가능하고 악용될 수 있는 일련의 취약점으로 구성됩니다. 주요 공격 표면은 다음과 같습니다.

  • 네트워크 공격 표면: 기업 네트워크, 광대역 네트워크 또는 인터넷을 포함합니다. 프로토콜 취약점, 서비스 거부 공급, 터미널 통신 링크 등이 포함될 수 있습니다.
  • 소프트웨어 공격 표면: 애플리케이션, 라이브러리 또는 운영 체제의 취약점을 포함합니다.
  • 인간 공격 표면: 주로 시스템 직원이나 외부 인력으로 인해 발생하는 취약점을 포함합니다.

공격 트리(Attack Tree)는 보안 취약점을 악용하는 가능한 기술들의 집합을 계층적으로 표현하는 데이터 구조입니다.

  • 루트 노드는 공격의 목적을 나타내며, 다음 계층은 공격 대상, 그 아래는 공격 방식을 나타냅니다.
  • 트리의 깊이가 깊어질수록 구체적인 공격 방식을 나타내는 잎 노드에 도달합니다.

네트워크 보안 모델은 다음을 고려해야 합니다.

  • 안전한 변환 알고리즘 설계
  • 알고리즘에 필요한 비밀 정보(키) 생성
  • 비밀 정보의 분배 및 공유 방안 설계
  • 보안 변환과 비밀 정보를 활용하여 보안 서비스를 구현하는 프로토콜 지정

전통적인 암호화 기술

암호학 (Cryptology)

암호학은 다음 세 가지 독립적인 특징을 가집니다.

  • 명문을 암호문으로 변환하는 연산 유형: 치환(Substitution)과 전치(Permutation)
    • 치환: 명문의 요소를 다른 요소로 매핑합니다.
    • 전치: 명문의 요소 순서를 재배열합니다. 이 두 연산 모두 정보 손실이 없어야 하며, 즉 모든 연산은 가역적이어야 합니다.
  • 키: 송신자와 수신자가 동일한 키를 사용하면 대칭키 암호, 그렇지 않으면 비대칭키 암호라고 합니다.
  • 명문 처리 방식: 블록 단위 또는 스트림 단위로 처리합니다.

암호 분석(Cryptanalysis)의 목표는 키를 획득하는 것이지, 개별 암호문이 대응하는 명문을 복구하는 것이 아닙니다.

  • 무차별 대입 공격(Brute-force attack)

섀넌(Shannon)은 좋은 암호 시스템이 통계 분석에 저항하기 위한 두 가지 특성을 가져야 한다고 제안했습니다.

  • 확산성(Diffusion): 동일한 키 하에서
    • 유사한 명문은 상당한 차이가 나는 암호문을 생성해야 합니다.
    • 유사한 암호문은 상당한 차이가 나는 명문을 생성해야 합니다.
    • 확산성은 명문과 암호문 간의 관계를 숨겨, 상대방이 암호문 통계를 통해 명문을 찾으려는 시도를 방해합니다.
  • 혼돈성(Confusion): 동일한 명문 하에서
    • 유사한 키는 상당한 차이가 나는 암호문을 생성해야 합니다.
    • 유사한 암호문은 상당한 차이가 나는 키를 생성해야 합니다.
    • 혼돈성은 암호문과 키 간의 관계를 숨겨, 상대방이 암호문 통계를 통해 키를 찾으려는 시도를 방해합니다.

치환 기술: 시저 암호 (Caesar Cipher)

아이디어:

  • 요소 표: 26개의 알파벳을 요소로 하여 순환적으로 배열합니다. 예: abc...xyzabc...
  • 암호 표: 명문 표와 상대적으로, 명문이 변환되어 생성되는 암호문의 집합입니다.
  • 간격: 사용자 정의 가능하며, 현재 알파벳을 대체할 뒤쪽의 알파벳 몇 번째인지 지정합니다. 간격이 다르면 암호 표도 달라집니다.

예를 들어, 간격이 3이면 A는 D, B는 E, C는 F로 치환됩니다.

시저 암호의 세 가지 중요한 특징은 무차별 대입 공격을 사용할 수 있게 합니다.

  • 암호화 및 복호화 알고리즘이 알려져 있습니다.
  • 테스트해야 할 키는 25개뿐입니다.
  • 명문에 사용된 언어는 알려져 있고 그 의미를 쉽게 식별할 수 있습니다.

시연 (DEMO)

다음 시저 암호를 복호화하십시오:

EHVWWLPHRIRIWKHKHBHBDULVLVVVSUSULQJZKHQIQRORZHUHVUVEOEORRRP

이 암호문에 대해 이해할 수 있는 텍스트가 나타날 때까지 모든 이동 값을 시도해 볼 수 있습니다. 시간을 절약하기 위해 이 과정을 수행하는 코드를 빠르게 작성할 수 있습니다.

무차별 대입 공격을 통해 3만큼 이동(앞으로)했을 때, 암호문이 다음의 이해 가능한 텍스트로 복호화됨을 발견했습니다:

BEST TIME OF THE YEAR IS SPRING WHEN FLOWERS BLOOM.

치환 기술: 단일 치환 암호 (Monoalphabetic Substitution)

단일 치환 암호와 시저 암호의 차이점을 먼저 구분해야 합니다.

시저 암호에서는 모든 명문 → 암호문 변환이 동일한 간격을 따라야 합니다. 즉, A가 D에 해당하면 B는 반드시 E에 해당한다고 추론할 수 있습니다. 이 경우 암호 표는 26개뿐입니다.

단일 치환 암호에서는 모든 명문 → 암호문 변환이 동일한 간격을 따르지 않습니다. 즉, A가 D에 해당하더라도 B는 A/B/C/E/F... 중 임의의 문자에 해당할 수 있습니다. 일대일 대응 관계만 보장되면, 명문과 암호문은 임의의 관계로 결정될 수 있습니다. 이 경우 암호 표는 26!개로, 복잡성이 크게 증가합니다.

그러나 치환 기술의 약점은 해결되지 않았습니다:

  • 단일 문자 대체는 문자의 빈도를 변경하지 않으므로, 원본 텍스트의 통계적 특성이 거의 완전히 유지됩니다.
  • 치환 암호에서 명문 구조가 암호문에 잔류하는 정도를 줄이는 두 가지 주요 방법이 있습니다.
    • 명문의 여러 문자를 함께 암호화합니다.
    • 다중 치환 암호를 사용합니다.

플레이페어 암호 (Playfair Cipher)

플레이페어 암호는 명문의 두 문자 조합을 하나의 단위로 취급하고, 이 단위를 암호문의 두 문자 조합으로 변환합니다.

암호 표 (행렬) 생성

플레이페어 암호에서 암호 표는 지정된 키 문자열로 구성된 행렬입니다.

  1. 키 문자열과 5x5 행렬을 준비합니다.
  2. 키 문자열에서 중복을 제거하여 순서 집합 A를 얻습니다.
  3. 26개의 알파벳에서 중복을 제거한 집합 A를 사용하여 순서 집합 B를 얻습니다.
  4. I와 J는 하나의 문자로 취급합니다.
  5. 왼쪽에서 오른쪽으로, 위에서 아래로 순서 집합 A를 행렬에 채우고, 그 다음 순서 집합 B를 채웁니다.
명문 표 정리
  1. 명문 문자를 두 개씩 그룹화하여 각 그룹을 한 쌍으로 만듭니다.
  2. 분할 후, 동일한 문자로 이루어진 쌍이 있으면, 해당 쌍의 문자 사이에 채움 문자(예: X)를 삽입합니다.
  3. 분할 및 채움 후, 동일한 행에 나타나는 명문 쌍의 문자(인접할 필요 없음)는 해당 행의 오른쪽 문자로 대체됩니다. 행의 마지막 문자는 행의 첫 번째 문자로 대체됩니다. (예: ar → RM)
  4. 분할 및 채움 후, 동일한 열에 나타나는 명문 쌍의 문자(인접할 필요 없음)는 해당 열의 아래쪽 문자로 대체됩니다. 열의 마지막 문자는 행의 첫 번째 문자로 대체됩니다. (예: hs → BP)
  5. 그렇지 않은 경우, 명문 쌍의 각 문자는 해당 문자와 같은 행에 있고 다른 문자와 같은 열에 있는 문자로 대체됩니다. (즉, 사각형 규칙에 따라 옆 모서리로 대체됩니다). (예: ea → IM/JM)
시연 (DEMO)

키워드 "monarchy"를 사용하여 "ballon"을 암호화합니다.

  1. 중복을 제거한 순서 집합 A는 [m, o, n, a, r, c, h, y]입니다.
  2. 26개의 알파벳에서 중복을 제거한 집합 A를 사용하여 순서 집합 B [b, d, e, f, g, i, j, k, l, p, q, s, t, u, v, w, x, z]를 얻습니다.
  3. I와 J를 하나의 문자로 간주하고 순서 집합 A와 B를 채우면 다음과 같은 행렬을 얻을 수 있습니다.
  4. 암호화할 명문은 "balloon"이므로, 두 문자씩 그룹화하면 "balloon" → "ba ll oo n" → "ba lx lo on"이 됩니다.
  5. "ba"는 동일한 열에 있으므로 "ib"로 대체됩니다. "lx"는 행과 열이 다르므로 사각형 규칙에 따라 "su"로 대체됩니다. "lo"는 행과 열이 다르므로 사각형 규칙에 따라 "pm"으로 대체됩니다. "on"은 동일한 행에 있으므로 "na"로 대체됩니다.
  6. 최종 암호문은 "ibsupmna"입니다.

치환 기술: 다중 치환 암호 (Polyalphabetic Substitution) (비제네르 암호)

  • 다중 치환 암호는 여러 개의 치환 표를 사용하며, 암호화 시 다른 치환 표를 번갈아 사용합니다. 단, 암호화 및 복호화 시 사용되는 치환 표의 순서가 일치해야 합니다.
  • 다중 치환 암호의 주요 장점은 키 공간을 확장하여 전체적인 통계적 특성을 더 철저하게 파괴한다는 것입니다.
  • 비제네르 암호는 본질적으로 확장된 시저 암호입니다. 비제네르 암호는 여러 개의 치환 표를 가지며, 각 표는 다른 간격을 사용합니다. 암호화 시 다른 치환 표를 번갈아 사용합니다.

다중 치환 암호 시연 (DEMO)

명문 집합 {1, 2, 3, 4}

치환 표 1: {1:2, 2:4, 3:3, 4:1}

치환 표 2: {1:4, 2:1, 3:2, 4:3}

치환 표 1과 2를 번갈아 사용합니다. 다음 명문 123112를 암호화합니다:

1 → (표 1, 첫 번째 사용) → 2

2 → (표 2, 첫 번째 사용) → 1

3 → (표 1, 두 번째 사용) → 3

1 → (표 2, 두 번째 사용) → 4

1 → (표 1, 세 번째 사용) → 2

2 → (표 2, 세 번째 사용) → 1

암호문: 213421

비제네르 암호 시연 (DEMO)

비제네르 암호에서 암호 표는 지정된 키 문자열로 구성된 행렬입니다.

  1. 26x26 행렬을 구성합니다. 첫 번째 행은 [a, b, ..., z]이고, 두 번째 행은 첫 번째 행을 오른쪽으로 한 칸 순환 이동한 [b, c, ..., a] 등입니다.
  2. 임의의 키 문자열을 선택합니다.
  3. 암호화할 명문과 키 문자열을 비교합니다. 키가 명문보다 짧으면, 키를 반복하여 명문과 길이가 같도록 합니다.
  4. 암호화 과정은 명문 문자와 키 문자의 암호 표에서의 위치 관계에 기반합니다. 명문 문자는 행을 결정합니다: 암호 표에서 명문 문자로 시작하는 행을 찾습니다. 키 문자는 열을 결정합니다: 암호 표에서 키 문자를 열 머리글로 하는 열을 찾습니다. 교차점의 문자가 암호 문자입니다.

키: deceptive

암호화할 명문: wearediscoveredsaveyourself

확장 키: deceptivedeceptivedeceptive

명문 문자 w에 해당하는 암호문은 Z입니다 (좌표 (w, d)).

전체 암호문: ZICVTWONGRZGVTWAVZHCOYGLMGI

다중 치환 암호: 로터 기계 (Enigma)

  • 송신자는 세 개의 로터를 정렬하여 17,576개의 방향 중 하나로 설정합니다 (실제로 로터의 초기 방향이 키이며, 송수신자 간에 사전에 합의되어야 합니다). 그런 다음 명문을 순서대로 입력하고 빛나는 문자를 순서대로 기록하면 암호화된 메시지를 전신으로 보낼 수 있습니다.

단일 치환 암호: 아핀 암호 (Affine Cipher)

아핀 암호는 알파벳의 모든 문자가 간단한 수학 방정식을 사용하여 암호화되며, 숫자로 변환되거나 다시 알파벳으로 변환됩니다. 모든 문자는 (ax + b) mod m 방정식을 사용하여 암호화됩니다. 여기서:

암호화 시
  • 각 문자는 숫자로 매핑됩니다 (일반적으로 A=0, B=1, ..., Z=25). 그런 다음 아핀 변환 함수 (ax + b) mod m을 사용하여 암호화되고, 숫자로 변환된 후 다시 알파벳으로 변환됩니다.
    • a와 b는 키입니다.
    • x는 명문 문자에 해당하는 숫자입니다.
    • m은 알파벳의 개수이며, 일반적으로 26입니다.
    • a와 m은 서로소여야 합니다. m이 일반적으로 26이므로, a는 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25 중에서 선택할 수 있습니다. (a > 26은 반복 계산으로 이어져 의미가 없습니다.)
    • a가 1일 때, 아핀 변환은 본질적으로 시저 암호입니다.
복호화 시
  • 각 문자는 숫자로 매핑됩니다 (일반적으로 A=0, B=1, ..., Z=25). 그런 다음 아핀 변환 복호화 함수 a-1(x - b) mod m을 사용하여 복호화되고, 숫자로 변환된 후 다시 알파벳으로 변환됩니다.
    • 여기서 a-1은 a의 모듈러 곱셈 역원입니다. 예를 들어, 3의 모듈러 곱셈 역원은 3x mod 26 = 1을 만족하는 x를 찾는 것으로, x = 9임을 알 수 있습니다.

이것은 본질적으로 무차별 대입이지만, 더 구체적으로 말하면 다음과 같은 아이디어가 있습니다. mod 결과가 1이 되도록 하려면, 방정식의 왼쪽 결과는 항상 오른쪽 결과의 가능한 배수보다 1 커야 합니다. 오른쪽 결과의 가능한 값은 26, 52, 78, 104, 130...이며, 따라서 오른쪽은 27, 53, 105, 131... 중에서만 선택할 수 있어 빠르게 일치시킬 수 있습니다.

시연 (DEMO)

명문: HELLO

매개변수: a = 5, b = 8, m = 26. 아핀 변환 함수는 (5x + 8) mod 26입니다.

암호화 과정

H의 경우, 암호화 과정은 (5 * 7 + 8) mod 26 = 43 mod 26 = 17 → R입니다.

이하 동일하게 진행하면 암호문은 RCLLA가 됩니다.

복호화 과정

5의 모듈러 곱셈 역원은 5x mod 26 = 1을 만족하는 x이므로 21입니다. 따라서 복호화 변환 함수는 21(x - 8) mod 26입니다.

암호 문자 R의 경우, 복호화 과정은 21(17 - 8) mod 26 = 189 mod 26 = 7 → H입니다.

이하 동일하게 진행하면 명문은 HELLO가 됩니다.

암호화 함수가 복호화 함수와 같음을 증명

치환: 힐 암호 (Hill Cipher)

힐 암호는 행렬 연산을 기반으로 하는 다중 문자 대체 암호로, 대수적 방법을 사용한 최초의 암호화 알고리즘이며, 주로 행렬과 벡터의 곱셈을 사용하여 암호화 및 복호화를 수행합니다.

힐 암호는 단순 암호문 공격에는 강하지만, 알려진 명문 공격에는 약합니다. 실제로 n개의 독립적인 명문 문자열과 해당 암호문이 주어지면 키를 결정할 수 있습니다.

암호화 공식: C = (K · P) mod m, 여기서:

  • P: 명문의 벡터 형태, 즉 문자를 숫자로 변환한 형태 (예: A=0, B=1, ..., Z=25 → [a,b,c,d]를 [0,1,2,3]으로 변환).
  • K: 키, n x n 행렬 (가역행렬이어야 함).
  • C: 암호문 벡터, 계산된 암호화 결과.
  • m: 알파벳의 크기 (일반적으로 m=26).

암호화 과정:

  1. 행렬의 행과 열이 모두 n인 정사각형 행렬을 선택합니다. 명문 문자열을 n개씩 그룹화하고, 마지막 그룹이 n개 미만이면 X로 채워 n x 1 벡터를 얻습니다.
  2. 그룹의 문자를 숫자로 매핑합니다.
  3. 각 명문 벡터 P와 키 행렬 K를 곱하여 C = (K · P) mod 26을 계산합니다. 각 연산 결과는 n x 1 암호문 벡터 Q가 되며, 이를 다시 문자로 변환하여 암호문을 얻습니다.

복호화 과정:

  1. 암호문 문자열을 n개씩 그룹화하고, 마지막 그룹이 n개 미만이면 X로 채워 n x 1 벡터를 얻습니다.
  2. 그룹의 문자를 숫자로 매핑합니다.
  3. 알려진 키 행렬 K의 역행렬 K'를 구합니다.
  4. 각 암호문 벡터 Q와 키 행렬 K'를 곱하여 C = (K' · Q) mod 26을 계산합니다. 각 연산 결과는 n x 1 명문 벡터 P가 되며, 이를 다시 문자로 변환하여 명문을 얻습니다.

역행렬 구하기

힐 암호의 역행렬은 모듈러 연산을 기반으로 하므로, 역행렬을 구할 때 항상 모듈러 연산을 계산해야 합니다.

시연: 암복호화 과정

시연: 알려진 명문-암호문 쌍, n으로 암호화 행렬 구하기

다음 정보를 사용하여 힐 암호화 행렬을 구합니다.

  • 그룹 길이 n = 2
  • 명문 (명문 쌍): "howareyoutoday"
  • 암호문 (암호문 쌍): "zwseniuspljveu"

명문과 암호문을 그룹 길이 n=2에 따라 해당 열 벡터로 분할하면 명문과 암호문 행렬을 얻게 됩니다.

명문 행렬 P:

h  o  w  a  r  e  y  o  u  t  o  d
11 14 22 0  17 4  24 14 20 19 14 3

암호문 행렬 C:

z  w  s  e  n  i  u  s  p  l  j  v
25 22 18 4  13 8  20 18 15 11 9  21

명문 행렬 P와 암호문 행렬 C를 사용하여, P의 역행렬(모듈러 26)과 C를 곱하여 키 행렬 K를 찾을 수 있습니다.

C = K · P (mod 26)

K = C · P-1 (mod 26)

P-1 (mod 26)을 계산하고 C와 곱하면 키 행렬 K를 얻을 수 있습니다.

치환: 일회용 패드 (One-Time Pad)

  • 메시지와 길이가 같고 반복되지 않는 임의의 키를 사용하여 메시지를 암호화합니다.
  • 각 키는 일회용이며, 암호화 후 다시 사용되지 않습니다.
  • 이론적으로 해독 불가능합니다. 생성된 무작위 출력은 명문과 어떤 통계적 관계도 가지지 않습니다. 암호문은 명문에 대한 어떤 정보도 포함하지 않습니다.

치환 기술: 해독 방법

가장 일반적인 방법은 통계적 방법입니다.

영어에서 가장 자주 사용되는 단일 문자는 e, t, o, a, h, i 순서이며, 가장 적게 사용되는 문자는 z, j입니다.

가장 자주 사용되는 두 문자 조합은 th, in, er, re, an 순서입니다.

가장 자주 사용되는 세 문자 조합은 the, ing, and, ion 순서입니다.

블록 암호 (Block Cipher)

  • 블록 암호는 크기 n의 명문 블록을 함께 암호화하여 동일한 크기의 암호문 블록을 생성합니다.
  • 블록 암호에서 키가 여러 값으로 구성되더라도 단일 키로 간주되어 전체 블록이 암호화됩니다.
  • 플레이페어 암호는 블록 암호이며, 블록 크기는 n=2 (두 문자 함께 암호화)입니다.
  • 힐 암호는 블록 암호이며, 단일 키(행렬)를 사용하여 전체를 암호화합니다. 키가 n x n개의 값으로 구성되더라도 단일 키로 간주됩니다.

전치 (Permutation)

전치는 명문 블록 내부의 문자 순서를 변경하여 정보를 암호화하는 목적을 달성합니다.

첫 번째 전치 방법

  • 명문을 문자 집합 A로 설정합니다.
  • 키는 치환 및 역치환입니다. 치환은 [2, 7, 4, 6, 1, 3, 5] (2는 현재 위치를 2번째 문자로 치환함을 의미). 역치환은 [5, 1, 6, 3, 7, 4, 2]입니다.
  • 암호문은 키(치환)를 사용하여 문자 집합 A의 순서를 변경하여 얻은 문자열 B입니다.

두 번째 전치 방법

  • 명문을 문자열 집합 A로 설정하고, A를 행 우선으로 빈 행렬에 순서대로 채웁니다.
  • 키는 순서 숫자 집합입니다.
  • 키에 있는 숫자의 순서에 따라 행렬의 열을 재배열합니다.

은닉 통신 (Steganography)

은닉 통신은 엄밀히 말해 암호화가 아니며, 비밀 메시지를 다른 메시지 안에 숨기는 방식으로 구현됩니다.

  • 문자 마킹: 인쇄되거나 타자된 텍스트를 선택하고 연필로 다시 씁니다. 이 표시는 일반적인 상황에서는 알아볼 수 없어야 하지만, 종이를 특정 각도로 빛에 비추면 보입니다.
  • 보이지 않는 잉크: 일부 물질은 쓴 후 눈에 보이는 흔적을 남기지 않지만, 가열하거나 특정 화학 물질을 바르면 나타납니다.
  • 바늘 구멍: 일부 글자에 작은 바늘 구멍을 뚫으면, 빛에 비추지 않는 한 구별하기 어렵습니다.
  • 타자기 리본 보정: 줄 사이의 검은색 리본으로 인쇄합니다. 이 리본으로 인쇄된 내용은 강한 빛 아래에서만 보입니다.
  • 워터마킹: 종이에 수작업으로 특정 패턴을 넣어 문서의 진위를 확인합니다.

수학적 기초

정수론 (Number Theory)

나눗셈

참고: a ≠ 0이지만, b는 0일 수 있습니다. b가 0일 때, 모든 a에 대해 a | b는 항상 참입니다. (예: 1 | 0, 2 | 0 ...)

예: 3 | n이고 7 | n이면 21 | n임을 증명하십시오.

3 | n이므로 정수 m이 존재하여 n = 3m이라고 할 수 있습니다. 이를 대입하면 7 | 3m이 됩니다.

또한, 모든 m에 대해 1 | m이 항상 참이므로, 7 | 7m이 항상 참입니다.

선형 연산 규칙을 적용하면, 임의의 x, y에 대해 7 | {x(3m) + y(7m)}이 항상 참입니다.

x = -2, y = 1이라고 하면, 7 | (-6m + 7m) = 7 | m이 됩니다. 이는 21 | 3m = 21 | n을 의미합니다.

유클리드 알고리즘 (Euclidean Algorithm)을 이용한 최대공약수 (GCD) 계산

최대공약수(GCD)는 최대공약수와 같습니다.

유클리드 알고리즘의 시간 복잡도는 O(log n)입니다.

확장 유클리드 알고리즘 (Extended Euclidean Algorithm)을 이용한 두 수의 최대공약수 선형 표현

198과 252의 최대공약수를 구하고, 이를 198과 252의 정수 계수 선형 조합으로 표현하십시오.

gcd(252, 198) = gcd(198, 54) = gcd(54, 42) = gcd(42, 12) = gcd(12, 6) = gcd(6, 0) = 6

이제 확장 유클리드 알고리즘을 사용하여 역으로 계산합니다.

6 = 42 - 3 * 12

12 = 54 - 1 * 42

6 = 42 - 3 * (54 - 1 * 42) = 42 - 3 * 54 + 3 * 42 = 4 * 42 - 3 * 54

42 = 252 - 1 * 198

6 = 4 * (252 - 1 * 198) - 3 * 54 = 4 * 252 - 4 * 198 - 3 * 54

54 = 198 - 3 * 42 = 198 - 3 * (252 - 1 * 198) = 198 - 3 * 252 + 3 * 198 = 4 * 198 - 3 * 252

6 = 4 * 252 - 4 * 198 - 3 * (4 * 198 - 3 * 252)

6 = 4 * 252 - 4 * 198 - 12 * 198 + 9 * 252

6 = 13 * 252 - 16 * 198

따라서, 198 * (-16) + 252 * 13 = 6 입니다.

확장 유클리드 알고리즘을 이용한 모듈러 곱셈 역원 구하기

ax ≡ 1 (mod m), a < m 일 때, 모듈러 곱셈 역원 구하기

  • 유클리드 알고리즘(나눗셈을 이용한 방법)은 두 비음 정수의 최대공약수를 찾을 수 있습니다.
  • 확장 유클리드 알고리즘 형식: 나머지 = 피제수 - 계수 * 제수. 각 단계는 뺄셈으로 이루어집니다.
  • 나머지가 1이 될 때까지 반복적으로 나눗셈을 수행합니다.
  • 이전 단계의 방정식을 대입하여 a와 m의 관계를 얻고, a의 계수가 원하는 역원입니다.

주의해야 할 세부 사항:

  • 나눗셈 계수는 오른쪽에 써서 병합하기 쉽게 합니다.
  • 첫 번째와 마찬가지로, 모든 곱셈은 순서를 주의해야 하며, 모든 항은 항상 두 개씩 곱해진 상태를 유지해야 합니다.
  • 최종적으로 얻은 x가 음수이면, |x| + z = m으로 하여 z를 원하는 값으로 합니다.

ax ≡ 1 (mod m), a > m 일 때, 모듈러 곱셈 역원 구하기

  1. 정상적으로 계산하고, 최종적으로 큰 수의 계수를 원하는 역원으로 사용합니다.

모듈러 연산 (Modular Arithmetic)

합동 (Congruence)

두 정수 a와 b가 합동이라고 하면, m으로 나눈 나머지가 같다는 것을 의미합니다. 기호는 a ≡ b (mod m)입니다.

모듈러 산술 연산 (빠른 거듭제곱 - Modular Exponentiation)

  1. 거듭제곱을 이진법으로 변환합니다.
  2. ans = 1, cur = 밑으로 설정하고 반복을 시작합니다.
  3. 반복 횟수는 이진수 거듭제곱의 길이와 같습니다. 이진수 거듭제곱을 뒤에서부터 봅니다: 1이면 ans = ans × cur (mod 모듈러 수), cur = cur × cur (mod 모듈러 수). 0이면 ans는 변경되지 않고, cur = cur × cur (mod 모듈러 수)가 됩니다.
  4. 최종 ans가 전체 결과입니다.

중국인의 나머지 정리 (Chinese Remainder Theorem - CRT)

  • 모듈러 연산을 가속화하는 데 사용됩니다.
  • 특정 범위 내의 정수는 서로소인 여러 정수로 나눈 나머지를 통해 재구성될 수 있습니다.
  • 매우 큰 수 M에 대한 모듈러 연산을 더 작은 수에 대한 연산으로 변환할 수 있게 합니다.

시연 (DEMO)

다음 연립 합동식을 만족하는 x를 구합니다:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
  1. Mi와 M을 계산합니다. M1 = 5 * 7 = 35, M2 = 3 * 7 = 21, M3 = 3 * 5 = 15. M = 3 * 5 * 7 = 105.
  2. Mi의 모듈러 곱셈 역원을 계산합니다.
    • 35d1 ≡ 1 (mod 3) → 2d1 ≡ 1 (mod 3) → d1 = 2
    • 21d2 ≡ 1 (mod 5) → 1d2 ≡ 1 (mod 5) → d2 = 1
    • 15d3 ≡ 1 (mod 7) → 1d3 ≡ 1 (mod 7) → d3 = 1
  3. 공식을 사용합니다: x = (a1M1d1 + a2M2d2 + a3M3d3) mod M
  4. x = (2 * 35 * 2 + 3 * 21 * 1 + 2 * 15 * 1) mod 105
  5. x = (140 + 63 + 30) mod 105
  6. x = 233 mod 105
  7. x = 23

오일러 정리, 페르마 소정리 (Euler's Theorem, Fermat's Little Theorem)

  • 오일러 함수: n이 양의 정수일 때, n보다 작고 n과 서로소인 양의 정수의 개수를 n의 오일러 함수라고 하며 φ(n)으로 표기합니다. 예: φ(6) = 2 (1, 5); φ(7) = 6 (1, 2, 3, 4, 5, 6).
    • n이 소수이면, φ(n) = n - 1입니다.
    • n = pq이고 p, q가 소수이면, φ(n) = (p - 1)(q - 1)입니다.

오일러 정리를 이용한 큰 정수의 마지막 몇 자리 구하기

  1. 모듈러 수 n의 오일러 함수 값 φ(n)을 계산합니다.
  2. 거듭제곱을 φ(n)을 포함하는 여러 인수의 곱으로 분해합니다.

페르마 소정리를 이용한 지수 모듈러 연산

a와 p가 서로소인 경우:

  1. 페르마 소정리를 사용하여 지수를 모듈러 수보다 작은 형태로 만듭니다.
  2. 지수를 계속 분해하고, 나머지를 곱한 후 최종적으로 모듈러 연산을 수행합니다.

이산 로그 (Discrete Logarithm)

이산 로그 문제는 지수 연산의 역연산입니다. 즉, g, y, p가 주어졌을 때, gx ≡ y (mod p)를 만족하는 x를 찾는 것입니다.

원시근 (Primitive Root)

p를 소수라고 할 때, p에 대한 원시근 g는 gk (mod p)가 k = 1, 2, ..., p-1에 대해 p-1개의 서로 다른 값을 생성하는 정수입니다.

다항식 연산

대칭키 암호 시스템 (Symmetric-key Cryptography)

블록 암호 (Block Cipher)

  • 블록 암호는 입력된 명문 블록을 하나의 단위로 처리하여 동일한 길이의 암호문 블록을 출력합니다.
  • 페이스텔 구조(Feistel structure)는 블록 암호의 대칭 구조 중 하나입니다. 대칭적인 암호 구조이므로, 정보의 암호화와 복호화 과정이 매우 유사하거나 동일합니다. 이는 구현 시 코딩 양과 회선 전송 요구 사항을 거의 절반으로 줄여줍니다.
  • 페이스텔은 곱셈 암호를 사용하여 암호 강도를 높일 것을 제안했습니다.
  • 페이스텔은 치환과 전치를 번갈아 사용하여 암호의 확산 및 혼돈 성능을 향상시킬 것을 제안했습니다.
    • 확산(Diffusion): 각 명문 숫자가 가능한 한 많은 암호문 숫자에 영향을 미치도록 하여, 명문과 암호문의 통계적 특성이 서로 무관하게 만듭니다.
    • 혼돈(Confusion): 암호문과 키 간의 관계를 복잡하게 만듭니다.
    • 곱셈 암호(Product Cipher): 단일 암호화 메커니즘에서 두 개 이상의 다른 유형의 기본 암호(예: 치환 및 전치)를 순차적으로 사용하면, 결과 암호 강도가 각 단일 암호의 강도보다 강해집니다.
  • DES와 같은 전통적인 블록 암호 알고리즘은 모두 페이스텔 구조를 채택했습니다.

블록 암호: DES (Data Encryption Standard)

  • DES는 훌륭한 눈사태 효과(Avalanche effect)를 가지고 있습니다. 명문 또는 키의 한 비트가 변경되면(미세한 변화) 암호문에 큰 영향을 미칩니다.
  • DES는 P-치환을 사용하여 확산성을 달성합니다.
  • DES는 S-box 치환을 사용하여 혼돈성을 달성합니다.

IP 변환, E 확장, P 치환은 모두 조회 테이블을 사용하는 치환입니다.

시연 (DEMO)

다음 S-box가 주어졌을 때, 입력이 101101이면 출력을 구하십시오.

S-box:

   0 1 2 3 4 5 6 7 8 9
0: 14 4 13 1 2 15 11 8 3 10
1: 0 9 14 15 5 2 13 12 11 4
2: 3 10 5 12 6 14 9 11 13 8
3: 15 1 3 10 0 12 11 4 9 8
...

입력: 101101

첫 번째와 마지막 비트: 11 (십진수 3), 따라서 세 번째 행.

중간 비트: 1001 (십진수 9), 따라서 아홉 번째 열.

세 번째 행 아홉 번째 열을 조회하면 14가 나옵니다. 십진수 14는 이진수로 1100이므로, 출력 값은 1100입니다.

블록 암호: AES (Advanced Encryption Standard)

  • AES의 블록 크기는 128비트만 가능합니다.
  • 키 길이는 128/192/256비트이며, 각각 10/12/14 라운드의 반복에 해당합니다.
  • 처리 단위는 바이트입니다. 비교하자면, DES는 비트를 처리 단위로 사용합니다.
  • AES의 기본 연산은 "세 번 대체, 한 번 치환"으로 요약할 수 있습니다.
    • 바이트 대체(SubBytes)
    • 열 섞기(MixColumns)
    • 행 이동(ShiftRows)
    • 라운드 키 더하기(AddRoundKey)
  • AES 복호화의 기본 연산은 다음과 같습니다.
    • 역 행 이동(Inverse ShiftRows)
    • 역 바이트 대체(Inverse SubBytes)
    • 라운드 키 더하기(AddRoundKey)
    • 역 열 섞기(Inverse MixColumns)

블록 암호 운영 모드

메시지 길이가 블록 길이보다 클 때, 메시지를 여러 블록으로 나누어 각각 처리해야 합니다. 이러한 분할 방식/순서를 블록 암호의 운영 모드라고 합니다.

  • 전자 코드북 모드 (ECB)
    • 장점: 간단하고 병렬 계산에 유리하며, 오류가 전파되지 않습니다.
    • 단점: 명문의 패턴을 숨길 수 없습니다. 하나의 블록이 해독되면, 동일한 방법으로 모든 명문 데이터를 복호화할 수 있어 보안성이 낮습니다. 명문에 대한 능동적 공격이 가능할 수 있습니다.
  • 암호 블록 체인 모드 (CBC)
    • 장점: 능동적 공격에 강하며, SSL, IPSec의 표준입니다.
    • 단점: 병렬 계산에 불리하고, 오류가 전파됩니다.
  • 출력 피드백 모드 (OFB): CBC와 유사합니다.
  • 암호 피드백 모드 (CFB)

공개키 암호 (Public-key Cryptography)

공개키 암호가 해결하는 기본 문제:

  • 전통적인 암호 시스템의 키 분배 및 디지털 서명 문제를 해결합니다.

공개키 암호의 특징:

  • 암호화 알고리즘과 키만으로는 복호화 키를 계산적으로 결정하는 것이 불가능합니다. 두 키 중 하나를 사용하여 암호화할 수 있으며, 다른 하나를 사용하여 복호화할 수 있습니다.

공개키 암호의 여섯 가지 구성 요소:

  • 명문, 암호문
  • 공개키, 개인키
  • 암호화, 복호화 알고리즘

공개키 암호의 세 가지 용도:

  • 암호화/복호화: 송신자는 수신자의 공개키로 메시지를 암호화합니다.
  • 디지털 서명: 송신자는 자신의 개인키로 메시지에 서명합니다.
  • 키 교환: 통신 당사자는 공개키 암호를 사용하여 세션 키를 교환한 후, 해당 세션 키로 대칭 암호화를 수행하여 리소스를 절약합니다.

단방향 함수(One-way function)

  • 함정 단방향 함수(Trapdoor one-way function)는 단방향 함수로, 함정 정보 없이는 f(x)에서 x를 찾는 것이 매우 어렵지만, 함정 정보를 알면 f(x)에서 x를 찾는 것이 용이하게 구현될 수 있습니다.

세 가지 암호 시스템 모두 과정은 약간 다르지만, 큰 소수 n을 모듈러로 사용하고 키 쌍을 구성합니다.

RSA

  • RSA는 블록 암호에 속합니다.
  • RSA를 공격하는 세 가지 방법:
    • 무차별 대입 공격
    • 수학적 공격: 본질적으로 두 소수의 곱을 분해하는 것입니다. 공격을 피하기 위해 현재 1024/2048 비트 키를 사용하는 것이 좋습니다.
    • 시간 공격: 복호화 알고리즘의 실행 시간에 의존합니다.

암복호화 시연 (DEMO)

  1. 두 개의 큰 소수 p, q를 무작위로 선택하고, 그 곱 n = p × q를 모듈러로 사용합니다.
  2. n의 오일러 함수 φ(n) = (p - 1)(q - 1)을 계산합니다.
  3. n과 서로소인 암호화 키 e를 선택합니다. 1 < e < φ(n)이고 gcd(e, φ(n)) = 1이어야 합니다.
  4. e × d ≡ 1 (mod φ(n))을 만족하는 d를 e의 모듈러 곱셈 역원으로 계산하여 복호화 키로 사용합니다.
  5. 공개키 PU = {e, n}를 공개하고, 개인키 PR = {d, n}를 보관합니다.
  6. 주의: 전송되는 명문 M은 반드시 n보다 작아야 합니다.

다음 x, y는 전송 텍스트입니다 (개인키는 지수). 암호화 과정: C = Me mod n 복호화 과정: M = Cd mod n

공개키와 개인키의 관계 시연 (DEMO)

공개키는 (e, n)이고 개인키는 (d, n)입니다. 공개키가 공개되므로 개인키의 n도 공개됩니다. 공격자가 개인키의 d를 찾으면 RSA를 해독할 수 있습니다.

공개키 e에서 개인키 d를 유도하는 과정:

  1. n을 두 소수 p, q로 분해합니다. 실제 사용되는 공개/개인키 쌍은 1024/2048 비트에 이르므로, 이러한 분해는 거의 불가능합니다.
  2. φ(n) = (p - 1)(q - 1)을 계산합니다.
  3. e × d ≡ 1 (mod φ(n))에 따라, 개인키 d를 구할 수 있습니다.

예제: RSA 암호 시스템을 사용하여, 수신자의 공개키가 (e, n) = (5, 35)이고 가로챈 암호문이 C = 10일 때, 명문을 복호화하십시오.

  1. 35 = 5 × 7. 5와 7은 모두 소수입니다.
  2. φ(35) = (5 - 1)(7 - 1) = 24.
  3. 5 × d ≡ 1 (mod 24)를 풉니다. 즉, 5 mod 24의 모듈러 곱셈 역원을 구하면 d = 5입니다. 따라서 개인키 PR = (5, 35)입니다.
  4. 복호화 공식을 사용합니다: M = Cd mod n = 105 mod 35.
  5. 105 = 100000.
  6. 100000 mod 35 = 10.
  7. 따라서 명문 M = 10입니다.

DH 키 교환 (Diffie-Hellman Key Exchange)

  • 최초의 공개키 알고리즘입니다.
  • 키 교환 알고리즘만을 제공합니다.
  • 알고리즘 자체는 키 교환(공개 키 생성)만 가능하며, 정보를 교환할 수는 없습니다.
  • 알고리즘의 기초는 유한 체계에서의 지수 연산(소수 모듈러)은 상대적으로 쉽지만, 이산 로그 계산은 상대적으로 어렵다는 것입니다.
  • 중간자 공격(Man-in-the-Middle attack)에 취약합니다.
    • 인증 기능을 추가하고, 공개키 인증서/공유 키를 사용합니다.
  1. 사용자 A와 B는 다음 전역 매개변수를 알고 있습니다: 큰 소수 n (이후 모듈러로 사용), 모듈러 n의 원시근: α (공개 키 계산 시 밑으로 사용).
  2. 각 사용자는 독립적으로 자신의 키 쌍을 생성합니다. 비밀스러운 임의의 수: PR < n, PR은 개인키입니다. 공개 키를 계산합니다: PU = αPR mod n (개인키는 지수).
  3. 각 사용자는 자신의 공개 키 PU를 공개하고, 개인 키 PR을 보관합니다.
  4. A와 B는 두 사람이 공유할 세션 키 Kab를 독립적으로 계산합니다.
  5. 공격자가 개인 키 PR을 알아내려면 이산 로그를 풀어야 하지만, 앞서 언급했듯이 이산 로그 계산은 매우 어렵습니다.

시연 (DEMO)

사용자 A와 B가 있습니다. 전역 매개변수는 n=23, α=5입니다.

  1. A의 개인키: xA = 6. A의 공개 키: yA = 56 mod 23 = 15625 mod 23 = 8.
  2. B의 개인키: xB = 15. B의 공개 키: yB = 515 mod 23 = 30517578125 mod 23 = 19.
  3. A가 계산하는 공유 비밀 키: K = yBxA mod n = 196 mod 23 = 47045881 mod 23 = 2.
  4. B가 계산하는 공유 비밀 키: K = yAxB mod n = 815 mod 23 = 35184372088832 mod 23 = 2.
  5. 두 사용자는 공유 비밀 키 2를 얻습니다.

EIGamal

  • ELGamal 알고리즘은 정보의 안전한 전파에 중점을 두며, 생성된 키 쌍은 정보를 전송하는 데 사용됩니다.
  • ElGamal을 해독하는 것은 Diffie-Hellman 문제를 푸는 것과 같습니다.
  • ElGamal의 보안성은 Z*에서의 이산 로그 문제에 의존합니다.
  • 암호화 시, 다른 메시지에 대해 다른 임의의 수 k를 선택해야 합니다. 그렇지 않으면 공격자가 ElGamal 공개키 시스템을 쉽게 공격할 수 있습니다.

시연 (DEMO)

전역 매개변수: 소수 p=11, 생성원 g=2.

사용자 A:

  • 개인키: xA = 3 (비밀).
  • 공개 키: yA = gxA mod p = 23 mod 11 = 8.
  • 공개키: (p=11, g=2, yA=8).

사용자 B가 A에게 메시지 M=5를 보내려고 합니다.

암호화 과정:

  1. B는 임의의 수 k를 선택합니다. k=4 (비밀).
  2. C1 = gk mod p = 24 mod 11 = 16 mod 11 = 5.
  3. C2 = M × yAk mod p = 5 × 84 mod 11 = 5 × 4096 mod 11 = 5 × 7 mod 11 = 35 mod 11 = 2.
  4. 암호문: (C1=5, C2=2).

A가 복호화하는 과정:

  1. A는 개인키 xA=3를 사용하여 계산합니다.
  2. S = C1xA mod p = 53 mod 11 = 125 mod 11 = 4.
  3. M = C2 × S-1 mod p. S-1 mod 11을 구해야 합니다. 4 × S-1 ≡ 1 (mod 11). S-1 = 3.
  4. M = 2 × 3 mod 11 = 6 mod 11 = 6. (오류 발생, 공식 확인 필요)

정확한 복호화 공식: M = C2 / (C1xA) mod p = C2 × (C1xA)-1 mod p

A가 복호화하는 과정 (수정):

  1. S = C1xA mod p = 53 mod 11 = 125 mod 11 = 4.
  2. S-1 mod 11을 구합니다. 4x ≡ 1 (mod 11) → x = 3.
  3. M = C2 × S-1 mod p = 2 × 3 mod 11 = 6 mod 11 = 6.

다시 확인: ElGamal 복호화 공식은 M = C2 * (C1x)-1 mod p 가 아니라 M = C2 * (yx)-1 mod p 와 관련이 있습니다. ElGamal의 복호화는 M = C2 / (C1x) mod p 가 아니라, M = C2 * (C1x)-1 mod p 입니다. 여기서 C1x는 yk 와 같습니다. 정확한 복호화 공식: M = C2 * (C1xA)-1 mod p

재계산:

  1. A의 개인키 xA = 3.
  2. 공격자는 yAk = 84 mod 11 = 7 을 계산할 수 있습니다.
  3. C1 = 5, C2 = 2.
  4. 공유 비밀 키 K = yAk mod p = 84 mod 11 = 7.
  5. C2 = M * K mod p = 5 * 7 mod 11 = 35 mod 11 = 2.
  6. 복호화: M = C2 * K-1 mod p. K-1 mod 11 = 7-1 mod 11. 7x ≡ 1 (mod 11) → x = 8.
  7. M = 2 * 8 mod 11 = 16 mod 11 = 5.

메시지 M=5가 성공적으로 복호화되었습니다.

디지털 서명 (Digital Signature)

디지털 서명의 기능:

  • 정보가 서명자에 의해 전송되었음을 확인합니다.
  • 메시지가 서명 후 수신될 때까지 변경되지 않았음을 확인합니다.
  • 서명자는 서명을 부인할 수 없습니다.

디지털 서명의 구성:

  • 키 생성: 공개키와 개인키를 생성합니다 (공개키 암호 시스템과 유사).
  • 서명 알고리즘: 개인키를 사용하여 문서에 서명합니다.
  • 검증 알고리즘: 공개키를 사용하여 서명을 검증합니다.

서명 과정은 본질적으로 상대방의 공개키로 암호화하는 것과 같으며, 일반적인 전송과 동일합니다.

해시 함수 (Hash Function)

해시 함수의 주요 기능은 데이터 무결성을 검증하는 것입니다.

해시 함수의 응용:

  • 메시지 인증
    • 메시지 인증은 메시지의 무결성을 검증하는 메커니즘입니다.
    • 해시 함수가 메시지 인증 기능을 제공하는 데 사용될 때, 해시 함수 값은 일반적으로 메시지 다이제스트(message digest)라고 합니다.
    • 일반적으로 메시지 인증은 메시지 인증 코드(MAC, keyed hash function)를 사용하여 구현됩니다.
    • 파일 전송(예: 네트워크 파일 다운로드)에 널리 사용됩니다.
  • 디지털 서명

해시 함수의 보안 조건:

  • 단방향성 (One-way)
  • 약한 충돌 저항성 (Weak Collision Resistance): 주어진 x에 대해 y ≠ x 이면서 H(x) = H(y)를 만족하는 y를 찾는 것이 계산적으로 불가능해야 합니다.
  • 강한 충돌 저항성 (Strong Collision Resistance): 임의의 두 다른 x, y에 대해 H(x) = H(y)를 만족하는 쌍을 찾는 것이 계산적으로 불가능해야 합니다.
  • 의사 난수성 (Pseudo-randomness)

해시 함수에 대한 공격 방법:

  • 무차별 대입 공격
  • 암호 분석 공격

MD5는 512비트 블록 크기로 메시지를 처리합니다.

SHA-1 (Secure Hash Algorithm 1): 160비트 메시지 다이제스트를 생성하는 해시 함수입니다.

MD5는 리틀 엔디안 구조를 사용하고, SHA는 빅 엔디안 구조를 사용합니다.

태그: 암호학 보안 대칭키 암호 비대칭키 암호 해시 함수

10월 28일 01:01에 게시됨