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
|
/*
big integer class for RSA calculation
Numbers stored in big endian order.
*/
/*
* Includes
*/
#include <stdio.h>
#include <string.h>
#include "bigint.h"
/*
* Sub
* Subtract (shifted) b from a.
*/
int BigInt::Sub(BigInt &a, BigInt &b, int b_shift)
{
unsigned int b_byte = sizeof(data) - 1 + (b_shift / 8);
int b_bit = (b_shift % 8);
int carry = 0;
for (int ia=sizeof(data)-1; ia>=0; ia--)
{
unsigned char b_data_shifted = 0;
if (b_byte + 1 < sizeof(b.data)) b_data_shifted |= b.data[b_byte + 1] >> (8 - b_bit);
if (b_byte + 0 < sizeof(b.data)) b_data_shifted |= b.data[b_byte + 0] << b_bit;
b_byte--;
int r = a.data[ia] - b_data_shifted + carry;
data[ia] = r;
carry = r>>8;
}
return carry;
}
/*
* MulMod
* Multiply two numbers and perform modulo.
*/
void BigInt::MulMod(BigInt &a, BigInt &b, BigInt &m)
{
memset(this, 0, sizeof(*this));
for (unsigned int ia=sizeof(data) - 1; ia>=sizeof(data)/2; ia--)
{
int carry = 0;
for (unsigned int ib=sizeof(data) - 1; ib>=sizeof(data)/2; ib--)
{
int iab = ia + ib - sizeof(data) + 1;
unsigned int r = a.data[ia] * b.data[ib] + carry + data[iab];
data[iab] = r;
carry = r>>8;
}
}
for (int shift=sizeof(data)/2*8; shift>=0; shift--)
{
BigInt subbed;
if (!subbed.Sub(*this, m, shift)) // positive?
{
memcpy(this, &subbed, sizeof(*this));
}
}
}
/*
* PowMod
* Raise to power 65537 and perform modulo.
*/
void BigInt::PowMod(BigInt &n, BigInt &m)
{
BigInt n65536;
memcpy(&n65536, &n, sizeof(n));
for (int i=0; i<16; i++) // 16 times n^2 = n^65536
{
BigInt tmp;
tmp.MulMod(n65536, n65536, m);
memcpy(&n65536, &tmp, sizeof(n));
}
MulMod(n, n65536, m); // final result: n^1 * n^65536
}
/*
* print
*/
void BigInt::print()
{
printf("0x");
bool show = false;
for (unsigned int i=0; i<sizeof(data); i++)
{
if (data[i]) show = true;
if (show) printf("%02X", data[i]);
}
printf(show ? "\n" : "0\n");
}
/*
* Set
*/
void BigInt::Set(unsigned char *data, unsigned int length)
{
memset(this, 0, sizeof(*this));
memcpy(this->data + sizeof(this->data) - length, data, length);
}
/*
* Get
*/
void BigInt::Get(unsigned char *data, unsigned int length)
{
memcpy(data, this->data + sizeof(this->data) - length, length);
}
|
