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 Wed Jul 28 08:07:07 2004 for Crypto++ by doxygen 1.3.7