Botan  2.11.0
Crypto and TLS for C++11
base58.cpp
Go to the documentation of this file.
1 /*
2 * (C) 2018 Jack Lloyd
3 *
4 * Botan is released under the Simplified BSD License (see license.txt)
5 */
6 
7 #include <botan/base58.h>
8 #include <botan/exceptn.h>
9 #include <botan/bigint.h>
10 #include <botan/divide.h>
11 #include <botan/loadstor.h>
12 #include <botan/hash.h>
13 
14 namespace Botan {
15 
16 namespace {
17 
18 uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length)
19  {
20  std::unique_ptr<HashFunction> sha256 = HashFunction::create_or_throw("SHA-256");
21 
22  std::vector<uint8_t> checksum(32);
23 
24  sha256->update(input, input_length);
25  sha256->final(checksum);
26 
27  sha256->update(checksum);
28  sha256->final(checksum);
29 
30  return load_be<uint32_t>(checksum.data(), 0);
31  }
32 
33 class Character_Table
34  {
35  public:
36  // This must be a literal constant
37  Character_Table(const char* alphabet) :
38  m_alphabet(alphabet)
39  {
40  const size_t alpha_len = std::strlen(alphabet);
41 
42  // 128 or up would flow into 0x80 invalid bit
43  if(alpha_len == 0 || alpha_len >= 128)
44  throw Invalid_Argument("Bad Character_Table string");
45 
46  m_alphabet_len = static_cast<uint8_t>(alpha_len);
47 
48  set_mem(m_tab, 256, 0x80);
49 
50  for(size_t i = 0; m_alphabet[i]; ++i)
51  {
52  const uint8_t b = static_cast<uint8_t>(m_alphabet[i]);
53  BOTAN_ASSERT(m_tab[b] == 0x80, "No duplicate chars");
54  m_tab[b] = static_cast<uint8_t>(i);
55  }
56  }
57 
58  uint8_t radix() const { return m_alphabet_len; }
59 
60  char operator[](size_t i) const
61  {
62  BOTAN_ASSERT(i < m_alphabet_len, "Character in range");
63  return m_alphabet[i];
64  }
65 
66  uint8_t code_for(char c) const
67  {
68  return m_tab[static_cast<uint8_t>(c)];
69  }
70 
71  private:
72  const char* m_alphabet;
73  uint8_t m_alphabet_len;
74  uint8_t m_tab[256];
75  };
76 
77 static const Character_Table& BASE58_ALPHA()
78  {
79  static const Character_Table base58_alpha("123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz");
80  return base58_alpha;
81  }
82 
83 std::string base58_encode(BigInt v, size_t leading_zeros)
84  {
85  const auto base58 = BASE58_ALPHA();
86 
87  std::string result;
88  BigInt q;
89  uint8_t r;
90 
91  while(v.is_nonzero())
92  {
93  ct_divide_u8(v, base58.radix(), q, r);
94  result.push_back(base58[r]);
95  v.swap(q);
96  }
97 
98  for(size_t i = 0; i != leading_zeros; ++i)
99  result.push_back(base58[0]);
100 
101  return std::string(result.rbegin(), result.rend());
102  }
103 
104 template<typename T, typename Z>
105 size_t count_leading_zeros(const T input[], size_t input_length, Z zero)
106  {
107  size_t leading_zeros = 0;
108 
109  while(leading_zeros < input_length && input[leading_zeros] == zero)
110  leading_zeros += 1;
111 
112  return leading_zeros;
113  }
114 
115 }
116 
117 std::string base58_encode(const uint8_t input[], size_t input_length)
118  {
119  BigInt v(input, input_length);
120  return base58_encode(v, count_leading_zeros(input, input_length, 0));
121  }
122 
123 std::string base58_check_encode(const uint8_t input[], size_t input_length)
124  {
125  BigInt v(input, input_length);
126  v <<= 32;
127  v += sha256_d_checksum(input, input_length);
128  return base58_encode(v, count_leading_zeros(input, input_length, 0));
129  }
130 
131 std::vector<uint8_t> base58_decode(const char input[], size_t input_length)
132  {
133  const auto base58 = BASE58_ALPHA();
134 
135  const size_t leading_zeros = count_leading_zeros(input, input_length, base58[0]);
136 
137  BigInt v;
138 
139  for(size_t i = leading_zeros; i != input_length; ++i)
140  {
141  const char c = input[i];
142 
143  if(c == ' ' || c == '\n')
144  continue;
145 
146  const size_t idx = base58.code_for(c);
147 
148  if(idx == 0x80)
149  throw Decoding_Error("Invalid base58");
150 
151  v *= base58.radix();
152  v += idx;
153  }
154 
155  std::vector<uint8_t> output(v.bytes() + leading_zeros);
156  v.binary_encode(output.data() + leading_zeros);
157  return output;
158  }
159 
160 std::vector<uint8_t> base58_check_decode(const char input[], size_t input_length)
161  {
162  std::vector<uint8_t> dec = base58_decode(input, input_length);
163 
164  if(dec.size() < 4)
165  throw Decoding_Error("Invalid base58 too short for checksum");
166 
167  const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);
168  const uint32_t checksum = load_be<uint32_t>(&dec[dec.size()-4], 0);
169 
170  if(checksum != computed_checksum)
171  throw Decoding_Error("Invalid base58 checksum");
172 
173  dec.resize(dec.size() - 4);
174 
175  return dec;
176  }
177 
178 }
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: hash.cpp:359
std::vector< uint8_t > base58_check_decode(const char input[], size_t input_length)
Definition: base58.cpp:160
uint32_t load_be< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:177
void set_mem(uint8_t *ptr, size_t n, uint8_t val)
Definition: mem_ops.h:151
std::string base58_encode(const uint8_t input[], size_t input_length)
Definition: base58.cpp:117
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:384
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:55
std::vector< uint8_t > base58_decode(const char input[], size_t input_length)
Definition: base58.cpp:131
Definition: alg_id.cpp:13
size_t bytes() const
Definition: bigint.cpp:266
std::string base58_check_encode(const uint8_t input[], size_t input_length)
Definition: base58.cpp:123
void ct_divide_u8(const BigInt &x, uint8_t y, BigInt &q_out, uint8_t &r_out)
Definition: divide.cpp:82
fe T
Definition: ge.cpp:37
fe Z
Definition: ge.cpp:29