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::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

Generated on Sun Jul 3 00:20:17 2005 for Crypto++ by  doxygen 1.4.3-20050530