ecp_8cpp-source.html

来自「Crypto++是一个非常强大的密码学库,主要是功能全」· HTML 代码 · 共 484 行 · 第 1/3 页

00156 
00157 <span class="keywordtype">bool</span> ECP::ValidateParameters(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &amp;rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> level)<span class="keyword"> const</span>
00158 <span class="keyword"></span>{
00159         <a class="code" href="class_integer.html">Integer</a> p = FieldSize();
00160 
00161         <span class="keywordtype">bool</span> pass = p.<a class="code" href="class_integer.html#_integerz41_15">IsOdd</a>();
00162         pass = pass &amp;&amp; !m_a.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>() &amp;&amp; m_a&lt;p &amp;&amp; !m_b.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>() &amp;&amp; m_b&lt;p;
00163 
00164         <span class="keywordflow">if</span> (level &gt;= 1)
00165                 pass = pass &amp;&amp; ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
00166 
00167         <span class="keywordflow">if</span> (level &gt;= 2)
00168                 pass = pass &amp;&amp; VerifyPrime(rng, p);
00169 
00170         <span class="keywordflow">return</span> pass;
00171 }
00172 
00173 <span class="keywordtype">bool</span> ECP::VerifyPoint(<span class="keyword">const</span> Point &amp;P)<span class="keyword"> const</span>
00174 <span class="keyword"></span>{
00175         <span class="keyword">const</span> FieldElement &amp;x = P.x, &amp;y = P.y;
00176         <a class="code" href="class_integer.html">Integer</a> p = FieldSize();
00177         <span class="keywordflow">return</span> P.identity ||
00178                 (!x.IsNegative() &amp;&amp; x&lt;p &amp;&amp; !y.<a class="code" href="class_integer.html#_integerz41_10">IsNegative</a>() &amp;&amp; y&lt;p
00179                 &amp;&amp; !(((x*x+m_a)*x+m_b-y*y)%p));
00180 }
00181 
00182 <span class="keywordtype">bool</span> ECP::Equal(<span class="keyword">const</span> Point &amp;P, <span class="keyword">const</span> Point &amp;Q)<span class="keyword"> const</span>
00183 <span class="keyword"></span>{
00184         <span class="keywordflow">if</span> (P.identity &amp;&amp; Q.identity)
00185                 <span class="keywordflow">return</span> <span class="keyword">true</span>;
00186 
00187         <span class="keywordflow">if</span> (P.identity &amp;&amp; !Q.identity)
00188                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00189 
00190         <span class="keywordflow">if</span> (!P.identity &amp;&amp; Q.identity)
00191                 <span class="keywordflow">return</span> <span class="keyword">false</span>;
00192 
00193         <span class="keywordflow">return</span> (GetField().<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa17">Equal</a>(P.x,Q.x) &amp;&amp; GetField().<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa17">Equal</a>(P.y,Q.y));
00194 }
00195 
00196 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html">ECP::Point</a>&amp; ECP::Identity()<span class="keyword"> const</span>
00197 <span class="keyword"></span>{
00198         <span class="keyword">static</span> <span class="keyword">const</span> Point zero;
00199         <span class="keywordflow">return</span> zero;
00200 }
00201 
00202 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html">ECP::Point</a>&amp; ECP::Inverse(<span class="keyword">const</span> Point &amp;P)<span class="keyword"> const</span>
00203 <span class="keyword"></span>{
00204         <span class="keywordflow">if</span> (P.identity)
00205                 <span class="keywordflow">return</span> P;
00206         <span class="keywordflow">else</span>
00207         {
00208                 m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo0">identity</a> = <span class="keyword">false</span>;
00209                 m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo1">x</a> = P.x;
00210                 m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo2">y</a> = GetField().<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa24">Inverse</a>(P.y);
00211                 <span class="keywordflow">return</span> m_R;
00212         }
00213 }
00214 
00215 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html">ECP::Point</a>&amp; ECP::Add(<span class="keyword">const</span> Point &amp;P, <span class="keyword">const</span> Point &amp;Q)<span class="keyword"> const</span>
00216 <span class="keyword"></span>{
00217         <span class="keywordflow">if</span> (P.identity) <span class="keywordflow">return</span> Q;
00218         <span class="keywordflow">if</span> (Q.identity) <span class="keywordflow">return</span> P;
00219         <span class="keywordflow">if</span> (GetField().<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa17">Equal</a>(P.x, Q.x))
00220                 <span class="keywordflow">return</span> GetField().<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa17">Equal</a>(P.y, Q.y) ? Double(P) : Identity();
00221 
00222         FieldElement t = GetField().<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa26">Subtract</a>(Q.y, P.y);
00223         t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
00224         FieldElement x = GetField().Subtract(GetField().Subtract(GetField().<a class="code" href="class_square.html">Square</a>(t), P.x), Q.x);
00225         m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo2">y</a> = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo2">y</a>);
00226 
00227         m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo1">x</a>.<a class="code" href="class_integer.html#_integerz43_20">swap</a>(x);
00228         m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo0">identity</a> = <span class="keyword">false</span>;
00229         <span class="keywordflow">return</span> m_R;
00230 }
00231 
00232 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html">ECP::Point</a>&amp; ECP::Double(<span class="keyword">const</span> Point &amp;P)<span class="keyword"> const</span>
00233 <span class="keyword"></span>{
00234         <span class="keywordflow">if</span> (P.identity || P.y==GetField().Identity()) <span class="keywordflow">return</span> Identity();
00235 
00236         FieldElement t = GetField().Square(P.x);
00237         t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
00238         t = GetField().Divide(t, GetField().Double(P.y));
00239         FieldElement x = GetField().Subtract(GetField().Subtract(GetField().<a class="code" href="class_square.html">Square</a>(t), P.x), P.x);
00240         m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo2">y</a> = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo2">y</a>);
00241 
00242         m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo1">x</a>.<a class="code" href="class_integer.html#_integerz43_20">swap</a>(x);
00243         m_R.<a class="code" href="struct_e_c_p_point.html#_e_c_p_pointo0">identity</a> = <span class="keyword">false</span>;
00244         <span class="keywordflow">return</span> m_R;
00245 }
00246 
00247 <span class="keyword">template</span> &lt;<span class="keyword">class</span> T, <span class="keyword">class</span> Iterator&gt; <span class="keywordtype">void</span> ParallelInvert(<span class="keyword">const</span> <a class="code" href="class_abstract_ring.html">AbstractRing&lt;T&gt;</a> &amp;ring, Iterator begin, Iterator end)
00248 {
00249         <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> n = end-begin;
00250         <span class="keywordflow">if</span> (n == 1)
00251                 *begin = ring.<a class="code" href="class_abstract_ring.html#_abstract_ringa6">MultiplicativeInverse</a>(*begin);
00252         <span class="keywordflow">else</span> <span class="keywordflow">if</span> (n &gt; 1)
00253         {
00254                 std::vector&lt;T&gt; vec((n+1)/2);
00255                 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
00256                 Iterator it;
00257 
00258                 <span class="keywordflow">for</span> (i=0, it=begin; i&lt;n/2; i++, it+=2)
00259                         vec[i] = ring.<a class="code" href="class_abstract_ring.html#_abstract_ringa5">Multiply</a>(*it, *(it+1));
00260                 <span class="keywordflow">if</span> (n%2 == 1)
00261                         vec[n/2] = *it;
00262 
00263                 ParallelInvert(ring, vec.begin(), vec.end());
00264 
00265                 <span class="keywordflow">for</span> (i=0, it=begin; i&lt;n/2; i++, it+=2)
00266                 {
00267                         <span class="keywordflow">if</span> (!vec[i])
00268                         {
00269                                 *it = ring.<a class="code" href="class_abstract_ring.html#_abstract_ringa6">MultiplicativeInverse</a>(*it);
00270                                 *(it+1) = ring.<a class="code" href="class_abstract_ring.html#_abstract_ringa6">MultiplicativeInverse</a>(*(it+1));
00271                         }
00272                         <span class="keywordflow">else</span>
00273                         {
00274                                 std::swap(*it, *(it+1));
00275                                 *it = ring.<a class="code" href="class_abstract_ring.html#_abstract_ringa5">Multiply</a>(*it, vec[i]);
00276                                 *(it+1) = ring.<a class="code" href="class_abstract_ring.html#_abstract_ringa5">Multiply</a>(*(it+1), vec[i]);
00277                         }
00278                 }
00279                 <span class="keywordflow">if</span> (n%2 == 1)
00280                         *it = vec[n/2];
00281         }
00282 }
00283 
00284 <span class="keyword">struct </span>ProjectivePoint
00285 {
00286         ProjectivePoint() {}
00287         ProjectivePoint(<span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;x, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;y, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;z)
00288                 : x(x), y(y), z(z)      {}
00289 
00290         <a class="code" href="class_integer.html">Integer</a> x,y,z;
00291 };
00292 
00293 <span class="keyword">class </span>ProjectiveDoubling
00294 {
00295 <span class="keyword">public</span>:
00296         ProjectiveDoubling(<span class="keyword">const</span> <a class="code" href="class_modular_arithmetic.html">ModularArithmetic</a> &amp;mr, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;m_a, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &amp;m_b, <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html">ECPPoint</a> &amp;Q)
00297                 : mr(mr), firstDoubling(true), negated(false)
00298         {
00299                 <span class="keywordflow">if</span> (Q.identity)
00300                 {
00301                         sixteenY4 = P.x = P.y = mr.<a class="code" href="class_modular_arithmetic.html#_modular_arithmetica21">MultiplicativeIdentity</a>();
00302                         aZ4 = P.z = mr.<a class="code" href="class_modular_arithmetic.html#_montgomery_representationa19">Identity</a>();
00303                 }
00304                 <span class="keywordflow">else</span>
00305                 {
00306                         P.x = Q.x;
00307                         P.y = Q.y;
00308                         sixteenY4 = P.z = mr.<a class="code" href="class_modular_arithmetic.html#_modular_arithmetica21">MultiplicativeIdentity</a>();
00309                         aZ4 = m_a;
00310                 }
00311         }
00312 
00313         <span class="keywordtype">void</span> Double()
00314         {
00315                 twoY = mr.Double(P.y);
00316                 P.z = mr.Multiply(P.z, twoY);
00317                 fourY2 = mr.Square(twoY);