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