Crypto++  5.6.5
Free C++ class library of cryptographic schemes
ida.cpp
1 // ida.cpp - written and placed in the public domain by Wei Dai
2 
3 #include "pch.h"
4 #include "config.h"
5 
6 #include "ida.h"
7 #include "stdcpp.h"
8 #include "algebra.h"
9 #include "gf2_32.h"
10 #include "polynomi.h"
11 #include "polynomi.cpp"
12 
13 ANONYMOUS_NAMESPACE_BEGIN
14 const CryptoPP::GF2_32 field;
15 NAMESPACE_END
16 
17 NAMESPACE_BEGIN(CryptoPP)
18 
19 #if (defined(_MSC_VER) && (_MSC_VER < 1400)) && !defined(__MWERKS__)
20  // VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
21  typedef std::reverse_bidirectional_iterator<const byte *, const byte> RevIt;
22 #elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
23  typedef std::reverse_iterator<const byte *, std::random_access_iterator_tag, const byte> RevIt;
24 #else
25  typedef std::reverse_iterator<const byte *> RevIt;
26 #endif
27 
28 void RawIDA::IsolatedInitialize(const NameValuePairs &parameters)
29 {
30  if (!parameters.GetIntValue("RecoveryThreshold", m_threshold))
31  throw InvalidArgument("RawIDA: missing RecoveryThreshold argument");
32 
33  CRYPTOPP_ASSERT(m_threshold > 0);
34  if (m_threshold <= 0)
35  throw InvalidArgument("RawIDA: RecoveryThreshold must be greater than 0");
36 
37  m_lastMapPosition = m_inputChannelMap.end();
38  m_channelsReady = 0;
39  m_channelsFinished = 0;
40  m_w.New(m_threshold);
41  m_y.New(m_threshold);
42  m_inputQueues.reserve(m_threshold);
43 
44  m_outputChannelIds.clear();
45  m_outputChannelIdStrings.clear();
46  m_outputQueues.clear();
47 
48  word32 outputChannelID;
49  if (parameters.GetValue("OutputChannelID", outputChannelID))
50  AddOutputChannel(outputChannelID);
51  else
52  {
53  int nShares = parameters.GetIntValueWithDefault("NumberOfShares", m_threshold);
54  CRYPTOPP_ASSERT(nShares > 0);
55  if (nShares <= 0) {nShares = m_threshold;}
56  for (unsigned int i=0; i< (unsigned int)(nShares); i++)
57  AddOutputChannel(i);
58  }
59 }
60 
61 unsigned int RawIDA::InsertInputChannel(word32 channelId)
62 {
63  if (m_lastMapPosition != m_inputChannelMap.end())
64  {
65  if (m_lastMapPosition->first == channelId)
66  goto skipFind;
67  ++m_lastMapPosition;
68  if (m_lastMapPosition != m_inputChannelMap.end() && m_lastMapPosition->first == channelId)
69  goto skipFind;
70  }
71  m_lastMapPosition = m_inputChannelMap.find(channelId);
72 
73 skipFind:
74  if (m_lastMapPosition == m_inputChannelMap.end())
75  {
76  if (m_inputChannelIds.size() == size_t(m_threshold))
77  return m_threshold;
78 
79  m_lastMapPosition = m_inputChannelMap.insert(InputChannelMap::value_type(channelId, (unsigned int)m_inputChannelIds.size())).first;
80  m_inputQueues.push_back(MessageQueue());
81  m_inputChannelIds.push_back(channelId);
82 
83  if (m_inputChannelIds.size() == size_t(m_threshold))
84  PrepareInterpolation();
85  }
86  return m_lastMapPosition->second;
87 }
88 
89 unsigned int RawIDA::LookupInputChannel(word32 channelId) const
90 {
91  std::map<word32, unsigned int>::const_iterator it = m_inputChannelMap.find(channelId);
92  if (it == m_inputChannelMap.end())
93  return m_threshold;
94  else
95  return it->second;
96 }
97 
98 void RawIDA::ChannelData(word32 channelId, const byte *inString, size_t length, bool messageEnd)
99 {
100  int i = InsertInputChannel(channelId);
101  if (i < m_threshold)
102  {
103  lword size = m_inputQueues[i].MaxRetrievable();
104  m_inputQueues[i].Put(inString, length);
105  if (size < 4 && size + length >= 4)
106  {
107  m_channelsReady++;
108  if (m_channelsReady == size_t(m_threshold))
109  ProcessInputQueues();
110  }
111 
112  if (messageEnd)
113  {
114  m_inputQueues[i].MessageEnd();
115  if (m_inputQueues[i].NumberOfMessages() == 1)
116  {
117  m_channelsFinished++;
118  if (m_channelsFinished == size_t(m_threshold))
119  {
120  m_channelsReady = 0;
121  for (i=0; i<m_threshold; i++)
122  m_channelsReady += m_inputQueues[i].AnyRetrievable();
123  ProcessInputQueues();
124  }
125  }
126  }
127  }
128 }
129 
130 lword RawIDA::InputBuffered(word32 channelId) const
131 {
132  int i = LookupInputChannel(channelId);
133  return i < m_threshold ? m_inputQueues[i].MaxRetrievable() : 0;
134 }
135 
136 void RawIDA::ComputeV(unsigned int i)
137 {
138  if (i >= m_v.size())
139  {
140  m_v.resize(i+1);
141  m_outputToInput.resize(i+1);
142  }
143 
144  m_outputToInput[i] = LookupInputChannel(m_outputChannelIds[i]);
145  if (m_outputToInput[i] == size_t(m_threshold) && i * size_t(m_threshold) <= 1000*1000)
146  {
147  m_v[i].resize(m_threshold);
148  PrepareBulkPolynomialInterpolationAt(field, m_v[i].begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
149  }
150 }
151 
152 void RawIDA::AddOutputChannel(word32 channelId)
153 {
154  m_outputChannelIds.push_back(channelId);
155  m_outputChannelIdStrings.push_back(WordToString(channelId));
156  m_outputQueues.push_back(ByteQueue());
157  if (m_inputChannelIds.size() == size_t(m_threshold))
158  ComputeV((unsigned int)m_outputChannelIds.size() - 1);
159 }
160 
161 void RawIDA::PrepareInterpolation()
162 {
163  CRYPTOPP_ASSERT(m_inputChannelIds.size() == size_t(m_threshold));
164  PrepareBulkPolynomialInterpolation(field, m_w.begin(), &(m_inputChannelIds[0]), (unsigned int)(m_threshold));
165  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
166  ComputeV(i);
167 }
168 
169 void RawIDA::ProcessInputQueues()
170 {
171  bool finished = (m_channelsFinished == size_t(m_threshold));
172  unsigned int i;
173 
174  while (finished ? m_channelsReady > 0 : m_channelsReady == size_t(m_threshold))
175  {
176  m_channelsReady = 0;
177  for (i=0; i<size_t(m_threshold); i++)
178  {
179  MessageQueue &queue = m_inputQueues[i];
180  queue.GetWord32(m_y[i]);
181 
182  if (finished)
183  m_channelsReady += queue.AnyRetrievable();
184  else
185  m_channelsReady += queue.NumberOfMessages() > 0 || queue.MaxRetrievable() >= 4;
186  }
187 
188  for (i=0; (unsigned int)i<m_outputChannelIds.size(); i++)
189  {
190  if (m_outputToInput[i] != size_t(m_threshold))
191  m_outputQueues[i].PutWord32(m_y[m_outputToInput[i]]);
192  else if (m_v[i].size() == size_t(m_threshold))
193  m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_v[i].begin(), m_threshold));
194  else
195  {
196  m_u.resize(m_threshold);
197  PrepareBulkPolynomialInterpolationAt(field, m_u.begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
198  m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_u.begin(), m_threshold));
199  }
200  }
201  }
202 
203  if (m_outputChannelIds.size() > 0 && m_outputQueues[0].AnyRetrievable())
204  FlushOutputQueues();
205 
206  if (finished)
207  {
208  OutputMessageEnds();
209 
210  m_channelsReady = 0;
211  m_channelsFinished = 0;
212  m_v.clear();
213 
214  std::vector<MessageQueue> inputQueues;
215  std::vector<word32> inputChannelIds;
216 
217  inputQueues.swap(m_inputQueues);
218  inputChannelIds.swap(m_inputChannelIds);
219  m_inputChannelMap.clear();
220  m_lastMapPosition = m_inputChannelMap.end();
221 
222  for (i=0; i<size_t(m_threshold); i++)
223  {
224  inputQueues[i].GetNextMessage();
225  inputQueues[i].TransferAllTo(*AttachedTransformation(), WordToString(inputChannelIds[i]));
226  }
227  }
228 }
229 
230 void RawIDA::FlushOutputQueues()
231 {
232  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
233  m_outputQueues[i].TransferAllTo(*AttachedTransformation(), m_outputChannelIdStrings[i]);
234 }
235 
236 void RawIDA::OutputMessageEnds()
237 {
238  if (GetAutoSignalPropagation() != 0)
239  {
240  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
241  AttachedTransformation()->ChannelMessageEnd(m_outputChannelIdStrings[i], GetAutoSignalPropagation()-1);
242  }
243 }
244 
245 // ****************************************************************
246 
248 {
249  m_pad = parameters.GetValueWithDefault("AddPadding", true);
250  m_ida.IsolatedInitialize(parameters);
251 }
252 
253 size_t SecretSharing::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
254 {
255  if (!blocking)
256  throw BlockingInputOnly("SecretSharing");
257 
258  SecByteBlock buf(UnsignedMin(256, length));
259  unsigned int threshold = m_ida.GetThreshold();
260  while (length > 0)
261  {
262  size_t len = STDMIN(length, buf.size());
263  m_ida.ChannelData(0xffffffff, begin, len, false);
264  for (unsigned int i=0; i<threshold-1; i++)
265  {
266  m_rng.GenerateBlock(buf, len);
267  m_ida.ChannelData(i, buf, len, false);
268  }
269  length -= len;
270  begin += len;
271  }
272 
273  if (messageEnd)
274  {
275  m_ida.SetAutoSignalPropagation(messageEnd-1);
276  if (m_pad)
277  {
279  while (m_ida.InputBuffered(0xffffffff) > 0)
281  }
282  m_ida.ChannelData(0xffffffff, NULL, 0, true);
283  for (unsigned int i=0; i<m_ida.GetThreshold()-1; i++)
284  m_ida.ChannelData(i, NULL, 0, true);
285  }
286 
287  return 0;
288 }
289 
291 {
292  m_pad = parameters.GetValueWithDefault("RemovePadding", true);
293  RawIDA::IsolatedInitialize(CombinedNameValuePairs(parameters, MakeParameters("OutputChannelID", (word32)0xffffffff)));
294 }
295 
296 void SecretRecovery::FlushOutputQueues()
297 {
298  if (m_pad)
299  m_outputQueues[0].TransferTo(*AttachedTransformation(), m_outputQueues[0].MaxRetrievable()-4);
300  else
301  m_outputQueues[0].TransferTo(*AttachedTransformation());
302 }
303 
304 void SecretRecovery::OutputMessageEnds()
305 {
306  if (m_pad)
307  {
308  PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
309  m_outputQueues[0].TransferAllTo(paddingRemover);
310  }
311 
312  if (GetAutoSignalPropagation() != 0)
313  AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
314 }
315 
316 // ****************************************************************
317 
319 {
320  m_nextChannel = 0;
321  m_pad = parameters.GetValueWithDefault("AddPadding", true);
322  m_ida.IsolatedInitialize(parameters);
323 }
324 
325 size_t InformationDispersal::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
326 {
327  if (!blocking)
328  throw BlockingInputOnly("InformationDispersal");
329 
330  while (length--)
331  {
332  m_ida.ChannelData(m_nextChannel, begin, 1, false);
333  begin++;
334  m_nextChannel++;
335  if (m_nextChannel == m_ida.GetThreshold())
336  m_nextChannel = 0;
337  }
338 
339  if (messageEnd)
340  {
341  m_ida.SetAutoSignalPropagation(messageEnd-1);
342  if (m_pad)
344  for (word32 i=0; i<m_ida.GetThreshold(); i++)
345  m_ida.ChannelData(i, NULL, 0, true);
346  }
347 
348  return 0;
349 }
350 
352 {
353  m_pad = parameters.GetValueWithDefault("RemovePadding", true);
354  RawIDA::IsolatedInitialize(parameters);
355 }
356 
357 void InformationRecovery::FlushOutputQueues()
358 {
359  while (m_outputQueues[0].AnyRetrievable())
360  {
361  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
362  m_outputQueues[i].TransferTo(m_queue, 1);
363  }
364 
365  if (m_pad)
366  m_queue.TransferTo(*AttachedTransformation(), m_queue.MaxRetrievable()-4*m_threshold);
367  else
369 }
370 
371 void InformationRecovery::OutputMessageEnds()
372 {
373  if (m_pad)
374  {
375  PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
376  m_queue.TransferAllTo(paddingRemover);
377  }
378 
379  if (GetAutoSignalPropagation() != 0)
380  AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
381 }
382 
383 size_t PaddingRemover::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
384 {
385  if (!blocking)
386  throw BlockingInputOnly("PaddingRemover");
387 
388  const byte *const end = begin + length;
389 
390  if (m_possiblePadding)
391  {
392  size_t len = std::find_if(begin, end, std::bind2nd(std::not_equal_to<byte>(), byte(0))) - begin;
393  m_zeroCount += len;
394  begin += len;
395  if (begin == end)
396  return 0;
397 
399  while (m_zeroCount--)
401  AttachedTransformation()->Put(*begin++);
402  m_possiblePadding = false;
403  }
404 
405  const byte *x = std::find_if(RevIt(end), RevIt(begin), std::bind2nd(std::not_equal_to<byte>(), byte(0))).base();
406  if (x != begin && *(x-1) == 1)
407  {
408  AttachedTransformation()->Put(begin, x-begin-1);
409  m_possiblePadding = true;
410  m_zeroCount = end - x;
411  }
412  else
413  AttachedTransformation()->Put(begin, end-begin);
414 
415  if (messageEnd)
416  {
417  m_possiblePadding = false;
418  Output(0, begin, length, messageEnd, blocking);
419  }
420  return 0;
421 }
422 
423 NAMESPACE_END
An invalid argument was detected.
Definition: cryptlib.h:184
virtual bool AnyRetrievable() const
Determines whether bytes are ready for retrieval.
Definition: cryptlib.cpp:504
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:350
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: cryptlib.cpp:326
Message Queue.
Definition: mqueue.h:14
unsigned int NumberOfMessages() const
Provides the number of meesages processed by this object.
Definition: mqueue.h:48
void resize(size_type newSize)
Change size and preserve contents.
Definition: secblock.h:705
Library configuration file.
void New(size_type newSize)
Change size without preserving contents.
Definition: secblock.h:647
Combines two sets of NameValuePairs.
Definition: algparam.h:135
SecBlock typedef.
Definition: secblock.h:731
Classes for performing mathematics over different fields.
lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: mqueue.h:38
lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: queue.h:35
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
bool GetIntValue(const char *name, int &value) const
Get a named value with type int.
Definition: cryptlib.h:373
bool MessageEnd(int propagation=-1, bool blocking=true)
Signals the end of messages to the object.
Definition: cryptlib.h:1434
bool AnyRetrievable() const
Determines whether bytes are ready for retrieval.
Definition: mqueue.h:40
Classes and functions for schemes over GF(2^32)
bool GetValue(const char *name, T &value) const
Get a named value.
Definition: cryptlib.h:337
lword TransferTo(BufferedTransformation &target, lword transferMax=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL)
move transferMax bytes of the buffered output to target as input
Definition: cryptlib.h:1654
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
int GetIntValueWithDefault(const char *name, int defaultValue) const
Get a named value with type int, with default.
Definition: cryptlib.h:382
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1376
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:500
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
BufferedTransformation * AttachedTransformation()
Retrieve attached transformation.
Definition: filters.cpp:36
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Definition: misc.h:512
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:477
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:62
Classes for polynomial basis and operations.
Redirect input to another BufferedTransformation without owning it.
Definition: filters.h:808
Data structure used to store byte strings.
Definition: queue.h:20
iterator begin()
Provides an iterator pointing to the first element in the memory block.
Definition: secblock.h:499
size_t PutWord32(word32 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 32-bit word for processing.
Definition: cryptlib.cpp:719
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
size_t GetWord32(word32 &value, ByteOrder order=BIG_ENDIAN_ORDER)
Retrieve a 32-bit word.
Definition: cryptlib.cpp:767
void TransferAllTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL)
Transfer all bytes from this object to another BufferedTransformation.
Definition: cryptlib.h:1763
virtual unsigned int NumberOfMessages() const
Provides the number of meesages processed by this object.
Definition: cryptlib.cpp:569
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:496
void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs)
Initialize or reinitialize this object, without signal propagation.
Crypto++ library namespace.
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
Classes for Rabin's Information Dispersal and Shamir's Secret Sharing algorithms. ...
bool ChannelMessageEnd(const std::string &channel, int propagation=-1, bool blocking=true)
Signal the end of a message.
Definition: cryptlib.h:1913
Interface for retrieving values given their names.
Definition: cryptlib.h:279