<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>Crypto++: ecp.cpp Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.1 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</span></a></li>
</ul>
</div>
<h1>ecp.cpp</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// ecp.cpp - written and placed in the public domain by Wei Dai</span>
<a name="l00002"></a>00002
<a name="l00003"></a>00003 <span class="preprocessor">#include "pch.h"</span>
<a name="l00004"></a>00004
<a name="l00005"></a>00005 <span class="preprocessor">#ifndef CRYPTOPP_IMPORTS</span>
<a name="l00006"></a>00006 <span class="preprocessor"></span>
<a name="l00007"></a>00007 <span class="preprocessor">#include "ecp.h"</span>
<a name="l00008"></a>00008 <span class="preprocessor">#include "asn.h"</span>
<a name="l00009"></a>00009 <span class="preprocessor">#include "nbtheory.h"</span>
<a name="l00010"></a>00010
<a name="l00011"></a>00011 <span class="preprocessor">#include "algebra.cpp"</span>
<a name="l00012"></a>00012
<a name="l00013"></a>00013 NAMESPACE_BEGIN(CryptoPP)
<a name="l00014"></a>00014
<a name="l00015"></a>00015 ANONYMOUS_NAMESPACE_BEGIN
<a name="l00016"></a>00016 static inline <a class="code" href="class_e_c_p.html" title="Elliptic Curve over GF(p), where p is prime.">ECP</a>::Point ToMontgomery(const <a class="code" href="class_modular_arithmetic.html" title="ring of congruence classes modulo n">ModularArithmetic</a> &mr, const <a class="code" href="class_e_c_p.html" title="Elliptic Curve over GF(p), where p is prime.">ECP</a>::Point &P)
<a name="l00017"></a>00017 {
<a name="l00018"></a>00018 <span class="keywordflow">return</span> P.identity ? P : <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a>(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
<a name="l00019"></a>00019 }
<a name="l00020"></a>00020
<a name="l00021"></a>00021 <span class="keyword">static</span> <span class="keyword">inline</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> FromMontgomery(<span class="keyword">const</span> <a class="code" href="class_modular_arithmetic.html" title="ring of congruence classes modulo n">ModularArithmetic</a> &mr, <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> &P)
<a name="l00022"></a>00022 {
<a name="l00023"></a>00023 <span class="keywordflow">return</span> P.identity ? P : <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a>(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
<a name="l00024"></a>00024 }
<a name="l00025"></a>00025 NAMESPACE_END
<a name="l00026"></a>00026
<a name="l00027"></a>00027 ECP::ECP(<span class="keyword">const</span> <a class="code" href="class_e_c_p.html" title="Elliptic Curve over GF(p), where p is prime.">ECP</a> &ecp, <span class="keywordtype">bool</span> convertToMontgomeryRepresentation)
<a name="l00028"></a>00028 {
<a name="l00029"></a>00029 <span class="keywordflow">if</span> (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
<a name="l00030"></a>00030 {
<a name="l00031"></a>00031 m_fieldPtr.reset(<span class="keyword">new</span> <a class="code" href="class_montgomery_representation.html" title="do modular arithmetics in Montgomery representation for increased speed">MontgomeryRepresentation</a>(ecp.GetField().GetModulus()));
<a name="l00032"></a>00032 m_a = GetField().ConvertIn(ecp.m_a);
<a name="l00033"></a>00033 m_b = GetField().ConvertIn(ecp.m_b);
<a name="l00034"></a>00034 }
<a name="l00035"></a>00035 <span class="keywordflow">else</span>
<a name="l00036"></a>00036 operator=(ecp);
<a name="l00037"></a>00037 }
<a name="l00038"></a>00038
<a name="l00039"></a>00039 ECP::ECP(<a class="code" href="class_buffered_transformation.html" title="interface for buffered transformations">BufferedTransformation</a> &bt)
<a name="l00040"></a>00040 : m_fieldPtr(new Field(bt))
<a name="l00041"></a>00041 {
<a name="l00042"></a>00042 <a class="code" href="class_b_e_r_sequence_decoder.html" title="BER Sequence Decoder.">BERSequenceDecoder</a> seq(bt);
<a name="l00043"></a>00043 GetField().BERDecodeElement(seq, m_a);
<a name="l00044"></a>00044 GetField().BERDecodeElement(seq, m_b);
<a name="l00045"></a>00045 <span class="comment">// skip optional seed</span>
<a name="l00046"></a>00046 <span class="keywordflow">if</span> (!seq.EndReached())
<a name="l00047"></a>00047 {
<a name="l00048"></a>00048 <a class="code" href="class_sec_block.html" title="a block of memory allocated using A">SecByteBlock</a> seed;
<a name="l00049"></a>00049 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> unused;
<a name="l00050"></a>00050 BERDecodeBitString(seq, seed, unused);
<a name="l00051"></a>00051 }
<a name="l00052"></a>00052 seq.MessageEnd();
<a name="l00053"></a>00053 }
<a name="l00054"></a>00054
<a name="l00055"></a>00055 <span class="keywordtype">void</span> ECP::DEREncode(<a class="code" href="class_buffered_transformation.html" title="interface for buffered transformations">BufferedTransformation</a> &bt)<span class="keyword"> const</span>
<a name="l00056"></a>00056 <span class="keyword"></span>{
<a name="l00057"></a>00057 GetField().DEREncode(bt);
<a name="l00058"></a>00058 <a class="code" href="class_d_e_r_sequence_encoder.html" title="DER Sequence Encoder.">DERSequenceEncoder</a> seq(bt);
<a name="l00059"></a>00059 GetField().DEREncodeElement(seq, m_a);
<a name="l00060"></a>00060 GetField().DEREncodeElement(seq, m_b);
<a name="l00061"></a>00061 seq.MessageEnd();
<a name="l00062"></a>00062 }
<a name="l00063"></a>00063
<a name="l00064"></a>00064 <span class="keywordtype">bool</span> ECP::DecodePoint(<a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> &P, <span class="keyword">const</span> byte *encodedPoint, <span class="keywordtype">size_t</span> encodedPointLen)<span class="keyword"> const</span>
<a name="l00065"></a>00065 <span class="keyword"></span>{
<a name="l00066"></a>00066 <a class="code" href="class_string_store.html" title="string-based implementation of Store interface">StringStore</a> store(encodedPoint, encodedPointLen);
<a name="l00067"></a>00067 <span class="keywordflow">return</span> DecodePoint(P, store, encodedPointLen);
<a name="l00068"></a>00068 }
<a name="l00069"></a>00069
<a name="l00070"></a>00070 <span class="keywordtype">bool</span> ECP::DecodePoint(<a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> &P, <a class="code" href="class_buffered_transformation.html" title="interface for buffered transformations">BufferedTransformation</a> &bt, <span class="keywordtype">size_t</span> encodedPointLen)<span class="keyword"> const</span>
<a name="l00071"></a>00071 <span class="keyword"></span>{
<a name="l00072"></a>00072 byte type;
<a name="l00073"></a>00073 <span class="keywordflow">if</span> (encodedPointLen < 1 || !bt.<a class="code" href="class_buffered_transformation.html#a9e1ad913c8fe697d269f408a7d5928fc" title="try to retrieve a single byte">Get</a>(type))
<a name="l00074"></a>00074 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00075"></a>00075
<a name="l00076"></a>00076 <span class="keywordflow">switch</span> (type)
<a name="l00077"></a>00077 {
<a name="l00078"></a>00078 <span class="keywordflow">case</span> 0:
<a name="l00079"></a>00079 P.identity = <span class="keyword">true</span>;
<a name="l00080"></a>00080 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00081"></a>00081 <span class="keywordflow">case</span> 2:
<a name="l00082"></a>00082 <span class="keywordflow">case</span> 3:
<a name="l00083"></a>00083 {
<a name="l00084"></a>00084 <span class="keywordflow">if</span> (encodedPointLen != EncodedPointSize(<span class="keyword">true</span>))
<a name="l00085"></a>00085 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00086"></a>00086
<a name="l00087"></a>00087 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> p = FieldSize();
<a name="l00088"></a>00088
<a name="l00089"></a>00089 P.identity = <span class="keyword">false</span>;
<a name="l00090"></a>00090 P.x.Decode(bt, GetField().MaxElementByteLength());
<a name="l00091"></a>00091 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
<a name="l00092"></a>00092
<a name="l00093"></a>00093 <span class="keywordflow">if</span> (Jacobi(P.y, p) !=1)
<a name="l00094"></a>00094 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00095"></a>00095
<a name="l00096"></a>00096 P.y = ModularSquareRoot(P.y, p);
<a name="l00097"></a>00097
<a name="l00098"></a>00098 <span class="keywordflow">if</span> ((type & 1) != P.y.<a class="code" href="class_integer.html#a2814c3b82849bd8f6f44cc36974f1717" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(0))
<a name="l00099"></a>00099 P.y = p-P.y;
<a name="l00100"></a>00100
<a name="l00101"></a>00101 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00102"></a>00102 }
<a name="l00103"></a>00103 <span class="keywordflow">case</span> 4:
<a name="l00104"></a>00104 {
<a name="l00105"></a>00105 <span class="keywordflow">if</span> (encodedPointLen != EncodedPointSize(<span class="keyword">false</span>))
<a name="l00106"></a>00106 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00107"></a>00107
<a name="l00108"></a>00108 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len = GetField().MaxElementByteLength();
<a name="l00109"></a>00109 P.identity = <span class="keyword">false</span>;
<a name="l00110"></a>00110 P.x.Decode(bt, len);
<a name="l00111"></a>00111 P.y.Decode(bt, len);
<a name="l00112"></a>00112 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00113"></a>00113 }
<a name="l00114"></a>00114 <span class="keywordflow">default</span>:
<a name="l00115"></a>00115 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00116"></a>00116 }
<a name="l00117"></a>00117 }
<a name="l00118"></a>00118
<a name="l00119"></a>00119 <span class="keywordtype">void</span> ECP::EncodePoint(<a class="code" href="class_buffered_transformation.html" title="interface for buffered transformations">BufferedTransformation</a> &bt, <span class="keyword">const</span> Point &P, <span class="keywordtype">bool</span> compressed)<span class="keyword"> const</span>
<a name="l00120"></a>00120 <span class="keyword"></span>{
<a name="l00121"></a>00121 <span class="keywordflow">if</span> (P.identity)
<a name="l00122"></a>00122 <a class="code" href="class_null_store.html" title="empty store">NullStore</a>().TransferTo(bt, EncodedPointSize(compressed));
<a name="l00123"></a>00123 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (compressed)
<a name="l00124"></a>00124 {
<a name="l00125"></a>00125 bt.<a class="code" href="class_buffered_transformation.html#ae70658b0d271f8e114ac6c3cc9774ede" title="input a byte for processing">Put</a>(2 + P.y.GetBit(0));
<a name="l00126"></a>00126 P.x.Encode(bt, GetField().MaxElementByteLength());
<a name="l00127"></a>00127 }
<a name="l00128"></a>00128 <span class="keywordflow">else</span>
<a name="l00129"></a>00129 {
<a name="l00130"></a>00130 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> len = GetField().MaxElementByteLength();
<a name="l00131"></a>00131 bt.<a class="code" href="class_buffered_transformation.html#ae70658b0d271f8e114ac6c3cc9774ede" title="input a byte for processing">Put</a>(4); <span class="comment">// uncompressed</span>
<a name="l00132"></a>00132 P.x.Encode(bt, len);
<a name="l00133"></a>00133 P.y.Encode(bt, len);
<a name="l00134"></a>00134 }
<a name="l00135"></a>00135 }
<a name="l00136"></a>00136
<a name="l00137"></a>00137 <span class="keywordtype">void</span> ECP::EncodePoint(byte *encodedPoint, <span class="keyword">const</span> Point &P, <span class="keywordtype">bool</span> compressed)<span class="keyword"> const</span>
<a name="l00138"></a>00138 <span class="keyword"></span>{
<a name="l00139"></a>00139 <a class="code" href="class_array_sink.html" title="Copy input to a memory buffer.">ArraySink</a> sink(encodedPoint, EncodedPointSize(compressed));
<a name="l00140"></a>00140 EncodePoint(sink, P, compressed);
<a name="l00141"></a>00141 assert(sink.TotalPutLength() == EncodedPointSize(compressed));
<a name="l00142"></a>00142 }
<a name="l00143"></a>00143
<a name="l00144"></a>00144 <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> ECP::BERDecodePoint(<a class="code" href="class_buffered_transformation.html" title="interface for buffered transformations">BufferedTransformation</a> &bt)<span class="keyword"> const</span>
<a name="l00145"></a>00145 <span class="keyword"></span>{
<a name="l00146"></a>00146 <a class="code" href="class_sec_block.html" title="a block of memory allocated using A">SecByteBlock</a> str;
<a name="l00147"></a>00147 BERDecodeOctetString(bt, str);
<a name="l00148"></a>00148 Point P;
<a name="l00149"></a>00149 <span class="keywordflow">if</span> (!DecodePoint(P, str, str.size()))
<a name="l00150"></a>00150 BERDecodeError();
<a name="l00151"></a>00151 <span class="keywordflow">return</span> P;
<a name="l00152"></a>00152 }
<a name="l00153"></a>00153
<a name="l00154"></a>00154 <span class="keywordtype">void</span> ECP::DEREncodePoint(<a class="code" href="class_buffered_transformation.html" title="interface for buffered transformations">BufferedTransformation</a> &bt, <span class="keyword">const</span> Point &P, <span class="keywordtype">bool</span> compressed)<span class="keyword"> const</span>
<a name="l00155"></a>00155 <span class="keyword"></span>{
<a name="l00156"></a>00156 <a class="code" href="class_sec_block.html" title="a block of memory allocated using A">SecByteBlock</a> str(EncodedPointSize(compressed));
<a name="l00157"></a>00157 EncodePoint(str, P, compressed);
<a name="l00158"></a>00158 DEREncodeOctetString(bt, str);
<a name="l00159"></a>00159 }
<a name="l00160"></a>00160
<a name="l00161"></a>00161 <span class="keywordtype">bool</span> ECP::ValidateParameters(<a class="code" href="class_random_number_generator.html" title="interface for random number generators">RandomNumberGenerator</a> &rng, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> level)<span class="keyword"> const</span>
<a name="l00162"></a>00162 <span class="keyword"></span>{
<a name="l00163"></a>00163 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> p = FieldSize();
<a name="l00164"></a>00164
<a name="l00165"></a>00165 <span class="keywordtype">bool</span> pass = p.IsOdd();
<a name="l00166"></a>00166 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
<a name="l00167"></a>00167
<a name="l00168"></a>00168 <span class="keywordflow">if</span> (level >= 1)
<a name="l00169"></a>00169 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
<a name="l00170"></a>00170
<a name="l00171"></a>00171 <span class="keywordflow">if</span> (level >= 2)
<a name="l00172"></a>00172 pass = pass && VerifyPrime(rng, p);
<a name="l00173"></a>00173
<a name="l00174"></a>00174 <span class="keywordflow">return</span> pass;
<a name="l00175"></a>00175 }
<a name="l00176"></a>00176
<a name="l00177"></a>00177 <span class="keywordtype">bool</span> ECP::VerifyPoint(<span class="keyword">const</span> Point &P)<span class="keyword"> const</span>
<a name="l00178"></a>00178 <span class="keyword"></span>{
<a name="l00179"></a>00179 <span class="keyword">const</span> FieldElement &x = P.x, &y = P.y;
<a name="l00180"></a>00180 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> p = FieldSize();
<a name="l00181"></a>00181 <span class="keywordflow">return</span> P.identity ||
<a name="l00182"></a>00182 (!x.IsNegative() && x<p && !y.IsNegative() && y<p
<a name="l00183"></a>00183 && !(((x*x+m_a)*x+m_b-y*y)%p));
<a name="l00184"></a>00184 }
<a name="l00185"></a>00185
<a name="l00186"></a>00186 <span class="keywordtype">bool</span> ECP::Equal(<span class="keyword">const</span> Point &P, <span class="keyword">const</span> Point &Q)<span class="keyword"> const</span>
<a name="l00187"></a>00187 <span class="keyword"></span>{
<a name="l00188"></a>00188 <span class="keywordflow">if</span> (P.identity && Q.identity)
<a name="l00189"></a>00189 <span class="keywordflow">return</span> <span class="keyword">true</span>;
<a name="l00190"></a>00190
<a name="l00191"></a>00191 <span class="keywordflow">if</span> (P.identity && !Q.identity)
<a name="l00192"></a>00192 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00193"></a>00193
<a name="l00194"></a>00194 <span class="keywordflow">if</span> (!P.identity && Q.identity)
<a name="l00195"></a>00195 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l00196"></a>00196
<a name="l00197"></a>00197 <span class="keywordflow">return</span> (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
<a name="l00198"></a>00198 }
<a name="l00199"></a>00199
<a name="l00200"></a>00200 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a>& ECP::Identity()<span class="keyword"> const</span>
<a name="l00201"></a>00201 <span class="keyword"></span>{
<a name="l00202"></a>00202 <span class="keywordflow">return</span> <a class="code" href="class_singleton.html">Singleton<Point></a>().Ref();
<a name="l00203"></a>00203 }
<a name="l00204"></a>00204
<a name="l00205"></a>00205 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a>& ECP::Inverse(<span class="keyword">const</span> Point &P)<span class="keyword"> const</span>
<a name="l00206"></a>00206 <span class="keyword"></span>{
<a name="l00207"></a>00207 <span class="keywordflow">if</span> (P.identity)
<a name="l00208"></a>00208 <span class="keywordflow">return</span> P;
<a name="l00209"></a>00209 <span class="keywordflow">else</span>
<a name="l00210"></a>00210 {
<a name="l00211"></a>00211 m_R.identity = <span class="keyword">false</span>;
<a name="l00212"></a>00212 m_R.x = P.x;
<a name="l00213"></a>00213 m_R.y = GetField().Inverse(P.y);
<a name="l00214"></a>00214 <span class="keywordflow">return</span> m_R;
<a name="l00215"></a>00215 }
<a name="l00216"></a>00216 }
<a name="l00217"></a>00217
<a name="l00218"></a>00218 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a>& ECP::Add(<span class="keyword">const</span> Point &P, <span class="keyword">const</span> Point &Q)<span class="keyword"> const</span>
<a name="l00219"></a>00219 <span class="keyword"></span>{
<a name="l00220"></a>00220 <span class="keywordflow">if</span> (P.identity) <span class="keywordflow">return</span> Q;
<a name="l00221"></a>00221 <span class="keywordflow">if</span> (Q.identity) <span class="keywordflow">return</span> P;
<a name="l00222"></a>00222 <span class="keywordflow">if</span> (GetField().Equal(P.x, Q.x))
<a name="l00223"></a>00223 <span class="keywordflow">return</span> GetField().Equal(P.y, Q.y) ? Double(P) : Identity();
<a name="l00224"></a>00224
<a name="l00225"></a>00225 FieldElement t = GetField().Subtract(Q.y, P.y);
<a name="l00226"></a>00226 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
<a name="l00227"></a>00227 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().<a class="code" href="class_square.html" title="Square">Square</a>(t), P.x), Q.x);
<a name="l00228"></a>00228 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
<a name="l00229"></a>00229
<a name="l00230"></a>00230 m_R.x.swap(x);
<a name="l00231"></a>00231 m_R.identity = <span class="keyword">false</span>;
<a name="l00232"></a>00232 <span class="keywordflow">return</span> m_R;
<a name="l00233"></a>00233 }
<a name="l00234"></a>00234
<a name="l00235"></a>00235 <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a>& ECP::Double(<span class="keyword">const</span> Point &P)<span class="keyword"> const</span>
<a name="l00236"></a>00236 <span class="keyword"></span>{
<a name="l00237"></a>00237 <span class="keywordflow">if</span> (P.identity || P.y==GetField().Identity()) <span class="keywordflow">return</span> Identity();
<a name="l00238"></a>00238
<a name="l00239"></a>00239 FieldElement t = GetField().Square(P.x);
<a name="l00240"></a>00240 t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
<a name="l00241"></a>00241 t = GetField().Divide(t, GetField().Double(P.y));
<a name="l00242"></a>00242 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().<a class="code" href="class_square.html" title="Square">Square</a>(t), P.x), P.x);
<a name="l00243"></a>00243 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
<a name="l00244"></a>00244
<a name="l00245"></a>00245 m_R.x.swap(x);
<a name="l00246"></a>00246 m_R.identity = <span class="keyword">false</span>;
<a name="l00247"></a>00247 <span class="keywordflow">return</span> m_R;
<a name="l00248"></a>00248 }
<a name="l00249"></a>00249
<a name="l00250"></a>00250 <span class="keyword">template</span> <<span class="keyword">class</span> T, <span class="keyword">class</span> Iterator> <span class="keywordtype">void</span> ParallelInvert(<span class="keyword">const</span> <a class="code" href="class_abstract_ring.html" title="Abstract Ring.">AbstractRing<T></a> &ring, Iterator begin, Iterator end)
<a name="l00251"></a>00251 {
<a name="l00252"></a>00252 <span class="keywordtype">size_t</span> n = end-begin;
<a name="l00253"></a>00253 <span class="keywordflow">if</span> (n == 1)
<a name="l00254"></a>00254 *begin = ring.MultiplicativeInverse(*begin);
<a name="l00255"></a>00255 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (n > 1)
<a name="l00256"></a>00256 {
<a name="l00257"></a>00257 std::vector<T> vec((n+1)/2);
<a name="l00258"></a>00258 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
<a name="l00259"></a>00259 Iterator it;
<a name="l00260"></a>00260
<a name="l00261"></a>00261 <span class="keywordflow">for</span> (i=0, it=begin; i<n/2; i++, it+=2)
<a name="l00262"></a>00262 vec[i] = ring.Multiply(*it, *(it+1));
<a name="l00263"></a>00263 <span class="keywordflow">if</span> (n%2 == 1)
<a name="l00264"></a>00264 vec[n/2] = *it;
<a name="l00265"></a>00265
<a name="l00266"></a>00266 ParallelInvert(ring, vec.begin(), vec.end());
<a name="l00267"></a>00267
<a name="l00268"></a>00268 <span class="keywordflow">for</span> (i=0, it=begin; i<n/2; i++, it+=2)
<a name="l00269"></a>00269 {
<a name="l00270"></a>00270 <span class="keywordflow">if</span> (!vec[i])
<a name="l00271"></a>00271 {
<a name="l00272"></a>00272 *it = ring.MultiplicativeInverse(*it);
<a name="l00273"></a>00273 *(it+1) = ring.MultiplicativeInverse(*(it+1));
<a name="l00274"></a>00274 }
<a name="l00275"></a>00275 <span class="keywordflow">else</span>
<a name="l00276"></a>00276 {
<a name="l00277"></a>00277 std::swap(*it, *(it+1));
<a name="l00278"></a>00278 *it = ring.Multiply(*it, vec[i]);
<a name="l00279"></a>00279 *(it+1) = ring.Multiply(*(it+1), vec[i]);
<a name="l00280"></a>00280 }
<a name="l00281"></a>00281 }
<a name="l00282"></a>00282 <span class="keywordflow">if</span> (n%2 == 1)
<a name="l00283"></a>00283 *it = vec[n/2];
<a name="l00284"></a>00284 }
<a name="l00285"></a>00285 }
<a name="l00286"></a>00286
<a name="l00287"></a>00287 <span class="keyword">struct </span>ProjectivePoint
<a name="l00288"></a>00288 {
<a name="l00289"></a>00289 ProjectivePoint() {}
<a name="l00290"></a>00290 ProjectivePoint(<span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &x, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &y, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &z)
<a name="l00291"></a>00291 : x(x), y(y), z(z) {}
<a name="l00292"></a>00292
<a name="l00293"></a>00293 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> x,y,z;
<a name="l00294"></a>00294 };
<a name="l00295"></a>00295
<a name="l00296"></a>00296 <span class="keyword">class </span>ProjectiveDoubling
<a name="l00297"></a>00297 {
<a name="l00298"></a>00298 <span class="keyword">public</span>:
<a name="l00299"></a>00299 ProjectiveDoubling(<span class="keyword">const</span> <a class="code" href="class_modular_arithmetic.html" title="ring of congruence classes modulo n">ModularArithmetic</a> &mr, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &m_a, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &m_b, <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECPPoint</a> &Q)
<a name="l00300"></a>00300 : mr(mr), firstDoubling(true), negated(false)
<a name="l00301"></a>00301 {
<a name="l00302"></a>00302 <span class="keywordflow">if</span> (Q.identity)
<a name="l00303"></a>00303 {
<a name="l00304"></a>00304 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
<a name="l00305"></a>00305 aZ4 = P.z = mr.Identity();
<a name="l00306"></a>00306 }
<a name="l00307"></a>00307 <span class="keywordflow">else</span>
<a name="l00308"></a>00308 {
<a name="l00309"></a>00309 P.x = Q.x;
<a name="l00310"></a>00310 P.y = Q.y;
<a name="l00311"></a>00311 sixteenY4 = P.z = mr.MultiplicativeIdentity();
<a name="l00312"></a>00312 aZ4 = m_a;
<a name="l00313"></a>00313 }
<a name="l00314"></a>00314 }
<a name="l00315"></a>00315
<a name="l00316"></a>00316 <span class="keywordtype">void</span> Double()
<a name="l00317"></a>00317 {
<a name="l00318"></a>00318 twoY = mr.Double(P.y);
<a name="l00319"></a>00319 P.z = mr.Multiply(P.z, twoY);
<a name="l00320"></a>00320 fourY2 = mr.Square(twoY);
<a name="l00321"></a>00321 S = mr.Multiply(fourY2, P.x);
<a name="l00322"></a>00322 aZ4 = mr.Multiply(aZ4, sixteenY4);
<a name="l00323"></a>00323 M = mr.Square(P.x);
<a name="l00324"></a>00324 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
<a name="l00325"></a>00325 P.x = mr.Square(M);
<a name="l00326"></a>00326 mr.Reduce(P.x, S);
<a name="l00327"></a>00327 mr.Reduce(P.x, S);
<a name="l00328"></a>00328 mr.Reduce(S, P.x);
<a name="l00329"></a>00329 P.y = mr.Multiply(M, S);
<a name="l00330"></a>00330 sixteenY4 = mr.Square(fourY2);
<a name="l00331"></a>00331 mr.Reduce(P.y, mr.Half(sixteenY4));
<a name="l00332"></a>00332 }
<a name="l00333"></a>00333
<a name="l00334"></a>00334 <span class="keyword">const</span> <a class="code" href="class_modular_arithmetic.html" title="ring of congruence classes modulo n">ModularArithmetic</a> &mr;
<a name="l00335"></a>00335 ProjectivePoint P;
<a name="l00336"></a>00336 <span class="keywordtype">bool</span> firstDoubling, negated;
<a name="l00337"></a>00337 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> sixteenY4, aZ4, twoY, fourY2, S, M;
<a name="l00338"></a>00338 };
<a name="l00339"></a>00339
<a name="l00340"></a>00340 <span class="keyword">struct </span>ZIterator
<a name="l00341"></a>00341 {
<a name="l00342"></a>00342 ZIterator() {}
<a name="l00343"></a>00343 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
<a name="l00344"></a>00344 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a>& operator*() {<span class="keywordflow">return</span> it->z;}
<a name="l00345"></a>00345 <span class="keywordtype">int</span> operator-(ZIterator it2) {<span class="keywordflow">return</span> int(it-it2.it);}
<a name="l00346"></a>00346 ZIterator operator+(<span class="keywordtype">int</span> i) {<span class="keywordflow">return</span> ZIterator(it+i);}
<a name="l00347"></a>00347 ZIterator& operator+=(<span class="keywordtype">int</span> i) {it+=i; <span class="keywordflow">return</span> *<span class="keyword">this</span>;}
<a name="l00348"></a>00348 std::vector<ProjectivePoint>::iterator it;
<a name="l00349"></a>00349 };
<a name="l00350"></a>00350
<a name="l00351"></a>00351 <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> ECP::ScalarMultiply(<span class="keyword">const</span> Point &P, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &k)<span class="keyword"> const</span>
<a name="l00352"></a>00352 <span class="keyword"></span>{
<a name="l00353"></a>00353 Element result;
<a name="l00354"></a>00354 <span class="keywordflow">if</span> (k.<a class="code" href="class_integer.html#a178398002ab175e788a3bc224e5e5a8d" title="number of significant bits = floor(log2(abs(*this))) + 1">BitCount</a>() <= 5)
<a name="l00355"></a>00355 <a class="code" href="class_abstract_group.html" title="Abstract Group.">AbstractGroup<ECPPoint>::SimultaneousMultiply</a>(&result, P, &k, 1);
<a name="l00356"></a>00356 <span class="keywordflow">else</span>
<a name="l00357"></a>00357 ECP::SimultaneousMultiply(&result, P, &k, 1);
<a name="l00358"></a>00358 <span class="keywordflow">return</span> result;
<a name="l00359"></a>00359 }
<a name="l00360"></a>00360
<a name="l00361"></a>00361 <span class="keywordtype">void</span> ECP::SimultaneousMultiply(<a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> *results, <span class="keyword">const</span> <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> &P, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> *expBegin, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expCount)<span class="keyword"> const</span>
<a name="l00362"></a>00362 <span class="keyword"></span>{
<a name="l00363"></a>00363 <span class="keywordflow">if</span> (!GetField().IsMontgomeryRepresentation())
<a name="l00364"></a>00364 {
<a name="l00365"></a>00365 <a class="code" href="class_e_c_p.html" title="Elliptic Curve over GF(p), where p is prime.">ECP</a> ecpmr(*<span class="keyword">this</span>, <span class="keyword">true</span>);
<a name="l00366"></a>00366 <span class="keyword">const</span> <a class="code" href="class_modular_arithmetic.html" title="ring of congruence classes modulo n">ModularArithmetic</a> &mr = ecpmr.GetField();
<a name="l00367"></a>00367 ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
<a name="l00368"></a>00368 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i=0; i<expCount; i++)
<a name="l00369"></a>00369 results[i] = FromMontgomery(mr, results[i]);
<a name="l00370"></a>00370 <span class="keywordflow">return</span>;
<a name="l00371"></a>00371 }
<a name="l00372"></a>00372
<a name="l00373"></a>00373 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
<a name="l00374"></a>00374 std::vector<ProjectivePoint> bases;
<a name="l00375"></a>00375 std::vector<WindowSlider> exponents;
<a name="l00376"></a>00376 exponents.reserve(expCount);
<a name="l00377"></a>00377 std::vector<std::vector<word32> > baseIndices(expCount);
<a name="l00378"></a>00378 std::vector<std::vector<bool> > negateBase(expCount);
<a name="l00379"></a>00379 std::vector<std::vector<word32> > exponentWindows(expCount);
<a name="l00380"></a>00380 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
<a name="l00381"></a>00381
<a name="l00382"></a>00382 <span class="keywordflow">for</span> (i=0; i<expCount; i++)
<a name="l00383"></a>00383 {
<a name="l00384"></a>00384 assert(expBegin->NotNegative());
<a name="l00385"></a>00385 exponents.push_back(<a class="code" href="struct_window_slider.html">WindowSlider</a>(*expBegin++, InversionIsFast(), 5));
<a name="l00386"></a>00386 exponents[i].FindNextWindow();
<a name="l00387"></a>00387 }
<a name="l00388"></a>00388
<a name="l00389"></a>00389 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> expBitPosition = 0;
<a name="l00390"></a>00390 <span class="keywordtype">bool</span> notDone = <span class="keyword">true</span>;
<a name="l00391"></a>00391
<a name="l00392"></a>00392 <span class="keywordflow">while</span> (notDone)
<a name="l00393"></a>00393 {
<a name="l00394"></a>00394 notDone = <span class="keyword">false</span>;
<a name="l00395"></a>00395 <span class="keywordtype">bool</span> baseAdded = <span class="keyword">false</span>;
<a name="l00396"></a>00396 <span class="keywordflow">for</span> (i=0; i<expCount; i++)
<a name="l00397"></a>00397 {
<a name="l00398"></a>00398 <span class="keywordflow">if</span> (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
<a name="l00399"></a>00399 {
<a name="l00400"></a>00400 <span class="keywordflow">if</span> (!baseAdded)
<a name="l00401"></a>00401 {
<a name="l00402"></a>00402 bases.push_back(rd.P);
<a name="l00403"></a>00403 baseAdded =<span class="keyword">true</span>;
<a name="l00404"></a>00404 }
<a name="l00405"></a>00405
<a name="l00406"></a>00406 exponentWindows[i].push_back(exponents[i].expWindow);
<a name="l00407"></a>00407 baseIndices[i].push_back((word32)bases.size()-1);
<a name="l00408"></a>00408 negateBase[i].push_back(exponents[i].negateNext);
<a name="l00409"></a>00409
<a name="l00410"></a>00410 exponents[i].FindNextWindow();
<a name="l00411"></a>00411 }
<a name="l00412"></a>00412 notDone = notDone || !exponents[i].finished;
<a name="l00413"></a>00413 }
<a name="l00414"></a>00414
<a name="l00415"></a>00415 <span class="keywordflow">if</span> (notDone)
<a name="l00416"></a>00416 {
<a name="l00417"></a>00417 rd.Double();
<a name="l00418"></a>00418 expBitPosition++;
<a name="l00419"></a>00419 }
<a name="l00420"></a>00420 }
<a name="l00421"></a>00421
<a name="l00422"></a>00422 <span class="comment">// convert from projective to affine coordinates</span>
<a name="l00423"></a>00423 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
<a name="l00424"></a>00424 <span class="keywordflow">for</span> (i=0; i<bases.size(); i++)
<a name="l00425"></a>00425 {
<a name="l00426"></a>00426 <span class="keywordflow">if</span> (bases[i].z.NotZero())
<a name="l00427"></a>00427 {
<a name="l00428"></a>00428 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
<a name="l00429"></a>00429 bases[i].z = GetField().Square(bases[i].z);
<a name="l00430"></a>00430 bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
<a name="l00431"></a>00431 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
<a name="l00432"></a>00432 }
<a name="l00433"></a>00433 }
<a name="l00434"></a>00434
<a name="l00435"></a>00435 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
<a name="l00436"></a>00436 <span class="keywordflow">for</span> (i=0; i<expCount; i++)
<a name="l00437"></a>00437 {
<a name="l00438"></a>00438 finalCascade.resize(baseIndices[i].size());
<a name="l00439"></a>00439 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> j=0; j<baseIndices[i].size(); j++)
<a name="l00440"></a>00440 {
<a name="l00441"></a>00441 ProjectivePoint &base = bases[baseIndices[i][j]];
<a name="l00442"></a>00442 <span class="keywordflow">if</span> (base.z.IsZero())
<a name="l00443"></a>00443 finalCascade[j].base.identity = <span class="keyword">true</span>;
<a name="l00444"></a>00444 <span class="keywordflow">else</span>
<a name="l00445"></a>00445 {
<a name="l00446"></a>00446 finalCascade[j].base.identity = <span class="keyword">false</span>;
<a name="l00447"></a>00447 finalCascade[j].base.x = base.x;
<a name="l00448"></a>00448 if (negateBase[i][j])
<a name="l00449"></a>00449 finalCascade[j].base.y = GetField().Inverse(base.y);
<a name="l00450"></a>00450 <span class="keywordflow">else</span>
<a name="l00451"></a>00451 finalCascade[j].base.y = base.y;
<a name="l00452"></a>00452 }
<a name="l00453"></a>00453 finalCascade[j].exponent = <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a>(Integer::POSITIVE, 0, exponentWindows[i][j]);
<a name="l00454"></a>00454 }
<a name="l00455"></a>00455 results[i] = GeneralCascadeMultiplication(*<span class="keyword">this</span>, finalCascade.begin(), finalCascade.end());
<a name="l00456"></a>00456 }
<a name="l00457"></a>00457 }
<a name="l00458"></a>00458
<a name="l00459"></a>00459 <a class="code" href="struct_e_c_p_point.html" title="Elliptical Curve Point.">ECP::Point</a> ECP::CascadeScalarMultiply(<span class="keyword">const</span> Point &P, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &k1, <span class="keyword">const</span> Point &Q, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &k2)<span class="keyword"> const</span>
<a name="l00460"></a>00460 <span class="keyword"></span>{
<a name="l00461"></a>00461 <span class="keywordflow">if</span> (!GetField().IsMontgomeryRepresentation())
<a name="l00462"></a>00462 {
<a name="l00463"></a>00463 <a class="code" href="class_e_c_p.html" title="Elliptic Curve over GF(p), where p is prime.">ECP</a> ecpmr(*<span class="keyword">this</span>, <span class="keyword">true</span>);
<a name="l00464"></a>00464 <span class="keyword">const</span> <a class="code" href="class_modular_arithmetic.html" title="ring of congruence classes modulo n">ModularArithmetic</a> &mr = ecpmr.GetField();
<a name="l00465"></a>00465 <span class="keywordflow">return</span> FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
<a name="l00466"></a>00466 }
<a name="l00467"></a>00467 <span class="keywordflow">else</span>
<a name="l00468"></a>00468 <span class="keywordflow">return</span> <a class="code" href="class_abstract_group.html" title="Abstract Group.">AbstractGroup<Point>::CascadeScalarMultiply</a>(P, k1, Q, k2);
<a name="l00469"></a>00469 }
<a name="l00470"></a>00470
<a name="l00471"></a>00471 NAMESPACE_END
<a name="l00472"></a>00472
<a name="l00473"></a>00473 <span class="preprocessor">#endif</span>
</pre></div></div>
<hr size="1"/><address style="text-align: right;"><small>Generated on 9 Dec 2009 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
distrib
>
Fedora
>
13
>
i386
>
media
>
os
>
by-pkgid
>
07dfcfe50d66c9a48a3c5e6c1693f12a
>
files
>
1709
