量子コンピュータ耐性があるランポート署名について解説&シェルスクリプトで実装してみた

  • 22
    いいね
  • 1
    コメント

はじめましての人ははじめまして。かちおと申します。
今回は表題の通り、量子コンピュータ耐性があると言われているランポート署名についての解説と、実装したものを紹介しようと思います。

ランポート署名について

近年、量子コンピュータが普及すると、その計算力により暗号・電子署名が解かれる…なんて問題が提唱されています。
その解決策の1つとして、「ランポート署名(Lamport Signature)」があります。
これは、単純な一方向関数(ハッシュ関数)を組み合わせ、署名にかかる時間と、総当たり計算にかかる時間の差を引き離すことで、量子コンピュータでも相当な時間かけないと解読できないだろう、と考えられている電子署名です。

仕組み

ボブがアリスに、データと、その署名を送信したいとします。

秘密鍵と公開鍵の作成

まずボブは、長さが長い(256bit程度)乱数を256対生成します。つまりトータルで512個の乱数が生成されることになります。
配列宣言風にいえば、int [256][2];となるでしょう。たとえば対の片方を乱数a、もう片方を乱数bと呼びましょう。
これが秘密鍵的な役割になります。
そして、その全てのハッシュ値を取り、公開鍵として世界に公開します。

秘密鍵 (公開しない)

乱数対 乱数a 乱数b
1対目 aaa bbb
2対目 ccc 111
3対目 222 333
4対目 444 555
5対目 666 xyz

公開鍵 (公開する)

乱数対 乱数aのハッシュ値 乱数bのハッシュ値
1対目 hash(aaa) hash(bbb)
2対目 hash(ccc) hash(111)
3対目 hash(222) hash(333)
4対目 hash(444) hash(555)
5対目 hash(666) hash(xyz)

署名の作成

次に、ボブは送りたいデータのハッシュ値を取ります。
データのハッシュ値を取得したら、それをすべて2進数に直します。
そして先頭からビットが0か1か判断し、1ビット目が0だった場合、乱数の1対目の乱数a、1だった場合は乱数の対の1対目の乱数bを公開します。
これを全256bit分繰り返します。これにより、256対(512個)あった乱数のうち256個だけが公開されます。

署名 (公開する)

ビット ハッシュ値
1 hash(bbb) ※1対目の乱数bの方のハッシュ値
0 hash(ccc) ※2対目の乱数aの方のハッシュ値
1 hash(333) ※3対目の乱数bの方のハッシュ値
1 hash(555) ※4対目の乱数bの方のハッシュ値
0 hash(666) ※5対目の乱数aの方のハッシュ値

検証

アリスは、ボブから、公開鍵、データ、署名を手に入れます。
このデータが本当にボブから送信されたか確認してみましょう。
このときボブが知っているのは、「256対の乱数すべて」で、アリスが知っているのは、ボブから公開鍵として送られた、「256対の乱数のハッシュ値すべて」と、署名として送られた「256対の乱数の半分」となります。
つまり、ボブ以外は、秘密鍵のハッシュ値を知っていても、その元の平文は半分しか知りません。

アリスが知っている乱数

乱数対 乱数a 乱数b
1対目 ??? bbb
2対目 ccc 111
3対目 ??? 333
4対目 ??? 555
5対目 666 ???

ここで、アリスは、データのハッシュ値を取り、それを全て2進数に直します。
そして、署名として渡された乱数、つまり256対の乱数の片方だけをすべてハッシュ化します。

ビット ハッシュ値
1 hash(bbb) ※1対目の乱数bの方のハッシュ値
0 hash(ccc) ※2対目の乱数aの方のハッシュ値
1 hash(333) ※3対目の乱数bの方のハッシュ値
1 hash(555) ※4対目の乱数bの方のハッシュ値
0 hash(666) ※5対目の乱数aの方のハッシュ値

こうすることで、アリスは元からボブからもらっていた公開鍵と、署名を比べて等しかったら、検証が完了します。

乱数をすべて知っているのはボブだけなのです。
つまり、送りたいデータの(ハッシュ値の)ビットごとに乱数を選んで、署名とすることで、自分だけが乱数を持っていると証明できます。
アリスは、元からボブの公開鍵を持っているので、ボブから渡された乱数(署名)のハッシュさえとれば、乱数が正しいかわかります。

まとめ

  1. 512個の乱数を作って、署名したいデータの2進数列を元に、公開する乱数を選ぶ。
  2. 公開鍵(乱数のハッシュ値)を知っている人は、その乱数をハッシュ計算することで、その乱数はボブが元から持っていたものと同じか確認する。
  3. 使いたい乱数を、2進数の列を元に公開できるのは、乱数a,b両方知っている署名者本人だけとなる。

おまけ

よく見れば分かるように、データのハッシュ化に使う乱数のハッシュ値の長さと、乱数対の対の数は同じでなければいけません。
でも、乱数をハッシュ化するのに用いるハッシュ関数は異なっても構いません。
なので、ハッシュ関数を2種類使って実装することもできますね。

シェルスクリプトで実装してみる

最初はまともな言語で実装しようと思ったのですが、なにぶん書ける言語が少ないもので、一番簡単に作れるのはなんだろう、と考えたときにパッと思いついたのが、シェル芸人な私の大好き変態言語シェルスクリプトでした。
やはり、エンジニアは日本語じゃなくてコードで殴り合わなきゃね!ということで、おそらく上の説明を読むよりも理解できるかと思います。
あまりコードを書くのが得意でないので、わからないところや、間違っているところなどあればコメントで指摘して頂けるとありがたいです。

lamport.sh
#!/bin/bash

create_private(){
        mkdir -p private-keys
        for i in {001..256};do
                head --bytes=32 /dev/urandom > private-keys/key${i}_a.private
                head --bytes=32 /dev/urandom > private-keys/key${i}_b.private
        done
}

create_public(){
        mkdir -p public-keys
        echo -n "" > publickey.pub
        for i in {001..256};do
                sha256sum private-keys/key${i}_a.private | cut -d " " -f 1 | tr -d "\n" > public-keys/key${i}_a.pub
                sha256sum private-keys/key${i}_b.private | cut -d " " -f 1 | tr -d "\n" > public-keys/key${i}_b.pub

                cat public-keys/key${i}_a.pub >> publickey.pub
                echo "" >> publickey.pub
                cat public-keys/key${i}_b.pub >> publickey.pub
                echo "" >> publickey.pub

        done
}

hash2bit(){
        BIT=""
        for i in {1..64};do
                NUM=$( echo -n "$1" | cut -c$i | xargs -I{} printf "%d" "0x{}" )
                BIT1=$(( ( NUM & 1 ) >> 0 ))
                BIT2=$(( ( NUM & 2 ) >> 1 ))
                BIT4=$(( ( NUM & 4 ) >> 2 ))
                BIT8=$(( ( NUM & 8 ) >> 3 ))
                BIT=${BIT}${BIT1}${BIT2}${BIT4}${BIT8}
        done
        echo "${BIT}"
}

create_sig(){
        echo -n "" > signature.sig
        for i in {001..256};do
                FLAG=$( echo $1 | cut -c$i)
                if [[ $FLAG == "0" ]];then cat private-keys/key${i}_a.private | base64 | tr -d "\n" >> signature.sig ; fi
                if [[ $FLAG == "1" ]];then cat private-keys/key${i}_b.private | base64 | tr -d "\n" >> signature.sig ; fi
                echo "" >> signature.sig
        done
}

check(){
        HASH=$( sha256sum $1 | cut --d " " -f 1 | tr -d "\n")
        HASH=$(hash2bit ${HASH})

        echo -n "" > signature2.sig
        echo -n "" > publickey2.pub

        for i in {1..256};do
                FLAG=$( echo ${HASH} | cut -c$i)
                if [[ $FLAG == "0" ]];then cat publickey.pub | head -n $(( $i * 2 - 1 )) | tail -n 1 | tr -d "\n" >> publickey2.pub ; fi
                if [[ $FLAG == "1" ]];then cat publickey.pub | head -n $(( $i * 2     )) | tail -n 1 | tr -d "\n" >> publickey2.pub ; fi
                echo "" >> publickey2.pub

                cat signature.sig | head -n $i | tail -n 1 | base64 -d | sha256sum | cut -d " " -f 1 >> signature2.sig
        done
}

if [[ ! -f $1 ]];then echo "file not found" ; exit 1 ; fi

HASH=$( sha256sum $1 | cut --d " " -f 1 | tr -d "\n")

echo "File Name : $1"
echo "File Hash : ${HASH}"
echo

echo "Creating Private keys ..."
create_private # 秘密鍵の生成

echo "Creating Public keys ..."
create_public # 公開鍵ファイルであるpublickey.pubの作成

create_sig $( hash2bit ${HASH} ) # ファイルを署名し、署名ファイルであるsignature.sigを生成
echo "Create signature success."

rm -rf private-keys public-keys # ここで秘密鍵と公開鍵の一時ファイルを削除する。

check $1 # ここで、signature.sigとpublickey.pubのみで署名を検証している。

ランポート署名の安全性を、簡単に確認してみる

ランポート署名の安全性を確認してみましょう。つまり、総当り計算をするときにどれくらいの計算力が必要化を計算すれば良いことになります。

まず、通常の署名をするときの計算量を見てみましょう。
この場合、データ本体のハッシュ値と、512個の乱数のハッシュ計算が必要になります。

次に検証するときの計算量です。
データ本体のハッシュ計算と、256個の乱数のハッシュ計算が必要になります。

では総当りするときを考えてみましょう。
まず送りたいデータのハッシュ値が256bitあるとすればします。
この場合必要な乱数のハッシュ値は256個となります。
つまり、単純計算で、通常のハッシュ計算の総当りに必要な計算量×256の計算量が必要となります。

このあたりの詳しいことは、今回参考にしたWikipediaのページに掲載されています。
この記事の最後にリンクを載せてあるので、興味のある方はぜひ一度目を通してみてください。

ランポート署名の問題点

ランポート署名の問題点として、「公開鍵が本当にその人のものか証明する必要がある」ことと、「一度使った乱数対は二度と使えない(使わないほうが良い)」という問題があります。
前者は、現状全ての電子署名に言えることです。
後者に関しては、ランポート署名は乱数対を署名のたびに半分公開してしまうことが原因となっています。
なので、毎回秘密鍵・公開鍵を生成してあげる必要があります。

最後に

量子コンピュータが注目を浴びている中、今回のような「量子コンピュータ耐性」というものは、セキュリティ上将来的にどんどん必要になってくると思います。
そのためにも、暗号技術や署名に関して、今のうちに学んでおくと良いかと思います。
まあ一番の理由は、面白いからなんですけどね…笑

ということで、今回はココまでとなります。駄文でしたが、最後まで読んで頂きありがとうございました。

参考

Wikipedia : https://en.wikipedia.org/wiki/Lamport_signature

そして、うまく理解できなかったランポート署名の論文を一緒に読んでくれ、わかりやすく説明してくれたR先輩に感謝をここに述べておきます。