1 ////////////////////////////////////////////////////////////////////////////////
3 // This file contains a subset of the Crypto++ library (version 5.2.1), with
4 // kind permission from Wei Dai. Please note that this file should not reflect
5 // on the real Crypto++ library in any way, as this file been greatly mangled to
6 // reduce the code-size, since this app only makes use of RSA classes (for Secure
7 // Identification) and the MD4 hashing class (for FileIDs).
9 // For the full Crypto++ library, please refer to the official Crypto++ website,
10 // which can be found at, http://www.cryptopp.com
12 ////////////////////////////////////////////////////////////////////////////////
14 // Compilation Copyright (c) 1995-2004 by Wei Dai. All rights reserved.
15 // This copyright applies only to this software distribution package
16 // as a compilation, and does not imply a copyright on any particular
17 // file in the package.
19 // The following files are copyrighted by their respective original authors,
20 // and their use is subject to additional licenses included in these files.
22 // mars.cpp - Copyright 1998 Brian Gladman.
24 // All other files in this compilation are placed in the public domain by
25 // Wei Dai and other contributors.
27 // I would like to thank the following authors for placing their works into
30 // Joan Daemen - 3way.cpp
31 // Leonard Janke - cast.cpp, seal.cpp
32 // Steve Reid - cast.cpp
33 // Phil Karn - des.cpp
34 // Michael Paul Johnson - diamond.cpp
35 // Andrew M. Kuchling - md2.cpp, md4.cpp
36 // Colin Plumb - md5.cpp, md5mac.cpp
37 // Seal Woods - rc6.cpp
38 // Chris Morgan - rijndael.cpp
39 // Paulo Baretto - rijndael.cpp, skipjack.cpp, square.cpp
40 // Richard De Moliner - safer.cpp
41 // Matthew Skala - twofish.cpp
42 // Kevin Springle - camellia.cpp, shacal2.cpp, ttmac.cpp, whrlpool.cpp, ripemd.cpp
44 // Permission to use, copy, modify, and distribute this compilation for
45 // any purpose, including commercial applications, is hereby granted
46 // without fee, subject to the following restrictions:
48 // 1. Any copy or modification of this compilation in any form, except
49 // in object code form as part of an application software, must include
50 // the above copyright notice and this license.
52 // 2. Users of this software agree that any modification or extension
53 // they provide to Wei Dai will be considered public domain and not
54 // copyrighted unless it includes an explicit copyright notice.
56 // 3. Wei Dai makes no warranty or representation that the operation of the
57 // software in this compilation will be error-free, and Wei Dai is under no
58 // obligation to provide any services, by way of maintenance, update, or
59 // otherwise. THE SOFTWARE AND ANY DOCUMENTATION ARE PROVIDED "AS IS"
60 // WITHOUT EXPRESS OR IMPLIED WARRANTY INCLUDING, BUT NOT LIMITED TO,
61 // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
62 // PURPOSE. IN NO EVENT WILL WEI DAI OR ANY OTHER CONTRIBUTOR BE LIABLE FOR
63 // DIRECT, INCIDENTAL OR CONSEQUENTIAL DAMAGES, EVEN IF
64 // ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
66 // 4. Users will not use Wei Dai or any other contributor's name in any
67 // publicity or advertising, without prior written consent in each case.
69 // 5. Export of this software from the United States may require a
70 // specific license from the United States Government. It is the
71 // responsibility of any person or organization contemplating export
72 // to obtain such a license before exporting.
74 // 6. Certain parts of this software may be protected by patents. It
75 // is the users' responsibility to obtain the appropriate
76 // licenses before using those parts.
78 // If this compilation is used in object code form in an application
79 // software, acknowledgement of the author is not required but would be
80 // appreciated. The contribution of any useful modifications or extensions
81 // to Wei Dai is not required but would also be appreciated.
83 ////////////////////////////////////////////////////////////////////////////////
87 ////////////////////////////////////////////////////////////////////////////////
88 #ifndef CRYPTOPP_FLTRIMPL_H
89 #define CRYPTOPP_FLTRIMPL_H
91 #define FILTER_BEGIN \
92 switch (m_continueAt) \
97 #define FILTER_END_NO_MESSAGE_END_NO_RETURN \
103 #define FILTER_END_NO_MESSAGE_END \
104 FILTER_END_NO_MESSAGE_END_NO_RETURN \
110 if (messageEnd && Output(-1, NULL, 0, messageEnd, blocking)) \
112 FILTER_END_NO_MESSAGE_END
115 #define FILTER_OUTPUT2(site, statement, output, length, messageEnd) \
119 if (Output(site, output, length, messageEnd, blocking)) \
120 return STDMAX(1U, (unsigned int)length-m_inputPosition);\
123 #define FILTER_OUTPUT(site, output, length, messageEnd) \
126 if (Output(site, output, length, messageEnd, blocking)) \
127 return STDMAX(1U, (unsigned int)length-m_inputPosition);\
131 ////////////////////////////////////////////////////////////////////////////////
135 ////////////////////////////////////////////////////////////////////////////////
136 // cryptlib.cpp - written and placed in the public domain by Wei Dai
140 #ifndef CRYPTOPP_IMPORTS
142 //- #include "cryptlib.h"
143 //- #include "misc.h"
144 //- #include "filters.h"
145 //- #include "algparam.h"
146 //- #include "fips140.h"
147 //- #include "argnames.h"
148 //- #include "fltrimpl.h"
152 NAMESPACE_BEGIN(CryptoPP
)
154 CRYPTOPP_COMPILE_ASSERT_GLOBAL(sizeof(byte
) == 1);
155 CRYPTOPP_COMPILE_ASSERT_GLOBAL(sizeof(word16
) == 2);
156 CRYPTOPP_COMPILE_ASSERT_GLOBAL(sizeof(word32
) == 4);
157 #ifdef WORD64_AVAILABLE
158 CRYPTOPP_COMPILE_ASSERT_GLOBAL(sizeof(word64
) == 8);
160 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
161 CRYPTOPP_COMPILE_ASSERT_GLOBAL(sizeof(dword
) == 2*sizeof(word
));
164 const std::string
BufferedTransformation::NULL_CHANNEL
;
165 const NullNameValuePairs g_nullNameValuePairs
;
167 BufferedTransformation
& TheBitBucket()
169 static BitBucket bitBucket
;
173 Algorithm::Algorithm(bool /* checkSelfTestStatus */)
177 void SimpleKeyingInterface::SetKeyWithRounds(const byte
*key
, unsigned int length
, int rounds
)
179 SetKey(key
, length
, MakeParameters(Name::Rounds(), rounds
));
182 void SimpleKeyingInterface::SetKeyWithIV(const byte
*key
, unsigned int length
, const byte
*iv
)
184 SetKey(key
, length
, MakeParameters(Name::IV(), iv
));
187 void SimpleKeyingInterface::ThrowIfInvalidKeyLength(const Algorithm
&algorithm
, unsigned int length
)
189 if (!IsValidKeyLength(length
))
190 throw InvalidKeyLength(algorithm
.AlgorithmName(), length
);
193 void SimpleKeyingInterface::ThrowIfResynchronizable()
195 if (IsResynchronizable())
196 throw InvalidArgument("SimpleKeyingInterface: this object requires an IV");
199 void SimpleKeyingInterface::ThrowIfInvalidIV(const byte
*iv
)
201 if (!iv
&& !(IVRequirement() == INTERNALLY_GENERATED_IV
|| IVRequirement() == STRUCTURED_IV
|| !IsResynchronizable()))
202 throw InvalidArgument("SimpleKeyingInterface: this object cannot use a null IV");
205 const byte
* SimpleKeyingInterface::GetIVAndThrowIfInvalid(const NameValuePairs
¶ms
)
208 if (params
.GetValue(Name::IV(), iv
))
209 ThrowIfInvalidIV(iv
);
211 ThrowIfResynchronizable();
215 void BlockTransformation::ProcessAndXorMultipleBlocks(const byte
*inBlocks
, const byte
*xorBlocks
, byte
*outBlocks
, unsigned int numberOfBlocks
) const
217 unsigned int blockSize
= BlockSize();
218 while (numberOfBlocks
--)
220 ProcessAndXorBlock(inBlocks
, xorBlocks
, outBlocks
);
221 inBlocks
+= blockSize
;
222 outBlocks
+= blockSize
;
224 xorBlocks
+= blockSize
;
228 void StreamTransformation::ProcessLastBlock(byte
*outString
, const byte
*inString
, unsigned int length
)
230 assert(MinLastBlockSize() == 0); // this function should be overriden otherwise
232 if (length
== MandatoryBlockSize())
233 ProcessData(outString
, inString
, length
);
234 else if (length
!= 0)
235 throw NotImplemented("StreamTransformation: this object does't support a special last block");
238 unsigned int RandomNumberGenerator::GenerateBit()
240 return Parity(GenerateByte());
243 void RandomNumberGenerator::GenerateBlock(byte
*output
, unsigned int size
)
246 *output
++ = GenerateByte();
249 word32
RandomNumberGenerator::GenerateWord32(word32 min
, word32 max
)
251 word32 range
= max
-min
;
252 const int maxBytes
= BytePrecision(range
);
253 const int maxBits
= BitPrecision(range
);
260 for (int i
=0; i
<maxBytes
; i
++)
261 value
= (value
<< 8) | GenerateByte();
263 value
= Crop(value
, maxBits
);
264 } while (value
> range
);
269 void RandomNumberGenerator::DiscardBytes(unsigned int n
)
276 class ClassNullRNG
: public RandomNumberGenerator
279 std::string
AlgorithmName() const {return "NullRNG";}
280 byte
GenerateByte() {throw NotImplemented("NullRNG: NullRNG should only be passed to functions that don't need to generate random bytes");}
283 RandomNumberGenerator
& NullRNG()
285 static ClassNullRNG s_nullRNG
;
289 bool HashTransformation::TruncatedVerify(const byte
*digestIn
, unsigned int digestLength
)
291 ThrowIfInvalidTruncatedSize(digestLength
);
292 SecByteBlock
digest(digestLength
);
293 TruncatedFinal(digest
, digestLength
);
294 return memcmp(digest
, digestIn
, digestLength
) == 0;
297 void HashTransformation::ThrowIfInvalidTruncatedSize(unsigned int size
) const
299 if (size
> DigestSize())
300 throw InvalidArgument("HashTransformation: can't truncate a " + IntToString(DigestSize(), 10) + " byte digest to " + IntToString(size
, 10) + " bytes");
303 unsigned int BufferedTransformation::GetMaxWaitObjectCount() const
305 const BufferedTransformation
*t
= AttachedTransformation();
306 return t
? t
->GetMaxWaitObjectCount() : 0;
309 void BufferedTransformation::GetWaitObjects(WaitObjectContainer
&container
)
311 BufferedTransformation
*t
= AttachedTransformation();
313 t
->GetWaitObjects(container
);
316 void BufferedTransformation::Initialize(const NameValuePairs
¶meters
, int /* propagation */)
318 assert(!AttachedTransformation());
319 IsolatedInitialize(parameters
);
322 bool BufferedTransformation::Flush(bool hardFlush
, int /* propagation */, bool blocking
)
324 assert(!AttachedTransformation());
325 return IsolatedFlush(hardFlush
, blocking
);
328 bool BufferedTransformation::MessageSeriesEnd(int /* propagation */, bool blocking
)
330 assert(!AttachedTransformation());
331 return IsolatedMessageSeriesEnd(blocking
);
334 byte
* BufferedTransformation::ChannelCreatePutSpace(const std::string
&channel
, unsigned int &size
)
337 return CreatePutSpace(size
);
339 throw NoChannelSupport();
342 unsigned int BufferedTransformation::ChannelPut2(const std::string
&channel
, const byte
*begin
, unsigned int length
, int messageEnd
, bool blocking
)
345 return Put2(begin
, length
, messageEnd
, blocking
);
347 throw NoChannelSupport();
350 unsigned int BufferedTransformation::ChannelPutModifiable2(const std::string
&channel
, byte
*begin
, unsigned int length
, int messageEnd
, bool blocking
)
353 return PutModifiable2(begin
, length
, messageEnd
, blocking
);
355 return ChannelPut2(channel
, begin
, length
, messageEnd
, blocking
);
358 bool BufferedTransformation::ChannelFlush(const std::string
&channel
, bool completeFlush
, int propagation
, bool blocking
)
361 return Flush(completeFlush
, propagation
, blocking
);
363 throw NoChannelSupport();
366 bool BufferedTransformation::ChannelMessageSeriesEnd(const std::string
&channel
, int propagation
, bool blocking
)
369 return MessageSeriesEnd(propagation
, blocking
);
371 throw NoChannelSupport();
374 unsigned long BufferedTransformation::MaxRetrievable() const
376 if (AttachedTransformation())
377 return AttachedTransformation()->MaxRetrievable();
379 return CopyTo(TheBitBucket());
382 bool BufferedTransformation::AnyRetrievable() const
384 if (AttachedTransformation())
385 return AttachedTransformation()->AnyRetrievable();
393 unsigned int BufferedTransformation::Get(byte
&outByte
)
395 if (AttachedTransformation())
396 return AttachedTransformation()->Get(outByte
);
398 return Get(&outByte
, 1);
401 unsigned int BufferedTransformation::Get(byte
*outString
, unsigned int getMax
)
403 if (AttachedTransformation())
404 return AttachedTransformation()->Get(outString
, getMax
);
407 ArraySink
arraySink(outString
, getMax
);
408 return TransferTo(arraySink
, getMax
);
412 unsigned int BufferedTransformation::Peek(byte
&outByte
) const
414 if (AttachedTransformation())
415 return AttachedTransformation()->Peek(outByte
);
417 return Peek(&outByte
, 1);
420 unsigned int BufferedTransformation::Peek(byte
*outString
, unsigned int peekMax
) const
422 if (AttachedTransformation())
423 return AttachedTransformation()->Peek(outString
, peekMax
);
426 ArraySink
arraySink(outString
, peekMax
);
427 return CopyTo(arraySink
, peekMax
);
431 unsigned long BufferedTransformation::Skip(unsigned long skipMax
)
433 if (AttachedTransformation())
434 return AttachedTransformation()->Skip(skipMax
);
436 return TransferTo(TheBitBucket(), skipMax
);
439 unsigned long BufferedTransformation::TotalBytesRetrievable() const
441 if (AttachedTransformation())
442 return AttachedTransformation()->TotalBytesRetrievable();
444 return MaxRetrievable();
447 unsigned int BufferedTransformation::NumberOfMessages() const
449 if (AttachedTransformation())
450 return AttachedTransformation()->NumberOfMessages();
452 return CopyMessagesTo(TheBitBucket());
455 bool BufferedTransformation::AnyMessages() const
457 if (AttachedTransformation())
458 return AttachedTransformation()->AnyMessages();
460 return NumberOfMessages() != 0;
463 bool BufferedTransformation::GetNextMessage()
465 if (AttachedTransformation())
466 return AttachedTransformation()->GetNextMessage();
469 assert(!AnyMessages());
474 unsigned int BufferedTransformation::SkipMessages(unsigned int count
)
476 if (AttachedTransformation())
477 return AttachedTransformation()->SkipMessages(count
);
479 return TransferMessagesTo(TheBitBucket(), count
);
482 unsigned int BufferedTransformation::TransferMessagesTo2(BufferedTransformation
&target
, unsigned int &messageCount
, const std::string
&channel
, bool blocking
)
484 if (AttachedTransformation())
485 return AttachedTransformation()->TransferMessagesTo2(target
, messageCount
, channel
, blocking
);
488 unsigned int maxMessages
= messageCount
;
489 for (messageCount
=0; messageCount
< maxMessages
&& AnyMessages(); messageCount
++)
491 unsigned int blockedBytes
;
492 unsigned long transferredBytes
;
494 while (AnyRetrievable())
496 transferredBytes
= ULONG_MAX
;
497 blockedBytes
= TransferTo2(target
, transferredBytes
, channel
, blocking
);
498 if (blockedBytes
> 0)
502 if (target
.ChannelMessageEnd(channel
, GetAutoSignalPropagation(), blocking
))
505 bool result
= GetNextMessage();
512 unsigned int BufferedTransformation::CopyMessagesTo(BufferedTransformation
&target
, unsigned int count
, const std::string
&channel
) const
514 if (AttachedTransformation())
515 return AttachedTransformation()->CopyMessagesTo(target
, count
, channel
);
520 void BufferedTransformation::SkipAll()
522 if (AttachedTransformation())
523 AttachedTransformation()->SkipAll();
526 while (SkipMessages()) {}
531 unsigned int BufferedTransformation::TransferAllTo2(BufferedTransformation
&target
, const std::string
&channel
, bool blocking
)
533 if (AttachedTransformation())
534 return AttachedTransformation()->TransferAllTo2(target
, channel
, blocking
);
537 assert(!NumberOfMessageSeries());
539 unsigned int messageCount
;
542 messageCount
= UINT_MAX
;
543 unsigned int blockedBytes
= TransferMessagesTo2(target
, messageCount
, channel
, blocking
);
547 while (messageCount
!= 0);
549 unsigned long byteCount
;
552 byteCount
= ULONG_MAX
;
553 unsigned int blockedBytes
= TransferTo2(target
, byteCount
, channel
, blocking
);
557 while (byteCount
!= 0);
563 void BufferedTransformation::CopyAllTo(BufferedTransformation
&target
, const std::string
&channel
) const
565 if (AttachedTransformation())
566 AttachedTransformation()->CopyAllTo(target
, channel
);
569 assert(!NumberOfMessageSeries());
570 while (CopyMessagesTo(target
, UINT_MAX
, channel
)) {}
574 void BufferedTransformation::SetRetrievalChannel(const std::string
&channel
)
576 if (AttachedTransformation())
577 AttachedTransformation()->SetRetrievalChannel(channel
);
580 unsigned int BufferedTransformation::ChannelPutWord16(const std::string
&channel
, word16 value
, ByteOrder order
, bool blocking
)
582 FixedSizeSecBlock
<byte
, 2> buf
;
583 PutWord(false, order
, buf
, value
);
584 return ChannelPut(channel
, buf
, 2, blocking
);
587 unsigned int BufferedTransformation::ChannelPutWord32(const std::string
&channel
, word32 value
, ByteOrder order
, bool blocking
)
589 FixedSizeSecBlock
<byte
, 4> buf
;
590 PutWord(false, order
, buf
, value
);
591 return ChannelPut(channel
, buf
, 4, blocking
);
594 unsigned int BufferedTransformation::PutWord16(word16 value
, ByteOrder order
, bool blocking
)
596 return ChannelPutWord16(NULL_CHANNEL
, value
, order
, blocking
);
599 unsigned int BufferedTransformation::PutWord32(word32 value
, ByteOrder order
, bool blocking
)
601 return ChannelPutWord32(NULL_CHANNEL
, value
, order
, blocking
);
604 unsigned int BufferedTransformation::PeekWord16(word16
&value
, ByteOrder order
)
606 byte buf
[2] = {0, 0};
607 unsigned int len
= Peek(buf
, 2);
610 value
= (buf
[0] << 8) | buf
[1];
612 value
= (buf
[1] << 8) | buf
[0];
617 unsigned int BufferedTransformation::PeekWord32(word32
&value
, ByteOrder order
)
619 byte buf
[4] = {0, 0, 0, 0};
620 unsigned int len
= Peek(buf
, 4);
623 value
= (buf
[0] << 24) | (buf
[1] << 16) | (buf
[2] << 8) | buf
[3];
625 value
= (buf
[3] << 24) | (buf
[2] << 16) | (buf
[1] << 8) | buf
[0];
630 unsigned int BufferedTransformation::GetWord16(word16
&value
, ByteOrder order
)
632 return Skip(PeekWord16(value
, order
));
635 unsigned int BufferedTransformation::GetWord32(word32
&value
, ByteOrder order
)
637 return Skip(PeekWord32(value
, order
));
640 void BufferedTransformation::Attach(BufferedTransformation
*newOut
)
642 if (AttachedTransformation() && AttachedTransformation()->Attachable())
643 AttachedTransformation()->Attach(newOut
);
648 void GeneratableCryptoMaterial::GenerateRandomWithKeySize(RandomNumberGenerator
&rng
, unsigned int keySize
)
650 GenerateRandom(rng
, MakeParameters("KeySize", (int)keySize
));
653 class PK_DefaultEncryptionFilter
: public Unflushable
<Filter
>
656 PK_DefaultEncryptionFilter(RandomNumberGenerator
&rng
, const PK_Encryptor
&encryptor
, BufferedTransformation
*attachment
, const NameValuePairs
¶meters
)
657 : m_rng(rng
), m_encryptor(encryptor
), m_parameters(parameters
)
662 unsigned int Put2(const byte
*inString
, unsigned int length
, int messageEnd
, bool blocking
)
665 m_plaintextQueue
.Put(inString
, length
);
670 unsigned int plaintextLength
= m_plaintextQueue
.CurrentSize();
671 unsigned int ciphertextLength
= m_encryptor
.CiphertextLength(plaintextLength
);
673 SecByteBlock
plaintext(plaintextLength
);
674 m_plaintextQueue
.Get(plaintext
, plaintextLength
);
675 m_ciphertext
.resize(ciphertextLength
);
676 m_encryptor
.Encrypt(m_rng
, plaintext
, plaintextLength
, m_ciphertext
, m_parameters
);
679 FILTER_OUTPUT(1, m_ciphertext
, m_ciphertext
.size(), messageEnd
);
681 FILTER_END_NO_MESSAGE_END
;
684 RandomNumberGenerator
&m_rng
;
685 const PK_Encryptor
&m_encryptor
;
686 const NameValuePairs
&m_parameters
;
687 ByteQueue m_plaintextQueue
;
688 SecByteBlock m_ciphertext
;
691 BufferedTransformation
* PK_Encryptor::CreateEncryptionFilter(RandomNumberGenerator
&rng
, BufferedTransformation
*attachment
, const NameValuePairs
¶meters
) const
693 return new PK_DefaultEncryptionFilter(rng
, *this, attachment
, parameters
);
696 unsigned int PK_Signer::Sign(RandomNumberGenerator
&rng
, PK_MessageAccumulator
*messageAccumulator
, byte
*signature
) const
698 std::auto_ptr
<PK_MessageAccumulator
> m(messageAccumulator
);
699 return SignAndRestart(rng
, *m
, signature
, false);
702 unsigned int PK_Signer::SignMessage(RandomNumberGenerator
&rng
, const byte
*message
, unsigned int messageLen
, byte
*signature
) const
704 std::auto_ptr
<PK_MessageAccumulator
> m(NewSignatureAccumulator(rng
));
705 m
->Update(message
, messageLen
);
706 return SignAndRestart(rng
, *m
, signature
, false);
709 unsigned int PK_Signer::SignMessageWithRecovery(RandomNumberGenerator
&rng
, const byte
*recoverableMessage
, unsigned int recoverableMessageLength
,
710 const byte
*nonrecoverableMessage
, unsigned int nonrecoverableMessageLength
, byte
*signature
) const
712 std::auto_ptr
<PK_MessageAccumulator
> m(NewSignatureAccumulator(rng
));
713 InputRecoverableMessage(*m
, recoverableMessage
, recoverableMessageLength
);
714 m
->Update(nonrecoverableMessage
, nonrecoverableMessageLength
);
715 return SignAndRestart(rng
, *m
, signature
, false);
718 bool PK_Verifier::Verify(PK_MessageAccumulator
*messageAccumulator
) const
720 std::auto_ptr
<PK_MessageAccumulator
> m(messageAccumulator
);
721 return VerifyAndRestart(*m
);
724 bool PK_Verifier::VerifyMessage(const byte
*message
, unsigned int messageLen
, const byte
*signature
, unsigned int signatureLength
) const
726 std::auto_ptr
<PK_MessageAccumulator
> m(NewVerificationAccumulator());
727 InputSignature(*m
, signature
, signatureLength
);
728 m
->Update(message
, messageLen
);
729 return VerifyAndRestart(*m
);
732 DecodingResult
PK_Verifier::Recover(byte
*recoveredMessage
, PK_MessageAccumulator
*messageAccumulator
) const
734 std::auto_ptr
<PK_MessageAccumulator
> m(messageAccumulator
);
735 return RecoverAndRestart(recoveredMessage
, *m
);
738 DecodingResult
PK_Verifier::RecoverMessage(byte
*recoveredMessage
,
739 const byte
*nonrecoverableMessage
, unsigned int nonrecoverableMessageLength
,
740 const byte
*signature
, unsigned int signatureLength
) const
742 std::auto_ptr
<PK_MessageAccumulator
> m(NewVerificationAccumulator());
743 InputSignature(*m
, signature
, signatureLength
);
744 m
->Update(nonrecoverableMessage
, nonrecoverableMessageLength
);
745 return RecoverAndRestart(recoveredMessage
, *m
);
751 ////////////////////////////////////////////////////////////////////////////////
755 ////////////////////////////////////////////////////////////////////////////////
756 #ifndef CRYPTOPP_WORDS_H
757 #define CRYPTOPP_WORDS_H
759 //- #include "misc.h"
761 NAMESPACE_BEGIN(CryptoPP
)
763 inline unsigned int CountWords(const word
*X
, unsigned int N
)
765 while (N
&& X
[N
-1]==0)
770 inline void SetWords(word
*r
, word a
, unsigned int n
)
772 for (unsigned int i
=0; i
<n
; i
++)
776 inline void CopyWords(word
*r
, const word
*a
, unsigned int n
)
778 for (unsigned int i
=0; i
<n
; i
++)
782 inline void XorWords(word
*r
, const word
*a
, const word
*b
, unsigned int n
)
784 for (unsigned int i
=0; i
<n
; i
++)
788 inline void XorWords(word
*r
, const word
*a
, unsigned int n
)
790 for (unsigned int i
=0; i
<n
; i
++)
794 inline word
ShiftWordsLeftByBits(word
*r
, unsigned int n
, unsigned int shiftBits
)
796 assert (shiftBits
<WORD_BITS
);
799 for (unsigned int i
=0; i
<n
; i
++)
802 r
[i
] = (u
<< shiftBits
) | carry
;
803 carry
= u
>> (WORD_BITS
-shiftBits
);
808 inline word
ShiftWordsRightByBits(word
*r
, unsigned int n
, unsigned int shiftBits
)
810 assert (shiftBits
<WORD_BITS
);
813 for (int i
=n
-1; i
>=0; i
--)
816 r
[i
] = (u
>> shiftBits
) | carry
;
817 carry
= u
<< (WORD_BITS
-shiftBits
);
822 inline void ShiftWordsLeftByWords(word
*r
, unsigned int n
, unsigned int shiftWords
)
824 shiftWords
= STDMIN(shiftWords
, n
);
827 for (unsigned int i
=n
-1; i
>=shiftWords
; i
--)
828 r
[i
] = r
[i
-shiftWords
];
829 SetWords(r
, 0, shiftWords
);
833 inline void ShiftWordsRightByWords(word
*r
, unsigned int n
, unsigned int shiftWords
)
835 shiftWords
= STDMIN(shiftWords
, n
);
838 for (unsigned int i
=0; i
+shiftWords
<n
; i
++)
839 r
[i
] = r
[i
+shiftWords
];
840 SetWords(r
+n
-shiftWords
, 0, shiftWords
);
847 ////////////////////////////////////////////////////////////////////////////////
851 ////////////////////////////////////////////////////////////////////////////////
852 // misc.cpp - written and placed in the public domain by Wei Dai
856 #ifndef CRYPTOPP_IMPORTS
858 //- #include "misc.h"
859 //- #include "words.h"
862 NAMESPACE_BEGIN(CryptoPP
)
864 void xorbuf(byte
*buf
, const byte
*mask
, unsigned int count
)
866 if (((size_t)buf
| (size_t)mask
| count
) % WORD_SIZE
== 0)
867 XorWords((word
*)buf
, (const word
*)mask
, count
/WORD_SIZE
);
870 for (unsigned int i
=0; i
<count
; i
++)
875 void xorbuf(byte
*output
, const byte
*input
, const byte
*mask
, unsigned int count
)
877 if (((size_t)output
| (size_t)input
| (size_t)mask
| count
) % WORD_SIZE
== 0)
878 XorWords((word
*)output
, (const word
*)input
, (const word
*)mask
, count
/WORD_SIZE
);
881 for (unsigned int i
=0; i
<count
; i
++)
882 output
[i
] = input
[i
] ^ mask
[i
];
886 unsigned int Parity(unsigned long value
)
888 for (unsigned int i
=8*sizeof(value
)/2; i
>0; i
/=2)
890 return (unsigned int)value
&1;
893 unsigned long Crop(unsigned long value
, unsigned int size
)
895 if (size
< 8*sizeof(value
))
896 return (value
& ((1L << size
) - 1));
901 #if !(defined(_MSC_VER) && (_MSC_VER < 1300))
902 using std::new_handler
;
903 using std::set_new_handler
;
906 void CallNewHandler()
908 new_handler newHandler
= set_new_handler(NULL
);
910 set_new_handler(newHandler
);
915 throw std::bad_alloc();
921 ////////////////////////////////////////////////////////////////////////////////
925 ////////////////////////////////////////////////////////////////////////////////
926 // nbtheory.h - written and placed in the public domain by Wei Dai
928 #ifndef CRYPTOPP_NBTHEORY_H
929 #define CRYPTOPP_NBTHEORY_H
931 //- #include "integer.h"
932 //- #include "algparam.h"
934 NAMESPACE_BEGIN(CryptoPP
)
936 // obtain pointer to small prime table and get its size
937 CRYPTOPP_DLL
const word16
* GetPrimeTable(unsigned int &size
);
939 // ************ primality testing ****************
941 CRYPTOPP_DLL
bool IsSmallPrime(const Integer
&p
);
943 // returns true if p is divisible by some prime less than bound
944 // bound not be greater than the largest entry in the prime table
945 CRYPTOPP_DLL
bool TrialDivision(const Integer
&p
, unsigned bound
);
947 // returns true if p is NOT divisible by small primes
948 CRYPTOPP_DLL
bool SmallDivisorsTest(const Integer
&p
);
950 CRYPTOPP_DLL
bool IsStrongProbablePrime(const Integer
&n
, const Integer
&b
);
951 CRYPTOPP_DLL
bool IsStrongLucasProbablePrime(const Integer
&n
);
953 // Rabin-Miller primality test, i.e. repeating the strong probable prime test
954 // for several rounds with random bases
955 CRYPTOPP_DLL
bool RabinMillerTest(RandomNumberGenerator
&rng
, const Integer
&w
, unsigned int rounds
);
957 // primality test, used to generate primes
958 CRYPTOPP_DLL
bool IsPrime(const Integer
&p
);
960 // more reliable than IsPrime(), used to verify primes generated by others
961 CRYPTOPP_DLL
bool VerifyPrime(RandomNumberGenerator
&rng
, const Integer
&p
, unsigned int level
= 1);
966 virtual ~PrimeSelector() {};
967 const PrimeSelector
*GetSelectorPointer() const {return this;}
968 virtual bool IsAcceptable(const Integer
&candidate
) const =0;
971 // use a fast sieve to find the first probable prime in {x | p<=x<=max and x%mod==equiv}
972 // returns true iff successful, value of p is undefined if no such prime exists
973 CRYPTOPP_DLL
bool FirstPrime(Integer
&p
, const Integer
&max
, const Integer
&equiv
, const Integer
&mod
, const PrimeSelector
*pSelector
);
975 CRYPTOPP_DLL
unsigned int PrimeSearchInterval(const Integer
&max
);
977 CRYPTOPP_DLL AlgorithmParameters
<AlgorithmParameters
<AlgorithmParameters
<NullNameValuePairs
, Integer::RandomNumberType
>, Integer
>, Integer
>
978 MakeParametersForTwoPrimesOfEqualSize(unsigned int productBitLength
);
980 // ********** other number theoretic functions ************
982 inline Integer
GCD(const Integer
&a
, const Integer
&b
)
983 {return Integer::Gcd(a
,b
);}
984 inline bool RelativelyPrime(const Integer
&a
, const Integer
&b
)
985 {return Integer::Gcd(a
,b
) == Integer::One();}
986 inline Integer
LCM(const Integer
&a
, const Integer
&b
)
987 {return a
/Integer::Gcd(a
,b
)*b
;}
988 inline Integer
EuclideanMultiplicativeInverse(const Integer
&a
, const Integer
&b
)
989 {return a
.InverseMod(b
);}
991 // use Chinese Remainder Theorem to calculate x given x mod p and x mod q
992 CRYPTOPP_DLL Integer
CRT(const Integer
&xp
, const Integer
&p
, const Integer
&xq
, const Integer
&q
);
993 // use this one if u = inverse of p mod q has been precalculated
994 CRYPTOPP_DLL Integer
CRT(const Integer
&xp
, const Integer
&p
, const Integer
&xq
, const Integer
&q
, const Integer
&u
);
996 // if b is prime, then Jacobi(a, b) returns 0 if a%b==0, 1 if a is quadratic residue mod b, -1 otherwise
997 // check a number theory book for what Jacobi symbol means when b is not prime
998 CRYPTOPP_DLL
int Jacobi(const Integer
&a
, const Integer
&b
);
1000 // calculates the Lucas function V_e(p, 1) mod n
1001 CRYPTOPP_DLL Integer
Lucas(const Integer
&e
, const Integer
&p
, const Integer
&n
);
1002 // calculates x such that m==Lucas(e, x, p*q), p q primes
1003 CRYPTOPP_DLL Integer
InverseLucas(const Integer
&e
, const Integer
&m
, const Integer
&p
, const Integer
&q
);
1004 // use this one if u=inverse of p mod q has been precalculated
1005 CRYPTOPP_DLL Integer
InverseLucas(const Integer
&e
, const Integer
&m
, const Integer
&p
, const Integer
&q
, const Integer
&u
);
1007 inline Integer
ModularExponentiation(const Integer
&a
, const Integer
&e
, const Integer
&m
)
1008 {return a_exp_b_mod_c(a
, e
, m
);}
1009 // returns x such that a==ModularExponentiation(x, e, p*q), p q primes,
1010 // and e relatively prime to (p-1)*(q-1)
1011 CRYPTOPP_DLL Integer
ModularRoot(const Integer
&a
, const Integer
&e
, const Integer
&p
, const Integer
&q
);
1012 // use this one if dp=d%(p-1), dq=d%(q-1), (d is inverse of e mod (p-1)*(q-1))
1013 // and u=inverse of p mod q have been precalculated
1014 CRYPTOPP_DLL Integer
ModularRoot(const Integer
&a
, const Integer
&dp
, const Integer
&dq
, const Integer
&p
, const Integer
&q
, const Integer
&u
);
1019 ////////////////////////////////////////////////////////////////////////////////
1023 ////////////////////////////////////////////////////////////////////////////////
1024 // nbtheory.cpp - written and placed in the public domain by Wei Dai
1026 //- #include "pch.h"
1028 #ifndef CRYPTOPP_IMPORTS
1030 //- #include "nbtheory.h"
1031 //- #include "modarith.h"
1032 //- #include "algparam.h"
1037 NAMESPACE_BEGIN(CryptoPP
)
1039 const word s_lastSmallPrime
= 32719;
1041 struct NewPrimeTable
1043 std::vector
<word16
> * operator()() const
1045 const unsigned int maxPrimeTableSize
= 3511;
1047 std::auto_ptr
<std::vector
<word16
> > pPrimeTable(new std::vector
<word16
>);
1048 std::vector
<word16
> &primeTable
= *pPrimeTable
;
1049 primeTable
.reserve(maxPrimeTableSize
);
1051 primeTable
.push_back(2);
1052 unsigned int testEntriesEnd
= 1;
1054 for (unsigned int p
=3; p
<=s_lastSmallPrime
; p
+=2)
1057 for (j
=1; j
<testEntriesEnd
; j
++)
1058 if (p
%primeTable
[j
] == 0)
1060 if (j
== testEntriesEnd
)
1062 primeTable
.push_back(p
);
1063 testEntriesEnd
= STDMIN((size_t)54U, primeTable
.size());
1067 return pPrimeTable
.release();
1071 const word16
* GetPrimeTable(unsigned int &size
)
1073 const std::vector
<word16
> &primeTable
= Singleton
<std::vector
<word16
>, NewPrimeTable
>().Ref();
1074 size
= primeTable
.size();
1075 return &primeTable
[0];
1078 bool IsSmallPrime(const Integer
&p
)
1080 unsigned int primeTableSize
;
1081 const word16
* primeTable
= GetPrimeTable(primeTableSize
);
1083 if (p
.IsPositive() && p
<= primeTable
[primeTableSize
-1])
1084 return std::binary_search(primeTable
, primeTable
+primeTableSize
, (word16
)p
.ConvertToLong());
1089 bool TrialDivision(const Integer
&p
, unsigned bound
)
1091 unsigned int primeTableSize
;
1092 const word16
* primeTable
= GetPrimeTable(primeTableSize
);
1094 assert(primeTable
[primeTableSize
-1] >= bound
);
1097 for (i
= 0; primeTable
[i
]<bound
; i
++)
1098 if ((p
% primeTable
[i
]) == 0)
1101 if (bound
== primeTable
[i
])
1102 return (p
% bound
== 0);
1107 bool SmallDivisorsTest(const Integer
&p
)
1109 unsigned int primeTableSize
;
1110 const word16
* primeTable
= GetPrimeTable(primeTableSize
);
1111 return !TrialDivision(p
, primeTable
[primeTableSize
-1]);
1114 bool IsStrongProbablePrime(const Integer
&n
, const Integer
&b
)
1117 return n
==2 || n
==3;
1119 assert(n
>3 && b
>1 && b
<n
-1);
1121 if ((n
.IsEven() && n
!=2) || GCD(b
, n
) != 1)
1124 Integer nminus1
= (n
-1);
1127 // calculate a = largest power of 2 that divides (n-1)
1129 if (nminus1
.GetBit(a
))
1131 Integer m
= nminus1
>>a
;
1133 Integer z
= a_exp_b_mod_c(b
, m
, n
);
1134 if (z
==1 || z
==nminus1
)
1136 for (unsigned j
=1; j
<a
; j
++)
1147 bool RabinMillerTest(RandomNumberGenerator
&rng
, const Integer
&n
, unsigned int rounds
)
1150 return n
==2 || n
==3;
1155 for (unsigned int i
=0; i
<rounds
; i
++)
1157 b
.Randomize(rng
, 2, n
-2);
1158 if (!IsStrongProbablePrime(n
, b
))
1164 bool IsStrongLucasProbablePrime(const Integer
&n
)
1178 while ((j
=Jacobi(b
.Squared()-4, n
)) == 1)
1180 if (++i
==64 && n
.IsSquare()) // avoid infinite loop if n is a square
1191 // calculate a = largest power of 2 that divides n1
1197 Integer z
= Lucas(m
, b
, n
);
1202 z
= (z
.Squared()-2)%n
;
1211 struct NewLastSmallPrimeSquared
1213 Integer
* operator()() const
1215 return new Integer(Integer(s_lastSmallPrime
).Squared());
1219 bool IsPrime(const Integer
&p
)
1221 if (p
<= s_lastSmallPrime
)
1222 return IsSmallPrime(p
);
1223 else if (p
<= Singleton
<Integer
, NewLastSmallPrimeSquared
>().Ref())
1224 return SmallDivisorsTest(p
);
1226 return SmallDivisorsTest(p
) && IsStrongProbablePrime(p
, 3) && IsStrongLucasProbablePrime(p
);
1229 bool VerifyPrime(RandomNumberGenerator
&rng
, const Integer
&p
, unsigned int level
)
1231 bool pass
= IsPrime(p
) && RabinMillerTest(rng
, p
, 1);
1233 pass
= pass
&& RabinMillerTest(rng
, p
, 10);
1237 unsigned int PrimeSearchInterval(const Integer
&max
)
1239 return max
.BitCount();
1242 static inline bool FastProbablePrimeTest(const Integer
&n
)
1244 return IsStrongProbablePrime(n
,2);
1247 AlgorithmParameters
<AlgorithmParameters
<AlgorithmParameters
<NullNameValuePairs
, Integer::RandomNumberType
>, Integer
>, Integer
>
1248 MakeParametersForTwoPrimesOfEqualSize(unsigned int productBitLength
)
1250 if (productBitLength
< 16)
1251 throw InvalidArgument("invalid bit length");
1255 if (productBitLength
%2==0)
1257 minP
= Integer(182) << (productBitLength
/2-8);
1258 maxP
= Integer::Power2(productBitLength
/2)-1;
1262 minP
= Integer::Power2((productBitLength
-1)/2);
1263 maxP
= Integer(181) << ((productBitLength
+1)/2-8);
1266 return MakeParameters("RandomNumberType", Integer::PRIME
)("Min", minP
)("Max", maxP
);
1272 // delta == 1 or -1 means double sieve with p = 2*q + delta
1273 PrimeSieve(const Integer
&first
, const Integer
&last
, const Integer
&step
, signed int delta
=0);
1274 bool NextCandidate(Integer
&c
);
1277 static void SieveSingle(std::vector
<bool> &sieve
, word16 p
, const Integer
&first
, const Integer
&step
, word16 stepInv
);
1279 Integer m_first
, m_last
, m_step
;
1282 std::vector
<bool> m_sieve
;
1285 PrimeSieve::PrimeSieve(const Integer
&first
, const Integer
&last
, const Integer
&step
, signed int delta
)
1286 : m_first(first
), m_last(last
), m_step(step
), m_delta(delta
), m_next(0)
1291 bool PrimeSieve::NextCandidate(Integer
&c
)
1293 m_next
= std::find(m_sieve
.begin()+m_next
, m_sieve
.end(), false) - m_sieve
.begin();
1294 if (m_next
== m_sieve
.size())
1296 m_first
+= m_sieve
.size()*m_step
;
1297 if (m_first
> m_last
)
1303 return NextCandidate(c
);
1308 c
= m_first
+ m_next
*m_step
;
1314 void PrimeSieve::SieveSingle(std::vector
<bool> &sieve
, word16 p
, const Integer
&first
, const Integer
&step
, word16 stepInv
)
1318 unsigned int sieveSize
= sieve
.size();
1319 word j
= word((word32(p
-(first
%p
))*stepInv
) % p
);
1320 // if the first multiple of p is p, skip it
1321 if (first
.WordCount() <= 1 && first
+ step
*j
== p
)
1323 for (; j
< sieveSize
; j
+= p
)
1328 void PrimeSieve::DoSieve()
1330 unsigned int primeTableSize
;
1331 const word16
* primeTable
= GetPrimeTable(primeTableSize
);
1333 const unsigned int maxSieveSize
= 32768;
1334 unsigned int sieveSize
= STDMIN(Integer(maxSieveSize
), (m_last
-m_first
)/m_step
+1).ConvertToLong();
1337 m_sieve
.resize(sieveSize
, false);
1341 for (unsigned int i
= 0; i
< primeTableSize
; ++i
)
1342 SieveSingle(m_sieve
, primeTable
[i
], m_first
, m_step
, m_step
.InverseMod(primeTable
[i
]));
1346 assert(m_step
%2==0);
1347 Integer qFirst
= (m_first
-m_delta
) >> 1;
1348 Integer halfStep
= m_step
>> 1;
1349 for (unsigned int i
= 0; i
< primeTableSize
; ++i
)
1351 word16 p
= primeTable
[i
];
1352 word16 stepInv
= m_step
.InverseMod(p
);
1353 SieveSingle(m_sieve
, p
, m_first
, m_step
, stepInv
);
1355 word16 halfStepInv
= 2*stepInv
< p
? 2*stepInv
: 2*stepInv
-p
;
1356 SieveSingle(m_sieve
, p
, qFirst
, halfStep
, halfStepInv
);
1361 bool FirstPrime(Integer
&p
, const Integer
&max
, const Integer
&equiv
, const Integer
&mod
, const PrimeSelector
*pSelector
)
1363 assert(!equiv
.IsNegative() && equiv
< mod
);
1365 Integer gcd
= GCD(equiv
, mod
);
1366 if (gcd
!= Integer::One())
1368 // the only possible prime p such that p%mod==equiv where GCD(mod,equiv)!=1 is GCD(mod,equiv)
1369 if (p
<= gcd
&& gcd
<= max
&& IsPrime(gcd
) && (!pSelector
|| pSelector
->IsAcceptable(gcd
)))
1378 unsigned int primeTableSize
;
1379 const word16
* primeTable
= GetPrimeTable(primeTableSize
);
1381 if (p
<= primeTable
[primeTableSize
-1])
1387 pItr
= std::upper_bound(primeTable
, primeTable
+primeTableSize
, (word
)p
.ConvertToLong());
1391 while (pItr
< primeTable
+primeTableSize
&& !(*pItr
%mod
== equiv
&& (!pSelector
|| pSelector
->IsAcceptable(*pItr
))))
1394 if (pItr
< primeTable
+primeTableSize
)
1400 p
= primeTable
[primeTableSize
-1]+1;
1403 assert(p
> primeTable
[primeTableSize
-1]);
1406 return FirstPrime(p
, max
, CRT(equiv
, mod
, 1, 2, 1), mod
<<1, pSelector
);
1413 PrimeSieve
sieve(p
, max
, mod
);
1415 while (sieve
.NextCandidate(p
))
1417 if ((!pSelector
|| pSelector
->IsAcceptable(p
)) && FastProbablePrimeTest(p
) && IsPrime(p
))
1424 Integer
CRT(const Integer
&xp
, const Integer
&p
, const Integer
&xq
, const Integer
&q
, const Integer
&u
)
1426 // isn't operator overloading great?
1427 return p
* (u
* (xq
-xp
) % q
) + xp
;
1430 Integer
CRT(const Integer
&xp
, const Integer
&p
, const Integer
&xq
, const Integer
&q
)
1432 return CRT(xp
, p
, xq
, q
, EuclideanMultiplicativeInverse(p
, q
));
1435 Integer
ModularRoot(const Integer
&a
, const Integer
&dp
, const Integer
&dq
,
1436 const Integer
&p
, const Integer
&q
, const Integer
&u
)
1438 Integer p2
= ModularExponentiation((a
% p
), dp
, p
);
1439 Integer q2
= ModularExponentiation((a
% q
), dq
, q
);
1440 return CRT(p2
, p
, q2
, q
, u
);
1443 Integer
ModularRoot(const Integer
&a
, const Integer
&e
,
1444 const Integer
&p
, const Integer
&q
)
1446 Integer dp
= EuclideanMultiplicativeInverse(e
, p
-1);
1447 Integer dq
= EuclideanMultiplicativeInverse(e
, q
-1);
1448 Integer u
= EuclideanMultiplicativeInverse(p
, q
);
1449 assert(!!dp
&& !!dq
&& !!u
);
1450 return ModularRoot(a
, dp
, dq
, p
, q
, u
);
1453 int Jacobi(const Integer
&aIn
, const Integer
&bIn
)
1455 assert(bIn
.IsOdd());
1457 Integer b
= bIn
, a
= aIn
%bIn
;
1463 while (a
.GetBit(i
)==0)
1467 if (i
%2==1 && (b
%8==3 || b
%8==5))
1470 if (a
%4==3 && b
%4==3)
1477 return (b
==1) ? result
: 0;
1480 Integer
Lucas(const Integer
&e
, const Integer
&pIn
, const Integer
&n
)
1482 unsigned i
= e
.BitCount();
1484 return Integer::Two();
1486 MontgomeryRepresentation
m(n
);
1487 Integer p
=m
.ConvertIn(pIn
%n
), two
=m
.ConvertIn(Integer::Two());
1488 Integer v
=p
, v1
=m
.Subtract(m
.Square(p
), two
);
1495 // v = (v*v1 - p) % m;
1496 v
= m
.Subtract(m
.Multiply(v
,v1
), p
);
1497 // v1 = (v1*v1 - 2) % m;
1498 v1
= m
.Subtract(m
.Square(v1
), two
);
1502 // v1 = (v*v1 - p) % m;
1503 v1
= m
.Subtract(m
.Multiply(v
,v1
), p
);
1504 // v = (v*v - 2) % m;
1505 v
= m
.Subtract(m
.Square(v
), two
);
1508 return m
.ConvertOut(v
);
1511 Integer
InverseLucas(const Integer
&e
, const Integer
&m
, const Integer
&p
, const Integer
&q
, const Integer
&u
)
1513 Integer d
= (m
*m
-4);
1514 Integer p2
= p
-Jacobi(d
,p
);
1515 Integer q2
= q
-Jacobi(d
,q
);
1516 return CRT(Lucas(EuclideanMultiplicativeInverse(e
,p2
), m
, p
), p
, Lucas(EuclideanMultiplicativeInverse(e
,q2
), m
, q
), q
, u
);
1519 Integer
InverseLucas(const Integer
&e
, const Integer
&m
, const Integer
&p
, const Integer
&q
)
1521 return InverseLucas(e
, m
, p
, q
, EuclideanMultiplicativeInverse(p
, q
));
1527 ////////////////////////////////////////////////////////////////////////////////
1531 ////////////////////////////////////////////////////////////////////////////////
1532 #ifndef CRYPTOPP_OIDS_H
1533 #define CRYPTOPP_OIDS_H
1535 // crypto-related ASN.1 object identifiers
1537 //- #include "asn.h"
1539 NAMESPACE_BEGIN(CryptoPP
)
1541 NAMESPACE_BEGIN(ASN1
)
1543 #define DEFINE_OID(value, name) inline OID name() {return value;}
1546 DEFINE_OID(iso()+2, member_body
)
1547 DEFINE_OID(member_body()+840, iso_us
)
1548 DEFINE_OID(iso_us()+10040, ansi_x9_57
)
1549 DEFINE_OID(ansi_x9_57()+4+1, id_dsa
)
1550 DEFINE_OID(iso_us()+10045, ansi_x9_62
)
1551 DEFINE_OID(ansi_x9_62()+1, id_fieldType
)
1552 DEFINE_OID(id_fieldType()+1, prime_field
)
1553 DEFINE_OID(id_fieldType()+2, characteristic_two_field
)
1554 DEFINE_OID(characteristic_two_field()+3, id_characteristic_two_basis
)
1555 DEFINE_OID(id_characteristic_two_basis()+1, gnBasis
)
1556 DEFINE_OID(id_characteristic_two_basis()+2, tpBasis
)
1557 DEFINE_OID(id_characteristic_two_basis()+3, ppBasis
)
1558 DEFINE_OID(ansi_x9_62()+2, id_publicKeyType
)
1559 DEFINE_OID(id_publicKeyType()+1, id_ecPublicKey
)
1560 DEFINE_OID(ansi_x9_62()+3, ansi_x9_62_curves
)
1561 DEFINE_OID(ansi_x9_62_curves()+1, ansi_x9_62_curves_prime
)
1562 DEFINE_OID(ansi_x9_62_curves_prime()+1, secp192r1
)
1563 DEFINE_OID(ansi_x9_62_curves_prime()+7, secp256r1
)
1564 DEFINE_OID(iso_us()+113549, rsadsi
)
1565 DEFINE_OID(rsadsi()+1, pkcs
)
1566 DEFINE_OID(pkcs()+1, pkcs_1
)
1567 DEFINE_OID(pkcs_1()+1, rsaEncryption
)
1568 DEFINE_OID(rsadsi()+2, rsadsi_digestAlgorithm
)
1569 DEFINE_OID(rsadsi_digestAlgorithm()+2, id_md2
)
1570 DEFINE_OID(rsadsi_digestAlgorithm()+5, id_md5
)
1571 DEFINE_OID(iso()+3, identified_organization
)
1572 DEFINE_OID(identified_organization()+14, oiw
)
1573 DEFINE_OID(oiw()+14, oiw_secsig
)
1574 DEFINE_OID(oiw_secsig()+2, oiw_secsig_algorithms
)
1575 DEFINE_OID(oiw_secsig_algorithms()+26, id_sha1
)
1576 DEFINE_OID(identified_organization()+36, teletrust
)
1577 DEFINE_OID(teletrust()+3+2+1, id_ripemd160
)
1578 DEFINE_OID(identified_organization()+132, certicom
)
1579 DEFINE_OID(certicom()+0, certicom_ellipticCurve
)
1580 // these are sorted by curve type and then by OID
1581 // first curves based on GF(p)
1582 DEFINE_OID(certicom_ellipticCurve()+6, secp112r1
)
1583 DEFINE_OID(certicom_ellipticCurve()+7, secp112r2
)
1584 DEFINE_OID(certicom_ellipticCurve()+8, secp160r1
)
1585 DEFINE_OID(certicom_ellipticCurve()+9, secp160k1
)
1586 DEFINE_OID(certicom_ellipticCurve()+10, secp256k1
)
1587 DEFINE_OID(certicom_ellipticCurve()+28, secp128r1
)
1588 DEFINE_OID(certicom_ellipticCurve()+29, secp128r2
)
1589 DEFINE_OID(certicom_ellipticCurve()+30, secp160r2
)
1590 DEFINE_OID(certicom_ellipticCurve()+31, secp192k1
)
1591 DEFINE_OID(certicom_ellipticCurve()+32, secp224k1
)
1592 DEFINE_OID(certicom_ellipticCurve()+33, secp224r1
)
1593 DEFINE_OID(certicom_ellipticCurve()+34, secp384r1
)
1594 DEFINE_OID(certicom_ellipticCurve()+35, secp521r1
)
1595 // then curves based on GF(2^n)
1596 DEFINE_OID(certicom_ellipticCurve()+1, sect163k1
)
1597 DEFINE_OID(certicom_ellipticCurve()+2, sect163r1
)
1598 DEFINE_OID(certicom_ellipticCurve()+3, sect239k1
)
1599 DEFINE_OID(certicom_ellipticCurve()+4, sect113r1
)
1600 DEFINE_OID(certicom_ellipticCurve()+5, sect113r2
)
1601 DEFINE_OID(certicom_ellipticCurve()+15, sect163r2
)
1602 DEFINE_OID(certicom_ellipticCurve()+16, sect283k1
)
1603 DEFINE_OID(certicom_ellipticCurve()+17, sect283r1
)
1604 DEFINE_OID(certicom_ellipticCurve()+22, sect131r1
)
1605 DEFINE_OID(certicom_ellipticCurve()+23, sect131r2
)
1606 DEFINE_OID(certicom_ellipticCurve()+24, sect193r1
)
1607 DEFINE_OID(certicom_ellipticCurve()+25, sect193r2
)
1608 DEFINE_OID(certicom_ellipticCurve()+26, sect233k1
)
1609 DEFINE_OID(certicom_ellipticCurve()+27, sect233r1
)
1610 DEFINE_OID(certicom_ellipticCurve()+36, sect409k1
)
1611 DEFINE_OID(certicom_ellipticCurve()+37, sect409r1
)
1612 DEFINE_OID(certicom_ellipticCurve()+38, sect571k1
)
1613 DEFINE_OID(certicom_ellipticCurve()+39, sect571r1
)
1614 DEFINE_OID(2, joint_iso_ccitt
)
1615 DEFINE_OID(joint_iso_ccitt()+16, country
)
1616 DEFINE_OID(country()+840, joint_iso_ccitt_us
)
1617 DEFINE_OID(joint_iso_ccitt_us()+1, us_organization
)
1618 DEFINE_OID(us_organization()+101, us_gov
)
1619 DEFINE_OID(us_gov()+3, csor
)
1620 DEFINE_OID(csor()+4, nistalgorithms
)
1621 DEFINE_OID(nistalgorithms()+1, aes
)
1622 DEFINE_OID(aes()+1, id_aes128_ECB
)
1623 DEFINE_OID(aes()+2, id_aes128_cbc
)
1624 DEFINE_OID(aes()+3, id_aes128_ofb
)
1625 DEFINE_OID(aes()+4, id_aes128_cfb
)
1626 DEFINE_OID(aes()+21, id_aes192_ECB
)
1627 DEFINE_OID(aes()+22, id_aes192_cbc
)
1628 DEFINE_OID(aes()+23, id_aes192_ofb
)
1629 DEFINE_OID(aes()+24, id_aes192_cfb
)
1630 DEFINE_OID(aes()+41, id_aes256_ECB
)
1631 DEFINE_OID(aes()+42, id_aes256_cbc
)
1632 DEFINE_OID(aes()+43, id_aes256_ofb
)
1633 DEFINE_OID(aes()+44, id_aes256_cfb
)
1634 DEFINE_OID(nistalgorithms()+2, nist_hashalgs
)
1635 DEFINE_OID(nist_hashalgs()+1, id_sha256
)
1636 DEFINE_OID(nist_hashalgs()+2, id_sha384
)
1637 DEFINE_OID(nist_hashalgs()+3, id_sha512
)
1644 ////////////////////////////////////////////////////////////////////////////////
1648 ////////////////////////////////////////////////////////////////////////////////
1649 // integer.cpp - written and placed in the public domain by Wei Dai
1650 // contains public domain code contributed by Alister Lee and Leonard Janke
1652 //- #include "pch.h"
1654 #ifndef CRYPTOPP_IMPORTS
1656 //- #include "integer.h"
1657 //- #include "modarith.h"
1658 //- #include "nbtheory.h"
1659 //- #include "asn.h"
1660 //- #include "oids.h"
1661 //- #include "words.h"
1662 //- #include "algparam.h"
1663 //- #include "pubkey.h" // for P1363_KDF2
1664 //- #include "sha.h"
1668 #ifdef SSE2_INTRINSICS_AVAILABLE
1670 #include <xmmintrin.h>
1673 #ifdef CRYPTOPP_MEMALIGN_AVAILABLE
1679 #include <emmintrin.h>
1681 #elif defined(_MSC_VER) && defined(_M_IX86)
1682 #pragma message("You do not seem to have the Visual C++ Processor Pack installed, so use of SSE2 intrinsics will be disabled.")
1683 #elif defined(__GNUC__) && defined(__i386__)
1684 #warning "You do not have GCC 3.3 or later, or did not specify -msse2 compiler option, so use of SSE2 intrinsics will be disabled."
1687 NAMESPACE_BEGIN(CryptoPP
)
1689 bool FunctionAssignIntToInteger(const std::type_info
&valueType
, void *pInteger
, const void *pInt
)
1691 if (valueType
!= typeid(Integer
))
1693 *reinterpret_cast<Integer
*>(pInteger
) = *reinterpret_cast<const int *>(pInt
);
1697 static const char s_RunAtStartup
= (AssignIntToInteger
= FunctionAssignIntToInteger
, 0);
1699 #ifdef SSE2_INTRINSICS_AVAILABLE
1701 CPP_TYPENAME AllocatorBase
<T
>::pointer AlignedAllocator
<T
>::allocate(size_type n
, const void *)
1709 #ifdef CRYPTOPP_MM_MALLOC_AVAILABLE
1710 while (!(p
= _mm_malloc(sizeof(T
)*n
, 16)))
1711 #elif defined(CRYPTOPP_MEMALIGN_AVAILABLE)
1712 while (!(p
= memalign(16, sizeof(T
)*n
)))
1713 #elif defined(CRYPTOPP_MALLOC_ALIGNMENT_IS_16)
1714 while (!(p
= malloc(sizeof(T
)*n
)))
1716 while (!(p
= (byte
*)malloc(sizeof(T
)*n
+ 8))) // assume malloc alignment is at least 8
1720 #ifdef CRYPTOPP_NO_ALIGNED_ALLOC
1721 assert(m_pBlock
== NULL
);
1723 if (!IsAlignedOn(p
, 16))
1725 assert(IsAlignedOn(p
, 8));
1730 assert(IsAlignedOn(p
, 16));
1737 void AlignedAllocator
<T
>::deallocate(void *p
, size_type n
)
1739 memset(p
, 0, n
*sizeof(T
));
1742 #ifdef CRYPTOPP_MM_MALLOC_AVAILABLE
1744 #elif defined(CRYPTOPP_NO_ALIGNED_ALLOC)
1745 assert(m_pBlock
== p
|| (byte
*)m_pBlock
+8 == p
);
1757 static int Compare(const word
*A
, const word
*B
, unsigned int N
)
1762 else if (A
[N
] < B
[N
])
1768 static word
Increment(word
*A
, unsigned int N
, word B
=1)
1775 for (unsigned i
=1; i
<N
; i
++)
1781 static word
Decrement(word
*A
, unsigned int N
, word B
=1)
1788 for (unsigned i
=1; i
<N
; i
++)
1794 static void TwosComplement(word
*A
, unsigned int N
)
1797 for (unsigned i
=0; i
<N
; i
++)
1801 static word
AtomicInverseModPower2(word A
)
1807 for (unsigned i
=3; i
<WORD_BITS
; i
*=2)
1814 // ********************************************************
1821 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1822 explicit DWord(word low
)
1827 explicit DWord(word low
)
1834 DWord(word low
, word high
)
1837 m_halfs
.high
= high
;
1840 static DWord
Multiply(word a
, word b
)
1843 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1844 r
.m_whole
= (dword
)a
* b
;
1845 #elif defined(__alpha__)
1846 r
.m_halfs
.low
= a
*b
; __asm__("umulh %1,%2,%0" : "=r" (r
.m_halfs
.high
) : "r" (a
), "r" (b
));
1847 #elif defined(__ia64__)
1848 r
.m_halfs
.low
= a
*b
; __asm__("xmpy.hu %0=%1,%2" : "=f" (r
.m_halfs
.high
) : "f" (a
), "f" (b
));
1849 #elif defined(_ARCH_PPC64)
1850 r
.m_halfs
.low
= a
*b
; __asm__("mulhdu %0,%1,%2" : "=r" (r
.m_halfs
.high
) : "r" (a
), "r" (b
) : "cc");
1851 #elif defined(__x86_64__)
1852 __asm__("mulq %3" : "=d" (r
.m_halfs
.high
), "=a" (r
.m_halfs
.low
) : "a" (a
), "rm" (b
) : "cc");
1853 #elif defined(__mips64)
1854 //typedef unsigned int uint128_t __attribute__((mode(TI)));
1855 __uint128_t tmp
= (__uint128_t
) a
* b
;
1856 r
.m_halfs
.high
= tmp
>> 64;
1857 r
.m_halfs
.low
= tmp
;
1858 #elif defined(_M_IX86)
1860 word64 t
= (word64
)a
* b
;
1861 r
.m_halfs
.high
= ((word32
*)(&t
))[1];
1862 r
.m_halfs
.low
= (word32
)t
;
1864 #error can not implement DWord
1869 static DWord
MultiplyAndAdd(word a
, word b
, word c
)
1871 DWord r
= Multiply(a
, b
);
1875 DWord
& operator+=(word a
)
1877 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1878 m_whole
= m_whole
+ a
;
1881 m_halfs
.high
+= (m_halfs
.low
< a
);
1886 DWord
operator+(word a
)
1889 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1890 r
.m_whole
= m_whole
+ a
;
1892 r
.m_halfs
.low
= m_halfs
.low
+ a
;
1893 r
.m_halfs
.high
= m_halfs
.high
+ (r
.m_halfs
.low
< a
);
1898 DWord
operator-(DWord a
)
1901 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1902 r
.m_whole
= m_whole
- a
.m_whole
;
1904 r
.m_halfs
.low
= m_halfs
.low
- a
.m_halfs
.low
;
1905 r
.m_halfs
.high
= m_halfs
.high
- a
.m_halfs
.high
- (r
.m_halfs
.low
> m_halfs
.low
);
1910 DWord
operator-(word a
)
1913 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1914 r
.m_whole
= m_whole
- a
;
1916 r
.m_halfs
.low
= m_halfs
.low
- a
;
1917 r
.m_halfs
.high
= m_halfs
.high
- (r
.m_halfs
.low
> m_halfs
.low
);
1922 // returns quotient, which must fit in a word
1923 word
operator/(word divisor
);
1925 word
operator%(word a
);
1927 bool operator!() const
1929 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1932 return !m_halfs
.high
&& !m_halfs
.low
;
1936 word
GetLowHalf() const {return m_halfs
.low
;}
1937 word
GetHighHalf() const {return m_halfs
.high
;}
1938 word
GetHighHalfAsBorrow() const {return 0-m_halfs
.high
;}
1943 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
1948 #ifdef IS_LITTLE_ENDIAN
1969 Word(hword low
, hword high
)
1971 m_whole
= low
| (word(high
) << (WORD_BITS
/2));
1974 static Word
Multiply(hword a
, hword b
)
1977 r
.m_whole
= (word
)a
* b
;
1981 Word
operator-(Word a
)
1984 r
.m_whole
= m_whole
- a
.m_whole
;
1988 Word
operator-(hword a
)
1991 r
.m_whole
= m_whole
- a
;
1995 // returns quotient, which must fit in a word
1996 hword
operator/(hword divisor
)
1998 return hword(m_whole
/ divisor
);
2001 bool operator!() const
2006 word
GetWhole() const {return m_whole
;}
2007 hword
GetLowHalf() const {return hword(m_whole
);}
2008 hword
GetHighHalf() const {return hword(m_whole
>>(WORD_BITS
/2));}
2009 hword
GetHighHalfAsBorrow() const {return 0-hword(m_whole
>>(WORD_BITS
/2));}
2015 // do a 3 word by 2 word divide, returns quotient and leaves remainder in A
2016 template <class S
, class D
>
2017 S
DivideThreeWordsByTwo(S
*A
, S B0
, S B1
, D
* /* dummy */ = NULL
)
2019 // assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a S
2020 assert(A
[2] < B1
|| (A
[2]==B1
&& A
[1] < B0
));
2022 // estimate the quotient: do a 2 S by 1 S divide
2027 Q
= D(A
[1], A
[2]) / S(B1
+1);
2029 // now subtract Q*B from A
2030 D p
= D::Multiply(B0
, Q
);
2031 D u
= (D
) A
[0] - p
.GetLowHalf();
2032 A
[0] = u
.GetLowHalf();
2033 u
= (D
) A
[1] - p
.GetHighHalf() - u
.GetHighHalfAsBorrow() - D::Multiply(B1
, Q
);
2034 A
[1] = u
.GetLowHalf();
2035 A
[2] += u
.GetHighHalf();
2037 // Q <= actual quotient, so fix it
2038 while (A
[2] || A
[1] > B1
|| (A
[1]==B1
&& A
[0]>=B0
))
2041 A
[0] = u
.GetLowHalf();
2042 u
= (D
) A
[1] - B1
- u
.GetHighHalfAsBorrow();
2043 A
[1] = u
.GetLowHalf();
2044 A
[2] += u
.GetHighHalf();
2046 assert(Q
); // shouldn't overflow
2052 // do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1
2053 template <class S
, class D
>
2054 inline D
DivideFourWordsByTwo(S
*T
, const D
&Al
, const D
&Ah
, const D
&B
)
2056 if (!B
) // if divisor is 0, we assume divisor==2**(2*WORD_BITS)
2057 return D(Ah
.GetLowHalf(), Ah
.GetHighHalf());
2061 T
[0] = Al
.GetLowHalf();
2062 T
[1] = Al
.GetHighHalf();
2063 T
[2] = Ah
.GetLowHalf();
2064 T
[3] = Ah
.GetHighHalf();
2065 Q
[1] = DivideThreeWordsByTwo
<S
, D
>(T
+1, B
.GetLowHalf(), B
.GetHighHalf());
2066 Q
[0] = DivideThreeWordsByTwo
<S
, D
>(T
, B
.GetLowHalf(), B
.GetHighHalf());
2067 return D(Q
[0], Q
[1]);
2071 // returns quotient, which must fit in a word
2072 inline word
DWord::operator/(word a
)
2074 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
2075 return word(m_whole
/ a
);
2078 return DivideFourWordsByTwo
<hword
, Word
>(r
, m_halfs
.low
, m_halfs
.high
, a
).GetWhole();
2082 inline word
DWord::operator%(word a
)
2084 #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE
2085 return word(m_whole
% a
);
2087 if (a
< (word(1) << (WORD_BITS
/2)))
2090 word r
= m_halfs
.high
% h
;
2091 r
= ((m_halfs
.low
>> (WORD_BITS
/2)) + (r
<< (WORD_BITS
/2))) % h
;
2092 return hword((hword(m_halfs
.low
) + (r
<< (WORD_BITS
/2))) % h
);
2097 DivideFourWordsByTwo
<hword
, Word
>(r
, m_halfs
.low
, m_halfs
.high
, a
);
2098 return Word(r
[0], r
[1]).GetWhole();
2103 // ********************************************************
2108 static word
Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2109 static word
Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2111 static inline void Multiply2(word
*C
, const word
*A
, const word
*B
);
2112 static inline word
Multiply2Add(word
*C
, const word
*A
, const word
*B
);
2113 static void Multiply4(word
*C
, const word
*A
, const word
*B
);
2114 static void Multiply8(word
*C
, const word
*A
, const word
*B
);
2115 static inline unsigned int MultiplyRecursionLimit() {return 8;}
2117 static inline void Multiply2Bottom(word
*C
, const word
*A
, const word
*B
);
2118 static void Multiply4Bottom(word
*C
, const word
*A
, const word
*B
);
2119 static void Multiply8Bottom(word
*C
, const word
*A
, const word
*B
);
2120 static inline unsigned int MultiplyBottomRecursionLimit() {return 8;}
2122 static void Square2(word
*R
, const word
*A
);
2123 static void Square4(word
*R
, const word
*A
);
2124 static void Square8(word
* /* R */, const word
* /* A */) {assert(false);}
2125 static inline unsigned int SquareRecursionLimit() {return 4;}
2128 word
Portable::Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2133 for (unsigned int i
= 0; i
< N
; i
+=2)
2135 u
= DWord(A
[i
]) + B
[i
] + u
.GetHighHalf();
2136 C
[i
] = u
.GetLowHalf();
2137 u
= DWord(A
[i
+1]) + B
[i
+1] + u
.GetHighHalf();
2138 C
[i
+1] = u
.GetLowHalf();
2140 return u
.GetHighHalf();
2143 word
Portable::Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2148 for (unsigned int i
= 0; i
< N
; i
+=2)
2150 u
= (DWord
) A
[i
] - B
[i
] - u
.GetHighHalfAsBorrow();
2151 C
[i
] = u
.GetLowHalf();
2152 u
= (DWord
) A
[i
+1] - B
[i
+1] - u
.GetHighHalfAsBorrow();
2153 C
[i
+1] = u
.GetLowHalf();
2155 return 0-u
.GetHighHalf();
2158 void Portable::Multiply2(word
*C
, const word
*A
, const word
*B
)
2160 // this segment is the branchless equivalent of above
2161 word D
[4] = {A
[1]-A
[0], A
[0]-A
[1], B
[0]-B
[1], B
[1]-B
[0]};
2162 unsigned int ai
= A
[1] < A
[0];
2163 unsigned int bi
= B
[0] < B
[1];
2164 unsigned int di
= ai
& bi
;
2165 DWord d
= DWord::Multiply(D
[di
], D
[di
+2]);
2167 unsigned int si
= ai
+ !bi
;
2170 DWord A0B0
= DWord::Multiply(A
[0], B
[0]);
2171 C
[0] = A0B0
.GetLowHalf();
2173 DWord A1B1
= DWord::Multiply(A
[1], B
[1]);
2174 DWord t
= (DWord
) A0B0
.GetHighHalf() + A0B0
.GetLowHalf() + d
.GetLowHalf() + A1B1
.GetLowHalf();
2175 C
[1] = t
.GetLowHalf();
2177 t
= A1B1
+ t
.GetHighHalf() + A0B0
.GetHighHalf() + d
.GetHighHalf() + A1B1
.GetHighHalf() - s
;
2178 C
[2] = t
.GetLowHalf();
2179 C
[3] = t
.GetHighHalf();
2182 inline void Portable::Multiply2Bottom(word
*C
, const word
*A
, const word
*B
)
2184 DWord t
= DWord::Multiply(A
[0], B
[0]);
2185 C
[0] = t
.GetLowHalf();
2186 C
[1] = t
.GetHighHalf() + A
[0]*B
[1] + A
[1]*B
[0];
2189 word
Portable::Multiply2Add(word
*C
, const word
*A
, const word
*B
)
2191 word D
[4] = {A
[1]-A
[0], A
[0]-A
[1], B
[0]-B
[1], B
[1]-B
[0]};
2192 unsigned int ai
= A
[1] < A
[0];
2193 unsigned int bi
= B
[0] < B
[1];
2194 unsigned int di
= ai
& bi
;
2195 DWord d
= DWord::Multiply(D
[di
], D
[di
+2]);
2197 unsigned int si
= ai
+ !bi
;
2200 DWord A0B0
= DWord::Multiply(A
[0], B
[0]);
2201 DWord t
= A0B0
+ C
[0];
2202 C
[0] = t
.GetLowHalf();
2204 DWord A1B1
= DWord::Multiply(A
[1], B
[1]);
2205 t
= (DWord
) t
.GetHighHalf() + A0B0
.GetLowHalf() + d
.GetLowHalf() + A1B1
.GetLowHalf() + C
[1];
2206 C
[1] = t
.GetLowHalf();
2208 t
= (DWord
) t
.GetHighHalf() + A1B1
.GetLowHalf() + A0B0
.GetHighHalf() + d
.GetHighHalf() + A1B1
.GetHighHalf() - s
+ C
[2];
2209 C
[2] = t
.GetLowHalf();
2211 t
= (DWord
) t
.GetHighHalf() + A1B1
.GetHighHalf() + C
[3];
2212 C
[3] = t
.GetLowHalf();
2213 return t
.GetHighHalf();
2216 #define MulAcc(x, y) \
2217 p = DWord::MultiplyAndAdd(A[x], B[y], c); \
2218 c = p.GetLowHalf(); \
2219 p = (DWord) d + p.GetHighHalf(); \
2220 d = p.GetLowHalf(); \
2221 e += p.GetHighHalf();
2223 #define SaveMulAcc(s, x, y) \
2225 p = DWord::MultiplyAndAdd(A[x], B[y], d); \
2226 c = p.GetLowHalf(); \
2227 p = (DWord) e + p.GetHighHalf(); \
2228 d = p.GetLowHalf(); \
2229 e = p.GetHighHalf();
2231 #define SquAcc(x, y) \
2232 q = DWord::Multiply(A[x], A[y]); \
2234 c = p.GetLowHalf(); \
2235 p = (DWord) d + p.GetHighHalf(); \
2236 d = p.GetLowHalf(); \
2237 e += p.GetHighHalf(); \
2239 c = p.GetLowHalf(); \
2240 p = (DWord) d + p.GetHighHalf(); \
2241 d = p.GetLowHalf(); \
2242 e += p.GetHighHalf();
2244 #define SaveSquAcc(s, x, y) \
2246 q = DWord::Multiply(A[x], A[y]); \
2248 c = p.GetLowHalf(); \
2249 p = (DWord) e + p.GetHighHalf(); \
2250 d = p.GetLowHalf(); \
2251 e = p.GetHighHalf(); \
2253 c = p.GetLowHalf(); \
2254 p = (DWord) d + p.GetHighHalf(); \
2255 d = p.GetLowHalf(); \
2256 e += p.GetHighHalf();
2258 void Portable::Multiply4(word
*R
, const word
*A
, const word
*B
)
2263 p
= DWord::Multiply(A
[0], B
[0]);
2264 R
[0] = p
.GetLowHalf();
2265 c
= p
.GetHighHalf();
2271 SaveMulAcc(1, 2, 0);
2275 SaveMulAcc(2, 0, 3);
2280 SaveMulAcc(3, 3, 1);
2284 SaveMulAcc(4, 2, 3);
2288 p
= DWord::MultiplyAndAdd(A
[3], B
[3], d
);
2289 R
[6] = p
.GetLowHalf();
2290 R
[7] = e
+ p
.GetHighHalf();
2293 void Portable::Square2(word
*R
, const word
*A
)
2298 p
= DWord::Multiply(A
[0], A
[0]);
2299 R
[0] = p
.GetLowHalf();
2300 c
= p
.GetHighHalf();
2306 p
= DWord::MultiplyAndAdd(A
[1], A
[1], d
);
2307 R
[2] = p
.GetLowHalf();
2308 R
[3] = e
+ p
.GetHighHalf();
2311 void Portable::Square4(word
*R
, const word
*A
)
2314 // VC60 workaround: MSVC 6.0 has an optimization bug that makes
2315 // (dword)A*B where either A or B has been cast to a dword before
2316 // very expensive. Revisit this function when this
2324 p
= DWord::Multiply(A
[0], A
[0]);
2325 R
[0] = p
.GetLowHalf();
2326 c
= p
.GetHighHalf();
2331 SaveSquAcc(1, 2, 0);
2334 SaveSquAcc(2, 0, 3);
2337 SaveSquAcc(3, 3, 1);
2340 SaveSquAcc(4, 2, 3);
2343 p
= DWord::MultiplyAndAdd(A
[3], A
[3], d
);
2344 R
[6] = p
.GetLowHalf();
2345 R
[7] = e
+ p
.GetHighHalf();
2349 void Portable::Multiply8(word
*R
, const word
*A
, const word
*B
)
2354 p
= DWord::Multiply(A
[0], B
[0]);
2355 R
[0] = p
.GetLowHalf();
2356 c
= p
.GetHighHalf();
2362 SaveMulAcc(1, 2, 0);
2366 SaveMulAcc(2, 0, 3);
2371 SaveMulAcc(3, 0, 4);
2377 SaveMulAcc(4, 0, 5);
2384 SaveMulAcc(5, 0, 6);
2392 SaveMulAcc(6, 0, 7);
2401 SaveMulAcc(7, 1, 7);
2409 SaveMulAcc(8, 2, 7);
2416 SaveMulAcc(9, 3, 7);
2422 SaveMulAcc(10, 4, 7);
2427 SaveMulAcc(11, 5, 7);
2431 SaveMulAcc(12, 6, 7);
2435 p
= DWord::MultiplyAndAdd(A
[7], B
[7], d
);
2436 R
[14] = p
.GetLowHalf();
2437 R
[15] = e
+ p
.GetHighHalf();
2440 void Portable::Multiply4Bottom(word
*R
, const word
*A
, const word
*B
)
2445 p
= DWord::Multiply(A
[0], B
[0]);
2446 R
[0] = p
.GetLowHalf();
2447 c
= p
.GetHighHalf();
2453 SaveMulAcc(1, 2, 0);
2458 R
[3] = d
+ A
[0] * B
[3] + A
[1] * B
[2] + A
[2] * B
[1] + A
[3] * B
[0];
2461 void Portable::Multiply8Bottom(word
*R
, const word
*A
, const word
*B
)
2466 p
= DWord::Multiply(A
[0], B
[0]);
2467 R
[0] = p
.GetLowHalf();
2468 c
= p
.GetHighHalf();
2474 SaveMulAcc(1, 2, 0);
2478 SaveMulAcc(2, 0, 3);
2483 SaveMulAcc(3, 0, 4);
2489 SaveMulAcc(4, 0, 5);
2496 SaveMulAcc(5, 0, 6);
2505 R
[7] = d
+ A
[0] * B
[7] + A
[1] * B
[6] + A
[2] * B
[5] + A
[3] * B
[4] +
2506 A
[4] * B
[3] + A
[5] * B
[2] + A
[6] * B
[1] + A
[7] * B
[0];
2514 #ifdef CRYPTOPP_X86ASM_AVAILABLE
2516 // ************** x86 feature detection ***************
2518 static void CpuId(word32 input
, word32
*output
)
2523 // save ebx in case -fPIC is being used
2524 "push %%ebx; cpuid; mov %%ebx, %%edi; pop %%ebx"
2525 : "=a" (output
[0]), "=D" (output
[1]), "=c" (output
[2]), "=d" (output
[3])
2547 std::swap(cpuid
[2], cpuid
[3]);
2548 if (memcmp(cpuid
+1, "GenuineIntel", 12) != 0)
2552 return ((cpuid
[0] >> 8) & 0xf) == 0xf;
2557 // ************** Pentium/P4 optimizations ***************
2559 class PentiumOptimized
: public Portable
2562 static word CRYPTOPP_CDECL
Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2563 static word CRYPTOPP_CDECL
Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2564 static void CRYPTOPP_CDECL
Multiply4(word
*C
, const word
*A
, const word
*B
);
2565 static void CRYPTOPP_CDECL
Multiply8(word
*C
, const word
*A
, const word
*B
);
2566 static void CRYPTOPP_CDECL
Multiply8Bottom(word
*C
, const word
*A
, const word
*B
);
2572 static word CRYPTOPP_CDECL
Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2573 static word CRYPTOPP_CDECL
Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2576 typedef word (CRYPTOPP_CDECL
* PAddSub
)(word
*C
, const word
*A
, const word
*B
, unsigned int N
);
2577 typedef void (CRYPTOPP_CDECL
* PMul
)(word
*C
, const word
*A
, const word
*B
);
2579 static PAddSub s_pAdd
, s_pSub
;
2580 #ifdef SSE2_INTRINSICS_AVAILABLE
2581 static PMul s_pMul4
, s_pMul8
, s_pMul8B
;
2584 static void SetPentiumFunctionPointers()
2588 s_pAdd
= &P4Optimized::Add
;
2589 s_pSub
= &P4Optimized::Subtract
;
2593 s_pAdd
= &PentiumOptimized::Add
;
2594 s_pSub
= &PentiumOptimized::Subtract
;
2597 #ifdef SSE2_INTRINSICS_AVAILABLE
2598 s_pMul4
= &PentiumOptimized::Multiply4
;
2599 s_pMul8
= &PentiumOptimized::Multiply8
;
2600 s_pMul8B
= &PentiumOptimized::Multiply8Bottom
;
2604 static const char s_RunAtStartupSetPentiumFunctionPointers
= (SetPentiumFunctionPointers(), 0);
2606 class LowLevel
: public PentiumOptimized
2609 inline static word
Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2610 {return s_pAdd(C
, A
, B
, N
);}
2611 inline static word
Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2612 {return s_pSub(C
, A
, B
, N
);}
2613 inline static void Square4(word
*R
, const word
*A
)
2614 {Multiply4(R
, A
, A
);}
2615 #ifdef SSE2_INTRINSICS_AVAILABLE
2616 inline static void Multiply4(word
*C
, const word
*A
, const word
*B
)
2618 inline static void Multiply8(word
*C
, const word
*A
, const word
*B
)
2620 inline static void Multiply8Bottom(word
*C
, const word
*A
, const word
*B
)
2621 {s_pMul8B(C
, A
, B
);}
2625 // use some tricks to share assembly code between MSVC and GCC
2627 #define CRYPTOPP_NAKED __declspec(naked)
2628 #define AS1(x) __asm x
2629 #define AS2(x, y) __asm x, y
2630 #define AddPrologue \
2635 __asm mov ecx, [esp+20] \
2636 __asm mov edx, [esp+24] \
2637 __asm mov ebx, [esp+28] \
2638 __asm mov esi, [esp+32]
2639 #define AddEpilogue \
2645 #define MulPrologue \
2650 __asm mov ecx, [esp+28] \
2651 __asm mov esi, [esp+24] \
2653 #define MulEpilogue \
2661 #define CRYPTOPP_NAKED
2662 #define AS1(x) #x ";"
2663 #define AS2(x, y) #x ", " #y ";"
2664 #define AddPrologue \
2665 __asm__ __volatile__ \
2667 "push %%ebx;" /* save this manually, in case of -fPIC */ \
2669 ".intel_syntax noprefix;" \
2671 #define AddEpilogue \
2673 ".att_syntax prefix;" \
2676 : "c" (C), "d" (A), "m" (B), "S" (N) \
2677 : "%edi", "memory", "cc" \
2679 #define MulPrologue \
2680 __asm__ __volatile__ \
2682 "push %%ebx;" /* save this manually, in case of -fPIC */ \
2685 ".intel_syntax noprefix;"
2686 #define MulEpilogue \
2690 ".att_syntax prefix;" \
2692 : "rm" (Z), "S" (X), "c" (Y) \
2693 : "%eax", "%edx", "%edi", "memory", "cc" \
2697 CRYPTOPP_NAKED word
PentiumOptimized::Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2701 // now: ebx = B, ecx = C, edx = A, esi = N
2702 AS2( sub ecx
, edx
) // hold the distance between C & A so we can add this to A to get C
2703 AS2( xor eax
, eax
) // clear eax
2705 AS2( sub eax
, esi
) // eax is a negative index from end of B
2706 AS2( lea ebx
, [ebx
+4*esi
]) // ebx is end of B
2708 AS2( sar eax
, 1) // unit of eax is now dwords; this also clears the carry flag
2709 AS1( jz loopendAdd
) // if no dwords then nothing to do
2712 AS2( mov esi
,[edx
]) // load lower word of A
2713 AS2( mov ebp
,[edx
+4]) // load higher word of A
2715 AS2( mov edi
,[ebx
+8*eax
]) // load lower word of B
2716 AS2( lea edx
,[edx
+8]) // advance A and C
2718 AS2( adc esi
,edi
) // add lower words
2719 AS2( mov edi
,[ebx
+8*eax
+4]) // load higher word of B
2721 AS2( adc ebp
,edi
) // add higher words
2722 AS1( inc eax
) // advance B
2724 AS2( mov
[edx
+ecx
-8],esi
) // store lower word result
2725 AS2( mov
[edx
+ecx
-4],ebp
) // store higher word result
2727 AS1( jnz loopstartAdd
) // loop until eax overflows and becomes zero
2730 AS2( adc eax
, 0) // store carry into eax (return result register)
2734 // Just to get rid of warnings
2738 CRYPTOPP_NAKED word
PentiumOptimized::Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2742 // now: ebx = B, ecx = C, edx = A, esi = N
2743 AS2( sub ecx
, edx
) // hold the distance between C & A so we can add this to A to get C
2744 AS2( xor eax
, eax
) // clear eax
2746 AS2( sub eax
, esi
) // eax is a negative index from end of B
2747 AS2( lea ebx
, [ebx
+4*esi
]) // ebx is end of B
2749 AS2( sar eax
, 1) // unit of eax is now dwords; this also clears the carry flag
2750 AS1( jz loopendSub
) // if no dwords then nothing to do
2753 AS2( mov esi
,[edx
]) // load lower word of A
2754 AS2( mov ebp
,[edx
+4]) // load higher word of A
2756 AS2( mov edi
,[ebx
+8*eax
]) // load lower word of B
2757 AS2( lea edx
,[edx
+8]) // advance A and C
2759 AS2( sbb esi
,edi
) // subtract lower words
2760 AS2( mov edi
,[ebx
+8*eax
+4]) // load higher word of B
2762 AS2( sbb ebp
,edi
) // subtract higher words
2763 AS1( inc eax
) // advance B
2765 AS2( mov
[edx
+ecx
-8],esi
) // store lower word result
2766 AS2( mov
[edx
+ecx
-4],ebp
) // store higher word result
2768 AS1( jnz loopstartSub
) // loop until eax overflows and becomes zero
2771 AS2( adc eax
, 0) // store carry into eax (return result register)
2775 // Just to get rid of warnings
2779 // On Pentium 4, the adc and sbb instructions are very expensive, so avoid them.
2781 CRYPTOPP_NAKED word
P4Optimized::Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2785 // now: ebx = B, ecx = C, edx = A, esi = N
2788 AS1( jz loopendAddP4
) // if no dwords then nothing to do
2790 AS2( mov edi
, [edx
])
2791 AS2( mov ebp
, [ebx
])
2792 AS1( jmp carry1AddP4
)
2794 AS1(loopstartAddP4
:)
2795 AS2( mov edi
, [edx
+8])
2798 AS2( mov ebp
, [ebx
])
2800 AS1( jc carry1AddP4
)
2806 AS2( mov
[ecx
], edi
)
2807 AS2( mov edi
, [edx
+4])
2808 AS2( cmovc eax
, ebp
)
2809 AS2( mov ebp
, [ebx
+4])
2812 AS1( jc carry2AddP4
)
2818 AS2( cmovc eax
, ebp
)
2819 AS2( mov
[ecx
+4], edi
)
2821 AS1( jnz loopstartAddP4
)
2827 // Just to get rid of warnings
2831 CRYPTOPP_NAKED word
P4Optimized::Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
2835 // now: ebx = B, ecx = C, edx = A, esi = N
2838 AS1( jz loopendSubP4
) // if no dwords then nothing to do
2840 AS2( mov edi
, [edx
])
2841 AS2( mov ebp
, [ebx
])
2842 AS1( jmp carry1SubP4
)
2844 AS1(loopstartSubP4
:)
2845 AS2( mov edi
, [edx
+8])
2848 AS2( mov ebp
, [ebx
])
2850 AS1( jc carry1SubP4
)
2856 AS2( mov
[ecx
], edi
)
2857 AS2( mov edi
, [edx
+4])
2858 AS2( cmovc eax
, ebp
)
2859 AS2( mov ebp
, [ebx
+4])
2862 AS1( jc carry2SubP4
)
2868 AS2( cmovc eax
, ebp
)
2869 AS2( mov
[ecx
+4], edi
)
2871 AS1( jnz loopstartSubP4
)
2877 // Just to get rid of warnings
2881 // multiply assembly code originally contributed by Leonard Janke
2883 #define MulStartup \
2888 #define MulShiftCarry \
2893 #define MulAccumulateBottom(i,j) \
2894 AS2(mov eax, [ecx+4*j]) \
2895 AS2(imul eax, dword ptr [esi+4*i]) \
2898 #define MulAccumulate(i,j) \
2899 AS2(mov eax, [ecx+4*j]) \
2900 AS1(mul dword ptr [esi+4*i]) \
2905 #define MulStoreDigit(i) \
2907 AS2(mov edi, [esp]) \
2908 AS2(mov [edi+4*i], ebp)
2910 #define MulLastDiagonal(digits) \
2911 AS2(mov eax, [ecx+4*(digits-1)]) \
2912 AS1(mul dword ptr [esi+4*(digits-1)]) \
2915 AS2(mov edi, [esp]) \
2916 AS2(mov [edi+4*(2*digits-2)], ebp) \
2917 AS2(mov [edi+4*(2*digits-1)], edx)
2919 CRYPTOPP_NAKED
void PentiumOptimized::Multiply4(word
* Z
, const word
* X
, const word
* Y
)
2922 // now: [esp] = Z, esi = X, ecx = Y
2961 CRYPTOPP_NAKED
void PentiumOptimized::Multiply8(word
* Z
, const word
* X
, const word
* Y
)
2964 // now: [esp] = Z, esi = X, ecx = Y
3075 CRYPTOPP_NAKED
void PentiumOptimized::Multiply8Bottom(word
* Z
, const word
* X
, const word
* Y
)
3078 // now: [esp] = Z, esi = X, ecx = Y
3129 MulAccumulateBottom(7,0)
3130 MulAccumulateBottom(6,1)
3131 MulAccumulateBottom(5,2)
3132 MulAccumulateBottom(4,3)
3133 MulAccumulateBottom(3,4)
3134 MulAccumulateBottom(2,5)
3135 MulAccumulateBottom(1,6)
3136 MulAccumulateBottom(0,7)
3144 #else // not x86 - no processor specific code at this layer
3146 typedef Portable LowLevel
;
3150 #ifdef SSE2_INTRINSICS_AVAILABLE
3153 #define CRYPTOPP_FASTCALL
3155 #define CRYPTOPP_FASTCALL __fastcall
3158 static void CRYPTOPP_FASTCALL
P4_Mul(__m128i
*C
, const __m128i
*A
, const __m128i
*B
)
3160 __m128i a3210
= _mm_load_si128(A
);
3161 __m128i b3210
= _mm_load_si128(B
);
3165 __m128i z
= _mm_setzero_si128();
3166 __m128i a2b2_a0b0
= _mm_mul_epu32(a3210
, b3210
);
3169 __m128i a3120
= _mm_shuffle_epi32(a3210
, _MM_SHUFFLE(3, 1, 2, 0));
3170 __m128i b3021
= _mm_shuffle_epi32(b3210
, _MM_SHUFFLE(3, 0, 2, 1));
3171 __m128i a1b0_a0b1
= _mm_mul_epu32(a3120
, b3021
);
3172 __m128i a1b0
= _mm_unpackhi_epi32(a1b0_a0b1
, z
);
3173 __m128i a0b1
= _mm_unpacklo_epi32(a1b0_a0b1
, z
);
3174 C
[1] = _mm_add_epi64(a1b0
, a0b1
);
3176 __m128i a31
= _mm_srli_epi64(a3210
, 32);
3177 __m128i b31
= _mm_srli_epi64(b3210
, 32);
3178 __m128i a3b3_a1b1
= _mm_mul_epu32(a31
, b31
);
3181 __m128i a1b1
= _mm_unpacklo_epi32(a3b3_a1b1
, z
);
3182 __m128i b3012
= _mm_shuffle_epi32(b3210
, _MM_SHUFFLE(3, 0, 1, 2));
3183 __m128i a2b0_a0b2
= _mm_mul_epu32(a3210
, b3012
);
3184 __m128i a0b2
= _mm_unpacklo_epi32(a2b0_a0b2
, z
);
3185 __m128i a2b0
= _mm_unpackhi_epi32(a2b0_a0b2
, z
);
3186 sum
= _mm_add_epi64(a1b1
, a0b2
);
3187 C
[2] = _mm_add_epi64(sum
, a2b0
);
3189 __m128i a2301
= _mm_shuffle_epi32(a3210
, _MM_SHUFFLE(2, 3, 0, 1));
3190 __m128i b2103
= _mm_shuffle_epi32(b3210
, _MM_SHUFFLE(2, 1, 0, 3));
3191 __m128i a3b0_a1b2
= _mm_mul_epu32(a2301
, b3012
);
3192 __m128i a2b1_a0b3
= _mm_mul_epu32(a3210
, b2103
);
3193 __m128i a3b0
= _mm_unpackhi_epi32(a3b0_a1b2
, z
);
3194 __m128i a1b2
= _mm_unpacklo_epi32(a3b0_a1b2
, z
);
3195 __m128i a2b1
= _mm_unpackhi_epi32(a2b1_a0b3
, z
);
3196 __m128i a0b3
= _mm_unpacklo_epi32(a2b1_a0b3
, z
);
3197 __m128i sum1
= _mm_add_epi64(a3b0
, a1b2
);
3198 sum
= _mm_add_epi64(a2b1
, a0b3
);
3199 C
[3] = _mm_add_epi64(sum
, sum1
);
3201 __m128i a3b1_a1b3
= _mm_mul_epu32(a2301
, b2103
);
3202 __m128i a2b2
= _mm_unpackhi_epi32(a2b2_a0b0
, z
);
3203 __m128i a3b1
= _mm_unpackhi_epi32(a3b1_a1b3
, z
);
3204 __m128i a1b3
= _mm_unpacklo_epi32(a3b1_a1b3
, z
);
3205 sum
= _mm_add_epi64(a2b2
, a3b1
);
3206 C
[4] = _mm_add_epi64(sum
, a1b3
);
3208 __m128i a1302
= _mm_shuffle_epi32(a3210
, _MM_SHUFFLE(1, 3, 0, 2));
3209 __m128i b1203
= _mm_shuffle_epi32(b3210
, _MM_SHUFFLE(1, 2, 0, 3));
3210 __m128i a3b2_a2b3
= _mm_mul_epu32(a1302
, b1203
);
3211 __m128i a3b2
= _mm_unpackhi_epi32(a3b2_a2b3
, z
);
3212 __m128i a2b3
= _mm_unpacklo_epi32(a3b2_a2b3
, z
);
3213 C
[5] = _mm_add_epi64(a3b2
, a2b3
);
3216 #endif // #ifdef SSE2_INTRINSICS_AVAILABLE
3218 // ********************************************************
3235 // R[2*N] - result = A*B
3236 // T[2*N] - temporary work space
3237 // A[N] --- multiplier
3238 // B[N] --- multiplicant
3240 void RecursiveMultiply(word
*R
, word
*T
, const word
*A
, const word
*B
, unsigned int N
)
3242 assert(N
>=2 && N
%2==0);
3244 if (LowLevel::MultiplyRecursionLimit() >= 8 && N
==8)
3245 LowLevel::Multiply8(R
, A
, B
);
3246 else if (LowLevel::MultiplyRecursionLimit() >= 4 && N
==4)
3247 LowLevel::Multiply4(R
, A
, B
);
3249 LowLevel::Multiply2(R
, A
, B
);
3252 const unsigned int N2
= N
/2;
3255 int aComp
= Compare(A0
, A1
, N2
);
3256 int bComp
= Compare(B0
, B1
, N2
);
3258 switch (2*aComp
+ aComp
+ bComp
)
3261 LowLevel::Subtract(R0
, A1
, A0
, N2
);
3262 LowLevel::Subtract(R1
, B0
, B1
, N2
);
3263 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3264 LowLevel::Subtract(T1
, T1
, R0
, N2
);
3268 LowLevel::Subtract(R0
, A1
, A0
, N2
);
3269 LowLevel::Subtract(R1
, B0
, B1
, N2
);
3270 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3274 LowLevel::Subtract(R0
, A0
, A1
, N2
);
3275 LowLevel::Subtract(R1
, B1
, B0
, N2
);
3276 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3280 LowLevel::Subtract(R0
, A1
, A0
, N2
);
3281 LowLevel::Subtract(R1
, B0
, B1
, N2
);
3282 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3283 LowLevel::Subtract(T1
, T1
, R1
, N2
);
3291 RecursiveMultiply(R0
, T2
, A0
, B0
, N2
);
3292 RecursiveMultiply(R2
, T2
, A1
, B1
, N2
);
3294 // now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1
3296 carry
+= LowLevel::Add(T0
, T0
, R0
, N
);
3297 carry
+= LowLevel::Add(T0
, T0
, R2
, N
);
3298 carry
+= LowLevel::Add(R1
, R1
, T0
, N
);
3300 assert (carry
>= 0 && carry
<= 2);
3301 Increment(R3
, N2
, carry
);
3305 // R[2*N] - result = A*A
3306 // T[2*N] - temporary work space
3307 // A[N] --- number to be squared
3309 void RecursiveSquare(word
*R
, word
*T
, const word
*A
, unsigned int N
)
3311 assert(N
&& N
%2==0);
3312 if (LowLevel::SquareRecursionLimit() >= 8 && N
==8)
3313 LowLevel::Square8(R
, A
);
3314 if (LowLevel::SquareRecursionLimit() >= 4 && N
==4)
3315 LowLevel::Square4(R
, A
);
3317 LowLevel::Square2(R
, A
);
3320 const unsigned int N2
= N
/2;
3322 RecursiveSquare(R0
, T2
, A0
, N2
);
3323 RecursiveSquare(R2
, T2
, A1
, N2
);
3324 RecursiveMultiply(T0
, T2
, A0
, A1
, N2
);
3326 word carry
= LowLevel::Add(R1
, R1
, T0
, N
);
3327 carry
+= LowLevel::Add(R1
, R1
, T0
, N
);
3328 Increment(R3
, N2
, carry
);
3332 // R[N] - bottom half of A*B
3333 // T[N] - temporary work space
3334 // A[N] - multiplier
3335 // B[N] - multiplicant
3337 void RecursiveMultiplyBottom(word
*R
, word
*T
, const word
*A
, const word
*B
, unsigned int N
)
3339 assert(N
>=2 && N
%2==0);
3340 if (LowLevel::MultiplyBottomRecursionLimit() >= 8 && N
==8)
3341 LowLevel::Multiply8Bottom(R
, A
, B
);
3342 else if (LowLevel::MultiplyBottomRecursionLimit() >= 4 && N
==4)
3343 LowLevel::Multiply4Bottom(R
, A
, B
);
3345 LowLevel::Multiply2Bottom(R
, A
, B
);
3348 const unsigned int N2
= N
/2;
3350 RecursiveMultiply(R
, T
, A0
, B0
, N2
);
3351 RecursiveMultiplyBottom(T0
, T1
, A1
, B0
, N2
);
3352 LowLevel::Add(R1
, R1
, T0
, N2
);
3353 RecursiveMultiplyBottom(T0
, T1
, A0
, B1
, N2
);
3354 LowLevel::Add(R1
, R1
, T0
, N2
);
3358 // R[N] --- upper half of A*B
3359 // T[2*N] - temporary work space
3360 // L[N] --- lower half of A*B
3361 // A[N] --- multiplier
3362 // B[N] --- multiplicant
3364 void RecursiveMultiplyTop(word
*R
, word
*T
, const word
*L
, const word
*A
, const word
*B
, unsigned int N
)
3366 assert(N
>=2 && N
%2==0);
3370 LowLevel::Multiply4(T
, A
, B
);
3371 memcpy(R
, T
+4, 4*WORD_SIZE
);
3375 LowLevel::Multiply2(T
, A
, B
);
3376 memcpy(R
, T
+2, 2*WORD_SIZE
);
3380 const unsigned int N2
= N
/2;
3383 int aComp
= Compare(A0
, A1
, N2
);
3384 int bComp
= Compare(B0
, B1
, N2
);
3386 switch (2*aComp
+ aComp
+ bComp
)
3389 LowLevel::Subtract(R0
, A1
, A0
, N2
);
3390 LowLevel::Subtract(R1
, B0
, B1
, N2
);
3391 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3392 LowLevel::Subtract(T1
, T1
, R0
, N2
);
3396 LowLevel::Subtract(R0
, A1
, A0
, N2
);
3397 LowLevel::Subtract(R1
, B0
, B1
, N2
);
3398 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3402 LowLevel::Subtract(R0
, A0
, A1
, N2
);
3403 LowLevel::Subtract(R1
, B1
, B0
, N2
);
3404 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3408 LowLevel::Subtract(R0
, A1
, A0
, N2
);
3409 LowLevel::Subtract(R1
, B0
, B1
, N2
);
3410 RecursiveMultiply(T0
, T2
, R0
, R1
, N2
);
3411 LowLevel::Subtract(T1
, T1
, R1
, N2
);
3419 RecursiveMultiply(T2
, R0
, A1
, B1
, N2
);
3421 // now T[01] holds (A1-A0)*(B0-B1), T[23] holds A1*B1
3423 word c2
= LowLevel::Subtract(R0
, L
+N2
, L
, N2
);
3424 c2
+= LowLevel::Subtract(R0
, R0
, T0
, N2
);
3425 word t
= (Compare(R0
, T2
, N2
) == -1);
3428 carry
+= Increment(R0
, N2
, c2
+t
);
3429 carry
+= LowLevel::Add(R0
, R0
, T1
, N2
);
3430 carry
+= LowLevel::Add(R0
, R0
, T3
, N2
);
3431 assert (carry
>= 0 && carry
<= 2);
3433 CopyWords(R1
, T3
, N2
);
3434 Increment(R1
, N2
, carry
);
3438 inline word
Add(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
3440 return LowLevel::Add(C
, A
, B
, N
);
3443 inline word
Subtract(word
*C
, const word
*A
, const word
*B
, unsigned int N
)
3445 return LowLevel::Subtract(C
, A
, B
, N
);
3448 inline void Multiply(word
*R
, word
*T
, const word
*A
, const word
*B
, unsigned int N
)
3450 RecursiveMultiply(R
, T
, A
, B
, N
);
3453 inline void Square(word
*R
, word
*T
, const word
*A
, unsigned int N
)
3455 RecursiveSquare(R
, T
, A
, N
);
3458 inline void MultiplyBottom(word
*R
, word
*T
, const word
*A
, const word
*B
, unsigned int N
)
3460 RecursiveMultiplyBottom(R
, T
, A
, B
, N
);
3463 inline void MultiplyTop(word
*R
, word
*T
, const word
*L
, const word
*A
, const word
*B
, unsigned int N
)
3465 RecursiveMultiplyTop(R
, T
, L
, A
, B
, N
);
3468 static word
LinearMultiply(word
*C
, const word
*A
, word B
, unsigned int N
)
3471 for(unsigned i
=0; i
<N
; i
++)
3473 DWord p
= DWord::MultiplyAndAdd(A
[i
], B
, carry
);
3474 C
[i
] = p
.GetLowHalf();
3475 carry
= p
.GetHighHalf();
3480 // R[NA+NB] - result = A*B
3481 // T[NA+NB] - temporary work space
3482 // A[NA] ---- multiplier
3483 // B[NB] ---- multiplicant
3485 void AsymmetricMultiply(word
*R
, word
*T
, const word
*A
, unsigned int NA
, const word
*B
, unsigned int NB
)
3490 Square(R
, T
, A
, NA
);
3492 Multiply(R
, T
, A
, B
, NA
);
3503 assert(NB
% NA
== 0);
3504 assert((NB
/NA
)%2 == 0); // NB is an even multiple of NA
3511 SetWords(R
, 0, NB
+2);
3514 CopyWords(R
, B
, NB
);
3515 R
[NB
] = R
[NB
+1] = 0;
3518 R
[NB
] = LinearMultiply(R
, B
, A
[0], NB
);
3524 Multiply(R
, T
, A
, B
, NA
);
3525 CopyWords(T
+2*NA
, R
+NA
, NA
);
3529 for (i
=2*NA
; i
<NB
; i
+=2*NA
)
3530 Multiply(T
+NA
+i
, T
, A
, B
+i
, NA
);
3531 for (i
=NA
; i
<NB
; i
+=2*NA
)
3532 Multiply(R
+i
, T
, A
, B
+i
, NA
);
3534 if (Add(R
+NA
, R
+NA
, T
+2*NA
, NB
-NA
))
3535 Increment(R
+NB
, NA
);
3538 // R[N] ----- result = A inverse mod 2**(WORD_BITS*N)
3539 // T[3*N/2] - temporary work space
3540 // A[N] ----- an odd number as input
3542 void RecursiveInverseModPower2(word
*R
, word
*T
, const word
*A
, unsigned int N
)
3546 T
[0] = AtomicInverseModPower2(A
[0]);
3548 LowLevel::Multiply2Bottom(T
+2, T
, A
);
3549 TwosComplement(T
+2, 2);
3550 Increment(T
+2, 2, 2);
3551 LowLevel::Multiply2Bottom(R
, T
, T
+2);
3555 const unsigned int N2
= N
/2;
3556 RecursiveInverseModPower2(R0
, T0
, A0
, N2
);
3558 SetWords(T0
+1, 0, N2
-1);
3559 MultiplyTop(R1
, T1
, T0
, R0
, A0
, N2
);
3560 MultiplyBottom(T0
, T1
, R0
, A1
, N2
);
3561 Add(T0
, R1
, T0
, N2
);
3562 TwosComplement(T0
, N2
);
3563 MultiplyBottom(R1
, T1
, R0
, T0
, N2
);
3567 // R[N] --- result = X/(2**(WORD_BITS*N)) mod M
3568 // T[3*N] - temporary work space
3569 // X[2*N] - number to be reduced
3571 // U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)
3573 void MontgomeryReduce(word
*R
, word
*T
, const word
*X
, const word
*M
, const word
*U
, unsigned int N
)
3575 MultiplyBottom(R
, T
, X
, U
, N
);
3576 MultiplyTop(T
, T
+N
, X
, R
, M
, N
);
3577 word borrow
= Subtract(T
, X
+N
, T
, N
);
3578 // defend against timing attack by doing this Add even when not needed
3579 word carry
= Add(T
+N
, T
, M
, N
);
3580 assert(carry
|| !borrow
);
3581 CopyWords(R
, T
+ (borrow
? N
: 0), N
);
3584 // R[N] --- result = X/(2**(WORD_BITS*N/2)) mod M
3585 // T[2*N] - temporary work space
3586 // X[2*N] - number to be reduced
3588 // U[N/2] - multiplicative inverse of M mod 2**(WORD_BITS*N/2)
3589 // V[N] --- 2**(WORD_BITS*3*N/2) mod M
3591 void HalfMontgomeryReduce(word
*R
, word
*T
, const word
*X
, const word
*M
, const word
*U
, const word
*V
, unsigned int N
)
3593 assert(N
%2==0 && N
>=4);
3605 const unsigned int N2
= N
/2;
3606 Multiply(T0
, T2
, V0
, X3
, N2
);
3607 int c2
= Add(T0
, T0
, X0
, N
);
3608 MultiplyBottom(T3
, T2
, T0
, U
, N2
);
3609 MultiplyTop(T2
, R
, T0
, T3
, M0
, N2
);
3610 c2
-= Subtract(T2
, T1
, T2
, N2
);
3611 Multiply(T0
, R
, T3
, M1
, N2
);
3612 c2
-= Subtract(T0
, T2
, T0
, N2
);
3613 int c3
= -(int)Subtract(T1
, X2
, T1
, N2
);
3614 Multiply(R0
, T2
, V1
, X3
, N2
);
3615 c3
+= Add(R
, R
, T
, N
);
3618 c3
+= Increment(R1
, N2
);
3620 c3
-= Decrement(R1
, N2
, -c2
);
3622 assert(c3
>=-1 && c3
<=1);
3624 Subtract(R
, R
, M
, N
);
3654 static inline void AtomicDivide(word
*Q
, const word
*A
, const word
*B
)
3657 DWord q
= DivideFourWordsByTwo
<word
, DWord
>(T
, DWord(A
[0], A
[1]), DWord(A
[2], A
[3]), DWord(B
[0], B
[1]));
3658 Q
[0] = q
.GetLowHalf();
3659 Q
[1] = q
.GetHighHalf();
3662 // for use by Divide(), corrects the underestimated quotient {Q1,Q0}
3663 static void CorrectQuotientEstimate(word
*R
, word
*T
, word
*Q
, const word
*B
, unsigned int N
)
3665 assert(N
&& N
%2==0);
3671 for (i
=0; i
<N
; i
+=4)
3672 LowLevel::Multiply2(T
+i
, Q
, B
+i
);
3673 for (i
=2; i
<N
; i
+=4)
3674 if (LowLevel::Multiply2Add(T
+i
, Q
, B
+i
))
3675 T
[i
+5] += (++T
[i
+4]==0);
3679 T
[N
] = LinearMultiply(T
, B
, Q
[0], N
);
3683 word borrow
= Subtract(R
, R
, T
, N
+2);
3684 assert(!borrow
&& !R
[N
+1]);
3686 while (R
[N
] || Compare(R
, B
, N
) >= 0)
3688 R
[N
] -= Subtract(R
, R
, B
, N
);
3689 Q
[1] += (++Q
[0]==0);
3690 assert(Q
[0] || Q
[1]); // no overflow
3694 // R[NB] -------- remainder = A%B
3695 // Q[NA-NB+2] --- quotient = A/B
3696 // T[NA+2*NB+4] - temp work space
3697 // A[NA] -------- dividend
3698 // B[NB] -------- divisor
3700 void Divide(word
*R
, word
*Q
, word
*T
, const word
*A
, unsigned int NA
, const word
*B
, unsigned int NB
)
3702 assert(NA
&& NB
&& NA
%2==0 && NB
%2==0);
3703 assert(B
[NB
-1] || B
[NB
-2]);
3706 // set up temporary work space
3708 word
*const TB
=T
+NA
+2;
3709 word
*const TP
=T
+NA
+2+NB
;
3711 // copy B into TB and normalize it so that TB has highest bit set to 1
3712 unsigned shiftWords
= (B
[NB
-1]==0);
3713 TB
[0] = TB
[NB
-1] = 0;
3714 CopyWords(TB
+shiftWords
, B
, NB
-shiftWords
);
3715 unsigned shiftBits
= WORD_BITS
- BitPrecision(TB
[NB
-1]);
3716 assert(shiftBits
< WORD_BITS
);
3717 ShiftWordsLeftByBits(TB
, NB
, shiftBits
);
3719 // copy A into TA and normalize it
3720 TA
[0] = TA
[NA
] = TA
[NA
+1] = 0;
3721 CopyWords(TA
+shiftWords
, A
, NA
);
3722 ShiftWordsLeftByBits(TA
, NA
+2, shiftBits
);
3724 if (TA
[NA
+1]==0 && TA
[NA
] <= 1)
3726 Q
[NA
-NB
+1] = Q
[NA
-NB
] = 0;
3727 while (TA
[NA
] || Compare(TA
+NA
-NB
, TB
, NB
) >= 0)
3729 TA
[NA
] -= Subtract(TA
+NA
-NB
, TA
+NA
-NB
, TB
, NB
);
3736 assert(Compare(TA
+NA
-NB
, TB
, NB
) < 0);
3740 BT
[0] = TB
[NB
-2] + 1;
3741 BT
[1] = TB
[NB
-1] + (BT
[0]==0);
3743 // start reducing TA mod TB, 2 words at a time
3744 for (unsigned i
=NA
-2; i
>=NB
; i
-=2)
3746 AtomicDivide(Q
+i
-NB
, TA
+i
-2, BT
);
3747 CorrectQuotientEstimate(TA
+i
-NB
, TP
, Q
+i
-NB
, TB
, NB
);
3750 // copy TA into R, and denormalize it
3751 CopyWords(R
, TA
+shiftWords
, NB
);
3752 ShiftWordsRightByBits(R
, NB
, shiftBits
);
3755 static inline unsigned int EvenWordCount(const word
*X
, unsigned int N
)
3757 while (N
&& X
[N
-2]==0 && X
[N
-1]==0)
3763 // R[N] --- result = A^(-1) * 2^k mod M
3764 // T[4*N] - temporary work space
3765 // A[NA] -- number to take inverse of
3768 unsigned int AlmostInverse(word
*R
, word
*T
, const word
*A
, unsigned int NA
, const word
*M
, unsigned int N
)
3770 assert(NA
<=N
&& N
&& N
%2==0);
3776 unsigned int bcLen
=2, fgLen
=EvenWordCount(M
, N
);
3777 unsigned int k
=0, s
=0;
3779 SetWords(T
, 0, 3*N
);
3781 CopyWords(f
, A
, NA
);
3789 if (EvenWordCount(f
, fgLen
)==0)
3795 ShiftWordsRightByWords(f
, fgLen
, 1);
3796 if (c
[bcLen
-1]) bcLen
+=2;
3798 ShiftWordsLeftByWords(c
, bcLen
, 1);
3811 if (t
==1 && f
[1]==0 && EvenWordCount(f
, fgLen
)==2)
3816 Subtract(R
, M
, b
, N
);
3820 ShiftWordsRightByBits(f
, fgLen
, i
);
3821 t
=ShiftWordsLeftByBits(c
, bcLen
, i
);
3829 if (f
[fgLen
-2]==0 && g
[fgLen
-2]==0 && f
[fgLen
-1]==0 && g
[fgLen
-1]==0)
3832 if (Compare(f
, g
, fgLen
)==-1)
3839 Subtract(f
, f
, g
, fgLen
);
3841 if (Add(b
, b
, c
, bcLen
))
3850 // R[N] - result = A/(2^k) mod M
3854 void DivideByPower2Mod(word
*R
, const word
*A
, unsigned int k
, const word
*M
, unsigned int N
)
3861 ShiftWordsRightByBits(R
, N
, 1);
3864 word carry
= Add(R
, R
, M
, N
);
3865 ShiftWordsRightByBits(R
, N
, 1);
3866 R
[N
-1] += carry
<<(WORD_BITS
-1);
3871 // R[N] - result = A*(2^k) mod M
3875 void MultiplyByPower2Mod(word
*R
, const word
*A
, unsigned int k
, const word
*M
, unsigned int N
)
3880 if (ShiftWordsLeftByBits(R
, N
, 1) || Compare(R
, M
, N
)>=0)
3881 Subtract(R
, R
, M
, N
);
3884 // ******************************************************************
3886 static const unsigned int RoundupSizeTable
[] = {2, 2, 2, 4, 4, 8, 8, 8, 8};
3888 static inline unsigned int RoundupSize(unsigned int n
)
3891 return RoundupSizeTable
[n
];
3898 else return 1U << BitPrecision(n
-1);
3902 : reg(2), sign(POSITIVE
)
3904 reg
[0] = reg
[1] = 0;
3907 Integer::Integer(const Integer
& t
)
3908 : ASN1Object(), reg(RoundupSize(t
.WordCount())), sign(t
.sign
)
3910 CopyWords(reg
, t
.reg
, reg
.size());
3913 Integer::Integer(Sign s
, lword value
)
3916 reg
[0] = word(value
);
3917 reg
[1] = word(SafeRightShift
<WORD_BITS
>(value
));
3920 Integer::Integer(signed long value
)
3930 reg
[0] = word(value
);
3931 reg
[1] = word(SafeRightShift
<WORD_BITS
>((unsigned long)value
));
3934 Integer::Integer(Sign s
, word high
, word low
)
3941 bool Integer::IsConvertableToLong() const
3943 if (ByteCount() > sizeof(long))
3946 unsigned long value
= reg
[0];
3947 value
+= SafeLeftShift
<WORD_BITS
, unsigned long>(reg
[1]);
3950 return (signed long)value
>= 0;
3952 return -(signed long)value
< 0;
3955 signed long Integer::ConvertToLong() const
3957 assert(IsConvertableToLong());
3959 unsigned long value
= reg
[0];
3960 value
+= SafeLeftShift
<WORD_BITS
, unsigned long>(reg
[1]);
3961 return sign
==POSITIVE
? value
: -(signed long)value
;
3964 Integer::Integer(BufferedTransformation
&encodedInteger
, unsigned int byteCount
, Signedness s
)
3966 Decode(encodedInteger
, byteCount
, s
);
3969 Integer::Integer(const byte
*encodedInteger
, unsigned int byteCount
, Signedness s
)
3971 Decode(encodedInteger
, byteCount
, s
);
3974 Integer::Integer(BufferedTransformation
&bt
)
3979 Integer::Integer(RandomNumberGenerator
&rng
, unsigned int bitcount
)
3981 Randomize(rng
, bitcount
);
3984 Integer::Integer(RandomNumberGenerator
&rng
, const Integer
&min
, const Integer
&max
, RandomNumberType rnType
, const Integer
&equiv
, const Integer
&mod
)
3986 if (!Randomize(rng
, min
, max
, rnType
, equiv
, mod
))
3987 throw Integer::RandomNumberNotFound();
3990 Integer
Integer::Power2(unsigned int e
)
3992 Integer
r((word
)0, BitsToWords(e
+1));
4000 Integer
* operator()() const
4002 return new Integer(i
);
4006 const Integer
&Integer::Zero()
4008 return Singleton
<Integer
>().Ref();
4011 const Integer
&Integer::One()
4013 return Singleton
<Integer
, NewInteger
<1> >().Ref();
4016 const Integer
&Integer::Two()
4018 return Singleton
<Integer
, NewInteger
<2> >().Ref();
4021 bool Integer::operator!() const
4023 return IsNegative() ? false : (reg
[0]==0 && WordCount()==0);
4026 Integer
& Integer::operator=(const Integer
& t
)
4030 reg
.New(RoundupSize(t
.WordCount()));
4031 CopyWords(reg
, t
.reg
, reg
.size());
4037 bool Integer::GetBit(unsigned int n
) const
4039 if (n
/WORD_BITS
>= reg
.size())
4042 return bool((reg
[n
/WORD_BITS
] >> (n
% WORD_BITS
)) & 1);
4045 void Integer::SetBit(unsigned int n
, bool value
)
4049 reg
.CleanGrow(RoundupSize(BitsToWords(n
+1)));
4050 reg
[n
/WORD_BITS
] |= (word(1) << (n
%WORD_BITS
));
4054 if (n
/WORD_BITS
< reg
.size())
4055 reg
[n
/WORD_BITS
] &= ~(word(1) << (n
%WORD_BITS
));
4059 byte
Integer::GetByte(unsigned int n
) const
4061 if (n
/WORD_SIZE
>= reg
.size())
4064 return byte(reg
[n
/WORD_SIZE
] >> ((n
%WORD_SIZE
)*8));
4067 void Integer::SetByte(unsigned int n
, byte value
)
4069 reg
.CleanGrow(RoundupSize(BytesToWords(n
+1)));
4070 reg
[n
/WORD_SIZE
] &= ~(word(0xff) << 8*(n
%WORD_SIZE
));
4071 reg
[n
/WORD_SIZE
] |= (word(value
) << 8*(n
%WORD_SIZE
));
4074 unsigned long Integer::GetBits(unsigned int i
, unsigned int n
) const
4076 assert(n
<= sizeof(unsigned long)*8);
4077 unsigned long v
= 0;
4078 for (unsigned int j
=0; j
<n
; j
++)
4079 v
|= GetBit(i
+j
) << j
;
4083 Integer
Integer::operator-() const
4085 Integer
result(*this);
4090 Integer
Integer::AbsoluteValue() const
4092 Integer
result(*this);
4093 result
.sign
= POSITIVE
;
4097 void Integer::swap(Integer
&a
)
4100 std::swap(sign
, a
.sign
);
4103 Integer::Integer(word value
, unsigned int length
)
4104 : reg(RoundupSize(length
)), sign(POSITIVE
)
4107 SetWords(reg
+1, 0, reg
.size()-1);
4111 static Integer
StringToInteger(const T
*str
)
4115 // std::char_traits doesn't exist in GCC 2.x
4116 // std::char_traits<wchar_t>::length() not defined in GCC 3.2 and STLport 4.5.3
4117 unsigned int length
;
4118 for (length
= 0; str
[length
] != 0; length
++) {}
4125 switch (str
[length
-1])
4143 if (length
> 2 && str
[0] == '0' && str
[1] == 'x')
4146 for (unsigned i
=0; i
<length
; i
++)
4150 if (str
[i
] >= '0' && str
[i
] <= '9')
4151 digit
= str
[i
] - '0';
4152 else if (str
[i
] >= 'A' && str
[i
] <= 'F')
4153 digit
= str
[i
] - 'A' + 10;
4154 else if (str
[i
] >= 'a' && str
[i
] <= 'f')
4155 digit
= str
[i
] - 'a' + 10;
4172 Integer::Integer(const char *str
)
4173 : reg(2), sign(POSITIVE
)
4175 *this = StringToInteger(str
);
4178 Integer::Integer(const wchar_t *str
)
4179 : reg(2), sign(POSITIVE
)
4181 *this = StringToInteger(str
);
4184 unsigned int Integer::WordCount() const
4186 return CountWords(reg
, reg
.size());
4189 unsigned int Integer::ByteCount() const
4191 unsigned wordCount
= WordCount();
4193 return (wordCount
-1)*WORD_SIZE
+ BytePrecision(reg
[wordCount
-1]);
4198 unsigned int Integer::BitCount() const
4200 unsigned wordCount
= WordCount();
4202 return (wordCount
-1)*WORD_BITS
+ BitPrecision(reg
[wordCount
-1]);
4207 void Integer::Decode(const byte
*input
, unsigned int inputLen
, Signedness s
)
4209 StringStore
store(input
, inputLen
);
4210 Decode(store
, inputLen
, s
);
4213 void Integer::Decode(BufferedTransformation
&bt
, unsigned int inputLen
, Signedness s
)
4215 assert(bt
.MaxRetrievable() >= inputLen
);
4219 sign
= ((s
==SIGNED
) && (b
& 0x80)) ? NEGATIVE
: POSITIVE
;
4221 while (inputLen
>0 && (sign
==POSITIVE
? b
==0 : b
==0xff))
4228 reg
.CleanNew(RoundupSize(BytesToWords(inputLen
)));
4230 for (unsigned int i
=inputLen
; i
> 0; i
--)
4233 reg
[(i
-1)/WORD_SIZE
] |= word(b
) << ((i
-1)%WORD_SIZE
)*8;
4236 if (sign
== NEGATIVE
)
4238 for (unsigned i
=inputLen
; i
<reg
.size()*WORD_SIZE
; i
++)
4239 reg
[i
/WORD_SIZE
] |= word(0xff) << (i
%WORD_SIZE
)*8;
4240 TwosComplement(reg
, reg
.size());
4244 unsigned int Integer::MinEncodedSize(Signedness signedness
) const
4246 unsigned int outputLen
= STDMAX(1U, ByteCount());
4247 if (signedness
== UNSIGNED
)
4249 if (NotNegative() && (GetByte(outputLen
-1) & 0x80))
4251 if (IsNegative() && *this < -Power2(outputLen
*8-1))
4256 unsigned int Integer::Encode(byte
*output
, unsigned int outputLen
, Signedness signedness
) const
4258 ArraySink
sink(output
, outputLen
);
4259 return Encode(sink
, outputLen
, signedness
);
4262 unsigned int Integer::Encode(BufferedTransformation
&bt
, unsigned int outputLen
, Signedness signedness
) const
4264 if (signedness
== UNSIGNED
|| NotNegative())
4266 for (unsigned int i
=outputLen
; i
> 0; i
--)
4267 bt
.Put(GetByte(i
-1));
4271 // take two's complement of *this
4272 Integer temp
= Integer::Power2(8*STDMAX(ByteCount(), outputLen
)) + *this;
4273 for (unsigned i
=0; i
<outputLen
; i
++)
4274 bt
.Put(temp
.GetByte(outputLen
-i
-1));
4279 void Integer::DEREncode(BufferedTransformation
&bt
) const
4281 DERGeneralEncoder
enc(bt
, INTEGER
);
4282 Encode(enc
, MinEncodedSize(SIGNED
), SIGNED
);
4286 void Integer::BERDecode(const byte
*input
, unsigned int len
)
4288 StringStore
store(input
, len
);
4292 void Integer::BERDecode(BufferedTransformation
&bt
)
4294 BERGeneralDecoder
dec(bt
, INTEGER
);
4295 if (!dec
.IsDefiniteLength() || dec
.MaxRetrievable() < dec
.RemainingLength())
4297 Decode(dec
, dec
.RemainingLength(), SIGNED
);
4301 void Integer::DEREncodeAsOctetString(BufferedTransformation
&bt
, unsigned int length
) const
4303 DERGeneralEncoder
enc(bt
, OCTET_STRING
);
4304 Encode(enc
, length
);
4308 void Integer::BERDecodeAsOctetString(BufferedTransformation
&bt
, unsigned int length
)
4310 BERGeneralDecoder
dec(bt
, OCTET_STRING
);
4311 if (!dec
.IsDefiniteLength() || dec
.RemainingLength() != length
)
4313 Decode(dec
, length
);
4317 unsigned int Integer::OpenPGPEncode(byte
*output
, unsigned int len
) const
4319 ArraySink
sink(output
, len
);
4320 return OpenPGPEncode(sink
);
4323 unsigned int Integer::OpenPGPEncode(BufferedTransformation
&bt
) const
4325 word16 bitCount
= BitCount();
4326 bt
.PutWord16(bitCount
);
4327 return 2 + Encode(bt
, BitsToBytes(bitCount
));
4330 void Integer::OpenPGPDecode(const byte
*input
, unsigned int len
)
4332 StringStore
store(input
, len
);
4333 OpenPGPDecode(store
);
4336 void Integer::OpenPGPDecode(BufferedTransformation
&bt
)
4339 if (bt
.GetWord16(bitCount
) != 2 || bt
.MaxRetrievable() < BitsToBytes(bitCount
))
4340 throw OpenPGPDecodeErr();
4341 Decode(bt
, BitsToBytes(bitCount
));
4344 void Integer::Randomize(RandomNumberGenerator
&rng
, unsigned int nbits
)
4346 const unsigned int nbytes
= nbits
/8 + 1;
4347 SecByteBlock
buf(nbytes
);
4348 rng
.GenerateBlock(buf
, nbytes
);
4350 buf
[0] = (byte
)Crop(buf
[0], nbits
% 8);
4351 Decode(buf
, nbytes
, UNSIGNED
);
4354 void Integer::Randomize(RandomNumberGenerator
&rng
, const Integer
&min
, const Integer
&max
)
4357 throw InvalidArgument("Integer: Min must be no greater than Max");
4359 Integer range
= max
- min
;
4360 const unsigned int nbits
= range
.BitCount();
4364 Randomize(rng
, nbits
);
4366 while (*this > range
);
4371 bool Integer::Randomize(RandomNumberGenerator
&rng
, const Integer
&min
, const Integer
&max
, RandomNumberType rnType
, const Integer
&equiv
, const Integer
&mod
)
4373 return GenerateRandomNoThrow(rng
, MakeParameters("Min", min
)("Max", max
)("RandomNumberType", rnType
)("EquivalentTo", equiv
)("Mod", mod
));
4376 class KDF2_RNG
: public RandomNumberGenerator
4379 KDF2_RNG(const byte
*seed
, unsigned int seedSize
)
4380 : m_counter(0), m_counterAndSeed(seedSize
+ 4)
4382 memcpy(m_counterAndSeed
+ 4, seed
, seedSize
);
4388 GenerateBlock(&b
, 1);
4392 void GenerateBlock(byte
*output
, unsigned int size
)
4394 UnalignedPutWord(BIG_ENDIAN_ORDER
, m_counterAndSeed
, m_counter
);
4396 P1363_KDF2
<SHA1
>::DeriveKey(output
, size
, m_counterAndSeed
, m_counterAndSeed
.size(), NULL
, 0);
4401 SecByteBlock m_counterAndSeed
;
4404 bool Integer::GenerateRandomNoThrow(RandomNumberGenerator
&i_rng
, const NameValuePairs
¶ms
)
4406 Integer min
= params
.GetValueWithDefault("Min", Integer::Zero());
4408 if (!params
.GetValue("Max", max
))
4411 if (params
.GetIntValue("BitLength", bitLength
))
4412 max
= Integer::Power2(bitLength
);
4414 throw InvalidArgument("Integer: missing Max argument");
4417 throw InvalidArgument("Integer: Min must be no greater than Max");
4419 Integer equiv
= params
.GetValueWithDefault("EquivalentTo", Integer::Zero());
4420 Integer mod
= params
.GetValueWithDefault("Mod", Integer::One());
4422 if (equiv
.IsNegative() || equiv
>= mod
)
4423 throw InvalidArgument("Integer: invalid EquivalentTo and/or Mod argument");
4425 Integer::RandomNumberType rnType
= params
.GetValueWithDefault("RandomNumberType", Integer::ANY
);
4427 member_ptr
<KDF2_RNG
> kdf2Rng
;
4428 ConstByteArrayParameter seed
;
4429 if (params
.GetValue("Seed", seed
))
4432 DERSequenceEncoder
seq(bq
);
4435 equiv
.DEREncode(seq
);
4437 DEREncodeUnsigned(seq
, rnType
);
4438 DEREncodeOctetString(seq
, seed
.begin(), seed
.size());
4441 SecByteBlock
finalSeed(bq
.MaxRetrievable());
4442 bq
.Get(finalSeed
, finalSeed
.size());
4443 kdf2Rng
.reset(new KDF2_RNG(finalSeed
.begin(), finalSeed
.size()));
4445 RandomNumberGenerator
&rng
= kdf2Rng
.get() ? (RandomNumberGenerator
&)*kdf2Rng
: i_rng
;
4451 Randomize(rng
, min
, max
);
4454 Integer min1
= min
+ (equiv
-min
)%mod
;
4457 Randomize(rng
, Zero(), (max
- min1
) / mod
);
4465 const PrimeSelector
*pSelector
= params
.GetValueWithDefault(Name::PointerToPrimeSelector(), (const PrimeSelector
*)NULL
);
4473 // check if there are any suitable primes in [min, max]
4474 Integer first
= min
;
4475 if (FirstPrime(first
, max
, equiv
, mod
, pSelector
))
4477 // if there is only one suitable prime, we're done
4479 if (!FirstPrime(first
, max
, equiv
, mod
, pSelector
))
4486 Randomize(rng
, min
, max
);
4487 if (FirstPrime(*this, STDMIN(*this+mod
*PrimeSearchInterval(max
), max
), equiv
, mod
, pSelector
))
4493 throw InvalidArgument("Integer: invalid RandomNumberType argument");
4497 std::istream
& operator>>(std::istream
& in
, Integer
&a
)
4500 unsigned int length
= 0;
4501 SecBlock
<char> str(length
+ 16);
4509 if (length
>= str
.size())
4510 str
.Grow(length
+ 16);
4512 while (in
&& (c
=='-' || c
=='x' || (c
>='0' && c
<='9') || (c
>='a' && c
<='f') || (c
>='A' && c
<='F') || c
=='h' || c
=='H' || c
=='o' || c
=='O' || c
==',' || c
=='.'));
4516 str
[length
-1] = '\0';
4522 std::ostream
& operator<<(std::ostream
& out
, const Integer
&a
)
4524 // Get relevant conversion specifications from ostream.
4525 long f
= out
.flags() & std::ios::basefield
; // Get base digits.
4530 case std::ios::oct
:
4535 case std::ios::hex
:
4546 SecBlock
<char> s(a
.BitCount() / (BitPrecision(base
)-1) + 1);
4547 Integer temp1
=a
, temp2
;
4549 const char vec
[]="0123456789ABCDEF";
4563 Integer::Divide(digit
, temp2
, temp1
, base
);
4571 // if (i && !(i%block))
4574 return out
<< suffix
;
4577 Integer
& Integer::operator++()
4581 if (Increment(reg
, reg
.size()))
4583 reg
.CleanGrow(2*reg
.size());
4584 reg
[reg
.size()/2]=1;
4589 word borrow
= Decrement(reg
, reg
.size());
4597 Integer
& Integer::operator--()
4601 if (Increment(reg
, reg
.size()))
4603 reg
.CleanGrow(2*reg
.size());
4604 reg
[reg
.size()/2]=1;
4609 if (Decrement(reg
, reg
.size()))
4615 void PositiveAdd(Integer
&sum
, const Integer
&a
, const Integer
& b
)
4618 if (a
.reg
.size() == b
.reg
.size())
4619 carry
= Add(sum
.reg
, a
.reg
, b
.reg
, a
.reg
.size());
4620 else if (a
.reg
.size() > b
.reg
.size())
4622 carry
= Add(sum
.reg
, a
.reg
, b
.reg
, b
.reg
.size());
4623 CopyWords(sum
.reg
+b
.reg
.size(), a
.reg
+b
.reg
.size(), a
.reg
.size()-b
.reg
.size());
4624 carry
= Increment(sum
.reg
+b
.reg
.size(), a
.reg
.size()-b
.reg
.size(), carry
);
4628 carry
= Add(sum
.reg
, a
.reg
, b
.reg
, a
.reg
.size());
4629 CopyWords(sum
.reg
+a
.reg
.size(), b
.reg
+a
.reg
.size(), b
.reg
.size()-a
.reg
.size());
4630 carry
= Increment(sum
.reg
+a
.reg
.size(), b
.reg
.size()-a
.reg
.size(), carry
);
4635 sum
.reg
.CleanGrow(2*sum
.reg
.size());
4636 sum
.reg
[sum
.reg
.size()/2] = 1;
4638 sum
.sign
= Integer::POSITIVE
;
4641 void PositiveSubtract(Integer
&diff
, const Integer
&a
, const Integer
& b
)
4643 unsigned aSize
= a
.WordCount();
4645 unsigned bSize
= b
.WordCount();
4650 if (Compare(a
.reg
, b
.reg
, aSize
) >= 0)
4652 Subtract(diff
.reg
, a
.reg
, b
.reg
, aSize
);
4653 diff
.sign
= Integer::POSITIVE
;
4657 Subtract(diff
.reg
, b
.reg
, a
.reg
, aSize
);
4658 diff
.sign
= Integer::NEGATIVE
;
4661 else if (aSize
> bSize
)
4663 word borrow
= Subtract(diff
.reg
, a
.reg
, b
.reg
, bSize
);
4664 CopyWords(diff
.reg
+bSize
, a
.reg
+bSize
, aSize
-bSize
);
4665 borrow
= Decrement(diff
.reg
+bSize
, aSize
-bSize
, borrow
);
4667 diff
.sign
= Integer::POSITIVE
;
4671 word borrow
= Subtract(diff
.reg
, b
.reg
, a
.reg
, aSize
);
4672 CopyWords(diff
.reg
+aSize
, b
.reg
+aSize
, bSize
-aSize
);
4673 borrow
= Decrement(diff
.reg
+aSize
, bSize
-aSize
, borrow
);
4675 diff
.sign
= Integer::NEGATIVE
;
4679 Integer
Integer::Plus(const Integer
& b
) const
4681 Integer
sum((word
)0, STDMAX(reg
.size(), b
.reg
.size()));
4684 if (b
.NotNegative())
4685 PositiveAdd(sum
, *this, b
);
4687 PositiveSubtract(sum
, *this, b
);
4691 if (b
.NotNegative())
4692 PositiveSubtract(sum
, b
, *this);
4695 PositiveAdd(sum
, *this, b
);
4696 sum
.sign
= Integer::NEGATIVE
;
4702 Integer
& Integer::operator+=(const Integer
& t
)
4704 reg
.CleanGrow(t
.reg
.size());
4707 if (t
.NotNegative())
4708 PositiveAdd(*this, *this, t
);
4710 PositiveSubtract(*this, *this, t
);
4714 if (t
.NotNegative())
4715 PositiveSubtract(*this, t
, *this);
4718 PositiveAdd(*this, *this, t
);
4719 sign
= Integer::NEGATIVE
;
4725 Integer
Integer::Minus(const Integer
& b
) const
4727 Integer
diff((word
)0, STDMAX(reg
.size(), b
.reg
.size()));
4730 if (b
.NotNegative())
4731 PositiveSubtract(diff
, *this, b
);
4733 PositiveAdd(diff
, *this, b
);
4737 if (b
.NotNegative())
4739 PositiveAdd(diff
, *this, b
);
4740 diff
.sign
= Integer::NEGATIVE
;
4743 PositiveSubtract(diff
, b
, *this);
4748 Integer
& Integer::operator-=(const Integer
& t
)
4750 reg
.CleanGrow(t
.reg
.size());
4753 if (t
.NotNegative())
4754 PositiveSubtract(*this, *this, t
);
4756 PositiveAdd(*this, *this, t
);
4760 if (t
.NotNegative())
4762 PositiveAdd(*this, *this, t
);
4763 sign
= Integer::NEGATIVE
;
4766 PositiveSubtract(*this, t
, *this);
4771 Integer
& Integer::operator<<=(unsigned int n
)
4773 const unsigned int wordCount
= WordCount();
4774 const unsigned int shiftWords
= n
/ WORD_BITS
;
4775 const unsigned int shiftBits
= n
% WORD_BITS
;
4777 reg
.CleanGrow(RoundupSize(wordCount
+BitsToWords(n
)));
4778 ShiftWordsLeftByWords(reg
, wordCount
+ shiftWords
, shiftWords
);
4779 ShiftWordsLeftByBits(reg
+shiftWords
, wordCount
+BitsToWords(shiftBits
), shiftBits
);
4783 Integer
& Integer::operator>>=(unsigned int n
)
4785 const unsigned int wordCount
= WordCount();
4786 const unsigned int shiftWords
= n
/ WORD_BITS
;
4787 const unsigned int shiftBits
= n
% WORD_BITS
;
4789 ShiftWordsRightByWords(reg
, wordCount
, shiftWords
);
4790 if (wordCount
> shiftWords
)
4791 ShiftWordsRightByBits(reg
, wordCount
-shiftWords
, shiftBits
);
4792 if (IsNegative() && WordCount()==0) // avoid -0
4797 void PositiveMultiply(Integer
&product
, const Integer
&a
, const Integer
&b
)
4799 unsigned aSize
= RoundupSize(a
.WordCount());
4800 unsigned bSize
= RoundupSize(b
.WordCount());
4802 product
.reg
.CleanNew(RoundupSize(aSize
+bSize
));
4803 product
.sign
= Integer::POSITIVE
;
4805 SecAlignedWordBlock
workspace(aSize
+ bSize
);
4806 AsymmetricMultiply(product
.reg
, workspace
, a
.reg
, aSize
, b
.reg
, bSize
);
4809 void Multiply(Integer
&product
, const Integer
&a
, const Integer
&b
)
4811 PositiveMultiply(product
, a
, b
);
4813 if (a
.NotNegative() != b
.NotNegative())
4817 Integer
Integer::Times(const Integer
&b
) const
4820 Multiply(product
, *this, b
);
4824 void PositiveDivide(Integer
&remainder
, Integer
"ient
,
4825 const Integer
&a
, const Integer
&b
)
4827 unsigned aSize
= a
.WordCount();
4828 unsigned bSize
= b
.WordCount();
4831 throw Integer::DivideByZero();
4833 if (a
.PositiveCompare(b
) == -1)
4836 remainder
.sign
= Integer::POSITIVE
;
4837 quotient
= Integer::Zero();
4841 aSize
+= aSize
%2; // round up to next even number
4844 remainder
.reg
.CleanNew(RoundupSize(bSize
));
4845 remainder
.sign
= Integer::POSITIVE
;
4846 quotient
.reg
.CleanNew(RoundupSize(aSize
-bSize
+2));
4847 quotient
.sign
= Integer::POSITIVE
;
4849 SecAlignedWordBlock
T(aSize
+2*bSize
+4);
4850 Divide(remainder
.reg
, quotient
.reg
, T
, a
.reg
, aSize
, b
.reg
, bSize
);
4853 void Integer::Divide(Integer
&remainder
, Integer
"ient
, const Integer
÷nd
, const Integer
&divisor
)
4855 PositiveDivide(remainder
, quotient
, dividend
, divisor
);
4857 if (dividend
.IsNegative())
4860 if (remainder
.NotZero())
4863 remainder
= divisor
.AbsoluteValue() - remainder
;
4867 if (divisor
.IsNegative())
4871 void Integer::DivideByPowerOf2(Integer
&r
, Integer
&q
, const Integer
&a
, unsigned int n
)
4876 const unsigned int wordCount
= BitsToWords(n
);
4877 if (wordCount
<= a
.WordCount())
4879 r
.reg
.resize(RoundupSize(wordCount
));
4880 CopyWords(r
.reg
, a
.reg
, wordCount
);
4881 SetWords(r
.reg
+wordCount
, 0, r
.reg
.size()-wordCount
);
4882 if (n
% WORD_BITS
!= 0)
4883 r
.reg
[wordCount
-1] %= (1 << (n
% WORD_BITS
));
4887 r
.reg
.resize(RoundupSize(a
.WordCount()));
4888 CopyWords(r
.reg
, a
.reg
, r
.reg
.size());
4892 if (a
.IsNegative() && r
.NotZero())
4899 Integer
Integer::DividedBy(const Integer
&b
) const
4901 Integer remainder
, quotient
;
4902 Integer::Divide(remainder
, quotient
, *this, b
);
4906 Integer
Integer::Modulo(const Integer
&b
) const
4908 Integer remainder
, quotient
;
4909 Integer::Divide(remainder
, quotient
, *this, b
);
4913 void Integer::Divide(word
&remainder
, Integer
"ient
, const Integer
÷nd
, word divisor
)
4916 throw Integer::DivideByZero();
4920 if ((divisor
& (divisor
-1)) == 0) // divisor is a power of 2
4922 quotient
= dividend
>> (BitPrecision(divisor
)-1);
4923 remainder
= dividend
.reg
[0] & (divisor
-1);
4927 unsigned int i
= dividend
.WordCount();
4928 quotient
.reg
.CleanNew(RoundupSize(i
));
4932 quotient
.reg
[i
] = DWord(dividend
.reg
[i
], remainder
) / divisor
;
4933 remainder
= DWord(dividend
.reg
[i
], remainder
) % divisor
;
4936 if (dividend
.NotNegative())
4937 quotient
.sign
= POSITIVE
;
4940 quotient
.sign
= NEGATIVE
;
4944 remainder
= divisor
- remainder
;
4949 Integer
Integer::DividedBy(word b
) const
4953 Integer::Divide(remainder
, quotient
, *this, b
);
4957 word
Integer::Modulo(word divisor
) const
4960 throw Integer::DivideByZero();
4966 if ((divisor
& (divisor
-1)) == 0) // divisor is a power of 2
4967 remainder
= reg
[0] & (divisor
-1);
4970 unsigned int i
= WordCount();
4977 remainder
= sum
% divisor
;
4983 remainder
= DWord(reg
[i
], remainder
) % divisor
;
4987 if (IsNegative() && remainder
)
4988 remainder
= divisor
- remainder
;
4993 void Integer::Negate()
4995 if (!!(*this)) // don't flip sign if *this==0
4996 sign
= Sign(1-sign
);
4999 int Integer::PositiveCompare(const Integer
& t
) const
5001 unsigned size
= WordCount(), tSize
= t
.WordCount();
5004 return CryptoPP::Compare(reg
, t
.reg
, size
);
5006 return size
> tSize
? 1 : -1;
5009 int Integer::Compare(const Integer
& t
) const
5013 if (t
.NotNegative())
5014 return PositiveCompare(t
);
5020 if (t
.NotNegative())
5023 return -PositiveCompare(t
);
5027 Integer
Integer::SquareRoot() const
5032 // overestimate square root
5033 Integer x
, y
= Power2((BitCount()+1)/2);
5034 assert(y
*y
>= *this);
5039 y
= (x
+ *this/x
) >> 1;
5045 bool Integer::IsSquare() const
5047 Integer r
= SquareRoot();
5048 return *this == r
.Squared();
5051 bool Integer::IsUnit() const
5053 return (WordCount() == 1) && (reg
[0] == 1);
5056 Integer
Integer::MultiplicativeInverse() const
5058 return IsUnit() ? *this : Zero();
5061 Integer
a_times_b_mod_c(const Integer
&x
, const Integer
& y
, const Integer
& m
)
5066 Integer
a_exp_b_mod_c(const Integer
&x
, const Integer
& e
, const Integer
& m
)
5068 ModularArithmetic
mr(m
);
5069 return mr
.Exponentiate(x
, e
);
5072 Integer
Integer::Gcd(const Integer
&a
, const Integer
&b
)
5074 return EuclideanDomainOf
<Integer
>().Gcd(a
, b
);
5077 Integer
Integer::InverseMod(const Integer
&m
) const
5079 assert(m
.NotNegative());
5081 if (IsNegative() || *this>=m
)
5082 return (*this%m
).InverseMod(m
);
5087 return Zero(); // no inverse
5091 Integer u
= m
.InverseMod(*this);
5092 return !u
? Zero() : (m
*(*this-u
)+1)/(*this);
5095 SecBlock
<word
> T(m
.reg
.size() * 4);
5096 Integer
r((word
)0, m
.reg
.size());
5097 unsigned k
= AlmostInverse(r
.reg
, T
, reg
, reg
.size(), m
.reg
, m
.reg
.size());
5098 DivideByPower2Mod(r
.reg
, r
.reg
, k
, m
.reg
, m
.reg
.size());
5102 word
Integer::InverseMod(const word mod
) const
5104 word g0
= mod
, g1
= *this % mod
;
5105 word v0
= 0, v1
= 1;
5127 // ********************************************************
5129 ModularArithmetic::ModularArithmetic(BufferedTransformation
&bt
)
5131 BERSequenceDecoder
seq(bt
);
5133 if (oid
!= ASN1::prime_field())
5135 modulus
.BERDecode(seq
);
5137 result
.reg
.resize(modulus
.reg
.size());
5140 void ModularArithmetic::DEREncode(BufferedTransformation
&bt
) const
5142 DERSequenceEncoder
seq(bt
);
5143 ASN1::prime_field().DEREncode(seq
);
5144 modulus
.DEREncode(seq
);
5148 void ModularArithmetic::DEREncodeElement(BufferedTransformation
&out
, const Element
&a
) const
5150 a
.DEREncodeAsOctetString(out
, MaxElementByteLength());
5153 void ModularArithmetic::BERDecodeElement(BufferedTransformation
&in
, Element
&a
) const
5155 a
.BERDecodeAsOctetString(in
, MaxElementByteLength());
5158 const Integer
& ModularArithmetic::Half(const Integer
&a
) const
5160 if (a
.reg
.size()==modulus
.reg
.size())
5162 CryptoPP::DivideByPower2Mod(result
.reg
.begin(), a
.reg
, 1, modulus
.reg
, a
.reg
.size());
5166 return result1
= (a
.IsEven() ? (a
>> 1) : ((a
+modulus
) >> 1));
5169 const Integer
& ModularArithmetic::Add(const Integer
&a
, const Integer
&b
) const
5171 if (a
.reg
.size()==modulus
.reg
.size() && b
.reg
.size()==modulus
.reg
.size())
5173 if (CryptoPP::Add(result
.reg
.begin(), a
.reg
, b
.reg
, a
.reg
.size())
5174 || Compare(result
.reg
, modulus
.reg
, a
.reg
.size()) >= 0)
5176 CryptoPP::Subtract(result
.reg
.begin(), result
.reg
, modulus
.reg
, a
.reg
.size());
5183 if (result1
>= modulus
)
5189 Integer
& ModularArithmetic::Accumulate(Integer
&a
, const Integer
&b
) const
5191 if (a
.reg
.size()==modulus
.reg
.size() && b
.reg
.size()==modulus
.reg
.size())
5193 if (CryptoPP::Add(a
.reg
, a
.reg
, b
.reg
, a
.reg
.size())
5194 || Compare(a
.reg
, modulus
.reg
, a
.reg
.size()) >= 0)
5196 CryptoPP::Subtract(a
.reg
, a
.reg
, modulus
.reg
, a
.reg
.size());
5209 const Integer
& ModularArithmetic::Subtract(const Integer
&a
, const Integer
&b
) const
5211 if (a
.reg
.size()==modulus
.reg
.size() && b
.reg
.size()==modulus
.reg
.size())
5213 if (CryptoPP::Subtract(result
.reg
.begin(), a
.reg
, b
.reg
, a
.reg
.size()))
5214 CryptoPP::Add(result
.reg
.begin(), result
.reg
, modulus
.reg
, a
.reg
.size());
5220 if (result1
.IsNegative())
5226 Integer
& ModularArithmetic::Reduce(Integer
&a
, const Integer
&b
) const
5228 if (a
.reg
.size()==modulus
.reg
.size() && b
.reg
.size()==modulus
.reg
.size())
5230 if (CryptoPP::Subtract(a
.reg
, a
.reg
, b
.reg
, a
.reg
.size()))
5231 CryptoPP::Add(a
.reg
, a
.reg
, modulus
.reg
, a
.reg
.size());
5243 const Integer
& ModularArithmetic::Inverse(const Integer
&a
) const
5248 CopyWords(result
.reg
.begin(), modulus
.reg
, modulus
.reg
.size());
5249 if (CryptoPP::Subtract(result
.reg
.begin(), result
.reg
, a
.reg
, a
.reg
.size()))
5250 Decrement(result
.reg
.begin()+a
.reg
.size(), 1, modulus
.reg
.size()-a
.reg
.size());
5255 Integer
ModularArithmetic::CascadeExponentiate(const Integer
&x
, const Integer
&e1
, const Integer
&y
, const Integer
&e2
) const
5257 if (modulus
.IsOdd())
5259 MontgomeryRepresentation
dr(modulus
);
5260 return dr
.ConvertOut(dr
.CascadeExponentiate(dr
.ConvertIn(x
), e1
, dr
.ConvertIn(y
), e2
));
5263 return AbstractRing
<Integer
>::CascadeExponentiate(x
, e1
, y
, e2
);
5266 void ModularArithmetic::SimultaneousExponentiate(Integer
*results
, const Integer
&base
, const Integer
*exponents
, unsigned int exponentsCount
) const
5268 if (modulus
.IsOdd())
5270 MontgomeryRepresentation
dr(modulus
);
5271 dr
.SimultaneousExponentiate(results
, dr
.ConvertIn(base
), exponents
, exponentsCount
);
5272 for (unsigned int i
=0; i
<exponentsCount
; i
++)
5273 results
[i
] = dr
.ConvertOut(results
[i
]);
5276 AbstractRing
<Integer
>::SimultaneousExponentiate(results
, base
, exponents
, exponentsCount
);
5279 MontgomeryRepresentation::MontgomeryRepresentation(const Integer
&m
) // modulus must be odd
5280 : ModularArithmetic(m
),
5281 u((word
)0, modulus
.reg
.size()),
5282 workspace(5*modulus
.reg
.size())
5284 if (!modulus
.IsOdd())
5285 throw InvalidArgument("MontgomeryRepresentation: Montgomery representation requires an odd modulus");
5287 RecursiveInverseModPower2(u
.reg
, workspace
, modulus
.reg
, modulus
.reg
.size());
5290 const Integer
& MontgomeryRepresentation::Multiply(const Integer
&a
, const Integer
&b
) const
5292 word
*const T
= workspace
.begin();
5293 word
*const R
= result
.reg
.begin();
5294 const unsigned int N
= modulus
.reg
.size();
5295 assert(a
.reg
.size()<=N
&& b
.reg
.size()<=N
);
5297 AsymmetricMultiply(T
, T
+2*N
, a
.reg
, a
.reg
.size(), b
.reg
, b
.reg
.size());
5298 SetWords(T
+a
.reg
.size()+b
.reg
.size(), 0, 2*N
-a
.reg
.size()-b
.reg
.size());
5299 MontgomeryReduce(R
, T
+2*N
, T
, modulus
.reg
, u
.reg
, N
);
5303 const Integer
& MontgomeryRepresentation::Square(const Integer
&a
) const
5305 word
*const T
= workspace
.begin();
5306 word
*const R
= result
.reg
.begin();
5307 const unsigned int N
= modulus
.reg
.size();
5308 assert(a
.reg
.size()<=N
);
5310 CryptoPP::Square(T
, T
+2*N
, a
.reg
, a
.reg
.size());
5311 SetWords(T
+2*a
.reg
.size(), 0, 2*N
-2*a
.reg
.size());
5312 MontgomeryReduce(R
, T
+2*N
, T
, modulus
.reg
, u
.reg
, N
);
5316 Integer
MontgomeryRepresentation::ConvertOut(const Integer
&a
) const
5318 word
*const T
= workspace
.begin();
5319 word
*const R
= result
.reg
.begin();
5320 const unsigned int N
= modulus
.reg
.size();
5321 assert(a
.reg
.size()<=N
);
5323 CopyWords(T
, a
.reg
, a
.reg
.size());
5324 SetWords(T
+a
.reg
.size(), 0, 2*N
-a
.reg
.size());
5325 MontgomeryReduce(R
, T
+2*N
, T
, modulus
.reg
, u
.reg
, N
);
5329 const Integer
& MontgomeryRepresentation::MultiplicativeInverse(const Integer
&a
) const
5331 // return (EuclideanMultiplicativeInverse(a, modulus)<<(2*WORD_BITS*modulus.reg.size()))%modulus;
5332 word
*const T
= workspace
.begin();
5333 word
*const R
= result
.reg
.begin();
5334 const unsigned int N
= modulus
.reg
.size();
5335 assert(a
.reg
.size()<=N
);
5337 CopyWords(T
, a
.reg
, a
.reg
.size());
5338 SetWords(T
+a
.reg
.size(), 0, 2*N
-a
.reg
.size());
5339 MontgomeryReduce(R
, T
+2*N
, T
, modulus
.reg
, u
.reg
, N
);
5340 unsigned k
= AlmostInverse(R
, T
, R
, N
, modulus
.reg
, N
);
5342 // cout << "k=" << k << " N*32=" << 32*N << endl;
5345 DivideByPower2Mod(R
, R
, k
-N
*WORD_BITS
, modulus
.reg
, N
);
5347 MultiplyByPower2Mod(R
, R
, N
*WORD_BITS
-k
, modulus
.reg
, N
);
5355 ////////////////////////////////////////////////////////////////////////////////
5359 ////////////////////////////////////////////////////////////////////////////////
5360 // algebra.cpp - written and placed in the public domain by Wei Dai
5362 //- #include "pch.h"
5363 //- #include "algebra.h"
5364 //- #include "integer.h"
5368 NAMESPACE_BEGIN(CryptoPP
)
5370 template <class T
> const T
& AbstractGroup
<T
>::Double(const Element
&a
) const
5375 template <class T
> const T
& AbstractGroup
<T
>::Subtract(const Element
&a
, const Element
&b
) const
5377 // make copy of a in case Inverse() overwrites it
5379 return Add(a1
, Inverse(b
));
5382 template <class T
> T
& AbstractGroup
<T
>::Accumulate(Element
&a
, const Element
&b
) const
5384 return a
= Add(a
, b
);
5387 template <class T
> T
& AbstractGroup
<T
>::Reduce(Element
&a
, const Element
&b
) const
5389 return a
= Subtract(a
, b
);
5392 template <class T
> const T
& AbstractRing
<T
>::Square(const Element
&a
) const
5394 return Multiply(a
, a
);
5397 template <class T
> const T
& AbstractRing
<T
>::Divide(const Element
&a
, const Element
&b
) const
5399 // make copy of a in case MultiplicativeInverse() overwrites it
5401 return Multiply(a1
, MultiplicativeInverse(b
));
5404 template <class T
> const T
& AbstractEuclideanDomain
<T
>::Mod(const Element
&a
, const Element
&b
) const
5407 DivisionAlgorithm(result
, q
, a
, b
);
5411 template <class T
> const T
& AbstractEuclideanDomain
<T
>::Gcd(const Element
&a
, const Element
&b
) const
5413 Element g
[3]={b
, a
};
5414 unsigned int i0
=0, i1
=1, i2
=2;
5416 while (!Equal(g
[i1
], this->Identity()))
5418 g
[i2
] = Mod(g
[i0
], g
[i1
]);
5419 unsigned int t
= i0
; i0
= i1
; i1
= i2
; i2
= t
;
5422 return result
= g
[i0
];
5425 template <class T
> T AbstractGroup
<T
>::ScalarMultiply(const Element
&base
, const Integer
&exponent
) const
5428 SimultaneousMultiply(&result
, base
, &exponent
, 1);
5432 template <class T
> T AbstractGroup
<T
>::CascadeScalarMultiply(const Element
&x
, const Integer
&e1
, const Element
&y
, const Integer
&e2
) const
5434 const unsigned expLen
= STDMAX(e1
.BitCount(), e2
.BitCount());
5438 const unsigned w
= (expLen
<= 46 ? 1 : (expLen
<= 260 ? 2 : 3));
5439 const unsigned tableSize
= 1<<w
;
5440 std::vector
<Element
> powerTable(tableSize
<< w
);
5443 powerTable
[tableSize
] = y
;
5445 powerTable
[3] = Add(x
,y
);
5448 powerTable
[2] = Double(x
);
5449 powerTable
[2*tableSize
] = Double(y
);
5453 for (i
=3; i
<tableSize
; i
+=2)
5454 powerTable
[i
] = Add(powerTable
[i
-2], powerTable
[2]);
5455 for (i
=1; i
<tableSize
; i
+=2)
5456 for (j
=i
+tableSize
; j
<(tableSize
<<w
); j
+=tableSize
)
5457 powerTable
[j
] = Add(powerTable
[j
-tableSize
], y
);
5459 for (i
=3*tableSize
; i
<(tableSize
<<w
); i
+=2*tableSize
)
5460 powerTable
[i
] = Add(powerTable
[i
-2*tableSize
], powerTable
[2*tableSize
]);
5461 for (i
=tableSize
; i
<(tableSize
<<w
); i
+=2*tableSize
)
5462 for (j
=i
+2; j
<i
+tableSize
; j
+=2)
5463 powerTable
[j
] = Add(powerTable
[j
-1], x
);
5467 unsigned power1
= 0, power2
= 0, prevPosition
= expLen
-1;
5468 bool firstTime
= true;
5470 for (int i
= expLen
-1; i
>=0; i
--)
5472 power1
= 2*power1
+ e1
.GetBit(i
);
5473 power2
= 2*power2
+ e2
.GetBit(i
);
5475 if (i
==0 || 2*power1
>= tableSize
|| 2*power2
>= tableSize
)
5477 unsigned squaresBefore
= prevPosition
-i
;
5478 unsigned squaresAfter
= 0;
5480 while ((power1
|| power2
) && power1
%2 == 0 && power2
%2==0)
5489 result
= powerTable
[(power2
<<w
) + power1
];
5494 while (squaresBefore
--)
5495 result
= Double(result
);
5496 if (power1
|| power2
)
5497 Accumulate(result
, powerTable
[(power2
<<w
) + power1
]);
5499 while (squaresAfter
--)
5500 result
= Double(result
);
5501 power1
= power2
= 0;
5509 WindowSlider(const Integer
&Exp
, bool FastNegate
, unsigned int windowSizeIn
=0)
5510 : exp(Exp
), windowModulus(Integer::One()), windowSize(windowSizeIn
), windowBegin(0), fastNegate(FastNegate
), firstTime(true), finished(false)
5512 if (windowSize
== 0)
5514 unsigned int expLen
= exp
.BitCount();
5515 windowSize
= expLen
<= 17 ? 1 : (expLen
<= 24 ? 2 : (expLen
<= 70 ? 3 : (expLen
<= 197 ? 4 : (expLen
<= 539 ? 5 : (expLen
<= 1434 ? 6 : 7)))));
5517 windowModulus
<<= windowSize
;
5520 void FindNextWindow()
5522 unsigned int expLen
= exp
.WordCount() * WORD_BITS
;
5523 unsigned int skipCount
= firstTime
? 0 : windowSize
;
5525 while (!exp
.GetBit(skipCount
))
5527 if (skipCount
>= expLen
)
5536 windowBegin
+= skipCount
;
5537 expWindow
= exp
% (1 << windowSize
);
5539 if (fastNegate
&& exp
.GetBit(windowSize
))
5542 expWindow
= (1 << windowSize
) - expWindow
;
5543 exp
+= windowModulus
;
5549 Integer exp
, windowModulus
;
5550 unsigned int windowSize
, windowBegin
, expWindow
;
5551 bool fastNegate
, negateNext
, firstTime
, finished
;
5555 void AbstractGroup
<T
>::SimultaneousMultiply(T
*results
, const T
&base
, const Integer
*expBegin
, unsigned int expCount
) const
5557 std::vector
<std::vector
<Element
> > buckets(expCount
);
5558 std::vector
<WindowSlider
> exponents
;
5559 exponents
.reserve(expCount
);
5562 for (i
=0; i
<expCount
; i
++)
5564 assert(expBegin
->NotNegative());
5565 exponents
.push_back(WindowSlider(*expBegin
++, InversionIsFast(), 0));
5566 exponents
[i
].FindNextWindow();
5567 buckets
[i
].resize(1<<(exponents
[i
].windowSize
-1), Identity());
5570 unsigned int expBitPosition
= 0;
5572 bool notDone
= true;
5577 for (i
=0; i
<expCount
; i
++)
5579 if (!exponents
[i
].finished
&& expBitPosition
== exponents
[i
].windowBegin
)
5581 Element
&bucket
= buckets
[i
][exponents
[i
].expWindow
/2];
5582 if (exponents
[i
].negateNext
)
5583 Accumulate(bucket
, Inverse(g
));
5585 Accumulate(bucket
, g
);
5586 exponents
[i
].FindNextWindow();
5588 notDone
= notDone
|| !exponents
[i
].finished
;
5598 for (i
=0; i
<expCount
; i
++)
5600 Element
&r
= *results
++;
5601 r
= buckets
[i
][buckets
[i
].size()-1];
5602 if (buckets
[i
].size() > 1)
5604 for (int j
= buckets
[i
].size()-2; j
>= 1; j
--)
5606 Accumulate(buckets
[i
][j
], buckets
[i
][j
+1]);
5607 Accumulate(r
, buckets
[i
][j
]);
5609 Accumulate(buckets
[i
][0], buckets
[i
][1]);
5610 r
= Add(Double(r
), buckets
[i
][0]);
5615 template <class T
> T AbstractRing
<T
>::Exponentiate(const Element
&base
, const Integer
&exponent
) const
5618 SimultaneousExponentiate(&result
, base
, &exponent
, 1);
5622 template <class T
> T AbstractRing
<T
>::CascadeExponentiate(const Element
&x
, const Integer
&e1
, const Element
&y
, const Integer
&e2
) const
5624 return MultiplicativeGroup().AbstractGroup
<T
>::CascadeScalarMultiply(x
, e1
, y
, e2
);
5628 void AbstractRing
<T
>::SimultaneousExponentiate(T
*results
, const T
&base
, const Integer
*exponents
, unsigned int expCount
) const
5630 MultiplicativeGroup().AbstractGroup
<T
>::SimultaneousMultiply(results
, base
, exponents
, expCount
);
5634 ////////////////////////////////////////////////////////////////////////////////
5638 ////////////////////////////////////////////////////////////////////////////////
5639 // queue.cpp - written and placed in the public domain by Wei Dai
5641 //- #include "pch.h"
5643 #ifndef CRYPTOPP_IMPORTS
5645 //- #include "queue.h"
5646 //- #include "filters.h"
5648 NAMESPACE_BEGIN(CryptoPP
)
5650 static const unsigned int s_maxAutoNodeSize
= 16*1024;
5652 // this class for use by ByteQueue only
5656 ByteQueueNode(unsigned int maxSize
)
5659 m_head
= m_tail
= 0;
5663 inline unsigned int MaxSize() const {return buf
.size();}
5665 inline unsigned int CurrentSize() const
5667 return m_tail
-m_head
;
5670 inline bool UsedUp() const
5672 return (m_head
==MaxSize());
5677 m_head
= m_tail
= 0;
5680 inline unsigned int Put(const byte
*begin
, unsigned int length
)
5682 unsigned int l
= STDMIN(length
, MaxSize()-m_tail
);
5683 if (buf
+m_tail
!= begin
)
5684 memcpy(buf
+m_tail
, begin
, l
);
5689 inline unsigned int Peek(byte
&outByte
) const
5694 outByte
=buf
[m_head
];
5698 inline unsigned int Peek(byte
*target
, unsigned int copyMax
) const
5700 unsigned int len
= STDMIN(copyMax
, m_tail
-m_head
);
5701 memcpy(target
, buf
+m_head
, len
);
5705 inline unsigned int CopyTo(BufferedTransformation
&target
, const std::string
&channel
=BufferedTransformation::NULL_CHANNEL
) const
5707 unsigned int len
= m_tail
-m_head
;
5708 target
.ChannelPut(channel
, buf
+m_head
, len
);
5712 inline unsigned int CopyTo(BufferedTransformation
&target
, unsigned int copyMax
, const std::string
&channel
=BufferedTransformation::NULL_CHANNEL
) const
5714 unsigned int len
= STDMIN(copyMax
, m_tail
-m_head
);
5715 target
.ChannelPut(channel
, buf
+m_head
, len
);
5719 inline unsigned int Get(byte
&outByte
)
5721 unsigned int len
= Peek(outByte
);
5726 inline unsigned int Get(byte
*outString
, unsigned int getMax
)
5728 unsigned int len
= Peek(outString
, getMax
);
5733 inline unsigned int TransferTo(BufferedTransformation
&target
, const std::string
&channel
=BufferedTransformation::NULL_CHANNEL
)
5735 unsigned int len
= m_tail
-m_head
;
5736 target
.ChannelPutModifiable(channel
, buf
+m_head
, len
);
5741 inline unsigned int TransferTo(BufferedTransformation
&target
, unsigned int transferMax
, const std::string
&channel
=BufferedTransformation::NULL_CHANNEL
)
5743 unsigned int len
= STDMIN(transferMax
, m_tail
-m_head
);
5744 target
.ChannelPutModifiable(channel
, buf
+m_head
, len
);
5749 inline unsigned int Skip(unsigned int skipMax
)
5751 unsigned int len
= STDMIN(skipMax
, m_tail
-m_head
);
5756 inline byte
operator[](unsigned int i
) const
5758 return buf
[m_head
+i
];
5761 ByteQueueNode
*next
;
5764 unsigned int m_head
, m_tail
;
5767 // ********************************************************
5769 ByteQueue::ByteQueue(unsigned int nodeSize
)
5772 SetNodeSize(nodeSize
);
5773 m_head
= m_tail
= new ByteQueueNode(m_nodeSize
);
5776 void ByteQueue::SetNodeSize(unsigned int nodeSize
)
5778 m_autoNodeSize
= !nodeSize
;
5779 m_nodeSize
= m_autoNodeSize
? 256 : nodeSize
;
5782 ByteQueue::ByteQueue(const ByteQueue
©
)
5783 : Bufferless
<BufferedTransformation
>()
5788 void ByteQueue::CopyFrom(const ByteQueue
©
)
5791 m_autoNodeSize
= copy
.m_autoNodeSize
;
5792 m_nodeSize
= copy
.m_nodeSize
;
5793 m_head
= m_tail
= new ByteQueueNode(*copy
.m_head
);
5795 for (ByteQueueNode
*current
=copy
.m_head
->next
; current
; current
=current
->next
)
5797 m_tail
->next
= new ByteQueueNode(*current
);
5798 m_tail
= m_tail
->next
;
5801 m_tail
->next
= NULL
;
5803 Put(copy
.m_lazyString
, copy
.m_lazyLength
);
5806 ByteQueue::~ByteQueue()
5811 void ByteQueue::Destroy()
5813 for (ByteQueueNode
*next
, *current
=m_head
; current
; current
=next
)
5820 void ByteQueue::IsolatedInitialize(const NameValuePairs
¶meters
)
5822 m_nodeSize
= parameters
.GetIntValueWithDefault("NodeSize", 256);
5826 unsigned long ByteQueue::CurrentSize() const
5828 unsigned long size
=0;
5830 for (ByteQueueNode
*current
=m_head
; current
; current
=current
->next
)
5831 size
+= current
->CurrentSize();
5833 return size
+ m_lazyLength
;
5836 bool ByteQueue::IsEmpty() const
5838 return m_head
==m_tail
&& m_head
->CurrentSize()==0 && m_lazyLength
==0;
5841 void ByteQueue::Clear()
5843 for (ByteQueueNode
*next
, *current
=m_head
->next
; current
; current
=next
)
5851 m_head
->next
= NULL
;
5855 unsigned int ByteQueue::Put2(const byte
*inString
, unsigned int length
, int /* messageEnd */, bool /* blocking */)
5857 if (m_lazyLength
> 0)
5861 while ((len
=m_tail
->Put(inString
, length
)) < length
)
5865 if (m_autoNodeSize
&& m_nodeSize
< s_maxAutoNodeSize
)
5870 while (m_nodeSize
< length
&& m_nodeSize
< s_maxAutoNodeSize
);
5871 m_tail
->next
= new ByteQueueNode(STDMAX(m_nodeSize
, length
));
5872 m_tail
= m_tail
->next
;
5878 void ByteQueue::CleanupUsedNodes()
5880 while (m_head
!= m_tail
&& m_head
->UsedUp())
5882 ByteQueueNode
*temp
=m_head
;
5883 m_head
=m_head
->next
;
5887 if (m_head
->CurrentSize() == 0)
5891 void ByteQueue::LazyPut(const byte
*inString
, unsigned int size
)
5893 if (m_lazyLength
> 0)
5896 if (inString
== m_tail
->buf
+m_tail
->m_tail
)
5897 Put(inString
, size
);
5900 m_lazyString
= const_cast<byte
*>(inString
);
5901 m_lazyLength
= size
;
5902 m_lazyStringModifiable
= false;
5906 void ByteQueue::LazyPutModifiable(byte
*inString
, unsigned int size
)
5908 if (m_lazyLength
> 0)
5910 m_lazyString
= inString
;
5911 m_lazyLength
= size
;
5912 m_lazyStringModifiable
= true;
5915 void ByteQueue::UndoLazyPut(unsigned int size
)
5917 if (m_lazyLength
< size
)
5918 throw InvalidArgument("ByteQueue: size specified for UndoLazyPut is too large");
5920 m_lazyLength
-= size
;
5923 void ByteQueue::FinalizeLazyPut()
5925 unsigned int len
= m_lazyLength
;
5928 Put(m_lazyString
, len
);
5931 unsigned int ByteQueue::Get(byte
&outByte
)
5933 if (m_head
->Get(outByte
))
5935 if (m_head
->UsedUp())
5939 else if (m_lazyLength
> 0)
5941 outByte
= *m_lazyString
++;
5949 unsigned int ByteQueue::Get(byte
*outString
, unsigned int getMax
)
5951 ArraySink
sink(outString
, getMax
);
5952 return TransferTo(sink
, getMax
);
5955 unsigned int ByteQueue::Peek(byte
&outByte
) const
5957 if (m_head
->Peek(outByte
))
5959 else if (m_lazyLength
> 0)
5961 outByte
= *m_lazyString
;
5968 unsigned int ByteQueue::Peek(byte
*outString
, unsigned int peekMax
) const
5970 ArraySink
sink(outString
, peekMax
);
5971 return CopyTo(sink
, peekMax
);
5974 unsigned int ByteQueue::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
5978 unsigned long bytesLeft
= transferBytes
;
5979 for (ByteQueueNode
*current
=m_head
; bytesLeft
&& current
; current
=current
->next
)
5980 bytesLeft
-= current
->TransferTo(target
, bytesLeft
, channel
);
5983 unsigned int len
= (unsigned int)STDMIN(bytesLeft
, (unsigned long)m_lazyLength
);
5986 if (m_lazyStringModifiable
)
5987 target
.ChannelPutModifiable(channel
, m_lazyString
, len
);
5989 target
.ChannelPut(channel
, m_lazyString
, len
);
5990 m_lazyString
+= len
;
5991 m_lazyLength
-= len
;
5994 transferBytes
-= bytesLeft
;
5999 Walker
walker(*this);
6000 unsigned int blockedBytes
= walker
.TransferTo2(target
, transferBytes
, channel
, blocking
);
6001 Skip(transferBytes
);
6002 return blockedBytes
;
6006 unsigned int ByteQueue::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
6008 Walker
walker(*this);
6010 unsigned long transferBytes
= end
-begin
;
6011 unsigned int blockedBytes
= walker
.TransferTo2(target
, transferBytes
, channel
, blocking
);
6012 begin
+= transferBytes
;
6013 return blockedBytes
;
6016 void ByteQueue::Unget(byte inByte
)
6021 void ByteQueue::Unget(const byte
*inString
, unsigned int length
)
6023 unsigned int len
= STDMIN(length
, m_head
->m_head
);
6025 m_head
->m_head
-= len
;
6026 memcpy(m_head
->buf
+ m_head
->m_head
, inString
+ length
, len
);
6030 ByteQueueNode
*newHead
= new ByteQueueNode(length
);
6031 newHead
->next
= m_head
;
6033 m_head
->Put(inString
, length
);
6037 const byte
* ByteQueue::Spy(unsigned int &contiguousSize
) const
6039 contiguousSize
= m_head
->m_tail
- m_head
->m_head
;
6040 if (contiguousSize
== 0 && m_lazyLength
> 0)
6042 contiguousSize
= m_lazyLength
;
6043 return m_lazyString
;
6046 return m_head
->buf
+ m_head
->m_head
;
6049 byte
* ByteQueue::CreatePutSpace(unsigned int &size
)
6051 if (m_lazyLength
> 0)
6054 if (m_tail
->m_tail
== m_tail
->MaxSize())
6056 m_tail
->next
= new ByteQueueNode(STDMAX(m_nodeSize
, size
));
6057 m_tail
= m_tail
->next
;
6060 size
= m_tail
->MaxSize() - m_tail
->m_tail
;
6061 return m_tail
->buf
+ m_tail
->m_tail
;
6064 ByteQueue
& ByteQueue::operator=(const ByteQueue
&rhs
)
6071 bool ByteQueue::operator==(const ByteQueue
&rhs
) const
6073 const unsigned long currentSize
= CurrentSize();
6075 if (currentSize
!= rhs
.CurrentSize())
6078 Walker
walker1(*this), walker2(rhs
);
6081 while (walker1
.Get(b1
) && walker2
.Get(b2
))
6088 byte
ByteQueue::operator[](unsigned long i
) const
6090 for (ByteQueueNode
*current
=m_head
; current
; current
=current
->next
)
6092 if (i
< current
->CurrentSize())
6093 return (*current
)[i
];
6095 i
-= current
->CurrentSize();
6098 assert(i
< m_lazyLength
);
6099 return m_lazyString
[i
];
6102 void ByteQueue::swap(ByteQueue
&rhs
)
6104 std::swap(m_autoNodeSize
, rhs
.m_autoNodeSize
);
6105 std::swap(m_nodeSize
, rhs
.m_nodeSize
);
6106 std::swap(m_head
, rhs
.m_head
);
6107 std::swap(m_tail
, rhs
.m_tail
);
6108 std::swap(m_lazyString
, rhs
.m_lazyString
);
6109 std::swap(m_lazyLength
, rhs
.m_lazyLength
);
6110 std::swap(m_lazyStringModifiable
, rhs
.m_lazyStringModifiable
);
6113 // ********************************************************
6115 void ByteQueue::Walker::IsolatedInitialize(const NameValuePairs
& /* parameters */)
6117 m_node
= m_queue
.m_head
;
6120 m_lazyString
= m_queue
.m_lazyString
;
6121 m_lazyLength
= m_queue
.m_lazyLength
;
6124 unsigned int ByteQueue::Walker::Get(byte
&outByte
)
6126 ArraySink
sink(&outByte
, 1);
6127 return TransferTo(sink
, 1);
6130 unsigned int ByteQueue::Walker::Get(byte
*outString
, unsigned int getMax
)
6132 ArraySink
sink(outString
, getMax
);
6133 return TransferTo(sink
, getMax
);
6136 unsigned int ByteQueue::Walker::Peek(byte
&outByte
) const
6138 ArraySink
sink(&outByte
, 1);
6139 return CopyTo(sink
, 1);
6142 unsigned int ByteQueue::Walker::Peek(byte
*outString
, unsigned int peekMax
) const
6144 ArraySink
sink(outString
, peekMax
);
6145 return CopyTo(sink
, peekMax
);
6148 unsigned int ByteQueue::Walker::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
6150 unsigned long bytesLeft
= transferBytes
;
6151 unsigned int blockedBytes
= 0;
6155 unsigned int len
= STDMIN(bytesLeft
, (unsigned long)m_node
->CurrentSize()-m_offset
);
6156 blockedBytes
= target
.ChannelPut2(channel
, m_node
->buf
+m_node
->m_head
+m_offset
, len
, 0, blocking
);
6170 m_node
= m_node
->next
;
6174 if (bytesLeft
&& m_lazyLength
)
6176 unsigned int len
= (unsigned int)STDMIN(bytesLeft
, (unsigned long)m_lazyLength
);
6177 unsigned int BlockedBytes
= target
.ChannelPut2(channel
, m_lazyString
, len
, 0, blocking
);
6181 m_lazyString
+= len
;
6182 m_lazyLength
-= len
;
6187 transferBytes
-= bytesLeft
;
6188 return blockedBytes
;
6191 unsigned int ByteQueue::Walker::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
6193 Walker
walker(*this);
6195 unsigned long transferBytes
= end
-begin
;
6196 unsigned int blockedBytes
= walker
.TransferTo2(target
, transferBytes
, channel
, blocking
);
6197 begin
+= transferBytes
;
6198 return blockedBytes
;
6204 ////////////////////////////////////////////////////////////////////////////////
6208 ////////////////////////////////////////////////////////////////////////////////
6209 // algparam.cpp - written and placed in the public domain by Wei Dai
6211 //- #include "pch.h"
6213 #ifndef CRYPTOPP_IMPORTS
6215 //- #include "algparam.h"
6217 NAMESPACE_BEGIN(CryptoPP
)
6219 bool (*AssignIntToInteger
)(const std::type_info
&valueType
, void *pInteger
, const void *pInt
) = NULL
;
6221 bool CombinedNameValuePairs::GetVoidValue(const char *name
, const std::type_info
&valueType
, void *pValue
) const
6223 if (strcmp(name
, "ValueNames") == 0)
6224 return m_pairs1
.GetVoidValue(name
, valueType
, pValue
) && m_pairs2
.GetVoidValue(name
, valueType
, pValue
);
6226 return m_pairs1
.GetVoidValue(name
, valueType
, pValue
) || m_pairs2
.GetVoidValue(name
, valueType
, pValue
);
6229 bool AlgorithmParametersBase::GetVoidValue(const char *name
, const std::type_info
&valueType
, void *pValue
) const
6231 if (strcmp(name
, "ValueNames") == 0)
6233 ThrowIfTypeMismatch(name
, typeid(std::string
), valueType
);
6234 GetParent().GetVoidValue(name
, valueType
, pValue
);
6235 (*reinterpret_cast<std::string
*>(pValue
) += m_name
) += ";";
6238 else if (strcmp(name
, m_name
) == 0)
6240 AssignValue(name
, valueType
, pValue
);
6245 return GetParent().GetVoidValue(name
, valueType
, pValue
);
6251 ////////////////////////////////////////////////////////////////////////////////
6255 ////////////////////////////////////////////////////////////////////////////////
6256 #ifndef CRYPTOPP_MQUEUE_H
6257 #define CRYPTOPP_MQUEUE_H
6259 //- #include "queue.h"
6260 //- #include "filters.h"
6263 NAMESPACE_BEGIN(CryptoPP
)
6266 class CRYPTOPP_DLL MessageQueue
: public AutoSignaling
<BufferedTransformation
>
6269 MessageQueue(unsigned int nodeSize
=256);
6271 void IsolatedInitialize(const NameValuePairs
¶meters
)
6272 {m_queue
.IsolatedInitialize(parameters
); m_lengths
.assign(1, 0U); m_messageCounts
.assign(1, 0U);}
6273 unsigned int Put2(const byte
*begin
, unsigned int length
, int messageEnd
, bool /* blocking */)
6275 m_queue
.Put(begin
, length
);
6276 m_lengths
.back() += length
;
6279 m_lengths
.push_back(0);
6280 m_messageCounts
.back()++;
6284 bool IsolatedFlush(bool /* hardFlush */, bool /* blocking */) {return false;}
6285 bool IsolatedMessageSeriesEnd(bool /* blocking */)
6286 {m_messageCounts
.push_back(0); return false;}
6288 unsigned long MaxRetrievable() const
6289 {return m_lengths
.front();}
6290 bool AnyRetrievable() const
6291 {return m_lengths
.front() > 0;}
6293 unsigned int TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
=NULL_CHANNEL
, bool blocking
=true);
6294 unsigned int CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
=ULONG_MAX
, const std::string
&channel
=NULL_CHANNEL
, bool blocking
=true) const;
6296 unsigned long TotalBytesRetrievable() const
6297 {return m_queue
.MaxRetrievable();}
6298 unsigned int NumberOfMessages() const
6299 {return m_lengths
.size()-1;}
6300 bool GetNextMessage();
6302 unsigned int NumberOfMessagesInThisSeries() const
6303 {return m_messageCounts
[0];}
6304 unsigned int NumberOfMessageSeries() const
6305 {return m_messageCounts
.size()-1;}
6307 unsigned int CopyMessagesTo(BufferedTransformation
&target
, unsigned int count
=UINT_MAX
, const std::string
&channel
=NULL_CHANNEL
) const;
6309 const byte
* Spy(unsigned int &contiguousSize
) const;
6311 void swap(MessageQueue
&rhs
);
6315 std::deque
<unsigned long> m_lengths
, m_messageCounts
;
6321 NAMESPACE_BEGIN(std
)
6322 template<> inline void swap(CryptoPP::MessageQueue
&a
, CryptoPP::MessageQueue
&b
)
6329 ////////////////////////////////////////////////////////////////////////////////
6333 ////////////////////////////////////////////////////////////////////////////////
6334 // mqueue.cpp - written and placed in the public domain by Wei Dai
6336 //- #include "pch.h"
6338 #ifndef CRYPTOPP_IMPORTS
6340 //- #include "mqueue.h"
6342 NAMESPACE_BEGIN(CryptoPP
)
6344 MessageQueue::MessageQueue(unsigned int nodeSize
)
6345 : m_queue(nodeSize
), m_lengths(1, 0U), m_messageCounts(1, 0U)
6349 unsigned int MessageQueue::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
6351 if (begin
>= MaxRetrievable())
6354 return m_queue
.CopyRangeTo2(target
, begin
, STDMIN(MaxRetrievable(), end
), channel
, blocking
);
6357 unsigned int MessageQueue::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
6359 transferBytes
= STDMIN(MaxRetrievable(), transferBytes
);
6360 unsigned int blockedBytes
= m_queue
.TransferTo2(target
, transferBytes
, channel
, blocking
);
6361 m_lengths
.front() -= transferBytes
;
6362 return blockedBytes
;
6365 bool MessageQueue::GetNextMessage()
6367 if (NumberOfMessages() > 0 && !AnyRetrievable())
6369 m_lengths
.pop_front();
6370 if (m_messageCounts
[0] == 0 && m_messageCounts
.size() > 1)
6371 m_messageCounts
.pop_front();
6378 unsigned int MessageQueue::CopyMessagesTo(BufferedTransformation
&target
, unsigned int count
, const std::string
&channel
) const
6380 ByteQueue::Walker
walker(m_queue
);
6381 std::deque
<unsigned long>::const_iterator it
= m_lengths
.begin();
6383 for (i
=0; i
<count
&& it
!= --m_lengths
.end(); ++i
, ++it
)
6385 walker
.TransferTo(target
, *it
, channel
);
6386 if (GetAutoSignalPropagation())
6387 target
.ChannelMessageEnd(channel
, GetAutoSignalPropagation()-1);
6392 void MessageQueue::swap(MessageQueue
&rhs
)
6394 m_queue
.swap(rhs
.m_queue
);
6395 m_lengths
.swap(rhs
.m_lengths
);
6398 const byte
* MessageQueue::Spy(unsigned int &contiguousSize
) const
6400 const byte
*result
= m_queue
.Spy(contiguousSize
);
6401 contiguousSize
= (unsigned int)STDMIN((unsigned long)contiguousSize
, MaxRetrievable());
6408 ////////////////////////////////////////////////////////////////////////////////
6412 ////////////////////////////////////////////////////////////////////////////////
6413 // filters.cpp - written and placed in the public domain by Wei Dai
6415 //- #include "pch.h"
6417 #ifndef CRYPTOPP_IMPORTS
6419 //- #include "filters.h"
6420 //- #include "mqueue.h"
6421 //- #include "fltrimpl.h"
6422 //- #include "argnames.h"
6424 #include <functional>
6426 NAMESPACE_BEGIN(CryptoPP
)
6428 Filter::Filter(BufferedTransformation
*attachment
)
6429 : m_attachment(attachment
), m_continueAt(0)
6433 BufferedTransformation
* Filter::NewDefaultAttachment() const
6435 return new MessageQueue
;
6438 BufferedTransformation
* Filter::AttachedTransformation()
6440 if (m_attachment
.get() == NULL
)
6441 m_attachment
.reset(NewDefaultAttachment());
6442 return m_attachment
.get();
6445 const BufferedTransformation
*Filter::AttachedTransformation() const
6447 if (m_attachment
.get() == NULL
)
6448 const_cast<Filter
*>(this)->m_attachment
.reset(NewDefaultAttachment());
6449 return m_attachment
.get();
6452 void Filter::Detach(BufferedTransformation
*newOut
)
6454 m_attachment
.reset(newOut
);
6457 void Filter::Insert(Filter
*filter
)
6459 filter
->m_attachment
.reset(m_attachment
.release());
6460 m_attachment
.reset(filter
);
6463 unsigned int Filter::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
6465 return AttachedTransformation()->CopyRangeTo2(target
, begin
, end
, channel
, blocking
);
6468 unsigned int Filter::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
6470 return AttachedTransformation()->TransferTo2(target
, transferBytes
, channel
, blocking
);
6473 void Filter::Initialize(const NameValuePairs
¶meters
, int propagation
)
6476 IsolatedInitialize(parameters
);
6477 PropagateInitialize(parameters
, propagation
);
6480 bool Filter::Flush(bool hardFlush
, int propagation
, bool blocking
)
6482 switch (m_continueAt
)
6485 if (IsolatedFlush(hardFlush
, blocking
))
6488 if (OutputFlush(1, hardFlush
, propagation
, blocking
))
6494 bool Filter::MessageSeriesEnd(int propagation
, bool blocking
)
6496 switch (m_continueAt
)
6499 if (IsolatedMessageSeriesEnd(blocking
))
6502 if (ShouldPropagateMessageSeriesEnd() && OutputMessageSeriesEnd(1, propagation
, blocking
))
6508 void Filter::PropagateInitialize(const NameValuePairs
¶meters
, int propagation
)
6511 AttachedTransformation()->Initialize(parameters
, propagation
-1);
6514 unsigned int Filter::OutputModifiable(int outputSite
, byte
*inString
, unsigned int length
, int messageEnd
, bool blocking
, const std::string
& /* channel */)
6518 unsigned int result
= AttachedTransformation()->PutModifiable2(inString
, length
, messageEnd
, blocking
);
6519 m_continueAt
= result
? outputSite
: 0;
6523 unsigned int Filter::Output(int outputSite
, const byte
*inString
, unsigned int length
, int messageEnd
, bool blocking
, const std::string
& /* channel */)
6527 unsigned int result
= AttachedTransformation()->Put2(inString
, length
, messageEnd
, blocking
);
6528 m_continueAt
= result
? outputSite
: 0;
6532 bool Filter::OutputFlush(int outputSite
, bool hardFlush
, int propagation
, bool blocking
, const std::string
&channel
)
6534 if (propagation
&& AttachedTransformation()->ChannelFlush(channel
, hardFlush
, propagation
-1, blocking
))
6536 m_continueAt
= outputSite
;
6543 bool Filter::OutputMessageSeriesEnd(int outputSite
, int propagation
, bool blocking
, const std::string
&channel
)
6545 if (propagation
&& AttachedTransformation()->ChannelMessageSeriesEnd(channel
, propagation
-1, blocking
))
6547 m_continueAt
= outputSite
;
6554 // *************************************************************
6556 void FilterWithBufferedInput::BlockQueue::ResetQueue(unsigned int blockSize
, unsigned int maxBlocks
)
6558 m_buffer
.New(blockSize
* maxBlocks
);
6559 m_blockSize
= blockSize
;
6560 m_maxBlocks
= maxBlocks
;
6565 byte
*FilterWithBufferedInput::BlockQueue::GetBlock()
6567 if (m_size
>= m_blockSize
)
6569 byte
*ptr
= m_begin
;
6570 if ((m_begin
+=m_blockSize
) == m_buffer
.end())
6572 m_size
-= m_blockSize
;
6579 byte
*FilterWithBufferedInput::BlockQueue::GetContigousBlocks(unsigned int &numberOfBytes
)
6581 numberOfBytes
= STDMIN(numberOfBytes
, STDMIN((unsigned int)(m_buffer
.end()-m_begin
), m_size
));
6582 byte
*ptr
= m_begin
;
6583 m_begin
+= numberOfBytes
;
6584 m_size
-= numberOfBytes
;
6585 if (m_size
== 0 || m_begin
== m_buffer
.end())
6590 unsigned int FilterWithBufferedInput::BlockQueue::GetAll(byte
*outString
)
6592 unsigned int size
= m_size
;
6593 unsigned int numberOfBytes
= m_maxBlocks
*m_blockSize
;
6594 const byte
*ptr
= GetContigousBlocks(numberOfBytes
);
6595 memcpy(outString
, ptr
, numberOfBytes
);
6596 memcpy(outString
+numberOfBytes
, m_begin
, m_size
);
6601 void FilterWithBufferedInput::BlockQueue::Put(const byte
*inString
, unsigned int length
)
6603 assert(m_size
+ length
<= m_buffer
.size());
6604 byte
*end
= (m_size
< (unsigned int)(m_buffer
.end()-m_begin
)) ? m_begin
+ m_size
: m_begin
+ m_size
- m_buffer
.size();
6605 unsigned int len
= STDMIN(length
, (unsigned int)(m_buffer
.end()-end
));
6606 memcpy(end
, inString
, len
);
6608 memcpy(m_buffer
, inString
+len
, length
-len
);
6612 FilterWithBufferedInput::FilterWithBufferedInput(BufferedTransformation
*attachment
)
6613 : Filter(attachment
)
6617 FilterWithBufferedInput::FilterWithBufferedInput(unsigned int firstSize
, unsigned int blockSize
, unsigned int lastSize
, BufferedTransformation
*attachment
)
6618 : Filter(attachment
), m_firstSize(firstSize
), m_blockSize(blockSize
), m_lastSize(lastSize
)
6619 , m_firstInputDone(false)
6621 if (m_blockSize
< 1)
6622 throw InvalidArgument("FilterWithBufferedInput: invalid buffer size");
6624 m_queue
.ResetQueue(1, m_firstSize
);
6627 void FilterWithBufferedInput::IsolatedInitialize(const NameValuePairs
¶meters
)
6629 InitializeDerivedAndReturnNewSizes(parameters
, m_firstSize
, m_blockSize
, m_lastSize
);
6630 if (m_blockSize
< 1)
6631 throw InvalidArgument("FilterWithBufferedInput: invalid buffer size");
6632 m_queue
.ResetQueue(1, m_firstSize
);
6633 m_firstInputDone
= false;
6636 bool FilterWithBufferedInput::IsolatedFlush(bool hardFlush
, bool blocking
)
6639 throw BlockingInputOnly("FilterWithBufferedInput");
6648 unsigned int FilterWithBufferedInput::PutMaybeModifiable(byte
*inString
, unsigned int length
, int messageEnd
, bool blocking
, bool modifiable
)
6651 throw BlockingInputOnly("FilterWithBufferedInput");
6655 unsigned int newLength
= m_queue
.CurrentSize() + length
;
6657 if (!m_firstInputDone
&& newLength
>= m_firstSize
)
6659 unsigned int len
= m_firstSize
- m_queue
.CurrentSize();
6660 m_queue
.Put(inString
, len
);
6661 FirstPut(m_queue
.GetContigousBlocks(m_firstSize
));
6662 assert(m_queue
.CurrentSize() == 0);
6663 m_queue
.ResetQueue(m_blockSize
, (2*m_blockSize
+m_lastSize
-2)/m_blockSize
);
6666 newLength
-= m_firstSize
;
6667 m_firstInputDone
= true;
6670 if (m_firstInputDone
)
6672 if (m_blockSize
== 1)
6674 while (newLength
> m_lastSize
&& m_queue
.CurrentSize() > 0)
6676 unsigned int len
= newLength
- m_lastSize
;
6677 byte
*ptr
= m_queue
.GetContigousBlocks(len
);
6678 NextPutModifiable(ptr
, len
);
6682 if (newLength
> m_lastSize
)
6684 unsigned int len
= newLength
- m_lastSize
;
6685 NextPutMaybeModifiable(inString
, len
, modifiable
);
6692 while (newLength
>= m_blockSize
+ m_lastSize
&& m_queue
.CurrentSize() >= m_blockSize
)
6694 NextPutModifiable(m_queue
.GetBlock(), m_blockSize
);
6695 newLength
-= m_blockSize
;
6698 if (newLength
>= m_blockSize
+ m_lastSize
&& m_queue
.CurrentSize() > 0)
6700 assert(m_queue
.CurrentSize() < m_blockSize
);
6701 unsigned int len
= m_blockSize
- m_queue
.CurrentSize();
6702 m_queue
.Put(inString
, len
);
6704 NextPutModifiable(m_queue
.GetBlock(), m_blockSize
);
6705 newLength
-= m_blockSize
;
6708 if (newLength
>= m_blockSize
+ m_lastSize
)
6710 unsigned int len
= RoundDownToMultipleOf(newLength
- m_lastSize
, m_blockSize
);
6711 NextPutMaybeModifiable(inString
, len
, modifiable
);
6718 m_queue
.Put(inString
, newLength
- m_queue
.CurrentSize());
6723 if (!m_firstInputDone
&& m_firstSize
==0)
6726 SecByteBlock
temp(m_queue
.CurrentSize());
6727 m_queue
.GetAll(temp
);
6728 LastPut(temp
, temp
.size());
6730 m_firstInputDone
= false;
6731 m_queue
.ResetQueue(1, m_firstSize
);
6733 Output(1, NULL
, 0, messageEnd
, blocking
);
6738 void FilterWithBufferedInput::ForceNextPut()
6740 if (!m_firstInputDone
)
6743 if (m_blockSize
> 1)
6745 while (m_queue
.CurrentSize() >= m_blockSize
)
6746 NextPutModifiable(m_queue
.GetBlock(), m_blockSize
);
6751 while ((len
= m_queue
.CurrentSize()) > 0)
6752 NextPutModifiable(m_queue
.GetContigousBlocks(len
), len
);
6756 void FilterWithBufferedInput::NextPutMultiple(const byte
*inString
, unsigned int length
)
6758 assert(m_blockSize
> 1); // m_blockSize = 1 should always override this function
6761 assert(length
>= m_blockSize
);
6762 NextPutSingle(inString
);
6763 inString
+= m_blockSize
;
6764 length
-= m_blockSize
;
6768 // *************************************************************
6770 ProxyFilter::ProxyFilter(BufferedTransformation
*filter
, unsigned int firstSize
, unsigned int lastSize
, BufferedTransformation
*attachment
)
6771 : FilterWithBufferedInput(firstSize
, 1, lastSize
, attachment
), m_filter(filter
)
6774 m_filter
->Attach(new OutputProxy(*this, false));
6777 bool ProxyFilter::IsolatedFlush(bool hardFlush
, bool blocking
)
6779 return m_filter
.get() ? m_filter
->Flush(hardFlush
, -1, blocking
) : false;
6782 void ProxyFilter::SetFilter(Filter
*filter
)
6784 m_filter
.reset(filter
);
6788 std::auto_ptr
<OutputProxy
> temp(proxy
= new OutputProxy(*this, false));
6789 m_filter
->TransferAllTo(*proxy
);
6790 m_filter
->Attach(temp
.release());
6794 void ProxyFilter::NextPutMultiple(const byte
*s
, unsigned int len
)
6797 m_filter
->Put(s
, len
);
6800 void ProxyFilter::NextPutModifiable(byte
*s
, unsigned int len
)
6803 m_filter
->PutModifiable(s
, len
);
6806 // *************************************************************
6808 unsigned int ArraySink::Put2(const byte
*begin
, unsigned int length
, int /* messageEnd */, bool /* blocking */)
6810 memcpy(m_buf
+m_total
, begin
, STDMIN(length
, SaturatingSubtract(m_size
, m_total
)));
6815 byte
* ArraySink::CreatePutSpace(unsigned int &size
)
6817 size
= m_size
- m_total
;
6818 return m_buf
+ m_total
;
6821 void ArraySink::IsolatedInitialize(const NameValuePairs
¶meters
)
6823 ByteArrayParameter array
;
6824 if (!parameters
.GetValue(Name::OutputBuffer(), array
))
6825 throw InvalidArgument("ArraySink: missing OutputBuffer argument");
6826 m_buf
= array
.begin();
6827 m_size
= array
.size();
6831 unsigned int ArrayXorSink::Put2(const byte
*begin
, unsigned int length
, int /* messageEnd */, bool /* blocking */)
6833 xorbuf(m_buf
+m_total
, begin
, STDMIN(length
, SaturatingSubtract(m_size
, m_total
)));
6838 // *************************************************************
6840 void HashFilter::IsolatedInitialize(const NameValuePairs
¶meters
)
6842 m_putMessage
= parameters
.GetValueWithDefault(Name::PutMessage(), false);
6843 m_hashModule
.Restart();
6846 unsigned int HashFilter::Put2(const byte
*inString
, unsigned int length
, int messageEnd
, bool blocking
)
6849 m_hashModule
.Update(inString
, length
);
6851 FILTER_OUTPUT(1, inString
, length
, 0);
6855 unsigned int size
, digestSize
= m_hashModule
.DigestSize();
6856 m_space
= HelpCreatePutSpace(*AttachedTransformation(), NULL_CHANNEL
, digestSize
, digestSize
, size
= digestSize
);
6857 m_hashModule
.Final(m_space
);
6859 FILTER_OUTPUT(2, m_space
, m_hashModule
.DigestSize(), messageEnd
);
6861 FILTER_END_NO_MESSAGE_END
;
6864 // *************************************************************
6866 unsigned int Source::PumpAll2(bool blocking
)
6868 // TODO: switch length type
6869 unsigned long i
= UINT_MAX
;
6870 RETURN_IF_NONZERO(Pump2(i
, blocking
));
6871 unsigned int j
= UINT_MAX
;
6872 return PumpMessages2(j
, blocking
);
6875 bool Store::GetNextMessage()
6877 if (!m_messageEnd
&& !AnyRetrievable())
6886 unsigned int Store::CopyMessagesTo(BufferedTransformation
&target
, unsigned int count
, const std::string
&channel
) const
6888 if (m_messageEnd
|| count
== 0)
6892 CopyTo(target
, ULONG_MAX
, channel
);
6893 if (GetAutoSignalPropagation())
6894 target
.ChannelMessageEnd(channel
, GetAutoSignalPropagation()-1);
6899 void StringStore::StoreInitialize(const NameValuePairs
¶meters
)
6901 ConstByteArrayParameter array
;
6902 if (!parameters
.GetValue(Name::InputBuffer(), array
))
6903 throw InvalidArgument("StringStore: missing InputBuffer argument");
6904 m_store
= array
.begin();
6905 m_length
= array
.size();
6909 unsigned int StringStore::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
6911 unsigned long position
= 0;
6912 unsigned int blockedBytes
= CopyRangeTo2(target
, position
, transferBytes
, channel
, blocking
);
6913 m_count
+= position
;
6914 transferBytes
= position
;
6915 return blockedBytes
;
6918 unsigned int StringStore::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
6920 unsigned int i
= (unsigned int)STDMIN((unsigned long)m_count
+begin
, (unsigned long)m_length
);
6921 unsigned int len
= (unsigned int)STDMIN((unsigned long)m_length
-i
, end
-begin
);
6922 unsigned int blockedBytes
= target
.ChannelPut2(channel
, m_store
+i
, len
, 0, blocking
);
6925 return blockedBytes
;
6932 ////////////////////////////////////////////////////////////////////////////////
6936 ////////////////////////////////////////////////////////////////////////////////
6937 // pubkey.cpp - written and placed in the public domain by Wei Dai
6939 //- #include "pch.h"
6941 #ifndef CRYPTOPP_IMPORTS
6943 //- #include "pubkey.h"
6945 NAMESPACE_BEGIN(CryptoPP
)
6947 void P1363_MGF1KDF2_Common(HashTransformation
&hash
, byte
*output
, unsigned int outputLength
, const byte
*input
, unsigned int inputLength
, const byte
*derivationParams
, unsigned int derivationParamsLength
, bool mask
, unsigned int counterStart
)
6950 HashFilter
filter(hash
, sink
= mask
? new ArrayXorSink(output
, outputLength
) : new ArraySink(output
, outputLength
));
6951 word32 counter
= counterStart
;
6952 while (sink
->AvailableSize() > 0)
6954 filter
.Put(input
, inputLength
);
6955 filter
.PutWord32(counter
++);
6956 filter
.Put(derivationParams
, derivationParamsLength
);
6957 filter
.MessageEnd();
6961 bool PK_DeterministicSignatureMessageEncodingMethod::VerifyMessageRepresentative(
6962 HashTransformation
&hash
, HashIdentifier hashIdentifier
, bool messageEmpty
,
6963 byte
*representative
, unsigned int representativeBitLength
) const
6965 SecByteBlock
computedRepresentative(BitsToBytes(representativeBitLength
));
6966 ComputeMessageRepresentative(NullRNG(), NULL
, 0, hash
, hashIdentifier
, messageEmpty
, computedRepresentative
, representativeBitLength
);
6967 return memcmp(representative
, computedRepresentative
, computedRepresentative
.size()) == 0;
6970 void TF_SignerBase::InputRecoverableMessage(PK_MessageAccumulator
&messageAccumulator
, const byte
*recoverableMessage
, unsigned int recoverableMessageLength
) const
6972 PK_MessageAccumulatorBase
&ma
= static_cast<PK_MessageAccumulatorBase
&>(messageAccumulator
);
6973 const MessageEncodingInterface
&mei
= GetMessageEncodingInterface();
6974 unsigned int maxRecoverableLength
= mei
.MaxRecoverableLength(MessageRepresentativeBitLength(), GetHashIdentifier().second
, ma
.AccessHash().DigestSize());
6976 if (maxRecoverableLength
== 0)
6977 {throw NotImplemented("TF_SignerBase: this algorithm does not support message recovery or the key is too short");}
6978 if (recoverableMessageLength
> maxRecoverableLength
)
6979 throw InvalidArgument("TF_SignerBase: the recoverable message part is too long for the given key and algorithm");
6981 ma
.m_recoverableMessage
.Assign(recoverableMessage
, recoverableMessageLength
);
6982 mei
.ProcessRecoverableMessage(
6984 recoverableMessage
, recoverableMessageLength
,
6985 NULL
, 0, ma
.m_semisignature
);
6988 unsigned int TF_SignerBase::SignAndRestart(RandomNumberGenerator
&rng
, PK_MessageAccumulator
&messageAccumulator
, byte
*signature
, bool /* restart */) const
6990 PK_MessageAccumulatorBase
&ma
= static_cast<PK_MessageAccumulatorBase
&>(messageAccumulator
);
6991 SecByteBlock
representative(MessageRepresentativeLength());
6992 GetMessageEncodingInterface().ComputeMessageRepresentative(rng
,
6993 ma
.m_recoverableMessage
, ma
.m_recoverableMessage
.size(),
6994 ma
.AccessHash(), GetHashIdentifier(), ma
.m_empty
,
6995 representative
, MessageRepresentativeBitLength());
6998 Integer
r(representative
, representative
.size());
6999 unsigned int signatureLength
= SignatureLength();
7000 GetTrapdoorFunctionInterface().CalculateRandomizedInverse(rng
, r
).Encode(signature
, signatureLength
);
7001 return signatureLength
;
7004 void TF_VerifierBase::InputSignature(PK_MessageAccumulator
&messageAccumulator
, const byte
*signature
, unsigned int signatureLength
) const
7006 PK_MessageAccumulatorBase
&ma
= static_cast<PK_MessageAccumulatorBase
&>(messageAccumulator
);
7007 ma
.m_representative
.New(MessageRepresentativeLength());
7008 Integer x
= GetTrapdoorFunctionInterface().ApplyFunction(Integer(signature
, signatureLength
));
7009 if (x
.BitCount() > MessageRepresentativeBitLength())
7010 x
= Integer::Zero(); // don't return false here to prevent timing attack
7011 x
.Encode(ma
.m_representative
, ma
.m_representative
.size());
7014 bool TF_VerifierBase::VerifyAndRestart(PK_MessageAccumulator
&messageAccumulator
) const
7016 PK_MessageAccumulatorBase
&ma
= static_cast<PK_MessageAccumulatorBase
&>(messageAccumulator
);
7017 bool result
= GetMessageEncodingInterface().VerifyMessageRepresentative(
7018 ma
.AccessHash(), GetHashIdentifier(), ma
.m_empty
, ma
.m_representative
, MessageRepresentativeBitLength());
7023 DecodingResult
TF_VerifierBase::RecoverAndRestart(byte
*recoveredMessage
, PK_MessageAccumulator
&messageAccumulator
) const
7025 PK_MessageAccumulatorBase
&ma
= static_cast<PK_MessageAccumulatorBase
&>(messageAccumulator
);
7026 DecodingResult result
= GetMessageEncodingInterface().RecoverMessageFromRepresentative(
7027 ma
.AccessHash(), GetHashIdentifier(), ma
.m_empty
, ma
.m_representative
, MessageRepresentativeBitLength(), recoveredMessage
);
7035 ////////////////////////////////////////////////////////////////////////////////
7039 ////////////////////////////////////////////////////////////////////////////////
7040 // iterhash.cpp - written and placed in the public domain by Wei Dai
7042 //- #include "pch.h"
7043 //- #include "iterhash.h"
7044 //- #include "misc.h"
7046 NAMESPACE_BEGIN(CryptoPP
)
7048 template <class T
, class BASE
> void IteratedHashBase
<T
, BASE
>::Update(const byte
*input
, unsigned int len
)
7050 HashWordType tmp
= m_countLo
;
7051 if ((m_countLo
= tmp
+ len
) < tmp
)
7052 m_countHi
++; // carry from low to high
7053 m_countHi
+= SafeRightShift
<8*sizeof(HashWordType
)>(len
);
7055 unsigned int blockSize
= BlockSize();
7056 unsigned int num
= ModPowerOf2(tmp
, blockSize
);
7058 if (num
!= 0) // process left over data
7060 if ((num
+len
) >= blockSize
)
7062 memcpy((byte
*)m_data
.begin()+num
, input
, blockSize
-num
);
7064 input
+= (blockSize
-num
);
7065 len
-=(blockSize
- num
);
7067 // drop through and do the rest
7071 memcpy((byte
*)m_data
.begin()+num
, input
, len
);
7076 // now process the input data in blocks of blockSize bytes and save the leftovers to m_data
7077 if (len
>= blockSize
)
7079 if (input
== (byte
*)m_data
.begin())
7081 assert(len
== blockSize
);
7085 else if (IsAligned
<T
>(input
))
7087 unsigned int leftOver
= HashMultipleBlocks((T
*)input
, len
);
7088 input
+= (len
- leftOver
);
7093 { // copy input first if it's not aligned correctly
7094 memcpy(m_data
, input
, blockSize
);
7098 } while (len
>= blockSize
);
7101 memcpy(m_data
, input
, len
);
7104 template <class T
, class BASE
> byte
* IteratedHashBase
<T
, BASE
>::CreateUpdateSpace(unsigned int &size
)
7106 unsigned int blockSize
= BlockSize();
7107 unsigned int num
= ModPowerOf2(m_countLo
, blockSize
);
7108 size
= blockSize
- num
;
7109 return (byte
*)m_data
.begin() + num
;
7112 template <class T
, class BASE
> unsigned int IteratedHashBase
<T
, BASE
>::HashMultipleBlocks(const T
*input
, unsigned int length
)
7114 unsigned int blockSize
= BlockSize();
7118 input
+= blockSize
/sizeof(T
);
7119 length
-= blockSize
;
7121 while (length
>= blockSize
);
7125 template <class T
, class BASE
> void IteratedHashBase
<T
, BASE
>::PadLastBlock(unsigned int lastBlockSize
, byte padFirst
)
7127 unsigned int blockSize
= BlockSize();
7128 unsigned int num
= ModPowerOf2(m_countLo
, blockSize
);
7129 ((byte
*)m_data
.begin())[num
++]=padFirst
;
7130 if (num
<= lastBlockSize
)
7131 memset((byte
*)m_data
.begin()+num
, 0, lastBlockSize
-num
);
7134 memset((byte
*)m_data
.begin()+num
, 0, blockSize
-num
);
7136 memset(m_data
, 0, lastBlockSize
);
7140 template <class T
, class BASE
> void IteratedHashBase
<T
, BASE
>::Restart()
7142 m_countLo
= m_countHi
= 0;
7147 ////////////////////////////////////////////////////////////////////////////////
7151 ////////////////////////////////////////////////////////////////////////////////
7152 // sha.cpp - modified by Wei Dai from Steve Reid's public domain sha1.c
7154 // Steve Reid implemented SHA-1. Wei Dai implemented SHA-2.
7155 // Both are in the public domain.
7157 //- #include "pch.h"
7158 //- #include "sha.h"
7159 //- #include "misc.h"
7161 NAMESPACE_BEGIN(CryptoPP
)
7163 // start of Steve Reid's code
7165 #define blk0(i) (W[i] = data[i])
7166 #define blk1(i) (W[i&15] = rotlFixed(W[(i+13)&15]^W[(i+8)&15]^W[(i+2)&15]^W[i&15],1))
7168 #ifndef CRYPTOPP_IMPORTS
7170 void SHA::InitState(HashWordType
*state
)
7172 state
[0] = 0x67452301L
;
7173 state
[1] = 0xEFCDAB89L
;
7174 state
[2] = 0x98BADCFEL
;
7175 state
[3] = 0x10325476L
;
7176 state
[4] = 0xC3D2E1F0L
;
7179 #define f1(x,y,z) (z^(x&(y^z)))
7180 #define f2(x,y,z) (x^y^z)
7181 #define f3(x,y,z) ((x&y)|(z&(x|y)))
7182 #define f4(x,y,z) (x^y^z)
7184 /* (R0+R1), R2, R3, R4 are the different operations used in SHA1 */
7185 #define R0(v,w,x,y,z,i) z+=f1(w,x,y)+blk0(i)+0x5A827999+rotlFixed(v,5);w=rotlFixed(w,30);
7186 #define R1(v,w,x,y,z,i) z+=f1(w,x,y)+blk1(i)+0x5A827999+rotlFixed(v,5);w=rotlFixed(w,30);
7187 #define R2(v,w,x,y,z,i) z+=f2(w,x,y)+blk1(i)+0x6ED9EBA1+rotlFixed(v,5);w=rotlFixed(w,30);
7188 #define R3(v,w,x,y,z,i) z+=f3(w,x,y)+blk1(i)+0x8F1BBCDC+rotlFixed(v,5);w=rotlFixed(w,30);
7189 #define R4(v,w,x,y,z,i) z+=f4(w,x,y)+blk1(i)+0xCA62C1D6+rotlFixed(v,5);w=rotlFixed(w,30);
7191 void SHA::Transform(word32
*state
, const word32
*data
)
7194 /* Copy context->state[] to working vars */
7195 word32 a
= state
[0];
7196 word32 b
= state
[1];
7197 word32 c
= state
[2];
7198 word32 d
= state
[3];
7199 word32 e
= state
[4];
7200 /* 4 rounds of 20 operations each. Loop unrolled. */
7201 R0(a
,b
,c
,d
,e
, 0); R0(e
,a
,b
,c
,d
, 1); R0(d
,e
,a
,b
,c
, 2); R0(c
,d
,e
,a
,b
, 3);
7202 R0(b
,c
,d
,e
,a
, 4); R0(a
,b
,c
,d
,e
, 5); R0(e
,a
,b
,c
,d
, 6); R0(d
,e
,a
,b
,c
, 7);
7203 R0(c
,d
,e
,a
,b
, 8); R0(b
,c
,d
,e
,a
, 9); R0(a
,b
,c
,d
,e
,10); R0(e
,a
,b
,c
,d
,11);
7204 R0(d
,e
,a
,b
,c
,12); R0(c
,d
,e
,a
,b
,13); R0(b
,c
,d
,e
,a
,14); R0(a
,b
,c
,d
,e
,15);
7205 R1(e
,a
,b
,c
,d
,16); R1(d
,e
,a
,b
,c
,17); R1(c
,d
,e
,a
,b
,18); R1(b
,c
,d
,e
,a
,19);
7206 R2(a
,b
,c
,d
,e
,20); R2(e
,a
,b
,c
,d
,21); R2(d
,e
,a
,b
,c
,22); R2(c
,d
,e
,a
,b
,23);
7207 R2(b
,c
,d
,e
,a
,24); R2(a
,b
,c
,d
,e
,25); R2(e
,a
,b
,c
,d
,26); R2(d
,e
,a
,b
,c
,27);
7208 R2(c
,d
,e
,a
,b
,28); R2(b
,c
,d
,e
,a
,29); R2(a
,b
,c
,d
,e
,30); R2(e
,a
,b
,c
,d
,31);
7209 R2(d
,e
,a
,b
,c
,32); R2(c
,d
,e
,a
,b
,33); R2(b
,c
,d
,e
,a
,34); R2(a
,b
,c
,d
,e
,35);
7210 R2(e
,a
,b
,c
,d
,36); R2(d
,e
,a
,b
,c
,37); R2(c
,d
,e
,a
,b
,38); R2(b
,c
,d
,e
,a
,39);
7211 R3(a
,b
,c
,d
,e
,40); R3(e
,a
,b
,c
,d
,41); R3(d
,e
,a
,b
,c
,42); R3(c
,d
,e
,a
,b
,43);
7212 R3(b
,c
,d
,e
,a
,44); R3(a
,b
,c
,d
,e
,45); R3(e
,a
,b
,c
,d
,46); R3(d
,e
,a
,b
,c
,47);
7213 R3(c
,d
,e
,a
,b
,48); R3(b
,c
,d
,e
,a
,49); R3(a
,b
,c
,d
,e
,50); R3(e
,a
,b
,c
,d
,51);
7214 R3(d
,e
,a
,b
,c
,52); R3(c
,d
,e
,a
,b
,53); R3(b
,c
,d
,e
,a
,54); R3(a
,b
,c
,d
,e
,55);
7215 R3(e
,a
,b
,c
,d
,56); R3(d
,e
,a
,b
,c
,57); R3(c
,d
,e
,a
,b
,58); R3(b
,c
,d
,e
,a
,59);
7216 R4(a
,b
,c
,d
,e
,60); R4(e
,a
,b
,c
,d
,61); R4(d
,e
,a
,b
,c
,62); R4(c
,d
,e
,a
,b
,63);
7217 R4(b
,c
,d
,e
,a
,64); R4(a
,b
,c
,d
,e
,65); R4(e
,a
,b
,c
,d
,66); R4(d
,e
,a
,b
,c
,67);
7218 R4(c
,d
,e
,a
,b
,68); R4(b
,c
,d
,e
,a
,69); R4(a
,b
,c
,d
,e
,70); R4(e
,a
,b
,c
,d
,71);
7219 R4(d
,e
,a
,b
,c
,72); R4(c
,d
,e
,a
,b
,73); R4(b
,c
,d
,e
,a
,74); R4(a
,b
,c
,d
,e
,75);
7220 R4(e
,a
,b
,c
,d
,76); R4(d
,e
,a
,b
,c
,77); R4(c
,d
,e
,a
,b
,78); R4(b
,c
,d
,e
,a
,79);
7221 /* Add the working vars back into context.state[] */
7227 /* Wipe variables */
7228 a
= b
= c
= d
= e
= 0;
7229 memset(W
, 0, sizeof(W
));
7232 #endif // #ifndef CRYPTOPP_IMPORTS
7234 // end of Steve Reid's code
7236 // *************************************************************
7239 ////////////////////////////////////////////////////////////////////////////////
7243 ////////////////////////////////////////////////////////////////////////////////
7244 // pkcspad.cpp - written and placed in the public domain by Wei Dai
7246 //- #include "pch.h"
7248 //- #include "pkcspad.h"
7251 NAMESPACE_BEGIN(CryptoPP
)
7253 template<> const byte PKCS_DigestDecoration
<SHA
>::decoration
[] = {0x30,0x21,0x30,0x09,0x06,0x05,0x2B,0x0E,0x03,0x02,0x1A,0x05,0x00,0x04,0x14};
7254 template<> const unsigned int PKCS_DigestDecoration
<SHA
>::length
= sizeof(PKCS_DigestDecoration
<SHA
>::decoration
);
7256 unsigned int PKCS_EncryptionPaddingScheme::MaxUnpaddedLength(unsigned int paddedLength
) const
7258 return SaturatingSubtract(paddedLength
/8, 10U);
7261 void PKCS_EncryptionPaddingScheme::Pad(RandomNumberGenerator
&rng
, const byte
*input
, unsigned int inputLen
, byte
*pkcsBlock
, unsigned int pkcsBlockLen
, const NameValuePairs
& /* parameters */) const
7263 assert (inputLen
<= MaxUnpaddedLength(pkcsBlockLen
)); // this should be checked by caller
7265 // convert from bit length to byte length
7266 if (pkcsBlockLen
% 8 != 0)
7273 pkcsBlock
[0] = 2; // block type 2
7275 // pad with non-zero random bytes
7276 for (unsigned i
= 1; i
< pkcsBlockLen
-inputLen
-1; i
++)
7277 pkcsBlock
[i
] = (byte
)rng
.GenerateWord32(1, 0xff);
7279 pkcsBlock
[pkcsBlockLen
-inputLen
-1] = 0; // separator
7280 memcpy(pkcsBlock
+pkcsBlockLen
-inputLen
, input
, inputLen
);
7283 DecodingResult
PKCS_EncryptionPaddingScheme::Unpad(const byte
*pkcsBlock
, unsigned int pkcsBlockLen
, byte
*output
, const NameValuePairs
& /* parameters */) const
7285 bool invalid
= false;
7286 unsigned int maxOutputLen
= MaxUnpaddedLength(pkcsBlockLen
);
7288 // convert from bit length to byte length
7289 if (pkcsBlockLen
% 8 != 0)
7291 invalid
= (pkcsBlock
[0] != 0) || invalid
;
7296 // Require block type 2.
7297 invalid
= (pkcsBlock
[0] != 2) || invalid
;
7299 // skip past the padding until we find the separator
7301 while (i
<pkcsBlockLen
&& pkcsBlock
[i
++]) { // null body
7303 assert(i
==pkcsBlockLen
|| pkcsBlock
[i
-1]==0);
7305 unsigned int outputLen
= pkcsBlockLen
- i
;
7306 invalid
= (outputLen
> maxOutputLen
) || invalid
;
7309 return DecodingResult();
7311 memcpy (output
, pkcsBlock
+i
, outputLen
);
7312 return DecodingResult(outputLen
);
7315 // ********************************************************
7317 #ifndef CRYPTOPP_IMPORTS
7319 void PKCS1v15_SignatureMessageEncodingMethod::ComputeMessageRepresentative(RandomNumberGenerator
& /* rng */,
7320 const byte
* /* recoverableMessage */, unsigned int /* recoverableMessageLength */,
7321 HashTransformation
&hash
, HashIdentifier hashIdentifier
, bool /* messageEmpty */,
7322 byte
*representative
, unsigned int representativeBitLength
) const
7324 unsigned int digestSize
= hash
.DigestSize();
7325 if (digestSize
+ hashIdentifier
.second
+ 10 > representativeBitLength
/8)
7326 throw PK_Signer::KeyTooShort();
7328 unsigned int pkcsBlockLen
= representativeBitLength
;
7329 // convert from bit length to byte length
7330 if (pkcsBlockLen
% 8 != 0)
7332 representative
[0] = 0;
7337 representative
[0] = 1; // block type 1
7339 byte
*pPadding
= representative
+ 1;
7340 byte
*pDigest
= representative
+ pkcsBlockLen
- digestSize
;
7341 byte
*pHashId
= pDigest
- hashIdentifier
.second
;
7342 byte
*pSeparator
= pHashId
- 1;
7345 memset(pPadding
, 0xff, pSeparator
-pPadding
);
7347 memcpy(pHashId
, hashIdentifier
.first
, hashIdentifier
.second
);
7348 hash
.Final(pDigest
);
7354 ////////////////////////////////////////////////////////////////////////////////
7358 ////////////////////////////////////////////////////////////////////////////////
7359 // asn.cpp - written and placed in the public domain by Wei Dai
7361 //- #include "pch.h"
7363 #ifndef CRYPTOPP_IMPORTS
7365 //- #include "asn.h"
7370 NAMESPACE_BEGIN(CryptoPP
)
7371 USING_NAMESPACE(std
)
7374 unsigned int DERLengthEncode(BufferedTransformation
&bt
, unsigned int length
)
7379 bt
.Put(byte(length
));
7384 bt
.Put(byte(BytePrecision(length
) | 0x80));
7386 for (int j
=BytePrecision(length
); j
; --j
)
7388 bt
.Put(byte(length
>> (j
-1)*8));
7395 bool BERLengthDecode(BufferedTransformation
&bt
, unsigned int &length
, bool &definiteLength
)
7404 definiteLength
= true;
7409 unsigned int lengthBytes
= b
& 0x7f;
7411 if (lengthBytes
== 0)
7413 definiteLength
= false;
7417 definiteLength
= true;
7419 while (lengthBytes
--)
7421 if (length
>> (8*(sizeof(length
)-1)))
7422 BERDecodeError(); // length about to overflow
7427 length
= (length
<< 8) | b
;
7433 bool BERLengthDecode(BufferedTransformation
&bt
, unsigned int &length
)
7435 bool definiteLength
;
7436 if (!BERLengthDecode(bt
, length
, definiteLength
))
7438 return definiteLength
;
7441 void DEREncodeNull(BufferedTransformation
&out
)
7447 void BERDecodeNull(BufferedTransformation
&in
)
7450 if (!in
.Get(b
) || b
!= TAG_NULL
)
7452 unsigned int length
;
7453 if (!BERLengthDecode(in
, length
) || length
!= 0)
7458 unsigned int DEREncodeOctetString(BufferedTransformation
&bt
, const byte
*str
, unsigned int strLen
)
7460 bt
.Put(OCTET_STRING
);
7461 unsigned int lengthBytes
= DERLengthEncode(bt
, strLen
);
7462 bt
.Put(str
, strLen
);
7463 return 1+lengthBytes
+strLen
;
7466 unsigned int DEREncodeOctetString(BufferedTransformation
&bt
, const SecByteBlock
&str
)
7468 return DEREncodeOctetString(bt
, str
.begin(), str
.size());
7471 void DERReencode(BufferedTransformation
&source
, BufferedTransformation
&dest
)
7475 BERGeneralDecoder
decoder(source
, tag
);
7476 DERGeneralEncoder
encoder(dest
, tag
);
7477 if (decoder
.IsDefiniteLength())
7478 decoder
.TransferTo(encoder
, decoder
.RemainingLength());
7481 while (!decoder
.EndReached())
7482 DERReencode(decoder
, encoder
);
7484 decoder
.MessageEnd();
7485 encoder
.MessageEnd();
7488 void OID::EncodeValue(BufferedTransformation
&bt
, unsigned long v
)
7490 for (unsigned int i
=RoundUpToMultipleOf(STDMAX(7U,BitPrecision(v
)), 7U)-7; i
!= 0; i
-=7)
7491 bt
.Put((byte
)(0x80 | ((v
>> i
) & 0x7f)));
7492 bt
.Put((byte
)(v
& 0x7f));
7495 unsigned int OID::DecodeValue(BufferedTransformation
&bt
, unsigned long &v
)
7512 void OID::DEREncode(BufferedTransformation
&bt
) const
7514 assert(m_values
.size() >= 2);
7516 temp
.Put(byte(m_values
[0] * 40 + m_values
[1]));
7517 for (unsigned int i
=2; i
<m_values
.size(); i
++)
7518 EncodeValue(temp
, m_values
[i
]);
7519 bt
.Put(OBJECT_IDENTIFIER
);
7520 DERLengthEncode(bt
, temp
.CurrentSize());
7521 temp
.TransferTo(bt
);
7524 void OID::BERDecode(BufferedTransformation
&bt
)
7527 if (!bt
.Get(b
) || b
!= OBJECT_IDENTIFIER
)
7530 unsigned int length
;
7531 if (!BERLengthDecode(bt
, length
) || length
< 1)
7539 m_values
[0] = b
/ 40;
7540 m_values
[1] = b
% 40;
7545 unsigned int valueLen
= DecodeValue(bt
, v
);
7546 if (valueLen
> length
)
7548 m_values
.push_back(v
);
7553 void OID::BERDecodeAndCheck(BufferedTransformation
&bt
) const
7560 BERGeneralDecoder::BERGeneralDecoder(BufferedTransformation
&inQueue
, byte asnTag
)
7561 : m_inQueue(inQueue
), m_finished(false)
7566 BERGeneralDecoder::BERGeneralDecoder(BERGeneralDecoder
&inQueue
, byte asnTag
)
7567 : m_inQueue(inQueue
), m_finished(false)
7572 void BERGeneralDecoder::Init(byte asnTag
)
7575 if (!m_inQueue
.Get(b
) || b
!= asnTag
)
7578 m_definiteLength
= BERLengthDecode(m_inQueue
, m_length
);
7579 if (!m_definiteLength
&& !(asnTag
& CONSTRUCTED
))
7580 BERDecodeError(); // cannot be primitive and have indefinite length
7583 BERGeneralDecoder::~BERGeneralDecoder()
7585 try // avoid throwing in constructor
7595 bool BERGeneralDecoder::EndReached() const
7597 if (m_definiteLength
)
7598 return m_length
== 0;
7600 { // check end-of-content octets
7602 return (m_inQueue
.PeekWord16(i
)==2 && i
==0);
7606 byte
BERGeneralDecoder::PeekByte() const
7614 void BERGeneralDecoder::CheckByte(byte check
)
7617 if (!Get(b
) || b
!= check
)
7621 void BERGeneralDecoder::MessageEnd()
7624 if (m_definiteLength
)
7630 { // remove end-of-content octets
7632 if (m_inQueue
.GetWord16(i
) != 2 || i
!= 0)
7637 unsigned int BERGeneralDecoder::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
7639 if (m_definiteLength
&& transferBytes
> m_length
)
7640 transferBytes
= m_length
;
7641 unsigned int blockedBytes
= m_inQueue
.TransferTo2(target
, transferBytes
, channel
, blocking
);
7642 ReduceLength(transferBytes
);
7643 return blockedBytes
;
7646 unsigned int BERGeneralDecoder::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
7648 if (m_definiteLength
)
7649 end
= STDMIN((unsigned long)m_length
, end
);
7650 return m_inQueue
.CopyRangeTo2(target
, begin
, end
, channel
, blocking
);
7653 unsigned int BERGeneralDecoder::ReduceLength(unsigned int delta
)
7655 if (m_definiteLength
)
7657 if (m_length
< delta
)
7664 DERGeneralEncoder::DERGeneralEncoder(BufferedTransformation
&outQueue
, byte asnTag
)
7665 : m_outQueue(outQueue
), m_finished(false), m_asnTag(asnTag
)
7669 DERGeneralEncoder::DERGeneralEncoder(DERGeneralEncoder
&outQueue
, byte asnTag
)
7670 : ByteQueue(), m_outQueue(outQueue
), m_finished(false), m_asnTag(asnTag
)
7674 DERGeneralEncoder::~DERGeneralEncoder()
7676 try // avoid throwing in constructor
7686 void DERGeneralEncoder::MessageEnd()
7689 unsigned int length
= (unsigned int)CurrentSize();
7690 m_outQueue
.Put(m_asnTag
);
7691 DERLengthEncode(m_outQueue
, length
);
7692 TransferTo(m_outQueue
);
7695 // *************************************************************
7697 void X509PublicKey::BERDecode(BufferedTransformation
&bt
)
7699 BERSequenceDecoder
subjectPublicKeyInfo(bt
);
7700 BERSequenceDecoder
algorithm(subjectPublicKeyInfo
);
7701 GetAlgorithmID().BERDecodeAndCheck(algorithm
);
7702 bool parametersPresent
= algorithm
.EndReached() ? false : BERDecodeAlgorithmParameters(algorithm
);
7703 algorithm
.MessageEnd();
7705 BERGeneralDecoder
subjectPublicKey(subjectPublicKeyInfo
, BIT_STRING
);
7706 subjectPublicKey
.CheckByte(0); // unused bits
7707 BERDecodeKey2(subjectPublicKey
, parametersPresent
, subjectPublicKey
.RemainingLength());
7708 subjectPublicKey
.MessageEnd();
7709 subjectPublicKeyInfo
.MessageEnd();
7712 void X509PublicKey::DEREncode(BufferedTransformation
&bt
) const
7714 DERSequenceEncoder
subjectPublicKeyInfo(bt
);
7716 DERSequenceEncoder
algorithm(subjectPublicKeyInfo
);
7717 GetAlgorithmID().DEREncode(algorithm
);
7718 DEREncodeAlgorithmParameters(algorithm
);
7719 algorithm
.MessageEnd();
7721 DERGeneralEncoder
subjectPublicKey(subjectPublicKeyInfo
, BIT_STRING
);
7722 subjectPublicKey
.Put(0); // unused bits
7723 DEREncodeKey(subjectPublicKey
);
7724 subjectPublicKey
.MessageEnd();
7726 subjectPublicKeyInfo
.MessageEnd();
7729 void PKCS8PrivateKey::BERDecode(BufferedTransformation
&bt
)
7731 BERSequenceDecoder
privateKeyInfo(bt
);
7733 BERDecodeUnsigned
<word32
>(privateKeyInfo
, version
, INTEGER
, 0, 0); // check version
7735 BERSequenceDecoder
algorithm(privateKeyInfo
);
7736 GetAlgorithmID().BERDecodeAndCheck(algorithm
);
7737 bool parametersPresent
= BERDecodeAlgorithmParameters(algorithm
);
7738 algorithm
.MessageEnd();
7740 BERGeneralDecoder
octetString(privateKeyInfo
, OCTET_STRING
);
7741 BERDecodeKey2(octetString
, parametersPresent
, privateKeyInfo
.RemainingLength());
7742 octetString
.MessageEnd();
7744 if (!privateKeyInfo
.EndReached())
7745 BERDecodeOptionalAttributes(privateKeyInfo
);
7746 privateKeyInfo
.MessageEnd();
7749 void PKCS8PrivateKey::DEREncode(BufferedTransformation
&bt
) const
7751 DERSequenceEncoder
privateKeyInfo(bt
);
7752 DEREncodeUnsigned
<word32
>(privateKeyInfo
, 0); // version
7754 DERSequenceEncoder
algorithm(privateKeyInfo
);
7755 GetAlgorithmID().DEREncode(algorithm
);
7756 DEREncodeAlgorithmParameters(algorithm
);
7757 algorithm
.MessageEnd();
7759 DERGeneralEncoder
octetString(privateKeyInfo
, OCTET_STRING
);
7760 DEREncodeKey(octetString
);
7761 octetString
.MessageEnd();
7763 DEREncodeOptionalAttributes(privateKeyInfo
);
7764 privateKeyInfo
.MessageEnd();
7767 void PKCS8PrivateKey::BERDecodeOptionalAttributes(BufferedTransformation
&bt
)
7769 DERReencode(bt
, m_optionalAttributes
);
7772 void PKCS8PrivateKey::DEREncodeOptionalAttributes(BufferedTransformation
&bt
) const
7774 m_optionalAttributes
.CopyTo(bt
);
7780 ////////////////////////////////////////////////////////////////////////////////
7784 ////////////////////////////////////////////////////////////////////////////////
7785 // rsa.cpp - written and placed in the public domain by Wei Dai
7787 //- #include "pch.h"
7788 //- #include "rsa.h"
7789 //- #include "asn.h"
7790 //- #include "oids.h"
7791 //- #include "modarith.h"
7792 //- #include "nbtheory.h"
7793 //- #include "sha.h"
7794 //- #include "algparam.h"
7795 //- #include "fips140.h"
7797 #ifndef CRYPTOPP_IMPORTS
7799 NAMESPACE_BEGIN(CryptoPP
)
7801 OID
RSAFunction::GetAlgorithmID() const
7803 return ASN1::rsaEncryption();
7806 void RSAFunction::BERDecodeKey(BufferedTransformation
&bt
)
7808 BERSequenceDecoder
seq(bt
);
7814 void RSAFunction::DEREncodeKey(BufferedTransformation
&bt
) const
7816 DERSequenceEncoder
seq(bt
);
7822 Integer
RSAFunction::ApplyFunction(const Integer
&x
) const
7824 DoQuickSanityCheck();
7825 return a_exp_b_mod_c(x
, m_e
, m_n
);
7828 bool RSAFunction::Validate(RandomNumberGenerator
& /* rng */, unsigned int /* level */) const
7831 pass
= pass
&& m_n
> Integer::One() && m_n
.IsOdd();
7832 pass
= pass
&& m_e
> Integer::One() && m_e
.IsOdd() && m_e
< m_n
;
7836 bool RSAFunction::GetVoidValue(const char *name
, const std::type_info
&valueType
, void *pValue
) const
7838 return GetValueHelper(this, name
, valueType
, pValue
).Assignable()
7839 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus
)
7840 CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent
)
7844 void RSAFunction::AssignFrom(const NameValuePairs
&source
)
7846 AssignFromHelper(this, source
)
7847 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus
)
7848 CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent
)
7852 // *****************************************************************************
7854 class RSAPrimeSelector
: public PrimeSelector
7857 RSAPrimeSelector(const Integer
&e
) : m_e(e
) {}
7858 virtual ~RSAPrimeSelector() {};
7860 bool IsAcceptable(const Integer
&candidate
) const {return RelativelyPrime(m_e
, candidate
-Integer::One());}
7864 void InvertibleRSAFunction::GenerateRandom(RandomNumberGenerator
&rng
, const NameValuePairs
&alg
)
7866 int modulusSize
= 2048;
7867 alg
.GetIntValue(Name::ModulusSize(), modulusSize
) || alg
.GetIntValue(Name::KeySize(), modulusSize
);
7869 if (modulusSize
< 16)
7870 throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small");
7872 m_e
= alg
.GetValueWithDefault(Name::PublicExponent(), Integer(17));
7874 if (m_e
< 3 || m_e
.IsEven())
7875 throw InvalidArgument("InvertibleRSAFunction: invalid public exponent");
7877 RSAPrimeSelector
selector(m_e
);
7878 const NameValuePairs
&primeParam
= MakeParametersForTwoPrimesOfEqualSize(modulusSize
)
7879 (Name::PointerToPrimeSelector(), selector
.GetSelectorPointer());
7880 m_p
.GenerateRandom(rng
, primeParam
);
7881 m_q
.GenerateRandom(rng
, primeParam
);
7883 m_d
= EuclideanMultiplicativeInverse(m_e
, LCM(m_p
-1, m_q
-1));
7884 assert(m_d
.IsPositive());
7886 m_dp
= m_d
% (m_p
-1);
7887 m_dq
= m_d
% (m_q
-1);
7889 m_u
= m_q
.InverseMod(m_p
);
7893 void InvertibleRSAFunction::Initialize(RandomNumberGenerator
&rng
, unsigned int keybits
, const Integer
&e
)
7895 GenerateRandom(rng
, MakeParameters(Name::ModulusSize(), (int)keybits
)(Name::PublicExponent(), e
+e
.IsEven()));
7898 void InvertibleRSAFunction::Initialize(const Integer
&n
, const Integer
&e
, const Integer
&d
)
7900 if (n
.IsEven() || e
.IsEven() | d
.IsEven())
7901 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
7907 Integer r
= --(d
*e
);
7915 ModularArithmetic
modn(n
);
7916 for (Integer i
= 2; ; ++i
)
7918 Integer a
= modn
.Exponentiate(i
, r
);
7930 m_dp
= m_d
% (m_p
-1);
7931 m_dq
= m_d
% (m_q
-1);
7932 m_u
= m_q
.InverseMod(m_p
);
7936 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key");
7942 void InvertibleRSAFunction::BERDecodeKey(BufferedTransformation
&bt
)
7944 BERSequenceDecoder
privateKey(bt
);
7946 BERDecodeUnsigned
<word32
>(privateKey
, version
, INTEGER
, 0, 0); // check version
7947 m_n
.BERDecode(privateKey
);
7948 m_e
.BERDecode(privateKey
);
7949 m_d
.BERDecode(privateKey
);
7950 m_p
.BERDecode(privateKey
);
7951 m_q
.BERDecode(privateKey
);
7952 m_dp
.BERDecode(privateKey
);
7953 m_dq
.BERDecode(privateKey
);
7954 m_u
.BERDecode(privateKey
);
7955 privateKey
.MessageEnd();
7958 void InvertibleRSAFunction::DEREncodeKey(BufferedTransformation
&bt
) const
7960 DERSequenceEncoder
privateKey(bt
);
7961 DEREncodeUnsigned
<word32
>(privateKey
, 0); // version
7962 m_n
.DEREncode(privateKey
);
7963 m_e
.DEREncode(privateKey
);
7964 m_d
.DEREncode(privateKey
);
7965 m_p
.DEREncode(privateKey
);
7966 m_q
.DEREncode(privateKey
);
7967 m_dp
.DEREncode(privateKey
);
7968 m_dq
.DEREncode(privateKey
);
7969 m_u
.DEREncode(privateKey
);
7970 privateKey
.MessageEnd();
7973 Integer
InvertibleRSAFunction::CalculateInverse(RandomNumberGenerator
&rng
, const Integer
&x
) const
7975 DoQuickSanityCheck();
7976 ModularArithmetic
modn(m_n
);
7978 do { // do this loop for people using small numbers for testing
7979 r
.Randomize(rng
, Integer::One(), m_n
- Integer::One());
7980 rInv
= modn
.MultiplicativeInverse(r
);
7981 } while (rInv
.IsZero());
7982 Integer re
= modn
.Exponentiate(r
, m_e
);
7983 re
= modn
.Multiply(re
, x
); // blind
7984 // here we follow the notation of PKCS #1 and let u=q inverse mod p
7985 // but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
7986 Integer y
= ModularRoot(re
, m_dq
, m_dp
, m_q
, m_p
, m_u
);
7987 y
= modn
.Multiply(y
, rInv
); // unblind
7988 if (modn
.Exponentiate(y
, m_e
) != x
) // check
7989 throw Exception(Exception::OTHER_ERROR
, "InvertibleRSAFunction: computational error during private key operation");
7993 bool InvertibleRSAFunction::Validate(RandomNumberGenerator
&rng
, unsigned int level
) const
7995 bool pass
= RSAFunction::Validate(rng
, level
);
7996 pass
= pass
&& m_p
> Integer::One() && m_p
.IsOdd() && m_p
< m_n
;
7997 pass
= pass
&& m_q
> Integer::One() && m_q
.IsOdd() && m_q
< m_n
;
7998 pass
= pass
&& m_d
> Integer::One() && m_d
.IsOdd() && m_d
< m_n
;
7999 pass
= pass
&& m_dp
> Integer::One() && m_dp
.IsOdd() && m_dp
< m_p
;
8000 pass
= pass
&& m_dq
> Integer::One() && m_dq
.IsOdd() && m_dq
< m_q
;
8001 pass
= pass
&& m_u
.IsPositive() && m_u
< m_p
;
8004 pass
= pass
&& m_p
* m_q
== m_n
;
8005 pass
= pass
&& m_e
*m_d
% LCM(m_p
-1, m_q
-1) == 1;
8006 pass
= pass
&& m_dp
== m_d
%(m_p
-1) && m_dq
== m_d
%(m_q
-1);
8007 pass
= pass
&& m_u
* m_q
% m_p
== 1;
8010 pass
= pass
&& VerifyPrime(rng
, m_p
, level
-2) && VerifyPrime(rng
, m_q
, level
-2);
8014 bool InvertibleRSAFunction::GetVoidValue(const char *name
, const std::type_info
&valueType
, void *pValue
) const
8016 return GetValueHelper
<RSAFunction
>(this, name
, valueType
, pValue
).Assignable()
8017 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1
)
8018 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2
)
8019 CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent
)
8020 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent
)
8021 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent
)
8022 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1
)
8026 void InvertibleRSAFunction::AssignFrom(const NameValuePairs
&source
)
8028 AssignFromHelper
<RSAFunction
>(this, source
)
8029 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1
)
8030 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2
)
8031 CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent
)
8032 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent
)
8033 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent
)
8034 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1
)
8041 ////////////////////////////////////////////////////////////////////////////////
8045 ////////////////////////////////////////////////////////////////////////////////
8046 // basecode.cpp - written and placed in the public domain by Wei Dai
8048 //- #include "pch.h"
8050 #ifndef CRYPTOPP_IMPORTS
8052 //- #include "basecode.h"
8053 //- #include "fltrimpl.h"
8056 NAMESPACE_BEGIN(CryptoPP
)
8058 void BaseN_Encoder::IsolatedInitialize(const NameValuePairs
¶meters
)
8060 parameters
.GetRequiredParameter("BaseN_Encoder", Name::EncodingLookupArray(), m_alphabet
);
8062 parameters
.GetRequiredIntParameter("BaseN_Encoder", Name::Log2Base(), m_bitsPerChar
);
8063 if (m_bitsPerChar
<= 0 || m_bitsPerChar
>= 8)
8064 throw InvalidArgument("BaseN_Encoder: Log2Base must be between 1 and 7 inclusive");
8068 if (parameters
.GetValue(Name::PaddingByte(), padding
))
8069 pad
= parameters
.GetValueWithDefault(Name::Pad(), true);
8072 m_padding
= pad
? padding
: -1;
8074 m_bytePos
= m_bitPos
= 0;
8077 while (i
%m_bitsPerChar
!= 0)
8079 m_outputBlockSize
= i
/m_bitsPerChar
;
8081 m_outBuf
.New(m_outputBlockSize
);
8084 unsigned int BaseN_Encoder::Put2(const byte
*begin
, unsigned int length
, int messageEnd
, bool blocking
)
8087 while (m_inputPosition
< length
)
8090 memset(m_outBuf
, 0, m_outputBlockSize
);
8093 unsigned int b
= begin
[m_inputPosition
++], bitsLeftInSource
= 8;
8096 assert(m_bitPos
< m_bitsPerChar
);
8097 unsigned int bitsLeftInTarget
= m_bitsPerChar
-m_bitPos
;
8098 m_outBuf
[m_bytePos
] |= b
>> (8-bitsLeftInTarget
);
8099 if (bitsLeftInSource
>= bitsLeftInTarget
)
8103 bitsLeftInSource
-= bitsLeftInTarget
;
8104 if (bitsLeftInSource
== 0)
8106 b
<<= bitsLeftInTarget
;
8111 m_bitPos
+= bitsLeftInSource
;
8117 assert(m_bytePos
<= m_outputBlockSize
);
8118 if (m_bytePos
== m_outputBlockSize
)
8121 for (i
=0; i
<m_bytePos
; i
++)
8123 assert(m_outBuf
[i
] < (1 << m_bitsPerChar
));
8124 m_outBuf
[i
] = m_alphabet
[m_outBuf
[i
]];
8126 FILTER_OUTPUT(1, m_outBuf
, m_outputBlockSize
, 0);
8128 m_bytePos
= m_bitPos
= 0;
8137 for (i
=0; i
<m_bytePos
; i
++)
8138 m_outBuf
[i
] = m_alphabet
[m_outBuf
[i
]];
8140 if (m_padding
!= -1 && m_bytePos
> 0)
8142 memset(m_outBuf
+m_bytePos
, m_padding
, m_outputBlockSize
-m_bytePos
);
8143 m_bytePos
= m_outputBlockSize
;
8145 FILTER_OUTPUT(2, m_outBuf
, m_bytePos
, messageEnd
);
8146 m_bytePos
= m_bitPos
= 0;
8148 FILTER_END_NO_MESSAGE_END
;
8151 void BaseN_Decoder::IsolatedInitialize(const NameValuePairs
¶meters
)
8153 parameters
.GetRequiredParameter("BaseN_Decoder", Name::DecodingLookupArray(), m_lookup
);
8155 parameters
.GetRequiredIntParameter("BaseN_Decoder", Name::Log2Base(), m_bitsPerChar
);
8156 if (m_bitsPerChar
<= 0 || m_bitsPerChar
>= 8)
8157 throw InvalidArgument("BaseN_Decoder: Log2Base must be between 1 and 7 inclusive");
8159 m_bytePos
= m_bitPos
= 0;
8161 int i
= m_bitsPerChar
;
8164 m_outputBlockSize
= i
/8;
8166 m_outBuf
.New(m_outputBlockSize
);
8169 unsigned int BaseN_Decoder::Put2(const byte
*begin
, unsigned int length
, int messageEnd
, bool blocking
)
8172 while (m_inputPosition
< length
)
8175 value
= m_lookup
[begin
[m_inputPosition
++]];
8179 if (m_bytePos
== 0 && m_bitPos
== 0)
8180 memset(m_outBuf
, 0, m_outputBlockSize
);
8183 int newBitPos
= m_bitPos
+ m_bitsPerChar
;
8185 m_outBuf
[m_bytePos
] |= value
<< (8-newBitPos
);
8188 m_outBuf
[m_bytePos
] |= value
>> (newBitPos
-8);
8189 m_outBuf
[m_bytePos
+1] |= value
<< (16-newBitPos
);
8192 m_bitPos
= newBitPos
;
8193 while (m_bitPos
>= 8)
8200 if (m_bytePos
== m_outputBlockSize
)
8202 FILTER_OUTPUT(1, m_outBuf
, m_outputBlockSize
, 0);
8203 m_bytePos
= m_bitPos
= 0;
8208 FILTER_OUTPUT(2, m_outBuf
, m_bytePos
, messageEnd
);
8209 m_bytePos
= m_bitPos
= 0;
8211 FILTER_END_NO_MESSAGE_END
;
8214 void BaseN_Decoder::InitializeDecodingLookupArray(int *lookup
, const byte
*alphabet
, unsigned int base
, bool caseInsensitive
)
8216 std::fill(lookup
, lookup
+256, -1);
8218 for (unsigned int i
=0; i
<base
; i
++)
8220 if (caseInsensitive
&& isalpha(alphabet
[i
]))
8222 assert(lookup
[toupper(alphabet
[i
])] == -1);
8223 lookup
[toupper(alphabet
[i
])] = i
;
8224 assert(lookup
[tolower(alphabet
[i
])] == -1);
8225 lookup
[tolower(alphabet
[i
])] = i
;
8229 assert(lookup
[alphabet
[i
]] == -1);
8230 lookup
[alphabet
[i
]] = i
;
8235 void Grouper::IsolatedInitialize(const NameValuePairs
¶meters
)
8237 m_groupSize
= parameters
.GetIntValueWithDefault(Name::GroupSize(), 0);
8238 ConstByteArrayParameter separator
, terminator
;
8240 parameters
.GetRequiredParameter("Grouper", Name::Separator(), separator
);
8242 parameters
.GetValue(Name::Separator(), separator
);
8243 parameters
.GetValue(Name::Terminator(), terminator
);
8245 m_separator
.Assign(separator
.begin(), separator
.size());
8246 m_terminator
.Assign(terminator
.begin(), terminator
.size());
8250 unsigned int Grouper::Put2(const byte
*begin
, unsigned int length
, int messageEnd
, bool blocking
)
8255 while (m_inputPosition
< length
)
8257 if (m_counter
== m_groupSize
)
8259 FILTER_OUTPUT(1, m_separator
, m_separator
.size(), 0);
8264 FILTER_OUTPUT2(2, len
= STDMIN(length
-m_inputPosition
, m_groupSize
-m_counter
),
8265 begin
+m_inputPosition
, len
, 0);
8266 m_inputPosition
+= len
;
8271 FILTER_OUTPUT(3, begin
, length
, 0);
8275 FILTER_OUTPUT(4, m_terminator
, m_terminator
.size(), messageEnd
);
8278 FILTER_END_NO_MESSAGE_END
8284 ////////////////////////////////////////////////////////////////////////////////
8288 ////////////////////////////////////////////////////////////////////////////////
8289 // base64.cpp - written and placed in the public domain by Wei Dai
8291 //- #include "pch.h"
8292 //- #include "base64.h"
8294 NAMESPACE_BEGIN(CryptoPP
)
8296 static const byte s_vec
[] =
8297 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
8298 static const byte s_padding
= '=';
8300 void Base64Encoder::IsolatedInitialize(const NameValuePairs
¶meters
)
8302 bool insertLineBreaks
= parameters
.GetValueWithDefault(Name::InsertLineBreaks(), true);
8303 int maxLineLength
= parameters
.GetIntValueWithDefault(Name::MaxLineLength(), 72);
8305 const char *lineBreak
= insertLineBreaks
? "\n" : "";
8307 m_filter
->Initialize(CombinedNameValuePairs(
8309 MakeParameters(Name::EncodingLookupArray(), &s_vec
[0], false)
8310 (Name::PaddingByte(), s_padding
)
8311 (Name::GroupSize(), insertLineBreaks
? maxLineLength
: 0)
8312 (Name::Separator(), ConstByteArrayParameter(lineBreak
))
8313 (Name::Terminator(), ConstByteArrayParameter(lineBreak
))
8314 (Name::Log2Base(), 6, true)));
8317 const int *Base64Decoder::GetDecodingLookupArray()
8319 static bool s_initialized
= false;
8320 static int s_array
[256];
8324 InitializeDecodingLookupArray(s_array
, s_vec
, 64, false);
8325 s_initialized
= true;
8331 ////////////////////////////////////////////////////////////////////////////////
8335 ////////////////////////////////////////////////////////////////////////////////
8336 // files.cpp - written and placed in the public domain by Wei Dai
8338 //- #include "pch.h"
8340 #ifndef CRYPTOPP_IMPORTS
8342 //- #include "files.h"
8344 NAMESPACE_BEGIN(CryptoPP
)
8346 using namespace std
;
8348 void FileStore::StoreInitialize(const NameValuePairs
¶meters
)
8350 m_file
.reset(new std::ifstream
);
8351 const char *fileName
;
8352 if (parameters
.GetValue(Name::InputFileName(), fileName
))
8354 ios::openmode binary
= parameters
.GetValueWithDefault(Name::InputBinaryMode(), true) ? ios::binary
: ios::openmode(0);
8355 m_file
->open(fileName
, ios::in
| binary
);
8357 throw OpenErr(fileName
);
8358 m_stream
= m_file
.get();
8363 parameters
.GetValue(Name::InputStreamPointer(), m_stream
);
8368 unsigned long FileStore::MaxRetrievable() const
8373 streampos current
= m_stream
->tellg();
8374 streampos end
= m_stream
->seekg(0, ios::end
).tellg();
8375 m_stream
->seekg(current
);
8379 unsigned int FileStore::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
8387 unsigned long size
=transferBytes
;
8393 while (size
&& m_stream
->good())
8396 unsigned int spaceSize
= 1024;
8397 m_space
= HelpCreatePutSpace(target
, channel
, 1, (unsigned int)STDMIN(size
, (unsigned long)UINT_MAX
), spaceSize
);
8399 m_stream
->read((char *)m_space
, STDMIN(size
, (unsigned long)spaceSize
));
8401 m_len
= m_stream
->gcount();
8402 unsigned int blockedBytes
;
8404 blockedBytes
= target
.ChannelPutModifiable2(channel
, m_space
, m_len
, 0, blocking
);
8405 m_waiting
= blockedBytes
> 0;
8407 return blockedBytes
;
8409 transferBytes
+= m_len
;
8412 if (!m_stream
->good() && !m_stream
->eof())
8418 unsigned int FileStore::CopyRangeTo2(BufferedTransformation
&target
, unsigned long &begin
, unsigned long end
, const std::string
&channel
, bool blocking
) const
8423 if (begin
== 0 && end
== 1)
8425 int result
= m_stream
->peek();
8426 if (result
== EOF
) // GCC workaround: 2.95.2 doesn't have char_traits<char>::eof()
8430 unsigned int blockedBytes
= target
.ChannelPut(channel
, byte(result
), blocking
);
8431 begin
+= 1-blockedBytes
;
8432 return blockedBytes
;
8436 // TODO: figure out what happens on cin
8437 streampos current
= m_stream
->tellg();
8438 streampos endPosition
= m_stream
->seekg(0, ios::end
).tellg();
8439 streampos newPosition
= current
+ (streamoff
)begin
;
8441 if (newPosition
>= endPosition
)
8443 m_stream
->seekg(current
);
8444 return 0; // don't try to seek beyond the end of file
8446 m_stream
->seekg(newPosition
);
8450 unsigned long copyMax
= end
-begin
;
8451 unsigned int blockedBytes
= const_cast<FileStore
*>(this)->TransferTo2(target
, copyMax
, channel
, blocking
);
8455 const_cast<FileStore
*>(this)->m_waiting
= false;
8456 return blockedBytes
;
8462 m_stream
->seekg(current
);
8466 m_stream
->seekg(current
);
8471 unsigned long FileStore::Skip(unsigned long skipMax
)
8473 unsigned long oldPos
= m_stream
->tellg();
8474 m_stream
->seekg(skipMax
, ios::cur
);
8475 return (unsigned long)m_stream
->tellg() - oldPos
;
8478 void FileSink::IsolatedInitialize(const NameValuePairs
¶meters
)
8480 m_file
.reset(new std::ofstream
);
8481 const char *fileName
;
8482 if (parameters
.GetValue(Name::OutputFileName(), fileName
))
8484 ios::openmode binary
= parameters
.GetValueWithDefault(Name::OutputBinaryMode(), true) ? ios::binary
: ios::openmode(0);
8485 m_file
->open(fileName
, ios::out
| ios::trunc
| binary
);
8487 throw OpenErr(fileName
);
8488 m_stream
= m_file
.get();
8493 parameters
.GetValue(Name::OutputStreamPointer(), m_stream
);
8497 bool FileSink::IsolatedFlush(bool /* hardFlush */, bool /* blocking */)
8500 throw Err("FileSink: output stream not opened");
8503 if (!m_stream
->good())
8509 unsigned int FileSink::Put2(const byte
*inString
, unsigned int length
, int messageEnd
, bool /* blocking */)
8512 throw Err("FileSink: output stream not opened");
8514 m_stream
->write((const char *)inString
, length
);
8519 if (!m_stream
->good())
8528 ////////////////////////////////////////////////////////////////////////////////
8532 ////////////////////////////////////////////////////////////////////////////////
8533 // mdc.h - written and placed in the public domain by Wei Dai
8535 #ifndef CRYPTOPP_MDC_H
8536 #define CRYPTOPP_MDC_H
8541 //- #include "seckey.h"
8542 //- #include "misc.h"
8544 NAMESPACE_BEGIN(CryptoPP
)
8548 struct MDC_Info
: public FixedBlockSize
<T::DIGESTSIZE
>, public FixedKeyLength
<T::BLOCKSIZE
>
8550 static std::string
StaticAlgorithmName() {return std::string("MDC/")+T::StaticAlgorithmName();}
8553 //! <a href="http://www.weidai.com/scan-mirror/cs.html#MDC">MDC</a>
8554 /*! a construction by Peter Gutmann to turn an iterated hash function into a PRF */
8556 class MDC
: public MDC_Info
<T
>
8558 class CRYPTOPP_NO_VTABLE Enc
: public BlockCipherImpl
<MDC_Info
<T
> >
8560 typedef typename
T::HashWordType HashWordType
;
8563 void UncheckedSetKey(CipherDir direction
, const byte
*userKey
, unsigned int length
)
8565 assert(direction
== ENCRYPTION
);
8566 this->AssertValidKeyLength(length
);
8567 memcpy(Key(), userKey
, this->KEYLENGTH
);
8568 T::CorrectEndianess(Key(), Key(), this->KEYLENGTH
);
8571 void ProcessAndXorBlock(const byte
*inBlock
, const byte
*xorBlock
, byte
*outBlock
) const
8573 T::CorrectEndianess(Buffer(), (HashWordType
*)inBlock
, this->BLOCKSIZE
);
8574 T::Transform(Buffer(), Key());
8577 T::CorrectEndianess(Buffer(), Buffer(), this->BLOCKSIZE
);
8578 xorbuf(outBlock
, xorBlock
, m_buffer
, this->BLOCKSIZE
);
8581 T::CorrectEndianess((HashWordType
*)outBlock
, Buffer(), this->BLOCKSIZE
);
8584 bool IsPermutation() const {return false;}
8586 unsigned int GetAlignment() const {return sizeof(HashWordType
);}
8589 HashWordType
*Key() {return (HashWordType
*)m_key
.data();}
8590 const HashWordType
*Key() const {return (const HashWordType
*)m_key
.data();}
8591 HashWordType
*Buffer() const {return (HashWordType
*)m_buffer
.data();}
8593 // VC60 workaround: bug triggered if using FixedSizeAllocatorWithCleanup
8594 FixedSizeSecBlock
<byte
, MDC_Info
<T
>::KEYLENGTH
, AllocatorWithCleanup
<byte
> > m_key
;
8595 mutable FixedSizeSecBlock
<byte
, MDC_Info
<T
>::BLOCKSIZE
, AllocatorWithCleanup
<byte
> > m_buffer
;
8599 //! use BlockCipher interface
8600 typedef BlockCipherFinal
<ENCRYPTION
, Enc
> Encryption
;
8606 ////////////////////////////////////////////////////////////////////////////////
8610 ////////////////////////////////////////////////////////////////////////////////
8612 This file contains helper classes for implementing stream ciphers.
8614 All this infrastructure may look very complex compared to what's in Crypto++ 4.x,
8615 but stream ciphers implementations now support a lot of new functionality,
8616 including better performance (minimizing copying), resetting of keys and IVs, and methods to
8617 query which features are supported by a cipher.
8619 Here's an explanation of these classes. The word "policy" is used here to mean a class with a
8620 set of methods that must be implemented by individual stream cipher implementations.
8621 This is usually much simpler than the full stream cipher API, which is implemented by
8622 either AdditiveCipherTemplate or CFB_CipherTemplate using the policy. So for example, an
8623 implementation of SEAL only needs to implement the AdditiveCipherAbstractPolicy interface
8624 (since it's an additive cipher, i.e., it xors a keystream into the plaintext).
8625 See this line in seal.h:
8627 typedef SymmetricCipherFinal\<ConcretePolicyHolder\<SEAL_Policy\<B\>, AdditiveCipherTemplate\<\> \> \> Encryption;
8629 AdditiveCipherTemplate and CFB_CipherTemplate are designed so that they don't need
8630 to take a policy class as a template parameter (although this is allowed), so that
8631 their code is not duplicated for each new cipher. Instead they each
8632 get a reference to an abstract policy interface by calling AccessPolicy() on itself, so
8633 AccessPolicy() must be overriden to return the actual policy reference. This is done
8634 by the ConceretePolicyHolder class. Finally, SymmetricCipherFinal implements the constructors and
8635 other functions that must be implemented by the most derived class.
8638 #ifndef CRYPTOPP_STRCIPHR_H
8639 #define CRYPTOPP_STRCIPHR_H
8641 //- #include "seckey.h"
8642 //- #include "secblock.h"
8643 //- #include "argnames.h"
8645 NAMESPACE_BEGIN(CryptoPP
)
8647 template <class POLICY_INTERFACE
, class BASE
= Empty
>
8648 class CRYPTOPP_NO_VTABLE AbstractPolicyHolder
: public BASE
8651 typedef POLICY_INTERFACE PolicyInterface
;
8654 virtual const POLICY_INTERFACE
& GetPolicy() const =0;
8655 virtual POLICY_INTERFACE
& AccessPolicy() =0;
8658 template <class POLICY
, class BASE
, class POLICY_INTERFACE
= CPP_TYPENAME
BASE::PolicyInterface
>
8659 class ConcretePolicyHolder
: public BASE
, protected POLICY
8662 const POLICY_INTERFACE
& GetPolicy() const {return *this;}
8663 POLICY_INTERFACE
& AccessPolicy() {return *this;}
8666 enum KeystreamOperation
{WRITE_KEYSTREAM
, XOR_KEYSTREAM
, XOR_KEYSTREAM_INPLACE
};
8668 class CRYPTOPP_DLL CRYPTOPP_NO_VTABLE CFB_CipherAbstractPolicy
8671 virtual ~CFB_CipherAbstractPolicy() {};
8672 virtual unsigned int GetAlignment() const =0;
8673 virtual unsigned int GetBytesPerIteration() const =0;
8674 virtual byte
* GetRegisterBegin() =0;
8675 virtual void TransformRegister() =0;
8676 virtual bool CanIterate() const {return false;}
8677 virtual void Iterate(byte
* /* output */, const byte
* /* input */, CipherDir
/* dir */, unsigned int /* iterationCount */) {assert(false);}
8678 virtual void CipherSetKey(const NameValuePairs
¶ms
, const byte
*key
, unsigned int length
) =0;
8679 virtual void CipherResynchronize(const byte
* /* iv */) {throw NotImplemented("StreamTransformation: this object doesn't support resynchronization");}
8682 template <class BASE
>
8683 class CRYPTOPP_NO_VTABLE CFB_CipherTemplate
: public BASE
8686 void ProcessData(byte
*outString
, const byte
*inString
, unsigned int length
);
8687 void Resynchronize(const byte
*iv
);
8688 unsigned int OptimalBlockSize() const {return this->GetPolicy().GetBytesPerIteration();}
8689 unsigned int GetOptimalNextBlockSize() const {return m_leftOver
;}
8690 unsigned int OptimalDataAlignment() const {return this->GetPolicy().GetAlignment();}
8691 bool IsRandomAccess() const {return false;}
8692 bool IsSelfInverting() const {return false;}
8694 typedef typename
BASE::PolicyInterface PolicyInterface
;
8697 virtual void CombineMessageAndShiftRegister(byte
*output
, byte
*reg
, const byte
*message
, unsigned int length
) =0;
8699 void UncheckedSetKey(const NameValuePairs
¶ms
, const byte
*key
, unsigned int length
, const byte
*iv
);
8701 unsigned int m_leftOver
;
8704 template <class BASE
= AbstractPolicyHolder
<CFB_CipherAbstractPolicy
, SymmetricCipher
> >
8705 class CRYPTOPP_NO_VTABLE CFB_EncryptionTemplate
: public CFB_CipherTemplate
<BASE
>
8707 bool IsForwardTransformation() const {return true;}
8708 void CombineMessageAndShiftRegister(byte
*output
, byte
*reg
, const byte
*message
, unsigned int length
);
8711 template <class BASE
= AbstractPolicyHolder
<CFB_CipherAbstractPolicy
, SymmetricCipher
> >
8712 class CRYPTOPP_NO_VTABLE CFB_DecryptionTemplate
: public CFB_CipherTemplate
<BASE
>
8714 bool IsForwardTransformation() const {return false;}
8715 void CombineMessageAndShiftRegister(byte
*output
, byte
*reg
, const byte
*message
, unsigned int length
);
8718 template <class BASE
>
8719 void CFB_CipherTemplate
<BASE
>::UncheckedSetKey(const NameValuePairs
¶ms
, const byte
*key
, unsigned int length
, const byte
*iv
)
8721 PolicyInterface
&policy
= this->AccessPolicy();
8722 policy
.CipherSetKey(params
, key
, length
);
8724 if (this->IsResynchronizable())
8725 policy
.CipherResynchronize(iv
);
8727 m_leftOver
= policy
.GetBytesPerIteration();
8733 ////////////////////////////////////////////////////////////////////////////////
8737 ////////////////////////////////////////////////////////////////////////////////
8738 // strciphr.cpp - written and placed in the public domain by Wei Dai
8740 //- #include "pch.h"
8742 #ifndef CRYPTOPP_IMPORTS
8744 //- #include "strciphr.h"
8746 NAMESPACE_BEGIN(CryptoPP
)
8748 template <class BASE
>
8749 void CFB_CipherTemplate
<BASE
>::Resynchronize(const byte
*iv
)
8751 PolicyInterface
&policy
= this->AccessPolicy();
8752 policy
.CipherResynchronize(iv
);
8753 m_leftOver
= policy
.GetBytesPerIteration();
8756 template <class BASE
>
8757 void CFB_CipherTemplate
<BASE
>::ProcessData(byte
*outString
, const byte
*inString
, unsigned int length
)
8759 assert(length
% this->MandatoryBlockSize() == 0);
8761 PolicyInterface
&policy
= this->AccessPolicy();
8762 unsigned int bytesPerIteration
= policy
.GetBytesPerIteration();
8763 unsigned int alignment
= policy
.GetAlignment();
8764 byte
*reg
= policy
.GetRegisterBegin();
8768 unsigned int len
= STDMIN(m_leftOver
, length
);
8769 CombineMessageAndShiftRegister(outString
, reg
+ bytesPerIteration
- m_leftOver
, inString
, len
);
8779 assert(m_leftOver
== 0);
8781 if (policy
.CanIterate() && length
>= bytesPerIteration
&& IsAlignedOn(outString
, alignment
))
8783 if (IsAlignedOn(inString
, alignment
))
8784 policy
.Iterate(outString
, inString
, GetCipherDir(*this), length
/ bytesPerIteration
);
8787 memcpy(outString
, inString
, length
);
8788 policy
.Iterate(outString
, outString
, GetCipherDir(*this), length
/ bytesPerIteration
);
8790 inString
+= length
- length
% bytesPerIteration
;
8791 outString
+= length
- length
% bytesPerIteration
;
8792 length
%= bytesPerIteration
;
8795 while (length
>= bytesPerIteration
)
8797 policy
.TransformRegister();
8798 CombineMessageAndShiftRegister(outString
, reg
, inString
, bytesPerIteration
);
8799 length
-= bytesPerIteration
;
8800 inString
+= bytesPerIteration
;
8801 outString
+= bytesPerIteration
;
8806 policy
.TransformRegister();
8807 CombineMessageAndShiftRegister(outString
, reg
, inString
, length
);
8808 m_leftOver
= bytesPerIteration
- length
;
8812 template <class BASE
>
8813 void CFB_EncryptionTemplate
<BASE
>::CombineMessageAndShiftRegister(byte
*output
, byte
*reg
, const byte
*message
, unsigned int length
)
8815 xorbuf(reg
, message
, length
);
8816 memcpy(output
, reg
, length
);
8819 template <class BASE
>
8820 void CFB_DecryptionTemplate
<BASE
>::CombineMessageAndShiftRegister(byte
*output
, byte
*reg
, const byte
*message
, unsigned int length
)
8822 for (unsigned int i
=0; i
<length
; i
++)
8824 byte b
= message
[i
];
8825 output
[i
] = reg
[i
] ^ b
;
8833 ////////////////////////////////////////////////////////////////////////////////
8837 ////////////////////////////////////////////////////////////////////////////////
8838 #ifndef CRYPTOPP_MODES_H
8839 #define CRYPTOPP_MODES_H
8844 //- #include "cryptlib.h"
8845 //- #include "secblock.h"
8846 //- #include "misc.h"
8847 //- #include "strciphr.h"
8848 //- #include "argnames.h"
8849 //- #include "algparam.h"
8851 NAMESPACE_BEGIN(CryptoPP
)
8853 //! Cipher mode documentation. See NIST SP 800-38A for definitions of these modes.
8855 /*! Each class derived from this one defines two types, Encryption and Decryption,
8856 both of which implement the SymmetricCipher interface.
8857 For each mode there are two classes, one of which is a template class,
8858 and the other one has a name that ends in "_ExternalCipher".
8859 The "external cipher" mode objects hold a reference to the underlying block cipher,
8860 instead of holding an instance of it. The reference must be passed in to the constructor.
8861 For the "cipher holder" classes, the CIPHER template parameter should be a class
8862 derived from BlockCipherDocumentation, for example DES or AES.
8864 struct CipherModeDocumentation
: public SymmetricCipherDocumentation
8868 class CRYPTOPP_DLL CRYPTOPP_NO_VTABLE CipherModeBase
: public SymmetricCipher
8871 unsigned int MinKeyLength() const {return m_cipher
->MinKeyLength();}
8872 unsigned int MaxKeyLength() const {return m_cipher
->MaxKeyLength();}
8873 unsigned int DefaultKeyLength() const {return m_cipher
->DefaultKeyLength();}
8874 unsigned int GetValidKeyLength(unsigned int n
) const {return m_cipher
->GetValidKeyLength(n
);}
8875 bool IsValidKeyLength(unsigned int n
) const {return m_cipher
->IsValidKeyLength(n
);}
8877 void SetKey(const byte
*key
, unsigned int length
, const NameValuePairs
¶ms
= g_nullNameValuePairs
);
8879 unsigned int OptimalDataAlignment() const {return BlockSize();}
8881 unsigned int IVSize() const {return BlockSize();}
8882 void GetNextIV(byte
*IV
);
8883 virtual IV_Requirement
IVRequirement() const =0;
8886 inline unsigned int BlockSize() const {assert(m_register
.size() > 0); return m_register
.size();}
8887 virtual void SetFeedbackSize(unsigned int feedbackSize
)
8889 if (!(feedbackSize
== 0 || feedbackSize
== BlockSize()))
8890 throw InvalidArgument("CipherModeBase: feedback size cannot be specified for this cipher mode");
8892 virtual void ResizeBuffers()
8894 m_register
.New(m_cipher
->BlockSize());
8896 virtual void UncheckedSetKey(const NameValuePairs
¶ms
, const byte
*key
, unsigned int length
, const byte
*iv
) =0;
8898 BlockCipher
*m_cipher
;
8899 SecByteBlock m_register
;
8902 template <class POLICY_INTERFACE
>
8903 class CRYPTOPP_NO_VTABLE ModePolicyCommonTemplate
: public CipherModeBase
, public POLICY_INTERFACE
8905 unsigned int GetAlignment() const {return m_cipher
->BlockAlignment();}
8906 void CipherSetKey(const NameValuePairs
¶ms
, const byte
*key
, unsigned int length
);
8909 template <class POLICY_INTERFACE
>
8910 void ModePolicyCommonTemplate
<POLICY_INTERFACE
>::CipherSetKey(const NameValuePairs
¶ms
, const byte
*key
, unsigned int length
)
8912 m_cipher
->SetKey(key
, length
, params
);
8914 int feedbackSize
= params
.GetIntValueWithDefault(Name::FeedbackSize(), 0);
8915 SetFeedbackSize(feedbackSize
);
8918 class CRYPTOPP_DLL CRYPTOPP_NO_VTABLE CFB_ModePolicy
: public ModePolicyCommonTemplate
<CFB_CipherAbstractPolicy
>
8921 IV_Requirement
IVRequirement() const {return RANDOM_IV
;}
8922 static const char *StaticAlgorithmName() {return "CFB";}
8925 unsigned int GetBytesPerIteration() const {return m_feedbackSize
;}
8926 byte
* GetRegisterBegin() {return m_register
+ BlockSize() - m_feedbackSize
;}
8927 void TransformRegister()
8929 m_cipher
->ProcessBlock(m_register
, m_temp
);
8930 memmove(m_register
, m_register
+m_feedbackSize
, BlockSize()-m_feedbackSize
);
8931 memcpy(m_register
+BlockSize()-m_feedbackSize
, m_temp
, m_feedbackSize
);
8933 void CipherResynchronize(const byte
*iv
)
8935 memcpy(m_register
, iv
, BlockSize());
8936 TransformRegister();
8938 void SetFeedbackSize(unsigned int feedbackSize
)
8940 if (feedbackSize
> BlockSize())
8941 throw InvalidArgument("CFB_Mode: invalid feedback size");
8942 m_feedbackSize
= feedbackSize
? feedbackSize
: BlockSize();
8944 void ResizeBuffers()
8946 CipherModeBase::ResizeBuffers();
8947 m_temp
.New(BlockSize());
8950 SecByteBlock m_temp
;
8951 unsigned int m_feedbackSize
;
8955 template <class CIPHER
, class BASE
>
8956 class CipherModeFinalTemplate_CipherHolder
: protected ObjectHolder
<CIPHER
>, public AlgorithmImpl
<BASE
, CipherModeFinalTemplate_CipherHolder
<CIPHER
, BASE
> >
8959 CipherModeFinalTemplate_CipherHolder()
8961 this->m_cipher
= &this->m_object
;
8962 this->ResizeBuffers();
8964 CipherModeFinalTemplate_CipherHolder(const byte
*key
, unsigned int length
)
8966 this->m_cipher
= &this->m_object
;
8967 this->SetKey(key
, length
);
8969 CipherModeFinalTemplate_CipherHolder(const byte
*key
, unsigned int length
, const byte
*iv
)
8971 this->m_cipher
= &this->m_object
;
8972 this->SetKey(key
, length
, MakeParameters(Name::IV(), iv
));
8974 CipherModeFinalTemplate_CipherHolder(const byte
*key
, unsigned int length
, const byte
*iv
, int feedbackSize
)
8976 this->m_cipher
= &this->m_object
;
8977 this->SetKey(key
, length
, MakeParameters(Name::IV(), iv
)(Name::FeedbackSize(), feedbackSize
));
8980 static std::string
StaticAlgorithmName()
8981 {return CIPHER::StaticAlgorithmName() + "/" + BASE::StaticAlgorithmName();}
8985 template <class CIPHER
>
8986 struct CFB_Mode
: public CipherModeDocumentation
8988 typedef CipherModeFinalTemplate_CipherHolder
<CPP_TYPENAME
CIPHER::Encryption
, ConcretePolicyHolder
<Empty
, CFB_EncryptionTemplate
<AbstractPolicyHolder
<CFB_CipherAbstractPolicy
, CFB_ModePolicy
> > > > Encryption
;
8989 typedef CipherModeFinalTemplate_CipherHolder
<CPP_TYPENAME
CIPHER::Encryption
, ConcretePolicyHolder
<Empty
, CFB_DecryptionTemplate
<AbstractPolicyHolder
<CFB_CipherAbstractPolicy
, CFB_ModePolicy
> > > > Decryption
;
8995 ////////////////////////////////////////////////////////////////////////////////
8999 ////////////////////////////////////////////////////////////////////////////////
9000 // modes.cpp - written and placed in the public domain by Wei Dai
9002 //- #include "pch.h"
9004 #ifndef CRYPTOPP_IMPORTS
9006 //- #include "modes.h"
9008 NAMESPACE_BEGIN(CryptoPP
)
9010 void CipherModeBase::SetKey(const byte
*key
, unsigned int length
, const NameValuePairs
¶ms
)
9012 UncheckedSetKey(params
, key
, length
, GetIVAndThrowIfInvalid(params
)); // the underlying cipher will check the key length
9015 void CipherModeBase::GetNextIV(byte
*IV
)
9017 if (!IsForwardTransformation())
9018 throw NotImplemented("CipherModeBase: GetNextIV() must be called on an encryption object");
9020 m_cipher
->ProcessBlock(m_register
);
9021 memcpy(IV
, m_register
, BlockSize());
9027 ////////////////////////////////////////////////////////////////////////////////
9031 ////////////////////////////////////////////////////////////////////////////////
9032 // randpool.cpp - written and placed in the public domain by Wei Dai
9033 // The algorithm in this module comes from PGP's randpool.c
9035 //- #include "pch.h"
9037 #ifndef CRYPTOPP_IMPORTS
9039 //- #include "randpool.h"
9040 //- #include "mdc.h"
9041 //- #include "sha.h"
9042 //- #include "modes.h"
9044 NAMESPACE_BEGIN(CryptoPP
)
9046 typedef MDC
<SHA
> RandomPoolCipher
;
9048 RandomPool::RandomPool(unsigned int poolSize
)
9049 : pool(poolSize
), key(RandomPoolCipher::DEFAULT_KEYLENGTH
)
9051 assert(poolSize
> key
.size());
9055 memset(pool
, 0, poolSize
);
9056 memset(key
, 0, key
.size());
9059 void RandomPool::Stir()
9061 CFB_Mode
<RandomPoolCipher
>::Encryption cipher
;
9063 for (int i
=0; i
<2; i
++)
9065 cipher
.SetKeyWithIV(key
, key
.size(), pool
.end()-cipher
.IVSize());
9066 cipher
.ProcessString(pool
, pool
.size());
9067 memcpy(key
, pool
, key
.size());
9071 getPos
= key
.size();
9074 unsigned int RandomPool::Put2(const byte
*inString
, unsigned int length
, int /* messageEnd */, bool /* blocking */)
9078 while (length
> (t
= pool
.size() - addPos
))
9080 xorbuf(pool
+addPos
, inString
, t
);
9088 xorbuf(pool
+addPos
, inString
, length
);
9090 getPos
= pool
.size(); // Force stir on get
9096 unsigned int RandomPool::TransferTo2(BufferedTransformation
&target
, unsigned long &transferBytes
, const std::string
&channel
, bool blocking
)
9099 throw NotImplemented("RandomPool: nonblocking transfer is not implemented by this object");
9102 unsigned long size
= transferBytes
;
9104 while (size
> (t
= pool
.size() - getPos
))
9106 target
.ChannelPut(channel
, pool
+getPos
, t
);
9113 target
.ChannelPut(channel
, pool
+getPos
, size
);
9120 byte
RandomPool::GenerateByte()
9122 if (getPos
== pool
.size())
9125 return pool
[getPos
++];
9128 void RandomPool::GenerateBlock(byte
*outString
, unsigned int size
)
9130 ArraySink
sink(outString
, size
);
9131 TransferTo(sink
, size
);
9137 ////////////////////////////////////////////////////////////////////////////////
9141 ////////////////////////////////////////////////////////////////////////////////
9142 // osrng.cpp - written and placed in the public domain by Wei Dai
9144 // Thanks to Leonard Janke for the suggestion for AutoSeededRandomPool.
9146 //- #include "pch.h"
9148 #ifndef CRYPTOPP_IMPORTS
9150 //- #include "osrng.h"
9152 #ifdef OS_RNG_AVAILABLE
9154 //- #include "rng.h"
9156 #ifdef CRYPTOPP_WIN32_AVAILABLE
9157 #ifndef _WIN32_WINNT
9158 #define _WIN32_WINNT 0x0400
9160 #include <windows.h>
9161 #include <wincrypt.h>
9164 #ifdef CRYPTOPP_UNIX_AVAILABLE
9170 NAMESPACE_BEGIN(CryptoPP
)
9172 #if defined(NONBLOCKING_RNG_AVAILABLE) || defined(BLOCKING_RNG_AVAILABLE)
9173 OS_RNG_Err::OS_RNG_Err(const std::string
&operation
)
9174 : Exception(OTHER_ERROR
, "OS_Rng: " + operation
+ " operation failed with error " +
9175 #ifdef CRYPTOPP_WIN32_AVAILABLE
9176 "0x" + IntToString(GetLastError(), 16)
9185 #ifdef NONBLOCKING_RNG_AVAILABLE
9187 #ifdef CRYPTOPP_WIN32_AVAILABLE
9189 MicrosoftCryptoProvider::MicrosoftCryptoProvider()
9191 if(!CryptAcquireContext(&m_hProvider
, 0, 0, PROV_RSA_FULL
, CRYPT_VERIFYCONTEXT
))
9192 throw OS_RNG_Err("CryptAcquireContext");
9195 MicrosoftCryptoProvider::~MicrosoftCryptoProvider()
9197 CryptReleaseContext(m_hProvider
, 0);
9202 NonblockingRng::NonblockingRng()
9204 #ifndef CRYPTOPP_WIN32_AVAILABLE
9205 m_fd
= open("/dev/urandom",O_RDONLY
);
9207 throw OS_RNG_Err("open /dev/urandom");
9211 NonblockingRng::~NonblockingRng()
9213 #ifndef CRYPTOPP_WIN32_AVAILABLE
9218 byte
NonblockingRng::GenerateByte()
9221 GenerateBlock(&b
, 1);
9225 void NonblockingRng::GenerateBlock(byte
*output
, unsigned int size
)
9227 #ifdef CRYPTOPP_WIN32_AVAILABLE
9228 # ifdef WORKAROUND_MS_BUG_Q258000
9229 static MicrosoftCryptoProvider m_Provider
;
9231 if (!CryptGenRandom(m_Provider
.GetProviderHandle(), size
, output
))
9232 throw OS_RNG_Err("CryptGenRandom");
9234 if ((unsigned int)read(m_fd
, output
, size
) != size
) {
9235 // Kernel 2.6.10 has non-concurrent access to /dev/urandom, retry at least once
9236 // printf("Shamelessly retrying a random generation attempt\n");
9237 if ((unsigned int)read(m_fd
, output
, size
) != size
) {
9238 // printf("Error reading /dev/urandom! (kernel 2.6.10?)\n");
9239 throw OS_RNG_Err("read /dev/urandom");
9247 // *************************************************************
9249 #ifdef BLOCKING_RNG_AVAILABLE
9251 BlockingRng::BlockingRng()
9253 m_fd
= open("/dev/random",O_RDONLY
);
9255 throw OS_RNG_Err("open /dev/random");
9258 BlockingRng::~BlockingRng()
9263 byte
BlockingRng::GenerateByte()
9266 GenerateBlock(&b
, 1);
9270 void BlockingRng::GenerateBlock(byte
*output
, unsigned int size
)
9274 // on some systems /dev/random will block until all bytes
9275 // are available, on others it will returns immediately
9276 int len
= read(m_fd
, output
, STDMIN(size
, (unsigned int)INT_MAX
));
9278 throw OS_RNG_Err("read /dev/random");
9288 // *************************************************************
9290 void OS_GenerateRandomBlock(bool blocking
, byte
*output
, unsigned int size
)
9292 #ifdef NONBLOCKING_RNG_AVAILABLE
9296 #ifdef BLOCKING_RNG_AVAILABLE
9298 rng
.GenerateBlock(output
, size
);
9302 #ifdef BLOCKING_RNG_AVAILABLE
9306 #ifdef NONBLOCKING_RNG_AVAILABLE
9308 rng
.GenerateBlock(output
, size
);
9313 void AutoSeededRandomPool::Reseed(bool blocking
, unsigned int seedSize
)
9315 SecByteBlock
seed(seedSize
);
9316 OS_GenerateRandomBlock(blocking
, seed
, seedSize
);
9317 Put(seed
, seedSize
);
9325 ////////////////////////////////////////////////////////////////////////////////
9329 ////////////////////////////////////////////////////////////////////////////////
9330 // md4.cpp - modified by Wei Dai from Andrew M. Kuchling's md4.c
9331 // The original code and all modifications are in the public domain.
9333 // This is the original introductory comment:
9336 * md4.c : MD4 hash algorithm.
9338 * Part of the Python Cryptography Toolkit, version 1.1
9340 * Distribute and use freely; there are no restrictions on further
9341 * dissemination and usage except those imposed by the laws of your
9342 * country of residence.
9346 //- #include "pch.h"
9347 //- #include "md4.h"
9348 //- #include "misc.h"
9350 NAMESPACE_BEGIN(CryptoPP
)
9352 void MD4::InitState(HashWordType
*state
)
9354 state
[0] = 0x67452301L
;
9355 state
[1] = 0xefcdab89L
;
9356 state
[2] = 0x98badcfeL
;
9357 state
[3] = 0x10325476L
;
9360 void MD4::Transform (word32
*digest
, const word32
*in
)
9362 // #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
9363 #define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
9364 #define G(x, y, z) (((x) & (y)) | ((x) & (z)) | ((y) & (z)))
9365 #define H(x, y, z) ((x) ^ (y) ^ (z))
9374 #define function(a,b,c,d,k,s) a=rotlFixed(a+F(b,c,d)+in[k],s);
9375 function(A
,B
,C
,D
, 0, 3);
9376 function(D
,A
,B
,C
, 1, 7);
9377 function(C
,D
,A
,B
, 2,11);
9378 function(B
,C
,D
,A
, 3,19);
9379 function(A
,B
,C
,D
, 4, 3);
9380 function(D
,A
,B
,C
, 5, 7);
9381 function(C
,D
,A
,B
, 6,11);
9382 function(B
,C
,D
,A
, 7,19);
9383 function(A
,B
,C
,D
, 8, 3);
9384 function(D
,A
,B
,C
, 9, 7);
9385 function(C
,D
,A
,B
,10,11);
9386 function(B
,C
,D
,A
,11,19);
9387 function(A
,B
,C
,D
,12, 3);
9388 function(D
,A
,B
,C
,13, 7);
9389 function(C
,D
,A
,B
,14,11);
9390 function(B
,C
,D
,A
,15,19);
9393 #define function(a,b,c,d,k,s) a=rotlFixed(a+G(b,c,d)+in[k]+0x5a827999,s);
9394 function(A
,B
,C
,D
, 0, 3);
9395 function(D
,A
,B
,C
, 4, 5);
9396 function(C
,D
,A
,B
, 8, 9);
9397 function(B
,C
,D
,A
,12,13);
9398 function(A
,B
,C
,D
, 1, 3);
9399 function(D
,A
,B
,C
, 5, 5);
9400 function(C
,D
,A
,B
, 9, 9);
9401 function(B
,C
,D
,A
,13,13);
9402 function(A
,B
,C
,D
, 2, 3);
9403 function(D
,A
,B
,C
, 6, 5);
9404 function(C
,D
,A
,B
,10, 9);
9405 function(B
,C
,D
,A
,14,13);
9406 function(A
,B
,C
,D
, 3, 3);
9407 function(D
,A
,B
,C
, 7, 5);
9408 function(C
,D
,A
,B
,11, 9);
9409 function(B
,C
,D
,A
,15,13);
9412 #define function(a,b,c,d,k,s) a=rotlFixed(a+H(b,c,d)+in[k]+0x6ed9eba1,s);
9413 function(A
,B
,C
,D
, 0, 3);
9414 function(D
,A
,B
,C
, 8, 9);
9415 function(C
,D
,A
,B
, 4,11);
9416 function(B
,C
,D
,A
,12,15);
9417 function(A
,B
,C
,D
, 2, 3);
9418 function(D
,A
,B
,C
,10, 9);
9419 function(C
,D
,A
,B
, 6,11);
9420 function(B
,C
,D
,A
,14,15);
9421 function(A
,B
,C
,D
, 1, 3);
9422 function(D
,A
,B
,C
, 9, 9);
9423 function(C
,D
,A
,B
, 5,11);
9424 function(B
,C
,D
,A
,13,15);
9425 function(A
,B
,C
,D
, 3, 3);
9426 function(D
,A
,B
,C
,11, 9);
9427 function(C
,D
,A
,B
, 7,11);
9428 function(B
,C
,D
,A
,15,15);
9437 ////////////////////////////////////////////////////////////////////////////////
9439 // Standard stuff from other gpl clients, external for mldonkey.
9441 typedef unsigned int wxUint32
;
9443 #define wxUINT32_SWAP_ALWAYS(val) \
9445 (((wxUint32) (val) & (wxUint32) 0x000000ffU) << 24) | \
9446 (((wxUint32) (val) & (wxUint32) 0x0000ff00U) << 8) | \
9447 (((wxUint32) (val) & (wxUint32) 0x00ff0000U) >> 8) | \
9448 (((wxUint32) (val) & (wxUint32) 0xff000000U) >> 24)))
9450 #ifndef IS_LITTLE_ENDIAN
9451 #define wxUINT32_SWAP_ON_BE(val) wxUINT32_SWAP_ALWAYS(val)
9453 #define wxUINT32_SWAP_ON_BE(val) (val)
9456 #define ENDIAN_SWAP_32(x) (wxUINT32_SWAP_ON_BE(x))
9460 typedef CryptoPP::RSASSA_PKCS1v15_SHA_Signer Signer
;
9461 typedef CryptoPP::RSASSA_PKCS1v15_SHA_Verifier Verifier
;
9464 inline void PokeUInt8(void* p
, uint8_t nVal
)
9466 *((uint8_t*)p
) = nVal
;
9469 inline void RawPokeUInt32(void* p
, uint32_t nVal
)
9471 memcpy( p
, &nVal
, sizeof(uint32_t) );
9475 inline void PokeUInt32(void* p
, uint32_t nVal
)
9477 RawPokeUInt32( p
, ENDIAN_SWAP_32( nVal
) );
9481 #define MAXPUBKEYSIZE 80
9482 #define PRIVKEYSIZE 384
9484 static Signer
* s_signer
= NULL
;
9485 static byte m_publicKey
[MAXPUBKEYSIZE
+1];
9486 static unsigned long m_publicKeyLen
= 0;
9488 void cc_lprintf_nl(const char * msg
, bool verb
);
9490 void crypto_exit () {
9492 delete (Signer
*) s_signer
;
9496 void createKey(char buf
[]) {
9497 using namespace CryptoPP
;
9501 std::string myString
;
9503 AutoSeededRandomPool rng
;
9504 InvertibleRSAFunction privKey
;
9505 privKey
.Initialize(rng
, PRIVKEYSIZE
);
9507 Base64Encoder
privKeySink(new StringSink(myString
), false);
9508 privKey
.DEREncode(privKeySink
);
9509 privKeySink
.MessageEnd();
9510 std::copy(myString
.begin(), myString
.end(), buf
);
9511 buf
[myString
.size()] = 0;
9513 } catch(const CryptoPP::Exception
& e
) {
9514 char buf
[256]="[CryptoPP] createKey: ";
9515 strcat(buf
, e
.what());
9516 cc_lprintf_nl(buf
, false);
9521 unsigned long loadKey(char privateKeyBase64
[], char buf
[]) {
9522 using namespace CryptoPP
;
9524 unsigned long result
= 0;
9528 StringSource
src(privateKeyBase64
, true, new Base64Decoder
);
9531 delete (Signer
*) s_signer
;
9533 s_signer
= new Signer(src
);
9534 Verifier
verifier(*((Signer
*)s_signer
));
9536 ArraySink
aSink(m_publicKey
, 80);
9537 verifier
.DEREncode(aSink
);
9538 m_publicKeyLen
= aSink
.TotalPutLength();
9541 memcpy(buf
, m_publicKey
, m_publicKeyLen
);
9542 buf
[m_publicKeyLen
] = 0;
9544 result
= m_publicKeyLen
;
9546 } catch(const CryptoPP::Exception
& e
) {
9547 char buf
[256]="[CryptoPP] loadKey: ";
9548 strcat(buf
, e
.what());
9549 cc_lprintf_nl(buf
, false);
9557 // return signatureSize (buf)
9558 int createSignature(byte
*buf
, int maxLen
, byte
*key
, int keyLen
, uint32_t cInt
, uint8_t ipType
, uint32_t ip
) {
9563 if (s_signer
== NULL
) {
9564 cc_lprintf_nl("createSignature: No signer", false);
9570 CryptoPP::SecByteBlock
sBB(s_signer
->SignatureLength());
9571 CryptoPP::AutoSeededRandomPool rng
;
9573 byte bArray
[MAXPUBKEYSIZE
+9];
9575 memcpy(bArray
,key
,keyLen
);
9576 PokeUInt32(bArray
+keyLen
,cInt
);
9581 PokeUInt32(bArray
+keyLen
+4,ip
);
9582 PokeUInt8(bArray
+keyLen
+4+4,ipType
);
9585 s_signer
->SignMessage(rng
, bArray
, keyLen
+4+extra
, sBB
.begin());
9586 CryptoPP::ArraySink
aSink(buf
, maxLen
);
9587 aSink
.Put(sBB
.begin(), sBB
.size());
9588 result
= aSink
.TotalPutLength();
9590 } catch(const CryptoPP::Exception
& e
) {
9591 char buf
[256]="[CryptoPP] createSignature: ";
9592 strcat(buf
, e
.what());
9593 cc_lprintf_nl(buf
, false);
9600 int verifySignature(byte
*key
, int keyLen
, byte
*sig
, int sigLen
, uint32_t cInt
, uint8_t ipType
, uint32_t ip
) {
9601 using namespace CryptoPP
;
9603 bool result
= false;
9607 StringSource
ss_Pubkey(key
, keyLen
,true,0);
9608 Verifier
pubKey(ss_Pubkey
);
9610 byte bArray
[MAXPUBKEYSIZE
+9];
9612 memcpy(bArray
,m_publicKey
,m_publicKeyLen
);
9613 PokeUInt32(bArray
+m_publicKeyLen
,cInt
);
9618 PokeUInt32(bArray
+m_publicKeyLen
+4,ip
);
9619 PokeUInt8(bArray
+m_publicKeyLen
+4+4,ipType
);
9621 result
= pubKey
.VerifyMessage(bArray
, m_publicKeyLen
+4+extra
, sig
, sigLen
);
9623 } catch(const CryptoPP::Exception
& e
) {
9624 char buf
[256]="[CryptoPP] verifySignature: ";
9625 strcat(buf
, e
.what());
9626 cc_lprintf_nl(buf
, true);
9629 return result
? 1 : 0;