LoginSignup
60
42

More than 5 years have passed since last update.

@onokatio(おのかちお)

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

Last updated at Posted at 2017-07-13
1 / 2

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

ランポート署名について

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

仕組み

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

秘密鍵と公開鍵の作成

まずボブは、長さが長い乱数を256 対生成します。つまりトータルで512個の乱数が生成されることになります。
※あとで説明しますが、この256という数字はデータのハッシュ値のビット幅と同じであればなんでもよいです。

配列宣言風にいえば、int [256][2]となるでしょう。たとえば対の片方を乱数a、もう片方を乱数bと呼びましょう。
これが秘密鍵的な役割になります。

そして公開鍵は、さきほど作った秘密鍵の全ての対をハッシュ値にしたモノです。
こっちは世界に公開します。

左が秘密鍵の対（公開しないもの）、右が公開鍵の対（公開するもの）です

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

署名の公開

次に署名を作成してみましょう。
ボブは送りたいデータ(ファイルでもなんでも良い)のハッシュ値を取ります。
ハッシュ値を取得したら、それをすべて2進数に直します。

例
平文: HelloWorld
SHA256: 872e4e50ce99…e9bb12c4
2進数: 010011000010…01111000

そして先頭からビットが0か1か判断し、1ビット目が0だった場合、乱数の1対目の乱数a、1だった場合は乱数の対の1対目の乱数bを公開します。
これを全256bit分繰り返します。これにより、256対(512個)あった乱数のうち256個だけが公開されます。

署名 （公開する）

番号 ビット ハッシュ値
先頭1ビット目 0 hash(aaa) ※1対目の乱数aの方のハッシュ値
2ビット目 1 hash(111) ※2対目の乱数bの方のハッシュ値
3ビット目 0 hash(222) ※3対目の乱数aの方のハッシュ値
4ビット目 0 hash(444) ※4対目の乱数aの方のハッシュ値
︙ ︙ ︙
256ビット目 0 hash(666) ※256対目の乱数aの方のハッシュ値

検証

アリスは、ボブから、公開鍵・データ・署名を手に入れます。
このデータが本当にボブから送信されたか検証してみましょう。

このときボブが知っているのは、「秘密鍵」(256対の乱数すべて)
アリスが知っているのは、「公開鍵」(256対の乱数のハッシュ値すべて)と「署名」(256対の乱数の、対の片方)となります。
つまり、ボブ以外は、秘密鍵のハッシュ値を知っていても、その元の平文は半分しか知りません。

アリス(と世界中の人)が知っている乱数対(署名と公開鍵)

乱数対 乱数a 乱数b
1対目 aaa と hash(aaa) hash(bbb) ※bbbは知らない
2対目 hash(ccc) ※cccは知らない 111 と hash(111)
3対目 222 と hash(222) hash(333) ※333は知らない
4対目 444 と hash(444) hash(555) ※555は知らない
︙ ︙ ︙
256対目 666 と hash(666) hash(xyz) ※xyzは知らない

ここで、アリスは、ボブが検証で行ったのと同じように、データのハッシュ値を取り、それを全て2進数に直します。アリスは乱数対を全ては知りませんが、ボブは署名に必要な乱数の片方の対だけ公開しています。なのでアリスもボブの検証とまったく同じ作業ができます。

つまり、署名として渡された乱数、つまり256対の乱数の片方だけをすべてハッシュ化します。

番号 ビット アリスが検証した署名 ボブが最初から公開していた公開鍵(乱数のハッシュ値)
先頭1ビット目 0 hash(署名で公開されたaaa) hash(aaa)
2ビット目 1 hash(署名で公開された111) hash(111)
3ビット目 0 hash(署名で公開された222) hash(222)
4ビット目 0 hash(署名で公開された444) hash(444)
︙ ︙ ︙ ︙
256ビット目 0 hash(署名で公開された666) hash(666)

こうすることで、アリスは自分で検証した署名と、元からボブからもらっていた公開鍵とを比べて等しかったら、検証が完了します。
もしボブ以外が署名を作った=本来とは違う方の乱数対を署名として配った場合、ボブの検証作業に必要な乱数対がアリスは手に入りません。なのでハッシュ値が合わなくなり、データが本物ではないことがわかります。

つまり

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

まとめ

  1. 512個の乱数を作って、そのハッシュ値を公開鍵として公開。
  2. 署名したいデータのハッシュ値の2進数列を元に、乱数を選んでそのまま署名として公開。
  3. 署名の乱数をハッシュ計算し、公開鍵と見比べることで、乱数がボブが元から公開していたものと同じか確認する。
  4. 署名に使った乱数を、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のみで署名を検証している。

このシェするクリプトの引数にファイル名を指定することで、乱数対の作成→全部のハッシュ値を計算・保存(公開鍵)→署名を保存→鍵を削除→ファイルのハッシュ値を計算→2進数に変換→署名のハッシュ値をもとめて公開鍵と比較まで一連の流れを自動化しています。うごかしても特に表示は起こりません。むしろ動かすことではなくコードを読むことに意味を置いています。

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

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

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

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

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

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

ランポート署名の問題点

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

最後に

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

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

参考

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

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

60
42
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
60
42