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

はじめに

RSAが署名につかえるよーみたいな話をやったので、今回はブラインド署名について話そうと思います

なお今回紹介するブラインド署名の仕組みはある程度簡略化しています。実際にはRSA署名自体を RSA-PSS など安全な仕組みで行うべきなのでもう少し複雑です。が、署名部分の安全性を除いて考えると原理的には同じです。今回は簡単のためにHash処理や確率的アルゴリズムによる操作を考えないものとします

ブラインド署名とは

署名者がメッセージの具体的な内容を知ることなく署名できる！という仕組みです

なんとなくなにがうれしいか分かりづらいですが、たとえば電子投票などで利用できるといえばすこしイメージしやすいかもしれません
有権者の投票をメッセージとすると、ブラインド署名の技術を使えば選挙を管理する団体は有権者による投票の具体的な内容を知ることなく署名によりその投票の有効性を保証できます

メッセージの内容をなにも知らずに署名を行うと、たとえば不正と思われるメッセージに対して署名してしまうかもしれません。
そのような場合のために 部分ブラインド署名 という仕組みもありますが今回はそれについては触れません

RSAによる(簡易的な)ブラインド署名のしくみ

RSAと同じく秘密鍵を $d$ , 公開鍵を $n, e$ とします。
平文を $m$ , ブラインドされたメッセージを $b$ , それへの署名を $bs$ , アンブラインドされた署名を $s$ とします。
ブラインド処理を $Blind(m)$ , ブラインドされたメッセージに対しての署名を $Sign(b)$ , アンブラインド処理を $Unblind(bs)$ とすると、それぞれの処理は以下です

ブラインド署名を要求するクライアントAliceは乱数 $r$ を発行して $Blind(m) := r^{e} m \bmod n$ を実行しブラインドされたメッセージ $b$ を生成
ブラインド署名を実行するBobはAliceから $b$ をうけとり、 $Sign(b) := b^{d} \bmod n$ を実行し署名 $bs$ を生成
Aliceは受け取った $bs$ にたいして $Unblind(bs) := \dfrac{bs}{r} \bmod n$ を実行することでアンブラインドされた署名 $s$ が取得できる。アンブラインドされた署名を通常の署名のように $s^{e}$ して検証すれば有効性を確認できる

処理を流れを図にすると以下のようになります

f:id:convto:20211206011849p:plain — uml図

署名が得られることの確認

ブラインドされた署名は $bs = b^{d} \bmod n$ なので $b^{d}$ について整理します

$bs \equiv b^{d} \equiv (r^{e}m)^{d} \equiv r^{ed}m^{d} \equiv r(m^{d}) \pmod n$

(念の為途中式の補足しておくと、RSAは元の内容を $ed$ 乗するともとに戻るので、 $r^{ed} \equiv r \pmod n$ となります)

$bs$ を整理した $r(m^{d})$ に対してアンブラインド処理 $\dfrac{bs}{r} \bmod n$ を適用すると

$\dfrac{r(m^{d})}{r} = m^{d}$

となり、RSAの署名が得られます。これを通常の署名のように $e$ 乗すると元のメッセージに戻り検証が可能です

$m^{ed} \equiv m\pmod n$

こうしてみると、乱数 $r$ をAliceが採番することによりアンブラインド処理を $r$ を知るAliceにしかできなくすることができています。本人以外にメッセージ内容はわからないということですね！よくできてる

実装

いつものとおりサクッとGoで実装します

まずはブラインド署名を実施するBobの実装をします。それぞれが持ってる情報をわかりやすくするためstructで実装します
処理はブラインドされたメッセージへの署名を実施するのみです。

type Bob struct {
    d, n *big.Int
}

func NewBob(d, n *big.Int) *Bob {
    return &Bob{
        d: d,
        n: n,
    }
}

// bs = ((r^e)m)^d mod n
func (bob *Bob) Sign(b *big.Int) (bs *big.Int) {
    return new(big.Int).Exp(b, bob.d, bob.n)
}

つぎにブラインド署名を依頼するAliceの実装をします。Aliceのほうがやることが多くて

乱数 $r$ の生成
ブラインド処理 $r^{e} m \bmod n$
ブラインド署名 $bv$ のアンブラインド処理 $\dfrac{bs}{r} \bmod n$
取り出した署名 $s$ の検証処理 $s^{e} \bmod n$

です。

また、アンブラインドの $\dfrac{bs}{r} \bmod n$ の処理は注意が必要で、これは $n$ の剰余環についての演算なので、除算を通常通りやってしまうと期待する結果がえられません。
$r\cdot r' \equiv 1\pmod n$ となる $n$ の剰余環で $r$ の逆元である $r'$ を見つけてそれに対する積を求める必要があります。(余談ですが実装してるときにこの部分を間違えて2時間くらい溶かしました)

逆元が存在するには法 $n=pq$ と $r$ が互いに素である必要がありますが、 $p, q$ は素数なのでそのサイズ以下にしておけば確実に互いに素なので、今回の実装では簡単のため $r$ を 100000 までの範囲の乱数としました。

その部分以外はただ実装しただけです。

type Alice struct {
    n, e, m *big.Int
    r       *big.Int
}

func NewAlice(n, e, m *big.Int) *Alice {
    return &Alice{
        n: n,
        e: e,
        m: m,
    }
}

func (a *Alice) GenR() {
    // n と互いに素となるような r を決定する
    // n の素因数である p, q はこの例では256bitの素数なので、それ以下のサイズであれば r は必ず n と互いに素
    // そのため逆元が存在するかどうかの確認は省略
    a.r, _ = rand.Int(rand.Reader, big.NewInt(100000))
}

// b = (r^e)m mod n
func (a *Alice) Blind() (b *big.Int) {
    return new(big.Int).Mod(
        new(big.Int).Mul(
            new(big.Int).Exp(a.r, a.e, a.n),
            a.m,
        ),
        a.n,
    )
}

// s = r(m^d) / r mod n
func (a *Alice) UnBlind(bs *big.Int) (s *big.Int) {
    rinv := new(big.Int).ModInverse(a.r, a.n)
    return new(big.Int).Mod(
        new(big.Int).Mul(bs, rinv),
        a.n,
    )
}

func (a *Alice) Verify(s *big.Int) (m *big.Int) {
    return new(big.Int).Exp(s, a.e, a.n)
}

これを以下のようなmain関数から呼び出します。aliceとbobにブラインド署名の処理をさきほどのシーケンスの順番通りに実行させます。
(鍵生成はRSAの証明のときに書いたので省略しています)

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()

    alice := NewAlice(n, e, m)
    bob := NewBob(d, n)

    alice.GenR()
    b := alice.Blind()
    fmt.Printf("blinded message: %v\n", b)
    bs := bob.Sign(b)
    fmt.Printf("blinded signature: %v\n", bs)
    s := alice.UnBlind(bs)
    fmt.Printf("signature: %v\n", s)
    v := alice.Verify(s)
    fmt.Printf("virify: %t\n", reflect.DeepEqual(m, v))
}

実行すると以下のような結果が得られるはずです(乱数に依存する処理があるので blinded message, blinded signature, signature は決定的ではありません)

plaintext: The magic words are squeamish ossifrage
blinded message: 592957193912741560485532936104481959901518939369688587213309390950940683284871864199151664911326672170426514357864552958032172239286245351844559969737706
blinded signature: 7021267363287817737401875019523677553252335152810568286952416800840028523381395206665687986007962789965437098704805186095987630187600415576730736518068103
signature: 4726576568790966315239152609717797468737737789715291013734854275870306906266006340501466960627372311329448519074779028377114021337693275921039530136195791
virify: true

手元で実行したい方向けにplaygroundのリンクも貼っておきます

go.dev