공개키 암호화 - 1

공개키 암호화의 필요성과 등장

• 관용 암호의 문제점
  • 키 분배 (키를 안전하게 보낼 방법이 있으면, 평문을 그 방식으로 보내면 된다)
  • 디지털 서명 불가능
    
    
• 공개키 암호화
  • Diffie Hellman에 의해 제안
  • 암호화, 복호화에 쓰이는 키가 다름 (공개키, 비밀키)

• 관용암호 vs 공개 키 암호

  관용	공개키
  암/복호에 동일한 키 사용	암/복호에 다른 키 사용
  키를 교환	키쌍중 하나를 알아야함
  교환한 키는 비밀로 유지	키쌍중 하나를 비밀로 유지
  디지털 서명 불가	디지털 서명가능
  빠름	느림

• 공개키 암호화 모델(simple)

  • 키쌍 생성(공개키, 비밀키)
  • 공개키는 공개, 비밀키는 개인 소유
  • 공개키로 암호화
  • 비밀키로 복호화 ( 비밀키를 모르면 복호를 할 수 없음)

• 공개키 알고리즘의 조건

  • key 생성이 쉽다.
  • 공개키를 사용한 암호문 생성이 간단하다.
  • 개인키를 사용한 복호화가 간단하다
  • 공개키로 비밀키를 유추하기 어렵다
  • 공개키로 복호화가 어렵다

공개키 암호화 예시 1, Knapsack Problem

• Knapsack Problem

  • 배낭의 부피에 맞춰 물건들을 넣는 문제
  • NP-complete problem ( size가 충분히 크면 해결하는데 걸리는 시간이 지수함수로 증가)

    $S=${$4,7,1,12,10$} (item, 물건)
    $T=17$ (target sum, 가방의 부피)
    17 = 10+7=4+1+12
    $P=[1,0,1,1,0]or[0,1,0,0,1]$

  • Superincreasing Knapsack(해법이 존재하는 Knapsack Problem)
    • $s_k > \displaystyle\sum_{i=1}^{k-1}{s_i}$ (Superincreasing)
    • $S$의 원소 $s$중 가장 큰것부터 $s<T$ 이면 1 아니면 0 후 $T=T-s$

      $S$ = $[1,2,5,9,20,43]$
      $T=49$
      $49 = 43 + 5 + 1$
      $P=[1,0,1,0,0,1]$
      $S*P = T$

• Knapsack Problem을 이용한 공개키 암호화

  • key

    $S=[s_1,s_2, ...,s_n]$ : superincresing Knapsack
    $n> s_1+s_2+...+s_n$
    $w$ 선택 ($1<w<n,$ $n$과$w$는 서로소)
    $H=[h_1,h_2,...,h_n]$, $h_i=w*s_i \space mod\space n$
    공개키: $H$ or $(H,n)$
    비밀키: $(n,w)$ or $(w)$

  • 암호화

    $c_j = \displaystyle\sum_{i=1}^{m}{h_i*p_{ji}}$

  • 복호화

    $w^{-1}$ 계산
    $T_j = w^{-1} * c_j\space mod\space n$ 계산
    $T_j = w^{-1} * c_j\space mod\space n = \displaystyle\sum_{i=1}^{m}{[h_i*p_{ji}*w^{-1}]mod\space n}$= $\displaystyle\sum_{i=1}^{m}{s_i*p_{ji}}$

  • 왜 이 기법이 공개키 암호화로 쓰일 수 있었을까

    • w 를 모르는 사람은 $c=h*p$를 통해 general knapsack problem 해결해야하지만
    • w 를 아는 사람은 $s_i*p_{ji}$ 만 계산하면 됨 (one-way function)

  • 현재는 사용되지 않는 기법

    • Superincreasing Knapsack의 특성이 가지는 문제때문에 취약점을 가짐

RSA

• 페르마의 소정리와 오일러 정리

  • 페르마의 소정리

    $a^{p-1} \equiv 1 \space mod \space p\space$($p\space is\space prime,\space gcd(a,p)=1$)

  • 위의 공식에서 알 수 있는 따름정리

    $a^{p} \equiv a \space mod \space p\space$($p\space is\space prime,\space a\space is\space any \space positive\space integer$)

  • 오일러의 정리

    $a^{\phi(n)} \equiv 1 \space mod \space n$

    • $\phi(n)$ : n 보다 작으면서 n과 서로소인 양의 정수의 수
    • $\phi(p)$ : $(p-1)$
    • $\phi(pq)$ : $(p-1)(q-1)$

  
  

• RSA

  • Rivest, Shamir, Adleman 세사람이 MIT에서 만든 공개키 암호화
  • 소인수분해에 기반한 암호화기법
  • 키생성

    공개키: $n,e \space(n=pq,GCD(e,(\phi(n)) =1)$
    비밀키: $d \space (ed \equiv 1\space mod\space \phi(n) ,d= k\phi(n)+1)$

  • 암호화 :

    $c=m^emod\space n$

  • 복호화 :

    $m=c^dmod\space n$

  • 분석
    • $p,q$만 예상하면 d를 쉽게 찾을 수 있지않을까?
      • n이 충분히 큰 양의 정수이면 소인수 분해는 의미있는 시간내에 해결할 수 없음
    • 복호화

      $c^d \equiv m^{ed} \equiv m^{k\phi(n) +1}$
      따라서 $c^d mod\space n = m^{k\phi(n) +1}mod\space n = m\space mod\space n$(오일러 정리)

  • 고려사항
    • 지수승 계산에 많은 시간이 필요함
      • 모듈러 연산의 특징을 이용해 중간 결과를 축소

        $[(a\space mod\space n)\times(b\space mod\space n)]\space mod\space n =(a \times b)\space mod\space n$

    • 효울적인 지수승
      • $x^{16}$의 경우 곱셈을 15번 하는것이 아니라 $x=x^2$을 통해 4번만 계산