Crypto++  5.6.3
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 "algebra.h"
8 #include "gf2_32.h"
9 #include "polynomi.h"
10 #include "polynomi.cpp"
11 
12 #include <functional>
13 
14 ANONYMOUS_NAMESPACE_BEGIN
15 static const CryptoPP::GF2_32 field;
16 NAMESPACE_END
17 
18 NAMESPACE_BEGIN(CryptoPP)
19 
20 void RawIDA::IsolatedInitialize(const NameValuePairs &parameters)
21 {
22  if (!parameters.GetIntValue("RecoveryThreshold", m_threshold))
23  throw InvalidArgument("RawIDA: missing RecoveryThreshold argument");
24 
25  assert(m_threshold > 0);
26  if (m_threshold <= 0)
27  throw InvalidArgument("RawIDA: RecoveryThreshold must be greater than 0");
28 
29  m_lastMapPosition = m_inputChannelMap.end();
30  m_channelsReady = 0;
31  m_channelsFinished = 0;
32  m_w.New(m_threshold);
33  m_y.New(m_threshold);
34  m_inputQueues.reserve(m_threshold);
35 
36  m_outputChannelIds.clear();
37  m_outputChannelIdStrings.clear();
38  m_outputQueues.clear();
39 
40  word32 outputChannelID;
41  if (parameters.GetValue("OutputChannelID", outputChannelID))
42  AddOutputChannel(outputChannelID);
43  else
44  {
45  int nShares = parameters.GetIntValueWithDefault("NumberOfShares", m_threshold);
46  assert(nShares > 0);
47  if (nShares <= 0) {nShares = m_threshold;}
48  for (unsigned int i=0; i< (unsigned int)(nShares); i++)
49  AddOutputChannel(i);
50  }
51 }
52 
53 unsigned int RawIDA::InsertInputChannel(word32 channelId)
54 {
55  if (m_lastMapPosition != m_inputChannelMap.end())
56  {
57  if (m_lastMapPosition->first == channelId)
58  goto skipFind;
59  ++m_lastMapPosition;
60  if (m_lastMapPosition != m_inputChannelMap.end() && m_lastMapPosition->first == channelId)
61  goto skipFind;
62  }
63  m_lastMapPosition = m_inputChannelMap.find(channelId);
64 
65 skipFind:
66  if (m_lastMapPosition == m_inputChannelMap.end())
67  {
68  if (m_inputChannelIds.size() == size_t(m_threshold))
69  return m_threshold;
70 
71  m_lastMapPosition = m_inputChannelMap.insert(InputChannelMap::value_type(channelId, (unsigned int)m_inputChannelIds.size())).first;
72  m_inputQueues.push_back(MessageQueue());
73  m_inputChannelIds.push_back(channelId);
74 
75  if (m_inputChannelIds.size() == size_t(m_threshold))
76  PrepareInterpolation();
77  }
78  return m_lastMapPosition->second;
79 }
80 
81 unsigned int RawIDA::LookupInputChannel(word32 channelId) const
82 {
83  std::map<word32, unsigned int>::const_iterator it = m_inputChannelMap.find(channelId);
84  if (it == m_inputChannelMap.end())
85  return m_threshold;
86  else
87  return it->second;
88 }
89 
90 void RawIDA::ChannelData(word32 channelId, const byte *inString, size_t length, bool messageEnd)
91 {
92  int i = InsertInputChannel(channelId);
93  if (i < m_threshold)
94  {
95  lword size = m_inputQueues[i].MaxRetrievable();
96  m_inputQueues[i].Put(inString, length);
97  if (size < 4 && size + length >= 4)
98  {
99  m_channelsReady++;
100  if (m_channelsReady == size_t(m_threshold))
101  ProcessInputQueues();
102  }
103 
104  if (messageEnd)
105  {
106  m_inputQueues[i].MessageEnd();
107  if (m_inputQueues[i].NumberOfMessages() == 1)
108  {
109  m_channelsFinished++;
110  if (m_channelsFinished == size_t(m_threshold))
111  {
112  m_channelsReady = 0;
113  for (i=0; i<m_threshold; i++)
114  m_channelsReady += m_inputQueues[i].AnyRetrievable();
115  ProcessInputQueues();
116  }
117  }
118  }
119  }
120 }
121 
122 lword RawIDA::InputBuffered(word32 channelId) const
123 {
124  int i = LookupInputChannel(channelId);
125  return i < m_threshold ? m_inputQueues[i].MaxRetrievable() : 0;
126 }
127 
128 void RawIDA::ComputeV(unsigned int i)
129 {
130  if (i >= m_v.size())
131  {
132  m_v.resize(i+1);
133  m_outputToInput.resize(i+1);
134  }
135 
136  m_outputToInput[i] = LookupInputChannel(m_outputChannelIds[i]);
137  if (m_outputToInput[i] == size_t(m_threshold) && i * size_t(m_threshold) <= 1000*1000)
138  {
139  m_v[i].resize(m_threshold);
140  PrepareBulkPolynomialInterpolationAt(field, m_v[i].begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
141  }
142 }
143 
144 void RawIDA::AddOutputChannel(word32 channelId)
145 {
146  m_outputChannelIds.push_back(channelId);
147  m_outputChannelIdStrings.push_back(WordToString(channelId));
148  m_outputQueues.push_back(ByteQueue());
149  if (m_inputChannelIds.size() == size_t(m_threshold))
150  ComputeV((unsigned int)m_outputChannelIds.size() - 1);
151 }
152 
153 void RawIDA::PrepareInterpolation()
154 {
155  assert(m_inputChannelIds.size() == size_t(m_threshold));
156  PrepareBulkPolynomialInterpolation(field, m_w.begin(), &(m_inputChannelIds[0]), (unsigned int)(m_threshold));
157  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
158  ComputeV(i);
159 }
160 
161 void RawIDA::ProcessInputQueues()
162 {
163  bool finished = (m_channelsFinished == size_t(m_threshold));
164  unsigned int i;
165 
166  while (finished ? m_channelsReady > 0 : m_channelsReady == size_t(m_threshold))
167  {
168  m_channelsReady = 0;
169  for (i=0; i<size_t(m_threshold); i++)
170  {
171  MessageQueue &queue = m_inputQueues[i];
172  queue.GetWord32(m_y[i]);
173 
174  if (finished)
175  m_channelsReady += queue.AnyRetrievable();
176  else
177  m_channelsReady += queue.NumberOfMessages() > 0 || queue.MaxRetrievable() >= 4;
178  }
179 
180  for (i=0; (unsigned int)i<m_outputChannelIds.size(); i++)
181  {
182  if (m_outputToInput[i] != size_t(m_threshold))
183  m_outputQueues[i].PutWord32(m_y[m_outputToInput[i]]);
184  else if (m_v[i].size() == size_t(m_threshold))
185  m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_v[i].begin(), m_threshold));
186  else
187  {
188  m_u.resize(m_threshold);
189  PrepareBulkPolynomialInterpolationAt(field, m_u.begin(), m_outputChannelIds[i], &(m_inputChannelIds[0]), m_w.begin(), m_threshold);
190  m_outputQueues[i].PutWord32(BulkPolynomialInterpolateAt(field, m_y.begin(), m_u.begin(), m_threshold));
191  }
192  }
193  }
194 
195  if (m_outputChannelIds.size() > 0 && m_outputQueues[0].AnyRetrievable())
196  FlushOutputQueues();
197 
198  if (finished)
199  {
200  OutputMessageEnds();
201 
202  m_channelsReady = 0;
203  m_channelsFinished = 0;
204  m_v.clear();
205 
206  std::vector<MessageQueue> inputQueues;
207  std::vector<word32> inputChannelIds;
208 
209  inputQueues.swap(m_inputQueues);
210  inputChannelIds.swap(m_inputChannelIds);
211  m_inputChannelMap.clear();
212  m_lastMapPosition = m_inputChannelMap.end();
213 
214  for (i=0; i<size_t(m_threshold); i++)
215  {
216  inputQueues[i].GetNextMessage();
217  inputQueues[i].TransferAllTo(*AttachedTransformation(), WordToString(inputChannelIds[i]));
218  }
219  }
220 }
221 
222 void RawIDA::FlushOutputQueues()
223 {
224  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
225  m_outputQueues[i].TransferAllTo(*AttachedTransformation(), m_outputChannelIdStrings[i]);
226 }
227 
228 void RawIDA::OutputMessageEnds()
229 {
230  if (GetAutoSignalPropagation() != 0)
231  {
232  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
233  AttachedTransformation()->ChannelMessageEnd(m_outputChannelIdStrings[i], GetAutoSignalPropagation()-1);
234  }
235 }
236 
237 // ****************************************************************
238 
240 {
241  m_pad = parameters.GetValueWithDefault("AddPadding", true);
242  m_ida.IsolatedInitialize(parameters);
243 }
244 
245 size_t SecretSharing::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
246 {
247  if (!blocking)
248  throw BlockingInputOnly("SecretSharing");
249 
250  SecByteBlock buf(UnsignedMin(256, length));
251  unsigned int threshold = m_ida.GetThreshold();
252  while (length > 0)
253  {
254  size_t len = STDMIN(length, buf.size());
255  m_ida.ChannelData(0xffffffff, begin, len, false);
256  for (unsigned int i=0; i<threshold-1; i++)
257  {
258  m_rng.GenerateBlock(buf, len);
259  m_ida.ChannelData(i, buf, len, false);
260  }
261  length -= len;
262  begin += len;
263  }
264 
265  if (messageEnd)
266  {
267  m_ida.SetAutoSignalPropagation(messageEnd-1);
268  if (m_pad)
269  {
271  while (m_ida.InputBuffered(0xffffffff) > 0)
273  }
274  m_ida.ChannelData(0xffffffff, NULL, 0, true);
275  for (unsigned int i=0; i<m_ida.GetThreshold()-1; i++)
276  m_ida.ChannelData(i, NULL, 0, true);
277  }
278 
279  return 0;
280 }
281 
283 {
284  m_pad = parameters.GetValueWithDefault("RemovePadding", true);
285  RawIDA::IsolatedInitialize(CombinedNameValuePairs(parameters, MakeParameters("OutputChannelID", (word32)0xffffffff)));
286 }
287 
288 void SecretRecovery::FlushOutputQueues()
289 {
290  if (m_pad)
291  m_outputQueues[0].TransferTo(*AttachedTransformation(), m_outputQueues[0].MaxRetrievable()-4);
292  else
293  m_outputQueues[0].TransferTo(*AttachedTransformation());
294 }
295 
296 void SecretRecovery::OutputMessageEnds()
297 {
298  if (m_pad)
299  {
300  PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
301  m_outputQueues[0].TransferAllTo(paddingRemover);
302  }
303 
304  if (GetAutoSignalPropagation() != 0)
305  AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
306 }
307 
308 // ****************************************************************
309 
311 {
312  m_nextChannel = 0;
313  m_pad = parameters.GetValueWithDefault("AddPadding", true);
314  m_ida.IsolatedInitialize(parameters);
315 }
316 
317 size_t InformationDispersal::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
318 {
319  if (!blocking)
320  throw BlockingInputOnly("InformationDispersal");
321 
322  while (length--)
323  {
324  m_ida.ChannelData(m_nextChannel, begin, 1, false);
325  begin++;
326  m_nextChannel++;
327  if (m_nextChannel == m_ida.GetThreshold())
328  m_nextChannel = 0;
329  }
330 
331  if (messageEnd)
332  {
333  m_ida.SetAutoSignalPropagation(messageEnd-1);
334  if (m_pad)
336  for (word32 i=0; i<m_ida.GetThreshold(); i++)
337  m_ida.ChannelData(i, NULL, 0, true);
338  }
339 
340  return 0;
341 }
342 
344 {
345  m_pad = parameters.GetValueWithDefault("RemovePadding", true);
346  RawIDA::IsolatedInitialize(parameters);
347 }
348 
349 void InformationRecovery::FlushOutputQueues()
350 {
351  while (m_outputQueues[0].AnyRetrievable())
352  {
353  for (unsigned int i=0; i<m_outputChannelIds.size(); i++)
354  m_outputQueues[i].TransferTo(m_queue, 1);
355  }
356 
357  if (m_pad)
358  m_queue.TransferTo(*AttachedTransformation(), m_queue.MaxRetrievable()-4*m_threshold);
359  else
361 }
362 
363 void InformationRecovery::OutputMessageEnds()
364 {
365  if (m_pad)
366  {
367  PaddingRemover paddingRemover(new Redirector(*AttachedTransformation()));
368  m_queue.TransferAllTo(paddingRemover);
369  }
370 
371  if (GetAutoSignalPropagation() != 0)
372  AttachedTransformation()->MessageEnd(GetAutoSignalPropagation()-1);
373 }
374 
375 size_t PaddingRemover::Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
376 {
377  if (!blocking)
378  throw BlockingInputOnly("PaddingRemover");
379 
380  const byte *const end = begin + length;
381 
382  if (m_possiblePadding)
383  {
384  size_t len = std::find_if(begin, end, std::bind2nd(std::not_equal_to<byte>(), byte(0))) - begin;
385  m_zeroCount += len;
386  begin += len;
387  if (begin == end)
388  return 0;
389 
391  while (m_zeroCount--)
393  AttachedTransformation()->Put(*begin++);
394  m_possiblePadding = false;
395  }
396 
397 #if defined(_MSC_VER) && (_MSC_VER <= 1300) && !defined(__MWERKS__)
398  // VC60 and VC7 workaround: built-in reverse_iterator has two template parameters, Dinkumware only has one
399  typedef std::reverse_bidirectional_iterator<const byte *, const byte> RevIt;
400 #elif defined(_RWSTD_NO_CLASS_PARTIAL_SPEC)
401  typedef std::reverse_iterator<const byte *, std::random_access_iterator_tag, const byte> RevIt;
402 #else
403  typedef std::reverse_iterator<const byte *> RevIt;
404 #endif
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:182
virtual bool AnyRetrievable() const
Determines whether bytes are ready for retrieval.
Definition: cryptlib.cpp:507
T GetValueWithDefault(const char *name, T defaultValue) const
Get a named value.
Definition: cryptlib.h:348
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
Definition: cryptlib.cpp:329
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:702
base class for secret sharing and information dispersal
Definition: ida.h:20
Library configuration file.
Combines two sets of NameValuePairs.
Definition: algparam.h:135
SecBlock typedef.
Definition: secblock.h:728
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 MessageEnd(int propagation=-1, bool blocking=true)
Signals the end of messages to the object.
Definition: cryptlib.h:1436
bool AnyRetrievable() const
Determines whether bytes are ready for retrieval.
Definition: mqueue.h:40
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:1656
size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking)
Input multiple bytes for processing.
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition: cryptlib.h:1378
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Definition: algparam.h:554
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:486
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:450
Classes for polynomial basis and operations.
Redirect input to another BufferedTransformation without owning it.
Definition: filters.h:755
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:496
size_t PutWord32(word32 value, ByteOrder order=BIG_ENDIAN_ORDER, bool blocking=true)
Input a 32-bit word for processing.
Definition: cryptlib.cpp:722
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:758
void TransferAllTo(BufferedTransformation &target, const std::string &channel=DEFAULT_CHANNEL)
Transfer all bytes from this object to another BufferedTransformation.
Definition: cryptlib.h:1757
virtual unsigned int NumberOfMessages() const
Provides the number of meesages processed by this object.
Definition: cryptlib.cpp:572
virtual lword MaxRetrievable() const
Provides the number of bytes ready for retrieval.
Definition: cryptlib.cpp:499
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 Information Dispersal Algorithm (IDA)
bool ChannelMessageEnd(const std::string &channel, int propagation=-1, bool blocking=true)
Signal the end of a message.
Definition: cryptlib.h:1907
Interface for retrieving values given their names.
Definition: cryptlib.h:277