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