はじめに

CTFをやる中で，少しは暗号に触れるようになってきたので，頻出のテーマであるRSA暗号について少し勉強してみました．

RSA暗号(safeprime)

RSA暗号とは暗号化に使う鍵と復号に使う鍵が異なる公開鍵暗号方式の一つであり，1977年にRivest(リベスト)，Shamir(シャミア)，Adleman(エーデルマン)によって考案された，桁数がとても多い数字に対する素因数分解が困難であることを利用した暗号方式です．

これらの開発者の頭文字からRSA暗号と命名されました．

最小公倍数
- 任意の整数$a,b$に対して最小の公倍数のこと．$LCM(a,b)$と表す．
最大公約数
- 任意の整数$a,b$に対して最大の公約数のこと．$GCD(a,b)$と表す．
- $GCD(a,b)=1$の場合，整数$a,b$は互いに素である．
モジュロ演算(合同式)
- 整数$a,b$に対して$a-b$が$n$の倍数であるとき，$a=b~mod~n$と表す．
逆元(モジュラ逆数)
- $ax~=1~mod~n$となるような逆数$x$を法$n$における$a$の逆元(モジュラ逆数)という
オイラー関数
- $n$を超えない正の整数のうち$n$と互いに素である数の個数のこと．$\phi(n)$と書く．
- 例えば$\phi(6)~=[1,5]~=2$となる．
- $n$が素数である場合，$\phi(n)~=~n-1$となる．
フェルマーの小定理
- 素数$p$と互いに素な整数$a$において
- $a^{p-1}=1~mod~p$が成り立つ．
オイラーの定理
- 整数$m$と互いに素な整数$a$において
- $a^{\phi(m)}=1~mod~m$

異なる大きな2つの素数$p,q$を生成する．
$n=pq$とする．
$\phi(n) = (p-1)(q-1)$と互いに素な自然数eを生成する．
- $GCD(\phi(n),e)=1$となるような自然数$e$
- ＊$n$は二つの素数$p,q$をかけたものであり，$p,q$は互いに素である．
- ＊その場合$\phi(pq)=\phi(p)~\phi(q)$が成り立つ．
$ed ≡ 1~mod~\phi(n)$となるような$d$を求める．
- $ed$を$\phi(n)$で割ったときの余りが$1$になる．
- この$d$を求めるには拡張ユークリッド互除法を用いて求めることができます．
- ここで$GCD(\phi(n),e)=1$であるため，$\phi(n)x+ey=GCD(\phi(n),e)=1$を解き，$d$を求めます．
最終的に公開鍵は$(e,n)$，秘密鍵は$(d,n)$となります．

送りたいメッセージを$M$，暗号文$C$とすると以下の式で暗号化をすることができる．

$C^d~mod~n ≡ x$
ここで$d$を求めるには$\phi$を求める必要がある，つまり，$(p-1)(q-1)$を知る必要がありますが，$\phi$は非常に大きな合成数であり，素因数分解を行うのが困難であることからRSA暗号の安全性が保障されています．