비대칭키 암호 시스템

• 개요
  • 1976년 Merkle과 Diffie, Hellman 이 처음으로 소개하였으며, 암호화 키와 복호화 키가 다른 암호 시스템
  • 암호화 키는 외부에 공개하고(공개키) 복호화 키만 소유자가 관리(비밀키)
  • 공개키 암호 시스템이라고도 함
  • A가 B에게 메시지를 전송하는 경우, A는 공개된 B의 공개키를 이용해 메시지를 암호화하며, B는 자신의 비밀키를 이용해 암호화된 메시지를 복호화 함
    
       
  •    
• 비대칭키 암호 시스템의 특징
  • 비대칭키 암호 알고리즘의 성질
    • 암호문을 복호화하면 원래의 평문을 얻어야 함 : P = Decrypt(Encrypt(P))
    • 암호화하는 함수 Encrypt는 누구나 계산할 수 있음
    • 비밀키를 모르면 Decrypt는 현실적으로 계산하기 어려움
    • 비밀키를 알고 있으면 Decrypt를 쉽게 계산 할 수 있음
    • 공개키로부터 비밀키를 구하는 것은 현실적으로 불가능
  • 공개키 암호 알고리즘 : 수학적으로 어려운 문제들에 바탕을 두고 있음
    • 소인수 분해: RSA(가장 널리 사용), Rabin encryption
    • 유한체의 이산대수 : EIGamal, Diffie-Hellman, XTR
    • 타원곡선의 이산대수 : Elliptic Curve Cryptosystem(ECC)
    • 부호 이론(Coding Theory) : McEliece
    • 배낭 문제 : Knapsack 암호
    • 기타 : NTRU(격자 이론), Braid-group, Cryptosystem(매듭이론)
         
• 비대칭키 암호 시스템의 장.단점

장점	단점
키의 분배가 용이 사용자의 증가에 따라 관리되는 키의 수가 상대적으로 적음 ⇒ 2N 키 변화의 빈도가 적음 다양한 보안 서비스(인증, 전자 서명, 키 분배 등)에 적합	구현이 어려움 암.복호화 속도가 느림 암.복호화 키의 크기가 상대적으로 김

   

• 비대칭키 암호 시스템의 종류
  • RSA 암호 알고리즘
    • 1978년 Rivest-Shamir-Adleman에 의해 제안
    • 키 생성 알고리즘
      • 큰 자리( > 10100)소수 p, q생성, n = p * q
      • n 보다는 작고, (p-1)(q-1)와 공통인수를 1 이외에는 갖지 않는 새로운 수 e
      • e * d mod (p-1)(q-1) = 1을 만족하는 d
      • 공개키 (e, n), 개인키(d, n)
    • 암.복호화 알고리즘 : 평문 M
      • 암호화 : C = Me mod n
      • 복호화 : D = C^d mode n = (M^e mod n)^d mod n = M
    • 공개키(e, n)로부터 개인키(d, n)을 구하기 어려움
      • p와 q를 알 수 있으면 계산이 가능하지만, n으로부터 p와 q를 구하는 인수분해 문제의 어려움
  • Diffie-Hellman 키 분배
    • 1976년 Diffie와 Hellman에 의해 제안
    • 대칭키 암.복호화를 수행하기 위해 비밀키를 서로 공유하기 위한 알고리즘
    • 키 생성 알고리즘
      • 공개된 값 n(큰 자리 소수 > 10200), g(n보다 작고 1보다는 큼)
      • 송.수신자는 각각 비교적 큰 난수 x, y 생성
      • 송.수신자는 각각 X(=gx mod n), Y(=gy mod n)를 계산하여 상대방에게 보냄
      • 송.수신자는 다음을 계산하여 비밀키를 얻음
        • 송신자 : K = (Y) * x mod n = gyx mod n
        • 수신자 : K = (X) * y mod n = gxy mod n
    • 공격자가 알 수 있는 n, g, X, Y를 가지고 K를 구할 수 있는가?
      • n이 충분히 클 경우, K(즉 x, y)를 구하는 이산대수 문제의 어려움
  • EIGamal 암호 알고리즘
    • Diffie-Hellman 키 분배 방식을 변형시켜 공개키 암호 방식을 제안
    • RSA는 동일 메시지에 대해 같은 암호문을 생성하지만, EIGamal은 동일 메시지에 대해 다른 암호문을 생성
    • 키 생성 알고리즘
      • 사전에 공개된 값 : G, P
      • 임의의 개인키 선정 : X
      • 공개키 계산 : Y = G^X mod P
    • 암.복호화 알고리즘 : 평문 M, k는 임의의 난수
      • 암호화 : R = Gk mod P, C = MYk mod P, 암호문 = (R, C)
      • 복호화 : M = CR^-X mode P
    • 공격자가 알 수 있는 G, P, Y를 가지고 X를 구할 수 있는가?
      • G, P, Y가 충분히 클 경우, X를 구하는 이산대수 문제의 어려움