Botan  2.19.1
Crypto and TLS for C++11
base58.cpp
Go to the documentation of this file.
1 /*
2 * (C) 2018,2020 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/internal/ct_utils.h>
13 #include <botan/hash.h>
14 
15 namespace Botan {
16 
17 namespace {
18 
19 uint32_t sha256_d_checksum(const uint8_t input[], size_t input_length)
20  {
21  std::unique_ptr<HashFunction> sha256 = HashFunction::create_or_throw("SHA-256");
22 
23  std::vector<uint8_t> checksum(32);
24 
25  sha256->update(input, input_length);
26  sha256->final(checksum);
27 
28  sha256->update(checksum);
29  sha256->final(checksum);
30 
31  return load_be<uint32_t>(checksum.data(), 0);
32  }
33 
34 char lookup_base58_char(uint8_t x)
35  {
36  // "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
37  BOTAN_DEBUG_ASSERT(x < 58);
38 
39  const auto is_dec_19 = CT::Mask<uint8_t>::is_lte(x, 8);
40  const auto is_alpha_AH = CT::Mask<uint8_t>::is_within_range(x, 9, 16);
41  const auto is_alpha_JN = CT::Mask<uint8_t>::is_within_range(x, 17, 21);
42  const auto is_alpha_PZ = CT::Mask<uint8_t>::is_within_range(x, 22, 32);
43  const auto is_alpha_ak = CT::Mask<uint8_t>::is_within_range(x, 33, 43);
44  // otherwise in 'm'-'z'
45 
46  const char c_19 = '1' + x;
47  const char c_AH = 'A' + (x - 9);
48  const char c_JN = 'J' + (x - 17);
49  const char c_PZ = 'P' + (x - 22);
50  const char c_ak = 'a' + (x - 33);
51  const char c_mz = 'm' + (x - 44);
52 
53  char ret = c_mz;
54  ret = is_dec_19.select(c_19, ret);
55  ret = is_alpha_AH.select(c_AH, ret);
56  ret = is_alpha_JN.select(c_JN, ret);
57  ret = is_alpha_PZ.select(c_PZ, ret);
58  ret = is_alpha_ak.select(c_ak, ret);
59 
60  return ret;
61  }
62 
63 std::string base58_encode(BigInt v, size_t leading_zeros)
64  {
65  const uint8_t radix = 58;
66 
67  std::string result;
68  BigInt q;
69 
70  while(v.is_nonzero())
71  {
72  uint8_t r;
73  ct_divide_u8(v, radix, q, r);
74  result.push_back(lookup_base58_char(r));
75  v.swap(q);
76  }
77 
78  for(size_t i = 0; i != leading_zeros; ++i)
79  result.push_back('1'); // 'zero' byte
80 
81  return std::string(result.rbegin(), result.rend());
82  }
83 
84 template<typename T, typename Z>
85 size_t count_leading_zeros(const T input[], size_t input_length, Z zero)
86  {
87  size_t leading_zeros = 0;
88 
89  while(leading_zeros < input_length && input[leading_zeros] == zero)
90  leading_zeros += 1;
91 
92  return leading_zeros;
93  }
94 
95 uint8_t base58_value_of(char input)
96  {
97  // "123456789 ABCDEFGH JKLMN PQRSTUVWXYZ abcdefghijk mnopqrstuvwxyz"
98 
99  const uint8_t c = static_cast<uint8_t>(input);
100 
101  const auto is_dec_19 = CT::Mask<uint8_t>::is_within_range(c, uint8_t('1'), uint8_t('9'));
102  const auto is_alpha_AH = CT::Mask<uint8_t>::is_within_range(c, uint8_t('A'), uint8_t('H'));
103  const auto is_alpha_JN = CT::Mask<uint8_t>::is_within_range(c, uint8_t('J'), uint8_t('N'));
104  const auto is_alpha_PZ = CT::Mask<uint8_t>::is_within_range(c, uint8_t('P'), uint8_t('Z'));
105 
106  const auto is_alpha_ak = CT::Mask<uint8_t>::is_within_range(c, uint8_t('a'), uint8_t('k'));
107  const auto is_alpha_mz = CT::Mask<uint8_t>::is_within_range(c, uint8_t('m'), uint8_t('z'));
108 
109  const uint8_t c_dec_19 = c - uint8_t('1');
110  const uint8_t c_AH = c - uint8_t('A') + 9;
111  const uint8_t c_JN = c - uint8_t('J') + 17;
112  const uint8_t c_PZ = c - uint8_t('P') + 22;
113 
114  const uint8_t c_ak = c - uint8_t('a') + 33;
115  const uint8_t c_mz = c - uint8_t('m') + 44;
116 
117  uint8_t ret = 0xFF; // default value
118 
119  ret = is_dec_19.select(c_dec_19, ret);
120  ret = is_alpha_AH.select(c_AH, ret);
121  ret = is_alpha_JN.select(c_JN, ret);
122  ret = is_alpha_PZ.select(c_PZ, ret);
123  ret = is_alpha_ak.select(c_ak, ret);
124  ret = is_alpha_mz.select(c_mz, ret);
125  return ret;
126  }
127 
128 }
129 
130 std::string base58_encode(const uint8_t input[], size_t input_length)
131  {
132  BigInt v(input, input_length);
133  return base58_encode(v, count_leading_zeros(input, input_length, 0));
134  }
135 
136 std::string base58_check_encode(const uint8_t input[], size_t input_length)
137  {
138  BigInt v(input, input_length);
139  v <<= 32;
140  v += sha256_d_checksum(input, input_length);
141  return base58_encode(v, count_leading_zeros(input, input_length, 0));
142  }
143 
144 std::vector<uint8_t> base58_decode(const char input[], size_t input_length)
145  {
146  const size_t leading_zeros = count_leading_zeros(input, input_length, '1');
147 
148  BigInt v;
149 
150  for(size_t i = leading_zeros; i != input_length; ++i)
151  {
152  const char c = input[i];
153 
154  if(c == ' ' || c == '\n')
155  continue;
156 
157  const uint8_t idx = base58_value_of(c);
158 
159  if(idx == 0xFF)
160  throw Decoding_Error("Invalid base58");
161 
162  v *= 58;
163  v += idx;
164  }
165 
166  std::vector<uint8_t> output(v.bytes() + leading_zeros);
167  v.binary_encode(output.data() + leading_zeros);
168  return output;
169  }
170 
171 std::vector<uint8_t> base58_check_decode(const char input[], size_t input_length)
172  {
173  std::vector<uint8_t> dec = base58_decode(input, input_length);
174 
175  if(dec.size() < 4)
176  throw Decoding_Error("Invalid base58 too short for checksum");
177 
178  const uint32_t computed_checksum = sha256_d_checksum(dec.data(), dec.size() - 4);
179  const uint32_t checksum = load_be<uint32_t>(&dec[dec.size()-4], 0);
180 
181  if(checksum != computed_checksum)
182  throw Decoding_Error("Invalid base58 checksum");
183 
184  dec.resize(dec.size() - 4);
185 
186  return dec;
187  }
188 
189 }
void binary_encode(uint8_t buf[]) const
Definition: bigint.cpp:399
static std::unique_ptr< HashFunction > create_or_throw(const std::string &algo_spec, const std::string &provider="")
Definition: hash.cpp:344
std::vector< uint8_t > base58_check_decode(const char input[], size_t input_length)
Definition: base58.cpp:171
uint32_t load_be< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:179
static Mask< T > is_within_range(T v, T l, T u)
Definition: ct_utils.h:186
std::string base58_encode(const uint8_t input[], size_t input_length)
Definition: base58.cpp:130
static Mask< T > is_lte(T x, T y)
Definition: ct_utils.h:173
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
std::vector< uint8_t > base58_decode(const char input[], size_t input_length)
Definition: base58.cpp:144
Definition: alg_id.cpp:13
std::string base58_check_encode(const uint8_t input[], size_t input_length)
Definition: base58.cpp:136
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
size_t bytes() const
Definition: bigint.cpp:281