RSAの暗号化/復号操作とその証明 - ちりもつもればミルキーウェイ

はじめに

これは RSA完全理解 Advent Calendar の3日目の記事です
フェルマーの小定理の証明をやったので、それを使ってRSAの暗号化/復号が成り立つ証明をやります

なお、秘密鍵の生成方法についてはベズーの等式や拡張ユークリッド互除法の知識が必要なので今回は割愛します(こんどそれについても書く予定)

また今回解説するのは素のRSAであり、そのままではいくつかの理由で安全ではありません(これもそのうち別で記事をかきたい)
そのため、現実にRSAを利用する際には安全とされる RSA-OEAP などを利用してください

RSAで必要になる鍵情報

以下の情報がRSAでは必要です

互いに素な素数 $p, q$ と $p\times q = n$ となる $n$
$(p-1)(q-1)$ と互いに素な $e$
$ed\equiv 1\pmod{(p-1)(q-1)}$ となる $d$

$n, e$ を公開鍵、 $d$ を秘密鍵とします

$(p-1)(q-1)$ と互いに素な $e$ を選ぶ理由は、これらが互いに素な場合は $e$ に対しての逆元となる $d$ が存在するためです。詳細はベズーの等式の紹介のときにまた触れます

RSAの暗号化

平文を $m$ とし、暗号化処理を $Enc(m, e, n)$ とすると暗号化処理は以下のようになります

$Enc(m, e, n) = m^{e}\bmod n$

RSAの復号

さきほどの暗号化処理で生成された暗号文を $c$ とし、復号処理を $Dec(c, d, n)$ とすると複合処理は以下のようになります

$Dec(c, d, n) = c^{d}\bmod n$

つまり、RSAでの平文 $m$ と暗号化/復号の関係性は以下のようになります(同じ法 $n$ に対しての剰余を取る操作は後でまとめても結果に影響しないので適宜省略)

$(m^{e})^{d} = m^{ed} \equiv m\pmod n$

ようは、 $m^{e}$ したあとさらにそれを $d$ 乗すると平文 $m$ にもどる！ということを言っています。わりと直感的には理解しづらい主張ですね

実際これは正しいのですが、これからそれを証明します

RSAの復号の証明

$m^{ed} \equiv m\pmod n$ となることを証明します

まず $ed$ について、条件より $ed\equiv 1\pmod{(p-1)(q-1)}$ となるように生成しているため $(p-1)(q-1)$ の倍数に1足したものと考えられます。そのため

$ed = s(p-1)(q-1) + 1$

とかけます。これを証明したい式に代入すると以下のようにできます

$m^{s(p-1)(q-1) + 1} = m\cdot (m^{(p-1)(q-1)})^{s} \equiv m\pmod n$

この式をグッとにらみつけると、仮に $m^{(p-1)(q-1)} \equiv 1\pmod n$ となるとすると $m\cdot (1)^{s} \equiv m\pmod n$ となり題意が示せそうなことがわかります
以前証明したフェルマーの小定理をつかって $m^{(p-1)(q-1)} \equiv 1\pmod n$ が成り立つことを示してみます

フェルマーの小定理: 素数 $p$ とその倍数でない正の整数 $a$ について、 $a^{(p-1)}\equiv 1\pmod p$ がなりたつ

方針としてはフェルマーの小定理だけだと $n$ で割って1あまることを確認するのは少し面倒なので、変形して $m^{(p-1)(q-1)} - 1 \equiv 0\pmod n$ が成り立つことをまず確認します。式変形しただけなので、これが成り立てば元の $m^{(p-1)(q-1)} \equiv 1\pmod n$ も成り立ちます $m^{(p-1)(q-1)} - 1$ が素数 $p, q$ どちらでも割り切れることを確認すれば、 $p, q$ は互いに素なので $n = pq$ でも割り切れることが示せそうです。それではやっていきます

$m^{(p-1)(q-1)} \equiv 1\pmod n$ が成り立つ

まず $p$ について確認します。 $m^{(p-1)(q-1)}$ について $m$ と $p$ が互いに素ならフェルマーの小定理より以下が成り立つことがわかります

$(m^{(q-1)})^{p-1} \equiv 1\pmod p$ 変形して $(m^{(q-1)})^{p-1} - 1\equiv 0\pmod p\ ... i$

同様に $p$ についても $m$ と $q$ が互いに素ならフェルマーの小定理より

$(m^{(p-1)})^{q-1} - 1\equiv 0\pmod q\ ... ii$

$i, ii$ より、 $m^{(p-1)(q-1)} - 1$ は素数 $p, q$ で割り切れるため $n = pq$ でも割り切れる。よって

$m^{(p-1)(q-1)} - 1 \equiv 0\pmod n$ 変形して $m^{(p-1)(q-1)} \equiv 1\pmod n$

これを

$m\cdot (m^{(p-1)(q-1)})^{s} \equiv m\pmod n$ の式に代入すると

$m\cdot (1)^{s} \equiv m\pmod n$

となり、 $m$ が $n$ 互いに素な場合において証明できた

※ちなみに $m$ と $n$ が互いに素でない場合についても同様に復号できることが証明できるけど全体の構成がちょっと変わるので省略した。一般に見かけるRSAの証明も大体似た流れで $m$ と $n$ が互いに素でない場合を考慮していないことが多いし流れに身を任せた。Advent Calendar でネタなくなったらそっちの証明も書くかも

Goでサクッと実装

証明ができてちゃんと成り立つこともわかったのでサクッと実装してみよう！
いまのところ $ed\equiv 1\pmod{(p-1)(q-1)}$ を満たす $d$ の生成については詳細は触れていないので読み流してください。適当に標準パッケージでシュッとやってます

鍵生成とかはこんなかんじ

func genKey() (n, e, d *big.Int) {
    e = big.NewInt(65537)
    // e と (p-1)(q-1) が互いに素となるような p, q を決定する
    var p, q *big.Int
    for {
        p, _ = rand.Prime(rand.Reader, 256)
        q, _ = rand.Prime(rand.Reader, 256)
        // ed ≡ 1 (mod φ(n)) となる e の逆元を求める
        // 逆元が存在しなければ e と (p-1)(q-1) が互いに素でないのでもう一度やり直す
        d = new(big.Int).ModInverse(
            e,
            new(big.Int).Mul(
                new(big.Int).Add(p, big.NewInt(-1)),
                new(big.Int).Add(q, big.NewInt(-1)),
            ),
        )
        if d == nil {
            continue
        }
        break
    }

    n = new(big.Int).Mul(p, q)
    return n, e, d
}

勉強用の実装なので、 $p, q$ が重複する可能性は無視してます。まあ $2^{256}$ くらいのサイズがあるからそんな気にするほどでもないけど念の為
鍵生成のところはいまはサクッと読み飛ばしてください

で、EncとDecは単にべき乗してmodとるだけなので省略

実行してみたい方や、動作する形のコードがみたいかた向けにplaygroundのリンクもはっときます go.dev