📄 xtr_8cpp-source.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"><html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8"><title>Crypto++: xtr.cpp Source File</title><link href="doxygen.css" rel="stylesheet" type="text/css"><link href="tabs.css" rel="stylesheet" type="text/css"></head><body><!-- Generated by Doxygen 1.5.2 --><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="classes.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>xtr.cpp</h1><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">// cryptlib.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 <span class="preprocessor">#include "<a class="code" href="xtr_8h.html" title=""The XTR public key system" by Arjen K.">xtr.h</a>"</span><a name="l00005"></a>00005 <span class="preprocessor">#include "nbtheory.h"</span><a name="l00006"></a>00006 <a name="l00007"></a>00007 <span class="preprocessor">#include "algebra.cpp"</span><a name="l00008"></a>00008 <a name="l00009"></a>00009 NAMESPACE_BEGIN(CryptoPP)<a name="l00010"></a>00010 <a name="l00011"></a><a class="code" href="class_g_f_p2_element.html#3665b10709f2a819bcb9e52ca5002d09">00011</a> const <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> & <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a>::Zero()<a name="l00012"></a>00012 {<a name="l00013"></a>00013 <span class="keywordflow">return</span> <a class="code" href="class_singleton.html">Singleton<GFP2Element></a>().Ref();<a name="l00014"></a>00014 }<a name="l00015"></a>00015 <a name="l00016"></a><a class="code" href="xtr_8h.html#23d746486b6db0723743846ee363f82c">00016</a> <span class="keywordtype">void</span> XTR_FindPrimesAndGenerator(<a class="code" href="class_random_number_generator.html" title="interface for random number generators">RandomNumberGenerator</a> &rng, <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &p, <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &q, <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> &g, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> pbits, <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> qbits)<a name="l00017"></a>00017 {<a name="l00018"></a>00018 assert(qbits > 9); <span class="comment">// no primes exist for pbits = 10, qbits = 9</span><a name="l00019"></a>00019 assert(pbits > qbits);<a name="l00020"></a>00020 <a name="l00021"></a>00021 <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> minQ = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(qbits - 1);<a name="l00022"></a>00022 <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> maxQ = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(qbits) - 1;<a name="l00023"></a>00023 <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> minP = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(pbits - 1);<a name="l00024"></a>00024 <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> maxP = <a class="code" href="class_integer.html#de53248f5dbb520273a70856b975417c" title="return the integer 2**e">Integer::Power2</a>(pbits) - 1;<a name="l00025"></a>00025 <a name="l00026"></a>00026 <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> r1, r2;<a name="l00027"></a>00027 <span class="keywordflow">do</span><a name="l00028"></a>00028 {<a name="l00029"></a>00029 <span class="keywordtype">bool</span> qFound = q.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, minQ, maxQ, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3fe686f55e5b6768b20009a12522bd0d9">Integer::PRIME</a>, 7, 12);<a name="l00030"></a>00030 assert(qFound);<a name="l00031"></a>00031 <span class="keywordtype">bool</span> solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);<a name="l00032"></a>00032 assert(solutionsExist);<a name="l00033"></a>00033 } <span class="keywordflow">while</span> (!p.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, minP, maxP, <a class="code" href="class_integer.html#9b4088ac01abf76b9ba60060abccb7a3fe686f55e5b6768b20009a12522bd0d9">Integer::PRIME</a>, CRT(rng.<a class="code" href="class_random_number_generator.html#ce592244cfbd6c18398ea6c75857532e" title="generate new random bit and return it">GenerateBit</a>()?r1:r2, q, 2, 3), 3*q));<a name="l00034"></a>00034 assert(((p.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>() - p + 1) % q).IsZero());<a name="l00035"></a>00035 <a name="l00036"></a>00036 <a class="code" href="class_g_f_p2___o_n_b.html" title="GF(p^2), optimal normal basis.">GFP2_ONB<ModularArithmetic></a> gfp2(p);<a name="l00037"></a>00037 <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> three = gfp2.ConvertIn(3), t;<a name="l00038"></a>00038 <a name="l00039"></a>00039 <span class="keywordflow">while</span> (<span class="keyword">true</span>)<a name="l00040"></a>00040 {<a name="l00041"></a>00041 g.<a class="code" href="class_g_f_p2_element.html#65778354421ad2da42fce4221e6da05c">c1</a>.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, <a class="code" href="class_integer.html#19b7e6d48b1b57bd4846160ea2928175" title="avoid calling constructors for these frequently used integers">Integer::Zero</a>(), p-1);<a name="l00042"></a>00042 g.<a class="code" href="class_g_f_p2_element.html#1688b28610e1b080a9304daad7c73bbb">c2</a>.<a class="code" href="class_integer.html#0f0574b9cae3cddf62c155da93085f0d">Randomize</a>(rng, <a class="code" href="class_integer.html#19b7e6d48b1b57bd4846160ea2928175" title="avoid calling constructors for these frequently used integers">Integer::Zero</a>(), p-1);<a name="l00043"></a>00043 t = XTR_Exponentiate(g, p+1, p);<a name="l00044"></a>00044 <span class="keywordflow">if</span> (t.c1 == t.c2)<a name="l00045"></a>00045 <span class="keywordflow">continue</span>;<a name="l00046"></a>00046 g = XTR_Exponentiate(g, (p.<a class="code" href="class_integer.html#7b5e639045868c5ac338f4180e1c7efa">Squared</a>()-p+1)/q, p);<a name="l00047"></a>00047 <span class="keywordflow">if</span> (g != three)<a name="l00048"></a>00048 <span class="keywordflow">break</span>;<a name="l00049"></a>00049 }<a name="l00050"></a>00050 assert(XTR_Exponentiate(g, q, p) == three);<a name="l00051"></a>00051 }<a name="l00052"></a>00052 <a name="l00053"></a><a class="code" href="xtr_8h.html#6fef7119a9babc3e61c8d18defa01c25">00053</a> <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> XTR_Exponentiate(<span class="keyword">const</span> <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> &b, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &e, <span class="keyword">const</span> <a class="code" href="class_integer.html" title="multiple precision integer and basic arithmetics">Integer</a> &p)<a name="l00054"></a>00054 {<a name="l00055"></a>00055 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitCount = e.<a class="code" href="class_integer.html#867356d88074424328d0ebb9bea63254" title="number of significant bits = floor(log2(abs(*this))) + 1">BitCount</a>();<a name="l00056"></a>00056 <span class="keywordflow">if</span> (bitCount == 0)<a name="l00057"></a>00057 <span class="keywordflow">return</span> <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a>(-3, -3);<a name="l00058"></a>00058 <a name="l00059"></a>00059 <span class="comment">// find the lowest bit of e that is 1</span><a name="l00060"></a>00060 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> lowest1bit;<a name="l00061"></a>00061 <span class="keywordflow">for</span> (lowest1bit=0; e.<a class="code" href="class_integer.html#0e377d23bde55fc7dc6ea2208c587d19" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(lowest1bit) == 0; lowest1bit++) {}<a name="l00062"></a>00062 <a name="l00063"></a>00063 <a class="code" href="class_g_f_p2___o_n_b.html" title="GF(p^2), optimal normal basis.">GFP2_ONB<MontgomeryRepresentation></a> gfp2(p);<a name="l00064"></a>00064 <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> c = gfp2.ConvertIn(b);<a name="l00065"></a>00065 <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> cp = gfp2.PthPower(c);<a name="l00066"></a>00066 <a class="code" href="class_g_f_p2_element.html" title="an element of GF(p^2)">GFP2Element</a> S[5] = {gfp2.ConvertIn(3), c, gfp2.SpecialOperation1(c)};<a name="l00067"></a>00067 <a name="l00068"></a>00068 <span class="comment">// do all exponents bits except the lowest zeros starting from the top</span><a name="l00069"></a>00069 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;<a name="l00070"></a>00070 <span class="keywordflow">for</span> (i = e.<a class="code" href="class_integer.html#867356d88074424328d0ebb9bea63254" title="number of significant bits = floor(log2(abs(*this))) + 1">BitCount</a>() - 1; i>lowest1bit; i--)<a name="l00071"></a>00071 {<a name="l00072"></a>00072 <span class="keywordflow">if</span> (e.<a class="code" href="class_integer.html#0e377d23bde55fc7dc6ea2208c587d19" title="return the i-th bit, i=0 being the least significant bit">GetBit</a>(i))<a name="l00073"></a>00073 {<a name="l00074"></a>00074 gfp2.RaiseToPthPower(S[0]);<a name="l00075"></a>00075 gfp2.Accumulate(S[0], gfp2.SpecialOperation2(S[2], c, S[1]));<a name="l00076"></a>00076 S[1] = gfp2.SpecialOperation1(S[1]);<a name="l00077"></a>00077 S[2] = gfp2.SpecialOperation1(S[2]);<a name="l00078"></a>00078 S[0].<a class="code" href="class_g_f_p2_element.html#aea0eacbd2dd61465f95c09690a3f89e">swap</a>(S[1]);<a name="l00079"></a>00079 }<a name="l00080"></a>00080 <span class="keywordflow">else</span><a name="l00081"></a>00081 {<a name="l00082"></a>00082 gfp2.RaiseToPthPower(S[2]);<a name="l00083"></a>00083 gfp2.Accumulate(S[2], gfp2.SpecialOperation2(S[0], cp, S[1]));<a name="l00084"></a>00084 S[1] = gfp2.SpecialOperation1(S[1]);<a name="l00085"></a>00085 S[0] = gfp2.SpecialOperation1(S[0]);<a name="l00086"></a>00086 S[2].<a class="code" href="class_g_f_p2_element.html#aea0eacbd2dd61465f95c09690a3f89e">swap</a>(S[1]);<a name="l00087"></a>00087 }<a name="l00088"></a>00088 }<a name="l00089"></a>00089 <a name="l00090"></a>00090 <span class="comment">// now do the lowest zeros</span><a name="l00091"></a>00091 <span class="keywordflow">while</span> (i--)<a name="l00092"></a>00092 S[1] = gfp2.SpecialOperation1(S[1]);<a name="l00093"></a>00093 <a name="l00094"></a>00094 <span class="keywordflow">return</span> gfp2.ConvertOut(S[1]);<a name="l00095"></a>00095 }<a name="l00096"></a>00096 <a name="l00097"></a>00097 <span class="keyword">template</span> <span class="keyword">class </span><a class="code" href="class_abstract_ring.html" title="Abstract Ring.">AbstractRing<GFP2Element></a>;<a name="l00098"></a>00098 <span class="keyword">template</span> <span class="keyword">class </span><a class="code" href="class_abstract_group.html" title="Abstract Group.">AbstractGroup<GFP2Element></a>;<a name="l00099"></a>00099 <a name="l00100"></a>00100 NAMESPACE_END</pre></div><hr size="1"><address style="text-align: right;"><small>Generated on Fri Jun 1 11:11:26 2007 for Crypto++ by <a href="http://www.doxygen.org/index.html"><img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.2 </small></address></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -