include/cryptopp/ida.h

0001 // ida.h - originally written and placed in the public domain by Wei Dai

0002
0003 /// \file ida.h

0004 /// \brief Classes for Rabin's Information Dispersal and Shamir's Secret Sharing algorithms

0005
0006 #ifndef CRYPTOPP_IDA_H
0007 #define CRYPTOPP_IDA_H
0008
0009 #include "cryptlib.h"
0010 #include "mqueue.h"
0011 #include "filters.h"
0012 #include "channels.h"
0013 #include "secblock.h"
0014 #include "gf2_32.h"
0015 #include "stdcpp.h"
0016 #include "misc.h"
0017
0018 NAMESPACE_BEGIN(CryptoPP)
0019
0020 /// \brief Secret sharing and information dispersal base class

0021 /// \since Crypto++ 1.0

0022 class RawIDA : public AutoSignaling<Unflushable<Multichannel<Filter> > >
0023 {
0024 public:
0025     RawIDA(BufferedTransformation *attachment=NULLPTR)
0026         : m_channelsReady(0), m_channelsFinished(0), m_threshold (0)
0027             {Detach(attachment);}
0028
0029     unsigned int GetThreshold() const {return m_threshold;}
0030     void AddOutputChannel(word32 channelId);
0031     void ChannelData(word32 channelId, const byte *inString, size_t length, bool messageEnd);
0032     lword InputBuffered(word32 channelId) const;
0033
0034     void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs);
0035     size_t ChannelPut2(const std::string &channel, const byte *begin, size_t length, int messageEnd, bool blocking)
0036     {
0037         if (!blocking)
0038             throw BlockingInputOnly("RawIDA");
0039         ChannelData(StringToWord<word32>(channel), begin, length, messageEnd != 0);
0040         return 0;
0041     }
0042
0043 protected:
0044     virtual void FlushOutputQueues();
0045     virtual void OutputMessageEnds();
0046
0047     unsigned int InsertInputChannel(word32 channelId);
0048     unsigned int LookupInputChannel(word32 channelId) const;
0049     void ComputeV(unsigned int);
0050     void PrepareInterpolation();
0051     void ProcessInputQueues();
0052
0053     typedef std::map<word32, unsigned int> InputChannelMap;
0054     InputChannelMap m_inputChannelMap;
0055     InputChannelMap::iterator m_lastMapPosition;
0056     std::vector<MessageQueue> m_inputQueues;
0057     std::vector<word32> m_inputChannelIds, m_outputChannelIds, m_outputToInput;
0058     std::vector<std::string> m_outputChannelIdStrings;
0059     std::vector<ByteQueue> m_outputQueues;
0060     std::vector<SecBlock<word32> > m_v;
0061     SecBlock<word32> m_u, m_w, m_y;
0062     const GF2_32 m_gf32;
0063     unsigned int m_channelsReady, m_channelsFinished;
0064     int m_threshold;
0065 };
0066
0067 /// \brief Shamir's Secret Sharing Algorithm

0068 /// \details SecretSharing is a variant of Shamir's secret sharing algorithm

0069 /// \sa SecretRecovery, SecretRecovery, InformationDispersal, InformationRecovery

0070 /// \since Crypto++ 1.0

0071 class SecretSharing : public CustomFlushPropagation<Filter>
0072 {
0073 public:
0074     /// \brief Construct a SecretSharing

0075     SecretSharing(RandomNumberGenerator &rng, int threshold, int nShares, BufferedTransformation *attachment=NULLPTR, bool addPadding=true)
0076         : m_rng(rng), m_ida(new OutputProxy(*this, true))
0077     {
0078         Detach(attachment);
0079         IsolatedInitialize(MakeParameters("RecoveryThreshold", threshold)("NumberOfShares", nShares)("AddPadding", addPadding));
0080     }
0081
0082     void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs);
0083     size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking);
0084     bool Flush(bool hardFlush, int propagation=-1, bool blocking=true) {return m_ida.Flush(hardFlush, propagation, blocking);}
0085
0086 protected:
0087     RandomNumberGenerator &m_rng;
0088     RawIDA m_ida;
0089     bool m_pad;
0090 };
0091
0092 /// \brief Shamir's Secret Sharing Algorithm

0093 /// \details SecretSharing is a variant of Shamir's secret sharing algorithm

0094 /// \sa SecretRecovery, SecretRecovery, InformationDispersal, InformationRecovery

0095 /// \since Crypto++ 1.0

0096 class SecretRecovery : public RawIDA
0097 {
0098 public:
0099     /// \brief Construct a SecretRecovery

0100     SecretRecovery(int threshold, BufferedTransformation *attachment=NULLPTR, bool removePadding=true)
0101         : RawIDA(attachment)
0102         {IsolatedInitialize(MakeParameters("RecoveryThreshold", threshold)("RemovePadding", removePadding));}
0103
0104     void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs);
0105
0106 protected:
0107     void FlushOutputQueues();
0108     void OutputMessageEnds();
0109
0110     bool m_pad;
0111 };
0112
0113 /// a variant of Rabin's Information Dispersal Algorithm

0114
0115 /// \brief Rabin's Information Dispersal Algorithm

0116 /// \details InformationDispersal is a variant of Rabin's information dispersal algorithm

0117 /// \sa SecretRecovery, SecretRecovery, InformationDispersal, InformationRecovery

0118 /// \since Crypto++ 1.0

0119 class InformationDispersal : public CustomFlushPropagation<Filter>
0120 {
0121 public:
0122     /// \brief Construct a InformationDispersal

0123     InformationDispersal(int threshold, int nShares, BufferedTransformation *attachment=NULLPTR, bool addPadding=true)
0124         : m_ida(new OutputProxy(*this, true)), m_pad(false), m_nextChannel(0)
0125     {
0126         Detach(attachment);
0127         IsolatedInitialize(MakeParameters("RecoveryThreshold", threshold)("NumberOfShares", nShares)("AddPadding", addPadding));
0128     }
0129
0130     void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs);
0131     size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking);
0132     bool Flush(bool hardFlush, int propagation=-1, bool blocking=true) {return m_ida.Flush(hardFlush, propagation, blocking);}
0133
0134 protected:
0135     RawIDA m_ida;
0136     bool m_pad;
0137     unsigned int m_nextChannel;
0138 };
0139
0140 /// \brief Rabin's Information Dispersal Algorithm

0141 /// \details InformationDispersal is a variant of Rabin's information dispersal algorithm

0142 /// \sa SecretRecovery, SecretRecovery, InformationDispersal, InformationRecovery

0143 /// \since Crypto++ 1.0

0144 class InformationRecovery : public RawIDA
0145 {
0146 public:
0147     /// \brief Construct a InformationRecovery

0148     InformationRecovery(int threshold, BufferedTransformation *attachment=NULLPTR, bool removePadding=true)
0149         : RawIDA(attachment), m_pad(false)
0150         {IsolatedInitialize(MakeParameters("RecoveryThreshold", threshold)("RemovePadding", removePadding));}
0151
0152     void IsolatedInitialize(const NameValuePairs &parameters=g_nullNameValuePairs);
0153
0154 protected:
0155     void FlushOutputQueues();
0156     void OutputMessageEnds();
0157
0158     bool m_pad;
0159     ByteQueue m_queue;
0160 };
0161
0162 class PaddingRemover : public Unflushable<Filter>
0163 {
0164 public:
0165     PaddingRemover(BufferedTransformation *attachment=NULLPTR)
0166         : m_possiblePadding(false), m_zeroCount(0) {Detach(attachment);}
0167
0168     void IsolatedInitialize(const NameValuePairs &parameters)
0169         {CRYPTOPP_UNUSED(parameters); m_possiblePadding = false;}
0170     size_t Put2(const byte *begin, size_t length, int messageEnd, bool blocking);
0171
0172     // GetPossiblePadding() == false at the end of a message indicates incorrect padding

0173     bool GetPossiblePadding() const {return m_possiblePadding;}
0174
0175 private:
0176     bool m_possiblePadding;
0177     lword m_zeroCount;
0178 };
0179
0180 NAMESPACE_END
0181
0182 #endif