電子署名～RSA署名～

みなさんこんにちは。

ブロックチェーンにはデジタル署名の技術が欠かせません。が、ブロックチェーンによく使われるECDSAをいきなり説明するには難しいので、順を追って、簡単（？）なRSA署名から紹介していきたいと思います。

準備

RSA署名の流れを説明する前に、前提となるものを説明します。素因数分解や、互いに素など、義務教育の範囲のものはスキップします。

合同式

[latex]a \equiv b \bmod m[/latex]

とすると、「[latex]a[/latex]を[latex]m[/latex]で割った余りと[latex]b[/latex]を[latex]m[/latex]で割った余りは同じ」という意味になります。

RSA署名の流れ

鍵生成

任意の[latex]k[/latex]を入力して、[latex]k[/latex]ビットの素数[latex]p,q[/latex]をランダムに生成します。
[latex]N=pq[/latex]を求めておきます。
[latex](p-1)(q-1)[/latex]との最大公約数が1となるような[latex]e[/latex]をランダムに選びます。
[latex]ed \equiv 1 \bmod (p-1)(q-1) [/latex]をみたす[latex]d(>0)[/latex]を求めます。

この流れにより、公開鍵[latex]pk=(N,e)[/latex]、秘密鍵[latex]sk=d[/latex]が決められます。

署名

署名したいメッセージ[latex]m[/latex]があるとします。

秘密鍵[latex]sk=d[/latex]を使い、[latex]\sigma = m^d \bmod N [/latex]を計算します。これが署名となります。

検証

公開鍵[latex]pk=(N,e)[/latex]を使い、[latex]m \equiv \sigma^e \bmod N[/latex]が成り立つかを検証します。

数式に関しては、ふんわりとした理解で大丈夫だと思います。

安全性

素因数分解問題

コンピュータで巨大な合成数の素因数分解を、多項式時間で解く問題を素因数分解問題といいます。

※合成数…二つ以上の素数の積でできる数

この素因数分解問題を解くアルゴリズムはまだ見つかっていません。

しかし、「存在しない」と証明されているわけでもありません。なので、これは「仮定」の状態です。

RSA問題

次に、「[latex](N,e)[/latex]から、[latex]d,p,q[/latex]を求める」という問題を「RSA問題」とします。

このRSA問題も、解法が未だに見つかっていないため、RSA問題を解くのが困難だという「RSA仮定」があります。

素因数分解問題困難仮定を使うと、[latex]N[/latex]を素因数分解して[latex]p,q[/latex]を求め、[latex](p-q)(q-i)[/latex]を求め、[latex]e[/latex]から[latex]d[/latex]を求める、ということが難しいといえます。

なのでこのRSA仮定は、素因数分解問題困難仮定よりも「強い」仮定となります。

言い換えれば、素因数分解問題の解法が見つかると、RSA問題の解法がみつかる、ということになります。

「巨大な合成数の素因数分解を、多項式時間で解くアルゴリズムは存在しない」という仮定のもとでやっと、RSA署名は安全だ、という根拠の一つができるということになります（後述するように、実際はそれ以外の理由で安全ではありません）。

ちなみに、量子コンピュータは素因数分解を多項式時間で解けることも知られています。そのため、量子コンピュータが実用化されると、RSA署名は偽造されうるようになります。

積攻撃

[latex]m_1,m_2[/latex]があるとします。

それぞれの署名データは

[latex]Sig(m_1)=\sigma_1 = m_1^d \bmod N[/latex]

[latex]Sig(m_2)=\sigma_2 = m_2^d \bmod N[/latex]

となります。これらの署名データが盗聴されたとしましょう。

本来は署名は盗聴されても問題が発生するべきではないですが、RSA署名では問題が発生します。

[latex]Sig(m_1)Sig(m_2)[/latex]を計算すると、

[latex]Sig(m_1)Sig(m_2)=\sigma_1 \sigma_2 = (m_1 m_2)^d = Sig(m_1 m_2) \bmod N[/latex]

となり、[latex]d[/latex]を知らなくても、[latex]m_1 m_2[/latex]の署名を作り出すことができてしまうのです。

この性質を乗法準同型性といいます。

ちなみに、[latex]Sig(m_1)+Sig(m_2)=Sig(m_1 + m_2)[/latex]の場合は加法準同型性といいます。

素RSA署名

RSA署名は、RSA暗号と同様、ナイーブに実装すると脆弱なものになります。ナイーブな実装は素RSAとも呼ばれます。

そのため、パディングと呼ばれる処理などが必要です。

RSA暗号 – Wikipedia

おわりに

このように、暗号や電子署名は、素因数分解のように、一方向の計算はすぐできるが逆はすぐにできないという性質を使っています。

次回はRSA署名より難しいDSAをご紹介し、その次にブロックチェーンでよく使われるECDSAをご紹介します。