1
by weidai
Initial revision |
1 |
// rw.cpp - written and placed in the public domain by Wei Dai
|
2 |
||
3 |
#include "pch.h" |
|
4 |
#include "rw.h" |
|
5 |
#include "nbtheory.h" |
|
6 |
#include "asn.h" |
|
7 |
||
181
by weidai
changes done for FIPS-140 lab code drop |
8 |
#ifndef CRYPTOPP_IMPORTS
|
9 |
||
1
by weidai
Initial revision |
10 |
NAMESPACE_BEGIN(CryptoPP) |
11 |
||
27
by weidai
various changes for 5.1 |
12 |
void RWFunction::BERDecode(BufferedTransformation &bt) |
1
by weidai
Initial revision |
13 |
{
|
14 |
BERSequenceDecoder seq(bt); |
|
15 |
m_n.BERDecode(seq); |
|
16 |
seq.MessageEnd(); |
|
17 |
}
|
|
18 |
||
27
by weidai
various changes for 5.1 |
19 |
void RWFunction::DEREncode(BufferedTransformation &bt) const |
1
by weidai
Initial revision |
20 |
{
|
21 |
DERSequenceEncoder seq(bt); |
|
22 |
m_n.DEREncode(seq); |
|
23 |
seq.MessageEnd(); |
|
24 |
}
|
|
25 |
||
27
by weidai
various changes for 5.1 |
26 |
Integer RWFunction::ApplyFunction(const Integer &in) const |
1
by weidai
Initial revision |
27 |
{
|
28 |
DoQuickSanityCheck(); |
|
29 |
||
30 |
Integer out = in.Squared()%m_n; |
|
27
by weidai
various changes for 5.1 |
31 |
const word r = 12; |
32 |
// this code was written to handle both r = 6 and r = 12,
|
|
33 |
// but now only r = 12 is used in P1363
|
|
1
by weidai
Initial revision |
34 |
const word r2 = r/2; |
35 |
const word r3a = (16 + 5 - r) % 16; // n%16 could be 5 or 13 |
|
36 |
const word r3b = (16 + 13 - r) % 16; |
|
37 |
const word r4 = (8 + 5 - r/2) % 8; // n%8 == 5 |
|
38 |
switch (out % 16) |
|
39 |
{
|
|
40 |
case r: |
|
41 |
break; |
|
42 |
case r2: |
|
43 |
case r2+8: |
|
44 |
out <<= 1; |
|
45 |
break; |
|
46 |
case r3a: |
|
47 |
case r3b: |
|
48 |
out.Negate(); |
|
49 |
out += m_n; |
|
50 |
break; |
|
51 |
case r4: |
|
52 |
case r4+8: |
|
53 |
out.Negate(); |
|
54 |
out += m_n; |
|
55 |
out <<= 1; |
|
56 |
break; |
|
57 |
default: |
|
58 |
out = Integer::Zero(); |
|
59 |
}
|
|
60 |
return out; |
|
61 |
}
|
|
62 |
||
27
by weidai
various changes for 5.1 |
63 |
bool RWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const |
1
by weidai
Initial revision |
64 |
{
|
65 |
bool pass = true; |
|
66 |
pass = pass && m_n > Integer::One() && m_n%8 == 5; |
|
67 |
return pass; |
|
68 |
}
|
|
69 |
||
27
by weidai
various changes for 5.1 |
70 |
bool RWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const |
1
by weidai
Initial revision |
71 |
{
|
72 |
return GetValueHelper(this, name, valueType, pValue).Assignable() |
|
73 |
CRYPTOPP_GET_FUNCTION_ENTRY(Modulus) |
|
74 |
;
|
|
75 |
}
|
|
76 |
||
27
by weidai
various changes for 5.1 |
77 |
void RWFunction::AssignFrom(const NameValuePairs &source) |
1
by weidai
Initial revision |
78 |
{
|
79 |
AssignFromHelper(this, source) |
|
80 |
CRYPTOPP_SET_FUNCTION_ENTRY(Modulus) |
|
81 |
;
|
|
82 |
}
|
|
83 |
||
84 |
// *****************************************************************************
|
|
85 |
// private key operations:
|
|
86 |
||
87 |
// generate a random private key
|
|
27
by weidai
various changes for 5.1 |
88 |
void InvertibleRWFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) |
1
by weidai
Initial revision |
89 |
{
|
90 |
int modulusSize = 2048; |
|
91 |
alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize); |
|
92 |
||
93 |
if (modulusSize < 16) |
|
94 |
throw InvalidArgument("InvertibleRWFunction: specified modulus length is too small"); |
|
95 |
||
411
by weidai
port to Sun Studio 12's 64-bit C++ Compiler 5.9 Patch 124864-09 2008/12/16 |
96 |
AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize); |
1
by weidai
Initial revision |
97 |
m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 3)("Mod", 8))); |
98 |
m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 7)("Mod", 8))); |
|
99 |
||
100 |
m_n = m_p * m_q; |
|
101 |
m_u = m_q.InverseMod(m_p); |
|
102 |
}
|
|
103 |
||
27
by weidai
various changes for 5.1 |
104 |
void InvertibleRWFunction::BERDecode(BufferedTransformation &bt) |
1
by weidai
Initial revision |
105 |
{
|
106 |
BERSequenceDecoder seq(bt); |
|
107 |
m_n.BERDecode(seq); |
|
108 |
m_p.BERDecode(seq); |
|
109 |
m_q.BERDecode(seq); |
|
110 |
m_u.BERDecode(seq); |
|
111 |
seq.MessageEnd(); |
|
112 |
}
|
|
113 |
||
27
by weidai
various changes for 5.1 |
114 |
void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const |
1
by weidai
Initial revision |
115 |
{
|
116 |
DERSequenceEncoder seq(bt); |
|
117 |
m_n.DEREncode(seq); |
|
118 |
m_p.DEREncode(seq); |
|
119 |
m_q.DEREncode(seq); |
|
120 |
m_u.DEREncode(seq); |
|
121 |
seq.MessageEnd(); |
|
122 |
}
|
|
123 |
||
266
by weidai
added blinding and error checking for RW private key operation |
124 |
Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const |
1
by weidai
Initial revision |
125 |
{
|
126 |
DoQuickSanityCheck(); |
|
266
by weidai
added blinding and error checking for RW private key operation |
127 |
ModularArithmetic modn(m_n); |
128 |
Integer r, rInv; |
|
129 |
do { // do this in a loop for people using small numbers for testing |
|
130 |
r.Randomize(rng, Integer::One(), m_n - Integer::One()); |
|
131 |
rInv = modn.MultiplicativeInverse(r); |
|
132 |
} while (rInv.IsZero()); |
|
133 |
Integer re = modn.Square(r); |
|
134 |
re = modn.Multiply(re, x); // blind |
|
135 |
||
136 |
Integer cp=re%m_p, cq=re%m_q; |
|
1
by weidai
Initial revision |
137 |
if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1) |
138 |
{
|
|
266
by weidai
added blinding and error checking for RW private key operation |
139 |
cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1; |
140 |
cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1; |
|
1
by weidai
Initial revision |
141 |
}
|
142 |
||
266
by weidai
added blinding and error checking for RW private key operation |
143 |
#pragma omp parallel
|
144 |
#pragma omp sections
|
|
145 |
{
|
|
146 |
#pragma omp section
|
|
147 |
cp = ModularSquareRoot(cp, m_p); |
|
148 |
#pragma omp section
|
|
149 |
cq = ModularSquareRoot(cq, m_q); |
|
150 |
}
|
|
151 |
||
152 |
Integer y = CRT(cq, m_q, cp, m_p, m_u); |
|
153 |
y = modn.Multiply(y, rInv); // unblind |
|
154 |
y = STDMIN(y, m_n-y); |
|
155 |
if (ApplyFunction(y) != x) // check |
|
156 |
throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation"); |
|
157 |
return y; |
|
1
by weidai
Initial revision |
158 |
}
|
159 |
||
27
by weidai
various changes for 5.1 |
160 |
bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const |
1
by weidai
Initial revision |
161 |
{
|
27
by weidai
various changes for 5.1 |
162 |
bool pass = RWFunction::Validate(rng, level); |
1
by weidai
Initial revision |
163 |
pass = pass && m_p > Integer::One() && m_p%8 == 3 && m_p < m_n; |
164 |
pass = pass && m_q > Integer::One() && m_q%8 == 7 && m_q < m_n; |
|
165 |
pass = pass && m_u.IsPositive() && m_u < m_p; |
|
166 |
if (level >= 1) |
|
167 |
{
|
|
168 |
pass = pass && m_p * m_q == m_n; |
|
169 |
pass = pass && m_u * m_q % m_p == 1; |
|
170 |
}
|
|
171 |
if (level >= 2) |
|
172 |
pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2); |
|
173 |
return pass; |
|
174 |
}
|
|
175 |
||
27
by weidai
various changes for 5.1 |
176 |
bool InvertibleRWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const |
1
by weidai
Initial revision |
177 |
{
|
27
by weidai
various changes for 5.1 |
178 |
return GetValueHelper<RWFunction>(this, name, valueType, pValue).Assignable() |
1
by weidai
Initial revision |
179 |
CRYPTOPP_GET_FUNCTION_ENTRY(Prime1) |
180 |
CRYPTOPP_GET_FUNCTION_ENTRY(Prime2) |
|
181 |
CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) |
|
182 |
;
|
|
183 |
}
|
|
184 |
||
27
by weidai
various changes for 5.1 |
185 |
void InvertibleRWFunction::AssignFrom(const NameValuePairs &source) |
1
by weidai
Initial revision |
186 |
{
|
27
by weidai
various changes for 5.1 |
187 |
AssignFromHelper<RWFunction>(this, source) |
1
by weidai
Initial revision |
188 |
CRYPTOPP_SET_FUNCTION_ENTRY(Prime1) |
189 |
CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) |
|
190 |
CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) |
|
191 |
;
|
|
192 |
}
|
|
193 |
||
194 |
NAMESPACE_END
|
|
181
by weidai
changes done for FIPS-140 lab code drop |
195 |
|
196 |
#endif
|