Crypto++ 8.2 Free C++ class library of cryptographic schemes

gf2_32.cpp
1 // gf2_32.cpp - originally written and placed in the public domain by Wei Dai
2
3 #include "pch.h"
4 #include "misc.h"
5 #include "gf2_32.h"
6
7 NAMESPACE_BEGIN(CryptoPP)
8
9 GF2_32::Element GF2_32::Multiply(Element a, Element b) const
10 {
11 word32 table[4];
12 table[0] = 0;
13 table[1] = m_modulus;
14 if (a & 0x80000000)
15 {
16 table[2] = m_modulus ^ (a<<1);
17 table[3] = a<<1;
18 }
19 else
20 {
21 table[2] = a<<1;
22 table[3] = m_modulus ^ (a<<1);
23 }
24
25 #if CRYPTOPP_FAST_ROTATE(32)
26 b = rotrConstant<30>(b);
27 word32 result = table[b&2];
28
29 for (int i=29; i>=0; --i)
30 {
31 b = rotlConstant<1>(b);
32 result = (result<<1) ^ table[(b&2) + (result>>31)];
33 }
34
35 return (b&1) ? result ^ a : result;
36 #else
37 word32 result = table[(b>>30) & 2];
38
39 for (int i=29; i>=0; --i)
40 result = (result<<1) ^ table[((b>>i)&2) + (result>>31)];
41
42 return (b&1) ? result ^ a : result;
43 #endif
44 }
45
46 GF2_32::Element GF2_32::MultiplicativeInverse(Element a) const
47 {
48 if (a <= 1) // 1 is a special case
49 return a;
50
51 // warning - don't try to adapt this algorithm for another situation
52 word32 g0=m_modulus, g1=a, g2=a;
53 word32 v0=0, v1=1, v2=1;
54
55 CRYPTOPP_ASSERT(g1);
56
57 while (!(g2 & 0x80000000))
58 {
59 g2 <<= 1;
60 v2 <<= 1;
61 }
62
63 g2 <<= 1;
64 v2 <<= 1;
65
66 g0 ^= g2;
67 v0 ^= v2;
68
69 while (g0 != 1)
70 {
71 if (g1 < g0 || ((g0^g1) < g0 && (g0^g1) < g1))
72 {
73 CRYPTOPP_ASSERT(BitPrecision(g1) <= BitPrecision(g0));
74 g2 = g1;
75 v2 = v1;
76 }
77 else
78 {
79 CRYPTOPP_ASSERT(BitPrecision(g1) > BitPrecision(g0));
80 g2 = g0; g0 = g1; g1 = g2;
81 v2 = v0; v0 = v1; v1 = v2;
82 }
83
84 while ((g0^g2) >= g2)
85 {
86 CRYPTOPP_ASSERT(BitPrecision(g0) > BitPrecision(g2));
87 g2 <<= 1;
88 v2 <<= 1;
89 }
90
91 CRYPTOPP_ASSERT(BitPrecision(g0) == BitPrecision(g2));
92 g0 ^= g2;
93 v0 ^= v2;
94 }
95
96 return v0;
97 }
98
99 NAMESPACE_END
misc.h
Utility functions for the Crypto++ library.
gf2_32.h
Classes and functions for schemes over GF(2^32)
pch.h
Precompiled header file.
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
CryptoPP
Crypto++ library namespace.
BitPrecision
unsigned int BitPrecision(const T &value)
Returns the number of bits required for a value.
Definition: misc.h:822