1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
|
import React from "react";
import Entry from "../../components/entry";
import { Styled } from "theme-ui";
import Link from "../../components/Link";
import Pseudocode from "../../components/Pseudocode";
import { InlineMath } from "react-katex";
export default ({ data, location }) => {
let rfcCodeCommon = `
\\begin{algorithm}
\\caption{RFC5639 UpdateSeed}
\\begin{algorithmic}
\\PROCEDURE{UpdateSeed}{$s$}
\\STATE Convert $s$ to an integer $z$
\\STATE Convert $(z+1) \\mod 2^{160}$ to a bit string $t$
\\RETURN $t$
\\ENDPROCEDURE
\\end{algorithmic}
\\end{algorithm}
`;
let rfcCodePrimes = `
\\begin{algorithm}
\\caption{RFC5639 Verifiably Random Primes}
\\begin{algorithmic}
\\INPUT bit size $L$ of the required prime
\\INPUT 160 bit-string seed $s$
\\PROCEDURE{GeneratePrime}{$s$}
\\STATE Let $c = $ \\CALL{FindInteger}{$s$}
\\STATE Let $p$ be the smallest prime $p \\ge c$ with $p \\equiv 3 \\mod 4$
\\IF{$2^{L-1} \\le p \\le 2^L - 1$}
\\RETURN $p$
\\ENDIF
\\STATE Let $s = $ \\CALL{UpdateSeed}{$s$} and \\textbf{goto} $2$
\\ENDPROCEDURE
\\PROCEDURE{FindInteger}{$s$}
\\STATE Let $v = \\lfloor (L-1) / 160 \\rfloor$ and $w = L - 160v$
\\STATE Compute $h = \\text{SHA-1}(s)$
\\STATE Let $h_0$ be the bit string obtained by taking the $w$ rightmost bits of $h$
\\STATE Convert $s$ to an integer $z$
\\FOR{$i = 1$ \\textbf{to} $v$}
\\STATE Let $z_i = (z + i) \\mod 2^{160}$
\\STATE Convert $z_i$ to bit-string $s_i$
\\STATE Let $h_i = \\text{SHA-1}(s_i)$
\\ENDFOR
\\STATE Let $h$ be the string obtained by the concatenation of $h_0 , \\ldots , h_v$ from left to right
\\STATE Convert $h$ to an integer $x$
\\RETURN $x$
\\ENDPROCEDURE
\\end{algorithmic}
\\end{algorithm}
`;
let rfcCodeCurves = `
\\begin{algorithm}
\\caption{RFC5639 Verifiably Random Curves $\\mathbb{F}_p$}
\\begin{algorithmic}
\\INPUT prime field size $p$ of bit-length $L$
\\INPUT 160 bit-string seed $s$
\\OUTPUT field elements $A, B \\in \\mathbb{F}_p$ which define an elliptic curve $\\mathcal{E}$
\\OUTPUT generator $G$ of the elliptic curve $\\mathcal{E}$
\\PROCEDURE{GenerateCurve}{$p, s$}
\\STATE Let $h = $ \\CALL{FindInteger2}{$s$}
\\STATE Convert $h$ to an integer $A$
\\IF{$-3 \\equiv A*Z^4 \\mod p$ is not solvable}
\\STATE Let $s = $ \\CALL{UpdateSeed}{$s$} and \\textbf{goto} $2$
\\ENDIF
\\STATE Compute one solution $Z$ of $-3 \\equiv A*Z^4 \\mod p$
\\STATE Let $s = $ \\CALL{UpdateSeed}{$s$}
\\STATE Let $B = $ \\CALL{FindInteger2}{$s$}
\\IF{$B$ is a square $\\mod p$}
\\STATE Let $s = $ \\CALL{UpdateSeed}{$s$} and \\textbf{goto} $8$
\\ENDIF
\\IF{$4*A^3 + 27*B^2 \\equiv 0 \\mod p$}
\\STATE Let $s = $ \\CALL{UpdateSeed}{s} and \\textbf{goto} $2$
\\ENDIF
\\STATE Check that the elliptic curve $\\mathcal{E}$ over $\\mathbb{F}_p$ given by $y^2 = x^3 + A x + B$ fulfills all security and functional requirements
\\STATE Let $s = $ \\CALL{UpdateSeed}{$s$}
\\STATE Let $k = $ \\CALL{FindInteger2}{$s$}
\\STATE Determine the points $Q$ and $-Q$ having the smallest x-coordinate on $\\mathcal{E}(\\mathbb{F}_p)$. Randomly select one of them as point $P$
\\STATE Compute the base point $G = [k]P$.
\\RETURN ($A, B, G$)
\\ENDPROCEDURE
\\PROCEDURE{FindInteger2}{$s$}
\\STATE Let $v = \\lfloor (L-1) / 160 \\rfloor$ and $w = L - 160v - 1$
\\STATE Compute $h = \\text{SHA-1}(s)$
\\STATE Let $h_0$ be the bit string obtained by taking the $w$ rightmost bits of $h$
\\STATE Convert $s$ to an integer $z$
\\FOR{$i = 1$ \\textbf{to} $v$}
\\STATE Let $z_i = (z + i) \\mod 2^{160}$
\\STATE Convert $z_i$ to bit-string $s_i$
\\STATE Let $h_i = \\text{SHA-1}(s_i)$
\\ENDFOR
\\STATE Let $h$ be the string obtained by the concatenation of $h_0 , \\ldots , h_v$ from left to right
\\STATE Convert $h$ to an integer $x$
\\RETURN $x$
\\ENDPROCEDURE
\\end{algorithmic}
\\end{algorithm}`;
return (
<Entry data={data} location={location} title={"Brainpool"}>
<Styled.h2>Brainpool</Styled.h2>
<Styled.h3>Technical requirements</Styled.h3>
<ul>
<li>
For each of the bit-lengths{" "}
<InlineMath>160, 192, 224, 256, 320, 384, 512</InlineMath> one curve
shall be proposed.
</li>
<li>
The base field size <InlineMath>p</InlineMath> should be congruent to{" "}
<InlineMath>{`3 \\mod 4`}</InlineMath>.
</li>
<li>
The curve should be <InlineMath>{`\\mathbb{F}_p`}</InlineMath>
-isomorphic to a curve with{" "}
<InlineMath>{`A \\equiv -3 \\mod p`}</InlineMath>.
</li>
<li>
The prime <InlineMath>p</InlineMath> must not be of a special form in
order to avoid patented fast arithmetic on the base field.
</li>
<li>
The order of the curve{" "}
<InlineMath>{`\\lvert \\mathcal{E}(\\mathbb{F}_p) \\rvert`}</InlineMath>{" "}
should be smaller than the size of the base field{" "}
<InlineMath>p</InlineMath>.
</li>
<li>
The curve coefficient <InlineMath>B</InlineMath> should be non-square
in <InlineMath>{`\\mathbb{F}_p`}</InlineMath>.
</li>
</ul>
<Styled.h3>Security requirements</Styled.h3>
<ul>
<li>
The embedding degree{" "}
<InlineMath>{`l = \\min\\{t \\vert q \\text{divides} p^t - 1 \\}`}</InlineMath>{" "}
should be large, where <InlineMath>q</InlineMath> is the order of the
basepoint and <InlineMath>p</InlineMath> the size of the base field.
Specifically, <InlineMath>{`(q - 1) / l < 100`}</InlineMath>.
</li>
<li>
The curves are not trace one curves. Specifically{" "}
<InlineMath>{`\\lvert \\mathcal{E}(\\mathbb{F}_p) \\rvert \\ne p`}</InlineMath>
.
</li>
<li>
The class number of the maximal order of the endomorphism ring of the
curve is larger than <InlineMath>10000000</InlineMath>.
</li>
<li>
The group order{" "}
<InlineMath>{`\\lvert \\mathcal{E}(\\mathbb{F}_p) \\rvert`}</InlineMath>{" "}
should be a prime number <InlineMath>q</InlineMath>.
</li>
</ul>
<Styled.h3>Original method</Styled.h3>
Brainpool published their method of generating verifiably random curves in
the <b>ECC Brainpool Standard Curves and Curve Generation</b>{" "}
<Link to="#brainpool-std">[1]</Link> document, along with generated domain
parameters claimed to be generated using the presented method and seeds.
However, the presented <Link to={"/brainpool/"}>curves</Link> were (with
the exception of the 512-bit curves) <b>not</b> generated using the
presented method, as they have properties that can not result from the
presented method of generating curves. See the <b>BADA55 paper</b>{" "}
<Link to="bada55-brainpool">[3]</Link> for more information.
<Styled.h3>RFC 5639 method</Styled.h3>
Brainpool published an RFC with their fixed method of generating
verifiably random curves and generated curves in <b>RFC 5639</b>{" "}
<Link to="#rfc-5639">[2]</Link>, which matches the generated curves and
seeds.
<pre>
<Pseudocode
code={rfcCodeCommon}
options={{ lineNumber: true, noEnd: true, captionCount: 0 }}
/>
</pre>
<Styled.h4>Generating primes</Styled.h4>
<pre>
<Pseudocode
code={rfcCodePrimes}
options={{ lineNumber: true, noEnd: true, captionCount: 1 }}
/>
</pre>
<Styled.h4>Generating curves</Styled.h4>
<pre>
<Pseudocode
code={rfcCodeCurves}
options={{ lineNumber: true, noEnd: true, captionCount: 2 }}
/>
</pre>
<Styled.h4>References</Styled.h4>
<ol>
<li id="brainpool-std">
Manfred Lochter:{" "}
<Link to="http://www.ecc-brainpool.org/download/Domain-parameters.pdf">
ECC Brainpool Standard Curves and Curve Generation v. 1.0
</Link>
,{" "}
<Link to="https://web.archive.org/web/20170921224120/http://www.ecc-brainpool.org/download/Domain-parameters.pdf">
[archive]
</Link>
</li>
<li id="rfc-5639">
Manfred Lochter, Johannes Merkle:{" "}
<Link to="https://tools.ietf.org/html/rfc5639">
Elliptic Curve Cryptography (ECC) Brainpool Standard Curves and
Curve Generation (RFC5639)
</Link>
</li>
<li id="bada55-brainpool">
BADA55 Research Team:{" "}
<Link to="https://bada55.cr.yp.to/brainpool.html">
BADA55 Crypto - Brainpool curves
</Link>
</li>
</ol>
</Entry>
);
};
|
