From 5494fc310acf0aabb9d828451331e44483eb21c7 Mon Sep 17 00:00:00 2001 From: Malfurious Date: Mon, 21 Oct 2024 11:09:00 -0400 Subject: Remove Crypto++ library The tracked version of Crypto++ is going on 10 years old and doesn't always compile properly on modern tooling. This removes the entire subdirectory as well as references to files in the build script. Due to the number of files touched by this commit, I opt to add its replacement in the next commit. Signed-off-by: Malfurious --- cryptopp562/integer.cpp | 4235 ----------------------------------------------- 1 file changed, 4235 deletions(-) delete mode 100644 cryptopp562/integer.cpp (limited to 'cryptopp562/integer.cpp') diff --git a/cryptopp562/integer.cpp b/cryptopp562/integer.cpp deleted file mode 100644 index f07cce8..0000000 --- a/cryptopp562/integer.cpp +++ /dev/null @@ -1,4235 +0,0 @@ -// integer.cpp - written and placed in the public domain by Wei Dai -// contains public domain code contributed by Alister Lee and Leonard Janke - -#include "pch.h" - -#ifndef CRYPTOPP_IMPORTS - -#include "integer.h" -#include "modarith.h" -#include "nbtheory.h" -#include "asn.h" -#include "oids.h" -#include "words.h" -#include "algparam.h" -#include "pubkey.h" // for P1363_KDF2 -#include "sha.h" -#include "cpu.h" - -#include - -#if _MSC_VER >= 1400 - #include -#endif - -#ifdef __DECCXX - #include -#endif - -#ifdef CRYPTOPP_MSVC6_NO_PP - #pragma message("You do not seem to have the Visual C++ Processor Pack installed, so use of SSE2 instructions will be disabled.") -#endif - -#define CRYPTOPP_INTEGER_SSE2 (CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE && CRYPTOPP_BOOL_X86) - -NAMESPACE_BEGIN(CryptoPP) - -bool AssignIntToInteger(const std::type_info &valueType, void *pInteger, const void *pInt) -{ - if (valueType != typeid(Integer)) - return false; - *reinterpret_cast(pInteger) = *reinterpret_cast(pInt); - return true; -} - -inline static int Compare(const word *A, const word *B, size_t N) -{ - while (N--) - if (A[N] > B[N]) - return 1; - else if (A[N] < B[N]) - return -1; - - return 0; -} - -inline static int Increment(word *A, size_t N, word B=1) -{ - assert(N); - word t = A[0]; - A[0] = t+B; - if (A[0] >= t) - return 0; - for (unsigned i=1; i>(WORD_BITS-1)); d##0 = 2*d##0 + (c>>(WORD_BITS-1)); c *= 2; - #endif - #ifndef Acc2WordsBy2 - #define Acc2WordsBy2(a, b) a##0 += b##0; a##1 += a##0 < b##0; a##1 += b##1; - #endif - #define AddWithCarry(u, a, b) {word t = a+b; u##0 = t + u##1; u##1 = (ta) + (u##0>t);} - #define GetCarry(u) u##1 - #define GetBorrow(u) u##1 -#else - #define Declare2Words(x) dword x; - #if _MSC_VER >= 1400 && !defined(__INTEL_COMPILER) - #define MultiplyWords(p, a, b) p = __emulu(a, b); - #else - #define MultiplyWords(p, a, b) p = (dword)a*b; - #endif - #define AssignWord(a, b) a = b; - #define Add2WordsBy1(a, b, c) a = b + c; - #define Acc2WordsBy2(a, b) a += b; - #define LowWord(a) word(a) - #define HighWord(a) word(a>>WORD_BITS) - #define Double3Words(c, d) d = 2*d + (c>>(WORD_BITS-1)); c *= 2; - #define AddWithCarry(u, a, b) u = dword(a) + b + GetCarry(u); - #define SubtractWithBorrow(u, a, b) u = dword(a) - b - GetBorrow(u); - #define GetCarry(u) HighWord(u) - #define GetBorrow(u) word(u>>(WORD_BITS*2-1)) -#endif -#ifndef MulAcc - #define MulAcc(c, d, a, b) MultiplyWords(p, a, b); Acc2WordsBy1(p, c); c = LowWord(p); Acc2WordsBy1(d, HighWord(p)); -#endif -#ifndef Acc2WordsBy1 - #define Acc2WordsBy1(a, b) Add2WordsBy1(a, a, b) -#endif -#ifndef Acc3WordsBy2 - #define Acc3WordsBy2(c, d, e) Acc2WordsBy1(e, c); c = LowWord(e); Add2WordsBy1(e, d, HighWord(e)); -#endif - -class DWord -{ -public: - DWord() {} - -#ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - explicit DWord(word low) - { - m_whole = low; - } -#else - explicit DWord(word low) - { - m_halfs.low = low; - m_halfs.high = 0; - } -#endif - - DWord(word low, word high) - { - m_halfs.low = low; - m_halfs.high = high; - } - - static DWord Multiply(word a, word b) - { - DWord r; - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - r.m_whole = (dword)a * b; - #elif defined(MultiplyWordsLoHi) - MultiplyWordsLoHi(r.m_halfs.low, r.m_halfs.high, a, b); - #endif - return r; - } - - static DWord MultiplyAndAdd(word a, word b, word c) - { - DWord r = Multiply(a, b); - return r += c; - } - - DWord & operator+=(word a) - { - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - m_whole = m_whole + a; - #else - m_halfs.low += a; - m_halfs.high += (m_halfs.low < a); - #endif - return *this; - } - - DWord operator+(word a) - { - DWord r; - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - r.m_whole = m_whole + a; - #else - r.m_halfs.low = m_halfs.low + a; - r.m_halfs.high = m_halfs.high + (r.m_halfs.low < a); - #endif - return r; - } - - DWord operator-(DWord a) - { - DWord r; - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - r.m_whole = m_whole - a.m_whole; - #else - r.m_halfs.low = m_halfs.low - a.m_halfs.low; - r.m_halfs.high = m_halfs.high - a.m_halfs.high - (r.m_halfs.low > m_halfs.low); - #endif - return r; - } - - DWord operator-(word a) - { - DWord r; - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - r.m_whole = m_whole - a; - #else - r.m_halfs.low = m_halfs.low - a; - r.m_halfs.high = m_halfs.high - (r.m_halfs.low > m_halfs.low); - #endif - return r; - } - - // returns quotient, which must fit in a word - word operator/(word divisor); - - word operator%(word a); - - bool operator!() const - { - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - return !m_whole; - #else - return !m_halfs.high && !m_halfs.low; - #endif - } - - word GetLowHalf() const {return m_halfs.low;} - word GetHighHalf() const {return m_halfs.high;} - word GetHighHalfAsBorrow() const {return 0-m_halfs.high;} - -private: - union - { - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - dword m_whole; - #endif - struct - { - #ifdef IS_LITTLE_ENDIAN - word low; - word high; - #else - word high; - word low; - #endif - } m_halfs; - }; -}; - -class Word -{ -public: - Word() {} - - Word(word value) - { - m_whole = value; - } - - Word(hword low, hword high) - { - m_whole = low | (word(high) << (WORD_BITS/2)); - } - - static Word Multiply(hword a, hword b) - { - Word r; - r.m_whole = (word)a * b; - return r; - } - - Word operator-(Word a) - { - Word r; - r.m_whole = m_whole - a.m_whole; - return r; - } - - Word operator-(hword a) - { - Word r; - r.m_whole = m_whole - a; - return r; - } - - // returns quotient, which must fit in a word - hword operator/(hword divisor) - { - return hword(m_whole / divisor); - } - - bool operator!() const - { - return !m_whole; - } - - word GetWhole() const {return m_whole;} - hword GetLowHalf() const {return hword(m_whole);} - hword GetHighHalf() const {return hword(m_whole>>(WORD_BITS/2));} - hword GetHighHalfAsBorrow() const {return 0-hword(m_whole>>(WORD_BITS/2));} - -private: - word m_whole; -}; - -// do a 3 word by 2 word divide, returns quotient and leaves remainder in A -template -S DivideThreeWordsByTwo(S *A, S B0, S B1, D *dummy=NULL) -{ - // assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a S - assert(A[2] < B1 || (A[2]==B1 && A[1] < B0)); - - // estimate the quotient: do a 2 S by 1 S divide - S Q; - if (S(B1+1) == 0) - Q = A[2]; - else if (B1 > 0) - Q = D(A[1], A[2]) / S(B1+1); - else - Q = D(A[0], A[1]) / B0; - - // now subtract Q*B from A - D p = D::Multiply(B0, Q); - D u = (D) A[0] - p.GetLowHalf(); - A[0] = u.GetLowHalf(); - u = (D) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - D::Multiply(B1, Q); - A[1] = u.GetLowHalf(); - A[2] += u.GetHighHalf(); - - // Q <= actual quotient, so fix it - while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0)) - { - u = (D) A[0] - B0; - A[0] = u.GetLowHalf(); - u = (D) A[1] - B1 - u.GetHighHalfAsBorrow(); - A[1] = u.GetLowHalf(); - A[2] += u.GetHighHalf(); - Q++; - assert(Q); // shouldn't overflow - } - - return Q; -} - -// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1 -template -inline D DivideFourWordsByTwo(S *T, const D &Al, const D &Ah, const D &B) -{ - if (!B) // if divisor is 0, we assume divisor==2**(2*WORD_BITS) - return D(Ah.GetLowHalf(), Ah.GetHighHalf()); - else - { - S Q[2]; - T[0] = Al.GetLowHalf(); - T[1] = Al.GetHighHalf(); - T[2] = Ah.GetLowHalf(); - T[3] = Ah.GetHighHalf(); - Q[1] = DivideThreeWordsByTwo(T+1, B.GetLowHalf(), B.GetHighHalf()); - Q[0] = DivideThreeWordsByTwo(T, B.GetLowHalf(), B.GetHighHalf()); - return D(Q[0], Q[1]); - } -} - -// returns quotient, which must fit in a word -inline word DWord::operator/(word a) -{ - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - return word(m_whole / a); - #else - hword r[4]; - return DivideFourWordsByTwo(r, m_halfs.low, m_halfs.high, a).GetWhole(); - #endif -} - -inline word DWord::operator%(word a) -{ - #ifdef CRYPTOPP_NATIVE_DWORD_AVAILABLE - return word(m_whole % a); - #else - if (a < (word(1) << (WORD_BITS/2))) - { - hword h = hword(a); - word r = m_halfs.high % h; - r = ((m_halfs.low >> (WORD_BITS/2)) + (r << (WORD_BITS/2))) % h; - return hword((hword(m_halfs.low) + (r << (WORD_BITS/2))) % h); - } - else - { - hword r[4]; - DivideFourWordsByTwo(r, m_halfs.low, m_halfs.high, a); - return Word(r[0], r[1]).GetWhole(); - } - #endif -} - -// ******************************************************** - -// use some tricks to share assembly code between MSVC and GCC -#if defined(__GNUC__) - #define AddPrologue \ - int result; \ - __asm__ __volatile__ \ - ( \ - ".intel_syntax noprefix;" - #define AddEpilogue \ - ".att_syntax prefix;" \ - : "=a" (result)\ - : "d" (C), "a" (A), "D" (B), "c" (N) \ - : "%esi", "memory", "cc" \ - );\ - return result; - #define MulPrologue \ - __asm__ __volatile__ \ - ( \ - ".intel_syntax noprefix;" \ - AS1( push ebx) \ - AS2( mov ebx, edx) - #define MulEpilogue \ - AS1( pop ebx) \ - ".att_syntax prefix;" \ - : \ - : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B) \ - : "%esi", "memory", "cc" \ - ); - #define SquPrologue MulPrologue - #define SquEpilogue \ - AS1( pop ebx) \ - ".att_syntax prefix;" \ - : \ - : "d" (s_maskLow16), "c" (C), "a" (A) \ - : "%esi", "%edi", "memory", "cc" \ - ); - #define TopPrologue MulPrologue - #define TopEpilogue \ - AS1( pop ebx) \ - ".att_syntax prefix;" \ - : \ - : "d" (s_maskLow16), "c" (C), "a" (A), "D" (B), "S" (L) \ - : "memory", "cc" \ - ); -#else - #define AddPrologue \ - __asm push edi \ - __asm push esi \ - __asm mov eax, [esp+12] \ - __asm mov edi, [esp+16] - #define AddEpilogue \ - __asm pop esi \ - __asm pop edi \ - __asm ret 8 -#if _MSC_VER < 1300 - #define SaveEBX __asm push ebx - #define RestoreEBX __asm pop ebx -#else - #define SaveEBX - #define RestoreEBX -#endif - #define SquPrologue \ - AS2( mov eax, A) \ - AS2( mov ecx, C) \ - SaveEBX \ - AS2( lea ebx, s_maskLow16) - #define MulPrologue \ - AS2( mov eax, A) \ - AS2( mov edi, B) \ - AS2( mov ecx, C) \ - SaveEBX \ - AS2( lea ebx, s_maskLow16) - #define TopPrologue \ - AS2( mov eax, A) \ - AS2( mov edi, B) \ - AS2( mov ecx, C) \ - AS2( mov esi, L) \ - SaveEBX \ - AS2( lea ebx, s_maskLow16) - #define SquEpilogue RestoreEBX - #define MulEpilogue RestoreEBX - #define TopEpilogue RestoreEBX -#endif - -#ifdef CRYPTOPP_X64_MASM_AVAILABLE -extern "C" { -int Baseline_Add(size_t N, word *C, const word *A, const word *B); -int Baseline_Sub(size_t N, word *C, const word *A, const word *B); -} -#elif defined(CRYPTOPP_X64_ASM_AVAILABLE) && defined(__GNUC__) && defined(CRYPTOPP_WORD128_AVAILABLE) -int Baseline_Add(size_t N, word *C, const word *A, const word *B) -{ - word result; - __asm__ __volatile__ - ( - ".intel_syntax;" - AS1( neg %1) - ASJ( jz, 1, f) - AS2( mov %0,[%3+8*%1]) - AS2( add %0,[%4+8*%1]) - AS2( mov [%2+8*%1],%0) - ASL(0) - AS2( mov %0,[%3+8*%1+8]) - AS2( adc %0,[%4+8*%1+8]) - AS2( mov [%2+8*%1+8],%0) - AS2( lea %1,[%1+2]) - ASJ( jrcxz, 1, f) - AS2( mov %0,[%3+8*%1]) - AS2( adc %0,[%4+8*%1]) - AS2( mov [%2+8*%1],%0) - ASJ( jmp, 0, b) - ASL(1) - AS2( mov %0, 0) - AS2( adc %0, %0) - ".att_syntax;" - : "=&r" (result), "+c" (N) - : "r" (C+N), "r" (A+N), "r" (B+N) - : "memory", "cc" - ); - return (int)result; -} - -int Baseline_Sub(size_t N, word *C, const word *A, const word *B) -{ - word result; - __asm__ __volatile__ - ( - ".intel_syntax;" - AS1( neg %1) - ASJ( jz, 1, f) - AS2( mov %0,[%3+8*%1]) - AS2( sub %0,[%4+8*%1]) - AS2( mov [%2+8*%1],%0) - ASL(0) - AS2( mov %0,[%3+8*%1+8]) - AS2( sbb %0,[%4+8*%1+8]) - AS2( mov [%2+8*%1+8],%0) - AS2( lea %1,[%1+2]) - ASJ( jrcxz, 1, f) - AS2( mov %0,[%3+8*%1]) - AS2( sbb %0,[%4+8*%1]) - AS2( mov [%2+8*%1],%0) - ASJ( jmp, 0, b) - ASL(1) - AS2( mov %0, 0) - AS2( adc %0, %0) - ".att_syntax;" - : "=&r" (result), "+c" (N) - : "r" (C+N), "r" (A+N), "r" (B+N) - : "memory", "cc" - ); - return (int)result; -} -#elif defined(CRYPTOPP_X86_ASM_AVAILABLE) && CRYPTOPP_BOOL_X86 -CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B) -{ - AddPrologue - - // now: eax = A, edi = B, edx = C, ecx = N - AS2( lea eax, [eax+4*ecx]) - AS2( lea edi, [edi+4*ecx]) - AS2( lea edx, [edx+4*ecx]) - - AS1( neg ecx) // ecx is negative index - AS2( test ecx, 2) // this clears carry flag - ASJ( jz, 0, f) - AS2( sub ecx, 2) - ASJ( jmp, 1, f) - - ASL(0) - ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero - AS2( mov esi,[eax+4*ecx]) - AS2( adc esi,[edi+4*ecx]) - AS2( mov [edx+4*ecx],esi) - AS2( mov esi,[eax+4*ecx+4]) - AS2( adc esi,[edi+4*ecx+4]) - AS2( mov [edx+4*ecx+4],esi) - ASL(1) - AS2( mov esi,[eax+4*ecx+8]) - AS2( adc esi,[edi+4*ecx+8]) - AS2( mov [edx+4*ecx+8],esi) - AS2( mov esi,[eax+4*ecx+12]) - AS2( adc esi,[edi+4*ecx+12]) - AS2( mov [edx+4*ecx+12],esi) - - AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2 - ASJ( jmp, 0, b) - - ASL(2) - AS2( mov eax, 0) - AS1( setc al) // store carry into eax (return result register) - - AddEpilogue -} - -CRYPTOPP_NAKED int CRYPTOPP_FASTCALL Baseline_Sub(size_t N, word *C, const word *A, const word *B) -{ - AddPrologue - - // now: eax = A, edi = B, edx = C, ecx = N - AS2( lea eax, [eax+4*ecx]) - AS2( lea edi, [edi+4*ecx]) - AS2( lea edx, [edx+4*ecx]) - - AS1( neg ecx) // ecx is negative index - AS2( test ecx, 2) // this clears carry flag - ASJ( jz, 0, f) - AS2( sub ecx, 2) - ASJ( jmp, 1, f) - - ASL(0) - ASJ( jecxz, 2, f) // loop until ecx overflows and becomes zero - AS2( mov esi,[eax+4*ecx]) - AS2( sbb esi,[edi+4*ecx]) - AS2( mov [edx+4*ecx],esi) - AS2( mov esi,[eax+4*ecx+4]) - AS2( sbb esi,[edi+4*ecx+4]) - AS2( mov [edx+4*ecx+4],esi) - ASL(1) - AS2( mov esi,[eax+4*ecx+8]) - AS2( sbb esi,[edi+4*ecx+8]) - AS2( mov [edx+4*ecx+8],esi) - AS2( mov esi,[eax+4*ecx+12]) - AS2( sbb esi,[edi+4*ecx+12]) - AS2( mov [edx+4*ecx+12],esi) - - AS2( lea ecx,[ecx+4]) // advance index, avoid inc which causes slowdown on Intel Core 2 - ASJ( jmp, 0, b) - - ASL(2) - AS2( mov eax, 0) - AS1( setc al) // store carry into eax (return result register) - - AddEpilogue -} - -#if CRYPTOPP_INTEGER_SSE2 -CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Add(size_t N, word *C, const word *A, const word *B) -{ - AddPrologue - - // now: eax = A, edi = B, edx = C, ecx = N - AS2( lea eax, [eax+4*ecx]) - AS2( lea edi, [edi+4*ecx]) - AS2( lea edx, [edx+4*ecx]) - - AS1( neg ecx) // ecx is negative index - AS2( pxor mm2, mm2) - ASJ( jz, 2, f) - AS2( test ecx, 2) // this clears carry flag - ASJ( jz, 0, f) - AS2( sub ecx, 2) - ASJ( jmp, 1, f) - - ASL(0) - AS2( movd mm0, DWORD PTR [eax+4*ecx]) - AS2( movd mm1, DWORD PTR [edi+4*ecx]) - AS2( paddq mm0, mm1) - AS2( paddq mm2, mm0) - AS2( movd DWORD PTR [edx+4*ecx], mm2) - AS2( psrlq mm2, 32) - - AS2( movd mm0, DWORD PTR [eax+4*ecx+4]) - AS2( movd mm1, DWORD PTR [edi+4*ecx+4]) - AS2( paddq mm0, mm1) - AS2( paddq mm2, mm0) - AS2( movd DWORD PTR [edx+4*ecx+4], mm2) - AS2( psrlq mm2, 32) - - ASL(1) - AS2( movd mm0, DWORD PTR [eax+4*ecx+8]) - AS2( movd mm1, DWORD PTR [edi+4*ecx+8]) - AS2( paddq mm0, mm1) - AS2( paddq mm2, mm0) - AS2( movd DWORD PTR [edx+4*ecx+8], mm2) - AS2( psrlq mm2, 32) - - AS2( movd mm0, DWORD PTR [eax+4*ecx+12]) - AS2( movd mm1, DWORD PTR [edi+4*ecx+12]) - AS2( paddq mm0, mm1) - AS2( paddq mm2, mm0) - AS2( movd DWORD PTR [edx+4*ecx+12], mm2) - AS2( psrlq mm2, 32) - - AS2( add ecx, 4) - ASJ( jnz, 0, b) - - ASL(2) - AS2( movd eax, mm2) - AS1( emms) - - AddEpilogue -} -CRYPTOPP_NAKED int CRYPTOPP_FASTCALL SSE2_Sub(size_t N, word *C, const word *A, const word *B) -{ - AddPrologue - - // now: eax = A, edi = B, edx = C, ecx = N - AS2( lea eax, [eax+4*ecx]) - AS2( lea edi, [edi+4*ecx]) - AS2( lea edx, [edx+4*ecx]) - - AS1( neg ecx) // ecx is negative index - AS2( pxor mm2, mm2) - ASJ( jz, 2, f) - AS2( test ecx, 2) // this clears carry flag - ASJ( jz, 0, f) - AS2( sub ecx, 2) - ASJ( jmp, 1, f) - - ASL(0) - AS2( movd mm0, DWORD PTR [eax+4*ecx]) - AS2( movd mm1, DWORD PTR [edi+4*ecx]) - AS2( psubq mm0, mm1) - AS2( psubq mm0, mm2) - AS2( movd DWORD PTR [edx+4*ecx], mm0) - AS2( psrlq mm0, 63) - - AS2( movd mm2, DWORD PTR [eax+4*ecx+4]) - AS2( movd mm1, DWORD PTR [edi+4*ecx+4]) - AS2( psubq mm2, mm1) - AS2( psubq mm2, mm0) - AS2( movd DWORD PTR [edx+4*ecx+4], mm2) - AS2( psrlq mm2, 63) - - ASL(1) - AS2( movd mm0, DWORD PTR [eax+4*ecx+8]) - AS2( movd mm1, DWORD PTR [edi+4*ecx+8]) - AS2( psubq mm0, mm1) - AS2( psubq mm0, mm2) - AS2( movd DWORD PTR [edx+4*ecx+8], mm0) - AS2( psrlq mm0, 63) - - AS2( movd mm2, DWORD PTR [eax+4*ecx+12]) - AS2( movd mm1, DWORD PTR [edi+4*ecx+12]) - AS2( psubq mm2, mm1) - AS2( psubq mm2, mm0) - AS2( movd DWORD PTR [edx+4*ecx+12], mm2) - AS2( psrlq mm2, 63) - - AS2( add ecx, 4) - ASJ( jnz, 0, b) - - ASL(2) - AS2( movd eax, mm2) - AS1( emms) - - AddEpilogue -} -#endif // #if CRYPTOPP_BOOL_SSE2_ASM_AVAILABLE -#else -int CRYPTOPP_FASTCALL Baseline_Add(size_t N, word *C, const word *A, const word *B) -{ - assert (N%2 == 0); - - Declare2Words(u); - AssignWord(u, 0); - for (size_t i=0; i=2 && N%2==0); - - if (N <= s_recursionLimit) - s_pMul[N/4](R, A, B); - else - { - const size_t N2 = N/2; - - size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2; - Subtract(R0, A + AN2, A + (N2 ^ AN2), N2); - - size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2; - Subtract(R1, B + BN2, B + (N2 ^ BN2), N2); - - RecursiveMultiply(R2, T2, A1, B1, N2); - RecursiveMultiply(T0, T2, R0, R1, N2); - RecursiveMultiply(R0, T2, A0, B0, N2); - - // now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1 - - int c2 = Add(R2, R2, R1, N2); - int c3 = c2; - c2 += Add(R1, R2, R0, N2); - c3 += Add(R2, R2, R3, N2); - - if (AN2 == BN2) - c3 -= Subtract(R1, R1, T0, N); - else - c3 += Add(R1, R1, T0, N); - - c3 += Increment(R2, N2, c2); - assert (c3 >= 0 && c3 <= 2); - Increment(R3, N2, c3); - } -} - -// R[2*N] - result = A*A -// T[2*N] - temporary work space -// A[N] --- number to be squared - -void RecursiveSquare(word *R, word *T, const word *A, size_t N) -{ - assert(N && N%2==0); - - if (N <= s_recursionLimit) - s_pSqu[N/4](R, A); - else - { - const size_t N2 = N/2; - - RecursiveSquare(R0, T2, A0, N2); - RecursiveSquare(R2, T2, A1, N2); - RecursiveMultiply(T0, T2, A0, A1, N2); - - int carry = Add(R1, R1, T0, N); - carry += Add(R1, R1, T0, N); - Increment(R3, N2, carry); - } -} - -// R[N] - bottom half of A*B -// T[3*N/2] - temporary work space -// A[N] - multiplier -// B[N] - multiplicant - -void RecursiveMultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N) -{ - assert(N>=2 && N%2==0); - - if (N <= s_recursionLimit) - s_pBot[N/4](R, A, B); - else - { - const size_t N2 = N/2; - - RecursiveMultiply(R, T, A0, B0, N2); - RecursiveMultiplyBottom(T0, T1, A1, B0, N2); - Add(R1, R1, T0, N2); - RecursiveMultiplyBottom(T0, T1, A0, B1, N2); - Add(R1, R1, T0, N2); - } -} - -// R[N] --- upper half of A*B -// T[2*N] - temporary work space -// L[N] --- lower half of A*B -// A[N] --- multiplier -// B[N] --- multiplicant - -void MultiplyTop(word *R, word *T, const word *L, const word *A, const word *B, size_t N) -{ - assert(N>=2 && N%2==0); - - if (N <= s_recursionLimit) - s_pTop[N/4](R, A, B, L[N-1]); - else - { - const size_t N2 = N/2; - - size_t AN2 = Compare(A0, A1, N2) > 0 ? 0 : N2; - Subtract(R0, A + AN2, A + (N2 ^ AN2), N2); - - size_t BN2 = Compare(B0, B1, N2) > 0 ? 0 : N2; - Subtract(R1, B + BN2, B + (N2 ^ BN2), N2); - - RecursiveMultiply(T0, T2, R0, R1, N2); - RecursiveMultiply(R0, T2, A1, B1, N2); - - // now T[01] holds (A1-A0)*(B0-B1) = A1*B0+A0*B1-A1*B1-A0*B0, R[01] holds A1*B1 - - int t, c3; - int c2 = Subtract(T2, L+N2, L, N2); - - if (AN2 == BN2) - { - c2 -= Add(T2, T2, T0, N2); - t = (Compare(T2, R0, N2) == -1); - c3 = t - Subtract(T2, T2, T1, N2); - } - else - { - c2 += Subtract(T2, T2, T0, N2); - t = (Compare(T2, R0, N2) == -1); - c3 = t + Add(T2, T2, T1, N2); - } - - c2 += t; - if (c2 >= 0) - c3 += Increment(T2, N2, c2); - else - c3 -= Decrement(T2, N2, -c2); - c3 += Add(R0, T2, R1, N2); - - assert (c3 >= 0 && c3 <= 2); - Increment(R1, N2, c3); - } -} - -inline void Multiply(word *R, word *T, const word *A, const word *B, size_t N) -{ - RecursiveMultiply(R, T, A, B, N); -} - -inline void Square(word *R, word *T, const word *A, size_t N) -{ - RecursiveSquare(R, T, A, N); -} - -inline void MultiplyBottom(word *R, word *T, const word *A, const word *B, size_t N) -{ - RecursiveMultiplyBottom(R, T, A, B, N); -} - -// R[NA+NB] - result = A*B -// T[NA+NB] - temporary work space -// A[NA] ---- multiplier -// B[NB] ---- multiplicant - -void AsymmetricMultiply(word *R, word *T, const word *A, size_t NA, const word *B, size_t NB) -{ - if (NA == NB) - { - if (A == B) - Square(R, T, A, NA); - else - Multiply(R, T, A, B, NA); - - return; - } - - if (NA > NB) - { - std::swap(A, B); - std::swap(NA, NB); - } - - assert(NB % NA == 0); - - if (NA==2 && !A[1]) - { - switch (A[0]) - { - case 0: - SetWords(R, 0, NB+2); - return; - case 1: - CopyWords(R, B, NB); - R[NB] = R[NB+1] = 0; - return; - default: - R[NB] = LinearMultiply(R, B, A[0], NB); - R[NB+1] = 0; - return; - } - } - - size_t i; - if ((NB/NA)%2 == 0) - { - Multiply(R, T, A, B, NA); - CopyWords(T+2*NA, R+NA, NA); - - for (i=2*NA; i=4); - -#define M0 M -#define M1 (M+N2) -#define V0 V -#define V1 (V+N2) - -#define X0 X -#define X1 (X+N2) -#define X2 (X+N) -#define X3 (X+N+N2) - - const size_t N2 = N/2; - Multiply(T0, T2, V0, X3, N2); - int c2 = Add(T0, T0, X0, N); - MultiplyBottom(T3, T2, T0, U, N2); - MultiplyTop(T2, R, T0, T3, M0, N2); - c2 -= Subtract(T2, T1, T2, N2); - Multiply(T0, R, T3, M1, N2); - c2 -= Subtract(T0, T2, T0, N2); - int c3 = -(int)Subtract(T1, X2, T1, N2); - Multiply(R0, T2, V1, X3, N2); - c3 += Add(R, R, T, N); - - if (c2>0) - c3 += Increment(R1, N2); - else if (c2<0) - c3 -= Decrement(R1, N2, -c2); - - assert(c3>=-1 && c3<=1); - if (c3>0) - Subtract(R, R, M, N); - else if (c3<0) - Add(R, R, M, N); - -#undef M0 -#undef M1 -#undef V0 -#undef V1 - -#undef X0 -#undef X1 -#undef X2 -#undef X3 -} - -#undef A0 -#undef A1 -#undef B0 -#undef B1 - -#undef T0 -#undef T1 -#undef T2 -#undef T3 - -#undef R0 -#undef R1 -#undef R2 -#undef R3 - -/* -// do a 3 word by 2 word divide, returns quotient and leaves remainder in A -static word SubatomicDivide(word *A, word B0, word B1) -{ - // assert {A[2],A[1]} < {B1,B0}, so quotient can fit in a word - assert(A[2] < B1 || (A[2]==B1 && A[1] < B0)); - - // estimate the quotient: do a 2 word by 1 word divide - word Q; - if (B1+1 == 0) - Q = A[2]; - else - Q = DWord(A[1], A[2]).DividedBy(B1+1); - - // now subtract Q*B from A - DWord p = DWord::Multiply(B0, Q); - DWord u = (DWord) A[0] - p.GetLowHalf(); - A[0] = u.GetLowHalf(); - u = (DWord) A[1] - p.GetHighHalf() - u.GetHighHalfAsBorrow() - DWord::Multiply(B1, Q); - A[1] = u.GetLowHalf(); - A[2] += u.GetHighHalf(); - - // Q <= actual quotient, so fix it - while (A[2] || A[1] > B1 || (A[1]==B1 && A[0]>=B0)) - { - u = (DWord) A[0] - B0; - A[0] = u.GetLowHalf(); - u = (DWord) A[1] - B1 - u.GetHighHalfAsBorrow(); - A[1] = u.GetLowHalf(); - A[2] += u.GetHighHalf(); - Q++; - assert(Q); // shouldn't overflow - } - - return Q; -} - -// do a 4 word by 2 word divide, returns 2 word quotient in Q0 and Q1 -static inline void AtomicDivide(word *Q, const word *A, const word *B) -{ - if (!B[0] && !B[1]) // if divisor is 0, we assume divisor==2**(2*WORD_BITS) - { - Q[0] = A[2]; - Q[1] = A[3]; - } - else - { - word T[4]; - T[0] = A[0]; T[1] = A[1]; T[2] = A[2]; T[3] = A[3]; - Q[1] = SubatomicDivide(T+1, B[0], B[1]); - Q[0] = SubatomicDivide(T, B[0], B[1]); - -#ifndef NDEBUG - // multiply quotient and divisor and add remainder, make sure it equals dividend - assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0](T, DWord(A[0], A[1]), DWord(A[2], A[3]), DWord(B[0], B[1])); - Q[0] = q.GetLowHalf(); - Q[1] = q.GetHighHalf(); - -#ifndef NDEBUG - if (B[0] || B[1]) - { - // multiply quotient and divisor and add remainder, make sure it equals dividend - assert(!T[2] && !T[3] && (T[1] < B[1] || (T[1]==B[1] && T[0]= 0) - { - R[N] -= Subtract(R, R, B, N); - Q[1] += (++Q[0]==0); - assert(Q[0] || Q[1]); // no overflow - } -} - -// R[NB] -------- remainder = A%B -// Q[NA-NB+2] --- quotient = A/B -// T[NA+3*(NB+2)] - temp work space -// A[NA] -------- dividend -// B[NB] -------- divisor - -void Divide(word *R, word *Q, word *T, const word *A, size_t NA, const word *B, size_t NB) -{ - assert(NA && NB && NA%2==0 && NB%2==0); - assert(B[NB-1] || B[NB-2]); - assert(NB <= NA); - - // set up temporary work space - word *const TA=T; - word *const TB=T+NA+2; - word *const TP=T+NA+2+NB; - - // copy B into TB and normalize it so that TB has highest bit set to 1 - unsigned shiftWords = (B[NB-1]==0); - TB[0] = TB[NB-1] = 0; - CopyWords(TB+shiftWords, B, NB-shiftWords); - unsigned shiftBits = WORD_BITS - BitPrecision(TB[NB-1]); - assert(shiftBits < WORD_BITS); - ShiftWordsLeftByBits(TB, NB, shiftBits); - - // copy A into TA and normalize it - TA[0] = TA[NA] = TA[NA+1] = 0; - CopyWords(TA+shiftWords, A, NA); - ShiftWordsLeftByBits(TA, NA+2, shiftBits); - - if (TA[NA+1]==0 && TA[NA] <= 1) - { - Q[NA-NB+1] = Q[NA-NB] = 0; - while (TA[NA] || Compare(TA+NA-NB, TB, NB) >= 0) - { - TA[NA] -= Subtract(TA+NA-NB, TA+NA-NB, TB, NB); - ++Q[NA-NB]; - } - } - else - { - NA+=2; - assert(Compare(TA+NA-NB, TB, NB) < 0); - } - - word BT[2]; - BT[0] = TB[NB-2] + 1; - BT[1] = TB[NB-1] + (BT[0]==0); - - // start reducing TA mod TB, 2 words at a time - for (size_t i=NA-2; i>=NB; i-=2) - { - AtomicDivide(Q+i-NB, TA+i-2, BT); - CorrectQuotientEstimate(TA+i-NB, TP, Q+i-NB, TB, NB); - } - - // copy TA into R, and denormalize it - CopyWords(R, TA+shiftWords, NB); - ShiftWordsRightByBits(R, NB, shiftBits); -} - -static inline size_t EvenWordCount(const word *X, size_t N) -{ - while (N && X[N-2]==0 && X[N-1]==0) - N-=2; - return N; -} - -// return k -// R[N] --- result = A^(-1) * 2^k mod M -// T[4*N] - temporary work space -// A[NA] -- number to take inverse of -// M[N] --- modulus - -unsigned int AlmostInverse(word *R, word *T, const word *A, size_t NA, const word *M, size_t N) -{ - assert(NA<=N && N && N%2==0); - - word *b = T; - word *c = T+N; - word *f = T+2*N; - word *g = T+3*N; - size_t bcLen=2, fgLen=EvenWordCount(M, N); - unsigned int k=0; - bool s=false; - - SetWords(T, 0, 3*N); - b[0]=1; - CopyWords(f, A, NA); - CopyWords(g, M, N); - - while (1) - { - word t=f[0]; - while (!t) - { - if (EvenWordCount(f, fgLen)==0) - { - SetWords(R, 0, N); - return 0; - } - - ShiftWordsRightByWords(f, fgLen, 1); - bcLen += 2 * (c[bcLen-1] != 0); - assert(bcLen <= N); - ShiftWordsLeftByWords(c, bcLen, 1); - k+=WORD_BITS; - t=f[0]; - } - - unsigned int i = TrailingZeros(t); - t >>= i; - k += i; - - if (t==1 && f[1]==0 && EvenWordCount(f+2, fgLen-2)==0) - { - if (s) - Subtract(R, M, b, N); - else - CopyWords(R, b, N); - return k; - } - - ShiftWordsRightByBits(f, fgLen, i); - t = ShiftWordsLeftByBits(c, bcLen, i); - c[bcLen] += t; - bcLen += 2 * (t!=0); - assert(bcLen <= N); - - bool swap = Compare(f, g, fgLen)==-1; - ConditionalSwapPointers(swap, f, g); - ConditionalSwapPointers(swap, b, c); - s ^= swap; - - fgLen -= 2 * !(f[fgLen-2] | f[fgLen-1]); - - Subtract(f, f, g, fgLen); - t = Add(b, b, c, bcLen); - b[bcLen] += t; - bcLen += 2*t; - assert(bcLen <= N); - } -} - -// R[N] - result = A/(2^k) mod M -// A[N] - input -// M[N] - modulus - -void DivideByPower2Mod(word *R, const word *A, size_t k, const word *M, size_t N) -{ - CopyWords(R, A, N); - - while (k--) - { - if (R[0]%2==0) - ShiftWordsRightByBits(R, N, 1); - else - { - word carry = Add(R, R, M, N); - ShiftWordsRightByBits(R, N, 1); - R[N-1] += carry<<(WORD_BITS-1); - } - } -} - -// R[N] - result = A*(2^k) mod M -// A[N] - input -// M[N] - modulus - -void MultiplyByPower2Mod(word *R, const word *A, size_t k, const word *M, size_t N) -{ - CopyWords(R, A, N); - - while (k--) - if (ShiftWordsLeftByBits(R, N, 1) || Compare(R, M, N)>=0) - Subtract(R, R, M, N); -} - -// ****************************************************************** - -InitializeInteger::InitializeInteger() -{ - if (!g_pAssignIntToInteger) - { - SetFunctionPointers(); - g_pAssignIntToInteger = AssignIntToInteger; - } -} - -static const unsigned int RoundupSizeTable[] = {2, 2, 2, 4, 4, 8, 8, 8, 8}; - -static inline size_t RoundupSize(size_t n) -{ - if (n<=8) - return RoundupSizeTable[n]; - else if (n<=16) - return 16; - else if (n<=32) - return 32; - else if (n<=64) - return 64; - else return size_t(1) << BitPrecision(n-1); -} - -Integer::Integer() - : reg(2), sign(POSITIVE) -{ - reg[0] = reg[1] = 0; -} - -Integer::Integer(const Integer& t) - : reg(RoundupSize(t.WordCount())), sign(t.sign) -{ - CopyWords(reg, t.reg, reg.size()); -} - -Integer::Integer(Sign s, lword value) - : reg(2), sign(s) -{ - reg[0] = word(value); - reg[1] = word(SafeRightShift(value)); -} - -Integer::Integer(signed long value) - : reg(2) -{ - if (value >= 0) - sign = POSITIVE; - else - { - sign = NEGATIVE; - value = -value; - } - reg[0] = word(value); - reg[1] = word(SafeRightShift((unsigned long)value)); -} - -Integer::Integer(Sign s, word high, word low) - : reg(2), sign(s) -{ - reg[0] = low; - reg[1] = high; -} - -bool Integer::IsConvertableToLong() const -{ - if (ByteCount() > sizeof(long)) - return false; - - unsigned long value = (unsigned long)reg[0]; - value += SafeLeftShift((unsigned long)reg[1]); - - if (sign==POSITIVE) - return (signed long)value >= 0; - else - return -(signed long)value < 0; -} - -signed long Integer::ConvertToLong() const -{ - assert(IsConvertableToLong()); - - unsigned long value = (unsigned long)reg[0]; - value += SafeLeftShift((unsigned long)reg[1]); - return sign==POSITIVE ? value : -(signed long)value; -} - -Integer::Integer(BufferedTransformation &encodedInteger, size_t byteCount, Signedness s) -{ - Decode(encodedInteger, byteCount, s); -} - -Integer::Integer(const byte *encodedInteger, size_t byteCount, Signedness s) -{ - Decode(encodedInteger, byteCount, s); -} - -Integer::Integer(BufferedTransformation &bt) -{ - BERDecode(bt); -} - -Integer::Integer(RandomNumberGenerator &rng, size_t bitcount) -{ - Randomize(rng, bitcount); -} - -Integer::Integer(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv, const Integer &mod) -{ - if (!Randomize(rng, min, max, rnType, equiv, mod)) - throw Integer::RandomNumberNotFound(); -} - -Integer Integer::Power2(size_t e) -{ - Integer r((word)0, BitsToWords(e+1)); - r.SetBit(e); - return r; -} - -template -struct NewInteger -{ - Integer * operator()() const - { - return new Integer(i); - } -}; - -const Integer &Integer::Zero() -{ - return Singleton().Ref(); -} - -const Integer &Integer::One() -{ - return Singleton >().Ref(); -} - -const Integer &Integer::Two() -{ - return Singleton >().Ref(); -} - -bool Integer::operator!() const -{ - return IsNegative() ? false : (reg[0]==0 && WordCount()==0); -} - -Integer& Integer::operator=(const Integer& t) -{ - if (this != &t) - { - if (reg.size() != t.reg.size() || t.reg[t.reg.size()/2] == 0) - reg.New(RoundupSize(t.WordCount())); - CopyWords(reg, t.reg, reg.size()); - sign = t.sign; - } - return *this; -} - -bool Integer::GetBit(size_t n) const -{ - if (n/WORD_BITS >= reg.size()) - return 0; - else - return bool((reg[n/WORD_BITS] >> (n % WORD_BITS)) & 1); -} - -void Integer::SetBit(size_t n, bool value) -{ - if (value) - { - reg.CleanGrow(RoundupSize(BitsToWords(n+1))); - reg[n/WORD_BITS] |= (word(1) << (n%WORD_BITS)); - } - else - { - if (n/WORD_BITS < reg.size()) - reg[n/WORD_BITS] &= ~(word(1) << (n%WORD_BITS)); - } -} - -byte Integer::GetByte(size_t n) const -{ - if (n/WORD_SIZE >= reg.size()) - return 0; - else - return byte(reg[n/WORD_SIZE] >> ((n%WORD_SIZE)*8)); -} - -void Integer::SetByte(size_t n, byte value) -{ - reg.CleanGrow(RoundupSize(BytesToWords(n+1))); - reg[n/WORD_SIZE] &= ~(word(0xff) << 8*(n%WORD_SIZE)); - reg[n/WORD_SIZE] |= (word(value) << 8*(n%WORD_SIZE)); -} - -lword Integer::GetBits(size_t i, size_t n) const -{ - lword v = 0; - assert(n <= sizeof(v)*8); - for (unsigned int j=0; j -static Integer StringToInteger(const T *str) -{ - int radix; - // GCC workaround - // std::char_traits::length() not defined in GCC 3.2 and STLport 4.5.3 - unsigned int length; - for (length = 0; str[length] != 0; length++) {} - - Integer v; - - if (length == 0) - return v; - - switch (str[length-1]) - { - case 'h': - case 'H': - radix=16; - break; - case 'o': - case 'O': - radix=8; - break; - case 'b': - case 'B': - radix=2; - break; - default: - radix=10; - } - - if (length > 2 && str[0] == '0' && str[1] == 'x') - radix = 16; - - for (unsigned i=0; i= '0' && str[i] <= '9') - digit = str[i] - '0'; - else if (str[i] >= 'A' && str[i] <= 'F') - digit = str[i] - 'A' + 10; - else if (str[i] >= 'a' && str[i] <= 'f') - digit = str[i] - 'a' + 10; - else - digit = radix; - - if (digit < radix) - { - v *= radix; - v += digit; - } - } - - if (str[0] == '-') - v.Negate(); - - return v; -} - -Integer::Integer(const char *str) - : reg(2), sign(POSITIVE) -{ - *this = StringToInteger(str); -} - -Integer::Integer(const wchar_t *str) - : reg(2), sign(POSITIVE) -{ - *this = StringToInteger(str); -} - -unsigned int Integer::WordCount() const -{ - return (unsigned int)CountWords(reg, reg.size()); -} - -unsigned int Integer::ByteCount() const -{ - unsigned wordCount = WordCount(); - if (wordCount) - return (wordCount-1)*WORD_SIZE + BytePrecision(reg[wordCount-1]); - else - return 0; -} - -unsigned int Integer::BitCount() const -{ - unsigned wordCount = WordCount(); - if (wordCount) - return (wordCount-1)*WORD_BITS + BitPrecision(reg[wordCount-1]); - else - return 0; -} - -void Integer::Decode(const byte *input, size_t inputLen, Signedness s) -{ - StringStore store(input, inputLen); - Decode(store, inputLen, s); -} - -void Integer::Decode(BufferedTransformation &bt, size_t inputLen, Signedness s) -{ - assert(bt.MaxRetrievable() >= inputLen); - - byte b; - bt.Peek(b); - sign = ((s==SIGNED) && (b & 0x80)) ? NEGATIVE : POSITIVE; - - while (inputLen>0 && (sign==POSITIVE ? b==0 : b==0xff)) - { - bt.Skip(1); - inputLen--; - bt.Peek(b); - } - - reg.CleanNew(RoundupSize(BytesToWords(inputLen))); - - for (size_t i=inputLen; i > 0; i--) - { - bt.Get(b); - reg[(i-1)/WORD_SIZE] |= word(b) << ((i-1)%WORD_SIZE)*8; - } - - if (sign == NEGATIVE) - { - for (size_t i=inputLen; i 0; i--) - bt.Put(GetByte(i-1)); - } - else - { - // take two's complement of *this - Integer temp = Integer::Power2(8*STDMAX((size_t)ByteCount(), outputLen)) + *this; - temp.Encode(bt, outputLen, UNSIGNED); - } -} - -void Integer::DEREncode(BufferedTransformation &bt) const -{ - DERGeneralEncoder enc(bt, INTEGER); - Encode(enc, MinEncodedSize(SIGNED), SIGNED); - enc.MessageEnd(); -} - -void Integer::BERDecode(const byte *input, size_t len) -{ - StringStore store(input, len); - BERDecode(store); -} - -void Integer::BERDecode(BufferedTransformation &bt) -{ - BERGeneralDecoder dec(bt, INTEGER); - if (!dec.IsDefiniteLength() || dec.MaxRetrievable() < dec.RemainingLength()) - BERDecodeError(); - Decode(dec, (size_t)dec.RemainingLength(), SIGNED); - dec.MessageEnd(); -} - -void Integer::DEREncodeAsOctetString(BufferedTransformation &bt, size_t length) const -{ - DERGeneralEncoder enc(bt, OCTET_STRING); - Encode(enc, length); - enc.MessageEnd(); -} - -void Integer::BERDecodeAsOctetString(BufferedTransformation &bt, size_t length) -{ - BERGeneralDecoder dec(bt, OCTET_STRING); - if (!dec.IsDefiniteLength() || dec.RemainingLength() != length) - BERDecodeError(); - Decode(dec, length); - dec.MessageEnd(); -} - -size_t Integer::OpenPGPEncode(byte *output, size_t len) const -{ - ArraySink sink(output, len); - return OpenPGPEncode(sink); -} - -size_t Integer::OpenPGPEncode(BufferedTransformation &bt) const -{ - word16 bitCount = BitCount(); - bt.PutWord16(bitCount); - size_t byteCount = BitsToBytes(bitCount); - Encode(bt, byteCount); - return 2 + byteCount; -} - -void Integer::OpenPGPDecode(const byte *input, size_t len) -{ - StringStore store(input, len); - OpenPGPDecode(store); -} - -void Integer::OpenPGPDecode(BufferedTransformation &bt) -{ - word16 bitCount; - if (bt.GetWord16(bitCount) != 2 || bt.MaxRetrievable() < BitsToBytes(bitCount)) - throw OpenPGPDecodeErr(); - Decode(bt, BitsToBytes(bitCount)); -} - -void Integer::Randomize(RandomNumberGenerator &rng, size_t nbits) -{ - const size_t nbytes = nbits/8 + 1; - SecByteBlock buf(nbytes); - rng.GenerateBlock(buf, nbytes); - if (nbytes) - buf[0] = (byte)Crop(buf[0], nbits % 8); - Decode(buf, nbytes, UNSIGNED); -} - -void Integer::Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max) -{ - if (min > max) - throw InvalidArgument("Integer: Min must be no greater than Max"); - - Integer range = max - min; - const unsigned int nbits = range.BitCount(); - - do - { - Randomize(rng, nbits); - } - while (*this > range); - - *this += min; -} - -bool Integer::Randomize(RandomNumberGenerator &rng, const Integer &min, const Integer &max, RandomNumberType rnType, const Integer &equiv, const Integer &mod) -{ - return GenerateRandomNoThrow(rng, MakeParameters("Min", min)("Max", max)("RandomNumberType", rnType)("EquivalentTo", equiv)("Mod", mod)); -} - -class KDF2_RNG : public RandomNumberGenerator -{ -public: - KDF2_RNG(const byte *seed, size_t seedSize) - : m_counter(0), m_counterAndSeed(seedSize + 4) - { - memcpy(m_counterAndSeed + 4, seed, seedSize); - } - - void GenerateBlock(byte *output, size_t size) - { - PutWord(false, BIG_ENDIAN_ORDER, m_counterAndSeed, m_counter); - ++m_counter; - P1363_KDF2::DeriveKey(output, size, m_counterAndSeed, m_counterAndSeed.size(), NULL, 0); - } - -private: - word32 m_counter; - SecByteBlock m_counterAndSeed; -}; - -bool Integer::GenerateRandomNoThrow(RandomNumberGenerator &i_rng, const NameValuePairs ¶ms) -{ - Integer min = params.GetValueWithDefault("Min", Integer::Zero()); - Integer max; - if (!params.GetValue("Max", max)) - { - int bitLength; - if (params.GetIntValue("BitLength", bitLength)) - max = Integer::Power2(bitLength); - else - throw InvalidArgument("Integer: missing Max argument"); - } - if (min > max) - throw InvalidArgument("Integer: Min must be no greater than Max"); - - Integer equiv = params.GetValueWithDefault("EquivalentTo", Integer::Zero()); - Integer mod = params.GetValueWithDefault("Mod", Integer::One()); - - if (equiv.IsNegative() || equiv >= mod) - throw InvalidArgument("Integer: invalid EquivalentTo and/or Mod argument"); - - Integer::RandomNumberType rnType = params.GetValueWithDefault("RandomNumberType", Integer::ANY); - - member_ptr kdf2Rng; - ConstByteArrayParameter seed; - if (params.GetValue(Name::Seed(), seed)) - { - ByteQueue bq; - DERSequenceEncoder seq(bq); - min.DEREncode(seq); - max.DEREncode(seq); - equiv.DEREncode(seq); - mod.DEREncode(seq); - DEREncodeUnsigned(seq, rnType); - DEREncodeOctetString(seq, seed.begin(), seed.size()); - seq.MessageEnd(); - - SecByteBlock finalSeed((size_t)bq.MaxRetrievable()); - bq.Get(finalSeed, finalSeed.size()); - kdf2Rng.reset(new KDF2_RNG(finalSeed.begin(), finalSeed.size())); - } - RandomNumberGenerator &rng = kdf2Rng.get() ? (RandomNumberGenerator &)*kdf2Rng : i_rng; - - switch (rnType) - { - case ANY: - if (mod == One()) - Randomize(rng, min, max); - else - { - Integer min1 = min + (equiv-min)%mod; - if (max < min1) - return false; - Randomize(rng, Zero(), (max - min1) / mod); - *this *= mod; - *this += min1; - } - return true; - - case PRIME: - { - const PrimeSelector *pSelector = params.GetValueWithDefault(Name::PointerToPrimeSelector(), (const PrimeSelector *)NULL); - - int i; - i = 0; - while (1) - { - if (++i==16) - { - // check if there are any suitable primes in [min, max] - Integer first = min; - if (FirstPrime(first, max, equiv, mod, pSelector)) - { - // if there is only one suitable prime, we're done - *this = first; - if (!FirstPrime(first, max, equiv, mod, pSelector)) - return true; - } - else - return false; - } - - Randomize(rng, min, max); - if (FirstPrime(*this, STDMIN(*this+mod*PrimeSearchInterval(max), max), equiv, mod, pSelector)) - return true; - } - } - - default: - throw InvalidArgument("Integer: invalid RandomNumberType argument"); - } -} - -std::istream& operator>>(std::istream& in, Integer &a) -{ - char c; - unsigned int length = 0; - SecBlock str(length + 16); - - std::ws(in); - - do - { - in.read(&c, 1); - str[length++] = c; - if (length >= str.size()) - str.Grow(length + 16); - } - 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=='.')); - - if (in.gcount()) - in.putback(c); - str[length-1] = '\0'; - a = Integer(str); - - return in; -} - -std::ostream& operator<<(std::ostream& out, const Integer &a) -{ - // Get relevant conversion specifications from ostream. - long f = out.flags() & std::ios::basefield; // Get base digits. - int base, block; - char suffix; - switch(f) - { - case std::ios::oct : - base = 8; - block = 8; - suffix = 'o'; - break; - case std::ios::hex : - base = 16; - block = 4; - suffix = 'h'; - break; - default : - base = 10; - block = 3; - suffix = '.'; - } - - Integer temp1=a, temp2; - - if (a.IsNegative()) - { - out << '-'; - temp1.Negate(); - } - - if (!a) - out << '0'; - - static const char upper[]="0123456789ABCDEF"; - static const char lower[]="0123456789abcdef"; - - const char* vec = (out.flags() & std::ios::uppercase) ? upper : lower; - unsigned i=0; - SecBlock s(a.BitCount() / (BitPrecision(base)-1) + 1); - - while (!!temp1) - { - word digit; - Integer::Divide(digit, temp2, temp1, base); - s[i++]=vec[digit]; - temp1.swap(temp2); - } - - while (i--) - { - out << s[i]; -// if (i && !(i%block)) -// out << ","; - } - return out << suffix; -} - -Integer& Integer::operator++() -{ - if (NotNegative()) - { - if (Increment(reg, reg.size())) - { - reg.CleanGrow(2*reg.size()); - reg[reg.size()/2]=1; - } - } - else - { - word borrow = Decrement(reg, reg.size()); - assert(!borrow); - if (WordCount()==0) - *this = Zero(); - } - return *this; -} - -Integer& Integer::operator--() -{ - if (IsNegative()) - { - if (Increment(reg, reg.size())) - { - reg.CleanGrow(2*reg.size()); - reg[reg.size()/2]=1; - } - } - else - { - if (Decrement(reg, reg.size())) - *this = -One(); - } - return *this; -} - -void PositiveAdd(Integer &sum, const Integer &a, const Integer& b) -{ - int carry; - if (a.reg.size() == b.reg.size()) - carry = Add(sum.reg, a.reg, b.reg, a.reg.size()); - else if (a.reg.size() > b.reg.size()) - { - carry = Add(sum.reg, a.reg, b.reg, b.reg.size()); - CopyWords(sum.reg+b.reg.size(), a.reg+b.reg.size(), a.reg.size()-b.reg.size()); - carry = Increment(sum.reg+b.reg.size(), a.reg.size()-b.reg.size(), carry); - } - else - { - carry = Add(sum.reg, a.reg, b.reg, a.reg.size()); - CopyWords(sum.reg+a.reg.size(), b.reg+a.reg.size(), b.reg.size()-a.reg.size()); - carry = Increment(sum.reg+a.reg.size(), b.reg.size()-a.reg.size(), carry); - } - - if (carry) - { - sum.reg.CleanGrow(2*sum.reg.size()); - sum.reg[sum.reg.size()/2] = 1; - } - sum.sign = Integer::POSITIVE; -} - -void PositiveSubtract(Integer &diff, const Integer &a, const Integer& b) -{ - unsigned aSize = a.WordCount(); - aSize += aSize%2; - unsigned bSize = b.WordCount(); - bSize += bSize%2; - - if (aSize == bSize) - { - if (Compare(a.reg, b.reg, aSize) >= 0) - { - Subtract(diff.reg, a.reg, b.reg, aSize); - diff.sign = Integer::POSITIVE; - } - else - { - Subtract(diff.reg, b.reg, a.reg, aSize); - diff.sign = Integer::NEGATIVE; - } - } - else if (aSize > bSize) - { - word borrow = Subtract(diff.reg, a.reg, b.reg, bSize); - CopyWords(diff.reg+bSize, a.reg+bSize, aSize-bSize); - borrow = Decrement(diff.reg+bSize, aSize-bSize, borrow); - assert(!borrow); - diff.sign = Integer::POSITIVE; - } - else - { - word borrow = Subtract(diff.reg, b.reg, a.reg, aSize); - CopyWords(diff.reg+aSize, b.reg+aSize, bSize-aSize); - borrow = Decrement(diff.reg+aSize, bSize-aSize, borrow); - assert(!borrow); - diff.sign = Integer::NEGATIVE; - } -} - -// MSVC .NET 2003 workaround -template inline const T& STDMAX2(const T& a, const T& b) -{ - return a < b ? b : a; -} - -Integer Integer::Plus(const Integer& b) const -{ - Integer sum((word)0, STDMAX2(reg.size(), b.reg.size())); - if (NotNegative()) - { - if (b.NotNegative()) - PositiveAdd(sum, *this, b); - else - PositiveSubtract(sum, *this, b); - } - else - { - if (b.NotNegative()) - PositiveSubtract(sum, b, *this); - else - { - PositiveAdd(sum, *this, b); - sum.sign = Integer::NEGATIVE; - } - } - return sum; -} - -Integer& Integer::operator+=(const Integer& t) -{ - reg.CleanGrow(t.reg.size()); - if (NotNegative()) - { - if (t.NotNegative()) - PositiveAdd(*this, *this, t); - else - PositiveSubtract(*this, *this, t); - } - else - { - if (t.NotNegative()) - PositiveSubtract(*this, t, *this); - else - { - PositiveAdd(*this, *this, t); - sign = Integer::NEGATIVE; - } - } - return *this; -} - -Integer Integer::Minus(const Integer& b) const -{ - Integer diff((word)0, STDMAX2(reg.size(), b.reg.size())); - if (NotNegative()) - { - if (b.NotNegative()) - PositiveSubtract(diff, *this, b); - else - PositiveAdd(diff, *this, b); - } - else - { - if (b.NotNegative()) - { - PositiveAdd(diff, *this, b); - diff.sign = Integer::NEGATIVE; - } - else - PositiveSubtract(diff, b, *this); - } - return diff; -} - -Integer& Integer::operator-=(const Integer& t) -{ - reg.CleanGrow(t.reg.size()); - if (NotNegative()) - { - if (t.NotNegative()) - PositiveSubtract(*this, *this, t); - else - PositiveAdd(*this, *this, t); - } - else - { - if (t.NotNegative()) - { - PositiveAdd(*this, *this, t); - sign = Integer::NEGATIVE; - } - else - PositiveSubtract(*this, t, *this); - } - return *this; -} - -Integer& Integer::operator<<=(size_t n) -{ - const size_t wordCount = WordCount(); - const size_t shiftWords = n / WORD_BITS; - const unsigned int shiftBits = (unsigned int)(n % WORD_BITS); - - reg.CleanGrow(RoundupSize(wordCount+BitsToWords(n))); - ShiftWordsLeftByWords(reg, wordCount + shiftWords, shiftWords); - ShiftWordsLeftByBits(reg+shiftWords, wordCount+BitsToWords(shiftBits), shiftBits); - return *this; -} - -Integer& Integer::operator>>=(size_t n) -{ - const size_t wordCount = WordCount(); - const size_t shiftWords = n / WORD_BITS; - const unsigned int shiftBits = (unsigned int)(n % WORD_BITS); - - ShiftWordsRightByWords(reg, wordCount, shiftWords); - if (wordCount > shiftWords) - ShiftWordsRightByBits(reg, wordCount-shiftWords, shiftBits); - if (IsNegative() && WordCount()==0) // avoid -0 - *this = Zero(); - return *this; -} - -void PositiveMultiply(Integer &product, const Integer &a, const Integer &b) -{ - size_t aSize = RoundupSize(a.WordCount()); - size_t bSize = RoundupSize(b.WordCount()); - - product.reg.CleanNew(RoundupSize(aSize+bSize)); - product.sign = Integer::POSITIVE; - - IntegerSecBlock workspace(aSize + bSize); - AsymmetricMultiply(product.reg, workspace, a.reg, aSize, b.reg, bSize); -} - -void Multiply(Integer &product, const Integer &a, const Integer &b) -{ - PositiveMultiply(product, a, b); - - if (a.NotNegative() != b.NotNegative()) - product.Negate(); -} - -Integer Integer::Times(const Integer &b) const -{ - Integer product; - Multiply(product, *this, b); - return product; -} - -/* -void PositiveDivide(Integer &remainder, Integer "ient, - const Integer ÷nd, const Integer &divisor) -{ - remainder.reg.CleanNew(divisor.reg.size()); - remainder.sign = Integer::POSITIVE; - quotient.reg.New(0); - quotient.sign = Integer::POSITIVE; - unsigned i=dividend.BitCount(); - while (i--) - { - word overflow = ShiftWordsLeftByBits(remainder.reg, remainder.reg.size(), 1); - remainder.reg[0] |= dividend[i]; - if (overflow || remainder >= divisor) - { - Subtract(remainder.reg, remainder.reg, divisor.reg, remainder.reg.size()); - quotient.SetBit(i); - } - } -} -*/ - -void PositiveDivide(Integer &remainder, Integer "ient, - const Integer &a, const Integer &b) -{ - unsigned aSize = a.WordCount(); - unsigned bSize = b.WordCount(); - - if (!bSize) - throw Integer::DivideByZero(); - - if (aSize < bSize) - { - remainder = a; - remainder.sign = Integer::POSITIVE; - quotient = Integer::Zero(); - return; - } - - aSize += aSize%2; // round up to next even number - bSize += bSize%2; - - remainder.reg.CleanNew(RoundupSize(bSize)); - remainder.sign = Integer::POSITIVE; - quotient.reg.CleanNew(RoundupSize(aSize-bSize+2)); - quotient.sign = Integer::POSITIVE; - - IntegerSecBlock T(aSize+3*(bSize+2)); - Divide(remainder.reg, quotient.reg, T, a.reg, aSize, b.reg, bSize); -} - -void Integer::Divide(Integer &remainder, Integer "ient, const Integer ÷nd, const Integer &divisor) -{ - PositiveDivide(remainder, quotient, dividend, divisor); - - if (dividend.IsNegative()) - { - quotient.Negate(); - if (remainder.NotZero()) - { - --quotient; - remainder = divisor.AbsoluteValue() - remainder; - } - } - - if (divisor.IsNegative()) - quotient.Negate(); -} - -void Integer::DivideByPowerOf2(Integer &r, Integer &q, const Integer &a, unsigned int n) -{ - q = a; - q >>= n; - - const size_t wordCount = BitsToWords(n); - if (wordCount <= a.WordCount()) - { - r.reg.resize(RoundupSize(wordCount)); - CopyWords(r.reg, a.reg, wordCount); - SetWords(r.reg+wordCount, 0, r.reg.size()-wordCount); - if (n % WORD_BITS != 0) - r.reg[wordCount-1] %= (word(1) << (n % WORD_BITS)); - } - else - { - r.reg.resize(RoundupSize(a.WordCount())); - CopyWords(r.reg, a.reg, r.reg.size()); - } - r.sign = POSITIVE; - - if (a.IsNegative() && r.NotZero()) - { - --q; - r = Power2(n) - r; - } -} - -Integer Integer::DividedBy(const Integer &b) const -{ - Integer remainder, quotient; - Integer::Divide(remainder, quotient, *this, b); - return quotient; -} - -Integer Integer::Modulo(const Integer &b) const -{ - Integer remainder, quotient; - Integer::Divide(remainder, quotient, *this, b); - return remainder; -} - -void Integer::Divide(word &remainder, Integer "ient, const Integer ÷nd, word divisor) -{ - if (!divisor) - throw Integer::DivideByZero(); - - assert(divisor); - - if ((divisor & (divisor-1)) == 0) // divisor is a power of 2 - { - quotient = dividend >> (BitPrecision(divisor)-1); - remainder = dividend.reg[0] & (divisor-1); - return; - } - - unsigned int i = dividend.WordCount(); - quotient.reg.CleanNew(RoundupSize(i)); - remainder = 0; - while (i--) - { - quotient.reg[i] = DWord(dividend.reg[i], remainder) / divisor; - remainder = DWord(dividend.reg[i], remainder) % divisor; - } - - if (dividend.NotNegative()) - quotient.sign = POSITIVE; - else - { - quotient.sign = NEGATIVE; - if (remainder) - { - --quotient; - remainder = divisor - remainder; - } - } -} - -Integer Integer::DividedBy(word b) const -{ - word remainder; - Integer quotient; - Integer::Divide(remainder, quotient, *this, b); - return quotient; -} - -word Integer::Modulo(word divisor) const -{ - if (!divisor) - throw Integer::DivideByZero(); - - assert(divisor); - - word remainder; - - if ((divisor & (divisor-1)) == 0) // divisor is a power of 2 - remainder = reg[0] & (divisor-1); - else - { - unsigned int i = WordCount(); - - if (divisor <= 5) - { - DWord sum(0, 0); - while (i--) - sum += reg[i]; - remainder = sum % divisor; - } - else - { - remainder = 0; - while (i--) - remainder = DWord(reg[i], remainder) % divisor; - } - } - - if (IsNegative() && remainder) - remainder = divisor - remainder; - - return remainder; -} - -void Integer::Negate() -{ - if (!!(*this)) // don't flip sign if *this==0 - sign = Sign(1-sign); -} - -int Integer::PositiveCompare(const Integer& t) const -{ - unsigned size = WordCount(), tSize = t.WordCount(); - - if (size == tSize) - return CryptoPP::Compare(reg, t.reg, size); - else - return size > tSize ? 1 : -1; -} - -int Integer::Compare(const Integer& t) const -{ - if (NotNegative()) - { - if (t.NotNegative()) - return PositiveCompare(t); - else - return 1; - } - else - { - if (t.NotNegative()) - return -1; - else - return -PositiveCompare(t); - } -} - -Integer Integer::SquareRoot() const -{ - if (!IsPositive()) - return Zero(); - - // overestimate square root - Integer x, y = Power2((BitCount()+1)/2); - assert(y*y >= *this); - - do - { - x = y; - y = (x + *this/x) >> 1; - } while (y().Gcd(a, b); -} - -Integer Integer::InverseMod(const Integer &m) const -{ - assert(m.NotNegative()); - - if (IsNegative()) - return Modulo(m).InverseMod(m); - - if (m.IsEven()) - { - if (!m || IsEven()) - return Zero(); // no inverse - if (*this == One()) - return One(); - - Integer u = m.Modulo(*this).InverseMod(*this); - return !u ? Zero() : (m*(*this-u)+1)/(*this); - } - - SecBlock T(m.reg.size() * 4); - Integer r((word)0, m.reg.size()); - unsigned k = AlmostInverse(r.reg, T, reg, reg.size(), m.reg, m.reg.size()); - DivideByPower2Mod(r.reg, r.reg, k, m.reg, m.reg.size()); - return r; -} - -word Integer::InverseMod(word mod) const -{ - word g0 = mod, g1 = *this % mod; - word v0 = 0, v1 = 1; - word y; - - while (g1) - { - if (g1 == 1) - return v1; - y = g0 / g1; - g0 = g0 % g1; - v0 += y * v1; - - if (!g0) - break; - if (g0 == 1) - return mod-v0; - y = g1 / g0; - g1 = g1 % g0; - v1 += y * v0; - } - return 0; -} - -// ******************************************************** - -ModularArithmetic::ModularArithmetic(BufferedTransformation &bt) -{ - BERSequenceDecoder seq(bt); - OID oid(seq); - if (oid != ASN1::prime_field()) - BERDecodeError(); - m_modulus.BERDecode(seq); - seq.MessageEnd(); - m_result.reg.resize(m_modulus.reg.size()); -} - -void ModularArithmetic::DEREncode(BufferedTransformation &bt) const -{ - DERSequenceEncoder seq(bt); - ASN1::prime_field().DEREncode(seq); - m_modulus.DEREncode(seq); - seq.MessageEnd(); -} - -void ModularArithmetic::DEREncodeElement(BufferedTransformation &out, const Element &a) const -{ - a.DEREncodeAsOctetString(out, MaxElementByteLength()); -} - -void ModularArithmetic::BERDecodeElement(BufferedTransformation &in, Element &a) const -{ - a.BERDecodeAsOctetString(in, MaxElementByteLength()); -} - -const Integer& ModularArithmetic::Half(const Integer &a) const -{ - if (a.reg.size()==m_modulus.reg.size()) - { - CryptoPP::DivideByPower2Mod(m_result.reg.begin(), a.reg, 1, m_modulus.reg, a.reg.size()); - return m_result; - } - else - return m_result1 = (a.IsEven() ? (a >> 1) : ((a+m_modulus) >> 1)); -} - -const Integer& ModularArithmetic::Add(const Integer &a, const Integer &b) const -{ - if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size()) - { - if (CryptoPP::Add(m_result.reg.begin(), a.reg, b.reg, a.reg.size()) - || Compare(m_result.reg, m_modulus.reg, a.reg.size()) >= 0) - { - CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.size()); - } - return m_result; - } - else - { - m_result1 = a+b; - if (m_result1 >= m_modulus) - m_result1 -= m_modulus; - return m_result1; - } -} - -Integer& ModularArithmetic::Accumulate(Integer &a, const Integer &b) const -{ - if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size()) - { - if (CryptoPP::Add(a.reg, a.reg, b.reg, a.reg.size()) - || Compare(a.reg, m_modulus.reg, a.reg.size()) >= 0) - { - CryptoPP::Subtract(a.reg, a.reg, m_modulus.reg, a.reg.size()); - } - } - else - { - a+=b; - if (a>=m_modulus) - a-=m_modulus; - } - - return a; -} - -const Integer& ModularArithmetic::Subtract(const Integer &a, const Integer &b) const -{ - if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size()) - { - if (CryptoPP::Subtract(m_result.reg.begin(), a.reg, b.reg, a.reg.size())) - CryptoPP::Add(m_result.reg.begin(), m_result.reg, m_modulus.reg, a.reg.size()); - return m_result; - } - else - { - m_result1 = a-b; - if (m_result1.IsNegative()) - m_result1 += m_modulus; - return m_result1; - } -} - -Integer& ModularArithmetic::Reduce(Integer &a, const Integer &b) const -{ - if (a.reg.size()==m_modulus.reg.size() && b.reg.size()==m_modulus.reg.size()) - { - if (CryptoPP::Subtract(a.reg, a.reg, b.reg, a.reg.size())) - CryptoPP::Add(a.reg, a.reg, m_modulus.reg, a.reg.size()); - } - else - { - a-=b; - if (a.IsNegative()) - a+=m_modulus; - } - - return a; -} - -const Integer& ModularArithmetic::Inverse(const Integer &a) const -{ - if (!a) - return a; - - CopyWords(m_result.reg.begin(), m_modulus.reg, m_modulus.reg.size()); - if (CryptoPP::Subtract(m_result.reg.begin(), m_result.reg, a.reg, a.reg.size())) - Decrement(m_result.reg.begin()+a.reg.size(), m_modulus.reg.size()-a.reg.size()); - - return m_result; -} - -Integer ModularArithmetic::CascadeExponentiate(const Integer &x, const Integer &e1, const Integer &y, const Integer &e2) const -{ - if (m_modulus.IsOdd()) - { - MontgomeryRepresentation dr(m_modulus); - return dr.ConvertOut(dr.CascadeExponentiate(dr.ConvertIn(x), e1, dr.ConvertIn(y), e2)); - } - else - return AbstractRing::CascadeExponentiate(x, e1, y, e2); -} - -void ModularArithmetic::SimultaneousExponentiate(Integer *results, const Integer &base, const Integer *exponents, unsigned int exponentsCount) const -{ - if (m_modulus.IsOdd()) - { - MontgomeryRepresentation dr(m_modulus); - dr.SimultaneousExponentiate(results, dr.ConvertIn(base), exponents, exponentsCount); - for (unsigned int i=0; i::SimultaneousExponentiate(results, base, exponents, exponentsCount); -} - -MontgomeryRepresentation::MontgomeryRepresentation(const Integer &m) // modulus must be odd - : ModularArithmetic(m), - m_u((word)0, m_modulus.reg.size()), - m_workspace(5*m_modulus.reg.size()) -{ - if (!m_modulus.IsOdd()) - throw InvalidArgument("MontgomeryRepresentation: Montgomery representation requires an odd modulus"); - - RecursiveInverseModPower2(m_u.reg, m_workspace, m_modulus.reg, m_modulus.reg.size()); -} - -const Integer& MontgomeryRepresentation::Multiply(const Integer &a, const Integer &b) const -{ - word *const T = m_workspace.begin(); - word *const R = m_result.reg.begin(); - const size_t N = m_modulus.reg.size(); - assert(a.reg.size()<=N && b.reg.size()<=N); - - AsymmetricMultiply(T, T+2*N, a.reg, a.reg.size(), b.reg, b.reg.size()); - SetWords(T+a.reg.size()+b.reg.size(), 0, 2*N-a.reg.size()-b.reg.size()); - MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N); - return m_result; -} - -const Integer& MontgomeryRepresentation::Square(const Integer &a) const -{ - word *const T = m_workspace.begin(); - word *const R = m_result.reg.begin(); - const size_t N = m_modulus.reg.size(); - assert(a.reg.size()<=N); - - CryptoPP::Square(T, T+2*N, a.reg, a.reg.size()); - SetWords(T+2*a.reg.size(), 0, 2*N-2*a.reg.size()); - MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N); - return m_result; -} - -Integer MontgomeryRepresentation::ConvertOut(const Integer &a) const -{ - word *const T = m_workspace.begin(); - word *const R = m_result.reg.begin(); - const size_t N = m_modulus.reg.size(); - assert(a.reg.size()<=N); - - CopyWords(T, a.reg, a.reg.size()); - SetWords(T+a.reg.size(), 0, 2*N-a.reg.size()); - MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N); - return m_result; -} - -const Integer& MontgomeryRepresentation::MultiplicativeInverse(const Integer &a) const -{ -// return (EuclideanMultiplicativeInverse(a, modulus)<<(2*WORD_BITS*modulus.reg.size()))%modulus; - word *const T = m_workspace.begin(); - word *const R = m_result.reg.begin(); - const size_t N = m_modulus.reg.size(); - assert(a.reg.size()<=N); - - CopyWords(T, a.reg, a.reg.size()); - SetWords(T+a.reg.size(), 0, 2*N-a.reg.size()); - MontgomeryReduce(R, T+2*N, T, m_modulus.reg, m_u.reg, N); - unsigned k = AlmostInverse(R, T, R, N, m_modulus.reg, N); - -// cout << "k=" << k << " N*32=" << 32*N << endl; - - if (k>N*WORD_BITS) - DivideByPower2Mod(R, R, k-N*WORD_BITS, m_modulus.reg, N); - else - MultiplyByPower2Mod(R, R, N*WORD_BITS-k, m_modulus.reg, N); - - return m_result; -} - -NAMESPACE_END - -#endif -- cgit v1.2.3