剰余環の逆元の探索とRSAの秘密鍵生成 - ちりもつもればミルキーウェイ

はじめに

これは RSA完全理解 Advent Calendar の10日目の記事です

いままででユークリッド互除法でベズーの等式の解が探索できることと、剰余環とかの言葉の意味がわかるようになりました。

ここまでくると剰余環の逆元を求める処理の説明ができるのでやっていきましょう！

これがわかるようになれば、素のRSAでつかわれる直感的に理解しづらい数学的な操作の裏付けはほぼ完了するはず！

(余談ですが一般にコンピュータが巨大な値の数値計算するときには数学的な知識を背景にしたテクいアルゴリズム使ってるので数学の出番はまだまだあります)

(数学的な裏付けだいだいおわった！っていうのはそもそもなんで成り立つんだっけ？みたいな根本的に意味わからんみたいな内容の説明についてはこれでひとしきり終わったかなーという意味です)

それではやっていきます

必要な知識

けっこう文脈があるので、この記事から読む人向けに必要知識をまとめておく

このへんがしっかりわかっていれば今回の内容はなんも難しくないです

剰余環の逆元と互いに素なベズーの等式の解の関係性

まず $a, b$ が互いに素なときは $gcd(a, b) = 1$ ですから

$ax + by = 1$

はベズーの等式を満たしているので、このときの解 $x, y$ は拡張ユークリッド互除法にて求まります。
さて、この式を変形すると

$ax = 1 + -by$

となります。これは $b$ の倍数+1 の形なので $b$ で剰余を取ると

$ax \equiv 1\pmod b$

となり剰余環の逆元のかたちになります！つまりこのときの解 $x$ が法 $b$ と元 $a$ に対する剰余環の逆元となることがわかります

以上で示したように、拡張ユークリッド互除法を用いて剰余環の逆元を求めることができます

実装

基本的には上の説明がわかっていればチョロいんですが、1点気をつけないといけないのはコンピュータは剰余をとるときに絶対値に対してあまりをとる操作をすることです。

なので、先程の途中式 $ax = 1 - by$ のときに $by$ が正だと、絶対値でいうと $by-1$ となってしまうため、コンピュータで実行する際には成り立たなくなります。ということは移項する前の元式 $ax + by = 1$ のときは $by$ は負でないといけません。そこから $ax$ は $ax = |by| + 1$ となるような正の値である必要があります。

そのため $x$ が負なら $ax + by = d$ の解の性質を使ってゴニョゴニョしてうまく条件を満たす形で結果を返してあげます

拡張ユークリッド互除法を用いて $ax + by = d$ について探索
gcd = 1だったら解の値が逆元候補
- $x$ が正だったら $x\bmod b$ が $a$ の逆元
- $x$ が負だったら正の解をさがす。 $ax + by = 1$ の解 $x$ について $x + b, x - b$ となる別解も存在する。また $x\bmod b$ を満たす別解も存在するので $((x\bmod b) + b)\bmod b$ とでき、それを逆元とできる

正の解を探すところはこんがらがるので一応補足しておく

$ax + by = 1$ の解 $x, y$ について $x + b, y - a$ と $x - b, y + a$ となる別解が存在する

基準となる式 $ab - ba = 0$ とその逆の $-ab + ba = 0$ を考えるとすぐわかる。
$ax + by = 1$ が成り立って解 $x, y$ があるなら

$ax + by + ab - ba = a(x+b) + b(y-a) = 1$ がなりたつ
$ax + by + ba - ab = a(x-b) + b(y+a) = 1$ がなりたつ

よって

$x+b, y-a$
$x - b, y + a$

となる解が存在する

$ax + by = 1$ の解 $x, y$ について $x' \equiv x\pmod b$ を満たせば別解 $x'$ が存在する

さきほど示したように

$x+b, y-a$
$x - b, y + a$

となる解が存在する。
つまり現在の $x$ の解を $x_i$ とすると

$x_{i-1} = x - b$
$x_{i+1} = x + b$

とできる。これは数学的帰納法により任意の $b$ の倍数の加算と減算に対応でき、つまり $x' \equiv x\pmod b$ を満たす別解 $x'$ が存在する。

func invmod(a, b int64) (int64, error) {
    gcd, x, _ := extGCD(a, b)
    fmt.Println(gcd)
    if gcd != 1 {
        return 0, errors.New("modular inverse does not exists")
    }
    if x < 0 {
        return (x%b + b) % b, nil
    }
    return x % b, nil
}

go.dev