RSA-PSSアルゴリズムを一緒に学びましょう

[[400577]]

AS(5): RSA-PSSアルゴリズムの紹介

2018 年にリリースされた TLS v1.3 (TLS: Transport Layer Security、Transport Security Layer Protocol、TLS v1.3 は RFC 8446 に相当) では、サポートされているデジタル署名アルゴリズムは、RSASSA-PKCS1-v1_5、RSASSA-PSS、ECDSA (楕円曲線デジタル署名アルゴリズム)、EdDSA (エドワーズ曲線デジタル署名アルゴリズム) です。

これらのアルゴリズムはすでに標準（または事実上の標準）となっていますが、ある意味では、これらのアルゴリズムはアメリカの署名アルゴリズム学派を代表するものでもあります。

米国に加えて、ロシアは 1994 年にデジタル署名アルゴリズム標準 GOST R 34.10-94 を発行し、2001 年には楕円曲線デジタル署名アルゴリズム標準 GOST R34.10-2001 を発行しました。 GOST R34.10-2001 は 2012 年に GOST R34.10-2012 に更新されました。韓国は1998年に韓国の証明書ベースのデジタル署名アルゴリズムKCDSAとEC-KCDAを公開し、対応する標準は[88,89]で公開されました。ドイツは、2005 年にドイツの楕円曲線デジタル署名アルゴリズム標準 EC-GDSA をリリースしました。中国は、2012 年に SM2 楕円曲線デジタル署名アルゴリズム標準をリリースし、2016 年には SM9 ID 暗号化デジタル署名アルゴリズム標準をリリースしました。

重要な国際標準化組織として、ISO/IEC は、ISO/IEC 9796、ISO/IEC 14888、ISO/IEC 20008、ISO/IEC 18370、ISO/IEC 23264 などの一連のデジタル署名アルゴリズム標準もリリースしています。

水の川は三千あるが、私は一すくいだけ取る。記事のテーマと長さの関係で、この論文では RSASA-PSS アルゴリズムのみを紹介します。

PSS (Probabilistic Signature Scheme) は、秘密鍵署名の入力方法です。 RSASA (RSA 署名アルゴリズム) は現在、RSASSA-PKCS1-v1_5 と RSASSA-PSS の 2 つのアルゴリズムをサポートしています。セキュリティ上の理由により、RSASSA-PKCS1-v1_5 は現在互換性のためだけに使用されています (「おとぎ話はすべて嘘である」、「夢は批判され、散らされる」、「蜀への道は困難で、天に昇るよりも難しい」を参照)。現在の主流の推奨事項は、RSASSA-PSS アルゴリズムを使用することです。

PSS 方式は Bellare 氏と Rogaway 氏によって最初に提案されました。PSS は、この 2 人の偉人によって提案された OAEP (最適非対称暗号化パディング) と非常によく似ています (OAEP の詳細については、「蜀への道は困難、天に登るより困難」を参照してください)。

Mihir Bellare 氏は、カリフォルニア大学サンディエゴ校 (UCSD) のコンピューターサイエンスおよびエンジニアリング学部の教授です。ベラーレ氏は1986年にカリフォルニア工科大学で学士号を取得し、1991年にマサチューセッツ工科大学で博士号を取得した。 Bellare 氏は 1991 年から 1995 年まで IBM で研究者として勤務しました。Bellare 氏は HMAC、RSA-OAEP、RSA-PSS、OCB の共同開発者です。 Bellare 氏は ACM および IACR のフェローです。彼は、ACM Paris Kanellakis Theory and Practice Award、RSA Conference Award in Mathematics、David and Lucille Packard Foundation Fellowship in Science and Engineering、および NSF Career Award を受賞しています。

フィリップ・ロガウェイは、カリフォルニア大学デービス校 (UCD) のコンピュータサイエンス学部の教授です。ロガウェイ氏はカリフォルニア大学バークレー校 (UCB) で学士号を取得し、1991 年に MIT の計算理論グループに進み、博士号を取得しました。博士号を取得した後、ロガウェイ氏は IBM でセキュリティ アーキテクトとして働き、1994 年に UCD に入社しました。ロガウェイ氏は、レフチン賞 (2016 年)、PET 賞 (2015 年)、IACR フェロー (2012 年)、ACM パリ カネラキス賞 (2009 年)、RSA 数学賞 (2003 年) を受賞しています。

[[400578]]

図1 ベラーレ（左）とロガウェイ（右）

RSA デジタル署名アルゴリズム (RSASA) の本質は、図 2 に示すように、依然として RSA 暗号化/復号化アルゴリズムです。

図2 RSAデジタル署名アルゴリズムの概略図

図 2 からわかるように、RSSA は 2 つのステップに分かれています。

1) 署名するMをハッシュしてHを取得する

2) HをRSA秘密鍵で暗号化する

これは RSA 暗号化であるため、RSA の致命的な問題を回避する方法はありません。つまり、選択暗号文攻撃によって簡単に解読される可能性があるということです (詳細については、「おとぎ話はすべて嘘である」を参照してください)。これが RSA パディング アルゴリズムの誕生につながりました。

RSASSA-PKCS1-v1_5 は RSA_PKCS1_PADDING_v1_5 パディング アルゴリズムを使用しますが、RSASSA-PSS のパディング アルゴリズムは RSA_PKCS1_OAEP_PADDING パディング アルゴリズムに似ています。次に、RSASSA-PSS アルゴリズムを紹介します。

1. RSASSA-PSSパディングアルゴリズム

RSASSA-PSS アルゴリズムの本質は、図 3 に示すように、RSA アルゴリズムに基づいてパディング アルゴリズムを重ねることです (説明の便宜上、このパディング アルゴリズムは RSA-PSS パディング アルゴリズム、または RSA-PSS エンコーディングとも呼ばれます)。

図3 RSA-PSSデジタル署名アルゴリズムの概略図

図 3 では、RSASA-PSS アルゴリズムはハッシュの後、RSA の前に RSA-PSS パディング アルゴリズムを挿入します。 RSA-PSS の具体的なアルゴリズムを図 4 に示します。

図4: RSA-PSSパディングアルゴリズム

図 4 では、RSA-PSS パディング アルゴリズムが 4 つのステップに分かれています。以下では、これら 4 つのステップを個別に説明します。

1.1 MからM1

図4からわかるように、

M1 = p1 || mHash || ソルト

p1は8バイトの0です。

mHash = Hash(M)、ここで M は署名するメッセージであり、現在選択されているハッシュ アルゴリズムは SHA-1 です。 SHA-1の出力は20バイトなので、mHashの長さは

長さ = 20

ソルトは、長さ（sLenと表記）が通常hLenに等しい擬似乱数です。現在の選択肢は

sLen = hLen

1.2 DBの構築

DB（データブロック）の構築方法は以下の通りです。

DB = p2 || 塩

p2 の値は、0x00 のいくつかのバイトとそれに続く 0x01 の 1 バイトに等しくなります。これらのバイトはxLenとして記録され、xLenは次のようになります。

xLen = emLen - sLen - hLen - 2

ここで、eMLenは図4のEMの長さである。

salt の値は、セクション 1.1 で説明した salt の値と同じです。特に強調したいのは、両者が等しくなければならないということであり、そうでない場合はデジタル署名を検証できない（詳細については、以下のセクション3「RSASSA-PSSのデジタル署名検証」を参照）。

1.3 MGF

MGF（マスク生成関数）の紹介については、「蜀への道は難し、天に登るより難しい」を参照してください。ここでは繰り返しません。また、RSA-PSS で使用される MGF 関数の出力も MGF1 です。

図4では、MGFに対応する入力と出力は

マスク = MGF1(mgfSeed、マスク長、ハッシュ)

で、

mgfSeed = Hash(M1)、ハッシュ関数はSHA-1

マスク長さ = emLen - hLen - 1

ハッシュ関数はSHA-1を選択

1.4 EMの構築

EM（エンコードされたメッセージ）の値は、

EM = マスクDB || H || bc

で、

maskedDB = DB xorマスク

H = ハッシュ(M1)

bc = 0xBC

このうち、bcの長さは1バイト、Hの長さはhLen、maskedDBの長さ（mdbLenと呼ぶ）は

mdbLen = emLen - hLen - 1

このうち、eMLenの長さはEMの長さとなります。 EM は次に RSA で暗号化されるため、EM の長さは RSA の要件を満たすだけで済みます。

2. RSASA-PSS署名アルゴリズム

RSA-PSS パディング後、次の署名アルゴリズムは比較的単純になります。

EM = RSA-PSS(M)

S = RSAEP(EM)

RSA アルゴリズムについては、「RSA 基本アルゴリズム」および「RSA 計算方法」を参照してください。ここでは繰り返しません。

3. RSASA-PSSの署名検証

RSASA-PSS 署名検証は次の手順に分かれています。

3.1 復号化

RSASA-PSS の署名検証は復号化から始まります。

EM = RSADP(S)

つまり、署名 S を取得した後、RSA 復号化アルゴリズムを実行して復号化された情報 EM を取得します。

3.2 セグメンテーションEM

EM を取得した後、次のステップはセグメンテーションと検証です。

マスクDB、H、bc = 分割(EM)

右端のバイトは bc で、bc から左側の hLen バイトは H、残りは maskedDB です。

右端のバイトが 0xBC でない場合、署名の検証は停止します (デジタル署名は不正です)。

3.3 塩分の計算

H を取得したら、マスクを計算できます。

マスク = MGF1(H, マスク長, ハッシュ)

なぜなら、

maskedDB = DB xorマスク

それで、

DB = マスクされたDB xorマスク

DBを取得したら、それを分割することができます

p2、ソルト = 分割(DB)

このうち、salt は DB の右端の sLen バイトであり、残りは p2 です。

p2 の値が、0x00 のいくつかのバイトとそれに続く 0x01 の 1 バイトと等しくない場合、検証は停止します (デジタル署名は不正です)。

3.4 ハッシュ検証

Mを受信して​​ハッシュを計算する

mハッシュ = ハッシュ(M)

次にM1を構築する

M1 = p1 || mHash || ソルト

このうち、塩はステップ3.3で計算された塩である。

次に、M1のハッシュを計算します。

H1 = ハッシュ(M1)

H1 と H を比較します。等しい場合、署名検証は成功です。等しくない場合、署名は不正です。

このうち、Hはステップ3.2で取得したハッシュ値です。

上記の 4 つの手順を実行すると、RSASA-PSS のデジタル署名検証が完了します。