From 7167ce41b61d2ba2cdb526777a4233eb84a3b66a Mon Sep 17 00:00:00 2001 From: Unit 193 Date: Sat, 6 Dec 2014 17:33:25 -0500 Subject: Imported Upstream version 2.99.6 --- SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp | 1151 ++++++++++++++++++++ SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.h | 294 +++++ SQLiteStudio3/coreSQLiteStudio/rsa/Key.cpp | 37 + SQLiteStudio3/coreSQLiteStudio/rsa/Key.h | 59 + SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.cpp | 37 + SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.h | 58 + .../coreSQLiteStudio/rsa/PrimeGenerator.cpp | 198 ++++ .../coreSQLiteStudio/rsa/PrimeGenerator.h | 71 ++ SQLiteStudio3/coreSQLiteStudio/rsa/RSA.cpp | 394 +++++++ SQLiteStudio3/coreSQLiteStudio/rsa/RSA.h | 130 +++ 10 files changed, 2429 insertions(+) create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.h create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/Key.cpp create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/Key.h create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.cpp create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.h create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.cpp create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.h create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/RSA.cpp create mode 100644 SQLiteStudio3/coreSQLiteStudio/rsa/RSA.h (limited to 'SQLiteStudio3/coreSQLiteStudio/rsa') diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp b/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp new file mode 100644 index 0000000..0579add --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.cpp @@ -0,0 +1,1151 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * BigInt.cpp + * + * Author: Nedim Srndic + * Release date: 14th of March 2008 + * + * This file contains the implementation for the BigInt class. + * + * There are two static constants defined in this file: + * + * - ULongMax : ULONG_MAX (defined in climits) of type BigInt + * Mainly used for speedup in the multiply() private member function. + * Represents the largest unsigned long integer a particular platform can + * handle. If a BigInt is <= ULongMax, it can be converted to unsigned + * long int. This is platform-specific. + * - SqrtUlongMax : sqrt(ULONG_MAX) of type BigInt + * Mainly used for speedup in the multiply() private member function. + * Represents the square root of the largest unsigned long integer a + * particular platform can handle. If two BigInts are <= SqrtULongMax, + * they can be converted to unsigned long int and safely multiplied + * by the CPU. This is platform-specific. + * + * **************************************************************************** + */ + +//comment the following line if you want to use long multiplication +//#define KARATSUBA + +#include "BigInt.h" +#include //strlen() +#include //ULONG_MAX +#include //vector +#include //operator std::string() +#include //reverse_copy(), copy(), copy_backward(), + //fill(), fill_n() + +using std::cout; +using std::endl; + +//define and initialize BigInt::FACTOR +const double BigInt::FACTOR = 1.6; + +//A BigInt number with the value of ULONG_MAX +static const BigInt ULongMax(ULONG_MAX); +//A BigInt number with the value of sqrt(ULONG_MAX) +static const BigInt SqrtULongMax + (static_cast(sqrt(static_cast(ULONG_MAX)))); + +/* Transforms the number from unsigned long int to unsigned char[] + * and pads the result with zeroes. Returns the number of digits. */ +unsigned long int BigInt::int2uchar(unsigned long int number, + unsigned char *digits, + unsigned long int padding = 0L) +{ + int i(0); + do + { + //the number is stored in reverse + //(i.e. long int 456 is stored as unsigned char[] {[6][5][4]}) + digits[i++] = (unsigned char) (number % 10); + number /= 10; + } while (number > 0L); + + std::fill_n(digits + i, padding, 0); + return i; +} + +/* Converts ASCII digits to equivalent unsigned char numeric values. */ +void BigInt::char2uchar(unsigned char *array, + unsigned long int length) +{ + for (unsigned long int i(0L); i < length; i++) + array[i] -= '0'; +} + +/* Check if all ASCII values are digits '0' to '9'. */ +bool BigInt::allCharsAreDigits( const char *array, + unsigned long int length) +{ + for (unsigned long int i(0L); i < length; i++) + if (array[i] < '0' || array[i] > '9') + return false; + + return true; +} + +/* Compares two BigInt. If the last two arguments are + * omitted, the comparison is sign-insensitive (comparison by + * absolute value). Returns 0 if a == b, 1 if a > b, 2 if a < b. */ +int BigInt::compareNumbers( unsigned char *a, unsigned long int na, + unsigned char *b, unsigned long int nb, + bool aPositive, bool bPositive) +{ + if (na < nb || (!aPositive && bPositive)) + //a < b + return 2; + else if (na > nb || (aPositive && !bPositive)) + //a > b + return 1; + + //check the digits one by one starting from the most significant one + for (long int i = na - 1; i >= 0L; i--) + //compare the digits + if (a[i] != b[i]) + { + if (a[i] < b[i]) // |a| < |b| + if (aPositive) + return 2; // a < b + else + return 1; // a > b + else // |a| > |b| + if (aPositive) + return 1; // a > b + else + return 2; // a < b + } + + //a == b + return 0; +} + +/* Multiplies two unsigned char[] using the Divide and Conquer + * a.k.a. Karatsuba algorithm .*/ +void BigInt::karatsubaMultiply( unsigned char *a, unsigned char *b, + unsigned long int n, unsigned char *buf1) +{ + //if *a <= SqrtULongMax && *b <= SqrtULongMax, + //the CPU can do the multiplication + if (compareNumbers(a, n, SqrtULongMax.digits, SqrtULongMax.digitCount) != 1 + && + compareNumbers(b, n, SqrtULongMax.digits, SqrtULongMax.digitCount) != 1 + ) + { + int2uchar(toInt(a, n) * toInt(b, n), buf1, n << 1); + return; + } + + //nh = higher half digits, nl = lower half digits + //nh == nl || nh + 1 == nl + //nt is used to avoid too much nl + 1 addition operations + unsigned long int nh(n >> 1), nl(n - nh), nt(nl + 1); + //t1 is a temporary pointer, points to p1 + unsigned char *t1(buf1 + (n << 1)); + + BigInt::add(a + nl, nh, a, nl, buf1, nt); + BigInt::add(b + nl, nh, b, nl, buf1 + nt, nt); + BigInt::karatsubaMultiply(a + nl, b + nl, nh, t1); //p1 + BigInt::karatsubaMultiply(a, b, nl, t1 + (nh << 1)); //p2 + BigInt::karatsubaMultiply(buf1, buf1 + nt, nt, t1 + (n << 1));//p3 + + //for leftshifting p3 and p1 + unsigned long int power(n); + if (power & 1) + power++; + //since the original multiplier is not needed any more, we can reuse a + a = buf1 + (power >> 1); + //copy and shift left p3 by power / 2 and pad right to n * 2 with zeroes + std::fill(buf1, a, 0); + std::copy(t1 + (n << 1), t1 + ((n + nl) << 1) + 1, a); + std::fill(a + (nl << 1) + 1, t1, 0); + + //shifted p3 -= p2 + //a = shifted p3, b = p2 + BigInt::quickSub(a, t1 + (nh << 1), t1, nl); + + //shifted p3 -= p1 + //a = shifted p3, b = p1 + BigInt::quickSub(a, t1, t1, nh); + + //shifted p3 += shifted p1 + //a = p3[power], b = p1 + a = buf1 + power; + BigInt::quickAdd(a, t1, nh); + + //p3 += p2 + //a = p3, b = p2 + unsigned char carry = BigInt::quickAdd(buf1, t1 + (nh << 1), nl); + a = buf1 + (nl << 1); + for (unsigned long int i(0L); carry; i++) + { + a[i] += 1; + carry = a[i] / 10; + a[i] %= 10; + } +} + +/* Multiplies two unsigned char[] the long way. */ +void BigInt::longMultiply( unsigned char *a, unsigned long int na, + unsigned char *b, unsigned long int nb, + unsigned char *result) +{ + std::fill_n(result, na + nb, 0); + unsigned char mult(0); + int carry(0); + + for (unsigned long int i(0L); i < na; i++) + { + for (unsigned long int j(0L); j < nb; j++) + { + mult = a[i] * b[j] + result[i + j] + carry; + result[i + j] = static_cast(mult) % 10; + carry = static_cast(mult) / 10; + } + if (carry) + { + result[i + nb] += carry; + carry = 0; + } + } +} + +/* Simple addition, used by the multiply function. + * Returns the remaining carry. */ +unsigned char BigInt::quickAdd( unsigned char *a, unsigned char *b, + unsigned long int n) +{ + unsigned char carry(0), sum(0); + for (unsigned long int i(0L); i < (n << 1); i++) + { + sum = a[i] + b[i] + carry; + carry = sum / 10; + a[i] = sum % 10; + } + return carry; +} + +/* Simple subtraction, used by the multiply function. */ +void BigInt::quickSub( unsigned char *a, unsigned char *b, + unsigned char *end, unsigned long int n) +{ + unsigned char carry(0), sum(0); + for (unsigned long int i(0L); i < (n << 1); i++) + { + sum = 10 + a[i] - (b[i] + carry); + if (sum < 10) //carry + { + a[i] = sum; + carry = 1; + } + else + { + a[i] = sum % 10; + carry = 0; + } + } + a = &a[n << 1]; + for (; carry && a < end; a++) + if (*a) + { + (*a)--; + break; + } + else + *a = 9; +} + +/* Divides two BigInt numbers by the formula + * dividend = divisor * quotient + remainder*/ +void BigInt::divide(const BigInt ÷nd, const BigInt &divisor, + BigInt "ient, BigInt &remainder) +{ + BigInt Z1, R, X(dividend.Abs()); + /* Make sure quotient and remainder are zero. + * The lack of this assignment introduces a bug if the actual parameters + * are not zero when calling this function. */ + quotient = BigIntZero; + remainder = BigIntZero; + + // while |X| >= |divisor| + while (BigInt::compareNumbers( X.digits, X.digitCount, + divisor.digits, divisor.digitCount, + true, true) != 2) + { + unsigned long int O(X.digitCount - divisor.digitCount); + if (O <= ULongMax.digitCount - 2) + { + unsigned long int i; + if (X.digitCount > ULongMax.digitCount - 1) + i = ULongMax.digitCount - 1; + else + i = X.digitCount; + unsigned long int j(i - O); + Z1 = toInt(X.digits + X.digitCount - i, i) / + toInt(divisor.digits + divisor.digitCount - j, j); + } + else + { + unsigned long int i(ULongMax.digitCount - 1); + unsigned long int j; + if (divisor.digitCount > ULongMax.digitCount - 2) + j = ULongMax.digitCount - 2; + else + j = divisor.digitCount; + Z1 = toInt(X.digits + X.digitCount - i, i) / + toInt(divisor.digits + divisor.digitCount - j, j); + Z1.shiftLeft(O - Z1.digitCount); + } + + predictZ1: + R = (Z1 * divisor).Abs(); + + if (X >= R) + { + X = X - R; + quotient += Z1; + } + else + { + if (Z1.digitCount > 1) + Z1.shiftRight(1); + else + --Z1; + goto predictZ1; + } + } + + remainder = X; +} + +/* Returns the value of the specified unsigned char[] as long int. */ +unsigned long int BigInt::toInt(unsigned char *digits, int n) +{ + unsigned long int newInt(0L); + unsigned long int powerOf10(1); + for (int i(0); i < n; i++) + { + newInt += digits[i] * powerOf10; + powerOf10 *= 10; + } + return newInt; +} + +/* Saves the sum of two unsigned char* shorter and longer into result. + * It must be nShorter <= nLonger. If doFill == true, it fills the + * remaining free places with zeroes (used in KaratsubaMultiply()). + * Returns true if there was an overflow at the end (meaning that + * the result.digitCount was longer.digitCount + 1. */ +bool BigInt::add(unsigned char *shorter, unsigned long int nShorter, + unsigned char *longer, unsigned long int nLonger, + unsigned char *result, int nResult, bool doFill) +{ + //single digitwise sum and carry + unsigned char subSum(0); + unsigned char subCarry(0); + + //count the digits + unsigned long int i(0L); + + //add the digits + for (; i < nShorter; i++) + { + subSum = longer[i] + shorter[i] + subCarry; + subCarry = subSum / 10; + result[i] = subSum % 10; + } + + for (; i < nLonger; i++) + { + subSum = longer[i] + subCarry; + subCarry = subSum / 10; + result[i] = subSum % 10; + } + + if (doFill) + std::fill_n(result + i, nResult - i, 0); + + if (subCarry) + { + result[i++] = 1; + return true; + } + return false; +} + +/* Shifts the digits n places left. */ +BigInt &BigInt::shiftLeft(unsigned long int n) +{ + //if the number is 0, we won't shift it + if (EqualsZero()) + return *this; + if (length <= digitCount + n + 2) + expandTo(digitCount + n + 2); + + std::copy_backward(digits, digits + digitCount, digits + n + digitCount); + std::fill_n(digits, n, 0); + digitCount += n; + return *this; +} + +/* Shifts the digits n places right. */ +BigInt &BigInt::shiftRight(unsigned long int n) +{ + if (n >= digitCount) + throw "Error BIGINT00: Overflow on shift right."; + + std::copy_backward( digits + n, digits + digitCount, + digits + digitCount - n); + digitCount -= n; + return *this; +} + +/* Expands the digits* to n. */ +void BigInt::expandTo(unsigned long int n) +{ + unsigned long int oldLength(length); + length = n; + unsigned char *oldDigits(digits); + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + digits = oldDigits; + length = oldLength; + throw "Error BIGINT01: BigInt creation error (out of memory?)."; + } + + std::copy(oldDigits, oldDigits + digitCount, digits); + delete[] oldDigits; +} + +BigInt::BigInt() : digits(0), length(10), digitCount(1), positive(true) +{ + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT02: BigInt creation error (out of memory?)."; + } + + //initialize to 0 + digits[0] = 0; +} + +BigInt::BigInt(const char * charNum) : digits(0) +{ + digitCount = (unsigned long int) strlen(charNum); + + if (digitCount == 0L) + throw "Error BIGINT03: Input string empty."; + else + { + switch (charNum[0]) + { + case '+': + digitCount--; + charNum++; + positive = true; + break; + case '-': + digitCount--; + charNum++; + positive = false; + break; + default: + positive = true; + } + } + + //get rid of the leading zeroes + while (charNum[0] == '0') + { + charNum++; + digitCount --; + } + + //check if the string contains only decimal digits + if (! BigInt::allCharsAreDigits(charNum, digitCount)) + throw "Error BIGINT04: Input string contains characters" + " other than digits."; + + //the input string was like ('+' or '-')"00...00\0" + if (charNum[0] == '\0') + { + digitCount = 1; + charNum--; + positive = true; + } + + length = (unsigned long int)(digitCount * BigInt::FACTOR + 1); + + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT05: BigInt creation error (out of memory?)."; + } + + //copy the digits backwards to the new BigInt + std::reverse_copy(charNum, charNum + digitCount, digits); + //convert them to unsigned char + BigInt::char2uchar(digits, digitCount); +} + +BigInt::BigInt(unsigned long int intNum) : digits(0) +{ + positive = true; + + //we don't know how many digits there are in intNum since + //sizeof(long int) is platform dependent (2^128 ~ 39 digits), so we'll + //first save them in a temporary unsigned char[], and later copy them + unsigned char tempDigits[40] = {0}; + + digitCount = int2uchar(intNum, tempDigits); + length = (unsigned long int)(digitCount * BigInt::FACTOR + 1); + + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete [] digits; + throw "Error BIGINT06: BigInt creation error (out of memory?)."; + } + + std::copy(tempDigits, tempDigits + digitCount, digits); +} + +BigInt::BigInt(const std::string &str) : digits(0), length(10), + digitCount(1), positive(true) +{ + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT07: BigInt creation error (out of memory?)."; + } + + //initialize to 0 + digits[0] = 0; + BigInt a(str.c_str()); + *this = a; +} + +BigInt::BigInt(const BigInt &rightNumber) : length(rightNumber.length), +digitCount(rightNumber.digitCount), positive(rightNumber.positive) +{ + //make sure we have just enough space + if (length <= digitCount + 2 || length > (digitCount << 2)) + length = (unsigned long int) (digitCount * BigInt::FACTOR + 1); + try + { + digits = new unsigned char[length]; + } + catch (...) + { + delete[] digits; + throw "Error BIGINT08: BigInt creation error (out of memory?)."; + } + + std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits); +} + +BigInt::operator std::string() const +{ + return ToString(); +} + +BigInt &BigInt::operator =(const BigInt &rightNumber) +{ + //if the right-hand operand is longer than the left-hand one or + //twice as small + if (length < rightNumber.digitCount + 2 || + length > (rightNumber.digitCount << 2)) + { + length = (unsigned long int) + (rightNumber.digitCount * BigInt::FACTOR + 1); + //keep a pointer to the current digits, in case + //there is not enough memory to allocate for the new digits + unsigned char *tempDigits(digits); + + try + { + digits = new unsigned char[length]; + } + catch (...) + { + //clean up the mess + delete[] digits; + //restore the digits + digits = tempDigits; + throw "Error BIGINT09: BigInt assignment error (out of memory?)."; + } + //it turns out we don't need this any more + delete[] tempDigits; + } + //destructive self-assignment protection + else if (this == &rightNumber) + return *this; + + //copy the values + digitCount = rightNumber.digitCount; + positive = rightNumber.positive; + std::copy(rightNumber.digits, rightNumber.digits + digitCount, digits); + return *this; +} + +std::ostream &operator <<(std::ostream &cout, const BigInt &number) +{ + if (!number.positive) + cout << '-'; + for (int i = number.digitCount - 1; i >= 0; i--) + cout << (int(number.digits[i])); + + return cout; +} + +std::istream &operator >>(std::istream &cin, BigInt &number) +{ + std::string newNumber; + std::cin >> std::ws >> newNumber; + if (!cin) + { + cin.clear(); + throw "Error BIGINT16: Input stream error."; + } + + number = newNumber; + return cin; +} + +bool operator <(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 2) + return true; + return false; +} + +bool operator <=(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 1) + return false; + return true; +} + +bool operator >(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 1) + return true; + return false; +} + +bool operator >=(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive) == 2) + return false; + return true; +} + +bool operator ==(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive)) + return false; + return true; +} + +bool operator !=(const BigInt &a, const BigInt &b) +{ + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount, + a.positive, b.positive)) + return true; + return false; +} + +BigInt operator +(const BigInt &a, const BigInt &b) +{ + if (a.positive && !b.positive) + return a - (-b); + else if (!a.positive && b.positive) + return b - (-a); + + //find the longer of the operands + const BigInt *shorter, *longer; + if (BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount) == 1) + { + shorter = &b; + longer = &a; + } + else + { + shorter = &a; + longer = &b; + } + + //Copies the "positive" field too. That is good because now either a and b + //are both positive or both negative, so the result has the same sign. + BigInt sum(*longer); + + bool overflow = BigInt::add(shorter->digits, shorter->digitCount, + longer->digits, longer->digitCount, + sum.digits, 0, false); + if (overflow) + sum.digitCount++; + + return sum; +} + +/*overloaded ++ operator, prefix version*/ +BigInt &BigInt::operator++() +{ + return *this += BigIntOne; +} + +/*overloaded ++ operator, postfix version*/ +BigInt BigInt::operator++(int) +{ + BigInt temp(*this); + *this += BigIntOne; + return temp; +} + +BigInt &BigInt::operator+=(const BigInt &number) +{ + *this = *this + number; + return *this; +} + +BigInt BigInt::operator-() const +{ + if (!this->EqualsZero()) + { + BigInt temp(*this); + temp.positive = !temp.positive; + return temp; + } + return *this; +} + +BigInt operator-(const BigInt &a, const BigInt &b) +{ + if (!a.positive && b.positive) + { + return -((-a) + b); + } + if (a.positive && !b.positive) + { + return a + (-b); + } + + const int cmpAbs = BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount); + //if a == b + if ((cmpAbs == 0) && (a.positive == b.positive)) + { + return BigIntZero; + } + + //find the longer of the operands (bigger by absolute value) + const BigInt *shorter, *longer; + bool sign(a.positive); //the sign of the result + if (cmpAbs != 2) // a >= b + { + shorter = &b; + longer = &a; + } + else + { + shorter = &a; + longer = &b; + sign = !sign; + } + + BigInt result(*longer); + result.positive = sign; + //temporary variable + const BigInt shorterCopy(*shorter); + //often used temporary variable + const int rDigits(shorterCopy.digitCount); + //in case of longer digitwise carry, overflow = true + bool overflow(false); + + for (int i(0); i < rDigits; i++) + { + overflow = (longer->digits[i] - shorterCopy.digits[i]) < 0; + if (overflow) + { + result.digits[i] = longer->digits[i] + 10 - shorterCopy.digits[i]; + //transfer carry + shorterCopy.digits[i+1]++; + } + else + //make the digitwise subtraction + result.digits[i] = longer->digits[i] - shorterCopy.digits[i]; + } + + //if there is a carry and the following digit is 0 => there will + //be a carry again... + if (overflow && result.digits[rDigits] == 0) + { + result.digits[rDigits] = 9; + + int i(rDigits + 1); + for (; result.digits[i] == 0; i++) + result.digits[i] = 9; + + result.digits[i] -= 1; + } //there is a carry but there will be no more carries + else if (overflow) + result.digits[rDigits]--; + + //get rid of the leading zeroes + for (int i(result.digitCount - 1); i > 0; i--) + if (result.digits[i] == 0) + result.digitCount--; + else + break; + + return result; +} + +/*overloaded -- operator, prefix version*/ +BigInt &BigInt::operator--() +{ + *this = *this - BigIntOne; + return *this; +} + +/*overloaded -- operator, postfix version*/ +BigInt BigInt::operator--(int) +{ + BigInt temp(*this); + *this = *this - BigIntOne; + return temp; +} + +BigInt &BigInt::operator-=(const BigInt &number) +{ + *this = *this - number; + return *this; +} + +BigInt operator*(const BigInt &a, const BigInt &b) +{ + if (a.EqualsZero() || b.EqualsZero()) + return BigIntZero; + + //this controls wether Karatsuba algorithm will be used for multiplication +#ifdef KARATSUBA + int n((a.digitCount < b.digitCount ? b.digitCount : a.digitCount)); + + //we will use a temporary buffer for multiplication + unsigned char *buffer(0); + + try + { + buffer = new unsigned char[11 * n]; + } + catch (...) + { + delete[] buffer; + throw "Error BIGINT10: Not enough memory?"; + } + + unsigned char *bb(buffer + n), *bc(bb + n); + + std::copy(a.digits, a.digits + a.digitCount, buffer); + std::fill(buffer + a.digitCount, buffer + n, 0); + std::copy(b.digits, b.digits + b.digitCount, bb); + std::fill(bb + b.digitCount, bb + n, 0); + + BigInt::karatsubaMultiply(buffer, bb, n, bc); + + n <<= 1; +#else + int n = a.digitCount + b.digitCount; + + unsigned char *buffer = new unsigned char[n]; + + BigInt::longMultiply( a.digits, a.digitCount, + b.digits, b.digitCount, buffer); + + unsigned char *bc(buffer); +#endif /*KARATSUBA*/ + + BigInt bigIntResult; //we assume it's a positive number + if (a.positive != b.positive) + bigIntResult.positive = false; + bigIntResult.expandTo(n + 10); + std::copy(bc, bc + n, bigIntResult.digits); + for (unsigned long int i = n - 1; i > 0L; i--) + { + if (bigIntResult.digits[i]) + { + bigIntResult.digitCount = i + 1; + break; + } + } + delete[] buffer; + + return bigIntResult; +} + +BigInt &BigInt::operator*=(const BigInt &number) +{ + *this = *this * number; + return *this; +} + +BigInt operator /(const BigInt &a, const BigInt &b) +{ + if (b.EqualsZero()) + throw "Error BIGINT11: Attempt to divide by zero."; + + //we don't want to call this function twice + int comparison(BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount)); + + //if a == 0 or |a| < |b| + if (a.EqualsZero() || comparison == 2) + return BigIntZero; + + //if a == b + if (comparison == 0) + { + if (a.positive == b.positive) + return BigIntOne; + else + return -BigIntOne; + } + + BigInt quotient, remainder; + BigInt::divide(a, b, quotient, remainder); + //adjust the sign (positive by default) + if (a.positive != b.positive) + quotient.positive = false; + return quotient; +} + +BigInt &BigInt::operator /=(const BigInt &number) +{ + *this = *this / number; + return *this; +} + +BigInt operator%(const BigInt &a, const BigInt &b) +{ + if (b.EqualsZero()) + throw "Error BIGINT12: Attempt to divide by zero."; + + //we don't want to call this function twice + int comparison(BigInt::compareNumbers( a.digits, a.digitCount, + b.digits, b.digitCount)); + + //a == b + if (comparison == 0) + return BigIntZero; + + //if a < b + if (comparison == 2 && a.positive) + return a; + + BigInt quotient, remainder; + BigInt::divide(a, b, quotient, remainder); + if (!a.positive && !remainder.EqualsZero()) + remainder.positive = false; + return remainder; +} + +BigInt &BigInt::operator%=(const BigInt &number) +{ + *this = *this % number; + return *this; +} + +/* Returns *this to the power of n + * using the fast Square and Multiply algorithm. */ +BigInt BigInt::GetPower(unsigned long int n) const +{ + BigInt result(BigIntOne); + BigInt base(*this); + + while (n) + { + //if n is odd + if (n & 1) + { + result = result * base; + n--; + } + n /= 2; + base = base * base; + } + + //number was negative and the exponent is odd, the result is negative + if (!positive && (n & 1)) + result.positive = false; + return result; +} + +/* *this = *this to the power of n. */ +void BigInt::SetPower(unsigned long int n) +{ + *this = (*this).GetPower(n); +} + +/* Returns *this to the power of n + * using the fast Square and Multiply algorithm. */ +BigInt BigInt::GetPower(BigInt n) const +{ + if (!n.positive) + throw "Error BIGINT13: Negative exponents not supported!"; + + BigInt result(BigIntOne); + BigInt base(*this); + BigInt bigIntTwo(BigIntOne + BigIntOne); + + while (!n.EqualsZero()) + { + //if n is odd + if (n.digits[0] & 1) + { + result = result * base; + n--; + } + n = n / bigIntTwo; + base = base * base; + } + + //number was negative and the exponent is odd, the result is negative + if (!positive && (n.digits[0] & 1)) + result.positive = false; + return result; +} + +/* *this = *this to the power of n. */ +void BigInt::SetPower(BigInt n) +{ + *this = (*this).GetPower(n); +} + +/* Returns (*this to the power of b) mod n. */ +BigInt BigInt::GetPowerMod(const BigInt &b, const BigInt &n) const +{ + BigInt a(*this); + a.SetPowerMod(b, n); + return a; +} + +/* *this = (*this to the power of b) mod n. */ +void BigInt::SetPowerMod(const BigInt &b, const BigInt &n) +{ + if (!b.positive) + throw "Error BIGINT14: Negative exponent not supported."; + //we will need this value later, since *this is going to change + const BigInt a(*this); + //temporary variables + BigInt bCopy(b), q, r; + const BigInt two(BigIntOne + BigIntOne); + + //first we will find the binary representation of b + std::vector bits; + while (!bCopy.EqualsZero()) + { + BigInt::divide(bCopy, two, q, r); + bCopy = q; + if (r.EqualsZero()) + bits.push_back(false); + else + bits.push_back(true); + } + + //do the exponentiating + *this = BigIntOne; + for (int i = (int) bits.size() - 1; i >= 0; i--) + { + BigInt::divide(*this * *this, n, q, *this); + if (bits[i]) + BigInt::divide(*this * a, n, q, *this); + } +} + +/* Returns the nth digit read-only, zero-based, right-to-left. */ +unsigned char BigInt::GetDigit(unsigned long int index) const +{ + if (index >= digitCount) + throw "Error BIGINT15: Index out of range."; + + return digits[index]; +} + +/* Returns the nth digit, zero-based, right-to-left. */ +void BigInt::SetDigit(unsigned long int index, unsigned char value) +{ + if (index >= digitCount) + throw "Error BIGINT15: Index out of range."; + if (value > 9) + throw "Error BIGINT16: Digit value out of range."; + + digits[index] = value; +} + +/* Returns the value of BigInt as std::string. */ +std::string BigInt::ToString(bool forceSign) const +{ + (void)forceSign; // avoid unused warning + std::string number; + if (!positive) + number.push_back('-'); + for (int i = digitCount - 1; i >= 0; i--) + number.push_back(char(digits[i]) + '0'); + + return number; +} + +/* Returns the absolute value. */ +BigInt BigInt::Abs() const +{ + return ((positive) ? *this : -(*this)); +} diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.h b/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.h new file mode 100644 index 0000000..c78dc11 --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/BigInt.h @@ -0,0 +1,294 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * BigInt.h + * + * Author: Nedim Srndic + * Release date: 14th of March 2008 + * + * A class representing a positive or negative integer that may + * be too large to fit in any of the standard C++ integer types + * (i. e. 2^128 is "just" 39 digits long). + * The digits are stored in a dinamic array of tipe unsigned char*, + * with values from 0 to 9 (not '0' to '9'), so that the CPU can + * add/subtract individual digits. + * + * The array has "length" memory locations, one byte each (the size of + * unsigned char is probably one byte). There are "digitCount" digits actually + * in use, the rest is spare space. + * The number of digits is constrained by available memory and the limit of the + * unsigned long int type used for indexing (the "length" property). + * The individual digits are stored right-to-left, to speed up computing and + * allow for faster growth of numbers (no need to reallocate memory when + * the digitCount grows). + * + * The class handles its own memory management. There are no memory leaks + * reported until this date. + * When creating a BigInt from const char* or unsigned long int, + * copying from an other BigInt with (digitCount + 2 <= length) + * (soon to be full), new memory is allocated and + * length is adjusted to (length * FACTOR + 1). This is done to expand the + * capacity of the digits array to accomodate potential new digits. + * When assigning a BigInt "bInt" that is twice as small or bigger than *this, + * the length is set to (bInt.length + 2). + * + * BigInt supports: + * + * - addition (unary +, binary +, +=, prefix ++, postfix ++) + * + * - subtraction (unary -, binary -, -=, prefix --, postfix --) + * + * - multiplication (*, *=) + * For multiplication, one can choose between the Square and multiply + * or Karatsuba algorithm, or long multiplication at compile time + * (this can be done by defining or undefining the macro "KARATSUBA" + * in BigInt.cpp). + * The Karatsuba algorithm multiplies integers in O(n^log2(3)) + * complexity. log2(3) is approximately 1.585, so this should be + * significantly faster than long multiplication, if the numbers are + * big enough. Currently, the long multiplication is better implemented, + * and runs faster than the Karatsuba multiplication for numbers shorter + * than about 100 digits. + * + * - C-style integer division (/, /=) + * + * - C-style integer division remainder (%, %=) + * When calculating the remainder, the number is first divided. + * + * - comparison (==, !=, <, <=, >, >=) + * All of the <, <=, >, >= operators are equally fast. + * + * - exponentiation (GetPower(), SetPower(), GetPowerMod(), SetPowerMod()) + * For exponentiation, the Exponantiation by squaring + * (or Square and multiply or Binary exponentiation) algorithm is used. + * It uses O(log(n)) multiplications and therefore is significantly faster + * than multiplying x with itself n-1 times. + * + * In addition to mathematical operations, BigInt supports: + * + * - automatic conversion from const char *, std::string and unsigned long int + * - safe construction, copying, assignment and destruction + * - automatic conversion to std::string + * - writing to the standard output (operator <<(std::ostream, BigInt)) + * - reading from the standard input (operator >>(std::istream, BigInt)) + * - getting and setting individual digits (GetDigit(), SetDigit()) + * - returning the number of digits (Length()) + * - returning a string of digits (ToString()) + * This can be useful for human-readable output. + * - returning a value indicating wether the number is odd (IsOdd()) + * - returning a value indicating wether the number is positive (IsPositive()) + * - returning a value indicating wether the BigInt equals zero (EqualsZero()) + * The fastest way to determine this. + * - returning absolute value (Abs()) + * + * There are a few static constants defined in this file: + * + * - BigIntZero : a zero of type BigInt + * If you need a zero fast, use this. + * - BigIntOne : a one of type BigInt + * If you need a one fast, use this. + * + * **************************************************************************** +*/ + +#ifndef BIGINT_H_ +#define BIGINT_H_ + +#include //ostream, istream +#include //sqrt() +#include //ToString(), BigInt(std::string) + +class BigInt +{ + private: + /* An array of digits stored right to left, + * i.e. int 345 = unsigned char {[5], [4], [3]} */ + unsigned char *digits; + // The total length of the allocated memory + unsigned long int length; + // Number of digits + unsigned long int digitCount; + // Sign + bool positive; + /* Multiplication factor for the length property + * when creating or copying objects. */ + static const double FACTOR; + /* Transforms the number from unsigned long int to unsigned char[] + * and pads the result with zeroes. Returns the number of digits. */ + static unsigned long int int2uchar( unsigned long int number, + unsigned char *digits, + unsigned long int padding); + /* Converts ASCII digits to equivalent unsigned char numeric values. */ + static void char2uchar( unsigned char *array, + unsigned long int length); + /* Check if all ASCII values are digits '0' to '9'. */ + static bool allCharsAreDigits( const char *array, + unsigned long int length); + /* Compares two BigInt. If the last two arguments are + * omitted, the comparison is sign-insensitive (comparison by + * absolute value). Returns 0 if a == b, 1 if a > b, 2 if a < b. */ + static int compareNumbers( unsigned char *a, unsigned long int na, + unsigned char *b, unsigned long int nb, + bool aPositive = true, + bool bPositive = true); + /* Multiplies two unsigned char[] using the Divide and Conquer + * a.k.a. Karatsuba algorithm .*/ + static void karatsubaMultiply( unsigned char *a, unsigned char *b, + unsigned long int n, + unsigned char *buffer); + /* Multiplies two unsigned char[] the long way. */ + static void longMultiply( unsigned char *a, unsigned long int na, + unsigned char *b, unsigned long int nb, + unsigned char *result); + /* Simple addition, used by the multiply function. + * Returns the remaining carry. */ + static unsigned char quickAdd( unsigned char *a, unsigned char *b, + unsigned long int n); + /* Simple subtraction, used by the multiply function. */ + static void quickSub( unsigned char *a, unsigned char *b, + unsigned char *end, unsigned long int n); + /* Divides two BigInt numbers. */ + static void divide( const BigInt ÷nd, const BigInt &divisor, + BigInt "ient, BigInt &remainder); + /* Returns the value of the specified unsigned char[] as long int. */ + static unsigned long int toInt(unsigned char *digits, int n); + /* Saves the sum of two unsigned char* shorter and longer into result. + * It must be nShorter <= nLonger. If doFill == true, it fills the + * remaining free places with zeroes (used in KaratsubaMultiply()). + * Returns true if there was an overflow at the end (meaning that + * the result.digitCount was longer.digitCount + 1. */ + static bool add(unsigned char *shorter, unsigned long int nShorter, + unsigned char *longer, unsigned long int nLonger, + unsigned char *result, int nResult, + bool doFill = true); + /* Shifts the digits n places left. */ + BigInt &shiftLeft(unsigned long int n); + /* Shifts the digits n places right. */ + BigInt &shiftRight(unsigned long int n); + /* Expands the digits* to n. */ + void expandTo(unsigned long int n); + public: + BigInt(); + BigInt(const char *charNum); + BigInt(unsigned long int intNum); + BigInt(const std::string &str); + BigInt(const BigInt &number); + BigInt &operator =(const BigInt &rightNumber); + ~BigInt(); + operator std::string() const; + friend std::ostream &operator <<( std::ostream &cout, + const BigInt &number); + friend std::istream &operator >>( std::istream &cin, + BigInt &number); + friend bool operator <(const BigInt &a, const BigInt &b); + friend bool operator <=(const BigInt &a, const BigInt &b); + friend bool operator >(const BigInt &a, const BigInt &b); + friend bool operator >=(const BigInt &a, const BigInt &b); + friend bool operator ==(const BigInt &a, const BigInt &b); + friend bool operator !=(const BigInt &a, const BigInt &b); + friend BigInt operator + (const BigInt &a, const BigInt &b); + BigInt &operator+(); + BigInt &operator++(); + BigInt operator++(int); + BigInt &operator+=(const BigInt &number); + BigInt operator-() const; + friend BigInt operator-(const BigInt &a, const BigInt &b); + BigInt &operator--(); + BigInt operator--(int); + BigInt &operator-=(const BigInt &number); + friend BigInt operator*(const BigInt &a, const BigInt &b); + BigInt &operator*=(const BigInt &number); + friend BigInt operator/(const BigInt &a, const BigInt &b); + BigInt &operator/=(const BigInt &number); + friend BigInt operator%(const BigInt &a, const BigInt &b); + BigInt &operator%=(const BigInt &number); + /* Returns *this to the power of n + * using the fast Square and Multiply algorithm. */ + BigInt GetPower(unsigned long int n) const; + /* *this = *this to the power of n. */ + void SetPower(unsigned long int n); + /* Returns *this to the power of n + * using the fast Square and Multiply algorithm. */ + BigInt GetPower(BigInt n) const; + /* *this = *this to the power of n. */ + void SetPower(BigInt n); + /* Returns (*this to the power of b) mod n. */ + BigInt GetPowerMod(const BigInt &b, const BigInt &n) const; + /* *this = (*this to the power of b) mod n. */ + void SetPowerMod(const BigInt &b, const BigInt &n); + /* Returns the 'index'th digit (zero-based, right-to-left). */ + unsigned char GetDigit(unsigned long int index) const; + /* Sets the value of 'index'th digit + * (zero-based, right-to-left) to 'value'. */ + void SetDigit(unsigned long int index, unsigned char value); + /* Returns the number of digits. */ + unsigned long int Length() const; + /* Returns true if *this is positive, otherwise false. */ + bool IsPositive() const; + /* Returns true if *this is odd, otherwise false. */ + bool IsOdd() const; + /* Returns the value of BigInt as std::string. */ + std::string ToString(bool forceSign = false) const; + /* Returns a value indicating whether *this equals 0. */ + bool EqualsZero() const; + /* Returns the absolute value. */ + BigInt Abs() const; +}; + +inline BigInt::~BigInt() +{ + delete[] digits; +} + +inline BigInt &BigInt::operator+() +{ + return *this; +} + +/* Returns the number of digits. */ +inline unsigned long int BigInt::Length() const +{ + return digitCount; +} + +/* Returns true if *this is positive, otherwise false. */ +inline bool BigInt::IsPositive() const +{ + return positive; +} + +/* Returns true if *this is odd, otherwise false. */ +inline bool BigInt::IsOdd() const +{ + return digits[0] & 1; +} + +/* Returns a value indicating whether *this equals 0. */ +inline bool BigInt::EqualsZero() const +{ + return digitCount == 1 && digits[0] == 0; +} + +// A BigInt number with the value of 0. +static const BigInt BigIntZero; +// A BigInt number with the value of 1. +static const BigInt BigIntOne(1L); + + +#endif /*BIGINT_H_*/ diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/Key.cpp b/SQLiteStudio3/coreSQLiteStudio/rsa/Key.cpp new file mode 100644 index 0000000..adc4a1f --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/Key.cpp @@ -0,0 +1,37 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * Key.cpp + * + * Author: Nedim Srndic + * Release date: 5th of September 2008 + * + * This file contains the implementation for the Key class. + * + * **************************************************************************** + */ + +#include "Key.h" + +std::ostream &operator<<(std::ostream &, const Key &key) +{ + return std::cout + << "Modulus: " << key.GetModulus() << std::endl + << "Exponent: " << key.GetExponent(); +} diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/Key.h b/SQLiteStudio3/coreSQLiteStudio/rsa/Key.h new file mode 100644 index 0000000..b193e2c --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/Key.h @@ -0,0 +1,59 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * Key.h + * + * Author: Nedim Srndic + * Release date: 16th of June 2008 + * + * A class representing a public or private RSA key. + * + * A public or private RSA key consists of a modulus and an exponent. In this + * implementation an object of type BigInt is used to store those values. + * + * **************************************************************************** + */ + +#ifndef KEY_H_ +#define KEY_H_ + +#include "BigInt.h" +#include + +class Key +{ + private: + BigInt modulus; + BigInt exponent; + public: + Key(const BigInt &modulus, const BigInt &exponent) : + modulus(modulus), exponent(exponent) + {} + const BigInt &GetModulus() const + { + return modulus; + } + const BigInt &GetExponent() const + { + return exponent; + } + friend std::ostream &operator<<(std::ostream &, const Key &key); +}; + +#endif /*KEY_H_*/ diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.cpp b/SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.cpp new file mode 100644 index 0000000..7780288 --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.cpp @@ -0,0 +1,37 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * KeyPair.cpp + * + * Author: Nedim Srndic + * Release date: 22th of July 2008 + * + * This file contains the implementation for the KeyPair class. + * + * **************************************************************************** + */ + +#include "KeyPair.h" + +std::ostream &operator <<(std::ostream &, const KeyPair &k) +{ + return std::cout + << "Private key:" << std::endl << k.GetPrivateKey() << std::endl + << "Public key:" << std::endl << k.GetPublicKey(); +} diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.h b/SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.h new file mode 100644 index 0000000..929ffe9 --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/KeyPair.h @@ -0,0 +1,58 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * KeyPair.h + * + * Author: Nedim Srndic + * Release date: 17th of June 2008 + * + * A class representing a public/private RSA keypair. + * + * A keypair consists of a public key and a matching private key. + * + * **************************************************************************** + */ + +#ifndef KEYPAIR_H_ +#define KEYPAIR_H_ + +#include "Key.h" +#include + +class KeyPair +{ + private: + const Key privateKey; + const Key publicKey; + public: + KeyPair(Key privateKey, Key publicKey): + privateKey(privateKey), publicKey(publicKey) + {} + const Key &GetPrivateKey() const + { + return privateKey; + } + const Key &GetPublicKey() const + { + return publicKey; + } + friend std::ostream &operator <<(std::ostream &, const KeyPair &k); +}; + +#endif /*KEYPAIR_H_*/ diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.cpp b/SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.cpp new file mode 100644 index 0000000..7f38f55 --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.cpp @@ -0,0 +1,198 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * PrimeGenerator.cpp + * + * Author: Nedim Srndic + * Release date: 14th of March 2008 + * + * This file contains the implementation for the PrimeGenerator class. + * + * There is a static constant defined in this file: + * + * - RandMax : RAND_MAX (defined in cstdlib) of type BigInt + * Mainly used for speedup in the Generate member function. + * Represents the largest random unsigned long integer that a particular + * platform can generate. This is platform-specific. + * + * **************************************************************************** + */ + +#include "PrimeGenerator.h" +#include +#include // rand() + +/* Generates a random number with digitCount digits. + * Returns it by reference in the "number" parameter. */ +void PrimeGenerator::MakeRandom(BigInt &number, unsigned long int digitCount) +{ + //the new number will be created using a string object (newNum), + //and later converted into a BigInt + std::string newNum; + newNum.resize(digitCount); + unsigned long int tempDigitCount(0); + + //generate random digits + while (tempDigitCount < digitCount) + { + unsigned long int newRand(std::rand()); + + //10 is chosen to skip the first digit, because it might be + //statistically <= n, where n is the first digit of RAND_MAX + while (newRand >= 10) + { + newNum[tempDigitCount++] = (newRand % 10) + '0'; + newRand /= 10; + if (tempDigitCount == digitCount) + break; + } + } + + //make sure the leading digit is not zero + if (newNum[0] == '0') + newNum[0] = (std::rand() % 9) + 1 + '0'; + number = newNum; +} + +/* Generates a random number such as 1 <= number < 'top'. + * Returns it by reference in the 'number' parameter. */ +void PrimeGenerator::makeRandom(BigInt &number, const BigInt &top) +{ + //randomly select the number of digits for the random number + unsigned long int newDigitCount = (rand() % top.Length()) + 1; + MakeRandom(number, newDigitCount); + //make sure number < top + while (number >= top) + MakeRandom(number, newDigitCount); +} + +/* Creates an odd BigInt with the specified number of digits. + * Returns it by reference in the "number" parameter. */ +void PrimeGenerator::makePrimeCandidate(BigInt &number, + unsigned long int digitCount) +{ + PrimeGenerator::MakeRandom(number, digitCount); + //make the number odd + if (!number.IsOdd()) + number.SetDigit(0, number.GetDigit(0) + 1); + //make sure the leading digit is not a zero + if (number.GetDigit(number.Length() - 1) == 0) + number.SetDigit(number.Length() - 1, (std::rand() % 9) + 1); +} + +/* Tests the primality of the given _odd_ number using the + * Miller-Rabin probabilistic primality test. Returns true if + * the tested argument "number" is a probable prime with a + * probability of at least 1 - 4^(-k), otherwise false. */ +bool PrimeGenerator::isProbablePrime( const BigInt &number, + unsigned long int k) +{ + //first we need to calculate such a and b, that + //number - 1 = 2^a * b, a and b are integers, b is odd + BigInt numberMinusOne(number - BigIntOne); + unsigned long int a(0); + BigInt temp(numberMinusOne); + BigInt b, quotient; + static const BigInt two(BigIntOne + BigIntOne); + + while (b.EqualsZero()) + { + //temp = quotient * 2 + remainder + + //PrimeGenerator used to be a friend of BigInt, so the following + //statement produced the result in one call to BigInt::divide() +// BigInt::divide(temp, two, quotient, b); + //That doesn't work any more, so we have to use two calls + quotient = temp / two; + b = temp % two; + temp = quotient; + a++; + } + b = temp * two + b; + a--; + + //test with k different possible witnesses to ensure that the probability + //that "number" is prime is at least 1 - 4^(-k) + for (unsigned long int i = 0; i < k; i++) + { + PrimeGenerator::makeRandom(temp, number); + + if (isWitness(temp, number, b, a, numberMinusOne)) + return false; //definitely a composite number + } + return true; //a probable prime +} + +/* Returns true if "candidate" is a witness for the compositeness + * of "number", false if "candidate" is a strong liar. "exponent" + * and "squareCount" are used for computation */ +bool PrimeGenerator::isWitness( BigInt candidate, + const BigInt &number, + const BigInt &exponent, + unsigned long int squareCount, + const BigInt &numberMinusOne) +{ + //calculate candidate = (candidate to the power of exponent) mod number + candidate.SetPowerMod(exponent, number); + //temporary variable, used to call the divide function + BigInt quotient; + + for (unsigned long int i = 0; i < squareCount; i++) + { + bool maybeWitness(false); + if (candidate != BigIntOne && candidate != numberMinusOne) + maybeWitness = true; + + //PrimeGenerator used to be a friend of BigInt, so the following + //statement produced the result in one call to BigInt::divide() +// BigInt::divide(candidate * candidate, number, quotient, candidate); + //That doesn't work any more, so we have to use two calls + candidate = candidate * candidate; + quotient = (candidate) / number; + candidate = (candidate) % number; + if (maybeWitness && candidate == BigIntOne) + return true; //definitely a composite number + } + + if (candidate != BigIntOne) + return true; //definitely a composite number + + return false; //probable prime +} + +/* Returns a probable prime number "digitCount" digits long, + * with a probability of at least 1 - 4^(-k) that it is prime. */ +BigInt PrimeGenerator::Generate(unsigned long int digitCount, + unsigned long int k) +{ + if (digitCount < 3) + throw "Error PRIMEGENERATOR00: Primes less than 3 digits long " + "not supported."; + + BigInt primeCandidate; + PrimeGenerator::makePrimeCandidate(primeCandidate, digitCount); + while (!isProbablePrime(primeCandidate, k)) + { + //select the next odd number and try again + primeCandidate = primeCandidate + 2; + if (primeCandidate.Length() != digitCount) + PrimeGenerator::makePrimeCandidate(primeCandidate, digitCount); + } + return primeCandidate; +} diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.h b/SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.h new file mode 100644 index 0000000..8a9dfac --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/PrimeGenerator.h @@ -0,0 +1,71 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * PrimeGenerator.h + * + * A class used to generate large prime or random numbers. + * + * Author: Nedim Srndic + * Release date: 14th of March 2008 + * + * **************************************************************************** + */ + +#ifndef PRIMEGENERATOR_H_ +#define PRIMEGENERATOR_H_ + +#include "BigInt.h" + +class PrimeGenerator +{ + private: + /* Generates a random "number" such as 1 <= "number" < "top". + * Returns it by reference in the "number" parameter. */ + static void makeRandom( BigInt &number, + const BigInt &top); + /* Creates an odd BigInt with the specified number of digits. + * Returns it by reference in the "number" parameter. */ + static void makePrimeCandidate( BigInt &number, + unsigned long int digitCount); + /* Tests the primality of the given _odd_ number using the + * Miller-Rabin probabilistic primality test. Returns true if + * the tested argument "number" is a probable prime with a + * probability of at least 1 - 4^(-k), otherwise false. */ + static bool isProbablePrime(const BigInt &number, + unsigned long int k); + /* Returns true if "candidate" is a witness for the compositeness + * of "number", false if "candidate" is a strong liar. "exponent" + * and "squareCount" are used for computation */ + static bool isWitness( BigInt candidate, + const BigInt &number, + const BigInt &exponent, + unsigned long int squareCount, + const BigInt &numberMinusOne); + public: + /* Generates a random number with digitCount digits. + * Returns it by reference in the "number" parameter. */ + static void MakeRandom( BigInt &number, + unsigned long int digitCount); + /* Returns a probable prime number "digitCount" digits long, + * with a probability of at least 1 - 4^(-k) that it is prime. */ + static BigInt Generate( unsigned long int digitCount, + unsigned long int k = 3); +}; + +#endif /*PRIMEGENERATOR_H_*/ diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/RSA.cpp b/SQLiteStudio3/coreSQLiteStudio/rsa/RSA.cpp new file mode 100644 index 0000000..0d8e921 --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/RSA.cpp @@ -0,0 +1,394 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * RSA.cpp + * + * Author: Nedim Srndic + * Release date: 16th of June 2008 + * + * This file contains the implementation for the RSA class. + * + * **************************************************************************** + */ + +#include "RSA.h" +#include "Key.h" //Key +#include "KeyPair.h" //KeyPair +#include "PrimeGenerator.h" //Generate() +#include //string +#include //ifstream, ofstream + +using std::string; + +/* Returns the greatest common divisor of the two arguments + * "a" and "b", using the Euclidean algorithm. */ +BigInt RSA::GCD(const BigInt &a, const BigInt &b) +{ + if (b.EqualsZero()) + return a; + else + return RSA::GCD(b, a % b); +} + +/* Solves the equation + * d = ax + by + * given a and b, and returns d, x and y by reference. + * It uses the Extended Euclidean Algorithm */ +void RSA::extendedEuclideanAlgorithm( const BigInt &a, const BigInt &b, + BigInt &d, BigInt &x, BigInt &y) +{ + if (b.EqualsZero()) + { + d = a; + x = BigIntOne; + y = BigIntZero; + return; + } + RSA::extendedEuclideanAlgorithm(b, a % b, d, x, y); + BigInt temp(x); + x = y; + y = temp - a / b * y; +} + +/* Solves the equation + * ax is congruent to b (mod n), + * given a, b and n finds x. */ +BigInt RSA::solveModularLinearEquation( const BigInt &a, + const BigInt &b, + const BigInt &n) +{ + BigInt p, q, r; + RSA::extendedEuclideanAlgorithm(a, n, p, q, r); + if ((b % p).EqualsZero()) // This has to evaluate to 'true'. + return (q * (b / p)) % n; + else + throw "Error RSA00: Error in key generation."; // Detect mistakes. +} + +/* Throws an exception if "key" is too short to be used. */ +void RSA::checkKeyLength(const Key &key) +{ + // Minimum required key length is around 24 bits. (In-house requirement) + if (key.GetModulus().Length() < 8) + throw "Error RSA01: Keys must be at least 8 digits long."; +} + +/* Transforms a std::string message into a BigInt message. + * Every ASCII character of the original message is replaced by it's + * ASCII value and appended to the end of the newly created BigInt object + * 'decoded' as a three-digit number, from left to right. */ +BigInt RSA::encode(const string &message) +{ + // The new number will be created using a string object (encoded), + // and converted into a BigInt on return. + string encoded; + encoded.resize(message.length() * 3 + 1); + unsigned long int index = message.length() * 3; + for (unsigned long int i(0); i < message.length(); i++) + { + // Encode the characters using their ASCII values' digits as + // BigInt digits. + unsigned char ASCII = message[i]; + encoded[index - 2] = (ASCII % 10) + '0'; + ASCII /= 10; + encoded[index - 1] = (ASCII % 10) + '0'; + encoded[index] = (ASCII / 10) + '0'; + index -= 3; + } + // We add an special symbol '1' to the beginning of the string 'encoded' + // to make sure that the returned BigInt doesn't begin with a zero. We also + // need to make sure we remove that '1' when decoding (see RSA::decode()). + encoded[0] = '1'; + return encoded; +} + +/* Transforms a BigInt cyphertext into a std::string cyphertext. */ +string RSA::decode(const BigInt &message) +{ + string decoded; + // The special symbol '1' we added to the beginning of the encoded message + // will now be positioned at message[message.Length() - 1], and + // message.Length() -1 must be divisible by 3 without remainder. Thus we + // can ignore the special symbol by only using digits in the range + // from message[0] to message[message.Length() - 2]. + for (unsigned long int i(0); i < message.Length() / 3; i++) + { + // Decode the characters using the ASCII values in the BigInt digits. + char ASCII = 100 * char(message.GetDigit(i * 3)); + ASCII += 10 * char(message.GetDigit(i * 3 + 1)); + decoded.push_back(ASCII + char(message.GetDigit(i * 3 + 2))); + } + return decoded; +} + +/* Encrypts a "chunk" (a small part of a message) using "key" */ +string RSA::encryptChunk(const string &chunk, const Key &key) +{ + // First encode the chunk, to make sure it is represented as an integer. + BigInt a = RSA::encode(chunk); + // The RSA encryption algorithm is a congruence equation. + a.SetPowerMod(key.GetExponent(), key.GetModulus()); + return a.ToString(); +} + +/* Decrypts a "chunk" (a small part of a message) using "key" */ +string RSA::decryptChunk(const BigInt &chunk, const Key &key) +{ + BigInt a = chunk; + // The RSA decryption algorithm is a congruence equation. + a.SetPowerMod(key.GetExponent(), key.GetModulus()); + // Decode the message to a readable form. + return RSA::decode(a); +} + +/* Encrypts a string "message" using "key". */ +std::string RSA::encryptString(const std::string &message, const Key &key) +{ + //partition the message into biggest possible encryptable chunks + const unsigned long int chunkSize(((key.GetModulus().Length() - 2) / 3)); + const unsigned long int chunkCount = message.length() / chunkSize; + + string cypherText; + for (unsigned long int i(0); i < chunkCount; i++) + { + // Get the next chunk. + string chunk(message.substr(i * chunkSize, chunkSize)); + chunk = RSA::encryptChunk(chunk, key); + // Put a ' ' between the chunks so that we can separate them later. + cypherText.append(chunk.append(" ")); + } + // If the last chunk has the same size as the others, we are finished. + if (chunkSize * chunkCount == message.length()) + return cypherText; + + // Handle the last chunk. It is smaller than the others. + const unsigned long int lastChunkSize = message.length() % chunkSize; + string lastChunk(message.substr(chunkCount * chunkSize, lastChunkSize)); + lastChunk = RSA::encryptChunk(lastChunk, key); + return cypherText.append(lastChunk.append(" ")); +} + +/* Decrypts a string "message" using "key". */ +std::string RSA::decryptString(const std::string &cypherText, const Key &key) +{ + // Partition the cypherText into chunks. They are seperated by ' '. + string message; + long int i(0), j(0); + while ((j = cypherText.find(' ', i)) != -1) + { + // Get the chunk. + BigInt chunk(cypherText.substr(i, j - i)); + if (chunk >= key.GetModulus()) + throw "Error RSA02: Chunk too large."; + + // Decrypt the chunk and store the message. + string text = RSA::decryptChunk(chunk, key); + message.append(text); + i = j + 1; + } + return message; +} + +/* Tests the file for 'eof', 'bad ' errors and throws an exception. */ +void RSA::fileError(bool eof, bool bad) +{ + if (eof) + throw "Error RSA03: Unexpected end of file."; + else if (bad) + throw "Error RSA04: Bad file?"; + else + throw "Error RSA05: File contains unexpected data."; +} + +/* Returns the string "message" RSA-encrypted using the key "key". */ +string RSA::Encrypt(const string &message, const Key &key) +{ + RSA::checkKeyLength(key); + + return RSA::encryptString(message, key); +} + +/* Encrypts the file "sourceFile" using the key "key" and saves + * the result into the file "destFile". */ +void RSA::Encrypt( const char *sourceFile, const char *destFile, + const Key &key) +{ + RSA::checkKeyLength(key); + + //open the input and output files + std::ifstream source(sourceFile, std::ios::in | std::ios::binary); + if (!source) + throw "Error RSA06: Opening file \"sourceFile\" failed."; + std::ofstream dest(destFile, std::ios::out | std::ios::binary); + if (!dest) + throw "Error RSA07: Creating file \"destFile\" failed."; + + //find the source file length + source.seekg(0, std::ios::end); + const unsigned long int fileSize = source.tellg(); + source.seekg(0, std::ios::beg); + + //create an input buffer + const unsigned long int bufferSize = 4096; + char buffer[bufferSize]; + + //encrypt file chunks + const unsigned long int chunkCount = fileSize / bufferSize; + for (unsigned long int i(0); i <= chunkCount; i++) + { + unsigned long int readLength; + //read the chunk + if (i == chunkCount) //if it's the last one + readLength = fileSize % bufferSize; + else + readLength = sizeof buffer; + source.read(buffer, readLength); + if (!source) + RSA::fileError(source.eof(), source.bad()); + + //encrypt the chunk + std::string chunk(buffer, readLength); + chunk = RSA::encryptString(chunk, key); + //write the chunk + dest.write(chunk.c_str(), chunk.length()); + if (!dest) + RSA::fileError(dest.eof(), dest.bad()); + } + + source.close(); + dest.close(); +} + +/* Returns the string "cypherText" RSA-decrypted using the key "key". */ +string RSA::Decrypt(const string &cypherText, const Key &key) +{ + RSA::checkKeyLength(key); + + return RSA::decryptString(cypherText, key); +} + +/* Decrypts the file "sourceFile" using the key "key" and saves + * the result into the file "destFile". */ +void RSA::Decrypt( const char *sourceFile, const char *destFile, + const Key &key) +{ + RSA::checkKeyLength(key); + + //open the input and output files + std::ifstream source(sourceFile, std::ios::in | std::ios::binary); + if (!source) + throw "Error RSA08: Opening file \"sourceFile\" failed."; + std::ofstream dest(destFile, std::ios::out | std::ios::binary); + if (!dest) + throw "Error RSA09: Creating file \"destFile\" failed."; + + //find the source file length + source.seekg(0, std::ios::end); + const unsigned long int fileSize = source.tellg(); + source.seekg(0, std::ios::beg); + + //create an input buffer + const unsigned long int bufferSize = 8192; + char buffer[bufferSize]; + unsigned long int readCount = 0; + + while (readCount < fileSize) + { + unsigned long int readLength; + //read new data + if (fileSize - readCount >= bufferSize) //if it's not the last one + readLength = sizeof buffer; + else + readLength = fileSize - readCount; + source.read(buffer, readLength); + if (!source) + RSA::fileError(source.eof(), source.bad()); + + //find the next chunk + std::string chunk(buffer, readLength); + chunk = chunk.substr(0, chunk.find_last_of(' ', chunk.length()) + 1); + readCount += chunk.length(); + source.seekg(readCount, std::ios::beg); + //decrypt the chunk + chunk = RSA::decryptString(chunk, key); + //write the chunk + dest.write(chunk.c_str(), chunk.length()); + if (!dest) + RSA::fileError(dest.eof(), dest.bad()); + } + + source.close(); + dest.close(); +} + +/* Generates a public/private keypair. The keys are retured in a + * KeyPair. The generated keys are 'digitCount' or + * 'digitCount' + 1 digits long. */ +KeyPair RSA::GenerateKeyPair( unsigned long int digitCount, + unsigned long int k) +{ + if (digitCount < 8) + throw "Error RSA10: Keys must be at least 8 digits long."; + + //generate two random numbers p and q + BigInt p(PrimeGenerator::Generate(digitCount / 2 + 2, k)); + BigInt q(PrimeGenerator::Generate(digitCount / 2 - 1, k)); + + //make sure they are different + while (p == q) + { + p = PrimeGenerator::Generate(digitCount / 2 + 1, k); + } + + //calculate the modulus of both the public and private keys, n + BigInt n(p * q); + + //calculate the totient phi + BigInt phi((p - BigIntOne) * (q - BigIntOne)); + + //select a small odd integer e that is coprime with phi and e < phi + //usually 65537 is used, and we will use it too if it fits + //it is recommended that this be the least possible value for e + BigInt e("65537"); + + //make sure the requirements are met + while (RSA::GCD(phi, e) != BigIntOne || e < "65537" || !e.IsOdd()) + { + PrimeGenerator::MakeRandom(e, 5); + } + + //now we have enough information to create the public key + //e is the public key exponent, n is the modulus + Key publicKey(n, e); + + //calculate d, d * e = 1 (mod phi) + BigInt d(RSA::solveModularLinearEquation(e, BigIntOne, phi)); + + //we need a positive private exponent + if (!d.IsPositive()) + return RSA::GenerateKeyPair(digitCount, k); + + //we can create the private key + //d is the private key exponent, n is the modulus + Key privateKey(n, d); + + //finally, the keypair is created and returned + KeyPair newKeyPair(privateKey, publicKey); + return newKeyPair; +} diff --git a/SQLiteStudio3/coreSQLiteStudio/rsa/RSA.h b/SQLiteStudio3/coreSQLiteStudio/rsa/RSA.h new file mode 100644 index 0000000..501261e --- /dev/null +++ b/SQLiteStudio3/coreSQLiteStudio/rsa/RSA.h @@ -0,0 +1,130 @@ +/* **************************************************************************** + * + * Copyright 2013 Nedim Srndic + * + * This file is part of rsa - the RSA implementation in C++. + * + * rsa is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * rsa is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with rsa. If not, see . + * + * RSA.h + * + * Author: Nedim Srndic + * Release date: 16th of June 2008 + * + * An implementation of the RSA public-key cryptography algorithm. + * + * RSA supports: + * + * - Message encryption (string and file) (Encrypt()) + * - Message decryption (string and file) (Decrypt()) + * - Public/private keypair generation (GenerateKeyPair()) + * + * NOTE: All methods are static. Instantiation, copying and assignment of + * objects of type RSA is forbidden. + * + * NOTE: it is highly recommended to call + * std::srand(time(NULL)); + * once when the program starts and before any use of methods provided by the + * RSA class. Calling the srand() function randomizes the standard C++ + * pseudorandom number generator, so that it provides different series of + * pseudorandom numbers every time the program is run. This greatly improves + * security. + * + * **************************************************************************** + */ + +#ifndef RSA_H_ +#define RSA_H_ + +#include +#include +#include "KeyPair.h" +#include "Key.h" +#include "BigInt.h" +#include "coreSQLiteStudio_global.h" + +class API_EXPORT RSA +{ + private: + /* Instantiation of objects of type RSA is forbidden. */ + RSA() + {} + /* Copying of objects of type RSA is forbidden. */ + RSA(const RSA &rsa); + /* Assignment of objects of type RSA is forbidden. */ + RSA &operator=(const RSA &rsa); + /* Returns the greatest common divisor of the two arguments + * "a" and "b", using the Euclidean algorithm. */ + static BigInt GCD(const BigInt &a, const BigInt &b); + /* Solves the equation + * d = ax + by + * given a and b, and returns d, x and y by reference. + * It uses the Extended Euclidean Algorithm */ + static void extendedEuclideanAlgorithm( const BigInt &a, + const BigInt &b, + BigInt &d, + BigInt &x, + BigInt &y); + /* Solves the equation + * ax is congruent to b (mod n), + * given a, b and n finds x. */ + static BigInt solveModularLinearEquation( const BigInt &a, + const BigInt &b, + const BigInt &n); + /* Throws an exception if "key" is too short to be used. */ + static void checkKeyLength(const Key &key); + /* Transforms a std::string message into a BigInt message. */ + static BigInt encode(const std::string &message); + /* Transforms a BigInt cyphertext into a std::string cyphertext. */ + static std::string decode(const BigInt &message); + /* Encrypts a "chunk" (a small part of a message) using "key" */ + static std::string encryptChunk(const std::string &chunk, + const Key &key); + /* Decrypts a "chunk" (a small part of a message) using "key" */ + static std::string decryptChunk(const BigInt &chunk, + const Key &key); + /* Encrypts a string "message" using "key". */ + static std::string encryptString( const std::string &message, + const Key &key); + /* Decrypts a string "message" using "key". */ + static std::string decryptString( const std::string &cypherText, + const Key &key); + /* Tests the file for 'eof', 'bad ' errors and throws an exception. */ + static void fileError(bool eof, bool bad); + public: + /* Returns the string "message" RSA-encrypted using the key "key". */ + static std::string Encrypt( const std::string &message, + const Key &key); + /* Encrypts the file "sourceFile" using the key "key" and saves + * the result into the file "destFile". */ + static void Encrypt(const char *sourceFile, + const char *destFile, + const Key &key); + /* Decrypts the file "sourceFile" using the key "key" and saves + * the result into the file "destFile". */ + static void Decrypt(const char *sourceFile, + const char *destFile, + const Key &key); + /* Returns the string "cypherText" RSA-decrypted + * using the key "key". */ + static std::string Decrypt( const std::string &cypherText, + const Key &key); + /* Generates a public/private keypair. The keys are retured in a + * KeyPair. The generated keys are 'digitCount' or + * 'digitCount' + 1 digits long. */ + static KeyPair GenerateKeyPair( unsigned long int digitCount, + unsigned long int k = 3); +}; + +#endif /*RSA_H_*/ -- cgit v1.2.3