컴퓨터보안#10

LeeMir, 12 May 2021

공개키 암호화(이어서)

DLP(Discrete Logarithm Problem)
  • \[y=g^xmod(p)\]

  • x를 주고 y를 계산하는 것은 쉽지만, y를 주고 x를 계산하는 것은 어려움

  • El Gamal Excryption

    • Keys
      • Private key
        • x < p
      • Public keys
        • p prime
        • g < p (g와 p는 서로소)
        • y = g^x (mod p)
      • random한 정수 k를 둬 암호화에 사용
    • Encryption
      • 2 ciphertexts (a, b)
      • a = g^k (mod p)
      • b = y^k * M (mod p), (M = plaintext, M < p)
    • Decryption
      • M = b / a^x (mod p)
        • a^x = g^(xk) (mod p)
        • b / a^x = y^k * M / a^x = g^(xk) * M / g^(xk) = M (mod p)

  • Rabin

    • \[C=M^2mod(n)\]
키 교환
  • Simple key exchange
    • Lockmonster라는 제 3의 존재가 가운데에서 key를 생성해 나누어주는 방식
      • 신뢰성 문제
    • 송신자가 session key(plaintext)를 만들고, 수신자의 공개키를 이용해 암호화해서 전송
  • Diffie-Hellman 키 교환
    • 공개키 암호화의 시초
    • 두 사용자가 안전하게 키를 교환하는 방식
    • DLP에 의존
    • session key를 암호화한 전달 불필요, 로컬에서 계산해서 해결
    • process
      • 소수 p 설정(공개)
      • p에 대한 primitive root인 α 설정(공개)
        • α의 n제곱수(n <= p-1)로 이어지는 수열에 대해 mod p를 계산하면 1부터 p-1이 나오는 α
        • 예) 5의 primitive root는 3
      • 송신측 : 비밀값 Xa( < P)를 선택, Ya = α^(Xa) mod P를 계산 후 Ya를 전송
      • 수신측 : 비밀값 Xb( < P)를 선택, Yb = α^(Xb) mod P를 계산 후 Yb를 전송
      • 송신측 : K = Yb^(Xa) mod P를 계산
      • 수신측 : K = Ya^(Xb) mod P를 계산
      • 송수신측의 K는 같으므로 key를 공유하게 됨
유클리드 알고리즘
  • gcd(a, b) = gcd(b, r)
    • r = a mod b
  • 확장 유클리드 알고리즘
    • 두 개의 정수들에 대한 최대 공약수
      • s × a + t × b = gcd(a, b)
    • 곱셈에 대한 역원도 찾을 수 있음
      • 만약, gcd(d, n) = 1이라면(서로소) 그 때 d는 modulo n 상에서 곱셈에 대한 역원을 갖는다
      • 양의 정수 d < n에 대해, dd^(-1) = 1 mod n인 d^(-1) < n이 존재