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::ChannelInitialize(const string &channel, const
NameValuePairs ¶meters,
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 ¶meters,
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 ¶meters,
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 ¶meters,
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 ¶meters,
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
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