DSA
デジタル署名アルゴリズム Digital Signature Algorithm DSA / Digital Signature Standard (DSS) のひとつだった NIST SP 800-89
NIST SP 800-57
RFC 6979 曖昧な乱数を使用せず疑似乱数を使用する版 DSA, ECDSA RFC 3279 OID
RFC 2792 ?
ANSI X9.31 ?
ISO/IEC 9796-2
新しい署名では利用しないこと
検証用に残っている
H ハッシュアルゴリズム FIPS 180で承認されているもの SHA-1, SHA-2
鍵長 (L, N) (1024, 160), (2048, 224), (2048, 256), (3072, 256) bit 推奨 (FIPS 186-3)
L 512 から 1024 の 64 の 倍数 (旧式)、2048bit から 3072bitに拡張 (NIST 800-57)
N 160以上 ハッシュの出力長以下
ドメインパラメータ p, q, g, (domain_parameter_seed, counter) 公開っぽい
p 素数 $ 2^{L-1}<p<2^{L} ビット長 L (1024bit以上)
q 素数 p-1 の素因数的な $ 2^{N-1} < q < 2^{N}ビット長 N (160bit以上, ハッシュ出力以下)
g pと互いに素である自然数 GF(p)のでRSAのeとだいたい同じ? $ 1<g<p素数でなくてもいい?
x 秘密鍵 $ 0<x<q
y 公開鍵 $ y = g^x \bmod p
k 秘密番号 $ 0<k<q メッセージ毎に違う値でランダムにすること
Hash メッセージMのハッシュ値
(r, s) 署名
$ r = (g^k \bmod p) \bmod q
$ z = Hash(M) の 左Nbit
$ s = (k^{-1}(z+xr)) \bmod q
FIPS PUB 186-4 (旧規格 最新ではDSA削除)
デジタル署名標準 Digital Signature Standard (DSS)
4章と付録A
3. 一般的な議論 General Discussion
デジタル署名は、書面による署名の電子的な類似物です。デジタル署名を使用すると、署名者が情報に署名し
たことを保証できます。さらに、デジタル署名を使用して、署名後に情報が変更されたかどうかを検出する
(つまり、署名されたデータの完全性を検出する) こともできます。これらの保証は、データが送信で受信された
か、ストレージから取得されたかに関係なく取得できます。この規格の要件を満たす適切に実装されたデジタル
署名アルゴリズムは、これらのサービスを提供できます。
4 デジタル署名アルゴリズム The Digital Signature Algorithm (DSA)
4.1 DSA パラメータ
DSA デジタル署名は、一連のドメイン パラメーター、秘密鍵 x、メッセージごとの秘密番号 k、署名されるデータ、およびハッシュ関数を使用して計算されます。 デジタル署名は、同じドメイン パラメーター、デジタル署名の生成に使用された秘密鍵 x に数学的に関連付けられた公開鍵 y、検証対象のデータ、および署名の生成中に使用されたのと同じハッシュ関数を使用して検証されます。 これらのパラメータは次のように定義されます。
p 素数係数(prime modulus)。$ 2^{L–1} < p < 2^L、L は p のビット長です。 L の値はセクション 4.2 に記載されています。
q (p – 1) の素約数。ここで、$ 2^{N–1} < q < 2^N、N は q のビット長です。 N の値はセクション 4.2 に記載されています。
g GF(p) の乗法群内の次数 q の部分群の生成器 (1 < g < p)。
x 秘密にしておく必要がある秘密鍵。 x はランダムまたは擬似ランダムに生成された整数で、0 < x < q、つまり x の範囲は $ [ 1, q–1 ] になります。
y 公開鍵、ここで $ y = g^x \mod p
k 各メッセージに固有の秘密番号。 k はランダムまたは擬似ランダムに生成された整数で、0 < k < q になります。つまり、k の範囲は $ [1, q–1]になります
4.2 DSAパラメータサイズとハッシュ関数の選択
この規格では、LとNのペア(それぞれpとqのビット長)について次の選択肢を指定します。
L = 1024, N = 160
L = 2048, N = 224
L = 2048, N = 256
L = 3072, N = 256
連邦政府機関は、これらの選択肢の 1 つ以上を使用してデジタル署名を生成するもの(shall)とします。
FIPS 180 で指定されている承認済みのハッシュ関数は、デジタル署名の生成中に使用されます(shall)。 DSA デジタル署名プロセスに関連するセキュリティ強度は、(L, N) ペアのセキュリティ強度と使用されるハッシュ関数のセキュリティ強度の最小値を超えません。 使用するハッシュ関数のセキュリティ強度と (L, N) ペアのセキュリティ強度の両方が、デジタル署名プロセスに必要なセキュリティ強度以上である必要があります。 各 (L, N) ペアとハッシュ関数のセキュリティ強度は SP 800-57 で提供されます。
SP 800-57 は、デジタル署名の生成のための所定の期間における望ましいセキュリティ強度に応じた適切な (L, N) ペアの選択に関する情報を提供します。 署名された情報がその情報の予想される有効期間全体にわたって保護される (L, N) ペアが選択されます。 たとえば、5 年間保護する必要がある情報に対してデジタル署名が 2009 年に生成され、特定の (L, N) ペアが 2010 年以降無効になった場合、残っているより大きな (L, N) ペアが使用されます。 情報を保護する必要がある全期間有効です。
(L, N) ペアのセキュリティ強度とデジタル署名の生成に使用されるハッシュ関数のセキュリティ強度は、より強力なハッシュ関数を使用するという参加エンティティ間での合意がない限り、同じであることが推奨されます。 ハッシュ関数の出力の長さが N (つまり、q のビット長) より大きい場合、ハッシュ関数出力ブロックの左端の N ビットは、生成または生成中にハッシュ関数出力を使用する計算に使用されます。 デジタル署名の検証。 (L, N) ペアよりも低いセキュリティ強度を提供するハッシュ関数は、通常は使用しないでください。これは、デジタル署名プロセスのセキュリティ強度がハッシュ関数によって提供されるレベル以下に低下するためです。
認証局 (CA) 以外の連邦政府機関は、最初の 3 つの (L, N) ペア (つまり、(1024, 160)、(2048, 224)、および (2048, 256) ペア) のみを使用する必要があります。 CA は、その加入者が使用する (L, N) ペア以上の (L, N) ペアを使用する必要があります。 たとえば、加入者が (2048, 224) ペアを使用している場合、CA は (2048, 224)、(2048, 256)、または (3072, 256) ペアのいずれかを使用します。 この規則の例外として考えられるのは、CA 間の相互認証、デジタル署名以外の目的での鍵の認証、ある鍵のサイズやアルゴリズムから別の鍵のサイズやアルゴリズムへの移行などです。 詳細については、SP 800-57 を参照してください。
4.3 DSA ドメインパラメータ Domain Parameters
DSA では、デジタル署名の生成と検証に使用される秘密鍵と公開鍵のペアが、特定のドメイン パラメータのセットに関して生成されることが必要です。 これらのドメイン パラメータは、ユーザーのグループに共通であり、公開されている場合があります。 ドメイン パラメータのセットのユーザー (つまり、署名者と検証者の両方) は、それらを使用する前にその有効性を保証する必要があります (セクション 3 を参照)。 ドメインパラメータは公開情報である可能性がありますが、特定の鍵ペアとそのドメインパラメータのセットの間の正しい対応関係が、その鍵ペアを使用するすべての関係者に対して維持されるように管理されなければなりません。 ドメイン パラメータのセットは、長期間にわたって固定されたままになる場合があります。
DSA のドメイン パラメーターは整数 p、q、g であり、オプションで p と q の生成に使用されたdomain_parameter_seed と counter も指定できます (つまり、ドメイン パラメーターの完全なセットは (p, q, g {,domain_parameter_seed, counter}））。
4.3.1 ドメインパラメータの生成 Domain Parameter Generation
ドメイン パラメータは、信頼できる第三者 (CA などの TTP) または TTP 以外のエンティティによって生成される場合があります。 ドメインパラメータの有効性の保証は、鍵ペアの生成、デジタル署名の生成、またはデジタル署名の検証の前に取得されるものとします (セクション 3 を参照)。
整数 p および q は、付録 A.1 の指定に従って生成されます。 生成プロセスへの入力は、L と N の選択された値です (セクション 4.2 を参照)。 生成プロセスの出力は、p と q の値であり、オプションで、domain_parameter_seed と counter の値も得られます。
ジェネレータ g は、付録 A.2 の指定に従って生成されます。
ドメインパラメータの生成中に使用されるハッシュ関数のセキュリティ強度は、(L, N) ペアに関連付けられたセキュリティ強度以上である必要があります。 これは、デジタル署名プロセスに使用できるハッシュ関数よりも制限が厳しいことに注意してください (セクション 4.2 を参照)。
4.3.2 ドメインパラメータ管理 Domain Parameter Management
各デジタル署名鍵のペアは、(たとえば、公開鍵に関連付けられたドメイン パラメーターを識別する公開鍵証明書によって) ドメイン パラメーターの 1 つの特定のセットに正しく関連付けられるものとします。 ドメイン パラメータは、セットが非アクティブ化されるまで (セットが不要になった場合)、不正な変更から保護されます。 同じドメイン パラメータが複数の目的に使用される場合があります (たとえば、同じドメイン パラメータがデジタル署名と鍵の確立の両方に使用される場合があります)。 ただし、ジェネレータ g に異なる値を使用すると、ある目的で生成された鍵ペアが別の目的で誤って (成功して) 使用されるリスクが軽減されます。
4.4 鍵ペア Key Pairs
各署名者は、互いに数学的に関連する秘密鍵 x と公開鍵 y という鍵ペアを持っています。 秘密鍵は、デジタル署名が生成される一定の期間 (つまり、秘密鍵の暗号化期間) のみ使用されます。 関連する秘密鍵を使用して生成されたデジタル署名を検証する必要がある限り、公開鍵は使用し続けることができます (つまり、公開鍵は、関連する秘密鍵の暗号化期間を超えて使用され続けることができます)。 詳細については、SP 800-57 を参照してください。
4.4.1 DSA鍵ペアの生成
デジタル署名鍵のペア x および y は、一連のドメイン パラメーター (p、q、g {、domain_parameter_seed、counter}) に対して生成されます。 x と y の生成方法は付録 B.1 に記載されています。
4.4.2 鍵ペアの管理 Key Pair Management
鍵ペアの保護に関するガイダンスは SP 800-57 で提供されます。 デジタル署名の安全な使用は、次のようにエンティティのデジタル署名鍵 ペアの管理に依存します:
1. ドメインパラメータの有効性は、鍵ペアの生成、またはデジタル署名の検証と妥当性確認の前に保証されなければなりません (セクション 3 を参照)。
2. 各鍵ペアは、鍵ペアが生成されたドメイン パラメーターに関連付けられます。
3. 鍵ペアは、その鍵ペアに関連付けられたドメイン パラメーターを使用して署名を生成および検証するためにのみ使用されます。
4. 秘密鍵は、この標準で指定されている署名生成にのみ使用され、秘密に保たれます。 公開鍵は署名の検証にのみ使用され、公開される場合があります。
5. 意図された署名者は、デジタル署名を生成するために秘密鍵を使用する前またはそれと同時に、秘密鍵を所有していることを保証するものとします (セクション 3.1 を参照)。
6. 秘密鍵は、不正なアクセス、開示、変更から保護されなければなりません。
7. 公開鍵は、不正な変更（置換を含む）から保護されなければなりません。 たとえば、CA によって署名された公開鍵証明書は、そのような保護を提供する場合があります。
8. 検証者は、公開鍵、それに関連するドメインパラメータ、および鍵ペアの所有者間のバインディングを保証されます (セクション 3 を参照)。
9. 検証者は、信頼できる方法で（例：エンティティが信頼する CA によって署名された証明書から、またはエンティティが検証者によって信頼され、検証対象の署名情報のソースとして認証できる場合には、意図された署名者または主張された署名者から直接）公開鍵を取得するものとします。
10. 検証者は、主張された署名者が鍵ペアの所有者であり、その所有者が署名の生成時にデジタル署名の生成に使用された秘密鍵（つまり、デジタル署名の検証に使用される公開鍵に関連付けられた秘密鍵）を所有していることを保証されるものとします。 (セクション 3.3 を参照)。
11. 署名者と検証者は、公開鍵の有効性を保証する必要があります (セクション 3.1 および 3.3 を参照)。
4.5 DSAメッセージごとの秘密番号 DSA Per-Message Secret Number
新しい秘密乱数 k は、署名生成プロセス中に使用する各デジタル署名の生成に先立って生成されます。 この秘密番号は、不正な開示や変更から保護されます。
$ k^{-1} は、q を法とする乗算に関する k の逆乗です。 つまり、$ 0 < k^{-1} < q および $ 1 = ( k^{-1} k) \mod q です。 この逆は、署名生成プロセスに必要です (セクション 4.6 を参照)。 k から $ k^{-1} を導出する手法は付録 C.1 に記載されています。
$ k と $ k^{-1} は、署名されるメッセージの知識が計算に必要ないため、事前に計算することができます。 $ k と $ k^{-1} が事前に計算される場合、それらの機密性と完全性は保護されます。
メッセージごとの秘密番号の生成方法は、付録 B.2 に記載されています。
4.6 DSA署名生成
意図された署名者は、セクション 3.1 に規定されている保証を有するものとします。
Nをqのビット長とします。 min(N, outlen) が正の整数 N と outlen の最小値を表すものとします。ここで、outlen はハッシュ関数出力ブロックのビット長です。
メッセージ M の署名は、次の式に従って計算される数値 r と s のペアで構成されます:
$ r = (g^k \mod p) \mod q
$ z = Hash(M) の左端の min(N, output) bit
$ s = (k^{-1}(z +xr)) \mod q
s を計算するとき、Hash(M) から取得した文字列 z は整数に変換されます。 変換ルールは付録 C.2 に記載されています。
k、p、q、g が利用可能なときはいつでも r を計算できることに注意してください。たとえば、ドメインパラメータ p、q、g が既知で、k が事前に計算されているとき (セクション 4.5 を参照)、r も事前に計算される可能性があります。 r の計算には署名されるメッセージの知識は必要ないため、計算されます。 事前に計算された k、$ k^{-1}、および r 値は、s が計算されるまで秘密鍵 x と同じ方法で保護されます (SP 800-57 を参照)。
r と s の値は、r = 0 か s = 0 かを決定するためにチェックされます。r = 0 または s = 0 の場合、k の新しい値が生成され、署名が再計算されます。 署名が適切に生成された場合、r = 0 または s = 0 になる可能性は非常に低いです。
署名 (r, s) はメッセージとともに検証者に送信されます。
4.7 DSA署名検証と妥当性確認 DSA Signature Verification and Validation
署名検証は、署名者の公開鍵を使用して、どの当事者 (つまり、署名者、対象受信者、またはその他の当事者) によっても実行できます。 署名者は、署名されたメッセージを目的の受信者に送信する前に、計算された署名が正しいことを検証したい場合があります。 意図された受信者 (またはその他の当事者) は、署名を検証してその信頼性を判断します。
署名付きメッセージの署名を検証する前に、ドメインパラメータ、主張された署名者の公開鍵とアイデンティティが認証された方法で検証者に利用可能になるものとします。 公開鍵は、たとえば、信頼できるエンティティ (CA など) によって署名された証明書の形式で、または公開鍵の所有者との直接の会議で取得できます。
M '、r'、および s' を、それぞれ M、r、および s の受信バージョンとする。 y を主張された署名者の公開鍵とする。 N を q のビット長とします。 また、min(N, outlen) が正の整数 N と outlen の最小値を表すものとします。ここで、outlen はハッシュ関数出力ブロックのビット長です。
署名検証プロセスは次のとおりです:
1. 検証者は、0 < r' < q および 0 < s' < q であることを確認します。 いずれかの条件に違反した場合、署名は無効として拒否されます。
2. ステップ 1 の 2 つの条件が満たされる場合、検証者は以下を計算します。
$ w = (s')^{-1} \mod q
$ z = Hash(M')の左端のmin(N, outlen)bit
$ u1 = (zw) \mod q
$ u2 = ((r')w) \mod q
$ v = (((g)^{u1}(y)^{u2}) \mod p)\mod q
$ (s')^{-1} (つまり、s' mod q の逆数) を導出する手法は、付録 C.1 に記載されています。
Hash(M') から取得した文字列 z は整数に変換されます。 変換ルールは付録 C.2 に記載されています。
3. v = r' の場合、署名は検証されます。 M' = M、r' = r、および s' = s のとき v = r' であることの証明については、付録 E を参照してください。
4. v が r' と等しくない場合、メッセージまたは署名が変更された可能性があります。署名者の生成プロセスにエラーがあった可能性があります。または、詐欺師 (要求されたメッセージの公開鍵に関連付けられた秘密鍵を知らなかった人) がいた可能性があり 署名を偽造しようとした可能性があります。 署名は無効とみなされます。 データが有効かどうかについては推論できません。署名を検証するために公開キーを使用した場合、そのデータの署名が正しくないということのみがわかります。
5. 署名を有効なものとして受け入れる前に、検証者はセクション 3.3 で指定されている保証を得る必要があります。
組織のポリシーによって、無効なデジタル署名に対して取られる措置が規定される場合があります。 このようなポリシーは、この規格の範囲外です。 デジタル署名されたメッセージの適時性の判断に関するガイダンスは、SP 800-102、デジタル署名の適時性に関する推奨事項で取り上げられています。
付録 A: FFC ドメイン パラメータの生成と検証
有限体暗号 (FFC) は、有限体数学を使用して離散対数暗号を実装する方法です。 この規格で指定されている DSA は、FFC の一例です。 SP 800-56A で指定されている Diffie-Hellman および MQV キー確立アルゴリズムは、FFC として実装することもできます。
FFC のドメイン パラメーターは、値のセット (p、q、g {、domain_parameter_seed、counter}) で構成されます。 この付録では、FFC ドメイン パラメータ p、q、および g を生成し、明示的なドメイン パラメータ検証を実行するための手法を指定します。 生成プロセス中に、domain_parameter_seed と counter の値が取得されます。
A.1 FFC 素数 p および q の生成 Generation of the FFC Primes p and q
このセクションでは、セクション 4.1 および 4.2 で指定された基準を満たす素数 p および q を生成する方法を提供します。 これらの素数を生成する際には、これらの方法の 1 つが使用されます。 付録 A.1.1 では、ランダムな候補整数を生成し、確率的アルゴリズムを使用してそれらの素数をテストする方法が提供されています。 付録 A.1.2 では、構築された整数が素数であることが保証されるように、より小さい整数から整数を構築する 2 番目の方法が提供されています。
生成、検証、テストのプロセス中に、ビット文字列と整数の間の変換が必要になります。 付録 C.2 では、これらの変換のメソッドを提供します。
A.1.1 推定素数の生成と検証 Generation and Validation of Probable Primes
この規格の以前のバージョンには、SHA-1 および確率的手法を使用してドメイン パラメータ p および q を生成する方法が含まれていました。 このメソッドはドメイン パラメーターの生成として承認されなくなりました。 ただし、以前に生成されたドメインパラメータを検証するために、このメソッドの検証プロセスが付録 A.1.1.1 に提供されています。
確率的手法を使用した素数 p と q の生成と検証の方法は、付録 A.1.1.2 で提供されており、承認されたハッシュ関数の使用に基づいています。 このメソッドは、確率素数を生成するために使用されます。 このメソッドの検証プロセスは、付録 A.1.1.3 に記載されています。
確率的手法では、ハッシュ関数と任意のシード (domain_parameter_seed) を使用します。 任意のシードは、ユーザーのお気に入りの数値、または承認された乱数発生器によって出力される乱数または擬似乱数など、あらゆるものにすることができます。 domain_parameter_seed は、必要な間隔で p および q の候補のシーケンスを決定し、その後、確率的素数性テストを使用して素数性がテストされます (付録 C.3 を参照)。 このテストでは、候補が素数ではないか (つまり、合成整数である)、または「おそらく素数である」(つまり、合成整数が素数であると宣言される確率は非常に低い) であるかどうかが判断されます。 p と q は、素数性テストに合格した最初の候補セットとなります。 domain_parameter_seed は、同じ方法を使用して生成されるドメイン パラメータの一意のセットごとに一意である必要があることに注意してください。
A.1.1.1 この標準の以前のバージョンで指定されている SHA-1 を使用して生成された推定素数 p および q の検証 Validation of the Probable Primes p and q that were Generated Using SHA-1 as Specified in Prior Versions of this Standard
この素数検証アルゴリズムは、この標準の以前のバージョンで指定された素数生成アルゴリズムによって生成された素数 p および q を検証するために使用されます。 このアルゴリズムには、素数生成アルゴリズムから出力された p、q、domain_parameter_seed、および counter の値が必要です。
SHA1( ) を FIPS 180 で指定された SHA-1 ハッシュ関数とします。このメソッドの p と q を検証するには、次のプロセスまたは同等のプロセスを使用します。
入力:
1. p, q 生成された素数 pとq。
2. domain_parameter_seed p と q を生成するために使用されたシード。
3. counter 生成時に決定されたカウント値。
出力:
1. status 検証プロシージャから返されるステータス。ステータスは VALID または INVALID のいずれかです。
処理:
1. ( $ len(p) \ne 1024) または ($ len(q)\ne 160) の場合は、INVALID を返します。
1. If (len(p) ≠ 1024) or (len(p) ≠ 160), then return INVALID
2. If (counter > 4095), then return INVALID.
3. seedlen = len(domain_parameter_seed).
4. If (seedlen < 160), then return INVALID.
5. computed_q = SHA1(domain_parameter_seed) ⊕ SHA1((domain_parameter_seed + 1) mod $ 2^{seedlen}).
6. computed_q の最初と最後のビット (つまり、$ 159^{番目}と $ 0^{番目}のビット) を 1 に設定します。
7. 付録 C.3 で指定されているように、computed_q が素数であるかどうかをテストします。 (computed_q ≠ q) または (computed_q が素数ではない) 場合は、INVALID を返します。If (computed_q ≠ q) or (computed_q is not prime), then INVALID.
8. offset = 2.
9. For i = 0 to counter do
9.1 For j = 0 to 6 do
$ V_j = SHA1((domain_parameter_seed + offset + j) mod $ 2^{seedlen}).
9.2 $ W = V_0 + (V_1 * 2^{160})+(V_2 * 2^{320})+(V_3 * 2^{480})+(V_4 * 2^{640})+(V_5*2^{800})+((V_6 \mod 2^{63})*2^{960}).
9.3 $ X = W + 2^{1023}. Comment: $ 0 \leq W < 2^{L-1}.
9.4 $ c = X \mod 2q.
9.5 computed_p = $ X - ( c - 1 ). Comment: $ computed\_p \equiv 1 \pmod {2q}.
9.6 (computed_p < $ 2^{1023}) の場合は、ステップ 9.8 に進みます。 If ( computed_p < $ 2^{1023}), then go to step 9.8.
9.7 付録 C.3 で指定されているように、computed_p が素数であるかどうかをテストします。 computed_p が素数であると判断された場合は、ステップ 10 に進みます。
9.8 offset = offset + 7.
10. (($ i \ne counter) または (computed_p $ \ne p) または (computed_p が素数ではない)) の場合は、INVALID を返します。
10. If (( i $ \ne counter) or (computed_p $ \ne p) or (computed_p is not prime)), then return INVALID.
11. Return VALID.
A.1.1.2 承認されたハッシュ関数を使用した推定素数 p および q の生成 Generation of the Probable Primes p and q Using an Approval Hash Function
この方法は承認されたハッシュ関数を使用しており、あらゆるアプリケーション (デジタル署名や鍵の確立など) の素数 p および q の生成に使用できます。 ハッシュ関数のセキュリティ強度は、(L, N) ペアに関連付けられたセキュリティ強度以上である必要があります。
また、seedlen ビットの任意のdomain_parameter_seedも使用されます。ここで、seedlenはN以上でなければなりません。
生成プロセスでは、素数である可能性が非常に高い整数 p と q のセットが返されます。 別のエンティティが付録 A.1.1.3 の検証プロセスを使用して素数が正しく生成されたことを検証するには、domain_parameter_seed の値と素数の生成に使用されたカウンタも返され、検証エンティティが利用できるようにする必要があります。 domain_parameter_seed と counter を秘密にしておく必要はありません。 Hash() を選択したハッシュ関数とし、outlen を出力ブロックのビット長とし、outlen は N 以上であるものとします。
このメソッドの p と q を生成するには、次のプロセスまたは同等のプロセスが使用されます。
入力:
1. L 素数 p の希望の長さ (ビット単位)。
2. N 素数 q の希望の長さ (ビット単位)。
3. seedlen ドメインパラメータシードの必要な長さ。 seedlen は N 以上である必要があります。
出力:
1. status 生成プロシージャから返されるステータス。ステータスは VALID または INVALID のいずれかです。 INVALID がステータスとして返された場合、他の出力パラメータの値が返されないか、無効な値 (ゼロまたはヌル文字列など) が返されます。
2. p, q 生成された素数 p と q。
3. domain_parameter_seed (オプション) p および q の生成に使用されたシード。
4. counter (オプション) 生成中に決定されたカウント値。
処理:
1. (L, N) ペアが許容可能な (L, N ペア) のリストに含まれていることを確認します (セクション 4.2 を参照)。 ペアがリストにない場合は、INVALID を返します。
2. If (seedlen < N), then return INVALID.
3. $ n = \lceil L / outlen \rceil - 1 .
4. b = L - 1 - (n * outlen).
5. 任意のseedlenビットのシーケンスをdomain_parameter_seedとして取得します。
6. $ U = Hash $ (domain\_parameter\_seed) \mod 2^{N–1}.
7. $ q = 2^{N-1} + U + 1 - (U \mod 2).
8. 付録 C.3 で指定されているように、q が素数であるかどうかをテストします。
9. q が素数でない場合は、ステップ 5 に進みます。
10. offset = 1.
11. For counter = 0 to (4L - 1) do
11.1 For j = 0 to n do
$ V_j = Hash $ ((domain\_parameter\_seed + offset + j ) \mod 2^{seedlen}).
11.2 $ W = V_0+(V_1 * 2^{outlen})+\ldots+(V_{n-1}*2^{(n-1)*outlen})+((V_n \mod 2^b)*2^{n*outlen}).
11.3 $ X = W + 2^{L-1}. Comment: $ 0 \leq W < 2^{L-1}; したがって, $ 2^{L-1} \leq X < 2^L.
11.4 $ c = X \mod 2q.
11.5 $ p = X - (c-1). Comment: $ p \equiv 1 \pmod {2q}.
11.6 $ (p < 2^{L–1}) の場合は、ステップ 11.9 に進みます。If $ ( p < 2^{L-1}), then go to step 11.9.
11.7 付録 C.3 で指定されているように、p が素数であるかどうかをテストします。
11.8 p が素数であると判定された場合は、VALIDと、p、q の値、および (オプションで)domain_parameter_seed と counter の値を返します。
11.9 $ offset = offset+n+1. Comment: offset を増分します。 次に、ステップ 11 のループの一部として、カウンターをインクリメントします。 カウンタ < 4L の場合、ステップ 11.1 ～ 11.8 を繰り返します。
12. ステップ5に進みます。
A.1.1.3 承認されたハッシュ関数を使用して生成された推定素数 p および q の検証 Validation of the Probable Primes p and q that were Generated Using an Approved Hash Function
この素数検証アルゴリズムは、整数 p および q が付録 A.1.1.2 に示されている素数生成アルゴリズムによって生成されたことを検証するために使用されます。 検証アルゴリズムには、素数生成アルゴリズムから出力された p、q、domain_parameter_seed、および counter の値が必要です。 Hash() を p と q の生成に使用されるハッシュ関数とし、outlen をその出力ブロック長とします。
このメソッドの p と q を検証するには、次のプロセスまたは同等のプロセスを使用します。
入力:
1. p, q 生成された素数 p と q。
3. domain_parameter_seed p と q を生成するために使用されたドメイン パラメーター シード。
4. counter 生成時に決定されたカウント値。
出力:
1. status 検証手順から返されたステータス。ステータスは VALID または INVALID のいずれかです。
処理:
1. L = len(p).
2. N = len(q).
3. (L, N) ペアが許容可能な (L, N) ペアのリストに含まれていることを確認します (セクション 4.2 を参照)。 ペアがリストにない場合は、INVALID を返します。
4. If (counter > (4L - 1)), then return INVALID.
5. seedlen = len(domain_parameter_seed).
6. If (seedlen < N), then return INVALID.
7. U = Hash$ (domain\_parameter\_seed) \mod 2^{N-1}.
8. $ computed\_q = 2^{N-1} + U+1 - (U \mod 2).
9. 付録 C.3 で指定されているように、computed_q が素数であるかどうかをテストします。If ($ computed\_q \ne q) or (computed_q が素数ではない), then return INVALID.
10. $ n = \lceil L / outlen \rceil - 1.
11. $ b = L - 1 - (n*outlen).
12. offset = 1.
13. For i = 0 to counter do
13.1 For j = 0 to n do
$ V_j = Hash$ ((domain\_parameter\_seed+offset+j) \mod 2^{seedlen}).
13.2 $ W = V_0 + ( V_1 * 2^{outlen})+\ldots+(V_{n-1}*2^{(n-1)*outlen})+((V_n \mod 2^{b})*2^{n*outlen}).
13.3 $ X = W + 2^{L-1}.
13.4 $ c = X \mod 2q.
13.5 computed_p = X - ( c - 1).
13.6 If ($ computed\_p < 2^{L-1}), then ステップ13.9に進みます.
13.7 付録 C.3 で指定されているように、computed_p が素数であるかどうかをテストします。
13.8 computed_p が素数であると判断された場合は、ステップ 14 に進みます。
13.9 offset = offset + n + 1.
14. If $ ((i \ne counter) or (computed\_p \ne p) or (computed\_pが素数ではない)), then return INVALID.
15. Return VALID.
A.1.2 証明可能な素数 p および q の構築と検証 Construction and Validation of the Provable Primes p and q
素数は、素数であることが保証されるように生成できます。 p と q を生成する次のアルゴリズムは、承認されたハッシュ関数と任意のシード (firstseed) を使用して、必要な間隔で p と q を構築します。 ハッシュ関数のセキュリティ強度は、(L, N) ペアに関連付けられたセキュリティ強度以上である必要があります。
任意のシードは、ユーザーのお気に入りの数値、乱数発生器から出力される乱数または擬似乱数など、何でも構いません。 一意のドメイン パラメータのセットを生成するには、firstseed が一意である必要があることに注意してください。 候補素数は、候補が素数であるかどうかを証明する決定論的素数性テストを使用して素数性についてテストされます。 結果として得られる p と q は素数であることが保証されます。
A.1.2.1 Shawe-Taylor アルゴリズムを使用した素数 p および q の構築 Construction of the Primes p and q Using the Shawe-Taylor Algorithm
生成されたドメイン パラメータのセットごとに、少なくとも seedlen ビットの任意の初期シード (firstseed) が決定されます。ただし、seedlen ≧ N となります。
生成プロセスでは、素数であることが保証されている整数 p と q のセットが返されます。 別のエンティティが (付録 A.1.2.2 の検証プロセスを使用して) 素数が正しく生成されたことを検証するには、firstseed、2 つの計算されたシード (pseed および qseed)、および素数の生成に使用されたカウンター (pgen_counter) の値を使用します。 および qgen_counter) を検証エンティティが利用できるようにする必要があります。 シードとカウンターを秘密にしておく必要はありません。 DSA のドメイン パラメーターはセクション 4.3 で (p, q, g {,domain_parameter_seed, counter}) として識別されます。 Shawe-Taylor アルゴリズムを使用して p と q を生成する場合、domain_parameter_seed は 3 つのシード値 (firstseed、pseed、qseed) で構成され、カウンターはカウンター値のペア (pgen_counter と qgen_counter) で構成されます。
Hash( ) を選択したハッシュ関数 (付録 A.1.2 を参照) とし、outlen をそのハッシュ関数の出力ブロックのビット長とします。
A.1.2.1.1 最初のシードを入手する Get the First Seed
この構築的なメソッドのファーストシードを生成するには、次のプロセスまたは同等のプロセスを使用します。
入力:
1. N qのビット長
2. seedlen firstseed の長さ (seedlen ≥ N)
出力:
1. status 生成プロシージャから返されるステータス。ステータスは SUCCESS または FAILURE のいずれかです。 FAILURE が返された場合は、firstseed 値が提供されないか、無効な値が返されます。
2. firstseed 生成された最初のシード。
処理:
1. firstseed = 0.
2. N が許容可能な (L, N) ペアのリストに含まれていることを確認します (セクション 4.2 を参照)。 そうでない場合は、FAILURE を返します。
3. If ( seedlen < N ), then return FAILURE.
4. While $ firstseed < 2^{N-1}.
任意のseedlenビットのシーケンスをfirstseedとして取得します。
5. Return SUCCESS と firstseed の値.
注: このルーチンは、付録 A.1.2.1.2 の構成素数生成手順の最初に組み込むことができます。 ただし、付録 A.1.2.2 の検証プロセスでも構成素数生成手順を呼び出し、入力として firstseed の値を提供できるように、これはこの仕様では行われませんでした。
A.1.2.1.2 構築的な素数の生成 Constructive Prime Generation
この構築的な方法の p と q を生成するには、次のプロセスまたは同等のプロセスが使用されます。
入力:
1. L p の要求された長さ (ビット単位)。
2. N q の要求された長さ (ビット単位)。
3. firstseed 最初に使用されるシード。 これは、付録 A.1.2.1.1 に指定されているように取得されます。
出力:
1. status 生成プロシージャから返されるステータス。ステータスは SUCCESS または FAILURE のいずれかです。 FAILURE が返された場合は、他の値が返されないか、無効な値が返されます。
2. p, q 要求された素数。
3. pseed, qseed (オプション) p と q の生成に使用された計算されたシード値。 p と q を生成するシード全体は、firstseed、pseed、qseed で構成されます。
4. pgen_counter, qgen_counter (オプション) 生成中に決定されたカウント値。
処理:
1. (L, N) ペアが許容可能な (L, N) ペアのリストに含まれていることを確認します (セクション 4.2 を参照)。 ペアがリストにない場合は、FAILURE を返します。
コメント: ランダム素数を生成するには、付録 C.6 の Shawe-Taylor ランダム素数ルーチンを使用します。
2. N を長さとして、firstseed を input_seed として使用し、付録 C.6 のランダム素数生成ルーチンを使用して、q、qseed、および qgen_counter を取得します。 FAILURE が返された場合は、FAILURE を返します。
3. 長さとして$ \lceil L / 2 + 1\rceilを使用し、input_seed として qseed を使用し、付録 C.6 のランダム プライム ルーチンを使用して、 $ p_0 、 pseed 、および pgen_counter を取得します。 FAILURE が返された場合は、FAILURE を返します。
4. $ iterations = \lceil L+outlen \rceil-1.
5. old_counter = pgen_counter.
コメント: 区間 $ [ 2^{L−1}, 2^{L}] で (擬似) ランダム x を生成します。
6. x = 0.
7. For i = 0 to iterations do
x = x +(Hash$ (pseed + i) * 2^{i*outlen}) .
8. pseed = pseed + iterations + 1.
9. $ x = 2^{L-1} + (x \mod 2^{L-1}).
コメント: $ [2^{L−1}, 2^L] 区間で素数の候補 p を生成します。
10. $ t= \lceil x/(2qp_0) \rceil.
11. If $ (2tqp_0+1)>2^L , then $ t = \lceil 2^{L-1}/(2qp_0) \rceil .
12. $ p = 2tqp_0 + 1.
13. pgen_counter = pgen_counter + 1.
コメント: p の素数性をテストします。 区間 $ [2, p-2] 内の整数 a を選択します。
14. a = 0
15. For i = 0 to iterations do
$ a = a + ( Hash $ (pseed+i)*2^{i*outlen}).
16. pseed = pseed + iterations + 1.
17. a = 2 + ( a mod (p-3)).
18. $ z = a^{2tq} \mod p.
19. If (( 1 = GCD(z-1,p)) and ($ 1 = z^{p_0} \mod p)), then return SUCCESS と p, q と (オプションの) pseed, qseed, pgen_counter, qgen_counter の値を返します。
20. If (pgen_counter > (4L + old_counter)), then return FAILURE.
21. t = t + 1.
22. ステップ11に行く.
A.1.2.2 Shawe-Taylor アルゴリズムを使用して構築された DSA プライム p および q の検証 Validation of the DSA Primes p and q that were Constructed Using the Shawe-Taylor Algorithm
firstseed、pseed、qseed、pgen_counter、および qgen_counter の値が保存され、次のアルゴリズムで使用するために提供されている場合、付録 A.1.2.1.2 で説明されている方法によって生成された素数 p および q の検証を実行できます。
この構築的な方法の p と q を検証するには、次のプロセスまたは同等のプロセスを使用します。
入力:
1. p, q 検証済みの素数。
2. firstseed, pseed, qseed p と q の生成に使用されたシード値。
3. pgen_counter, qgen_counter 生成中に決定されたカウント値。
出力:
1. status 検証手順から返されるステータス。ステータスは SUCCESS または FAILURE のいずれかです。
処理:
1. L = len(p).
2. N = len(q).
3. (L, N) ペアが許容可能な (L, N) ペアのリストに含まれていることを確認します (セクション 4.2 を参照)。 ペアがリストにない場合は、FAILURE を返します。
4. If ($ firstseed < 2^{N-1}), then return FAILURE
5. If ($ 2^N \leq q), then return FAILURE,
6. If ($ 2^L \leq p), then return FAILURE.
7. If ($ (p-1) \mod q \neq 0), then return FAILURE.
8. L、N、および firstseed を使用して、付録 A.1.2.1.2 の構成素数生成手順を実行して、p_val, q_val, pseed_val, qseed_val, pgen_counter_val, および qgen_counter_val を取得します。 FAILURE が返された場合、または (q_val $ \neq q) または (qseed_val $ \neq qseed) または (qgen_counter_val $ \neq qgen_counter) または (p_val $ \neq p) または (pseed_val $ \neq pseed) または (pgen_counter_val $ \neq pgen_counter) の場合は、FAILURE を返します。
9. return SUCCESS.
A.2 ジェネレーターgの生成 Generation of the Generator g
ジェネレーター g は、p と q の値に依存します。 ジェネレーター g を決定する 2 つの方法が提供されています: これらの方法のいずれかを使用する必要があります。 付録 A.2.1 で説明されている最初の方法は、ジェネレーター g の完全な検証が必要ない場合に使用できます; この方法は、g を生成する当事者が別の生成器 g' と潜在的に悪用可能な関係を持つ g を意図的に生成しないと信頼できる場合にのみ使用することをお勧めします。 たとえば、x の既知の値に対して $ g = (g')^x \mod p となるような、ジェネレータ間の指数関係を決定するのは困難に違いありません。 (注: $ (g')^x を x のプライム g と読み替えてください。)
付録 A.2.2 は、付録 A.2.1 の生成方法が使用される場合の部分検証の方法を提供します。 付録 A.2.3 で説明されている g を生成する 2 番目の方法は、ジェネレーター g の検証が必要な場合に使用されます。 付録 A.2.3 の方法を使用して決定されたジェネレータの検証方法は、付録 A.2.4 で提供されます。
A.2.1 ジェネレーター g の検証できない生成 Unverifiable Generation of the Generator g
この方法は、p と q の値に基づいて g の値を決定するために使用されます。 ジェネレーター g の検証が必要ない場合に使用できます。 g の正しい生成を完全に検証することはできません (付録 A.2.2 を参照)。 g のこの生成方法は、この規格の以前のバージョンでも指定されていたことに注意してください。
このメソッドのジェネレータ g を生成するには、次のプロセスまたは同等のプロセスを使用します。
入力:
1. p, q 生成された素数。
出力:
1. g 要求された g の値。
処理:
1. e = (p - 1)/q.
2. h = 1 < h < ( p – 1) を満たす任意の整数を設定し、h が以前に試行された値と異なるようにします。 h は乱数発生器から、または使用するたびに変更されるカウンターから取得できることに注意してください。
3. $ g = h^e \mod p.
4. If ( g = 1 ), then ステップ2に進む.
5. Return g.
A.2.2 ジェネレータgの有効性の保証 Assurance of the Validity of the Generator g
付録 A.2.1 を使用して生成されたジェネレータ g の次数は、範囲と次数をチェックすることで部分的に検証でき、それによって g の部分検証を実行します。
ジェネレータ g の部分的な検証が必要な場合は、次のプロセスまたは同等のプロセスを使用します。
入力:
1. p, q, g ドメインパラメータ。
出力:
1. status 生成ルーチンから返されるステータス。ステータスは PARTIALLY VALID または INVALID のいずれかです。
処理:
1. 2 ≤ g ≤ (p–1) であることを確認します。 true でない場合は、INVALID を返します。
2. If ($ g^q = 1 \mod p), then return PARTIALLY VALID.
3. Return INVALID.
g と別の生成器 g' との潜在的に悪用可能な関係 (g を生成したエンティティには知られているが、他のエンティティには知られていない可能性がある) が存在しないことをチェックすることはできません。
この意味で、g の正しい生成を完全に検証することはできません。
A.2.3
A.2.4
B.1
B.1.1
B.1.2
B.2
B.2.1
B.2.2
B.3
C.1
C.2
C.3
C.6
RFC 6979 確定的(determinstic) DSA, ECDSA
乱数生成を間違わないように工夫したもの
$ g^j \bmod p
$ 0 \leqq j < q
2.3. 整数変換
qlen = Nっぽい pのビット長
rlen = ((qlen + 7) / 8) *8) 的なところ
blen = 入力シーケンス(Hash?)の長さ(bit)
2.3.2. Bit Stringを整数に変換
bits2int(Hash)
if ( qlen < blen )
qlen の左ビットを保持、後続ビットを破棄
else
qlen-blenを左に追加
整数値に変換する(フラグなし)
2.3.3. 整数からオクテットString変換
int2octets(integer)
rlen の文字列に変換
2.3.4. Bit String から オクテットString
z1 = bits2int(b)
z2 = z1 mod q
if ( z1 < 0 ) z2 = z1 - q
else z2 = z1
でいいのか?
int2octets(z2)
int2octetsはbits2intの逆ではない点に注意
int2octets は DSA, ECDSAでは使わない、deterministic (EC)DSAで使う
セキュリティ強度
鍵長とハッシュ関数の低い方、ハッシュ関数の強度は NIST SP 800-57
今後の利用は推奨されない