🔐

電子署名まとめ

2022/12/04に公開

network

概要

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

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

以下のようなことを実現できます。(Menezes et al.[1997]）

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

署名者の信頼性は担保できません。

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

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

電子署名の利用用途

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

代表的な方式

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

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

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

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

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署名とも呼ばれます。）

電子署名に対する疑問

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

できません。

もし単純に送信したいメッセージを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'が意味のある文書になる可能性は低いものの、署名者が署名していない文書に対して署名できてしまう状態（存在的偽造）になるため電子署名として利用することはできないことになります。

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

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

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

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

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

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

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

電子署名の安全性

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

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

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

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

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

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

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

一覧

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の鍵長を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 dgst -sha1 -sign private.key -sigopt rsa_padding_mode:pss -sigopt rsa_pss_saltlen:-1 hello.txt > sig

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のこと