| 1 |
<pre>Independent Submission M. Lochter |
| 2 |
Request for Comments: 5639 BSI |
| 3 |
Category: Informational J. Merkle |
| 4 |
ISSN: 2070-1721 secunet Security Networks |
| 5 |
March 2010 |
| 6 |
|
| 7 |
|
| 8 |
<span class="h1">Elliptic Curve Cryptography (ECC) Brainpool Standard</span> |
| 9 |
<span class="h1">Curves and Curve Generation</span> |
| 10 |
|
| 11 |
Abstract |
| 12 |
|
| 13 |
This memo proposes several elliptic curve domain parameters over |
| 14 |
finite prime fields for use in cryptographic applications. The |
| 15 |
domain parameters are consistent with the relevant international |
| 16 |
standards, and can be used in X.509 certificates and certificate |
| 17 |
revocation lists (CRLs), for Internet Key Exchange (IKE), Transport |
| 18 |
Layer Security (TLS), XML signatures, and all applications or |
| 19 |
protocols based on the cryptographic message syntax (CMS). |
| 20 |
|
| 21 |
Status of This Memo |
| 22 |
|
| 23 |
This document is not an Internet Standards Track specification; it is |
| 24 |
published for informational purposes. |
| 25 |
|
| 26 |
This is a contribution to the RFC Series, independently of any other |
| 27 |
RFC stream. The RFC Editor has chosen to publish this document at |
| 28 |
its discretion and makes no statement about its value for |
| 29 |
implementation or deployment. Documents approved for publication by |
| 30 |
the RFC Editor are not a candidate for any level of Internet |
| 31 |
Standard; see <a href="./rfc5741#section-2">Section 2 of RFC 5741</a>. |
| 32 |
|
| 33 |
Information about the current status of this document, any errata, |
| 34 |
and how to provide feedback on it may be obtained at |
| 35 |
<a href="http://www.rfc-editor.org/info/rfc5639">http://www.rfc-editor.org/info/rfc5639</a>. |
| 36 |
|
| 37 |
Copyright Notice |
| 38 |
|
| 39 |
Copyright (c) 2010 IETF Trust and the persons identified as the |
| 40 |
document authors. All rights reserved. |
| 41 |
|
| 42 |
This document is subject to <a href="https://www.rfc-editor.org/bcp/bcp78">BCP 78</a> and the IETF Trust's Legal |
| 43 |
Provisions Relating to IETF Documents |
| 44 |
(<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of |
| 45 |
publication of this document. Please review these documents |
| 46 |
carefully, as they describe your rights and restrictions with respect |
| 47 |
to this document. |
| 48 |
|
| 49 |
|
| 50 |
|
| 51 |
|
| 52 |
<span class="grey">Lochter & Merkle Informational [Page 1]</span></pre> |
| 53 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span> |
| 54 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 55 |
|
| 56 |
|
| 57 |
Table of Contents |
| 58 |
|
| 59 |
<a href="#section-1">1</a>. Introduction ....................................................<a href="#page-3">3</a> |
| 60 |
<a href="#section-1.1">1.1</a>. Scope and Relation to Other Specifications .................<a href="#page-4">4</a> |
| 61 |
<a href="#section-1.2">1.2</a>. Requirements Language ......................................<a href="#page-4">4</a> |
| 62 |
<a href="#section-2">2</a>. Requirements on the Elliptic Curve Domain Parameters ............<a href="#page-4">4</a> |
| 63 |
<a href="#section-2.1">2.1</a>. Security Requirements ......................................<a href="#page-5">5</a> |
| 64 |
<a href="#section-2.2">2.2</a>. Technical Requirements .....................................<a href="#page-6">6</a> |
| 65 |
<a href="#section-3">3</a>. Domain Parameter Specification ..................................<a href="#page-8">8</a> |
| 66 |
<a href="#section-3.1">3.1</a>. Domain Parameters for 160-Bit Curves .......................<a href="#page-8">8</a> |
| 67 |
<a href="#section-3.2">3.2</a>. Domain Parameters for 192-Bit Curves .......................<a href="#page-9">9</a> |
| 68 |
<a href="#section-3.3">3.3</a>. Domain Parameters for 224-Bit Curves ......................<a href="#page-10">10</a> |
| 69 |
<a href="#section-3.4">3.4</a>. Domain Parameters for 256-Bit Curves ......................<a href="#page-11">11</a> |
| 70 |
<a href="#section-3.5">3.5</a>. Domain Parameters for 320-Bit Curves ......................<a href="#page-12">12</a> |
| 71 |
<a href="#section-3.6">3.6</a>. Domain Parameters for 384-Bit Curves ......................<a href="#page-13">13</a> |
| 72 |
<a href="#section-3.7">3.7</a>. Domain Parameters for 512-Bit Curves ......................<a href="#page-14">14</a> |
| 73 |
<a href="#section-4">4</a>. Object Identifiers and ASN.1 Syntax ............................<a href="#page-15">15</a> |
| 74 |
<a href="#section-4.1">4.1</a>. Object Identifiers ........................................<a href="#page-15">15</a> |
| 75 |
<a href="#section-4.2">4.2</a>. ASN.1 Syntax for Usage with X.509 Certificates ............<a href="#page-16">16</a> |
| 76 |
<a href="#section-5">5</a>. Security Considerations ........................................<a href="#page-17">17</a> |
| 77 |
<a href="#section-6">6</a>. Intellectual Property Rights ...................................<a href="#page-18">18</a> |
| 78 |
<a href="#section-7">7</a>. References .....................................................<a href="#page-18">18</a> |
| 79 |
<a href="#section-7.1">7.1</a>. Normative References ......................................<a href="#page-18">18</a> |
| 80 |
<a href="#section-7.2">7.2</a>. Informative References ....................................<a href="#page-19">19</a> |
| 81 |
<a href="#appendix-A">Appendix A</a>. Pseudo-Random Generation of Parameters ................<a href="#page-22">22</a> |
| 82 |
<a href="#appendix-A.1">A.1</a>. Generation of Prime Numbers ................................<a href="#page-22">22</a> |
| 83 |
<a href="#appendix-A.2">A.2</a>. Generation of Pseudo-Random Curves .........................<a href="#page-24">24</a> |
| 84 |
|
| 85 |
|
| 86 |
|
| 87 |
|
| 88 |
|
| 89 |
|
| 90 |
|
| 91 |
|
| 92 |
|
| 93 |
|
| 94 |
|
| 95 |
|
| 96 |
|
| 97 |
|
| 98 |
|
| 99 |
|
| 100 |
|
| 101 |
|
| 102 |
|
| 103 |
|
| 104 |
|
| 105 |
|
| 106 |
|
| 107 |
|
| 108 |
<span class="grey">Lochter & Merkle Informational [Page 2]</span></pre> |
| 109 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span> |
| 110 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 111 |
|
| 112 |
|
| 113 |
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span> |
| 114 |
|
| 115 |
Although several standards for elliptic curves and domain parameters |
| 116 |
exist (e.g., [<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>], [<a href="#ref-FIPS" title=""Digital Signature Standard (DSS)"">FIPS</a>], or [<a href="#ref-SEC2" title=""Recommended Elliptic Curve Domain Parameters"">SEC2</a>]), some major issues have |
| 117 |
still not been addressed: |
| 118 |
|
| 119 |
o Not all parameters have been generated in a verifiably pseudo- |
| 120 |
random way. In particular, the seeds from which the curve |
| 121 |
parameters were derived have been chosen ad hoc, leaving out an |
| 122 |
essential part of the security proof. |
| 123 |
|
| 124 |
o The primes selected for the base fields have a very special form |
| 125 |
facilitating efficient implementation. This does not only |
| 126 |
contradict the approach of pseudo-random parameters, but also |
| 127 |
increases the risk of implementations violating one of the |
| 128 |
numerous patents for fast modular arithmetic with special primes. |
| 129 |
|
| 130 |
o No proofs are provided that the proposed parameters do not belong |
| 131 |
to those classes of parameters that are susceptible to |
| 132 |
cryptanalytic attacks with sub-exponential complexity. |
| 133 |
|
| 134 |
o Recent research results seem to indicate a potential for new |
| 135 |
attacks on elliptic curve cryptosystems. At least for |
| 136 |
applications with the highest security demands or under |
| 137 |
circumstances that complicate a change of parameters in response |
| 138 |
to new attacks, the inclusion of a corresponding security |
| 139 |
requirement for domain parameters (the class group condition, see |
| 140 |
<a href="#section-2">Section 2</a>) is justified. |
| 141 |
|
| 142 |
o Some of the proposed subgroups have a non-trivial cofactor, which |
| 143 |
demands additional checks by cryptographic applications to prevent |
| 144 |
small subgroup attacks (see [<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>] or [<a href="#ref-SEC1" title=""Elliptic Curve Cryptography"">SEC1</a>]). |
| 145 |
|
| 146 |
o The domain parameters specified do not cover all bit lengths that |
| 147 |
correspond to the commonly used key lengths for symmetric |
| 148 |
cryptographic algorithms. In particular, there is no 512-bit |
| 149 |
curve defined, but only one with a 521-bit length, which may be |
| 150 |
disadvantageous for some implementations. |
| 151 |
|
| 152 |
Furthermore, many of the parameters specified by the existing |
| 153 |
standards are identical (see [<a href="#ref-SEC2" title=""Recommended Elliptic Curve Domain Parameters"">SEC2</a>] for a comparison). Thus, there |
| 154 |
is still a need for additional elliptic curve domain parameters that |
| 155 |
overcome the above limitations. |
| 156 |
|
| 157 |
|
| 158 |
|
| 159 |
|
| 160 |
|
| 161 |
|
| 162 |
|
| 163 |
|
| 164 |
<span class="grey">Lochter & Merkle Informational [Page 3]</span></pre> |
| 165 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span> |
| 166 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 167 |
|
| 168 |
|
| 169 |
<span class="h3"><a class="selflink" id="section-1.1" href="#section-1.1">1.1</a>. Scope and Relation to Other Specifications</span> |
| 170 |
|
| 171 |
This RFC specifies elliptic curve domain parameters over prime fields |
| 172 |
GF(p) with p having a length of 160, 192, 224, 256, 320, 384, and 512 |
| 173 |
bits. These parameters were generated in a pseudo-random, yet |
| 174 |
completely systematic and reproducible, way and have been verified to |
| 175 |
resist current cryptanalytic approaches. The parameters are |
| 176 |
compliant with ANSI X9.62 [<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>] and ANSI X9.63 [<a href="#ref-ANSI2" title=""Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using The Elliptic Curve Cryptography"">ANSI2</a>], ISO/IEC |
| 177 |
14888 [<a href="#ref-ISO1" title="">ISO1</a>] and ISO/IEC 15946 [<a href="#ref-ISO2" title=""Information Technology - Security Techniques - Cryptographic Techniques Based on Elliptic Curves - Part 2: Digital signatures"">ISO2</a>], ETSI TS 102 176-1 [<a href="#ref-ETSI" title=""Algorithms and Parameters for Secure Electronic Signatures, Part 1: Hash Functions and Asymmetric Algorithms"">ETSI</a>], as |
| 178 |
well as with FIPS-186-2 [<a href="#ref-FIPS" title=""Digital Signature Standard (DSS)"">FIPS</a>], and the Efficient Cryptography Group |
| 179 |
(SECG) specifications ([<a href="#ref-SEC1" title=""Elliptic Curve Cryptography"">SEC1</a>] and [<a href="#ref-SEC2" title=""Recommended Elliptic Curve Domain Parameters"">SEC2</a>]). |
| 180 |
|
| 181 |
Furthermore, this document identifies the security and implementation |
| 182 |
requirements for the parameters, and describes the methods used for |
| 183 |
the pseudo-random generation of the parameters. |
| 184 |
|
| 185 |
Finally, this RFC defines ASN.1 object identifiers for all elliptic |
| 186 |
curve domain parameter sets specified herein, e.g., for use in X.509 |
| 187 |
certificates. |
| 188 |
|
| 189 |
This document does neither address the cryptographic algorithms to be |
| 190 |
used with the specified parameters nor their application in other |
| 191 |
standards. However, it is consistent with the following RFCs that |
| 192 |
specify the usage of elliptic curve cryptography in protocols and |
| 193 |
applications: |
| 194 |
|
| 195 |
o [<a href="./rfc5753" title=""Use of Elliptic Curve Cryptography (ECC) Algorithms in Cryptographic Message Syntax (CMS)"">RFC5753</a>] for the cryptographic message syntax (CMS) |
| 196 |
|
| 197 |
o [<a href="./rfc3279" title=""Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile"">RFC3279</a>] and [<a href="./rfc5480" title=""Elliptic Curve Cryptography Subject Public Key Information"">RFC5480</a>] for X.509 certificates and CRLs |
| 198 |
|
| 199 |
o [<a href="./rfc4050" title=""Using the Elliptic Curve Signature Algorithm (ECDSA) for XML Digital Signatures"">RFC4050</a>] for XML signatures |
| 200 |
|
| 201 |
o [<a href="./rfc4492" title=""Elliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)"">RFC4492</a>] for TLS |
| 202 |
|
| 203 |
o [<a href="./rfc4754" title=""IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)"">RFC4754</a>] for IKE |
| 204 |
|
| 205 |
<span class="h3"><a class="selflink" id="section-1.2" href="#section-1.2">1.2</a>. Requirements Language</span> |
| 206 |
|
| 207 |
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", |
| 208 |
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this |
| 209 |
document are to be interpreted as described in <a href="./rfc2119">RFC 2119</a> [<a href="./rfc2119" title=""Key words for use in RFCs to Indicate Requirement Levels"">RFC2119</a>]. |
| 210 |
|
| 211 |
<span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Requirements on the Elliptic Curve Domain Parameters</span> |
| 212 |
|
| 213 |
Throughout this memo, let p > 3 be a prime and GF(p) a finite field |
| 214 |
(sometimes also referred to as Galois Field or GF(p)) with p |
| 215 |
elements. For given A and B with non-zero 4*A^3 + 27*B^2 mod p, the |
| 216 |
set of solutions (x,y) for the equation E: y^2 = x^3 + A*x + B mod p |
| 217 |
|
| 218 |
|
| 219 |
|
| 220 |
<span class="grey">Lochter & Merkle Informational [Page 4]</span></pre> |
| 221 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span> |
| 222 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 223 |
|
| 224 |
|
| 225 |
over GF(p) together with a neutral element O and well-defined laws |
| 226 |
for addition and inversion define a group E(GF(p)) -- the group of |
| 227 |
GF(p) rational points on E. Typically, for cryptographic |
| 228 |
applications, an element G of prime order q is chosen in E(GF(p)). |
| 229 |
|
| 230 |
A comprehensive introduction to elliptic curve cryptography can be |
| 231 |
found in [<a href="#ref-CFDA" title=""Handbook of Elliptic and Hyperelliptic Curve Cryptography"">CFDA</a>] and [<a href="#ref-BSS" title=""Elliptic Curves in Cryptography"">BSS</a>]. |
| 232 |
|
| 233 |
Note 1: We choose {0,...,p-1} as a set of representatives for the |
| 234 |
elements of GF(p). This choice induces a natural ordering on GF(p). |
| 235 |
|
| 236 |
<span class="h3"><a class="selflink" id="section-2.1" href="#section-2.1">2.1</a>. Security Requirements</span> |
| 237 |
|
| 238 |
The following security requirements are either motivated by known |
| 239 |
cryptographic analysis or aim to enhance trust in the recommended |
| 240 |
curves. As this specification aims at a particularly high level of |
| 241 |
security, a restrictive position is taken here. Nevertheless, it may |
| 242 |
be sensible to slightly deviate from these requirements for certain |
| 243 |
applications (e.g., in order to achieve higher computational |
| 244 |
performance). More details on requirements for cryptographically |
| 245 |
strong elliptic curves can be found in [<a href="#ref-CFDA" title=""Handbook of Elliptic and Hyperelliptic Curve Cryptography"">CFDA</a>] and [<a href="#ref-BSS" title=""Elliptic Curves in Cryptography"">BSS</a>]. |
| 246 |
|
| 247 |
1. Immunity to attacks using the Weil or Tate Pairing. These |
| 248 |
attacks allow the embedding of the cyclic subgroup generated by G |
| 249 |
into the group of units of a degree-l extension GF(p^l) of GF(p), |
| 250 |
where sub-exponential attacks on the discrete logarithm problem |
| 251 |
(DLP) exist. Here we have l = min{t | q divides p^t - 1}, i.e., |
| 252 |
l is the order of p mod q. By Fermat's Little Theorem, l divides |
| 253 |
q-1. We require (q-1)/l < 100, which means that l is close to |
| 254 |
the maximum possible value. This requirement is considerably |
| 255 |
stronger than those of [<a href="#ref-SEC2" title=""Recommended Elliptic Curve Domain Parameters"">SEC2</a>] and [<a href="#ref-ANSI2" title=""Public Key Cryptography For The Financial Services Industry: Key Agreement and Key Transport Using The Elliptic Curve Cryptography"">ANSI2</a>] and also excludes |
| 256 |
supersingular curves, as those are the curves of order p+1. |
| 257 |
|
| 258 |
2. The trace is not equal to one. Trace one curves (or anomalous |
| 259 |
curves) are curves with #E(GF(p)) = p. Satoh and Araki [<a href="#ref-SA" title=""Fermat Quotients and the Polynomial Time Discrete Log Algorithm for Anomalous Elliptic Curves"">SA</a>], |
| 260 |
Semaev [<a href="#ref-Sem" title=""Evaluation of Discrete Logarithms on Some Elliptic Curves"">Sem</a>], and Smart [<a href="#ref-Sma" title=""The Discrete Logarithm Problem on Elliptic Curves of Trace One"">Sma</a>] independently proposed efficient |
| 261 |
solutions to the elliptic curve discrete logarithm problem |
| 262 |
(ECDLP) on trace one curves. Note that these curves are also |
| 263 |
excluded by requirement 5 of <a href="#section-2.2">Section 2.2</a>. |
| 264 |
|
| 265 |
3. Large class number. The class number of the maximal order of the |
| 266 |
quotient field of the endomorphism ring End(E) of E is larger |
| 267 |
than 10^7. Generally, E cannot be "lifted" to a curve E' over an |
| 268 |
algebraic number field L with End(E) = End(E') unless the degree |
| 269 |
of L over the rationals is larger than the class number of |
| 270 |
End(E). Although there are no efficient attacks exploiting a |
| 271 |
small class number, recent work ([<a href="#ref-JMV" title=""Ramanujan Graphs and the Random Reducibility of Discrete Log on Isogenous Elliptic Curves"">JMV</a>] and [<a href="#ref-HR" title=""Signature Calculus and the Discrete Logarithm Problem for Elliptic Curves (Preliminary Version)"">HR</a>]) also may be seen |
| 272 |
as argument for the class number condition. |
| 273 |
|
| 274 |
|
| 275 |
|
| 276 |
<span class="grey">Lochter & Merkle Informational [Page 5]</span></pre> |
| 277 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span> |
| 278 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 279 |
|
| 280 |
|
| 281 |
4. Prime group order. The group order #E(GF(p)) shall be a prime |
| 282 |
number in order to counter small-subgroup attacks (see [<a href="#ref-HMV" title=""Guide to Elliptic Curve Cryptography"">HMV</a>]). |
| 283 |
Therefore, all groups proposed in this RFC have cofactor 1. Note |
| 284 |
that curves with prime order have no point of order 2 and |
| 285 |
therefore no point with y-coordinate 0. |
| 286 |
|
| 287 |
5. Verifiably pseudo-random. The elliptic curve domain parameters |
| 288 |
shall be generated in a pseudo-random manner using seeds that are |
| 289 |
generated in a systematic and comprehensive way. The methods by |
| 290 |
which the parameters have been obtained are explained in <a href="#appendix-A">Appendix</a> |
| 291 |
<a href="#appendix-A">A</a>. |
| 292 |
|
| 293 |
6. Proof of security. For all curves, a proof should be given that |
| 294 |
all security requirements are met. These proofs are provided in |
| 295 |
[<a href="#ref-EBP" title=""ECC Brainpool Standard Curves and Curve Generation"">EBP</a>]. |
| 296 |
|
| 297 |
In [<a href="#ref-BG" title=""The Static Diffie-Hellman Problem"">BG</a>], attacks are described that apply to elliptic curve domain |
| 298 |
parameters where q-1 has a factor u in the order of q^(1/3). |
| 299 |
However, the circumstances under which these attacks are applicable |
| 300 |
can be avoided in most applications. Therefore, no corresponding |
| 301 |
security requirement is stated here. However, it is highly |
| 302 |
recommended that developers verify the security of their |
| 303 |
implementations against this kind of attack. |
| 304 |
|
| 305 |
<span class="h3"><a class="selflink" id="section-2.2" href="#section-2.2">2.2</a>. Technical Requirements</span> |
| 306 |
|
| 307 |
Commercial demands and experience with existing implementations lead |
| 308 |
to the following technical requirements for the elliptic curve domain |
| 309 |
parameters. |
| 310 |
|
| 311 |
1. For each of the bit lengths 160, 192, 224, 256, 320, 384, and |
| 312 |
512, one curve shall be proposed. This requirement follows from |
| 313 |
the need for curves providing different levels of security that |
| 314 |
are appropriate for the underlying symmetric algorithms. The |
| 315 |
existing standards specify a 521-bit curve instead of a 512-bit |
| 316 |
curve. |
| 317 |
|
| 318 |
2. The prime number p shall be congruent 3 mod 4. This requirement |
| 319 |
allows efficient point compression: one method for the |
| 320 |
transmission of curve points P=(x,y) is to transmit only x and |
| 321 |
the least significant bit LSB(y) of y. For p = 3 mod 4, we get |
| 322 |
(y^2)^((p+1)/4) = y*y^((p-1)/2), which is either y or -y by |
| 323 |
Fermat's Little Theorem; hence, y can be computed very |
| 324 |
efficiently using the curve equation. This requirement is not |
| 325 |
always met by the parameters defined in existing standards. |
| 326 |
|
| 327 |
|
| 328 |
|
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
<span class="grey">Lochter & Merkle Informational [Page 6]</span></pre> |
| 333 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span> |
| 334 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 335 |
|
| 336 |
|
| 337 |
3. The curves shall be GF(p)-isomorphic to a curve E': y^2 = x^3 + |
| 338 |
A'*x + B' mod p with A' = -3 mod p. This property permits the |
| 339 |
use of the arithmetical advantages of curves with A = -3, as |
| 340 |
shown by Brier and Joyce [<a href="#ref-BJ" title=""Fast Multiplication on Elliptic Curves through Isogenies"">BJ</a>]. For p = 3 mod 4, approximately |
| 341 |
half of the isomorphism classes of elliptic curves over GF(p) |
| 342 |
contain a curve E' with A' = -3 mod p. Precisely, if a curve is |
| 343 |
given by E: y^2 = x^3 + A*x + B mod p with -3 = A*u^4 being |
| 344 |
solvable in GF(p) and u=Z is a solution to this equation, then |
| 345 |
the requirement is fulfilled by means of the quadratic twist E': |
| 346 |
y^2 = x^3 + Z^4*A*x + Z^6*B mod p, and the GF(p)-isomorphism is |
| 347 |
given by F(x,y) := (x*Z^2, y*Z^3). Due to this isomorphism, |
| 348 |
E(GF(p)) and E'(GF(p)) have the same number of points, share the |
| 349 |
same algebraic structure, and hence offer the same level of |
| 350 |
security. This constraint has also been used by [<a href="#ref-SEC2" title=""Recommended Elliptic Curve Domain Parameters"">SEC2</a>] and |
| 351 |
[<a href="#ref-FIPS" title=""Digital Signature Standard (DSS)"">FIPS</a>]. |
| 352 |
|
| 353 |
4. The prime p must not be of any special form; this requirement is |
| 354 |
met by a verifiably pseudo-random generation of the parameters |
| 355 |
(see requirement 5 in <a href="#section-2.1">Section 2.1</a>). Although parameters |
| 356 |
specified by existing standards do not meet this requirement, the |
| 357 |
need for such curves over (pseudo-)randomly chosen fields has |
| 358 |
already been foreseen by the Standards for Efficient Cryptography |
| 359 |
Group (SECG), see [<a href="#ref-SEC2" title=""Recommended Elliptic Curve Domain Parameters"">SEC2</a>]. |
| 360 |
|
| 361 |
5. #E(GF(p)) < p. As a consequence of the Hasse-Weil Theorem, the |
| 362 |
number of points #E(GF(p)) may be greater than the characteristic |
| 363 |
p of the prime field GF(p). In some cases, even the bit-length |
| 364 |
of #E(GF(p)) can exceed the bit-length of p. To avoid overruns |
| 365 |
in implementations, we require that #E(GF(p)) < p. In order to |
| 366 |
thwart attacks on digital signature schemes, some authors propose |
| 367 |
to use q > p, but the attacks described, e.g., in [<a href="#ref-BRS" title=""Key Substitution Attacks Revisited: Taking into Account Malicious Signers"">BRS</a>], appear |
| 368 |
infeasible in a well-designed Public Key Infrastructure (PKI). |
| 369 |
|
| 370 |
6. B shall be a non-square mod p. Otherwise, the compressed |
| 371 |
representations of the curve-points (0,0) and (0,X), with X being |
| 372 |
the square root of B with a least significant bit of 0, would be |
| 373 |
identical. As there are implementations of elliptic curves that |
| 374 |
encode the point at infinity as (0,0), we try to avoid |
| 375 |
ambiguities. Note that this condition is stable under quadratic |
| 376 |
twists as described in condition 3 above. Condition 6 makes the |
| 377 |
attack described in [<a href="#ref-G" title=""A Refined Power-Analysis-Attack on Elliptic Curve Cryptosystems"">G</a>] impossible. It can therefore also be |
| 378 |
seen as a security requirement. This constraint has not been |
| 379 |
specified by existing standards. |
| 380 |
|
| 381 |
|
| 382 |
|
| 383 |
|
| 384 |
|
| 385 |
|
| 386 |
|
| 387 |
|
| 388 |
<span class="grey">Lochter & Merkle Informational [Page 7]</span></pre> |
| 389 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span> |
| 390 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 391 |
|
| 392 |
|
| 393 |
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Domain Parameter Specification</span> |
| 394 |
|
| 395 |
In this section, the elliptic curve domain parameters proposed are |
| 396 |
specified in the following way. |
| 397 |
|
| 398 |
For all curves, an ID is given by which it can be referenced. |
| 399 |
|
| 400 |
p is the prime specifying the base field. |
| 401 |
|
| 402 |
A and B are the coefficients of the equation y^2 = x^3 + A*x + B |
| 403 |
mod p defining the elliptic curve. |
| 404 |
|
| 405 |
G = (x,y) is the base point, i.e., a point in E of prime order, |
| 406 |
with x and y being its x- and y-coordinates, respectively. |
| 407 |
|
| 408 |
q is the prime order of the group generated by G. |
| 409 |
|
| 410 |
h is the cofactor of G in E, i.e., #E(GF(p))/q. |
| 411 |
|
| 412 |
For the twisted curve, we also give the coefficient Z that defines |
| 413 |
the isomorphism F (see requirement 3 in <a href="#section-2.2">Section 2.2</a>). |
| 414 |
|
| 415 |
The methods for the generation of the parameters are given in |
| 416 |
<a href="#appendix-A">Appendix A</a>. Proofs for the fulfillment of the security requirements |
| 417 |
specified in <a href="#section-2.1">Section 2.1</a> are given in [<a href="#ref-EBP" title=""ECC Brainpool Standard Curves and Curve Generation"">EBP</a>]. |
| 418 |
|
| 419 |
<span class="h3"><a class="selflink" id="section-3.1" href="#section-3.1">3.1</a>. Domain Parameters for 160-Bit Curves</span> |
| 420 |
|
| 421 |
Curve-ID: brainpoolP160r1 |
| 422 |
|
| 423 |
p = E95E4A5F737059DC60DFC7AD95B3D8139515620F |
| 424 |
|
| 425 |
A = 340E7BE2A280EB74E2BE61BADA745D97E8F7C300 |
| 426 |
|
| 427 |
B = 1E589A8595423412134FAA2DBDEC95C8D8675E58 |
| 428 |
|
| 429 |
x = BED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3 |
| 430 |
|
| 431 |
y = 1667CB477A1A8EC338F94741669C976316DA6321 |
| 432 |
|
| 433 |
q = E95E4A5F737059DC60DF5991D45029409E60FC09 |
| 434 |
|
| 435 |
h = 1 |
| 436 |
|
| 437 |
|
| 438 |
|
| 439 |
|
| 440 |
|
| 441 |
|
| 442 |
|
| 443 |
|
| 444 |
<span class="grey">Lochter & Merkle Informational [Page 8]</span></pre> |
| 445 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span> |
| 446 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 447 |
|
| 448 |
|
| 449 |
#Twisted curve |
| 450 |
|
| 451 |
Curve-ID: brainpoolP160t1 |
| 452 |
|
| 453 |
Z = 24DBFF5DEC9B986BBFE5295A29BFBAE45E0F5D0B |
| 454 |
|
| 455 |
A = E95E4A5F737059DC60DFC7AD95B3D8139515620C |
| 456 |
|
| 457 |
B = 7A556B6DAE535B7B51ED2C4D7DAA7A0B5C55F380 |
| 458 |
|
| 459 |
x = B199B13B9B34EFC1397E64BAEB05ACC265FF2378 |
| 460 |
|
| 461 |
y = ADD6718B7C7C1961F0991B842443772152C9E0AD |
| 462 |
|
| 463 |
q = E95E4A5F737059DC60DF5991D45029409E60FC09 |
| 464 |
|
| 465 |
h = 1 |
| 466 |
|
| 467 |
<span class="h3"><a class="selflink" id="section-3.2" href="#section-3.2">3.2</a>. Domain Parameters for 192-Bit Curves</span> |
| 468 |
|
| 469 |
Curve-ID: brainpoolP192r1 |
| 470 |
|
| 471 |
p = C302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297 |
| 472 |
|
| 473 |
A = 6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF |
| 474 |
|
| 475 |
B = 469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9 |
| 476 |
|
| 477 |
x = C0A0647EAAB6A48753B033C56CB0F0900A2F5C4853375FD6 |
| 478 |
|
| 479 |
y = 14B690866ABD5BB88B5F4828C1490002E6773FA2FA299B8F |
| 480 |
|
| 481 |
q = C302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1 |
| 482 |
|
| 483 |
h = 1 |
| 484 |
|
| 485 |
#Twisted curve |
| 486 |
|
| 487 |
Curve-ID: brainpoolP192t1 |
| 488 |
|
| 489 |
Z = 1B6F5CC8DB4DC7AF19458A9CB80DC2295E5EB9C3732104CB |
| 490 |
|
| 491 |
A = C302F41D932A36CDA7A3463093D18DB78FCE476DE1A86294 |
| 492 |
|
| 493 |
B = 13D56FFAEC78681E68F9DEB43B35BEC2FB68542E27897B79 |
| 494 |
|
| 495 |
x = 3AE9E58C82F63C30282E1FE7BBF43FA72C446AF6F4618129 |
| 496 |
|
| 497 |
|
| 498 |
|
| 499 |
|
| 500 |
<span class="grey">Lochter & Merkle Informational [Page 9]</span></pre> |
| 501 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span> |
| 502 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 503 |
|
| 504 |
|
| 505 |
y = 097E2C5667C2223A902AB5CA449D0084B7E5B3DE7CCC01C9 |
| 506 |
|
| 507 |
q = C302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1 |
| 508 |
|
| 509 |
h = 1 |
| 510 |
|
| 511 |
<span class="h3"><a class="selflink" id="section-3.3" href="#section-3.3">3.3</a>. Domain Parameters for 224-Bit Curves</span> |
| 512 |
|
| 513 |
Curve-ID: brainpoolP224r1 |
| 514 |
|
| 515 |
p = D7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FF |
| 516 |
|
| 517 |
A = 68A5E62CA9CE6C1C299803A6C1530B514E182AD8B0042A59CAD29F43 |
| 518 |
|
| 519 |
B = 2580F63CCFE44138870713B1A92369E33E2135D266DBB372386C400B |
| 520 |
|
| 521 |
x = 0D9029AD2C7E5CF4340823B2A87DC68C9E4CE3174C1E6EFDEE12C07D |
| 522 |
|
| 523 |
y = 58AA56F772C0726F24C6B89E4ECDAC24354B9E99CAA3F6D3761402CD |
| 524 |
|
| 525 |
q = D7C134AA264366862A18302575D0FB98D116BC4B6DDEBCA3A5A7939F |
| 526 |
|
| 527 |
h = 1 |
| 528 |
|
| 529 |
#Twisted curve |
| 530 |
|
| 531 |
Curve-ID: brainpoolP224t1 |
| 532 |
|
| 533 |
Z = 2DF271E14427A346910CF7A2E6CFA7B3F484E5C2CCE1C8B730E28B3F |
| 534 |
|
| 535 |
A = D7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FC |
| 536 |
|
| 537 |
B = 4B337D934104CD7BEF271BF60CED1ED20DA14C08B3BB64F18A60888D |
| 538 |
|
| 539 |
x = 6AB1E344CE25FF3896424E7FFE14762ECB49F8928AC0C76029B4D580 |
| 540 |
|
| 541 |
y = 0374E9F5143E568CD23F3F4D7C0D4B1E41C8CC0D1C6ABD5F1A46DB4C |
| 542 |
|
| 543 |
q = D7C134AA264366862A18302575D0FB98D116BC4B6DDEBCA3A5A7939F |
| 544 |
|
| 545 |
h = 1 |
| 546 |
|
| 547 |
|
| 548 |
|
| 549 |
|
| 550 |
|
| 551 |
|
| 552 |
|
| 553 |
|
| 554 |
|
| 555 |
|
| 556 |
<span class="grey">Lochter & Merkle Informational [Page 10]</span></pre> |
| 557 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span> |
| 558 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 559 |
|
| 560 |
|
| 561 |
<span class="h3"><a class="selflink" id="section-3.4" href="#section-3.4">3.4</a>. Domain Parameters for 256-Bit Curves</span> |
| 562 |
|
| 563 |
Curve-ID: brainpoolP256r1 |
| 564 |
|
| 565 |
p = |
| 566 |
A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377 |
| 567 |
|
| 568 |
A = |
| 569 |
7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9 |
| 570 |
|
| 571 |
B = |
| 572 |
26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6 |
| 573 |
|
| 574 |
x = |
| 575 |
8BD2AEB9CB7E57CB2C4B482FFC81B7AFB9DE27E1E3BD23C23A4453BD9ACE3262 |
| 576 |
|
| 577 |
y = |
| 578 |
547EF835C3DAC4FD97F8461A14611DC9C27745132DED8E545C1D54C72F046997 |
| 579 |
|
| 580 |
q = |
| 581 |
A9FB57DBA1EEA9BC3E660A909D838D718C397AA3B561A6F7901E0E82974856A7 |
| 582 |
|
| 583 |
h = 1 |
| 584 |
|
| 585 |
#Twisted curve |
| 586 |
|
| 587 |
Curve-ID: brainpoolP256t1 |
| 588 |
|
| 589 |
Z = |
| 590 |
3E2D4BD9597B58639AE7AA669CAB9837CF5CF20A2C852D10F655668DFC150EF0 |
| 591 |
|
| 592 |
A = |
| 593 |
A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5374 |
| 594 |
|
| 595 |
B = |
| 596 |
662C61C430D84EA4FE66A7733D0B76B7BF93EBC4AF2F49256AE58101FEE92B04 |
| 597 |
|
| 598 |
x = |
| 599 |
A3E8EB3CC1CFE7B7732213B23A656149AFA142C47AAFBC2B79A191562E1305F4 |
| 600 |
|
| 601 |
y = |
| 602 |
2D996C823439C56D7F7B22E14644417E69BCB6DE39D027001DABE8F35B25C9BE |
| 603 |
|
| 604 |
q = |
| 605 |
A9FB57DBA1EEA9BC3E660A909D838D718C397AA3B561A6F7901E0E82974856A7 |
| 606 |
|
| 607 |
h = 1 |
| 608 |
|
| 609 |
|
| 610 |
|
| 611 |
|
| 612 |
<span class="grey">Lochter & Merkle Informational [Page 11]</span></pre> |
| 613 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span> |
| 614 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 615 |
|
| 616 |
|
| 617 |
<span class="h3"><a class="selflink" id="section-3.5" href="#section-3.5">3.5</a>. Domain Parameters for 320-Bit Curves</span> |
| 618 |
|
| 619 |
Curve-ID: brainpoolP320r1 |
| 620 |
|
| 621 |
p = D35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC |
| 622 |
28FCD412B1F1B32E27 |
| 623 |
|
| 624 |
A = 3EE30B568FBAB0F883CCEBD46D3F3BB8A2A73513F5EB79DA66190EB085FFA9 |
| 625 |
F492F375A97D860EB4 |
| 626 |
|
| 627 |
B = 520883949DFDBC42D3AD198640688A6FE13F41349554B49ACC31DCCD884539 |
| 628 |
816F5EB4AC8FB1F1A6 |
| 629 |
|
| 630 |
x = 43BD7E9AFB53D8B85289BCC48EE5BFE6F20137D10A087EB6E7871E2A10A599 |
| 631 |
C710AF8D0D39E20611 |
| 632 |
|
| 633 |
y = 14FDD05545EC1CC8AB4093247F77275E0743FFED117182EAA9C77877AAAC6A |
| 634 |
C7D35245D1692E8EE1 |
| 635 |
|
| 636 |
q = D35E472036BC4FB7E13C785ED201E065F98FCFA5B68F12A32D482EC7EE8658 |
| 637 |
E98691555B44C59311 |
| 638 |
|
| 639 |
h = 1 |
| 640 |
|
| 641 |
#Twisted curve |
| 642 |
|
| 643 |
Curve-ID: brainpoolP320t1 |
| 644 |
|
| 645 |
Z = 15F75CAF668077F7E85B42EB01F0A81FF56ECD6191D55CB82B7D861458A18F |
| 646 |
EFC3E5AB7496F3C7B1 |
| 647 |
|
| 648 |
A = D35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC |
| 649 |
28FCD412B1F1B32E24 |
| 650 |
|
| 651 |
B = A7F561E038EB1ED560B3D147DB782013064C19F27ED27C6780AAF77FB8A547 |
| 652 |
CEB5B4FEF422340353 |
| 653 |
|
| 654 |
x = 925BE9FB01AFC6FB4D3E7D4990010F813408AB106C4F09CB7EE07868CC136F |
| 655 |
FF3357F624A21BED52 |
| 656 |
|
| 657 |
y = 63BA3A7A27483EBF6671DBEF7ABB30EBEE084E58A0B077AD42A5A0989D1EE7 |
| 658 |
1B1B9BC0455FB0D2C3 |
| 659 |
|
| 660 |
q = D35E472036BC4FB7E13C785ED201E065F98FCFA5B68F12A32D482EC7EE8658 |
| 661 |
E98691555B44C59311 |
| 662 |
|
| 663 |
h = 1 |
| 664 |
|
| 665 |
|
| 666 |
|
| 667 |
|
| 668 |
<span class="grey">Lochter & Merkle Informational [Page 12]</span></pre> |
| 669 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span> |
| 670 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 671 |
|
| 672 |
|
| 673 |
<span class="h3"><a class="selflink" id="section-3.6" href="#section-3.6">3.6</a>. Domain Parameters for 384-Bit Curves</span> |
| 674 |
|
| 675 |
Curve-ID: brainpoolP384r1 |
| 676 |
|
| 677 |
p = 8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B412B1DA197FB711 |
| 678 |
23ACD3A729901D1A71874700133107EC53 |
| 679 |
|
| 680 |
A = 7BC382C63D8C150C3C72080ACE05AFA0C2BEA28E4FB22787139165EFBA91F9 |
| 681 |
0F8AA5814A503AD4EB04A8C7DD22CE2826 |
| 682 |
|
| 683 |
B = 04A8C7DD22CE28268B39B55416F0447C2FB77DE107DCD2A62E880EA53EEB62 |
| 684 |
D57CB4390295DBC9943AB78696FA504C11 |
| 685 |
|
| 686 |
x = 1D1C64F068CF45FFA2A63A81B7C13F6B8847A3E77EF14FE3DB7FCAFE0CBD10 |
| 687 |
E8E826E03436D646AAEF87B2E247D4AF1E |
| 688 |
|
| 689 |
y = 8ABE1D7520F9C2A45CB1EB8E95CFD55262B70B29FEEC5864E19C054FF99129 |
| 690 |
280E4646217791811142820341263C5315 |
| 691 |
|
| 692 |
q = 8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B31F166E6CAC0425 |
| 693 |
A7CF3AB6AF6B7FC3103B883202E9046565 |
| 694 |
|
| 695 |
h = 1 |
| 696 |
|
| 697 |
#Twisted curve |
| 698 |
|
| 699 |
Curve-ID: brainpoolP384t1 |
| 700 |
|
| 701 |
Z = 41DFE8DD399331F7166A66076734A89CD0D2BCDB7D068E44E1F378F41ECBAE |
| 702 |
97D2D63DBC87BCCDDCCC5DA39E8589291C |
| 703 |
|
| 704 |
A = 8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B412B1DA197FB711 |
| 705 |
23ACD3A729901D1A71874700133107EC50 |
| 706 |
|
| 707 |
B = 7F519EADA7BDA81BD826DBA647910F8C4B9346ED8CCDC64E4B1ABD11756DCE |
| 708 |
1D2074AA263B88805CED70355A33B471EE |
| 709 |
|
| 710 |
x = 18DE98B02DB9A306F2AFCD7235F72A819B80AB12EBD653172476FECD462AAB |
| 711 |
FFC4FF191B946A5F54D8D0AA2F418808CC |
| 712 |
|
| 713 |
y = 25AB056962D30651A114AFD2755AD336747F93475B7A1FCA3B88F2B6A208CC |
| 714 |
FE469408584DC2B2912675BF5B9E582928 |
| 715 |
|
| 716 |
q = 8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B31F166E6CAC0425 |
| 717 |
A7CF3AB6AF6B7FC3103B883202E9046565 |
| 718 |
|
| 719 |
h = 1 |
| 720 |
|
| 721 |
|
| 722 |
|
| 723 |
|
| 724 |
<span class="grey">Lochter & Merkle Informational [Page 13]</span></pre> |
| 725 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span> |
| 726 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 727 |
|
| 728 |
|
| 729 |
<span class="h3"><a class="selflink" id="section-3.7" href="#section-3.7">3.7</a>. Domain Parameters for 512-Bit Curves</span> |
| 730 |
|
| 731 |
Curve-ID: brainpoolP512r1 |
| 732 |
|
| 733 |
p = AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308 |
| 734 |
717D4D9B009BC66842AECDA12AE6A380E62881FF2F2D82C68528AA6056583A48F3 |
| 735 |
|
| 736 |
A = 7830A3318B603B89E2327145AC234CC594CBDD8D3DF91610A83441CAEA9863 |
| 737 |
BC2DED5D5AA8253AA10A2EF1C98B9AC8B57F1117A72BF2C7B9E7C1AC4D77FC94CA |
| 738 |
|
| 739 |
B = 3DF91610A83441CAEA9863BC2DED5D5AA8253AA10A2EF1C98B9AC8B57F1117 |
| 740 |
A72BF2C7B9E7C1AC4D77FC94CADC083E67984050B75EBAE5DD2809BD638016F723 |
| 741 |
|
| 742 |
x = 81AEE4BDD82ED9645A21322E9C4C6A9385ED9F70B5D916C1B43B62EEF4D009 |
| 743 |
8EFF3B1F78E2D0D48D50D1687B93B97D5F7C6D5047406A5E688B352209BCB9F822 |
| 744 |
|
| 745 |
y = 7DDE385D566332ECC0EABFA9CF7822FDF209F70024A57B1AA000C55B881F81 |
| 746 |
11B2DCDE494A5F485E5BCA4BD88A2763AED1CA2B2FA8F0540678CD1E0F3AD80892 |
| 747 |
|
| 748 |
q = AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308 |
| 749 |
70553E5C414CA92619418661197FAC10471DB1D381085DDADDB58796829CA90069 |
| 750 |
|
| 751 |
h = 1 |
| 752 |
|
| 753 |
#Twisted curve |
| 754 |
|
| 755 |
Curve-ID: brainpoolP512t1 |
| 756 |
|
| 757 |
Z = 12EE58E6764838B69782136F0F2D3BA06E27695716054092E60A80BEDB212B |
| 758 |
64E585D90BCE13761F85C3F1D2A64E3BE8FEA2220F01EBA5EEB0F35DBD29D922AB |
| 759 |
|
| 760 |
A = AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308 |
| 761 |
717D4D9B009BC66842AECDA12AE6A380E62881FF2F2D82C68528AA6056583A48F0 |
| 762 |
|
| 763 |
B = 7CBBBCF9441CFAB76E1890E46884EAE321F70C0BCB4981527897504BEC3E36 |
| 764 |
A62BCDFA2304976540F6450085F2DAE145C22553B465763689180EA2571867423E |
| 765 |
|
| 766 |
x = 640ECE5C12788717B9C1BA06CBC2A6FEBA85842458C56DDE9DB1758D39C031 |
| 767 |
3D82BA51735CDB3EA499AA77A7D6943A64F7A3F25FE26F06B51BAA2696FA9035DA |
| 768 |
|
| 769 |
y = 5B534BD595F5AF0FA2C892376C84ACE1BB4E3019B71634C01131159CAE03CE |
| 770 |
E9D9932184BEEF216BD71DF2DADF86A627306ECFF96DBB8BACE198B61E00F8B332 |
| 771 |
|
| 772 |
q = AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308 |
| 773 |
70553E5C414CA92619418661197FAC10471DB1D381085DDADDB58796829CA90069 |
| 774 |
|
| 775 |
h = 1 |
| 776 |
|
| 777 |
|
| 778 |
|
| 779 |
|
| 780 |
<span class="grey">Lochter & Merkle Informational [Page 14]</span></pre> |
| 781 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span> |
| 782 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 783 |
|
| 784 |
|
| 785 |
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Object Identifiers and ASN.1 Syntax</span> |
| 786 |
|
| 787 |
<span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a>. Object Identifiers</span> |
| 788 |
|
| 789 |
The root of the tree for the object identifiers defined in this |
| 790 |
specification is given by: |
| 791 |
|
| 792 |
ecStdCurvesAndGeneration OBJECT IDENTIFIER::= {iso(1) |
| 793 |
identified-organization(3) teletrust(36) algorithm(3) signature- |
| 794 |
algorithm(3) ecSign(2) 8} |
| 795 |
|
| 796 |
The object identifier ellipticCurve represents the tree for domain |
| 797 |
parameter sets. It has the following value: |
| 798 |
|
| 799 |
ellipticCurve OBJECT IDENTIFIER ::= {ecStdCurvesAndGeneration 1} |
| 800 |
|
| 801 |
The tree containing the object identifiers for each set of domain |
| 802 |
parameters defined in this RFC is: |
| 803 |
|
| 804 |
versionOne OBJECT IDENTIFIER ::= {ellipticCurve 1} |
| 805 |
|
| 806 |
The following object identifiers represent the domain parameter sets |
| 807 |
defined in this RFC: |
| 808 |
|
| 809 |
brainpoolP160r1 OBJECT IDENTIFIER ::= {versionOne 1} |
| 810 |
|
| 811 |
brainpoolP160t1 OBJECT IDENTIFIER ::= {versionOne 2} |
| 812 |
|
| 813 |
brainpoolP192r1 OBJECT IDENTIFIER ::= {versionOne 3} |
| 814 |
|
| 815 |
brainpoolP192t1 OBJECT IDENTIFIER ::= {versionOne 4} |
| 816 |
|
| 817 |
brainpoolP224r1 OBJECT IDENTIFIER ::= {versionOne 5} |
| 818 |
|
| 819 |
brainpoolP224t1 OBJECT IDENTIFIER ::= {versionOne 6} |
| 820 |
|
| 821 |
brainpoolP256r1 OBJECT IDENTIFIER ::= {versionOne 7} |
| 822 |
|
| 823 |
brainpoolP256t1 OBJECT IDENTIFIER ::= {versionOne 8} |
| 824 |
|
| 825 |
brainpoolP320r1 OBJECT IDENTIFIER ::= {versionOne 9} |
| 826 |
|
| 827 |
brainpoolP320t1 OBJECT IDENTIFIER ::= {versionOne 10} |
| 828 |
|
| 829 |
brainpoolP384r1 OBJECT IDENTIFIER ::= {versionOne 11} |
| 830 |
|
| 831 |
brainpoolP384t1 OBJECT IDENTIFIER ::= {versionOne 12} |
| 832 |
|
| 833 |
|
| 834 |
|
| 835 |
|
| 836 |
<span class="grey">Lochter & Merkle Informational [Page 15]</span></pre> |
| 837 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span> |
| 838 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 839 |
|
| 840 |
|
| 841 |
brainpoolP512r1 OBJECT IDENTIFIER ::= {versionOne 13} |
| 842 |
|
| 843 |
brainpoolP512t1 OBJECT IDENTIFIER ::= {versionOne 14} |
| 844 |
|
| 845 |
<span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a>. ASN.1 Syntax for Usage with X.509 Certificates</span> |
| 846 |
|
| 847 |
The domain parameters specified in this RFC SHALL be used with X.509 |
| 848 |
certificates in accordance with [<a href="./rfc5480" title=""Elliptic Curve Cryptography Subject Public Key Information"">RFC5480</a>]. In particular, |
| 849 |
|
| 850 |
o the algorithm field of subjectPublicKeyInfo MUST be set to: |
| 851 |
|
| 852 |
* id-ecPublicKey, if the algorithms that can be used with the |
| 853 |
subject public key are not restricted, or |
| 854 |
|
| 855 |
* id-ecDH to restrict the usage of the subject public key to |
| 856 |
Elliptic Curve Diffie-Hellman (ECDH) key agreement, or |
| 857 |
|
| 858 |
* id-ecMQV to restrict the usage of the subject public key to |
| 859 |
Elliptic Curve Menezes-Qu-Vanstone (ECMQV) key agreement, and |
| 860 |
|
| 861 |
o the field algorithm.parameter of subjectPublicKeyInfo MUST be of |
| 862 |
type: |
| 863 |
|
| 864 |
* namedCurve to specify the domain parameters by one of the |
| 865 |
Object Identifiers (OIDs) defined in <a href="#section-4.1">Section 4.1</a>, or |
| 866 |
|
| 867 |
* specifiedCurve to specify the domain parameters explicitly as |
| 868 |
defined in [<a href="./rfc5480" title=""Elliptic Curve Cryptography Subject Public Key Information"">RFC5480</a>], or |
| 869 |
|
| 870 |
* implicitCurve, if the domain parameters are found in an |
| 871 |
issuer's certificate. |
| 872 |
|
| 873 |
If the domain parameters are explicitly specified using the type |
| 874 |
specifiedCurve in the field algorithm.parameter of |
| 875 |
subjectPublicKeyInfo, ANSI X9.62 [<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>] and [<a href="./rfc5480" title=""Elliptic Curve Cryptography Subject Public Key Information"">RFC5480</a>] allow |
| 876 |
indicating whether or not a curve and base point have been generated |
| 877 |
verifiably in a pseudo-random way. Although the parameters specified |
| 878 |
in <a href="#section-3">Section 3</a> have all been generated by the pseudo-random methods |
| 879 |
described in <a href="#appendix-A">Appendix A</a>, these algorithms deviate from those mandated |
| 880 |
in ANSI X9.62, A.3.3.1. Consequently, applications following ANSI |
| 881 |
X9.62 or [<a href="./rfc5480" title=""Elliptic Curve Cryptography Subject Public Key Information"">RFC5480</a>] will not be able to verify the pseudo-randomness |
| 882 |
of the parameters. In order to avoid rejection of the parameters, |
| 883 |
the ASN.1 encoding SHOULD NOT specify that the curve or base point |
| 884 |
has been generated verifiably at random. In particular, |
| 885 |
certification authorities (CAs) SHOULD set the contents of |
| 886 |
specifiedCurve in the following way: |
| 887 |
|
| 888 |
o version is set to ecpVer1(1). |
| 889 |
|
| 890 |
|
| 891 |
|
| 892 |
<span class="grey">Lochter & Merkle Informational [Page 16]</span></pre> |
| 893 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span> |
| 894 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 895 |
|
| 896 |
|
| 897 |
o fieldId includes the fieldType prime-field and as parameter the |
| 898 |
value p of the selected domain parameters as specified in <a href="#section-3">Section</a> |
| 899 |
<a href="#section-3">3</a>. |
| 900 |
|
| 901 |
o curve includes the values a and b of the selected domain |
| 902 |
parameters as specified in <a href="#section-3">Section 3</a>, but seed is absent. |
| 903 |
|
| 904 |
o base is the octet string representation of the base point G of the |
| 905 |
selected domain parameters as specified in <a href="#section-3">Section 3</a>. |
| 906 |
|
| 907 |
o order is set to q of the selected domain parameters as specified |
| 908 |
in <a href="#section-3">Section 3</a>. |
| 909 |
|
| 910 |
o cofactor is set to 1. |
| 911 |
|
| 912 |
o hash is absent. |
| 913 |
|
| 914 |
<span class="h2"><a class="selflink" id="section-5" href="#section-5">5</a>. Security Considerations</span> |
| 915 |
|
| 916 |
The level of security provided by symmetric ciphers and hash |
| 917 |
functions used in conjunction with the elliptic curve domain |
| 918 |
parameters specified in this RFC should roughly match or exceed the |
| 919 |
level provided by the domain parameters. The following table |
| 920 |
indicates the minimum key sizes for symmetric ciphers and hash |
| 921 |
functions providing at least (roughly) comparable security. |
| 922 |
|
| 923 |
|
| 924 |
|
| 925 |
|
| 926 |
|
| 927 |
|
| 928 |
|
| 929 |
|
| 930 |
|
| 931 |
|
| 932 |
|
| 933 |
|
| 934 |
|
| 935 |
|
| 936 |
|
| 937 |
|
| 938 |
|
| 939 |
|
| 940 |
|
| 941 |
|
| 942 |
|
| 943 |
|
| 944 |
|
| 945 |
|
| 946 |
|
| 947 |
|
| 948 |
<span class="grey">Lochter & Merkle Informational [Page 17]</span></pre> |
| 949 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span> |
| 950 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 951 |
|
| 952 |
|
| 953 |
+--------------------+--------------------+-------------------------+ |
| 954 |
| elliptic curve | minimum length of | hash functions | |
| 955 |
| domain parameters | symmetric keys | | |
| 956 |
+--------------------+--------------------+-------------------------+ |
| 957 |
| brainpoolP160r1 | 80 | SHA-1, SHA-224, | |
| 958 |
| | | SHA-256, SHA-384, | |
| 959 |
| | | SHA-512 | |
| 960 |
| | | | |
| 961 |
| brainpoolP192r1 | 96 | SHA-224, SHA-256, | |
| 962 |
| | | SHA-384, SHA-512 | |
| 963 |
| | | | |
| 964 |
| brainpoolP224r1 | 112 | SHA-224, SHA-256, | |
| 965 |
| | | SHA-384, SHA-512 | |
| 966 |
| | | | |
| 967 |
| brainpoolP256r1 | 128 | SHA-256, SHA-384, | |
| 968 |
| | | SHA-512 | |
| 969 |
| | | | |
| 970 |
| brainpoolP320r1 | 160 | SHA-384, SHA-512 | |
| 971 |
| | | | |
| 972 |
| brainpoolP384r1 | 192 | SHA-384, SHA-512 | |
| 973 |
| | | | |
| 974 |
| brainpoolP512r1 | 256 | SHA-512 | |
| 975 |
+--------------------+--------------------+-------------------------+ |
| 976 |
|
| 977 |
Table 1 |
| 978 |
|
| 979 |
Security properties of the elliptic curve domain parameters specified |
| 980 |
in this RFC are discussed in <a href="#section-2.1">Section 2.1</a>. Further security |
| 981 |
discussions specific to elliptic curve cryptography can be found in |
| 982 |
[<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>] and [<a href="#ref-SEC1" title=""Elliptic Curve Cryptography"">SEC1</a>]. |
| 983 |
|
| 984 |
<span class="h2"><a class="selflink" id="section-6" href="#section-6">6</a>. Intellectual Property Rights</span> |
| 985 |
|
| 986 |
The authors have no knowledge about any intellectual property rights |
| 987 |
that cover the usage of the domain parameters defined herein. |
| 988 |
However, readers should be aware that implementations based on these |
| 989 |
domain parameters may require use of inventions covered by patent |
| 990 |
rights. |
| 991 |
|
| 992 |
<span class="h2"><a class="selflink" id="section-7" href="#section-7">7</a>. References</span> |
| 993 |
|
| 994 |
<span class="h3"><a class="selflink" id="section-7.1" href="#section-7.1">7.1</a>. Normative References</span> |
| 995 |
|
| 996 |
[<a id="ref-ANSI1">ANSI1</a>] American National Standards Institute, "Public Key |
| 997 |
Cryptography For The Financial Services Industry: The |
| 998 |
Elliptic Curve Digital Signature Algorithm (ECDSA)", ANSI |
| 999 |
X9.62, 2005. |
| 1000 |
|
| 1001 |
|
| 1002 |
|
| 1003 |
|
| 1004 |
<span class="grey">Lochter & Merkle Informational [Page 18]</span></pre> |
| 1005 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span> |
| 1006 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1007 |
|
| 1008 |
|
| 1009 |
[<a id="ref-RFC2119">RFC2119</a>] Bradner, S., "Key words for use in RFCs to Indicate |
| 1010 |
Requirement Levels", <a href="https://www.rfc-editor.org/bcp/bcp14">BCP 14</a>, <a href="./rfc2119">RFC 2119</a>, March 1997. |
| 1011 |
|
| 1012 |
[<a id="ref-RFC5480">RFC5480</a>] Turner, S., Brown, D., Yiu, K., Housley, R., and T. Polk, |
| 1013 |
"Elliptic Curve Cryptography Subject Public Key |
| 1014 |
Information", <a href="./rfc5480">RFC 5480</a>, March 2009. |
| 1015 |
|
| 1016 |
<span class="h3"><a class="selflink" id="section-7.2" href="#section-7.2">7.2</a>. Informative References</span> |
| 1017 |
|
| 1018 |
[<a id="ref-ANSI2">ANSI2</a>] American National Standards Institute, "Public Key |
| 1019 |
Cryptography For The Financial Services Industry: Key |
| 1020 |
Agreement and Key Transport Using The Elliptic Curve |
| 1021 |
Cryptography", ANSI X9.63, 2001. |
| 1022 |
|
| 1023 |
[<a id="ref-BJ">BJ</a>] Brier, E. and M. Joyce, "Fast Multiplication on Elliptic |
| 1024 |
Curves through Isogenies", Applied Algebra Algebraic |
| 1025 |
Algorithms and Error-Correcting Codes, Lecture Notes in |
| 1026 |
Computer Science 2643, Springer Verlag, 2003. |
| 1027 |
|
| 1028 |
[<a id="ref-BG">BG</a>] Brown, J. and R. Gallant, "The Static Diffie-Hellman |
| 1029 |
Problem", Centre for Applied Cryptographic Research, |
| 1030 |
University of Waterloo, Technical Report CACR 2004-10, |
| 1031 |
2005. |
| 1032 |
|
| 1033 |
[<a id="ref-BRS">BRS</a>] Bohli, J., Roehrich, S., and R. Steinwandt, "Key |
| 1034 |
Substitution Attacks Revisited: Taking into Account |
| 1035 |
Malicious Signers", International Journal of Information |
| 1036 |
Security Volume 5, Issue 1, January 2006. |
| 1037 |
|
| 1038 |
[<a id="ref-BSS">BSS</a>] Blake, I., Seroussi, G., and N. Smart, "Elliptic Curves in |
| 1039 |
Cryptography", Cambridge University Press, 1999. |
| 1040 |
|
| 1041 |
[<a id="ref-EBP">EBP</a>] ECC Brainpool, "ECC Brainpool Standard Curves and Curve |
| 1042 |
Generation", October 2005, <<a href="http://www.ecc-brainpool.org/download/Domain-parameters.pdf">http://www.ecc-brainpool.org/</a> |
| 1043 |
<a href="http://www.ecc-brainpool.org/download/Domain-parameters.pdf">download/Domain-parameters.pdf</a>>. |
| 1044 |
|
| 1045 |
[<a id="ref-ETSI">ETSI</a>] European Telecommunications Standards Institute (ETSI), |
| 1046 |
"Algorithms and Parameters for Secure Electronic |
| 1047 |
Signatures, Part 1: Hash Functions and Asymmetric |
| 1048 |
Algorithms", TS 102 176-1, July 2005. |
| 1049 |
|
| 1050 |
[<a id="ref-FIPS">FIPS</a>] National Institute of Standards and Technology, "Digital |
| 1051 |
Signature Standard (DSS)", FIPS PUB 186-2, December 1998. |
| 1052 |
|
| 1053 |
[<a id="ref-G">G</a>] Goubin, L., "A Refined Power-Analysis-Attack on Elliptic |
| 1054 |
Curve Cryptosystems", Proceedings of Public-Key- |
| 1055 |
Cryptography - PKC 2003, Lecture Notes in Computer Science |
| 1056 |
2567, Springer Verlag, 2003. |
| 1057 |
|
| 1058 |
|
| 1059 |
|
| 1060 |
<span class="grey">Lochter & Merkle Informational [Page 19]</span></pre> |
| 1061 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span> |
| 1062 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1063 |
|
| 1064 |
|
| 1065 |
[<a id="ref-CFDA">CFDA</a>] Cohen, H., Frey, G., Doche, C., Avanzi, R., Lange, T., |
| 1066 |
Nguyen, K., and F. Vercauteren, "Handbook of Elliptic and |
| 1067 |
Hyperelliptic Curve Cryptography", Chapman & Hall CRC |
| 1068 |
Press, 2006. |
| 1069 |
|
| 1070 |
[<a id="ref-HMV">HMV</a>] Hankerson, D., Menezes, A., and S. Vanstone, "Guide to |
| 1071 |
Elliptic Curve Cryptography", Springer Verlag, 2004. |
| 1072 |
|
| 1073 |
[<a id="ref-HR">HR</a>] Huang, M. and W. Raskind, "Signature Calculus and the |
| 1074 |
Discrete Logarithm Problem for Elliptic Curves |
| 1075 |
(Preliminary Version)", Unpublished Preprint, 2006, |
| 1076 |
<<a href="http://www-rcf.usc.edu/~mdhuang/mypapers/062806dl3.pdf">http://www-rcf.usc.edu/~mdhuang/mypapers/062806dl3.pdf</a>>. |
| 1077 |
|
| 1078 |
[<a id="ref-ISO1">ISO1</a>] International Organization for Standardization, |
| 1079 |
"Information Technology - Security Techniques - Digital |
| 1080 |
Signatures with Appendix - Part 3: Discrete Logarithm |
| 1081 |
Based Mechanisms", ISO/IEC 14888-3, 2006. |
| 1082 |
|
| 1083 |
[<a id="ref-ISO2">ISO2</a>] International Organization for Standardization, |
| 1084 |
"Information Technology - Security Techniques - |
| 1085 |
Cryptographic Techniques Based on Elliptic Curves - Part |
| 1086 |
2: Digital signatures", ISO/IEC 15946-2, 2002. |
| 1087 |
|
| 1088 |
[<a id="ref-ISO3">ISO3</a>] International Organization for Standardization, |
| 1089 |
"Information Technology - Security Techniques - Prime |
| 1090 |
Number Generation", ISO/IEC 18032, 2005. |
| 1091 |
|
| 1092 |
[<a id="ref-JMV">JMV</a>] Jao, D., Miller, SD., and R. Venkatesan, "Ramanujan Graphs |
| 1093 |
and the Random Reducibility of Discrete Log on Isogenous |
| 1094 |
Elliptic Curves", IACR Cryptology ePrint Archive 2004/312, |
| 1095 |
2004. |
| 1096 |
|
| 1097 |
[<a id="ref-RFC3279">RFC3279</a>] Bassham, L., Polk, W., and R. Housley, "Algorithms and |
| 1098 |
Identifiers for the Internet X.509 Public Key |
| 1099 |
Infrastructure Certificate and Certificate Revocation List |
| 1100 |
(CRL) Profile", <a href="./rfc3279">RFC 3279</a>, April 2002. |
| 1101 |
|
| 1102 |
[<a id="ref-RFC4050">RFC4050</a>] Blake-Wilson, S., Karlinger, G., Kobayashi, T., and Y. |
| 1103 |
Wang, "Using the Elliptic Curve Signature Algorithm |
| 1104 |
(ECDSA) for XML Digital Signatures", <a href="./rfc4050">RFC 4050</a>, April 2005. |
| 1105 |
|
| 1106 |
[<a id="ref-RFC4492">RFC4492</a>] Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., and B. |
| 1107 |
Moeller, "Elliptic Curve Cryptography (ECC) Cipher Suites |
| 1108 |
for Transport Layer Security (TLS)", <a href="./rfc4492">RFC 4492</a>, May 2006. |
| 1109 |
|
| 1110 |
[<a id="ref-RFC4754">RFC4754</a>] Fu, D. and J. Solinas, "IKE and IKEv2 Authentication Using |
| 1111 |
the Elliptic Curve Digital Signature Algorithm (ECDSA)", |
| 1112 |
<a href="./rfc4754">RFC 4754</a>, January 2007. |
| 1113 |
|
| 1114 |
|
| 1115 |
|
| 1116 |
<span class="grey">Lochter & Merkle Informational [Page 20]</span></pre> |
| 1117 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span> |
| 1118 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1119 |
|
| 1120 |
|
| 1121 |
[<a id="ref-RFC5753">RFC5753</a>] Turner, S. and D. Brown, "Use of Elliptic Curve |
| 1122 |
Cryptography (ECC) Algorithms in Cryptographic Message |
| 1123 |
Syntax (CMS)", <a href="./rfc5753">RFC 5753</a>, January 2010. |
| 1124 |
|
| 1125 |
[<a id="ref-SA">SA</a>] Satoh, T. and K. Araki, "Fermat Quotients and the |
| 1126 |
Polynomial Time Discrete Log Algorithm for Anomalous |
| 1127 |
Elliptic Curves", Commentarii Mathematici Universitatis |
| 1128 |
Sancti Pauli 47, 1998. |
| 1129 |
|
| 1130 |
[<a id="ref-SEC1">SEC1</a>] Certicom Research, "Elliptic Curve Cryptography", |
| 1131 |
Standards for Efficient Cryptography (SEC) 1, September |
| 1132 |
2000. |
| 1133 |
|
| 1134 |
[<a id="ref-SEC2">SEC2</a>] Certicom Research, "Recommended Elliptic Curve Domain |
| 1135 |
Parameters", Standards for Efficient Cryptography (SEC) 2, |
| 1136 |
September 2000. |
| 1137 |
|
| 1138 |
[<a id="ref-Sem">Sem</a>] Semaev, I., "Evaluation of Discrete Logarithms on Some |
| 1139 |
Elliptic Curves", Mathematics of Computation 67, 1998. |
| 1140 |
|
| 1141 |
[<a id="ref-Sma">Sma</a>] Smart, N., "The Discrete Logarithm Problem on Elliptic |
| 1142 |
Curves of Trace One", Journal of Cryptology 12, 1999. |
| 1143 |
|
| 1144 |
|
| 1145 |
|
| 1146 |
|
| 1147 |
|
| 1148 |
|
| 1149 |
|
| 1150 |
|
| 1151 |
|
| 1152 |
|
| 1153 |
|
| 1154 |
|
| 1155 |
|
| 1156 |
|
| 1157 |
|
| 1158 |
|
| 1159 |
|
| 1160 |
|
| 1161 |
|
| 1162 |
|
| 1163 |
|
| 1164 |
|
| 1165 |
|
| 1166 |
|
| 1167 |
|
| 1168 |
|
| 1169 |
|
| 1170 |
|
| 1171 |
|
| 1172 |
<span class="grey">Lochter & Merkle Informational [Page 21]</span></pre> |
| 1173 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span> |
| 1174 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1175 |
|
| 1176 |
|
| 1177 |
<span class="h2"><a class="selflink" id="appendix-A" href="#appendix-A">Appendix A</a>. Pseudo-Random Generation of Parameters</span> |
| 1178 |
|
| 1179 |
In this appendix, the methods used for pseudo-random generation of |
| 1180 |
the elliptic curve domain parameters are described. A comprehensive |
| 1181 |
description is given in [<a href="#ref-EBP" title=""ECC Brainpool Standard Curves and Curve Generation"">EBP</a>]. |
| 1182 |
|
| 1183 |
Throughout this section the following conventions are used: |
| 1184 |
|
| 1185 |
The conversion between integers x in the range 0 <= x <= 2^L - 1 and |
| 1186 |
bit strings of length L is given by x <--> {x_1,...,x_L} and the |
| 1187 |
binary expansion |
| 1188 |
x = x_1 * 2^(L-1) + x_2 * 2^(L-2) + ... + x_(L-1)*2 + x_L, i.e., the |
| 1189 |
first bit of the bit string corresponds to the most significant bit |
| 1190 |
of the corresponding integer and the last bit to the least |
| 1191 |
significant bit. |
| 1192 |
|
| 1193 |
For a real number x, let floor(x) denote the highest integer less |
| 1194 |
than or equal to x. |
| 1195 |
|
| 1196 |
For updating the seed s of 160-bit length we use the following |
| 1197 |
function update_seed(s): |
| 1198 |
|
| 1199 |
1. Convert s to an integer z. |
| 1200 |
|
| 1201 |
2. Convert (z+1) mod 2^160 to a bit string t and output t. |
| 1202 |
|
| 1203 |
<span class="h3"><a class="selflink" id="appendix-A.1" href="#appendix-A.1">A.1</a>. Generation of Prime Numbers</span> |
| 1204 |
|
| 1205 |
This section describes the systematic selection of the base fields |
| 1206 |
GF(p) proposed in this specification. The prime generation method is |
| 1207 |
similar to the method given in FIPS 186-2 [<a href="#ref-FIPS" title=""Digital Signature Standard (DSS)"">FIPS</a>], Appendix 6.4, and |
| 1208 |
ANSI X9.62 [<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>], A.3.2. It is a modification of the method |
| 1209 |
"incremental search" given in Section 8.2.2 of [<a href="#ref-ISO3" title=""Information Technology - Security Techniques - Prime Number Generation"">ISO3</a>]. |
| 1210 |
|
| 1211 |
For computing an integer x in the range 0 <= x <= 2^L - 1 from a seed |
| 1212 |
s of 160-bit length, we use the following algorithm find_integer(s): |
| 1213 |
|
| 1214 |
1. Set v = floor((L-1)/160) and w = L - 160*v. |
| 1215 |
|
| 1216 |
2. Compute h = SHA-1(s). |
| 1217 |
|
| 1218 |
3. Let h_0 be the bit string obtained by taking the w rightmost bits |
| 1219 |
of h. |
| 1220 |
|
| 1221 |
4. Convert s to an integer z. |
| 1222 |
|
| 1223 |
5. For i from 1 to v do: |
| 1224 |
|
| 1225 |
|
| 1226 |
|
| 1227 |
|
| 1228 |
<span class="grey">Lochter & Merkle Informational [Page 22]</span></pre> |
| 1229 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span> |
| 1230 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1231 |
|
| 1232 |
|
| 1233 |
A. Set z_i = (z+i) mod 2^160. |
| 1234 |
|
| 1235 |
B. Convert z_i to a bit string s_i. |
| 1236 |
|
| 1237 |
C. Set h_i = SHA-1(s_i). |
| 1238 |
|
| 1239 |
6. Let h be the string obtained by the concatenation of h_0,...,h_v |
| 1240 |
from left to right. |
| 1241 |
|
| 1242 |
7. Convert h to an integer x and output x. |
| 1243 |
|
| 1244 |
The following procedure is used to generate an L bit prime p from a |
| 1245 |
160-bit seed s. |
| 1246 |
|
| 1247 |
1. Set c = find_integer(s). |
| 1248 |
|
| 1249 |
2. Let p be the smallest prime p >= c with p = 3 mod 4. |
| 1250 |
|
| 1251 |
3. If 2^(L-1) <= p <= 2^L - 1 output p and stop. |
| 1252 |
|
| 1253 |
4. Set s = update_seed(s) and go to Step 1. |
| 1254 |
|
| 1255 |
For the generation of the primes p used as base fields GF(p) for the |
| 1256 |
curves defined in this specification (and the corresponding twisted |
| 1257 |
curves), the following values (in hexadecimal representation) have |
| 1258 |
been used as initial seed s: |
| 1259 |
|
| 1260 |
Seed_p_160 for brainpoolP160r1: |
| 1261 |
3243F6A8885A308D313198A2E03707344A409382 |
| 1262 |
|
| 1263 |
Seed_p_192 for brainpoolP192r1: |
| 1264 |
2299F31D0082EFA98EC4E6C89452821E638D0137 |
| 1265 |
|
| 1266 |
Seed_p_224 for brainpoolP224r1: |
| 1267 |
7BE5466CF34E90C6CC0AC29B7C97C50DD3F84D5B |
| 1268 |
|
| 1269 |
Seed_p_256 for brainpoolP256r1: |
| 1270 |
5B54709179216D5D98979FB1BD1310BA698DFB5A |
| 1271 |
|
| 1272 |
Seed_p_320 for brainpoolP320r1: |
| 1273 |
C2FFD72DBD01ADFB7B8E1AFED6A267E96BA7C904 |
| 1274 |
|
| 1275 |
Seed_p_384 for brainpoolP384r1: |
| 1276 |
5F12C7F9924A19947B3916CF70801F2E2858EFC1 |
| 1277 |
|
| 1278 |
Seed_p_512 for brainpoolP512r1: |
| 1279 |
6636920D871574E69A458FEA3F4933D7E0D95748 |
| 1280 |
|
| 1281 |
|
| 1282 |
|
| 1283 |
|
| 1284 |
<span class="grey">Lochter & Merkle Informational [Page 23]</span></pre> |
| 1285 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span> |
| 1286 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1287 |
|
| 1288 |
|
| 1289 |
These seeds have been obtained as the first 7 substrings of 160-bit |
| 1290 |
length each of Q = Pi*2^1120, where Pi is the constant 3.14159..., |
| 1291 |
also known as Ludolph's number, i.e., |
| 1292 |
|
| 1293 |
Q = Seed_p_160||Seed_p_192||...||Seed_p_512||Remainder, |
| 1294 |
where || denotes concatenation. |
| 1295 |
|
| 1296 |
Using these seeds and the above algorithm the following primes are |
| 1297 |
obtained: |
| 1298 |
|
| 1299 |
p_160 = 1332297598440044874827085558802491743757193798159 |
| 1300 |
|
| 1301 |
p_192 = 4781668983906166242955001894344923773259119655253013193367 |
| 1302 |
|
| 1303 |
p_224 = 2272162293245435278755253799591092807334073214594499230443 |
| 1304 |
5472941311 |
| 1305 |
|
| 1306 |
p_256 = 7688495639704534422080974662900164909303795020094305520373 |
| 1307 |
5601445031516197751 |
| 1308 |
|
| 1309 |
p_320 = 1763593322239166354161909842446019520889512772719515192772 |
| 1310 |
9604152886408688021498180955014999035278 |
| 1311 |
|
| 1312 |
p_384 = 2165927077011931617306923684233260497979611638701764860008 |
| 1313 |
1618503821089934025961822236561982844534088440708417973331 |
| 1314 |
|
| 1315 |
p_512 = 8948962207650232551656602815159153422162609644098354511344 |
| 1316 |
597187200057010413552439917934304191956942765446530386427345937963 |
| 1317 |
894309923928536070534607816947 |
| 1318 |
|
| 1319 |
<span class="h3"><a class="selflink" id="appendix-A.2" href="#appendix-A.2">A.2</a>. Generation of Pseudo-Random Curves</span> |
| 1320 |
|
| 1321 |
The generation procedure is similar to the procedure given in FIPS |
| 1322 |
PUB 186-2 [<a href="#ref-FIPS" title=""Digital Signature Standard (DSS)"">FIPS</a>], Appendix 6.4, and ANSI X9.62 [<a href="#ref-ANSI1" title=""Public Key Cryptography For The Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)"">ANSI1</a>], A.3.2. |
| 1323 |
|
| 1324 |
For computing an integer x in the range 0 <= x <= 2^(L-1) - 1 from a |
| 1325 |
seed s of 160-bit length, we use the algorithm find_integer_2(s), |
| 1326 |
which slightly differs from the method used for the generation of the |
| 1327 |
primes. |
| 1328 |
|
| 1329 |
1. Set v = floor((L-1)/160) and w = L - 160*v - 1. |
| 1330 |
|
| 1331 |
2. Compute h = SHA-1(s). |
| 1332 |
|
| 1333 |
3. Let h_0 be the bit string obtained by taking the w rightmost bits |
| 1334 |
of h. |
| 1335 |
|
| 1336 |
4. Convert s to an integer z. |
| 1337 |
|
| 1338 |
|
| 1339 |
|
| 1340 |
<span class="grey">Lochter & Merkle Informational [Page 24]</span></pre> |
| 1341 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-25" ></span> |
| 1342 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1343 |
|
| 1344 |
|
| 1345 |
5. For i from 1 to v do: |
| 1346 |
|
| 1347 |
A. Set z_i = (z+i) mod 2^160. |
| 1348 |
|
| 1349 |
B. Convert z_i to a bit string s_i. |
| 1350 |
|
| 1351 |
C. Set h_i = SHA-1(s_i). |
| 1352 |
|
| 1353 |
6. Let h be the string obtained by the concatenation of h_0,...,h_v |
| 1354 |
from left to right. |
| 1355 |
|
| 1356 |
7. Convert h to an integer x and output x. |
| 1357 |
|
| 1358 |
The following procedure is used to generate the parameters A and B of |
| 1359 |
a suitable elliptic curve over GF(p) and a base point G from a prime |
| 1360 |
p of bit length L and a 160-bit seed s. |
| 1361 |
|
| 1362 |
1. Set h = find_integer_2(s). |
| 1363 |
|
| 1364 |
2. Convert h to an integer A. |
| 1365 |
|
| 1366 |
3. If -3 = A*Z^4 mod p is not solvable, then set s = update_seed(s) |
| 1367 |
and go to Step 1. |
| 1368 |
|
| 1369 |
4. Compute one solution Z of -3 = A*Z^4 mod p. |
| 1370 |
|
| 1371 |
5. Set s = update_seed(s). |
| 1372 |
|
| 1373 |
6. Set B = find_integer_2(s). |
| 1374 |
|
| 1375 |
7. If B is a square mod p, then set s = update_seed(s) and go to |
| 1376 |
Step 6. |
| 1377 |
|
| 1378 |
8. If 4*A^3 + 27*B^2 = 0 mod p, then set s = update_seed(s) and go |
| 1379 |
to Step 1. |
| 1380 |
|
| 1381 |
9. Check that the elliptic curve E over GF(p) given by y^2 = x^3 + |
| 1382 |
A*x + B fulfills all security and functional requirements given |
| 1383 |
in <a href="#section-3">Section 3</a>. If not, then set s = update_seed(s) and go to Step |
| 1384 |
1. |
| 1385 |
|
| 1386 |
10. Set s = update_seed(s). |
| 1387 |
|
| 1388 |
11. Set k = find_integer_2(s). |
| 1389 |
|
| 1390 |
12. Determine the points Q and -Q having the smallest x-coordinate in |
| 1391 |
E(GF(p)). Randomly select one of them as point P. |
| 1392 |
|
| 1393 |
|
| 1394 |
|
| 1395 |
|
| 1396 |
<span class="grey">Lochter & Merkle Informational [Page 25]</span></pre> |
| 1397 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-26" ></span> |
| 1398 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1399 |
|
| 1400 |
|
| 1401 |
13. Compute the base point G = k * P. |
| 1402 |
|
| 1403 |
14. Output A, B, and G. |
| 1404 |
|
| 1405 |
Note: Of course P could also be used as a base point. However, the |
| 1406 |
small x-coordinate of P could possibly render the curve vulnerable to |
| 1407 |
side-channel attacks. |
| 1408 |
|
| 1409 |
For the generation of curve parameters A and B, and the base points G |
| 1410 |
defined in this specification, the following values (in hexadecimal |
| 1411 |
representation) have been used as initial seed s: |
| 1412 |
|
| 1413 |
Seed_ab_160 for brainpoolP160r1: |
| 1414 |
2B7E151628AED2A6ABF7158809CF4F3C762E7160 |
| 1415 |
|
| 1416 |
Seed_ab_192 for brainpoolP192r1: |
| 1417 |
F38B4DA56A784D9045190CFEF324E7738926CFBE |
| 1418 |
|
| 1419 |
Seed_ab_224 for brainpoolP224r1: |
| 1420 |
5F4BF8D8D8C31D763DA06C80ABB1185EB4F7C7B5 |
| 1421 |
|
| 1422 |
Seed_ab_256 for brainpoolP256r1: |
| 1423 |
757F5958490CFD47D7C19BB42158D9554F7B46BC |
| 1424 |
|
| 1425 |
Seed_ab_320 for brainpoolP320r1: |
| 1426 |
ED55C4D79FD5F24D6613C31C3839A2DDF8A9A276 |
| 1427 |
|
| 1428 |
Seed_ab_384 for brainpoolP384r1: |
| 1429 |
BCFBFA1C877C56284DAB79CD4C2B3293D20E9E5E |
| 1430 |
|
| 1431 |
Seed_ab_512 for brainpoolP384r1: |
| 1432 |
AF02AC60ACC93ED874422A52ECB238FEEE5AB6AD |
| 1433 |
|
| 1434 |
These seeds have been obtained as the first 7 substrings of 160-bit |
| 1435 |
length each of R = floor(e*2^1120), where e denotes the constant |
| 1436 |
2.71828..., also known as Euler's number, i.e., |
| 1437 |
|
| 1438 |
R = Seed_ab_160||Seed_ab_192||...||Seed_ab_512||Remainder, |
| 1439 |
where || denotes concatenation. |
| 1440 |
|
| 1441 |
|
| 1442 |
|
| 1443 |
|
| 1444 |
|
| 1445 |
|
| 1446 |
|
| 1447 |
|
| 1448 |
|
| 1449 |
|
| 1450 |
|
| 1451 |
|
| 1452 |
<span class="grey">Lochter & Merkle Informational [Page 26]</span></pre> |
| 1453 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-27" ></span> |
| 1454 |
<span class="grey"><a href="./rfc5639">RFC 5639</a> ECC Brainpool Standard Curves & Curve Generation March 2010</span> |
| 1455 |
|
| 1456 |
|
| 1457 |
Authors' Addresses |
| 1458 |
|
| 1459 |
Manfred Lochter |
| 1460 |
Bundesamt fuer Sicherheit in der Informationstechnik (BSI) |
| 1461 |
Postfach 200363 |
| 1462 |
53133 Bonn |
| 1463 |
Germany |
| 1464 |
|
| 1465 |
Phone: +49 228 9582 5643 |
| 1466 |
EMail: [email protected] |
| 1467 |
|
| 1468 |
|
| 1469 |
Johannes Merkle |
| 1470 |
secunet Security Networks |
| 1471 |
Mergenthaler Allee 77 |
| 1472 |
65760 Eschborn |
| 1473 |
Germany |
| 1474 |
|
| 1475 |
Phone: +49 201 5454 2021 |
| 1476 |
EMail: [email protected] |
| 1477 |
|
| 1478 |
|
| 1479 |
|
| 1480 |
|
| 1481 |
|
| 1482 |
|
| 1483 |
|
| 1484 |
|
| 1485 |
|
| 1486 |
|
| 1487 |
|
| 1488 |
|
| 1489 |
|
| 1490 |
|
| 1491 |
|
| 1492 |
|
| 1493 |
|
| 1494 |
|
| 1495 |
|
| 1496 |
|
| 1497 |
|
| 1498 |
|
| 1499 |
|
| 1500 |
|
| 1501 |
|
| 1502 |
|
| 1503 |
|
| 1504 |
|
| 1505 |
|
| 1506 |
|
| 1507 |
|
| 1508 |
Lochter & Merkle Informational [Page 27] |
| 1509 |
</pre> |