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