Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound 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::ChannelInitialize(const string &channel, const NameValuePairs &parameters, 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 (unsigned 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         unsigned 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         unsigned 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         unsigned 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; 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 &parameters, 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 &parameters, 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 &parameters, 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 &parameters, 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         // VC60 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
    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