11 #include "polynomi.cpp"
13 ANONYMOUS_NAMESPACE_BEGIN
14 static const CryptoPP::GF2_32 field;
19 NAMESPACE_BEGIN(CryptoPP)
23 if (!parameters.GetIntValue(
"RecoveryThreshold", m_threshold))
27 throw InvalidArgument(
"RawIDA: RecoveryThreshold must be greater than 0");
29 m_lastMapPosition = m_inputChannelMap.end();
31 m_channelsFinished = 0;
34 m_inputQueues.reserve(m_threshold);
36 m_outputChannelIds.clear();
37 m_outputChannelIdStrings.clear();
38 m_outputQueues.clear();
40 word32 outputChannelID;
41 if (parameters.GetValue(
"OutputChannelID", outputChannelID))
42 AddOutputChannel(outputChannelID);
45 int nShares = parameters.GetIntValueWithDefault(
"NumberOfShares", m_threshold);
46 for (
int i=0; i<nShares; i++)
51 unsigned int RawIDA::InsertInputChannel(word32 channelId)
53 if (m_lastMapPosition != m_inputChannelMap.end())
55 if (m_lastMapPosition->first == channelId)
58 if (m_lastMapPosition != m_inputChannelMap.end() && m_lastMapPosition->first == channelId)
61 m_lastMapPosition = m_inputChannelMap.find(channelId);
64 if (m_lastMapPosition == m_inputChannelMap.end())
66 if (m_inputChannelIds.size() == m_threshold)
69 m_lastMapPosition = m_inputChannelMap.insert(InputChannelMap::value_type(channelId, (
unsigned int)m_inputChannelIds.size())).first;
71 m_inputChannelIds.push_back(channelId);
73 if (m_inputChannelIds.size() == m_threshold)
74 PrepareInterpolation();
76 return m_lastMapPosition->second;
79 unsigned int RawIDA::LookupInputChannel(word32 channelId)
const
81 map<word32, unsigned int>::const_iterator it = m_inputChannelMap.find(channelId);
82 if (it == m_inputChannelMap.end())
88 void RawIDA::ChannelData(word32 channelId,
const byte *inString,
size_t length,
bool messageEnd)
90 int i = InsertInputChannel(channelId);
93 lword size = m_inputQueues[i].MaxRetrievable();
94 m_inputQueues[i].Put(inString, length);
95 if (size < 4 && size + length >= 4)
98 if (m_channelsReady == m_threshold)
104 m_inputQueues[i].MessageEnd();
105 if (m_inputQueues[i].NumberOfMessages() == 1)
107 m_channelsFinished++;
108 if (m_channelsFinished == m_threshold)
111 for (i=0; i<m_threshold; i++)
112 m_channelsReady += m_inputQueues[i].AnyRetrievable();
113 ProcessInputQueues();
120 lword RawIDA::InputBuffered(word32 channelId)
const
122 int i = LookupInputChannel(channelId);
123 return i < m_threshold ? m_inputQueues[i].MaxRetrievable() : 0;
126 void RawIDA::ComputeV(
unsigned int i)
131 m_outputToInput.resize(i+1);
134 m_outputToInput[i] = LookupInputChannel(m_outputChannelIds[i]);
135 if (m_outputToInput[i] == m_threshold && i * m_threshold <= 1000*1000)
137 m_v[i].resize(m_threshold);
138 PrepareBulkPolynomialInterpolationAt(field, m_v[i].begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
142 void RawIDA::AddOutputChannel(word32 channelId)
144 m_outputChannelIds.push_back(channelId);
145 m_outputChannelIdStrings.push_back(WordToString(channelId));
147 if (m_inputChannelIds.size() == m_threshold)
148 ComputeV((
unsigned int)m_outputChannelIds.size() - 1);
151 void RawIDA::PrepareInterpolation()
153 assert(m_inputChannelIds.size() == m_threshold);
154 PrepareBulkPolynomialInterpolation(field, m_w.begin(), &(m_inputChannelIds[0]), m_threshold);
155 for (
unsigned int i=0; i<m_outputChannelIds.size(); i++)
159 void RawIDA::ProcessInputQueues()
161 bool finished = (m_channelsFinished == m_threshold);
164 while (finished ? m_channelsReady > 0 : m_channelsReady == m_threshold)
167 for (i=0; i<m_threshold; i++)
178 for (i=0; (
unsigned int)i<m_outputChannelIds.size(); i++)
180 if (m_outputToInput[i] != m_threshold)
181 m_outputQueues[i].PutWord32(m_y[m_outputToInput[i]]);
182 else if (m_v[i].size() == m_threshold)
183 m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_v[i].begin(), m_threshold));
186 m_u.resize(m_threshold);
187 PrepareBulkPolynomialInterpolationAt(field, m_u.begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
188 m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_u.begin(), m_threshold));
193 if (m_outputChannelIds.size() > 0 && m_outputQueues[0].AnyRetrievable())
201 m_channelsFinished = 0;
204 vector<MessageQueue> inputQueues;
205 vector<word32> inputChannelIds;
207 inputQueues.swap(m_inputQueues);
208 inputChannelIds.swap(m_inputChannelIds);
209 m_inputChannelMap.clear();
210 m_lastMapPosition = m_inputChannelMap.end();
212 for (i=0; i<m_threshold; i++)
214 inputQueues[i].GetNextMessage();
215 inputQueues[i].TransferAllTo(*AttachedTransformation(), WordToString(inputChannelIds[i]));
220 void RawIDA::FlushOutputQueues()
222 for (
unsigned int i=0; i<m_outputChannelIds.size(); i++)
223 m_outputQueues[i].TransferAllTo(*AttachedTransformation(), m_outputChannelIdStrings[i]);
226 void RawIDA::OutputMessageEnds()
228 if (GetAutoSignalPropagation() != 0)
230 for (
unsigned int i=0; i<m_outputChannelIds.size(); i++)
231 AttachedTransformation()->ChannelMessageEnd(m_outputChannelIdStrings[i], GetAutoSignalPropagation()-1);
237 void SecretSharing::IsolatedInitialize(
const NameValuePairs ¶meters)
240 m_ida.IsolatedInitialize(parameters);
243 size_t SecretSharing::Put2(
const byte *begin,
size_t length,
int messageEnd,
bool blocking)
246 throw BlockingInputOnly(
"SecretSharing");
249 unsigned int threshold = m_ida.GetThreshold();
252 size_t len = STDMIN(length, buf.size());
253 m_ida.ChannelData(0xffffffff, begin, len,
false);
254 for (
unsigned int i=0; i<threshold-1; i++)
256 m_rng.GenerateBlock(buf, len);
257 m_ida.ChannelData(i, buf, len,
false);
265 m_ida.SetAutoSignalPropagation(messageEnd-1);
269 while (m_ida.InputBuffered(0xffffffff) > 0)
272 m_ida.ChannelData(0xffffffff, NULL, 0,
true);
273 for (
unsigned int i=0; i<m_ida.GetThreshold()-1; i++)
274 m_ida.ChannelData(i, NULL, 0,
true);
280 void SecretRecovery::IsolatedInitialize(
const NameValuePairs ¶meters)
283 RawIDA::IsolatedInitialize(
CombinedNameValuePairs(parameters, MakeParameters(
"OutputChannelID", (word32)0xffffffff)));
286 void SecretRecovery::FlushOutputQueues()
289 m_outputQueues[0].TransferTo(*AttachedTransformation(), m_outputQueues[0].MaxRetrievable()-4);
291 m_outputQueues[0].TransferTo(*AttachedTransformation());
294 void SecretRecovery::OutputMessageEnds()
299 m_outputQueues[0].TransferAllTo(paddingRemover);
302 if (GetAutoSignalPropagation() != 0)
303 AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
308 void InformationDispersal::IsolatedInitialize(
const NameValuePairs ¶meters)
312 m_ida.IsolatedInitialize(parameters);
318 throw BlockingInputOnly(
"InformationDispersal");
322 m_ida.ChannelData(m_nextChannel, begin, 1,
false);
325 if (m_nextChannel == m_ida.GetThreshold())
331 m_ida.SetAutoSignalPropagation(messageEnd-1);
334 for (word32 i=0; i<m_ida.GetThreshold(); i++)
335 m_ida.ChannelData(i, NULL, 0,
true);
341 void InformationRecovery::IsolatedInitialize(
const NameValuePairs ¶meters)
344 RawIDA::IsolatedInitialize(parameters);
347 void InformationRecovery::FlushOutputQueues()
349 while (m_outputQueues[0].AnyRetrievable())
351 for (
unsigned int i=0; i<m_outputChannelIds.size(); i++)
352 m_outputQueues[i].TransferTo(m_queue, 1);
356 m_queue.TransferTo(*AttachedTransformation(), m_queue.MaxRetrievable()-4*m_threshold);
358 m_queue.TransferTo(*AttachedTransformation());
361 void InformationRecovery::OutputMessageEnds()
366 m_queue.TransferAllTo(paddingRemover);
369 if (GetAutoSignalPropagation() != 0)
370 AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
376 throw BlockingInputOnly(
"PaddingRemover");
378 const byte *
const end = begin + length;
380 if (m_possiblePadding)
382 size_t len = find_if(begin, end, bind2nd(not_equal_to<byte>(), 0)) - begin;
388 AttachedTransformation()->Put(1);
389 while (m_zeroCount--)
390 AttachedTransformation()->Put(0);
391 AttachedTransformation()->Put(*begin++);
392 m_possiblePadding =
false;
395 #if defined(_MSC_VER) && !defined(__MWERKS__) && (_MSC_VER <= 1300)
397 typedef reverse_bidirectional_iterator<const byte *, const byte> RevIt;
398 #elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
399 typedef reverse_iterator<const byte *, random_access_iterator_tag, const byte> RevIt;
401 typedef reverse_iterator<const byte *> RevIt;
403 const byte *x = find_if(RevIt(end), RevIt(begin), bind2nd(not_equal_to<byte>(), 0)).base();
404 if (x != begin && *(x-1) == 1)
406 AttachedTransformation()->Put(begin, x-begin-1);
407 m_possiblePadding =
true;
408 m_zeroCount = end - x;
411 AttachedTransformation()->Put(begin, end-begin);
415 m_possiblePadding =
false;
416 Output(0, begin, length, messageEnd, blocking);
exception thrown when an invalid argument is detected
T GetValueWithDefault(const char *name, T defaultValue) const
get a named value, returns the default if the name doesn't exist
unsigned int NumberOfMessages() const
number of times MessageEnd() has been received minus messages retrieved or skipped ...
base class for secret sharing and information dispersal
lword MaxRetrievable() const
returns number of bytes that is currently ready for retrieval
bool AnyRetrievable() const
returns whether any bytes are currently ready for retrieval
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
input multiple bytes for blocking or non-blocking processing
Redirect input to another BufferedTransformation without owning it.
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
input multiple bytes for blocking or non-blocking processing
interface for retrieving values given their names