Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | 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::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 (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 &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

Generated on Sun Mar 14 20:44:26 2004 for Crypto++ by doxygen 1.3.6-20040222