algo_lec26

 

Public Key Cryptography

• 소인수 분해 문제 (Prime Factorization)→RSA
  • n=p×q일 때, p,q를 알아내는 것은 쉽지 않음 (NP-난해).
• 이산로그 문제 (Discrete Logarithm)→ElGamal
  • 주어진 g,y,p에 대해 g^x ≡ y (mod p)를 만족하는 x를 구하는 것 역시 매우 어려움.

이 두 문제의 난이도를 이용해 RSA, ElGamal 같은 공개키 암호가 동작한다.

---

Key Exchange or Establishment

• 시나리오
  • Alice와 Bob은 카페의 공용 인터넷을 통해 민감한 데이터를 주고받고 싶어하지만, 잠재적인 도청자로부터 통신을 보호해야 합니다. (암호화가 필요합니다!)
  • 그러므로, 그들은 민감한 데이터를 암호화할 key가 필요.
  • 안전하지 않은 채널을 통해 이 키를 어떻게 안전하게 공유할 수 있을까?
  • Diffie-Hellman key exchange protocol
    • By Whitfield Diffie and Martin Hellman
    • Discrete Logarithm problem (y=g^x mod p)
      • even if we know y,g, and p, it is hard to compute x.

---

Vulnerability of Diffie-Hellman key exchange

• Man-in-the-middle attack

Diffie–Hellman 키 교환이 인증 없이 실행될 때 발생할 수 있는 전형적인 중간자 공격(Man-in-the-Middle Attack) 을 보여줌.

 

1. Alice → Eve: R1=g^x mod  p

• Alice는 원래 Bob에게 g^x를 보내야 하지만, 네트워크 상에 끼어든 Eve가 가로채서 R1을 자신이 받아 버립니다.

2. Eve → Bob: R2=g^z mod p

• Eve는 자신만의 비밀값 z를 골라 R2  =  g^z mod p를 Bob에게 보냅니다.
• Bob은 이것이 “Alice가 보낸 R1”인 줄 알고 받아들임.

3. Bob → Eve: R3 = g^y mod p

• Bob은 올바로 받은 R2에 자신의 개인키 y를 써서 k2 = g^yz mod  p를 공유키로 삼으려 하지만,
• 이 역시 Eve에게만 전달됩니다.

4. Eve → Alice: R4 = g^z mod p

• Eve는 Bob이 보낸 R3 대신 자신의 R4=g^z (같은 값) 을 Alice에게 다시 보냅니다.

 

결과: Eve가 양쪽과 개별적인 키를 형성

• Alice–Eve 사이의 공유키:
  Eve는 Alice에게 보낸 R4=g^z와, Alice가 원래 보낸 R1=g^x를 이용해 kAE=(R4)^x=g^zx mod  p를 계산합니다.
• Eve–Bob 사이의 공유키:
  Bob이 받은 R2=g^z와 Bob이 보낸 R3=g^y를 이용해 kEB=(R2)^y=g^zy mod  p를 계산합니다.

이제 Eve는

1. Alice가 보낼 메시지를 kAE로 복호화(eavesdrop)
2. 내용을 읽거나 위조한 뒤
3. 다시 kEB로 암호화(encrypt)하여 Bob에게 전달

Alice와 Bob은 서로가 직접 공유한 키라고 믿지만,

실제로는 Eve와 각각 다른 키를 공유하고 있기 때문에, Eve는 양쪽 통신을 완전히 통제하게 됩니다.

 

• 방어 대책: 인증(Authentication)
  • Diffie–Hellman 자체는 키 교환만 담당하므로,
  • “상대가 진짜 Alice(또는 Bob)가 맞는지”를 검증해 주는 인증 계층이 필수적입니다.
  • 예를 들어 디지털 서명, 공개키 기반 구조(PKI), 미리 공유된 인증서 등을 이용해
    R1,R2가 진짜 상대방이 보낸 것임을 확인해야 중간자 공격을 막을 수 있습니다.

Diffie–Hellman 키 교환

- 공개 매개변수: 큰 소수 p, 원시근 g.
- 개인키:Alice: a, Bob: b

- 공개키 교환:
Alice → Bob: A=g^a mod p
Bob → Alice: B=g^b mod p
공통 비밀키 계산: K = A^b mod p = B^a mod p = g^ab mod p.

- 취약점:
중간자 공격(Man-in-the-Middle)인증(Authentication)이 없으면 공격자가 둘 사이에 끼어 키를 탈취·변조할 수 있음.

---

Prime and Primality test

“큰 소수를 어떻게 효율적으로 찾는가”

 

1. 왜 큰 소수가 필요한가?

• RSA 같은 공개키 암호의 보안 강도는 n=pq에서 p,q가 충분히 큰 소수일 때 유지됩니다.
• 따라서 우리는 임의의 큰 수를 뽑아서 소수 여부(primality)를 확인하는 과정을 반복해야 합니다.

2. 소수 분포와 확률

• π(x)는 “x 이하의 소수 개수”를 뜻하는 함수입니다.
  예를 들어 π(15)=6인데, 그 이유는 {2,3,5,7,11,13} 여섯 개가 15 이하의 소수이기 때문입니다.
• 소수 분포 정리(Prime Number Theorem) 덕분에 lim⁡(x→∞) π(x)/[x/ln⁡x]=1⟹π(x)≈x/ln⁡x로 근사할 수 있습니다.

3. 임의의 수가 소수일 확률

• 1에서 x 사이의 임의 정수가 소수일 확률은 π(x)/x  ≈  1/ln⁡x.
• 예를 들어, x=10^16이라면, ln⁡10^16 = 16 ln⁡10 ≈ 16×2.30 ≈ 36.8이므로, 1/ln⁡(1016) ≈ 1/36.8 ≈ 0.027(≈2.7%).

4. 반복 시도 횟수와 실패 확률

• 한번에 임의의 큰 수를 뽑아도 “소수가 나올 확률”이 1/ln⁡x 정도이므로,
• 예컨대 200번 반복해서 소수가 하나도 안 나올 확률은(1−0.027)^200  ≈  0.004 (≈0.4%)로 매우 낮습니다.
• 따라서 통상 수백 번 정도 무작위 시도 후 “확률적 소수 판정(Miller–Rabin 등)”을 거치면, 충분히 큰 소수를 현실적인 시간 안에 찾을 수 있습니다.

5. 결론

1. 소수 분포 정리를 통해 “큰 수 x에서 소수 밀도는 1/ln⁡x 정도”임을 알 수 있다.
2. 따라서 “임의의 x-비트 수를 뽑아서 소수 판정을 몇 번 반복하면 소수를 쉽게 얻는다”는 전략이 실용적이다.
3. 이 과정을 통해 안전한 RSA 모듈러 n=pq를 구성할 수 있다.

---

 

1. 큰 소수 생성 절차

1. 임의의 n-비트 수 N 선택: 2ⁿ의 범위 안에서 무작위로 하나 고른다.
2. 소수 판정 실행: N이 소수인지 확인한다.
3. 반복 또는 완료
   - 소수라면 N을 출력해 끝내고,
   - 합성수면(소수가 아니면) 1번으로 돌아가 다른 N을 골라 다시 판정.

 

 

 

2. 소수 판정(Primality Test) 알고리즘

 

2-1. Naïve trial division

• 2부터 ⌊N⌋까지 모든 수로 나눠보는 방법
• 시간 복잡도는 대략 O(sqrt(N)) → 입력 크기(비트수) n으로 보면 O(2^n/2)로 지수 시간이므로 실무 불가

2-2. AKS 알고리즘 (2002, R. Agrawal 외)

• 수학적으로 완전 결정론적이고, 다항식 시간에 소수 여부를 판정
• 최초의 순수 다항식 시간 알고리즘으로, 복잡도는 대략 Θ(n^6) (여기서 n은 입력 비트 길이)
• 이론적으로 의미가 크지만, 실제 구현 성능은 Miller–Rabin보다 느림

2-3. Miller–Rabin 알고리즘

• 현재 가장 널리 쓰이는 표준 소수 판정 기법
• 확률적(primality probabilistic) 테스트:
  • 몇 번의 랜덤 기저(base) 테스트를 수행해,
  • “합성수일 확률을 아주 낮게” 만들고,
  • 테스트를 다 통과하면 “거의 확실히 소수”로 간주

---

Miller-Rabin algo.

 

 

1. Fermat's test

Primalith test using Fermat's little theorem

• 만약 p가 소수라면, 임의의 a∈Zp∗에 대해 a^(p−1)  ≡  1 (mod p). 
• 따라서 “a^(p−1) ≡ 1 (mod p)”인 a가 하나라도 나오면 무조건 합성수입니다.

2. 필요충분조건이 아닌 이유: 위음수(Pseudoprime)

• 역(⇐)은 항상 참이 아닙니다.
  즉 “a^(p−1) ≡ 1 (mod p)인 a가 전부였다 → p는 소수다”는 거짓이 될 수 있습니다.
• 예: p=221일 때, 221=13×17인데, 임의의 a (예: a=38)를 골라 보면, 38^220  =1 (mod 221)이 성립합니다.
• 모든 a에 대해 a^(p−1) ≡ 1 (mod p)을 만족해도 합성수인 경우입니다.

3. 그래도 유용한 이유: 확률적 판정

• 합성수이더라도 “a^(p−1) ≡ 1 (mod p)”인 기저(base) a의 개수는 제한적이므로,
• 여러 번 무작위 a를 골라 테스트하면 대다수 합성수는 금세 걸러집니다.
• 즉, “테스트를 여러 차례 통과한 수”는 거의 확실히 소수라 할 수 있는 확률적(primality probabilistic) 방법입니다.

4. 의사코드

boolean primality1(int n)
{
    int a;
    Pick a positive integer a < n at random;
    if (a^(n-1) ≡ 1 (mod n))
        return true;    // Pass
    else
        return false;   // Fail
}

1. 무작위 기저 a 선택
2. 페르마 조건 a^(n−1) mod  n=1검사
3. 하나라도 실패하면 즉시 합성수로 판정
4. k번 모두 통과하면 “소수일 확률 높음”으로 판정

---

Prime and Primality test

 

Carmichael 수(Carmichael number)

모든 a에 대해서 primality 검사를 통과하는 아주 예외적인 합성수

• 페르마 소정리에 따르면, 소수 p에 대해 임의의 gcd⁡(a,p)=1인 a는 a^(p−1) ≡ 1 (mod p)을 만족합니다.
• Carmichael 수는 “합성수이면서도” 이 조건을 모든gcd⁡(a,n)=1인 a에 대해 충족시키는 예외적인 수입니다.
  즉, a^(n−1)≡1 (mod n) for all a with gcd⁡(a,n)=1이지만 n은 소수가 아닌 수입니다.

이 때문에 단순한 Fermat 테스트만으로는 Carmichael 수를 걸러낼 수 없어, 페르마 테스트의 “충분조건”이 되지 못합니다.

 

얼마나 드물게 나타날까?

다음 표는 “10^n 이하의 Carmichael 수 개수” C(10^n)를 보여줍니다:

n	9	10	11	12	13	14	15
C(10^n)	646	1 547	3 605	8 241	19 279	44 706	105 212

n	16	17	18	19	20	21
C(10n)C(10^n)	246 683	585 355	1 401 644	3 381 806	8 220 777	20 138 200

• 보시다시피 10^21 이하에 약 2천만 개 정도 있지만, 이는 10^21 자체에 비하면 극히 작은 밀도입니다.
• 그래서 “무작위로 큰 수를 뽑아 Fermat 테스트를 돌려도 Carmichael 수에 걸릴 확률은 매우 낮습니다.”

 

 

1. 소수인 경우와 합성수인 경우의 통과율 차이

If we just ignore Carmichael numbers,

1. n이 소수라면
   • 페르마 소정리에 의해, 모든 1≤a<n에 대하여 a^(n−1) ≡ 1 (mod n) 
   • 따라서 “테스트를 하면 항상 true(통과)” → 오류 없음(정확도 100%).
2. n이 합성수(Carmichael 수 제외)라면
   • 최대 절반 이하의 a만이 a^(n−1)≡1을 만족
   • 나머지 절반 이상에서는 “Fail(합성으로 올바르게 판정)”
   • 즉, “false positive(합성수를 소수로 잘못 판단)” 확률 ≤ 50%.

 

2. 확률적 테스트로서의 의미

That is, again it is Probabilistic primality test

• True Positive (실제로 소수인 n에 대해 true 반환)
  • Pr⁡[if n is prime → return true] = 1
• False Positive (합성수인 n에 대해 true 반환)
  • Pr⁡[if n is composite → return true] ≤ 1/2. 

즉, 단 한 번의 테스트로는 “합성수를 소수라 오판할” 위험이 최대 50%라는 확률적 한계가 있지만, 소수는 절대 빠지지 않습니다.

 

3. 에러 확률을 기하급수적으로 낮추기

To reduce such error rate, we can pick multiple a's and do primality test multiple times

• 여러 개의 서로 다른 기저 a1,a2,…,ak를 골라서 독립적으로 Fermat 테스트를 반복하면, Pr⁡[all k tests pass∣n composite]  ≤  (1/2)^k.
• 예를 들어, k=50이면(1/2)^50=2^(−50)<10^(−17), 사실상 0에 가까운 확률이 되어, 합성수를 소수로 오판할 가능성을 거의 완전히 제거할 수 있습니다.

---

이 결과는 10,000 이하 숫자에 대해 페르마 테스트를 여러 번 반복했을 때 “합성수임에도 소수로 잘못 통과하는(거짓 양성)” 숫자가 얼마나 줄어드는지를 보여줍니다:

• k=1 (기저 하나만 시험): 8개의 합성수가 소수로 잘못 통과
• k=3 (기저 세 개 시험): 약 5개만 통과
• k=5 (기저 다섯 개 시험): 약 2개만 통과
• k=10 (기저 열 개 시험): 통과하는 합성수 0개 → 완벽하게 걸러냄

즉, 반복 횟수 k를 늘릴수록 “합성수 오판”이 기하급수적으로 줄어들어,

충분한 k만큼 테스트하면 사실상 오류 없이 소수 판정이 가능합니다.

---

ElGamal Cryptographic system

• Discrete Logarithm Problem
• Also used in digital signature
• 같은 평문을 암호화하더라도 매번 서로 다른 암호문이 생성되어 확률적 특성을 갖습니다. 이는 발신자가 암호문을 생성할 때마다 매번 임의의 난수를 선택하기 때문입니다.

 

1. 키 쌍 생성 (Key Pair Generation)

1. 큰 소수 p와 그 원시근(primitive root) g를 선택
2. 개인키 x를 {1,2,…,p−2에서 무작위로 골라 비밀로 보관
3. 공개키 y  =  g^x mod p를 계산하고, (p,  g,  y)를 모두에게 공개

2. 암호화 (Encryption)

• 평문: m (단, 0<m<p)
• 매 암호화마다 임의의 난수 k∈{1,2,…,p−2}를 새로 골라 사용

1. C1=g^k mod p 
2. C2=m×y^k mod  p  =  m×(g^x)^k  mod  p  =  m  ×  g^xk  mod  p
3. 최종 암호문은 (C1,  C2) 쌍

확률적 암호화: 매번 다른 k를 골라 C1,C2를 생성하므로, 같은 m이라도 매번 다른 암호문이 나옵니다.

 

3. 복호화 (Decryption)

1. C1x  =  (g^k)^x=g^kx  mod  p 
2. 이 값의 역원을 곱하면, (C1x)^(−1)  =  g^(-kx) mod p
3. 복호화 식 m=C2  ×  (C1^x)^(−1) mod  p = (m g^kx) × g^(−kx) mod   p=m (mod p)

---

Example

 

1. 키 생성 (Key Generation)

1. 공개 매개변수 p=13,g=2
2. 개인키 x=3
3. 공개키 y=g^x mod  p=2^3 mod  13 = 8. 따라서 공개키는 (p,g,y)=(13,2,8).

 

 

 

2. 암호화 (Encryption)

• 평문 m = 11
• 임의 난수 k = 5

1. C1 = g^k mod  p = 2^5 mod  13 = 32  mod 13=6.
2. C2 = m×y^k mod  p = 11×8^5 mod  13 = 10

• 따라서 암호문은(C1, C2)=(6, 10).

3. 복호화 (Decryption)

수신자는 개인키 x=3을 사용하여: m = 10 x (6^3)^(-1) mod 13 = 11 

---