diff options
| -rw-r--r-- | Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp | 89 | ||||
| -rw-r--r-- | Libraries/LibCrypto/BigInt/UnsignedBigInteger.h | 61 | ||||
| -rw-r--r-- | Libraries/LibCrypto/Makefile | 3 | ||||
| -rw-r--r-- | Userland/test-crypto.cpp | 57 |
4 files changed, 209 insertions, 1 deletions
diff --git a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp new file mode 100644 index 0000000000..d22ce57a19 --- /dev/null +++ b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.cpp @@ -0,0 +1,89 @@ +/* + * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include "UnsignedBigInteger.h" + +namespace Crypto { + +UnsignedBigInteger UnsignedBigInteger::add(const UnsignedBigInteger& other) +{ + const UnsignedBigInteger* const longer = (length() > other.length()) ? this : &other; + const UnsignedBigInteger* const shorter = (longer == &other) ? this : &other; + UnsignedBigInteger result; + + u8 carry = 0; + for (size_t i = 0; i < shorter->length(); ++i) { + u32 word_addition_result = shorter->m_words[i] + longer->m_words[i]; + u8 carry_out = 0; + // if there was a carry, the result will be smaller than any of the operands + if (word_addition_result < shorter->m_words[i]) { + carry_out = 1; + } + if (carry) { + word_addition_result++; + } + carry = carry_out; + result.m_words.append(word_addition_result); + } + + for (size_t i = shorter->length(); i < longer->length(); ++i) { + u32 word_addition_result = longer->m_words[i] + carry; + + carry = 0; + if (word_addition_result < longer->m_words[i]) { + carry = 1; + } + result.m_words.append(word_addition_result); + } + if (carry) { + result.m_words.append(carry); + } + return result; +} + +bool UnsignedBigInteger::operator==(const UnsignedBigInteger& other) const +{ + if (trimmed_length() != other.trimmed_length()) { + return false; + } + for (size_t i = 0; i < trimmed_length(); ++i) { + if (m_words[i] != other.words()[i]) + return false; + } + return true; +} + +size_t UnsignedBigInteger::trimmed_length() const +{ + size_t num_leading_zeroes = 0; + for (int i = length() - 1; i >= 0; --i, ++num_leading_zeroes) { + if (m_words[i] != 0) + break; + } + return length() - num_leading_zeroes; +} + +} diff --git a/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h new file mode 100644 index 0000000000..cf3b280c8c --- /dev/null +++ b/Libraries/LibCrypto/BigInt/UnsignedBigInteger.h @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#pragma once +#include <AK/LogStream.h> +#include <AK/Types.h> +#include <AK/Vector.h> + +namespace Crypto { +class UnsignedBigInteger { +public: + UnsignedBigInteger(u32 x) { m_words.append(x); } + UnsignedBigInteger() {} + + const AK::Vector<u32>& words() const { return m_words; } + + UnsignedBigInteger add(const UnsignedBigInteger& other); + + size_t length() const { return m_words.size(); } + + // The "trimmed length" is the number of words after trimming leading zeroed words + size_t trimmed_length() const; + + bool operator==(const UnsignedBigInteger& other) const; + +private: + AK::Vector<u32> m_words; +}; + +} + +inline const LogStream& operator<<(const LogStream& stream, const Crypto::UnsignedBigInteger value) +{ + for (int i = value.length() - 1; i >= 0; --i) { + stream << value.words()[i] << "|"; + } + return stream; +} diff --git a/Libraries/LibCrypto/Makefile b/Libraries/LibCrypto/Makefile index 80f75f5130..a9c249dde9 100644 --- a/Libraries/LibCrypto/Makefile +++ b/Libraries/LibCrypto/Makefile @@ -1,7 +1,8 @@ LIBCRYPTO_OBJS = \ Cipher/AES.o \ Hash/MD5.o \ - Hash/SHA2.o + Hash/SHA2.o \ + BigInt/UnsignedBigInteger.o OBJS = $(LIBCRYPTO_OBJS) diff --git a/Userland/test-crypto.cpp b/Userland/test-crypto.cpp index 4259d1ad09..b47988a643 100644 --- a/Userland/test-crypto.cpp +++ b/Userland/test-crypto.cpp @@ -1,6 +1,8 @@ +#include <LibC/limits.h> #include <LibCore/ArgsParser.h> #include <LibCore/File.h> #include <LibCrypto/Authentication/HMAC.h> +#include <LibCrypto/BigInt/UnsignedBigInteger.h> #include <LibCrypto/Cipher/AES.h> #include <LibCrypto/Hash/MD5.h> #include <LibCrypto/Hash/SHA2.h> @@ -35,6 +37,9 @@ int hmac_md5_tests(); int hmac_sha256_tests(); int hmac_sha512_tests(); +// Big Integer +int bigint_tests(); + // stop listing tests void print_buffer(const ByteBuffer& buffer, int split) @@ -227,6 +232,9 @@ auto main(int argc, char** argv) -> int printf("unknown hash function '%s'\n", suite); return 1; } + if (mode_sv == "bigint") { + return bigint_tests(); + } encrypting = mode_sv == "encrypt"; if (encrypting || mode_sv == "decrypt") { if (suite == nullptr) @@ -294,6 +302,9 @@ void hmac_sha256_test_process(); void hmac_sha512_test_name(); void hmac_sha512_test_process(); +void bigint_test_fibo500(); +void bigint_addition_edgecases(); + int aes_cbc_tests() { aes_cbc_test_name(); @@ -781,3 +792,49 @@ void hmac_sha512_test_process() PASS; } } + +int bigint_tests() +{ + bigint_test_fibo500(); + bigint_addition_edgecases(); + return 0; +} + +void bigint_test_fibo500() +{ + { + I_TEST((BigInteger | Fibonacci500)); + Crypto::UnsignedBigInteger num1(0); + Crypto::UnsignedBigInteger num2(1); + for (int i = 0; i < 500; ++i) { + Crypto::UnsignedBigInteger t = num1.add(num2); + num2 = num1; + num1 = t; + } + bool pass = (num1.words() == AK::Vector<u32> { 315178285, 505575602, 1883328078, 125027121, 3649625763, 347570207, 74535262, 3832543808, 2472133297, 1600064941, 65273441 }); + + if (pass) + PASS; + else { + FAIL(Incorrect Result); + } + } +} + +void bigint_addition_edgecases() +{ + { + I_TEST((BigInteger | Edge Cases)); + Crypto::UnsignedBigInteger num1; + Crypto::UnsignedBigInteger num2(70); + Crypto::UnsignedBigInteger num3 = num1.add(num2); + bool pass = (num3 == num2); + pass &= (num1 == Crypto::UnsignedBigInteger(0)); + + if (pass) { + PASS; + } else { + FAIL(Incorrect Result); + } + } +} |