From 0b92da57db9397e799265a04eefc14852d2e4b28 Mon Sep 17 00:00:00 2001 From: Jack Lloyd Date: Sat, 17 Nov 2018 13:52:02 -0500 Subject: Add base58 encoding/decoding --- src/lib/codec/base58/base58.cpp | 175 ++++++++++++++++++++++++++++++++++++++++ src/lib/codec/base58/base58.h | 83 +++++++++++++++++++ src/lib/codec/base58/info.txt | 8 ++ src/tests/data/base58.vec | 68 ++++++++++++++++ src/tests/data/base58c.vec | 24 ++++++ src/tests/test_utils.cpp | 96 ++++++++++++++++++++++ 6 files changed, 454 insertions(+) create mode 100644 src/lib/codec/base58/base58.cpp create mode 100644 src/lib/codec/base58/base58.h create mode 100644 src/lib/codec/base58/info.txt create mode 100644 src/tests/data/base58.vec create mode 100644 src/tests/data/base58c.vec (limited to 'src') 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 +#include +#include +#include +#include +#include + +namespace Botan { + +namespace { + +uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length) + { + std::unique_ptr sha256 = HashFunction::create_or_throw("SHA-256"); + + std::vector checksum(32); + + sha256->update(input, input_length); + sha256->final(checksum); + + sha256->update(checksum); + sha256->final(checksum); + + checksum.resize(4); + uint32_t c = load_be(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(alpha_len); + + set_mem(m_tab, 256, 0x80); + + for(size_t i = 0; m_alphabet[i]; ++i) + { + const uint8_t b = static_cast(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(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 +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 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 output(v.bytes() + leading_zeros); + v.binary_encode(&output[leading_zeros]); + return output; + } + +std::vector base58_check_decode(const char input[], size_t input_length) + { + std::vector 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(&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 +#include +#include + +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 +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 +BOTAN_PUBLIC_API(2,9) base58_check_decode(const char input[], + size_t input_length); + + +// Some convenience wrappers: + +template +inline std::string base58_encode(const std::vector& vec) + { + return base58_encode(vec.data(), vec.size()); + } + +template +inline std::string base58_check_encode(const std::vector& vec) + { + return base58_check_encode(vec.data(), vec.size()); + } + +inline std::vector base58_decode(const std::string& s) + { + return base58_decode(s.data(), s.size()); + } + +inline std::vector 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 @@ + +BASE58_CODEC -> 20181209 + + + +sha2_32 +bigint + 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 #endif +#if defined(BOTAN_HAS_BASE58_CODEC) + #include +#endif + #if defined(BOTAN_HAS_POLY_DBL) #include #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 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 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 -- cgit v1.2.3