LibCrypto: Add UnsignedBigInteger and implement addition

UnsignedBigInteger stores an unsigned ainteger of arbitrary length.

A big integer is represented  as a vector of word. Each
word is an unsigned int.

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);
+        }
+    }
+}