athena/src/bn.cpp

85 lines
1.6 KiB
C++
Raw Permalink Normal View History

2017-12-29 07:55:42 +00:00
#include <cstring>
#include <stdio.h>
#include "bn.hpp"
2018-12-08 05:18:17 +00:00
namespace bignum {
void subModulus(atUint8* a, const atUint8* N, atUint32 n) {
atUint8 c = 0;
for (atUint32 i = n - 1; i < n; i--) {
atUint32 dig = N[i] + c;
c = (a[i] < dig);
a[i] -= dig;
}
}
2018-12-08 05:18:17 +00:00
void add(atUint8* d, atUint8* a, const atUint8* b, const atUint8* N, atUint32 n) {
atUint8 c = 0;
2018-12-08 05:18:17 +00:00
for (atUint32 i = n - 1; i < n; i--) {
atUint32 dig = a[i] + b[i] + c;
c = (dig >= 0x100);
d[i] = dig;
}
2018-12-08 05:18:17 +00:00
if (c)
subModulus(d, N, n);
2018-12-08 05:18:17 +00:00
if (compare(d, N, n) >= 0)
subModulus(d, N, n);
}
2018-12-08 05:18:17 +00:00
void mul(atUint8* d, atUint8* a, const atUint8* b, const atUint8* N, atUint32 n) {
memset(d, 0, n);
2018-12-08 05:18:17 +00:00
for (atUint32 i = 0; i < n; i++) {
for (atUint8 mask = 0x80; mask != 0; mask >>= 1) {
add(d, d, d, N, n);
2018-12-08 05:18:17 +00:00
if ((a[i] & mask) != 0)
add(d, d, b, N, n);
}
2018-12-08 05:18:17 +00:00
}
}
2018-12-08 05:18:17 +00:00
void exp(atUint8* d, const atUint8* a, const atUint8* N, atUint32 n, atUint8* e, atUint32 en) {
atUint8 t[512];
memset(d, 0, n);
d[n - 1] = 1;
for (atUint32 i = 0; i < en; i++) {
for (atUint8 mask = 0x80; mask != 0; mask >>= 1) {
mul(t, d, d, N, n);
if ((e[i] & mask) != 0)
mul(d, t, a, N, n);
else
memcpy(d, t, n);
}
2018-12-08 05:18:17 +00:00
}
}
2018-12-08 05:18:17 +00:00
void inv(atUint8* d, atUint8* a, const atUint8* N, atUint32 n) {
atUint8 t[512], s[512];
2018-12-08 05:18:17 +00:00
memcpy(t, N, n);
memset(s, 0, n);
s[n - 1] = 2;
subModulus(t, s, n);
exp(d, a, N, n, t, n);
}
2018-12-08 05:18:17 +00:00
int compare(const atUint8* a, const atUint8* b, atUint32 n) {
for (atUint32 i = 0; i < n; i++) {
if (a[i] < b[i])
return -1;
2018-12-08 05:18:17 +00:00
if (a[i] > b[i])
return 1;
}
return 0;
}
2018-12-08 05:18:17 +00:00
} // namespace bignum