<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>Crypto++: xtr.cpp Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.3.7 -->
<div class="qindex"><a class="qindex" href="index.html">Main Page</a> | <a class="qindex" href="namespaces.html">Namespace List</a> | <a class="qindex" href="hierarchy.html">Class Hierarchy</a> | <a class="qindex" href="classes.html">Alphabetical List</a> | <a class="qindex" href="annotated.html">Class List</a> | <a class="qindex" href="files.html">File List</a> | <a class="qindex" href="namespacemembers.html">Namespace Members</a> | <a class="qindex" href="functions.html">Class Members</a> | <a class="qindex" href="globals.html">File Members</a></div>
<h1>xtr.cpp</h1><pre class="fragment"><div>00001 <span class="comment">// cryptlib.cpp - written and placed in the public domain by Wei Dai</span>
00002
00003 <span class="preprocessor">#include "pch.h"</span>
00004 <span class="preprocessor">#include "<a class="code" href="xtr_8h.html">xtr.h</a>"</span>
00005 <span class="preprocessor">#include "nbtheory.h"</span>
00006
00007 <span class="preprocessor">#include "algebra.cpp"</span>
00008
00009 NAMESPACE_BEGIN(CryptoPP)
00010
00011 const <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> & <a class="code" href="class_g_f_p2_element.html">GFP2Element</a>::Zero()
00012 {
00013 <span class="keywordflow">return</span> <a class="code" href="class_singleton.html">Singleton<GFP2Element></a>().Ref();
00014 }
00015
00016 <span class="keywordtype">void</span> XTR_FindPrimesAndGenerator(<a class="code" href="class_random_number_generator.html">RandomNumberGenerator</a> &rng, <a class="code" href="class_integer.html">Integer</a> &p, <a class="code" href="class_integer.html">Integer</a> &q, <a class="code" href="class_g_f_p2_element.html">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)
00017 {
00018 assert(qbits > 9); <span class="comment">// no primes exist for pbits = 10, qbits = 9</span>
00019 assert(pbits > qbits);
00020
00021 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> minQ = <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(qbits - 1);
00022 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> maxQ = <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(qbits) - 1;
00023 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> minP = <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(pbits - 1);
00024 <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> maxP = <a class="code" href="class_integer.html#_integerz37_15">Integer::Power2</a>(pbits) - 1;
00025
00026 <a class="code" href="class_integer.html">Integer</a> r1, r2;
00027 <span class="keywordflow">do</span>
00028 {
00029 <span class="keywordtype">bool</span> qFound = q.<a class="code" href="class_integer.html#_integerz43_10">Randomize</a>(rng, minQ, maxQ, Integer::PRIME, 7, 12);
00030 assert(qFound);
00031 <span class="keywordtype">bool</span> solutionsExist = SolveModularQuadraticEquation(r1, r2, 1, -1, 1, q);
00032 assert(solutionsExist);
00033 } <span class="keywordflow">while</span> (!p.<a class="code" href="class_integer.html#_integerz43_10">Randomize</a>(rng, minP, maxP, Integer::PRIME, CRT(rng.<a class="code" href="class_random_number_generator.html#_x917_r_n_ga2">GenerateBit</a>()?r1:r2, q, 2, 3), 3*q));
00034 assert(((p.<a class="code" href="class_integer.html#_integerz49_2">Squared</a>() - p + 1) % q).IsZero());
00035
00036 <a class="code" href="class_g_f_p2___o_n_b.html">GFP2_ONB<ModularArithmetic></a> gfp2(p);
00037 <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> three = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba2">ConvertIn</a>(3), t;
00038
00039 <span class="keywordflow">while</span> (<span class="keyword">true</span>)
00040 {
00041 g.c1.Randomize(rng, Integer::Zero(), p-1);
00042 g.c2.Randomize(rng, Integer::Zero(), p-1);
00043 t = XTR_Exponentiate(g, p+1, p);
00044 <span class="keywordflow">if</span> (t.c1 == t.c2)
00045 <span class="keywordflow">continue</span>;
00046 g = XTR_Exponentiate(g, (p.<a class="code" href="class_integer.html#_integerz49_2">Squared</a>()-p+1)/q, p);
00047 <span class="keywordflow">if</span> (g != three)
00048 <span class="keywordflow">break</span>;
00049 }
00050 assert(XTR_Exponentiate(g, q, p) == three);
00051 }
00052
00053 <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> XTR_Exponentiate(<span class="keyword">const</span> <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> &b, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &e, <span class="keyword">const</span> <a class="code" href="class_integer.html">Integer</a> &p)
00054 {
00055 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> bitCount = e.BitCount();
00056 <span class="keywordflow">if</span> (bitCount == 0)
00057 <span class="keywordflow">return</span> <a class="code" href="class_g_f_p2_element.html">GFP2Element</a>(-3, -3);
00058
00059 <span class="comment">// find the lowest bit of e that is 1</span>
00060 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> lowest1bit;
00061 <span class="keywordflow">for</span> (lowest1bit=0; e.GetBit(lowest1bit) == 0; lowest1bit++) {}
00062
00063 <a class="code" href="class_g_f_p2___o_n_b.html">GFP2_ONB<MontgomeryRepresentation></a> gfp2(p);
00064 <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> c = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba2">ConvertIn</a>(b);
00065 <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> cp = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba19">PthPower</a>(c);
00066 <a class="code" href="class_g_f_p2_element.html">GFP2Element</a> S[5] = {gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba2">ConvertIn</a>(3), c, gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba21">SpecialOperation1</a>(c)};
00067
00068 <span class="comment">// do all exponents bits except the lowest zeros starting from the top</span>
00069 <span class="keywordtype">unsigned</span> <span class="keywordtype">int</span> i;
00070 <span class="keywordflow">for</span> (i = e.BitCount() - 1; i>lowest1bit; i--)
00071 {
00072 <span class="keywordflow">if</span> (e.GetBit(i))
00073 {
00074 gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba20">RaiseToPthPower</a>(S[0]);
00075 gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba11">Accumulate</a>(S[0], gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba22">SpecialOperation2</a>(S[2], c, S[1]));
00076 S[1] = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba21">SpecialOperation1</a>(S[1]);
00077 S[2] = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba21">SpecialOperation1</a>(S[2]);
00078 S[0].swap(S[1]);
00079 }
00080 <span class="keywordflow">else</span>
00081 {
00082 gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba20">RaiseToPthPower</a>(S[2]);
00083 gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba11">Accumulate</a>(S[2], gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba22">SpecialOperation2</a>(S[0], cp, S[1]));
00084 S[1] = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba21">SpecialOperation1</a>(S[1]);
00085 S[0] = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba21">SpecialOperation1</a>(S[0]);
00086 S[2].swap(S[1]);
00087 }
00088 }
00089
00090 <span class="comment">// now do the lowest zeros</span>
00091 <span class="keywordflow">while</span> (i--)
00092 S[1] = gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba21">SpecialOperation1</a>(S[1]);
00093
00094 <span class="keywordflow">return</span> gfp2.<a class="code" href="class_g_f_p2___o_n_b.html#_g_f_p2___o_n_ba4">ConvertOut</a>(S[1]);
00095 }
00096
00097 <span class="keyword">template</span> <span class="keyword">class </span><a class="code" href="class_abstract_ring.html">AbstractRing<GFP2Element></a>;
00098 <span class="keyword">template</span> <span class="keyword">class </span><a class="code" href="class_abstract_group.html">AbstractGroup<GFP2Element></a>;
00099
00100 NAMESPACE_END
</div></pre><hr size="1"><address style="align: right;"><small>Generated on Sun Nov 7 08:23:59 2004 for Crypto++ by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border=0 ></a> 1.3.7 </small></address>
</body>
</html>
distrib
>
Mandriva
>
10.2
>
i586
>
media
>
contrib
>
by-pkgid
>
7457b841ac8136d3a1a9d3d960c5252e
>
files
>
1753
