forked from trezor/trezor-firmware
-
Notifications
You must be signed in to change notification settings - Fork 0
/
bignum.h
184 lines (163 loc) · 7.13 KB
/
bignum.h
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
/**
* Copyright (c) 2013-2014 Tomas Dzetkulic
* Copyright (c) 2013-2014 Pavol Rusnak
* Copyright (c) 2016 Alex Beregszaszi
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES
* OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef __BIGNUM_H__
#define __BIGNUM_H__
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "options.h"
#define BN_LIMBS 9
#define BN_BITS_PER_LIMB 29
#define BN_BASE (1u << BN_BITS_PER_LIMB)
#define BN_LIMB_MASK ((1u << BN_BITS_PER_LIMB) - 1)
#define BN_EXTRA_BITS (32 - BN_BITS_PER_LIMB)
#define BN_BITS_LAST_LIMB (256 - (BN_LIMBS - 1) * BN_BITS_PER_LIMB)
// Represents the number sum([val[i] * 2**(29*i) for i in range(9))
typedef struct {
uint32_t val[BN_LIMBS];
} bignum256;
// Represents the number sum([val[i] * 2**(29*i) for i in range(18))
typedef struct {
uint32_t val[2 * BN_LIMBS];
} bignum512;
static inline uint32_t read_be(const uint8_t *data) {
return (((uint32_t)data[0]) << 24) | (((uint32_t)data[1]) << 16) |
(((uint32_t)data[2]) << 8) | (((uint32_t)data[3]));
}
static inline void write_be(uint8_t *data, uint32_t x) {
data[0] = x >> 24;
data[1] = x >> 16;
data[2] = x >> 8;
data[3] = x;
}
static inline uint32_t read_le(const uint8_t *data) {
return (((uint32_t)data[3]) << 24) | (((uint32_t)data[2]) << 16) |
(((uint32_t)data[1]) << 8) | (((uint32_t)data[0]));
}
static inline void write_le(uint8_t *data, uint32_t x) {
data[3] = x >> 24;
data[2] = x >> 16;
data[1] = x >> 8;
data[0] = x;
}
void bn_copy_lower(const bignum512 *x, bignum256 *y);
void bn_read_be(const uint8_t *in_number, bignum256 *out_number);
void bn_read_be_512(const uint8_t *in_number, bignum512 *out_number);
void bn_write_be(const bignum256 *in_number, uint8_t *out_number);
void bn_read_le(const uint8_t *in_number, bignum256 *out_number);
void bn_write_le(const bignum256 *in_number, uint8_t *out_number);
void bn_read_uint32(uint32_t in_number, bignum256 *out_number);
void bn_read_uint64(uint64_t in_number, bignum256 *out_number);
int bn_bitcount(const bignum256 *x);
unsigned int bn_digitcount(const bignum256 *x);
void bn_zero(bignum256 *x);
void bn_one(bignum256 *x);
int bn_is_zero(const bignum256 *x);
int bn_is_one(const bignum256 *x);
int bn_is_less(const bignum256 *x, const bignum256 *y);
int bn_is_equal(const bignum256 *x, const bignum256 *y);
void bn_cmov(bignum256 *res, volatile uint32_t cond, const bignum256 *truecase,
const bignum256 *falsecase);
void bn_cnegate(volatile uint32_t cond, bignum256 *x, const bignum256 *prime);
void bn_lshift(bignum256 *x);
void bn_rshift(bignum256 *x);
void bn_setbit(bignum256 *x, uint16_t i);
void bn_clearbit(bignum256 *x, uint16_t i);
uint32_t bn_testbit(const bignum256 *x, uint16_t i);
void bn_xor(bignum256 *res, const bignum256 *x, const bignum256 *y);
void bn_mult_half(bignum256 *x, const bignum256 *prime);
void bn_mult_k(bignum256 *x, uint8_t k, const bignum256 *prime);
void bn_mod(bignum256 *x, const bignum256 *prime);
void bn_multiply(const bignum256 *k, bignum256 *x, const bignum256 *prime);
void bn_reduce(bignum512 *x, const bignum256 *prime);
void bn_fast_mod(bignum256 *x, const bignum256 *prime);
void bn_power_mod(const bignum256 *x, const bignum256 *e,
const bignum256 *prime, bignum256 *res);
void bn_sqrt(bignum256 *x, const bignum256 *prime);
uint32_t inverse_mod_power_two(uint32_t a, uint32_t n);
void bn_divide_base(bignum256 *x, const bignum256 *prime);
void bn_normalize(bignum256 *x);
void bn_add(bignum256 *x, const bignum256 *y);
void bn_addmod(bignum256 *x, const bignum256 *y, const bignum256 *prime);
void bn_addi(bignum256 *x, uint32_t y);
void bn_subi(bignum256 *x, uint32_t y, const bignum256 *prime);
void bn_subtractmod(const bignum256 *x, const bignum256 *y, bignum256 *res,
const bignum256 *prime);
void bn_subtract(const bignum256 *x, const bignum256 *y, bignum256 *res);
int bn_legendre(const bignum256 *x, const bignum256 *prime);
void bn_long_division(bignum256 *x, uint32_t d, bignum256 *q, uint32_t *r);
void bn_divmod58(bignum256 *x, uint32_t *r);
void bn_divmod1000(bignum256 *x, uint32_t *r);
void bn_inverse(bignum256 *x, const bignum256 *prime);
size_t bn_format(const bignum256 *amount, const char *prefix,
const char *suffix, unsigned int decimals, int exponent,
bool trailing, char thousands, char *output,
size_t output_length);
// Returns (uint32_t) in_number
// Assumes in_number < 2**32
// Assumes in_number is normalized
static inline uint32_t bn_write_uint32(const bignum256 *in_number) {
return in_number->val[0] | (in_number->val[1] << BN_BITS_PER_LIMB);
}
// Returns (uint64_t) in_number
// Assumes in_number < 2**64
// Assumes in_number is normalized
static inline uint64_t bn_write_uint64(const bignum256 *in_number) {
uint64_t acc;
acc = in_number->val[2];
acc <<= BN_BITS_PER_LIMB;
acc |= in_number->val[1];
acc <<= BN_BITS_PER_LIMB;
acc |= in_number->val[0];
return acc;
}
// y = x
static inline void bn_copy(const bignum256 *x, bignum256 *y) { *y = *x; }
// Returns x % 2 == 0
static inline int bn_is_even(const bignum256 *x) {
return (x->val[0] & 1) == 0;
}
// Returns x % 2 == 0
static inline int bn_is_odd(const bignum256 *x) { return (x->val[0] & 1) == 1; }
static inline size_t bn_format_uint64(uint64_t amount, const char *prefix,
const char *suffix, unsigned int decimals,
int exponent, bool trailing,
char thousands, char *output,
size_t output_length) {
bignum256 bn_amount;
bn_read_uint64(amount, &bn_amount);
return bn_format(&bn_amount, prefix, suffix, decimals, exponent, trailing,
thousands, output, output_length);
}
static inline size_t bn_format_amount(uint64_t amount, const char *prefix,
const char *suffix, unsigned int decimals,
char *output, size_t output_length) {
return bn_format_uint64(amount, prefix, suffix, decimals, 0, false, ',',
output, output_length);
}
#if USE_BN_PRINT
void bn_print(const bignum256 *x);
void bn_print_raw(const bignum256 *x);
#endif
#endif