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

Generated on Wed Jul 21 19:15:27 2004 for Crypto++ by doxygen 1.3.7-20040704