AYSTORY

algo_lec24 본문

Computer Algorithms

algo_lec24

bye0nzn 2025. 6. 7. 00:07

Number theory and cryptographic algorithms (Part 3)
Spring 2025 Computer Algorithms

Number theory basics

  • Zn∗의 원소 개수를 오일러 파이 함수 ϕ(n) "Euler phi function"이라고 부름.

  • 여기서 p는 n을 나누는 모든 소수.
  • 만약 p가 소수라면, ϕ(p) = p−1.

먼저 n=9일 때, 9를 소인수분해하면, 9 = 3^2.
따라서 “n을 나누는 소수들”은 단 하나, p=3밖에 없다.

Cryptographic Algorithms and Protocols

  • 수론은 현대 암호 알고리즘·프로토콜의 핵심 도구.
  • 많은 보안 기법이 수론 기반으로 설계됨.
  • 이번 강의에서는 다음 두 개의 공개키 암호화 예시를 다룸:
    1. Merkle–Hellman Knapsack
    2. RSA Scheme
  • 그 전에 고전적(비대칭 전 키) 방식 먼저 복습.

Symmetric (Private) Key Cryptography

  • 앨리스(Alice)와 밥(Bob)이 동일한 비밀 키 K를 공유한다고 가정.
    1. 앨리스가 평문 mm을 EK(m)으로 암호화하여 밥에게 전송.
    2. 밥은 비밀 키 K로 DK(EK(m))=m을 계산하여 복호화.
  • 즉, 암호화·복호화에 모두 같은 키를 사용함.
  • 예시
    1. Classical algorithms: Caesar, Playfair, Vigenère, Hill cipher, Enigma 등
    2. Modern algorithms: DES, 3DES, AES, SEED 등
  • General Goals 디자인 목표
    1. hard - EK(m)만 보고 m이나 K를 알아내기가 어려워야 함.
    2. easy - 주어진 K를 바탕으로 암호화/복호화 연산은 매우 빨라야 함.
  • Problems with private key systems 단점
    1. 통신하려면 두 당사자가 안전한 방법으로 동일한 K를 공유해야 함.
    2. 만약 n명이 통신하려면 각 사용자마다 n-1개의 서로 다른 키를 유지해야 함 (총 n(n−1)2개의 키 관리 필요).

 

Public Key Cryptography

  • 1976년 처음 고안된 공개키 암호 방식은 위의 문제를 해결함.
  • 각 사용자는 공개키(Public Key)와 비밀키(Secret Key)를 쌍으로 가짐.
  • 예) Bob이 Alice에게 메시지 m을 보낼 때:
    1. 밥은 앨리스의 공개키 PA로 EPA(m)을 계산하여 암호문 전송. encrypt
    2. 앨리스는 자기 비밀키 SA로 DSA(EPA(m))을 계산해 복호화. descrypt
  • 모든 사용자의 공개키는 공개 디렉터리에 저장될 수 있음.
    • 누구나 해당 디렉터리에서 상대방 공개키를 가져다 메시지 암호화에 사용 가능.
  • secret keys는 오직 해당 사용자만 알고 있으므로, 암호화된 메시지는 오직 의도한 수신자만 복호화할 수 있음.

Merkle–Hellman Knapsack Algorithm

  • Sum-of-subset problem (or Knapsack problem) : revisited
    • 주어진 양의 정수 집합 S=[a1,a2,…,an]과 목표합 T가 주어졌을 때,
      이진 벡터 V=(v1,…,vn) (vi∈{0,1})을 찾아 ∑ai*vi=T이 되게 한다.
    • 이 문제는 일반적으로 NP-난해(NP-hard).
NP에 속한 임의의 문제 Y를 다항식 시간 환원(polynomial-time reduction)을 통해 X로 변환할 수 있다는 의미
  • super-increasing (or simple) knapsack
    • additional restriction to the Knapsack problem
      • S가 “super-increasing sequence” (초가열 수열)이 되어야 함.
    • 즉, ak>∑aj for all 1≤k≤n.

  • 예시:
    • S=[1, 4, 11, 17, 38, 73] (super-increasing)
    • 목표합 T1=96,  T2=95
  • 해법: 큰 원소부터 차례로 빼나가는 방식
    1. 96: 73? Yes, 96−73=23
    2. 23: 38? 38>23이므로 No
    3. 23: 17? Yes, 23−17=6
    4. 6: 4? Yes, 6-4=2
    5. 2: 남은 원소 [1]만 검사 → 2-1=1 “No solution”
  • T2=95도 비슷하게 계산 → 해를 구할 수 있음.
  • 아이디어는 이진 메시지를 배낭 문제( knapsack problem )의 해로 부호화함으로써,  
    평문에서 “1”에 대응하는 항목들만 골라 더한 합을 암호문(타깃 합)으로 사용하는 것이다.

 

  • Example (block size=6 bit)
    • (public) Plain text: 1 0 1 0 0 1 / 0 1 1 0 1 0 …
    • (secret) Knapsack: 1 2 5 9 20 43 / 1 2 5 9 20 43 …
    • Target sum: 49 / 27, …
      • 예: 49를 얻기 위해 43 + 5 + 1 = 49
    • 암호문 하나가 49라면, 대응 평문 블록 1 0 1 0 0 1이 됨.
  • 공개키 (Public Key): (hard) knapsack 문제에 해당하는 수열 H
  • 비밀키 (Secret Key): 대응하는 super-increasing(knapsack) 수열 S

 

  • Transforming a super-increasing knapsack to a hard one
  1. a simple Knapsack S=[s1,s2,…,sm] 선택
  2. multiplier w와 modulus n을 고르되, n>sm이며 gcd⁡(w,n)=1 (보통 n은 소수)
  3. “hard knapsack” H=[h1,h2,…,hm] when hi  =  w*si mod n .
    • 이때 H가 공개키가 되고, S + (w,n)가 비밀키가 됨.
  • S=[1, 2, 4, 9], w = 15, n=17
    1. 1×15  mod 17=15
    2. 2×15  mod 17=13
    3. 4×15  mod 17=9
    4. 9×15  mod 17=16
  • 따라서 하드 knapsack H=[15, 13, 9, 16]
  • 이 H가 공개키(public key).
  • Encypting a message (block size=4 bit)
    • S=[1,2,4,9],  H=[15,13,9,16]
    • public key is H while S is kept secret.
  • Decryption algo. 복호화 알고리즘
    • S가 simple knapsack 일 때, H = w*s mod n
    • The ciphertext C(암호문) produced by the encryption algo. is C=H*P=w*S*P  mod n where P is plaintext.
    • To decipher(암호해독), multiply C by w^(-1) 
      • w^(-1) * C = w^(-1) * H * P = w^(-1) * w * S * P = S * P mod n
      • where w^(-1) * w = 1 mod n
    • 이렇게 얻은 S와 목표합 w^(-1)*C를 해결하면 원래 평문 P를 recover(복원)
  • secrety key S={1,2,4,9}, public key  H={15,13,9,16},  w=15,  n=17
  • P = 0100 1011 1010 0101
  • Encrypted message: 13 40 24 29
    1. (0,1,0,0)·H = 13
    2. (1,0,1,1)·H = 40
    3. (1,0,1,0)·H = 24
    4. (0,1,0,1)·H = 29

x=8 (그리고 y=-7)을 구하는 법

  • Decrypted message, where 15^(-1) mod 17 = 8 (extended Euclidean algo. 결과)
  • w^(-1)*C 구하고 mod n 연산 
    1. 13×8  =104 mod  17=2  ⟶  (0,1,0,0)
    2. 40×8 =320  mod 17=14  ⟶  (1,0,1,1)
    3. 24×8 =192  mod  17=5  ⟶  (1,0,1,0)
    4. 29×8 =232   mod 17=11  ⟶  (0,1,0,1)

RSA public key cryptographic algorithm

  • 공개키는 공개 저장소에 보관되고, 비밀키는 오직 해당 사용자만 소유.
  • 암호화/복호화 흐름: c=EPA(m), m=DSA(c) 
  • RSA: Ronald Rivest, Adi Shamir, Leonard Adleman이 1978년 발표.
    • Rivest(1947~), MIT 교수
    • Shamir(1952~), Weizmann Institute 교수
    • Adleman(1945~), USC 교수
  • 현재 가장 널리 쓰이는 공개키 암호 알고리즘. most widely-used public key cryptographic algo.
  • 소인수분해의 어려움 기반. based on prime factrorization
  • applications
    • Public key cryptography(공개키 암호화), digital signature(디지털 서명), Key exchange protocol(키 교환 프로토콜) 등.
  • Key Setup
    • Public key: (n,e)
    • Secret key: d
  1. 두 개의 큰 소수 p, q 선택
    (일반적으로 ≥1024 bit 크기의 소수를 사용하고, 길이가 비슷해야 보안에 유리)
  2. n=p×q
  3. ϕ(n)=(p−1)(q−1)
  4. public key e: gcd⁡(e,ϕ(n))=1,  1<e<ϕ(n)
  5. secret key d: d=e^(−1) mod  ϕ(n) (확장 유클리드 알고리즘 사용)
  6. 암호화 Encryption: c=m^e  mod n (m < n)
  7. 복호화 Decryption: m=c^d  mod n
  • p, q가 노출되면 ϕ(n) 계산이 가능해지고, 그 결과 e, d도 구해지기 때문에 p, q 보호가 매우 중요.
Example
  • p=7, q=11  ⟶  n = p x q = 7×11 = 77
  • ϕ(n) = (p-1)(q-1) = (7−1)(11−1) = 6×10 = 60
  • e=7 (1 < e <  ϕ(n)이고 gcd⁡(7,60)=1)
유클리드 호제법을 “gcd⁡(7, 60)”으로 시작하여 단계별로 계산하면 다음과 같습니다:

첫 단계: gcd⁡(7, 60)
60÷7=8   … 나머지  4  ⟹  60=7×8+4.
따라서 gcd⁡(7, 60)  =  gcd⁡(7, 4).

두 번째 단계: gcd⁡(7, 4)
7÷4=1   … 나머지  3  ⟹  7=4×1+3.
따라서 gcd⁡(7, 4)  =  gcd⁡(4, 3).

세 번째 단계: gcd⁡(4, 3)
4÷3=1   … 나머지  1  ⟹  4=3×1+1.
따라서 gcd⁡(4, 3)  =  gcd⁡(3, 1).

네 번째 단계: gcd⁡(3, 1)
3÷1=3   … 나머지  0  ⟹  3=1×3+0.
이때 나머지가 0이므로 연산을 멈추고, 마지막 비(0이 아닌)나머지인 11이 최대공약수입니다.

결론: 
gcd⁡(7, 60) = gcd(1,0) = 1.
  • d = e^(−1) mod  60 = 7^(−1) mod  60=43
    (Extended Euclidean algo.)
1. 유클리드 호제법으로 gcd⁡(7, 60)=1 확인

60=7×8+4 ⟹  4=60−7×8
7=4×1+3 ⟹  3=7−4×1
4=3×1+1 ⟹  1=4−3×1
3=1×3+0 → 나머지가 0이므로 종료, gcd⁡(7,60)=1.

2. 뒤로 올라가며 확장유클리드로 1을 7과 60의 선형 결합으로 표현

Step 3로부터
1  =  4−3×1.

여기서 3을 Step 2 식으로 대체:
Step 2로부터
3=7−4×1  ⟹  1=4−( 7−4×1 )=4−7+4=2⋅4−7.
즉, 1=2⋅4−7.

이제 4를 Step 1 식으로 대체:
Step 1로부터
4=60−7×8  ⟹  1=2( 60−7×8 )−7=2⋅60−16⋅7−7=2⋅60−17⋅7.

정리하면,
1=(−17)×7  +  2×60.

따라서 확장 유클리드 결과로 얻은 식은 7×(−17)+60×2  =  1이고,
모듈로 60에서 보면, 7×(−17) ≡ 1(mod60).
즉, 7×x≡1(mod60) ⟹ x≡−17(mod60).

−17  mod 60 = 60−17 = 43이므로, x = 43이 “7의 역원 modulo 60”
  • 암호화
    • Plaintext m=8
    • Ciphertext c=8^7  mod 77 = 57
8^1 mod 77 = 8
8^2 mod 77 = 64
8^3 mod 77 = 50
8^4 mod 77 = 15
8^5 mod 77 = 438
8^6 mod 77 = 36
8^7 mod 77 = 57

따라서 실제 암호화 단계에서 c=8^7 mod 77 = 57
  • 복호화: m=57^43  mod 77=8.
  • 즉, 올바르게 복원됨.

Square-and-multiply Method

  • 공개키 암호화 대부분에서 y = a^x mod n 연산이 필요.
  • 일반 지수승 연산 a^x은 x가 매우 큰 경우 비효율적이기 때문에, “Square-and-multiply” 기법을 사용하여 빠르게 계산
    • represent the exponent in binary and use square and multiplication operations for exponentiation
    • 지수를 이진수로 표현한 뒤, 제곱 연산과 곱셈 연산을 반복.

Square‐and‐Multiply(x, c, n):
    # x: 밑 (base)
    # c: 지수 (exponent), 이진수로 c = (c_{l-1} c_{l-2} ... c_0)_2
    # n: 모듈러스 (modulus)

    z ← 1
    # 지수의 최상위 비트(c_{l-1})부터 c_0까지 순차 처리
    for i from (l - 1) down to 0 do
        # 1) 먼저 z를 제곱(제곱 후 모듈러 n)
        z ← (z × z) mod n

        # 2) 만약 현재 비트 c_i가 1이면, 
        if c_i = 1 then
            #   z에 다시 한 번 x를 곱하고 모듈러 n
            z ← (z × x) mod n
        end if
    end for

    return z

 

Square-and-multiply Method - Example

  • n=11413,  c=3533,  x=9726,  z=9726^3533 mod 11413. 
  • 지수 3533를 이진수로: 3533_{10} = 110111001101_{2}.

  • 최종 결과: z=5761

square_and_multiply_explanation.pdf
0.16MB

 

RSA public key cryptographic algorithm

  • 타당성(정당성)

  • 실제 암호화·복호화 효율을 높이기 위해
    • 보통 e=3(이진수로 11), 17(이진수로 10001), 65537(이진수로 10000000000000001) 같은 작은 값 사용.

 

'Computer Algorithms' 카테고리의 다른 글

algo_lec26  (3) 2025.06.07
[정수론 기초] algo_lec25  (2) 2025.06.07
algo_lec23  (1) 2025.05.30
algo_lec22  (0) 2025.05.30
algo_lec21  (1) 2025.05.23
'Computer Algorithms' Related Articles more