00001
00002
00003 #include "pch.h"
00004 #include "ida.h"
00005
00006 #include "algebra.h"
00007 #include "gf2_32.h"
00008 #include "polynomi.h"
00009
00010 #include "polynomi.cpp"
00011
00012 ANONYMOUS_NAMESPACE_BEGIN
00013 static const CryptoPP::GF2_32 field;
00014 NAMESPACE_END
00015
00016 using namespace std;
00017
00018 NAMESPACE_BEGIN(CryptoPP)
00019
00020 void RawIDA::IsolatedInitialize(const NameValuePairs ¶meters)
00021 {
00022 if (!parameters.GetIntValue("RecoveryThreshold", m_threshold))
00023 throw InvalidArgument("RawIDA: missing RecoveryThreshold argument");
00024
00025 if (m_threshold <= 0)
00026 throw InvalidArgument("RawIDA: RecoveryThreshold must be greater than 0");
00027
00028 m_lastMapPosition = m_inputChannelMap.end();
00029 m_channelsReady = 0;
00030 m_channelsFinished = 0;
00031 m_w.New(m_threshold);
00032 m_y.New(m_threshold);
00033 m_inputQueues.reserve(m_threshold);
00034
00035 m_outputChannelIds.clear();
00036 m_outputChannelIdStrings.clear();
00037 m_outputQueues.clear();
00038
00039 word32 outputChannelID;
00040 if (parameters.GetValue("OutputChannelID", outputChannelID))
00041 AddOutputChannel(outputChannelID);
00042 else
00043 {
00044 int nShares = parameters.GetIntValueWithDefault("NumberOfShares", m_threshold);
00045 for (int i=0; i<nShares; i++)
00046 AddOutputChannel(i);
00047 }
00048 }
00049
00050 unsigned int RawIDA::InsertInputChannel(word32 channelId)
00051 {
00052 if (m_lastMapPosition != m_inputChannelMap.end())
00053 {
00054 if (m_lastMapPosition->first == channelId)
00055 goto skipFind;
00056 ++m_lastMapPosition;
00057 if (m_lastMapPosition != m_inputChannelMap.end() && m_lastMapPosition->first == channelId)
00058 goto skipFind;
00059 }
00060 m_lastMapPosition = m_inputChannelMap.find(channelId);
00061
00062 skipFind:
00063 if (m_lastMapPosition == m_inputChannelMap.end())
00064 {
00065 if (m_inputChannelIds.size() == m_threshold)
00066 return m_threshold;
00067
00068 m_lastMapPosition = m_inputChannelMap.insert(InputChannelMap::value_type(channelId, (unsigned int)m_inputChannelIds.size())).first;
00069 m_inputQueues.push_back(MessageQueue());
00070 m_inputChannelIds.push_back(channelId);
00071
00072 if (m_inputChannelIds.size() == m_threshold)
00073 PrepareInterpolation();
00074 }
00075 return m_lastMapPosition->second;
00076 }
00077
00078 unsigned int RawIDA::LookupInputChannel(word32 channelId) const
00079 {
00080 map<word32, unsigned int>::const_iterator it = m_inputChannelMap.find(channelId);
00081 if (it == m_inputChannelMap.end())
00082 return m_threshold;
00083 else
00084 return it->second;
00085 }
00086
00087 void RawIDA::ChannelData(word32 channelId, const byte *inString, size_t length, bool messageEnd)
00088 {
00089 int i = InsertInputChannel(channelId);
00090 if (i < m_threshold)
00091 {
00092 lword size = m_inputQueues[i].MaxRetrievable();
00093 m_inputQueues[i].Put(inString, length);
00094 if (size < 4 && size + length >= 4)
00095 {
00096 m_channelsReady++;
00097 if (m_channelsReady == m_threshold)
00098 ProcessInputQueues();
00099 }
00100
00101 if (messageEnd)
00102 {
00103 m_inputQueues[i].MessageEnd();
00104 if (m_inputQueues[i].NumberOfMessages() == 1)
00105 {
00106 m_channelsFinished++;
00107 if (m_channelsFinished == m_threshold)
00108 {
00109 m_channelsReady = 0;
00110 for (i=0; i<m_threshold; i++)
00111 m_channelsReady += m_inputQueues[i].AnyRetrievable();
00112 ProcessInputQueues();
00113 }
00114 }
00115 }
00116 }
00117 }
00118
00119 lword RawIDA::InputBuffered(word32 channelId) const
00120 {
00121 int i = LookupInputChannel(channelId);
00122 return i < m_threshold ? m_inputQueues[i].MaxRetrievable() : 0;
00123 }
00124
00125 void RawIDA::ComputeV(unsigned int i)
00126 {
00127 if (i >= m_v.size())
00128 {
00129 m_v.resize(i+1);
00130 m_outputToInput.resize(i+1);
00131 }
00132
00133 m_outputToInput[i] = LookupInputChannel(m_outputChannelIds[i]);
00134 if (m_outputToInput[i] == m_threshold && i * m_threshold <= 1000*1000)
00135 {
00136 m_v[i].resize(m_threshold);
00137 PrepareBulkPolynomialInterpolationAt(field, m_v[i].begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
00138 }
00139 }
00140
00141 void RawIDA::AddOutputChannel(word32 channelId)
00142 {
00143 m_outputChannelIds.push_back(channelId);
00144 m_outputChannelIdStrings.push_back(WordToString(channelId));
00145 m_outputQueues.push_back(ByteQueue());
00146 if (m_inputChannelIds.size() == m_threshold)
00147 ComputeV((unsigned int)m_outputChannelIds.size() - 1);
00148 }
00149
00150 void RawIDA::PrepareInterpolation()
00151 {
00152 assert(m_inputChannelIds.size() == m_threshold);
00153 PrepareBulkPolynomialInterpolation(field, m_w.begin(), &(m_inputChannelIds[0]), m_threshold);
00154 for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
00155 ComputeV(i);
00156 }
00157
00158 void RawIDA::ProcessInputQueues()
00159 {
00160 bool finished = (m_channelsFinished == m_threshold);
00161 int i;
00162
00163 while (finished ? m_channelsReady > 0 : m_channelsReady == m_threshold)
00164 {
00165 m_channelsReady = 0;
00166 for (i=0; i<m_threshold; i++)
00167 {
00168 MessageQueue &queue = m_inputQueues[i];
00169 queue.GetWord32(m_y[i]);
00170
00171 if (finished)
00172 m_channelsReady += queue.AnyRetrievable();
00173 else
00174 m_channelsReady += queue.NumberOfMessages() > 0 || queue.MaxRetrievable() >= 4;
00175 }
00176
00177 for (i=0; (unsigned int)i<m_outputChannelIds.size(); i++)
00178 {
00179 if (m_outputToInput[i] != m_threshold)
00180 m_outputQueues[i].PutWord32(m_y[m_outputToInput[i]]);
00181 else if (m_v[i].size() == m_threshold)
00182 m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_v[i].begin(), m_threshold));
00183 else
00184 {
00185 m_u.resize(m_threshold);
00186 PrepareBulkPolynomialInterpolationAt(field, m_u.begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
00187 m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_u.begin(), m_threshold));
00188 }
00189 }
00190 }
00191
00192 if (m_outputChannelIds.size() > 0 && m_outputQueues[0].AnyRetrievable())
00193 FlushOutputQueues();
00194
00195 if (finished)
00196 {
00197 OutputMessageEnds();
00198
00199 m_channelsReady = 0;
00200 m_channelsFinished = 0;
00201 m_v.clear();
00202
00203 vector<MessageQueue> inputQueues;
00204 vector<word32> inputChannelIds;
00205
00206 inputQueues.swap(m_inputQueues);
00207 inputChannelIds.swap(m_inputChannelIds);
00208 m_inputChannelMap.clear();
00209 m_lastMapPosition = m_inputChannelMap.end();
00210
00211 for (i=0; i<m_threshold; i++)
00212 {
00213 inputQueues[i].GetNextMessage();
00214 inputQueues[i].TransferAllTo(*AttachedTransformation(), WordToString(inputChannelIds[i]));
00215 }
00216 }
00217 }
00218
00219 void RawIDA::FlushOutputQueues()
00220 {
00221 for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
00222 m_outputQueues[i].TransferAllTo(*AttachedTransformation(), m_outputChannelIdStrings[i]);
00223 }
00224
00225 void RawIDA::OutputMessageEnds()
00226 {
00227 if (GetAutoSignalPropagation() != 0)
00228 {
00229 for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
00230 AttachedTransformation()->ChannelMessageEnd(m_outputChannelIdStrings[i], GetAutoSignalPropagation()-1);
00231 }
00232 }
00233
00234
00235
00236 void SecretSharing::IsolatedInitialize(const NameValuePairs ¶meters)
00237 {
00238 m_pad = parameters.GetValueWithDefault("AddPadding", true);
00239 m_ida.IsolatedInitialize(parameters);
00240 }
00241
00242 size_t SecretSharing::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
00243 {
00244 if (!blocking)
00245 throw BlockingInputOnly("SecretSharing");
00246
00247 SecByteBlock buf(UnsignedMin(256, length));
00248 unsigned int threshold = m_ida.GetThreshold();
00249 while (length > 0)
00250 {
00251 size_t len = STDMIN(length, buf.size());
00252 m_ida.ChannelData(0xffffffff, begin, len, false);
00253 for (unsigned int i=0; i<threshold-1; i++)
00254 {
00255 m_rng.GenerateBlock(buf, len);
00256 m_ida.ChannelData(i, buf, len, false);
00257 }
00258 length -= len;
00259 begin += len;
00260 }
00261
00262 if (messageEnd)
00263 {
00264 m_ida.SetAutoSignalPropagation(messageEnd-1);
00265 if (m_pad)
00266 {
00267 SecretSharing::Put(1);
00268 while (m_ida.InputBuffered(0xffffffff) > 0)
00269 SecretSharing::Put(0);
00270 }
00271 m_ida.ChannelData(0xffffffff, NULL, 0, true);
00272 for (unsigned int i=0; i<m_ida.GetThreshold()-1; i++)
00273 m_ida.ChannelData(i, NULL, 0, true);
00274 }
00275
00276 return 0;
00277 }
00278
00279 void SecretRecovery::IsolatedInitialize(const NameValuePairs ¶meters)
00280 {
00281 m_pad = parameters.GetValueWithDefault("RemovePadding", true);
00282 RawIDA::IsolatedInitialize(CombinedNameValuePairs(parameters, MakeParameters("OutputChannelID", (word32)0xffffffff)));
00283 }
00284
00285 void SecretRecovery::FlushOutputQueues()
00286 {
00287 if (m_pad)
00288 m_outputQueues[0].TransferTo(*AttachedTransformation(), m_outputQueues[0].MaxRetrievable()-4);
00289 else
00290 m_outputQueues[0].TransferTo(*AttachedTransformation());
00291 }
00292
00293 void SecretRecovery::OutputMessageEnds()
00294 {
00295 if (m_pad)
00296 {
00297 PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
00298 m_outputQueues[0].TransferAllTo(paddingRemover);
00299 }
00300
00301 if (GetAutoSignalPropagation() != 0)
00302 AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
00303 }
00304
00305
00306
00307 void InformationDispersal::IsolatedInitialize(const NameValuePairs ¶meters)
00308 {
00309 m_nextChannel = 0;
00310 m_pad = parameters.GetValueWithDefault("AddPadding", true);
00311 m_ida.IsolatedInitialize(parameters);
00312 }
00313
00314 size_t InformationDispersal::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
00315 {
00316 if (!blocking)
00317 throw BlockingInputOnly("InformationDispersal");
00318
00319 while (length--)
00320 {
00321 m_ida.ChannelData(m_nextChannel, begin, 1, false);
00322 begin++;
00323 m_nextChannel++;
00324 if (m_nextChannel == m_ida.GetThreshold())
00325 m_nextChannel = 0;
00326 }
00327
00328 if (messageEnd)
00329 {
00330 m_ida.SetAutoSignalPropagation(messageEnd-1);
00331 if (m_pad)
00332 InformationDispersal::Put(1);
00333 for (word32 i=0; i<m_ida.GetThreshold(); i++)
00334 m_ida.ChannelData(i, NULL, 0, true);
00335 }
00336
00337 return 0;
00338 }
00339
00340 void InformationRecovery::IsolatedInitialize(const NameValuePairs ¶meters)
00341 {
00342 m_pad = parameters.GetValueWithDefault("RemovePadding", true);
00343 RawIDA::IsolatedInitialize(parameters);
00344 }
00345
00346 void InformationRecovery::FlushOutputQueues()
00347 {
00348 while (m_outputQueues[0].AnyRetrievable())
00349 {
00350 for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
00351 m_outputQueues[i].TransferTo(m_queue, 1);
00352 }
00353
00354 if (m_pad)
00355 m_queue.TransferTo(*AttachedTransformation(), m_queue.MaxRetrievable()-4*m_threshold);
00356 else
00357 m_queue.TransferTo(*AttachedTransformation());
00358 }
00359
00360 void InformationRecovery::OutputMessageEnds()
00361 {
00362 if (m_pad)
00363 {
00364 PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
00365 m_queue.TransferAllTo(paddingRemover);
00366 }
00367
00368 if (GetAutoSignalPropagation() != 0)
00369 AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
00370 }
00371
00372 size_t PaddingRemover::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
00373 {
00374 if (!blocking)
00375 throw BlockingInputOnly("PaddingRemover");
00376
00377 const byte *const end = begin + length;
00378
00379 if (m_possiblePadding)
00380 {
00381 size_t len = find_if(begin, end, bind2nd(not_equal_to<byte>(), 0)) - begin;
00382 m_zeroCount += len;
00383 begin += len;
00384 if (begin == end)
00385 return 0;
00386
00387 AttachedTransformation()->Put(1);
00388 while (m_zeroCount--)
00389 AttachedTransformation()->Put(0);
00390 AttachedTransformation()->Put(*begin++);
00391 m_possiblePadding = false;
00392 }
00393
00394 #if defined(_MSC_VER) && !defined(__MWERKS__) && (_MSC_VER < 1300)
00395
00396 typedef reverse_bidirectional_iterator<const byte *, const byte> RevIt;
00397 #else
00398 typedef reverse_iterator<const byte *> RevIt;
00399 #endif
00400 const byte *x = find_if(RevIt(end), RevIt(begin), bind2nd(not_equal_to<byte>(), 0)).base();
00401 if (x != begin && *(x-1) == 1)
00402 {
00403 AttachedTransformation()->Put(begin, x-begin-1);
00404 m_possiblePadding = true;
00405 m_zeroCount = end - x;
00406 }
00407 else
00408 AttachedTransformation()->Put(begin, end-begin);
00409
00410 if (messageEnd)
00411 {
00412 m_possiblePadding = false;
00413 Output(0, begin, length, messageEnd, blocking);
00414 }
00415 return 0;
00416 }
00417
00418 NAMESPACE_END