공개키 암호화-2

Discrete Logarithm Problem (DLP)

• 개념

  $a,x\space$가 주어졌을 때$\space a^x=b$는 계산하기 쉽지만
  $a,b\space$가 주어졌을 때$\space x=log_ab\space$인 $x$를 찾아내는 것이 어렵다는 것, 실수 범위에서는 대소 관계를 통해서 $x$를 쉽게 찾을 수도있지만, '군'에서는 $x$를 쉽게 찾을 수 없음

  $x,g ,p$ 가 주어졌을 때 $y=g^x\space mod \space p$ 를 만족하는 $y$는 쉽게 찾을 수 있음
  $g,y ,p$ 가 주어졌을 때 $y=g^x\space mod \space p$ 를 만족하는 $x$는 쉽게 찾을 수 없음
  (one-way function)

ElGamal Encryption

위에서 언급한 DLP를 사용한 공개키 암호화 기법

• Key
  • public: $p,g,y,k$
    • $p:$ prime
    • $g: g<p\space$ (generator of $Z_p,GCD(g,p)=1$)
      • 여기서 $g$는 $mod\space p$의 원시근을 의미

        $Z_{p}\space$의 원시근 $r$은 $0<a\le p-1$ 인 모든 $a$에 대하여 $Z_p$내에 $r^e \space mod \space p =a$ 를 만족하는 $e$를 가지고있다.
        $p=5$, $r=3$ 이라면 $Z_5$ 안에서 즉 $mod\space 5$상에서 3의 거듭제곱을 나열해보면
        $3^1=3$
        $3^2=4$
        $3^3=2$
        $3^4=1$
        모든 $a$에 대응되는 모든값이 3의 거듭제곱 형태이므로 3은 $mod$ 5의 원시근이다

    • $y: y=g^x\space mod \space p$
    • $k:$ 임의의 정수 k 주로 $p-1$을 사용
      • $k$ 값을 다르게 주면 같은 문자도 다르게 암호화 됨
  • private: $x (x<p)$
    
    
• 암호화 $C=(a,b)$

  $a=g^k\space mod \space p$
  $b=y^k*M\space mod \space p\space (M<p)$

• 복호화

  $M=\frac{b}{a^x}\space mod\space p$
  $a^x =g^{kx}\space mod \space p$
  $\frac{b}{a^x}=\frac{y^k*M}{g^{kx}}=\frac{g^{kx}*M}{g^{kx}}=M$

Rabin Encryption

모듈로 상에서 제곱근 값을 찾는 것의 어려움에 기반

$C=M^2\space mod\space n$

Simple Key Exchange

• Simple example 1

  A가 B와 키를 공유하기를 원한다고 가정, 신뢰할 수 있는 제 3자를 통해서 키를 교환
  1) A->Lockmaster: $E_{keyA}(ID_A||ID_B)$
  2) Lockmasket->A: $E_{keyA}(newkey||E_{keyB}(newkey))$
  3) A->B: $E_{keyB}(newkey)$

• simple example 2

  A가 B와 키를 공유하기를 원한다고 가정, 로컬에서 세션키를 암호화해서 전달
  1) A->B: $E_{keyBpub}(E_{keyApri}(newkey))$

Diffie-Hellman Key Exchange

이산 대수계산의 어려움에서 고안한 방법
세션키를 암호화하여 전달할 필요 없음

• Process

  A가 B와 키를 공유하기를 원한다면
  소수 $p$, 원시근 $\alpha$를 공개하고 각자의 비밀값 $X_a<P$ $X_b<P$ 선택 후
  A: $Y_a=\alpha^{X_a}\space mod\space p$ 를 계산해서 B에게 $Y_a$ 전송
  B: $Y_a=\alpha^{X_b}\space mod\space p$ 를 계산해서 A에게 $Y_b$ 전송
  A: $K=Y_b^{X_a}\space mod\space p$ 계산
  B: $K=Y_a^{X_b}\space mod\space p$ 계산
  위의 두 식의 계산 결과는 같음, 따라서 같은 키를 공유하게 됨