Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members

# ida.cpp

    00001 // ida.cpp - written and placed in the public domain by Wei Dai
    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 &parameters)
    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(pair<const unsigned long, unsigned int>(channelId, 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, unsigned int length, bool messageEnd)
    00088 {
    00089         int i = InsertInputChannel(channelId);
    00090         if (i < m_threshold)
    00091         {
    00092                 unsigned long 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 unsigned int 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(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 &parameters)
    00237 {
    00238         m_pad = parameters.GetValueWithDefault("AddPadding", true);
    00239         m_ida.IsolatedInitialize(parameters);
    00240 }
    00241
    00242 unsigned int SecretSharing::Put2(const byte *begin, unsigned int length, int messageEnd, bool blocking)
    00243 {
    00244         if (!blocking)
    00245                 throw BlockingInputOnly("SecretSharing");
    00246
    00247         SecByteBlock buf(STDMIN(length, 256U));
    00248         unsigned int threshold = m_ida.GetThreshold();
    00249         while (length > 0)
    00250         {
    00251                 unsigned int len = STDMIN(length, (unsigned int)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 &parameters)
    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 &parameters)
    00308 {
    00309         m_nextChannel = 0;
    00310         m_pad = parameters.GetValueWithDefault("AddPadding", true);
    00311         m_ida.IsolatedInitialize(parameters);
    00312 }
    00313
    00314 unsigned int InformationDispersal::Put2(const byte *begin, unsigned int 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 &parameters)
    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 unsigned int PaddingRemover::Put2(const byte *begin, unsigned int 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                 unsigned int 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         // VC60 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
    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