※一部、英文及び仏文を自動翻訳した日本語訳を使用しています。
序文
ISO (国際標準化機構) と IEC (国際電気標準会議) は、世界標準化のための専門システムを形成しています。 ISO または IEC のメンバーである国家機関は、技術活動の特定の分野を扱うために、それぞれの組織によって設立された技術委員会を通じて、国際規格の開発に参加しています。 ISO と IEC の技術委員会は、相互に関心のある分野で協力しています。 ISO および IEC と連携して、政府および非政府の他の国際機関もこの作業に参加しています。
この文書の開発に使用された手順と、今後の維持のために意図された手順は、ISO/IEC 指令で説明されています。 1. 特に、さまざまなタイプの文書に必要なさまざまな承認基準に注意する必要があります。この文書は、ISO/IEC 指令の編集規則に従って作成されました。 2 ( www.iso.org/directives を参照)
このドキュメントの要素の一部が特許権の対象となる可能性があることに注意してください。 ISO および IEC は、そのような特許権の一部またはすべてを特定する責任を負わないものとします。ドキュメントの開発中に特定された特許権の詳細は、序論および/または受信した特許宣言の ISO リスト ( www.iso.org/patents を参照) または受信した特許宣言の IEC リスト ( http://patents.iec.ch )
このドキュメントで使用されている商号は、ユーザーの便宜のために提供された情報であり、保証を構成するものではありません。
規格の自発的な性質の説明、適合性評価に関連する ISO 固有の用語と表現の意味、および技術的貿易障壁 (TBT) における世界貿易機関 (WTO) の原則への ISO の準拠に関する情報については、以下を参照してください。 www.iso.org/iso/foreword.html .
この文書は、合同技術委員会 ISO/IEC JTC 1, 情報技術、小委員会 SC 27, 情報セキュリティ、サイバーセキュリティおよびプライバシー保護によって作成されました。
この第 2 版は、技術的に改訂された第 1 版 (ISO/IEC 18032:2005) を取り消して置き換えるものです。
前作からの主な変更点は以下の通り。
- 6.2 の Frobenius-Grantham 素数性検定、6.3 の Lehmann 素数性検定、および 8.3.1 の Maurer のアルゴリズムは削除されました。
- –楕円曲線素数性証明アルゴリズム、Shawe-Taylor アルゴリズム、副条件付き素数生成アルゴリズムが追加または大幅に改訂されました。
1 スコープ
このドキュメントでは、暗号化プロトコルとアルゴリズムで必要とされる素数の生成とテストの方法を指定します。
まず、このドキュメントでは、特定の数値が素数であるかどうかをテストする方法を指定します。このドキュメントに含まれるテスト方法は、次の 2 つのグループに分けられます。
- エラー確率が小さい確率的素数性テスト。ここで説明するすべての確率的テストは、コンポジットを素数として宣言できます。
- 正しい評決を与えることが保証されている決定論的方法。これらの方法では、いわゆるプライマリ証明書が使用されます。
次に、このドキュメントでは素数を生成する方法を指定します。ここでも、確率論的方法と決定論的方法の両方が示されています。
注記アルゴリズム理論のバックグラウンドを持つ読者は、確率論的および決定論的アルゴリズムにすでに遭遇している可能性があります。このドキュメントの決定論的な方法は、内部的にはランダム ビット (ISO/IEC 18031 で説明されている方法で生成される) を使用しており、「決定論的」とは、出力が確率 1 で正しいという事実のみを指します。
附属書 A は、Miller-Rabin 素数性検定で利用されるエラー確率を提供します。
附属書 B では、特定の暗号要件を満たすことができるように素数を生成する方法のバリエーションについて説明します。
附属書 C では、素数の生成および検証方法で使用されるプリミティブを定義しています。
2 参考文献
以下のドキュメントは、その内容の一部またはすべてがこのドキュメントの要件を構成するように、本文で参照されています。日付のある参考文献については、引用された版のみが適用されます。日付のない参照については、参照文書の最新版 (修正を含む) が適用されます。
- ISO/IEC 18031, 情報技術 - セキュリティ技術 - ランダム ビット生成
3 用語と定義
このドキュメントでは、次の用語と定義が適用されます。
ISO および IEC は、次のアドレスで標準化に使用する用語データベースを維持しています。
3.1
合成数
複合
自明な 約数ではない約数が存在する整数 (3.8)
3.2
決定論的ランダム ビット ジェネレーター
DRBG
決定論的アルゴリズムをシードと呼ばれる適切にランダムな初期値に適用することにより、ランダムに見えるビット シーケンスを生成するランダム ビット ジェネレーター、および場合によっては、ランダム ビット ジェネレーターのセキュリティが依存しないセカンダリ入力
3.3
エントロピ
閉鎖系における無秩序、ランダム性または変動性の尺度
[出典: ISO/IEC 18031:2011, 3.11]
3.4
ヤコビ記号
奇数nに関する正の整数aのヤコビ記号
多重度 (3.5) を含むnの素因数に関するaのルジャンドル記号の積
注記素因数pがnの因数分解において多重度m ≥ 1 で発生する場合， pに関するaのルジャンドル記号は， nに関するaのヤコビ記号を生成する積において多重度mで発生する.
a(p− 1)/2 mod p
3.5
多重度
nの素因数pの多重度
nをp eで割った最大の正の整数e
3.6
素数証明書
与えられた整数が実際に素数であることの数学的証明
注記1:小さい整数の場合、素数性は試行分割によって最も効率的に証明されます。したがって、この場合、素性証明書は空である可能性があります。
3.7
素数
素数
自明な 約数のみが存在する正の整数 (3.8)
3.8
自明な約数
非ゼロ整数Nの自明な約数
1, -1, N 、および – N
注記1:任意の非ゼロ整数Nは、(少なくとも) 1, -1, N 、および – Nで割り切れます。
参考文献
| [1] | ANSI X9.80-2010, 素数生成、素数テスト、および素数証明書。 |
| [2] | Atkin AOL, Morain F.、楕円曲線と素数性の証明。計算の数学 61, 1993, pp. 29-68 |
| [3] | ベイリー・ロバート、ワグスタッフ・サミュエル・S, ジュニア・ルーカス・シュードプライム。計算の数学 35, 1980, pp 1391-141 |
| [4] | Blake Ian F, Seroussie Gadiel, Smart Nigel P, 暗号化における楕円曲線、第 3 刷、Cambridge University Press, 2000 年 |
| [5] | Brandt J, Damgård I インクリメンタルサーチによる可能性のある素数の生成について。 Proceedings CRYPTO 92, LNCS 740, Springer, 1993 年、pp. 358-370 |
| [6] | ジョン・ブリルハート DH, レーマー、JL セルフリッジ。新しい素数基準と2 m ±1の因数分解。計算の数学 29(130) 1975, pp. 620-647 |
| [7] | 銅細工人ドンa二変量整数方程式a小さな根を見つける;既知の上位ビットによる因数分解。暗号化の進歩 - EUROCRYPT 1996, pp 178-18 |
| [8] | ISO/IEC 15946-1, 情報技術 - セキュリティ技術 - 楕円曲線に基づく暗号技術 - Part1: 一般 |
| [9] | Damgård Ivan, Landrock Peter, Pomerance Carl 、強確率プライムテストの平均ケースエラー推定値。計算の数学 61(203), 1993, pp. 177-194 |
| [10] | NIST, デジタル署名標準( DSS )、連邦情報処理標準公開 186-4, 2013 年 7 月。 |
| [11] | Elkies ND, 有限体上の楕円曲線およびモジュラー曲線、および関連する計算上の問題。 Computational Perspectives on Number Theory, volume 7 of AMS/IP Stud. Adv. Math. Amer.社会、プロビデンス、ロードアイランド州、1998 年。 |
| [12] | Lenstra HW, 剰余クラスの除数。計算の数学42 (165), 1984, pp. 331-340. |
| [13] | Marcus Daniel, NumberFields 、第 3 刷、Springer-Verlag, 1995 年。 |
| [14] | Nemec M, Sys M, Svenda P, Klinec D, Matyas Vコッパースミスの攻撃の復活:広く使用されているRSA係数の実用的な因数分解. 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp 1631-1648 の議事録。 |
| [15] | ポメランス・カール、ベイリーの反例toありますか–PSWプライマリティテスト? 1984年 |
| [16] | Schoof Rene, 有限フィールド上の楕円曲線上の点を数えます。 J理論。 Nombres Bourdeaux, 7:219-254, 1995 年。 |
| [17] | Stinson Douglas R.、 Cryptography 、 TheoryandPractice 、第 2 版、Chapman & Hall/CRC, 2002 年 |
| [18] | Shawe-Taylor J.、強い素数の生成。エレクトロニクス レターズ (22) 16, 1986 年、875 ～ 877 ページ |
| [19] | Washington L., Elliptic Curves: Number Theory and Cryptography, CRC Press, 2003, 2nd ed. 2008. |
Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical Commission) form the specialized system for worldwide standardization. National bodies that are members of ISO or IEC participate in the development of International Standards through technical committees established by the respective organization to deal with particular fields of technical activity. ISO and IEC technical committees collaborate in fields of mutual interest. Other international organizations, governmental and non-governmental, in liaison with ISO and IEC, also take part in the work.
The procedures used to develop this document and those intended for its further maintenance are described in the ISO/IEC Directives, 1. In particular, the different approval criteria needed for the different types of document should be noted. This document was drafted in accordance with the editorial rules of the ISO/IEC Directives, 2 (see www.iso.org/directives ).
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights. Details of any patent rights identified during the development of the document will be in the Introduction and/or on the ISO list of patent declarations received (see www.iso.org/patents ) or the IEC list of patent declarations received (see http://patents.iec.ch ).
Any trade name used in this document is information given for the convenience of users and does not constitute an endorsement.
For an explanation of the voluntary nature of standards, the meaning of ISO specific terms and expressions related to conformity assessment, as well as information about ISO's adherence to the World Trade Organization (WTO) principles in the Technical Barriers to Trade (TBT), see www.iso.org/iso/foreword.html .
This document was prepared by Joint Technical Committee ISO/IEC JTC 1, Informationtechnology, Subcommittee SC 27, Informationsecurity, cybersecurityandprivacyprotection.
This second edition cancels and replaces the first edition (ISO/IEC 18032:2005), which has been technically revised.
The main changes compared to the previous edition are as follows:
- the Frobenius-Grantham primality test in 6.2, the Lehmann primality test in 6.3 and Maurer’s algorithm in 8.3.1, have been removed;
- – the Elliptic curve primality proving algorithm, The Shawe-Taylor algorithm and the algorithm to generate primes with side conditions, have been added or substantially revised.
1 Scope
This document specifies methods for generating and testing prime numbers as required in cryptographic protocols and algorithms.
Firstly, this document specifies methods for testing whether a given number is prime. The testing methods included in this document are divided into two groups:
- probabilistic primality tests, which have a small error probability. All probabilistic tests described here can declare a composite to be a prime;
- deterministic methods, which are guaranteed to give the right verdict. These methods use so-called primality certificates.
Secondly, this document specifies methods to generate prime numbers. Again, both probabilistic and deterministic methods are presented.
NOTE It is possible that readers with a background in algorithm theory have already had previous encounters with probabilistic and deterministic algorithms. The deterministic methods in this document internally still make use of random bits (to be generated via methods described in ISO/IEC 18031), and “deterministic” only refers to the fact that the output is correct with probability one.
Annex A provides error probabilities that are utilized by the Miller-Rabin primality test.
Annex B describes variants of the methods for generating primes so that particular cryptographic requirements can be met.
Annex C defines primitives utilized by the prime generation and verification methods.
2 Normative references
The following documents are referred to in the text in such a way that some or all of their content constitutes requirements of this document. For dated references, only the edition cited applies. For undated references, the latest edition of the referenced document (including any amendments) applies.
- ISO/IEC 18031, Informationtechnology—Securitytechniques—Randombitgeneration
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
ISO and IEC maintain terminological databases for use in standardization at the following addresses:
3.1
composite number
composite
integer for which divisors exist that are not trivial divisors (3.8)
3.2
deterministic random bit generator
DRBG
random bit generator that produces a random-appearing sequence of bits by applying a deterministic algorithm to a suitably random initial value called a seed and, possibly, some secondary inputs on which the security of the random bit generator does not depend
3.3
entropy
measure of the disorder, randomness or variability in a closed system
[SOURCE: ISO/IEC 18031:2011, 3.11]
3.4
Jacobi symbol
Jacobi symbol of a positive integer a with respect to an odd integer n
product of the Legendre symbols of a with respect to the prime factors of n, including multiplicity (3.5)
Note 1 to entry: If the prime factor p occurs with multiplicity m ≥ 1 in the factorization of n, then the Legendre symbol of a with respect to p occurs with multiplicity m in the product that yields the Jacobi symbol of a with respect to n.
a(p- 1)/2 mod p
3.5
multiplicity
multiplicity of a prime divisor p of n
largest positive integer e with pe dividing n
3.6
primality certificate
mathematical proof that a given integer is indeed a prime
Note 1 to entry: For a small integer, primality is most efficiently proven by trial division. In this case, the primality certificate can therefore be empty.
3.7
prime number
prime
positive integer for which there exist only trivial divisors (3.8)
3.8
trivial divisors
trivial divisors of a nonzero integer N
1, -1, N and –N
Note 1 to entry: Any nonzero integer N is divisible by (at least) 1, -1, N and –N.
Bibliography
| [1] | ANSI X9.80-2010, Primenumbergeneration, primalitytesting, andprimalitycertificates. |
| [2] | Atkin A.O.L., Morain F., Ellipticcurvesandprimalityproving. Mathematics of Computation 61, 1993, pp. 29-68 |
| [3] | Baillie Robert, Wagstaff Samuel S.,Jr LucasPsuedoprimes. Mathematics of Computation 35, 1980, pp 1391-1417. |
| [4] | Blake Ian F., Seroussie Gadiel, Smart Nigel P., Ellipticcurvesincryptography, third printing, Cambridge University Press, 2000 |
| [5] | Brandt J., Damgård I., Ongenerationofprobableprimesbyincrementalsearch. Proceedings CRYPTO 92, LNCS 740, Springer, 1993, pp. 358-370 |
| [6] | John Brillhart D. H., Lehmer, J. L. Selfridge. NewPrimalityCriteriaandFactorizationsof 2 m ±1. Mathematics of Computation 29(130) 1975, pp. 620-647 |
| [7] | Coppersmith Don, FindingaSmallRootofaBivariateIntegerEquation;Factoringwithhighbitsknown. Advances in Cryptography – EUROCRYPT 1996, pp 178-189. |
| [8] | ISO/IEC 15946-1, Informationtechnology—Securitytechniques—Cryptographictechniquesbasedonellipticcurves—Part 1:General |
| [9] | Damgård Ivan, Landrock Peter, Pomerance Carl, Averagecaseerrorestimatesforthestrongprobableprimetest. Mathematics of Computations 61(203), 1993, pp. 177-194 |
| [10] | NIST, DigitalSignatureStandard (DSS), Federal Information Processing Standards Publication 186-4, July 2013. |
| [11] | Elkies N.D., Ellipticandmodularcurvesoverfinitefieldsandrelatedcomputationalissues. Computational Perspectives on Number Theory, volume 7 of AMS/IP Stud. Adv. Math. Amer. Soc., Providence, RI, 1998. |
| [12] | Lenstra H. W., Divisors in Residue Classes. MathematicsofComputation 42 (165), 1984, pp. 331-340. |
| [13] | Marcus Daniel, NumberFields, third printing, Springer-Verlag, 1995. |
| [14] | Nemec M., Sys M., Svenda P., Klinec D., Matyas V., TheReturnofCoppersmith’sAttack:PracticalFactorizationofWidelyUsedRSAModuli. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp 1631-1648. |
| [15] | Pomerance Carl, ArethereCounter-examplestotheBaillie–PSWPrimalitytest? 1984 |
| [16] | Schoof Rene, Countingpointsonellipticcurvesoverfinitefields. J. Theory. Nombres Bourdeaux, 7:219-254, 1995. |
| [17] | Stinson Douglas R., Cryptography, TheoryandPractice, 2nd edition, Chapman & Hall/CRC, 2002 |
| [18] | Shawe-Taylor J., Generatingstrongprimes. Electronics Letters (22) 16, 1986, pp. 875-877 |
| [19] | Washington L., Elliptic Curves: Number Theory and Cryptography, CRC Press, 2003, 2nd ed. 2008. |