RSA

Public Key System

• 암호화하기 위한 key는 모든 사람에게 공개되어 있다.(public)
• 복호화하기 위한 key는 private 하다.
• RSA는 public key system이다.

RSA

• Setting
  • $p$ and $q$ : 서로 다른 두 소수, $n=p\times q$, $e$ : Encryption Key, $d$ : Decryption Key
    • public: $n, e$
    • private: $p, q, d$
  • $ed=1 \mod {(p-1)(q-1)}$
    • $e$는 $\gcd(e, (p-1)(q-1))=1$을 만족해야 함 ($d$가 존재하기 위한 조건), 참고
    • $e, p$가 정해진 상태에서 $d$는 곱셈의 역원을 찾으면 된다.(확장 유클리드 알고리즘)
    • [참고] $\varphi(n)=\varphi(pq)=(p-1)(q-1)$ (오일러 피 함수 특징)
      • $pq-pq*\left(\frac 1p+\frac 1q\right)+1$
      • 따라서 $ed=1 \mod \varphi(n)$ 로 표현할 수 있다.
  • $m$: message
• Encryption
  • $C=m^e \mod n$
• Decryption
  • $m=C^d \mod n$

Proof - 복원하면 원래 메시지가 되는지 보자

• When $\gcd(m, n)=1$
  • $C^d=(m^e)^d=m^{ed}=m^{\varphi(n)\times k + 1}=m^1=m \mod n$
  • 오일러 정리에 의해 $m^{\varphi(n)} \mod n$은 1이다.
• When $\gcd(m, n)=n$
  • $m^{ed}=0=m \mod n$
• else: 반드시 $\gcd(m, n)=p$ 또는 $q$ 이다. (because $n=pq$). $\gcd(m, n)=p$인 경우만 증명하자.
  • $\gcd(m, n)=p$이면 $\gcd(m, p)=p$이고 $\gcd(m, q)=1$ 이다.
  • 페르마 소정리에 의해 $m^{q-1}=1 \mod q$이고 $m^{(p-1)(q-1)}=1 \mod q$ 이다.
  • 따라서 $m^{ed}=m^{k(p-1)(q-1)+ 1}=m \mod q$ 이다.
  • 또한 $\gcd(m, p)=p$이므로 $m^{ed}=m^{k(p-1)(q-1)+ 1}=0=m \mod p$ 이다.
  • [여기까지 결론] $C^d=m \mod p, C^d=m \mod q$
  • 다시쓰면 $C^d-m=kp, C^d-m=lq$로 표현할 수 있다.
  • $C^d-m$은 $p, q$에 대해 각각 배수이고, $p, q$는 서로 다른 소수이므로 서로소 관계이다.
  • 따라서 $C^d-m = x\times pq$로 나타낼 수 있고, $C^d-m=0 \mod pq$로도 나타낼 수 있다.
  • $pq=n$ 이므로 $C^d=m \mod n$ 이다.

RSA is secure?

RSA가 안전한지 알아보자. RSA의 핵심 키는 $ed=1 \mod (p-1)(q-1)$ 이다. 이때 $e, n(=pq)$은 공개 정보이고, $d, p, q$는 비밀 정보이다.
특히 복호화하기 위해서는 $d$를 알아내는 것이 핵심이다. 따라서 $d$를 구할 수 있는지 알아보자.

$ed=1 \mod (p-1)(q-1)$에서 $(p-1)(q-1)$을 알아내거나 각 $p, q$를 알아내면 RSA가 뚫린다.

1. $p, q$를 각각 알아내기
   • RSA 가정상 $n=pq$이고 $n$은 공개정보이다. 따라서 $p, q$를 알아낸다는 것은 $n$을 소인수분해한 것과 같다.
   • 소인수 분해는 NP$\cap$co-NP 문제이다. (P 문제임이 증명되지 않았다.)
2. $(p-1)(q-1)$ 알아내기
   • $(p-1)(q-1)=pq-(q+p)+1$이고 $pq$는 이미 알고있으므로, 사실상 $p+q$를 알아낸다는 것과 같다.
   • $pq, p+q$를 알고있으면 방정식을 이용해 $p, q$를 각각 알아낼 수 있다.
   • (위 1번과 같은 상황) 소인수분해꼴이다.
     

하지만 모든 소인수분해가 어려운건 아니다. 쉬운 케이스는 분명 존재한다.
현실의 practical에 맞게 ‘$(p-q)$를 큰 것을 사용한다’ 등의 추가 조건들이 붙는다.

• NIST에서 권장하는 키 사이즈
  • 2002년: 1024 bits
  • 2015년: 2048 bits

RSA의 2가지 이슈

1. Modular Exponentiation을 어떻게 빠르게 계산하느냐?
   • Calculate $C=m^e\mod n$?
2. 아주 큰 소수 $p, q$를 어떻게 찾느냐?

1. Modular Exponentiation

(분할정복을 이용한 거듭제곱) $O(\log N)$ 시간에 계산이 가능하다.

2. Finding Primes

소수는 무한하다.
만일 소수 개수가 무한하지 않다고 가정하자. 이때 소수를 $(p_1, p_2, …, p_k)$라 하자.
$N=p_1\times p_2 \times \cdots \times p_k +1$이라고 하면 $N$은 가정에 의해 합성수여야 한다.
합성수는 반드시 소인수분해가 가능해야 한다. 하지만 그 어떤 소수 $(p_1, p_2, …, p_k)$로 나눠도 나누어떨어지지 않는다.
따라서 소수는 무한하다.

또한 소수는 생각보다 밀도가 높다고 알려져있다. 1부터 n까지 자연수 중 소수의 개수는 대락 $(n/\log_en)$ 이다.
1,000,000까지의 자연수 중 소수는 대략 60,000개 인데, 이는 14개 중에 1개는 소수라는 의미이다.
따라서 랜덤하게 자연수를 찍다보면 빠른 시간 내에 소수를 찾을 수 있다.
물론 소수인지 아닌지 구별하기 위해서 소수판정이 필요하다.

Primality Test (probabilistic)

Fermat Theorem: If $p$ is a Prime and $a\in Z^*_p$, then $a^{p-1}=1$ mod $p$

$p$가 소수인지 확인하고 싶다면 $a$를 계속 바꿔가며 테스트를 수행하면 아주 높은 확률로 소수를 찾을 수 있다.
소수 테스트를 실패하게 만드는 $a$를 witness(증인)이라고 한다.

만약 합성수라면 witness를 얼마나 가지고 있을까?

Theorem: witness가 1개라도 존재한다면, 절반 이상이 witness이다.

Proof of Theorem

• Let $a$ be a Witness for $p$
  • $a^{n-1}\ne1 \mod p$
• Let’s partition $Z^*_n$ into $A$ and $B$
  • $A$ : Witnesses 집합, $B$ : not Witnesses 집합
  • $b\in B$, $b^{n-1}=1 \mod n$
• We can prove that $|A|\ge |B|$
  • Let’s consider $aB$ ($a \in A$) : $B$의 모든 원소에 $a$를 곱함
    • $|B|=|aB|$
      • 만약 $ab_1=ab_2 \mod m$ 이면 $gcd(a, m)=1$이므로 $b_1=b_2 \mod m$ 이다. 따라서 $ab_1\not = ab_2 \mod m$ 이다.
  • All members of $aB$ are Witnesses
    • $ab_i \in aB, ~~~(ab_i)^{n-1}=a^{n-1}b^{n-1}_i=a^{n-1}\ne 1 \mod n$
  • $aB \subset A$이므로 witness가 1개라도 존재한다면, 절반 이상이 witness이다.

특이하게 witness가 없는 합성수가 존재한다. 이를 Carmichael Number라고 한다. 다행히 이 수들을 테스트하는 방법이 따로 존재한다. (여기서 다루지 않음)

Primality Test Process

• Step1. 랜덤 수 $n$ 뽑기
• Step2. $n$이 Carmichael Number인지 판별
  • if so, go back Step1
• Step3. 랜덤 $a$ 뽑기 $(1\lt a \lt n)$
  • check if $\gcd(a, n)=1$
    • if not $1$, then $n$ is not a prime. go back to Step1
  • check if $a^{n-1}=1 \mod n$
    • if so, go back to Step3 for Repeat Test
      • Witness가 1개라도 있으면 절반 이상이 Witness이므로 약 1000번 정도 돌리면 충분하다.(합성수일 확률이 1/2씩 줄어듦)
    • if not, $n$ is not a Prime, go back to Step1