00001
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 ¶meters)
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 ¶meters)
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 ¶meters)
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 ¶meters)
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 ¶meters)
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
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