RSAによる署名 - ちりもつもればミルキーウェイ

はじめに

これは RSA完全理解 Advent Calendar の4日目の記事です
昨日はRSAの操作について説明したので、今回はそれをつかった署名について触れたいと思います

なお、今回紹介する署名は実際の方式から大幅に簡略化しています。現実には各種攻撃を防ぐため安全なhash関数を噛ませてメッセージ長を固定化したり、決定的な出力としないために確率的な操作を入れていたりします。

RSAの暗号化/復号の特別な性質について

RSAは暗号化/復号の操作を振り返ると

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

となるのでした

これらはよく見ると「与えられた底 $a$ 、指数 $b$ 、法 $n$ を使って $a^{b} \bmod n$ を取る」という同一の操作を行っています

また、RSA暗号は以前証明したとおり $m^{ed} \equiv m\pmod n$ となります
つまり、暗号化/復号の処理が同一なため、操作の順番を入れ替えても最終的に $m^{ed}$ の形式になりさえすれば平文 $m$ に戻るということです

試してみると

$m$ に対して順番を入れ替えて先に復号相当の操作をためすと $s = m^{d} \bmod n$
$s$ に対してそのあとに暗号化相当の操作をためすと $m = (m^{d})^{e} \bmod n$

となり、操作の順番を入れ替えても最終的に $m^{ed}$ の形になり平文に戻ることがわかります

これは他の暗号にはあまりない性質で、またRSA署名にも利用される重要な性質です

RSA署名について

※以下で紹介する内容はあくまで原理的な説明であり、そのまま利用すると安全ではありません。現実にRSA署名を利用する場合は RSA-PSS などの安全な実装を利用してください

平文を $m$ , 署名を $s$ , 署名をする処理を $Sign(m, d, n)$ , 検証を $Verify(s, e, n)$ とするとそれぞれの操作は以下です

$Sign(m, d, n) = m^{d} \bmod n$
$Verify(s, e, n) = s^{e} \bmod n$

これが成り立つことはさきほど説明したRSAの性質からわかります。

あたりまえですがこれは暗号としては成り立っていません。なぜなら、メッセージの内容を公開鍵を知っている第三者なら誰でも確認することができるためです。

ではなにがうれしいのかというと、署名ができるのが $d$ を知っているものだけというのが保証できることです
署名としてのRSAは、秘密鍵を知らない第三者がメッセージに署名を行えないことをRSAの安全性の上で保証できます

公開鍵を使って署名を検証する場合は平文 $m$ と署名 $s$ をうけとり、 $m$ と $s^{e} \bmod n$ を比較して一致するか確認すればよいです。一致していれば秘密鍵 $d$ によって署名された内容であることがわかるので信頼でき、一致しなければ秘密鍵 $d$ による正しい署名がされていないとしてその内容は破棄できます

実装してみる

実装があったほうがイメージしやすいと思うのでサクッと実装します。とはいえ RSAの証明で実装したコードと鍵生成部分は全く同一です。異なるのは操作の順番と、検証処理のみです。差分があるmain関数のみ記載します

func main() {
    plaintext := "The magic words are squeamish ossifrage"
    fmt.Printf("plaintext: %s\n", plaintext)
    m := new(big.Int).SetBytes([]byte(plaintext))

    n, e, d := genKey()

    s := new(big.Int).Exp(m, d, n) // RSAによる署名 m^d mod n
    fmt.Printf("signature: %v\n", s)

    v := new(big.Int).Exp(s, e, n) // RSAによる署名の検証 s^e mod n
    fmt.Printf("virify: %t\n", reflect.DeepEqual(m, v))
}

署名は秘密鍵 $d$ を使って行い、その検証は公開鍵 $e$ で行われます。単にその内容が平文 $m$ と一致しているか調べれば署名が有効か判断できます

go.dev