RSA暗号とcpawQ29のwriteup

#1.目的等
RSA暗号の原理というか初歩を大まかに学習したので、忘れないようにアウトプットしつつ頭の中の整理を行う。
また、cpawCTFの[challengesQ.29](http://ctf.cpaw.site/questions.php?qnum=29)のwriteupのため。
CTF初心者なので誤っている部分があると思います。大目に見てください。また指摘していただけるとありがたいです。
#2.公開鍵と秘密鍵
RSAを解説していく前に軽く公開鍵暗号を説明したい。
受信者は暗号化および復号化にそれぞれ別の鍵を用い、それらを公開鍵と秘密鍵とに分け、扱いを異にしている。
注意として、送信者が固有に保有する鍵は関係ない。
##2.1公開鍵
その名の通り世界に向けて公開する鍵のことである。
送信者に配布し、通信の内容についてこの鍵で暗号化し受信者に渡す。
##2.2秘密鍵
その名（略
先の項で述べた通り、公開鍵で暗号化されたものを復号するのに用いる。
公開鍵に対応する秘密鍵は一つしかないので通信経路中に盗聴される危険性は低い。
が、秘密鍵が流出してしまえば第三者でも通信の内容を明らかにできてしまう。
以上の暗号化から復号化までのプロセスを公開鍵暗号方式と呼び、この方式の一つにRSA暗号がある。
#3.RSA暗号について
桁数の多い数の素因数分解にかかる時間が膨大であることを秘匿性の根拠としている。
この暗号では鍵として３つの数字$n$と$e$と$d$を用意する。これらの数字にも一定のルールがある。

$n =pq$
$(p-1)(q-1)と互いに素となる任意の素数e$
$ed \equiv 1 \quad {mod(p-1)(q-1)}を満たすd$
$ただし、pおよびqは素数$

公開鍵として$n$と$e$を、秘密鍵として$d$を保持する。
（先駆者のページを参考にすると$e$を公開指数、$d$を秘密指数と呼んでいる）
![鍵のやりとり](https://i.imgur.com/2mHc5NK.png)
##3.1暗号化

さて、暗号化に必要な要素が揃ったので平文$m$を暗号化する。

```math
\quad c = m^e \quad (mod \quad n)\\
ただし、m \in Zかつ0 \leq m \leq nとする。
```

以上の式から算出される$c$が平文$m$に対する暗号文となる。
平文に公開指数$e$を乗じた値に$n$で剰余を取った値が暗号$c$だ。
この処理を、公開鍵を受け取った送信者側で行い通信経路に乗せる。
##3.2復号
送信者から送られてきた暗号$c$を平文に戻す処理については、以下の通りである。

```math
\quad m = c^d \quad (mod \quad n)\\
ただし、c \in Zかつ0 \leq c \leq nとする。
```

$d$が必要となるので、正しい受信者でなければ復号できないといった仕組みになっている。
#4.復号したものが平文と同一かの証明
基本的な数学的知識に加え、オイラーの定理を知っていれば簡単に証明ができる。
本番の証明をする前にオイラーの定理について軽く触れておきます。
#4.1オイラーの定理


$-Euler's theorem-$
$kを正の整数、xを任意の整数とする。$
$xとkが互いに素ならば、x^{\phi(k)}\equiv 1\quad (mod\quad k)$
$ただし、\phi(k)はkと互いに素な1以上k未満の整数の個数$
<br>
ある整数$x$について、$n$まで互いに素となる整数を数え累乗を取ると、その値が$n$で除すると1になる。ということである。
途中にある$\phi(n)$はオイラーの$\phi$関数と呼ばれる。
例として$\phi(5)$を考える。5未満で5と互いに素となる整数は、{1,2,3,4}の4つであるから$\phi(5)= 4$である。
同様に、$\phi(6)=2$、$\phi(7)= 6$と定まる。
このオイラーの定理の証明はさすがに省きます。気になる人は調べてください。
この前提知識があると楽に理解できると思います。
##4.2証明開始


$平文mをm \in Z、0 \leq m \leq nとし、暗号文cをc\in Z、0 \leq c \leq nとする。$
$そして暗号化関数Enc(m)および復号化関数Dec(c)を以下の通り定義する。$
<br>

```math
\begin{align}
Enc(m) &:= m^e \quad (mod \quad n)\\
Dec(c) &:= c^d \quad (mod \quad n)\\
\end{align}
```
<br>
$ここでは、Dec(Enc(m)) \equiv m\quad (mod\quad n)を証明する。$
$以下は、$n$を法とした合同式で考える。$
<br>

```math
\begin{align}
Dec(Enc(m)) &\equiv (m^e)^d\\
&\equiv m^{ed}\\
&\equiv m^{1+k(p-1)(q-1)}\\
&\equiv m^1 \cdot m^{k(p-1)(q-1)}\\
&\equiv m \cdot m^{(p-1)(q-1)k}\\
&\end{align}\\
```
$と式変形していく。ここで、m^{(p-1)(q-1)}にフェルマーの定理を適用したい。$
$そのため、(p-1)(q-1) = \phi(n)であることを導く。$
$nと互いに素な整数の個数は、互いに素とならない個数を全体個数から引いて求められる。$
$n(=pq)と互いに素とならない数は、{p,2p,\cdots,(q-1)p}および{q,2q,\cdots,(p-1)q}である。$
$nの素因数はpとqだけのため、互いに素とならない整数は(p-1)+(q-1)[個]となる。$
$よって互いに素となる個数は次のように求められる。$

```math
\begin{align}
\phi(n) &= n -\{(p-1)+(q-1)\}-1\\
&=n-(p+q)+1\\
&=pq-p-q+1\\
&=p(q-1)-(q-1)\\
&=(p-1)(q-1)\\
\end{align}
\\
```
$よって、\phi(n)=(p-1)(q-1)であるので、オイラーの定理を適用し$

```math
m^{(p-1)(q-1)}\equiv 1 
```
$となる。$
$これを元の式にあてはめ、式変形を続けていく。$

```math
\begin{align}
Dec(Enc(m)) &\equiv m \cdot m^{(p-1)(q-1)k}\\
&\equiv m\cdot 1^k\\
&\equiv m\\ 
\end{align}
```

$以上から、0 \leq m \leq nの条件下では、Dec(Enc(m)) = mが証明できた。$

#5.Writeup
##5.1Common modules attackとは
cpaw.Q29を解き始める前に一般化して考えていく。
Common modules attackは、同一の平文に対して、$n$の値が同一となる複数の鍵で暗号化した場合に生じる脆弱性であり、
平文$m$を二つの鍵$(n,e_1)$と$(n,e_2)$で暗号化した場合、$gcd(e_1,e_2)=1$である時に簡単に平文を求めることができてしまう。
最大公約数を求めるユークリッド互除法を拡張し、
$ax+by=gcd(a,b)$
という二元一次方程式の解を求められることを利用します。
同一の平文を暗号化した$c_1$および$c_2$を用意する。

```math
\begin{align}
c_1 &\equiv m^{e_1}\quad (mod\quad n )\\
c_2 &\equiv m^{e_2}\quad (mod\quad n )\\
\end{align}\\
```
そして、この2式の辺々を掛ける。（以下は$n$を法として合同）

```math
\begin{align}
c_1 c_2&\equiv m^{e_1}m^{e_2}\\
\end{align}\\
```
ここで拡張ユークリッド互除法にて、以下を満たす$x$および$y$を求めておく。


```math
{e_1}x+{e_2}y=gcd(a,b)=1
```
合同式では同じ値をべき乗しても関係は変わらないため、整数$x$および$y$を両辺でべき乗する。

```math
\begin{align}
{c_1}^{x} c_2^{y}&\equiv {(m^{e_1})}^{x}{(m^{e_2})}^{y}\\
&\equiv m^{{e_1}x+{e_1}y}\\
&\equiv m
\end{align}\\
```
$m$の指数${e_1}x+{e_2}y$は1であるため、結果平文が求まる。

#5.2解答
さて、[問題](http://ctf.cpaw.site/questions.php?qnum=29)では２つの鍵と暗号文が手に入ります。
1つ目の鍵(e,N)=(11,236934049743116267137...)
2つ目の鍵(e,N)=(13,236934049743116267137...)
Nの値が同じになっています。そのためCommon modules attackを試します。


```python
import gmpy

c1 = 
c2 = 

e1 = 
e2 = 
n = 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b%a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m

def commom_world(c1, c2, e1, e2, n):
    gcd, s1, s2 = egcd(e1, e2)
    print gcd
    print s1
    print s2
    if s1 < 0:
        s1 = -s1
        c1 = modinv(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = modinv(c2, n)

    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v*w) % n
    return x

print commom_world(c1, c2, e1, e2, n)
```
コードは[ここから](https://gist.github.com/horoama/688c94fe629a321284c2b4706c75be98#file-common_modulus_attack-py-L9)拝借しました。
エントリポイントであるcommom_world関数を見ていく。
まず、関数egcdに公開指数$e_1$$e_2$を渡して最大公約数と${e_1}x+{e_2}y=gcd(a,b)$を満たす$x$と$y$を求めます。
次の条件分岐では、先ほど求めた$x$と$y$はどちらか一方が必ず負の数になっているため、それぞれのケースで負の数を正の数に反転させまた、暗号文が法$n$の剰余となっているか再計算して確認しています。
最後にこの関数の終盤

```python
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v*w) % n
    return x
```
において

```math
\begin{align}
{c_1}^{x} c_2^{y}&\equiv {(m^{e_1})}^{x}{(m^{e_2})}^{y}\\
&\equiv m^{{e_1}x+{e_1}y}\\
&\equiv m
\end{align}\\
```
に相当する計算を行い、算出された平文を出力しています。
よってコード中のc1,c2,e1,e2,nに任意の値を入力すると解読することができます。
あくまで条件に当てはまる場合です。。。
以上です。
##6.参考文献等
₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです「公開鍵暗号 - RSA - 基礎」
http://elliptic-shiho.hatenablog.com/entry/2015/11/12/182219
₍₍ (ง ˘ω˘ )ว ⁾⁾ < 暗号楽しいです「公開鍵暗号 RSA - Common Modulus Attack, 秘密鍵からの素因数分解」
http://elliptic-shiho.hatenablog.com/entry/2015/12/14/043745
akashisnの日記「Common Modulus Attack」
https://blog.akashisn.info/entry/2018/08/07/132209
アルゴリズムロジック「拡張ユークリッドの互除法」
https://algo-logic.info/extend-gcd/
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜
https://qiita.com/drken/items/b97ff231e43bce50199a