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