Add base58 encoding/decoding

6 files changed, 454 insertions, 0 deletions

diff --git a/src/lib/codec/base58/base58.cpp b/src/lib/codec/base58/base58.cpp
new file mode 100644
index 000000000..15925cc17
--- /dev/null
+++ b/src/lib/codec/base58/base58.cpp
@@ -0,0 +1,175 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/base58.h>
+#include <botan/exceptn.h>
+#include <botan/bigint.h>
+#include <botan/divide.h>
+#include <botan/loadstor.h>
+#include <botan/hash.h>
+
+namespace Botan {
+
+namespace {
+
+uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length)
+   {
+   std::unique_ptr<HashFunction> sha256 = HashFunction::create_or_throw("SHA-256");
+
+   std::vector<uint8_t> checksum(32);
+
+   sha256->update(input, input_length);
+   sha256->final(checksum);
+
+   sha256->update(checksum);
+   sha256->final(checksum);
+
+   checksum.resize(4);
+   uint32_t c = load_be<uint32_t>(checksum.data(), 0);
+   return c;
+   }
+
+class Character_Table
+   {
+   public:
+      // This must be a literal constant
+      Character_Table(const char* alphabet) :
+         m_alphabet(alphabet)
+         {
+         const size_t alpha_len = std::strlen(alphabet);
+
+         // 128 or up would flow into 0x80 invalid bit
+         if(alpha_len == 0 || alpha_len >= 128)
+            throw Invalid_Argument("Bad Character_Table string");
+
+         m_alphabet_len = static_cast<uint8_t>(alpha_len);
+
+         set_mem(m_tab, 256, 0x80);
+
+         for(size_t i = 0; m_alphabet[i]; ++i)
+            {
+            const uint8_t b = static_cast<uint8_t>(m_alphabet[i]);
+            BOTAN_ASSERT(m_tab[b] == 0x80, "No duplicate chars");
+            m_tab[b] = i;
+            }
+         }
+
+      uint8_t radix() const { return m_alphabet_len; }
+
+      char operator[](size_t i) const
+         {
+         BOTAN_ASSERT(i < m_alphabet_len, "Character in range");
+         return m_alphabet[i];
+         }
+
+      uint8_t code_for(char c) const
+         {
+         return m_tab[static_cast<uint8_t>(c)];
+         }
+
+   private:
+      const char* m_alphabet;
+      uint8_t m_alphabet_len;
+      uint8_t m_tab[256];
+   };
+
+static const Character_Table& BASE58_ALPHA()
+   {
+   static const Character_Table base58_alpha("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz");
+   return base58_alpha;
+   }
+
+std::string base58_encode(BigInt v, size_t leading_zeros)
+   {
+   const auto base58 = BASE58_ALPHA();
+
+   std::string result;
+   BigInt q;
+   uint8_t r;
+
+   while(v.is_nonzero())
+      {
+      ct_divide_u8(v, base58.radix(), q, r);
+      result.push_back(base58[r]);
+      v.swap(q);
+      }
+
+   for(size_t i = 0; i != leading_zeros; ++i)
+      result.push_back(base58[0]);
+
+   return std::string(result.rbegin(), result.rend());
+   }
+
+template<typename T, typename Z>
+size_t count_leading_zeros(const T input[], size_t input_length, Z zero)
+   {
+   size_t leading_zeros = 0;
+
+   while(leading_zeros < input_length && input[leading_zeros] == zero)
+      leading_zeros += 1;
+
+   return leading_zeros;
+   }
+
+}
+
+std::string base58_encode(const uint8_t input[], size_t input_length)
+   {
+   BigInt v(input, input_length);
+   return base58_encode(v, count_leading_zeros(input, input_length, 0));
+   }
+
+std::string base58_check_encode(const uint8_t input[], size_t input_length)
+   {
+   BigInt v(input, input_length);
+   v <<= 32;
+   v += sha256_d_checksum(input, input_length);
+   return base58_encode(v, count_leading_zeros(input, input_length, 0));
+   }
+
+std::vector<uint8_t> base58_decode(const char input[], size_t input_length)
+   {
+   const auto base58 = BASE58_ALPHA();
+
+   const size_t leading_zeros = count_leading_zeros(input, input_length, base58[0]);
+
+   BigInt v;
+
+   for(size_t i = leading_zeros; i != input_length; ++i)
+      {
+      size_t idx = base58.code_for(input[i]);
+
+      if(idx == 0x80)
+         throw Decoding_Error("Invalid base58");
+
+      v *= base58.radix();
+      v += idx;
+      }
+
+   std::vector<uint8_t> output(v.bytes() + leading_zeros);
+   v.binary_encode(&output[leading_zeros]);
+   return output;
+   }
+
+std::vector<uint8_t> base58_check_decode(const char input[], size_t input_length)
+   {
+   std::vector<uint8_t> dec = base58_decode(input, input_length);
+
+   if(dec.size() < 4)
+      throw Decoding_Error("Invalid base58 too short for checksum");
+
+   const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);
+   const uint32_t checksum = load_be<uint32_t>(&dec[dec.size()-4], 0);
+
+   if(checksum != computed_checksum)
+      throw Decoding_Error("Invalid base58 checksum");
+
+   dec.resize(dec.size() - 4);
+
+   return dec;
+   }
+
+}
diff --git a/src/lib/codec/base58/base58.h b/src/lib/codec/base58/base58.h
new file mode 100644
index 000000000..7a548e75e
--- /dev/null
+++ b/src/lib/codec/base58/base58.h
@@ -0,0 +1,83 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_BASE58_CODEC_H_
+#define BOTAN_BASE58_CODEC_H_
+
+#include <botan/secmem.h>
+#include <vector>
+#include <string>
+
+namespace Botan {
+
+/**
+* Perform base58 encoding
+*
+* This is raw base58 encoding, without the checksum
+*/
+std::string
+BOTAN_PUBLIC_API(2,9) base58_encode(const uint8_t input[],
+                                    size_t input_length);
+
+/**
+* Perform base58 encoding
+*
+* This is raw base58 encoding, without the checksum
+*/
+/**
+* Perform base58 encoding with checksum
+*/
+std::string
+BOTAN_PUBLIC_API(2,9) base58_check_encode(const uint8_t input[],
+                                          size_t input_length);
+
+
+/**
+* Perform base58 decoding
+*
+* This is raw base58 encoding, without the checksum
+*/
+std::vector<uint8_t>
+BOTAN_PUBLIC_API(2,9) base58_decode(const char input[],
+                                    size_t input_length);
+
+/**
+* Perform base58 decoding with checksum
+*
+* This is raw base58 encoding, without the checksum
+*/
+std::vector<uint8_t>
+BOTAN_PUBLIC_API(2,9) base58_check_decode(const char input[],
+                                          size_t input_length);
+
+
+// Some convenience wrappers:
+
+template<typename Alloc>
+inline std::string base58_encode(const std::vector<uint8_t, Alloc>& vec)
+   {
+   return base58_encode(vec.data(), vec.size());
+   }
+
+template<typename Alloc>
+inline std::string base58_check_encode(const std::vector<uint8_t, Alloc>& vec)
+   {
+   return base58_check_encode(vec.data(), vec.size());
+   }
+
+inline std::vector<uint8_t> base58_decode(const std::string& s)
+   {
+   return base58_decode(s.data(), s.size());
+   }
+
+inline std::vector<uint8_t> base58_check_decode(const std::string& s)
+   {
+   return base58_check_decode(s.data(), s.size());
+   }
+
+}
+
+#endif
diff --git a/src/lib/codec/base58/info.txt b/src/lib/codec/base58/info.txt
new file mode 100644
index 000000000..0b09c016d
--- /dev/null
+++ b/src/lib/codec/base58/info.txt
@@ -0,0 +1,8 @@
+<defines>
+BASE58_CODEC -> 20181209
+</defines>
+
+<requires>
+sha2_32
+bigint
+</requires>
diff --git a/src/tests/data/base58.vec b/src/tests/data/base58.vec
new file mode 100644
index 000000000..6c8d30fcc
--- /dev/null
+++ b/src/tests/data/base58.vec
@@ -0,0 +1,68 @@
+
+# Test data from https://github.com/nham/rust-base58/blob/master/src/lib.rs
+
+[valid]
+
+Binary =
+Base58 =
+
+Binary = 20
+Base58 = Z
+
+Binary = 2d
+Base58 = n
+
+Binary = 30
+Base58 = q
+
+Binary = 31
+Base58 = r
+
+Binary = 39
+Base58 = z
+
+Binary = 2D31
+Base58 = 4SU
+
+Binary = 3131
+Base58 = 4k8
+
+Binary = 616263
+Base58 = ZiCa
+
+Binary = 31323334353938373630
+Base58 = 3mJr7AoUXx2Wqd
+
+Binary = 6162636465666768696a6b6c6d6e6f707172737475767778797a
+Base58 = 3yxU3u1igY8WkgtjK92fbJQCd4BZiiT1v25f
+
+Binary = 00010966776006953D5567439E5E39F86A0D273BEED61967F6
+Base58 = 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM
+
+Binary = 00616263
+Base58 = 1ZiCa
+
+Binary = 0000616263
+Base58 = 11ZiCa
+
+Binary = 000000616263
+Base58 = 111ZiCa
+
+Binary = 00000000616263
+Base58 = 1111ZiCa
+
+[invalid]
+
+Base58 = 0
+Base58 = O
+Base58 = I
+Base58 = l
+Base58 = 3mJr0
+Base58 = O3yxU
+Base58 = 3sNI
+Base58 = 4kl8
+Base58 = s!5<
+Base58 = t$@mX<*
+Base58 = AreYouEvenLookingAtThese?
+
+
diff --git a/src/tests/data/base58c.vec b/src/tests/data/base58c.vec
new file mode 100644
index 000000000..30ea5a840
--- /dev/null
+++ b/src/tests/data/base58c.vec
@@ -0,0 +1,24 @@
+
+[valid]
+
+Binary =
+Base58 = 3QJmnh
+
+Binary = 31
+Base58 = 6bdbJ1U
+
+Binary = 00010966776006953D5567439E5E39F86A0D273BEE
+Base58 = 16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM
+
+Binary = 6162636465666768696a6b6c6d6e6f707172737475767778797a
+Base58 = LWmP1W82eUos2HWzVn19rapmig4X5dqPWgGFLsUTJ
+
+[invalid]
+
+Base58 = 3vQB7B6MrGQZaxCuFg4oH
+
+Base58 = 39QB7B6MrGQZaxCuFg4oH
+
+Base58 = 3mJr7AoUXx2Wqd
+Base58 = 3mJr7AoUXx2Wqd
+Base58 = 4SU
diff --git a/src/tests/test_utils.cpp b/src/tests/test_utils.cpp
index f1c6bef43..6708524b4 100644
--- a/src/tests/test_utils.cpp
+++ b/src/tests/test_utils.cpp
@@ -27,6 +27,10 @@
    #include <botan/base32.h>
 #endif
 
+#if defined(BOTAN_HAS_BASE58_CODEC)
+   #include <botan/base58.h>
+#endif
+
 #if defined(BOTAN_HAS_POLY_DBL)
    #include <botan/internal/poly_dbl.h>
 #endif
@@ -459,6 +463,98 @@ BOTAN_REGISTER_TEST("base32", Base32_Tests);
 
 #endif
 
+#if defined(BOTAN_HAS_BASE58_CODEC)
+
+class Base58_Tests final : public Text_Based_Test
+   {
+   public:
+      Base58_Tests() : Text_Based_Test("base58.vec", "Base58", "Binary") {}
+
+      Test::Result run_one_test(const std::string& type, const VarMap& vars) override
+         {
+         Test::Result result("Base58");
+
+         const bool is_valid = (type == "valid");
+         const std::string base58 = vars.get_req_str("Base58");
+
+         try
+            {
+            if(is_valid)
+               {
+               const std::vector<uint8_t> binary = vars.get_req_bin("Binary");
+               result.test_eq("base58 decoding", Botan::base58_decode(base58), binary);
+               result.test_eq("base58 encoding", Botan::base58_encode(binary), base58);
+               }
+            else
+               {
+               auto res = Botan::base58_decode(base58);
+               result.test_failure("decoded invalid base58 to " + Botan::hex_encode(res));
+               }
+            }
+         catch(std::exception& e)
+            {
+            if(is_valid)
+               {
+               result.test_failure("rejected valid base58", e.what());
+               }
+            else
+               {
+               result.test_note("rejected invalid base58");
+               }
+            }
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("base58", Base58_Tests);
+
+class Base58_Check_Tests final : public Text_Based_Test
+   {
+   public:
+      Base58_Check_Tests() : Text_Based_Test("base58c.vec", "Base58", "Binary") {}
+
+      Test::Result run_one_test(const std::string& type, const VarMap& vars) override
+         {
+         Test::Result result("Base58 Check");
+
+         const bool is_valid = (type == "valid");
+         const std::string base58 = vars.get_req_str("Base58");
+
+         try
+            {
+            if(is_valid)
+               {
+               const std::vector<uint8_t> binary = vars.get_req_bin("Binary");
+               result.test_eq("base58 decoding", Botan::base58_check_decode(base58), binary);
+               result.test_eq("base58 encoding", Botan::base58_check_encode(binary), base58);
+               }
+            else
+               {
+               auto res = Botan::base58_check_decode(base58);
+               result.test_failure("decoded invalid base58c to " + Botan::hex_encode(res));
+               }
+            }
+         catch(std::exception& e)
+            {
+            if(is_valid)
+               {
+               result.test_failure("rejected valid base58c", e.what());
+               }
+            else
+               {
+               result.test_note("rejected invalid base58c");
+               }
+            }
+
+         return result;
+         }
+   };
+
+BOTAN_REGISTER_TEST("base58c", Base58_Check_Tests);
+
+#endif
+
 #if defined(BOTAN_HAS_BASE64_CODEC)
 
 class Base64_Tests final : public Text_Based_Test