1#ifndef CRYPTOPP_XTR_H
2#define CRYPTOPP_XTR_H
3
4/** \file
5	"The XTR public key system" by Arjen K. Lenstra and Eric R. Verheul
6*/
7
8#include "modarith.h"
9
10NAMESPACE_BEGIN(CryptoPP)
11
12//! an element of GF(p^2)
13class GFP2Element
14{
15public:
16	GFP2Element() {}
17	GFP2Element(const Integer &c1, const Integer &c2) : c1(c1), c2(c2) {}
18	GFP2Element(const byte *encodedElement, unsigned int size)
19		: c1(encodedElement, size/2), c2(encodedElement+size/2, size/2) {}
20
21	void Encode(byte *encodedElement, unsigned int size)
22	{
23		c1.Encode(encodedElement, size/2);
24		c2.Encode(encodedElement+size/2, size/2);
25	}
26
27	bool operator==(const GFP2Element &rhs)	const {return c1 == rhs.c1 && c2 == rhs.c2;}
28	bool operator!=(const GFP2Element &rhs) const {return !operator==(rhs);}
29
30	void swap(GFP2Element &a)
31	{
32		c1.swap(a.c1);
33		c2.swap(a.c2);
34	}
35
36	static const GFP2Element & Zero();
37
38	Integer c1, c2;
39};
40
41//! GF(p^2), optimal normal basis
42template <class F>
43class GFP2_ONB : public AbstractRing<GFP2Element>
44{
45public:
46	typedef F BaseField;
47
48	GFP2_ONB(const Integer &p) : modp(p)
49	{
50		if (p%3 != 2)
51			throw InvalidArgument("GFP2_ONB: modulus must be equivalent to 2 mod 3");
52	}
53
54	const Integer& GetModulus() const {return modp.GetModulus();}
55
56	GFP2Element ConvertIn(const Integer &a) const
57	{
58		t = modp.Inverse(modp.ConvertIn(a));
59		return GFP2Element(t, t);
60	}
61
62	GFP2Element ConvertIn(const GFP2Element &a) const
63		{return GFP2Element(modp.ConvertIn(a.c1), modp.ConvertIn(a.c2));}
64
65	GFP2Element ConvertOut(const GFP2Element &a) const
66		{return GFP2Element(modp.ConvertOut(a.c1), modp.ConvertOut(a.c2));}
67
68	bool Equal(const GFP2Element &a, const GFP2Element &b) const
69	{
70		return modp.Equal(a.c1, b.c1) && modp.Equal(a.c2, b.c2);
71	}
72
73	const Element& Identity() const
74	{
75		return GFP2Element::Zero();
76	}
77
78	const Element& Add(const Element &a, const Element &b) const
79	{
80		result.c1 = modp.Add(a.c1, b.c1);
81		result.c2 = modp.Add(a.c2, b.c2);
82		return result;
83	}
84
85	const Element& Inverse(const Element &a) const
86	{
87		result.c1 = modp.Inverse(a.c1);
88		result.c2 = modp.Inverse(a.c2);
89		return result;
90	}
91
92	const Element& Double(const Element &a) const
93	{
94		result.c1 = modp.Double(a.c1);
95		result.c2 = modp.Double(a.c2);
96		return result;
97	}
98
99	const Element& Subtract(const Element &a, const Element &b) const
100	{
101		result.c1 = modp.Subtract(a.c1, b.c1);
102		result.c2 = modp.Subtract(a.c2, b.c2);
103		return result;
104	}
105
106	Element& Accumulate(Element &a, const Element &b) const
107	{
108		modp.Accumulate(a.c1, b.c1);
109		modp.Accumulate(a.c2, b.c2);
110		return a;
111	}
112
113	Element& Reduce(Element &a, const Element &b) const
114	{
115		modp.Reduce(a.c1, b.c1);
116		modp.Reduce(a.c2, b.c2);
117		return a;
118	}
119
120	bool IsUnit(const Element &a) const
121	{
122		return a.c1.NotZero() || a.c2.NotZero();
123	}
124
125	const Element& MultiplicativeIdentity() const
126	{
127		result.c1 = result.c2 = modp.Inverse(modp.MultiplicativeIdentity());
128		return result;
129	}
130
131	const Element& Multiply(const Element &a, const Element &b) const
132	{
133		t = modp.Add(a.c1, a.c2);
134		t = modp.Multiply(t, modp.Add(b.c1, b.c2));
135		result.c1 = modp.Multiply(a.c1, b.c1);
136		result.c2 = modp.Multiply(a.c2, b.c2);
137		result.c1.swap(result.c2);
138		modp.Reduce(t, result.c1);
139		modp.Reduce(t, result.c2);
140		modp.Reduce(result.c1, t);
141		modp.Reduce(result.c2, t);
142		return result;
143	}
144
145	const Element& MultiplicativeInverse(const Element &a) const
146	{
147		return result = Exponentiate(a, modp.GetModulus()-2);
148	}
149
150	const Element& Square(const Element &a) const
151	{
152		const Integer &ac1 = (&a == &result) ? (t = a.c1) : a.c1;
153		result.c1 = modp.Multiply(modp.Subtract(modp.Subtract(a.c2, a.c1), a.c1), a.c2);
154		result.c2 = modp.Multiply(modp.Subtract(modp.Subtract(ac1, a.c2), a.c2), ac1);
155		return result;
156	}
157
158	Element Exponentiate(const Element &a, const Integer &e) const
159	{
160		Integer edivp, emodp;
161		Integer::Divide(emodp, edivp, e, modp.GetModulus());
162		Element b = PthPower(a);
163		return AbstractRing<GFP2Element>::CascadeExponentiate(a, emodp, b, edivp);
164	}
165
166	const Element & PthPower(const Element &a) const
167	{
168		result = a;
169		result.c1.swap(result.c2);
170		return result;
171	}
172
173	void RaiseToPthPower(Element &a) const
174	{
175		a.c1.swap(a.c2);
176	}
177
178	// a^2 - 2a^p
179	const Element & SpecialOperation1(const Element &a) const
180	{
181		assert(&a != &result);
182		result = Square(a);
183		modp.Reduce(result.c1, a.c2);
184		modp.Reduce(result.c1, a.c2);
185		modp.Reduce(result.c2, a.c1);
186		modp.Reduce(result.c2, a.c1);
187		return result;
188	}
189
190	// x * z - y * z^p
191	const Element & SpecialOperation2(const Element &x, const Element &y, const Element &z) const
192	{
193		assert(&x != &result && &y != &result && &z != &result);
194		t = modp.Add(x.c2, y.c2);
195		result.c1 = modp.Multiply(z.c1, modp.Subtract(y.c1, t));
196		modp.Accumulate(result.c1, modp.Multiply(z.c2, modp.Subtract(t, x.c1)));
197		t = modp.Add(x.c1, y.c1);
198		result.c2 = modp.Multiply(z.c2, modp.Subtract(y.c2, t));
199		modp.Accumulate(result.c2, modp.Multiply(z.c1, modp.Subtract(t, x.c2)));
200		return result;
201	}
202
203protected:
204	BaseField modp;
205	mutable GFP2Element result;
206	mutable Integer t;
207};
208
209void XTR_FindPrimesAndGenerator(RandomNumberGenerator &rng, Integer &p, Integer &q, GFP2Element &g, unsigned int pbits, unsigned int qbits);
210
211GFP2Element XTR_Exponentiate(const GFP2Element &b, const Integer &e, const Integer &p);
212
213NAMESPACE_END
214
215#endif
216