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);