現在のインターネットの安全性の根幹を支えており、基本情報などでも一つの山場として登場する電子署名ですが、普段はあまり意識することなく利用できてしまうため、なんとなく理解してしまっていることはないでしょうか。

例えば、電子署名の流れは一般的には下記のように説明されることが多いと思います。

目的
電子データの改ざんの防止

流れ
・送信者がハッシュ関数で送信データをハッシュ化
・送信者がハッシュ化したハッシュ値を秘密鍵で暗号化
・送信者が送信データ＋暗号化されたハッシュ値を送信
・受信者が受信した暗号化されたハッシュ値を送信者の公開鍵で復号
・受信者が受信データのハッシュ値を算出し、復号化したハッシュ値と比較

これは大まかには正しいですが、実際に運用されている電子署名処理について少し誤解をあたえてしまう内容になっているように思います。（例えば、ハッシュ化＝電子署名のような印象を持ってしまうことはないでしょうか。）

また、電子署名の効果についても、暗号化との違いがわかりにくく、少し誤解が生まれやすい形になっているように思います。（こちらも例えば、暗号化と比べてハッシュ化することで処理が軽くなることが目的、という説明も散見されるときがありますが、必ずしも正しくないです）

この記事について

電子署名をより深く理解するために、現在よく利用されているRSA署名を中心に、電子署名について整理します。

電子署名で実現できるもの

まずは、改めて電子署名の導入の目的となりますが、以下のようなことを実現するためとなります。(Menezes et al.[1997]）

メッセージ作成者の保証
メッセージ完全性（改ざんされていない事）の保証
否認の防止

メッセージが改ざんされていないことの保証も目的の一つですが、その他の効果も重要となります。(メッセージ認証コード (MAC) では実現できないものとなります）

ただし、電子署名単独では、署名者の信頼性は担保できません。

電子署名の作成自体は誰でも可能なため、電子署名が施されていることだけで署名者や署名文書の信頼性の保証はできません。これは、印鑑が押しているからといって、印鑑の持ち主や文書内容の信頼性が保証されていないのと同じです。

署名文書の信頼性の保護については「信頼できる署名者」を予め定義して、その署名者による署名が行われているかを確認する（信頼できる署名者から提供されていることが確実である既知の公開鍵で署名検証する）方法がとられています。

電子署名の利用用途

主にSSL/TLS通信における電子証明書の署名に利用されています。公開鍵の改ざんやなりすましを防止し、中間者攻撃を防ぐ目的で電子署名が導入されています。
（PKI：Public Key Infrastructure）

代表的な方式

電子署名はおもに先の例のように説明されますが、これは主にRSA署名のあるバージョンをもとにした説明となっています。実際には数々の電子署名の方式が提案されています。

電子署名は下記に分類できます。

メッセージ復元型署名（署名からメッセージが復元できる）
署名添付型署名

さらに、それぞれの方式において下記に分類できます。

同一データに対する署名値が常に同じ（確定型）
同一データに対する署名値が異なる（確率型）

以下では現時点で最もよく利用されている方式の一つであるRSA署名のPKCS #1 v1.5の流れを説明します。

PKCS #1 v1.5 (RSA署名)

署名添付型署名（確定型）で最も利用されているものの一つです。OpenSSLなどで幅広く利用可能です。メッセージMに対してハッシュ値とパディングを行ったメッセージに対してRSA暗号化を行う方法です。

この方式は、冒頭の例の処理フローとほとんど同じになりますが、細かい点として暗号化する値に対してハッシュ値だけでなくパディングを施す点が異なっています。

以下にて順を示します。

1. メッセージダイジェストの作成

署名対象のメッセージMに対してハッシュ関数Hを適用してハッシュ値H（M)を作成する。
HはSHA1を始め、SHA224, SHA256, SHA384, SHA512などが適用可能。

2. パディング

以下のスキームによるパディングを行った署名対象メッセージmを作成する

m = (0x) 00||01||PS||00||ID||H(M)

PS: メッセージ全体を鍵長と合わせるようにFFで埋める
ID: ハッシュ関数のオブジェクトID（OID)
H : ハッシュ値

例 SHA1の場合 OID=3021300906052b0e03021a05000414

00 || 01 || FF...FF || 00 || 3021300906052b0e03021a05000414 || H

各ハッシュ関数のOIDの値はISO等で規定されておりRFC文書等で値が定義されています。

※ || の記号は「結合」を意味しています。単純に値を並べているだけの理解で問題ありません

3. 署名値を生成する

下記の式の通り、署名対象メッセージmに対してRSAの秘密鍵dと剰余Nを用いて計算した値を署名値とする

$signature : s = m^d \pmod n$

検証

署名値に対して、RSAの公開鍵eと剰余nを用いて以下の値を計算する。

$m' = s^e \pmod n$

計算した結果のメッセージがPKCS #1 v1.5のパディングスキームを満たしていること、送付されたメッセージのハッシュ値とメッセージダイジェストの値が一致することを確認する。

その他の方式

数学的に安全性が証明されている方式として下記のものがあります。

署名添付型署名(確率型)
- RSA-PSS
- TSH-ESIGN
- Schnorr (離散対数問題に基づく）
メッセージ復元型署名(確率型)
- RSA-PSS-R
- ECAO/ECAOS (離散対数問題に基づく。Abe-Okamoto署名とも呼ばれます。）

電子署名の安全性

上記で記載したように、電子署名には偽造不可である性質が求められることになります。

そして、その偽造に対する安全性の指標として、電子署名には適応的選択文書攻撃に対して存在的偽造不可である性質（EUF-CMA安全性） が求められます。

電子署名に対する攻撃は以下があります。下に行くほど攻撃者有利です。

直接攻撃（公開情報のみで攻撃）
既知文書攻撃（盗聴したメッセージを利用して攻撃）
一般文書攻撃（予め用意したメッセージとそれに対する署名値の情報を利用して攻撃）
適応的選択文書攻撃（任意のメッセージとそれに対する署名値を何度も取得して攻撃）

受ける被害は以下に分類されます。下に行くほど被害は少ない（攻撃は簡単）です。

完全解読（秘密鍵の情報が漏洩）
一般的偽造（任意のメッセージに対して署名偽造）
選択的偽造（特定の性質を持つメッセージ群に対して署名偽造）
存在的偽造（少なくとも一つ以上のメッセージに対して署名偽造）

このとき、攻撃者に最も有利な状況は「適応的選択文書攻撃」を行える環境で「存在的偽造」を達成する状態となります。

電子署名はこの攻撃者に最も有利な状況において一つの文書たりとも偽造を許さないことを目標とするためEUF-CMA安全性が求められます。

電子署名に対する疑問

上述したように、冒頭のような典型的な電子署名の説明については主にRSA署名をイメージして語られることが多いです。その際、特に初めて学んだ時などに感じるであろう電子署名に対する素朴な疑問について、記載してみたいと思います。（以下はRSA署名を前提として記載しています）

メッセージを単純に暗号化した結果を署名として利用できないのか

できません。

もし単純に送信したいメッセージをRSA秘密鍵で暗号化したものを署名として利用すると存在的偽造を許してしまいます。

RSA署名において検証時に行う処理は前述の通り下記となります。sは署名値、eは公開鍵、nは剰余です。(e,n)は公開情報のため誰でも利用可能です。

$m' = s^e \pmod n$

本来であれば署名値sは署名者が送信したいメッセージmに対して、$s = m^d \pmod n$ を計算して算出するものです。そのように計算するとm' = mとなり復号できます。

ただ、そのような計算をすっとばして、sを適当な値として設定してeとnを用いることで当然ながらm'を計算することができます。

このように適当なsから勝手に作った(m', s)のペアは、署名者が署名処理を行ったsでないのにもかかわらず検証処理を通過してしまいます。
（これはRSA暗号の暗号化処理と同一です。sを署名値だと偽って公開している状況です。）

このように作ったm'が意味のある文書になる可能性は低いものの、署名者が署名していない文書に対して署名できてしまう状態（存在的偽造）になるため、単純にRSA暗号化したデータを電子署名として利用することはできないことになります。

このような公開情報だけを用いて攻撃を行うことを直接攻撃といいます。

メッセージにハッシュ値を用いるのはなぜか

存在的偽造を防止するためです。

攻撃には直接攻撃、および積攻撃（メッセージ$m_1,m_2$の署名値の積からメッセージ$m_1・m_2$の署名値を計算する攻撃）などがあります。暗号化、復号化の計算処理の効率化の効果もあります。

メッセージにパディングを行うのはなぜか

ハッシュだけを施した場合、デスメット・オドリズコ攻撃(Desmedt and Odlyzko [1986]）による署名偽造を許してしまう可能性があるためです。

ちなみに、パディングを行うだけでも存在的偽造をある程度防止することができると考えられます。そのため、ハッシュを用いずにパディングだけを行う方式も検討されていましたが、ミザルスキー攻撃(Misarsky[1997])など複数の攻撃が提案されたため、パディングとハッシュを組み合わせる方式が取られるようになっています。

一覧

RSA署名、パディングあり、ハッシュ関数適用あり、パディングおよびハッシュ関数ありの安全性について整理します。

	方式	既知の攻撃	安全性	安全性の仮定	補足
RSA署名	単純RSA	直接攻撃（存在的偽造）、積攻撃（一般的偽造）	×	-
RSA署名＋パディング	単純パディング	De Jonge and Chaum攻撃、Girault-Misarsky攻撃	×	-
	ISO9796-3	Misarsky攻撃	×	-
RSA署名＋ハッシュ関数	単純ハッシュ	Desmedt and Odlyzko攻撃	×	-
	RSA-FDH		EUF-CMA	ランダムオラクル	実用性に問題あり
RSA署名＋パディング＋ハッシュ関数	ISO9796-2	Coron, Naccache, and Stern攻撃	×	-
	PKCS#1 v1.5		解読法は発見されていない	-
	RSA-PSS		EUF-CMA	ランダムオラクル	TLS1.3より利用可

RSA署名の注意事項

パディング、ハッシュ化はRSA暗号方式を電子署名に応用する際の偽造防止の観点で導入されていることがわかりました。

ただしRSA暗号自体が解読されてしまっては、元も子もないため、RSA署名を運用する際には、RSA暗号の強度についても確保しておく必要があります。

RSAの鍵長を1024bit以上にする

鍵長が短い場合、素因数分解に成功している例があります。

素数p,qを推測しにくいものにする

両方とも大きな素数を採用する
近い値をとらないようにする（フェルマー法対策）

公開情報eの値を適切に設定する

大きすぎても、小さすぎても攻撃手法が見つかっています
eは通常65537(0x10001)で固定となります

OpenSSLによる具体例

理論的な側面を確認してきましたので、実際にどのように電子署名がつくられるのかを確認します。最もよく利用されるツールの一つであるOpenSSLを使って確認したいと思います。

RSA暗号化用の秘密鍵パラメータを生成した結果は以下のようになります。

肝となるのは素数p、q（prime1、prime2）より生成する値n(modulus)となり、この素因数分解が困難であることがRSA暗号の安全性の根拠となっています。

鍵生成（秘密鍵、公開鍵）

$ openssl genrsa > private.key
$ openssl rsa -in private.key -pubout -out public.key

秘密鍵の確認

$ openssl rsa -text < private.key
RSA Private-Key: (2048 bit, 2 primes)
modulus:
    00:bf:d9:ce:76:f6:e1:50:8e:f7:85:ae:e5:fe:61:
    ....
publicExponent: 65537 (0x10001)
privateExponent:
    4c:de:a5:76:4f:37:3a:42:fe:74:66:fe:aa:6d:70:
    ....
prime1:
    00:e3:9e:0e:3c:97:2d:69:3e:0d:8b:ce:98:67:7b:
    ....
prime2:
    00:d7:c6:04:cb:1d:cc:d1:47:8d:4b:ac:7b:52:a6:
    ....
exponent1:
    00:8a:ce:72:64:24:d5:3e:9e:e6:e7:e1:5f:33:8c:
    ....
exponent2:
    00:b8:44:c3:93:32:bf:d7:79:e3:90:dc:9b:f4:d9:
    ....
coefficient:
    00:8d:f3:1e:c8:0e:f0:a1:1f:e2:4a:c5:d0:16:df:
    ....
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MIIEpQIBAAKCAQEAv9nOdvbhUI73ha7l/mH2Z/b1CpRSlfmKWi+i47d2a0z1rQON
.....
-----END RSA PRIVATE KEY-----

それぞれのパラメータの関係は下記となります。exponent1、exponent2、coefficientは秘密鍵による処理を式変換で簡単にした際に用いる計算用の数値となります。

modulus           : n = pq
publicExponent    : e = 65537
privateExponent   : d = e^(-1) mod (p-1)(q-1)
prime1            : p
prime2            : q
exponent1         : d mod (p-1)
exponent2         : d mod (q-1)
coefficient       : q^(-1) mod p

秘密鍵を使った署名は下記で行われます。PKCS#1 1.5のフォーマット形式になっていることがわかります。

署名

$ openssl dgst -sha1 -sign private.key hello.txt -out sig

署名結果の確認

$ openssl rsautl -verify -in sig -inkey private.key -raw -hexdu
mp

結果

「30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14」の部分がSHA1のOIDを示しています。
「f9 51 b1 01 98 9b 2c 3b 74 71 71 0b 4e 78 fc 4d bd fa 0c a6」はメッセージのSHA1値です。

0000 - 00 01 ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0010 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0020 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0030 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0040 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0050 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0060 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0070 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0080 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
0090 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
00a0 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
00b0 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
00c0 - ff ff ff ff ff ff ff ff-ff ff ff ff ff ff ff ff   ................
00d0 - ff ff ff ff ff ff ff ff-ff ff ff ff 00 30 21 30   .............0!0
00e0 - 09 06 05 2b 0e 03 02 1a-05 00 04 14 f9 51 b1 01   ...+.........Q..
00f0 - 98 9b 2c 3b 74 71 71 0b-4e 78 fc 4d bd fa 0c a6   ..,;tqq.Nx.M....

RSA-PSS方式もOpenSSLではサポートされています。バイナリでのデータ確認は難しいため省略しますが、コマンドとしては以下のようにすることで署名を作成できます。

$ openssl dgst -sha1 -sign private.key -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:-1 hello.txt > sig

量子コンピュータの台頭について (補足)

電子署名についてRSA署名を中心に方式について記載しましたが、これらの安全性は現在のコンピュータによる計算困難性を前提に理論が構築されています。

昨今、研究が加速している量子コンピュータが実用化されてしまうと、この前提が崩れてしまいます。（例えばRSA署名が拠り所にしている素因数分解については、量子コンピュータ上ではショアのアルゴリズムという解法が見つかっています）

そのため、NISTなどを中心に量子コンピュータでも解くことが難しい特性を持つ暗号方式（耐量子暗号）の標準化が進められており、主に「格子問題」を応用した数々の方式が提案され標準化プロセスが進められています。

CRYSTALS-Dilithium
FALCON

など

※いくつかのアルゴリズムはliboqsを使ってwolfSSLで利用できます

References

RFC8017 : PKCS #1: RSA Cryptography Specifications Version 2.2
RFC5758 : Internet X.509 Public Key Infrastructure: Additional Algorithms and Identifiers for DSA and ECDSA
RFC5754 : Using SHA2 Algorithms with Cryptographic Message Syntax
OpenSSL : objects.txt
RSA運用でやってはいけないnのこと