This library provides a way to easily handle arbitrary large integers.

This library provides the following operations :

  • addition, substraction, multiplication, division and modulo
  • bits operators (AND, OR, XOR, left and right shifts)
  • boolean operators
  • modular exponentiation (using montgomery algorithm)
  • modular inverse

Example

In this example, we use a 1024 bits long RSA key to encrypt and decrypt a message. We first encrypt the value 0x41 (65 in decimal) and then decrypt it. At the end, m should be equal to 0x41. The encryption is fast (0, 4 second) while the decryption is really slow. This code will take between 30 seconds and 2 minutes to execute depending on the compiler and optimization flags.

main.cpp

#include "mbed.h"
#include "BigInt.h"
#include <stdlib.h>
#include <stdio.h>

uint8_t modbits[] = {
0xd9, 0x4d, 0x88, 0x9e, 0x88, 0x85, 0x3d, 0xd8, 0x97, 0x69, 0xa1, 0x80, 0x15, 0xa0, 0xa2, 0xe6,
0xbf, 0x82, 0xbf, 0x35, 0x6f, 0xe1, 0x4f, 0x25, 0x1f, 0xb4, 0xf5, 0xe2, 0xdf, 0x0d, 0x9f, 0x9a,
0x94, 0xa6, 0x8a, 0x30, 0xc4, 0x28, 0xb3, 0x9e, 0x33, 0x62, 0xfb, 0x37, 0x79, 0xa4, 0x97, 0xec,
0xea, 0xea, 0x37, 0x10, 0x0f, 0x26, 0x4d, 0x7f, 0xb9, 0xfb, 0x1a, 0x97, 0xfb, 0xf6, 0x21, 0x13,
0x3d, 0xe5, 0x5f, 0xdc, 0xb9, 0xb1, 0xad, 0x0d, 0x7a, 0x31, 0xb3, 0x79, 0x21, 0x6d, 0x79, 0x25,
0x2f, 0x5c, 0x52, 0x7b, 0x9b, 0xc6, 0x3d, 0x83, 0xd4, 0xec, 0xf4, 0xd1, 0xd4, 0x5c, 0xbf, 0x84,
0x3e, 0x84, 0x74, 0xba, 0xbc, 0x65, 0x5e, 0x9b, 0xb6, 0x79, 0x9c, 0xba, 0x77, 0xa4, 0x7e, 0xaf,
0xa8, 0x38, 0x29, 0x64, 0x74, 0xaf, 0xc2, 0x4b, 0xeb, 0x9c, 0x82, 0x5b, 0x73, 0xeb, 0xf5, 0x49
};

uint8_t dbits[] = {
0x04, 0x7b, 0x9c, 0xfd, 0xe8, 0x43, 0x17, 0x6b, 0x88, 0x74, 0x1d, 0x68, 0xcf, 0x09, 0x69, 0x52,
0xe9, 0x50, 0x81, 0x31, 0x51, 0x05, 0x8c, 0xe4, 0x6f, 0x2b, 0x04, 0x87, 0x91, 0xa2, 0x6e, 0x50,
0x7a, 0x10, 0x95, 0x79, 0x3c, 0x12, 0xba, 0xe1, 0xe0, 0x9d, 0x82, 0x21, 0x3a, 0xd9, 0x32, 0x69,
0x28, 0xcf, 0x7c, 0x23, 0x50, 0xac, 0xb1, 0x9c, 0x98, 0xf1, 0x9d, 0x32, 0xd5, 0x77, 0xd6, 0x66,
0xcd, 0x7b, 0xb8, 0xb2, 0xb5, 0xba, 0x62, 0x9d, 0x25, 0xcc, 0xf7, 0x2a, 0x5c, 0xeb, 0x8a, 0x8d,
0xa0, 0x38, 0x90, 0x6c, 0x84, 0xdc, 0xdb, 0x1f, 0xe6, 0x77, 0xdf, 0xfb, 0x2c, 0x02, 0x9f, 0xd8,
0x92, 0x63, 0x18, 0xee, 0xde, 0x1b, 0x58, 0x27, 0x2a, 0xf2, 0x2b, 0xda, 0x5c, 0x52, 0x32, 0xbe,
0x06, 0x68, 0x39, 0x39, 0x8e, 0x42, 0xf5, 0x35, 0x2d, 0xf5, 0x88, 0x48, 0xad, 0xad, 0x11, 0xa1
};

int main() 
{
    BigInt e = 65537, mod, d;
    mod.importData(modbits, sizeof(modbits));
    d.importData(dbits, sizeof(dbits));

    BigInt c = modPow(0x41,e,mod);
    c.print();
    BigInt m = modPow(c,d,mod);
    m.print();
    printf("done\n");
    
    return 0;
}

Committer:
feb11
Date:
Mon Mar 10 12:51:47 2014 +0000
Revision:
20:d747159d77c4
Parent:
19:412b822df7bf
Child:
21:cfa04e0e6b59
fixed bugs + minor changes

Who changed what in which revision?

UserRevisionLine numberNew contents of line
feb11 0:9d554894785b 1 #include "BigInt.h"
feb11 0:9d554894785b 2 #include <string.h>
feb11 0:9d554894785b 3 #include <stdio.h>
feb11 0:9d554894785b 4 #include <stdlib.h>
feb11 0:9d554894785b 5 #include <iostream>
feb11 0:9d554894785b 6 #include <climits>
feb11 9:3c191fa04f6e 7 #include <cassert>
feb11 10:116e201f7d89 8 #include <algorithm>
feb11 0:9d554894785b 9
feb11 15:85a6bd4539eb 10 static uint32_t BITS[] =
feb11 15:85a6bd4539eb 11 {
feb11 15:85a6bd4539eb 12 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080,
feb11 15:85a6bd4539eb 13 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000,
feb11 15:85a6bd4539eb 14 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
feb11 15:85a6bd4539eb 15 0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000
feb11 15:85a6bd4539eb 16 };
feb11 15:85a6bd4539eb 17
feb11 0:9d554894785b 18 static uint32_t num(const uint32_t a)
feb11 0:9d554894785b 19 {
feb11 0:9d554894785b 20 return a/4 + (a%4 ? 1:0);
feb11 0:9d554894785b 21 }
feb11 10:116e201f7d89 22
feb11 10:116e201f7d89 23
feb11 0:9d554894785b 24 BigInt::BigInt():
feb11 0:9d554894785b 25 size(0),
feb11 0:9d554894785b 26 bits(0)
feb11 0:9d554894785b 27 {
feb11 0:9d554894785b 28 }
feb11 0:9d554894785b 29
feb11 2:1001793a090d 30 BigInt::BigInt(const uint32_t a)
feb11 2:1001793a090d 31 {
feb11 2:1001793a090d 32 if(a >> 24)
feb11 2:1001793a090d 33 size = 4;
feb11 2:1001793a090d 34 else if(a >> 16)
feb11 2:1001793a090d 35 size = 3;
feb11 2:1001793a090d 36 else if(a >> 8)
feb11 2:1001793a090d 37 size = 2;
feb11 2:1001793a090d 38 else
feb11 2:1001793a090d 39 size = 1;
feb11 2:1001793a090d 40 bits = new uint32_t[1];
feb11 2:1001793a090d 41 bits[0] = a;
feb11 2:1001793a090d 42 }
feb11 2:1001793a090d 43
feb11 0:9d554894785b 44 BigInt::BigInt(const BigInt &a):
feb11 0:9d554894785b 45 size(a.size)
feb11 0:9d554894785b 46 {
feb11 0:9d554894785b 47 uint32_t l = num(size);
feb11 0:9d554894785b 48 bits = new uint32_t[l];
feb11 0:9d554894785b 49 for(int i = 0; i < l; ++i)
feb11 0:9d554894785b 50 bits[i] = a.bits[i];
feb11 0:9d554894785b 51 }
feb11 0:9d554894785b 52
feb11 0:9d554894785b 53
feb11 0:9d554894785b 54 BigInt::~BigInt()
feb11 0:9d554894785b 55 {
feb11 10:116e201f7d89 56 if(size)
feb11 9:3c191fa04f6e 57 {
feb11 0:9d554894785b 58 delete[] bits;
feb11 9:3c191fa04f6e 59 }
feb11 0:9d554894785b 60 }
feb11 0:9d554894785b 61
feb11 0:9d554894785b 62 BigInt& BigInt::operator=(const BigInt& a)
feb11 0:9d554894785b 63 {
feb11 0:9d554894785b 64 size = a.size;
feb11 0:9d554894785b 65 uint32_t l = num(size);
feb11 0:9d554894785b 66 if(bits)
feb11 0:9d554894785b 67 delete[] bits;
feb11 0:9d554894785b 68 bits = new uint32_t[l];
feb11 0:9d554894785b 69 for(int i = 0; i < l; ++i)
feb11 0:9d554894785b 70 bits[i] = a.bits[i];
feb11 0:9d554894785b 71 return *this;
feb11 0:9d554894785b 72 }
feb11 0:9d554894785b 73
feb11 13:d0b4d7cfeb98 74 void BigInt::importData(uint8_t *data, uint32_t length)
feb11 0:9d554894785b 75 {
feb11 0:9d554894785b 76 size = length;
feb11 0:9d554894785b 77 size_t l = size/4;
feb11 0:9d554894785b 78 if(size % 4 != 0)
feb11 0:9d554894785b 79 l++;
feb11 0:9d554894785b 80 if(bits)
feb11 0:9d554894785b 81 delete[] bits;
feb11 0:9d554894785b 82 bits = new uint32_t[l];
feb11 0:9d554894785b 83 memset(bits, 0, sizeof(uint32_t)*l);
feb11 4:773aed3156c5 84 for(int i = length-1; i >=0; --i)
feb11 0:9d554894785b 85 bits[i/4] |= data[i] << ((i%4)*8);
feb11 18:4549ca354fdb 86
feb11 18:4549ca354fdb 87 trim();
feb11 0:9d554894785b 88 }
feb11 0:9d554894785b 89
feb11 13:d0b4d7cfeb98 90 void BigInt::exportData(uint8_t *data, uint32_t length)
feb11 13:d0b4d7cfeb98 91 {
feb11 13:d0b4d7cfeb98 92 assert(isValid() && data != 0);
feb11 13:d0b4d7cfeb98 93
feb11 14:5a1852dac7f7 94 if(length < size)
feb11 14:5a1852dac7f7 95 return;
feb11 14:5a1852dac7f7 96 uint32_t offset = length-size;
feb11 14:5a1852dac7f7 97 memset(data, 0, offset);
feb11 14:5a1852dac7f7 98 for(int i = size-1; i >= 0; --i)
feb11 14:5a1852dac7f7 99 data[offset+size-1-i] = bits[i/4] >> ((i%4)*8);
feb11 13:d0b4d7cfeb98 100 }
feb11 13:d0b4d7cfeb98 101
feb11 0:9d554894785b 102 BigInt operator+(const BigInt &a, const BigInt& b)
feb11 0:9d554894785b 103 {
feb11 9:3c191fa04f6e 104 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 105
feb11 0:9d554894785b 106 BigInt result;
feb11 9:3c191fa04f6e 107
feb11 20:d747159d77c4 108 result.size = std::max(a.size, b.size) + 1;
feb11 20:d747159d77c4 109 size_t l = num(result.size);
feb11 0:9d554894785b 110 result.bits = new uint32_t[l];
feb11 0:9d554894785b 111 memset(result.bits, 0, sizeof(uint32_t)*l);
feb11 0:9d554894785b 112 uint32_t al = num(a.size);
feb11 0:9d554894785b 113 uint32_t bl = num(b.size);
feb11 0:9d554894785b 114 uint32_t carry = 0;
feb11 0:9d554894785b 115 for(int i = 0; i < l; ++i)
feb11 0:9d554894785b 116 {
feb11 0:9d554894785b 117 uint32_t tmpA = 0, tmpB = 0;
feb11 0:9d554894785b 118 if(i < al)
feb11 0:9d554894785b 119 tmpA = a.bits[i];
feb11 0:9d554894785b 120 if(i < bl)
feb11 0:9d554894785b 121 tmpB = b.bits[i];
feb11 0:9d554894785b 122 result.bits[i] = tmpA + tmpB + carry;
feb11 10:116e201f7d89 123 carry = result.bits[i] < std::max(tmpA, tmpB);
feb11 0:9d554894785b 124 }
feb11 20:d747159d77c4 125
feb11 20:d747159d77c4 126 result.trim();
feb11 20:d747159d77c4 127
feb11 0:9d554894785b 128 return result;
feb11 0:9d554894785b 129 }
feb11 0:9d554894785b 130
feb11 0:9d554894785b 131 BigInt& BigInt::operator+=(const BigInt &b)
feb11 0:9d554894785b 132 {
feb11 0:9d554894785b 133 return (*this = (*this) + b);
feb11 0:9d554894785b 134 }
feb11 0:9d554894785b 135
feb11 0:9d554894785b 136 BigInt& BigInt::operator++()
feb11 0:9d554894785b 137 {
feb11 3:3fa3ceb0c69d 138 return (*this += 1);
feb11 0:9d554894785b 139 }
feb11 0:9d554894785b 140
feb11 0:9d554894785b 141 BigInt BigInt::operator++(int)
feb11 0:9d554894785b 142 {
feb11 0:9d554894785b 143 BigInt t = *this;
feb11 3:3fa3ceb0c69d 144 *this += 1;
feb11 0:9d554894785b 145 return t;
feb11 0:9d554894785b 146 }
feb11 0:9d554894785b 147
feb11 0:9d554894785b 148 // a - b, if b >= a, returns 0
feb11 0:9d554894785b 149 // No negative number allowed
feb11 20:d747159d77c4 150 BigInt operator-(const BigInt& a, const BigInt& b)
feb11 0:9d554894785b 151 {
feb11 9:3c191fa04f6e 152 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 153
feb11 20:d747159d77c4 154 if(b >= a)
feb11 20:d747159d77c4 155 return 0;
feb11 0:9d554894785b 156
feb11 20:d747159d77c4 157 BigInt result;
feb11 20:d747159d77c4 158 result.size = a.size;
feb11 20:d747159d77c4 159 uint32_t l = num(a.size);
feb11 20:d747159d77c4 160 result.bits = new uint32_t[l];
feb11 20:d747159d77c4 161 memset(result.bits, 0, sizeof(uint32_t)*l);
feb11 20:d747159d77c4 162 uint32_t bl = num(b.size);
feb11 20:d747159d77c4 163 uint8_t borrow = 0;
feb11 20:d747159d77c4 164 for(uint32_t i = 0; i < l; ++i)
feb11 0:9d554894785b 165 {
feb11 20:d747159d77c4 166 uint32_t tmpA = a.bits[i], tmpB = 0;
feb11 20:d747159d77c4 167 if(i < bl)
feb11 20:d747159d77c4 168 tmpB = b.bits[i];
feb11 20:d747159d77c4 169
feb11 20:d747159d77c4 170 if(borrow)
feb11 0:9d554894785b 171 {
feb11 20:d747159d77c4 172 if(tmpA == 0)
feb11 20:d747159d77c4 173 tmpA = 0xFFFFFFFF;
feb11 0:9d554894785b 174 else
feb11 0:9d554894785b 175 {
feb11 20:d747159d77c4 176 --tmpA;
feb11 20:d747159d77c4 177 borrow = 0;
feb11 0:9d554894785b 178 }
feb11 0:9d554894785b 179 }
feb11 20:d747159d77c4 180 if(tmpA >= tmpB)
feb11 20:d747159d77c4 181 result.bits[i] = tmpA - tmpB;
feb11 20:d747159d77c4 182 else
feb11 20:d747159d77c4 183 {
feb11 20:d747159d77c4 184 result.bits[i] = 0xFFFFFFFF - tmpB;
feb11 20:d747159d77c4 185 result.bits[i] += tmpA + 1;
feb11 20:d747159d77c4 186 borrow = 1;
feb11 20:d747159d77c4 187 }
feb11 20:d747159d77c4 188 }
feb11 20:d747159d77c4 189 result.trim();
feb11 0:9d554894785b 190
feb11 20:d747159d77c4 191 return result;
feb11 0:9d554894785b 192 }
feb11 0:9d554894785b 193
feb11 0:9d554894785b 194 BigInt& BigInt::operator-=(const BigInt &b)
feb11 0:9d554894785b 195 {
feb11 0:9d554894785b 196 return (*this = (*this) - b);
feb11 0:9d554894785b 197 }
feb11 0:9d554894785b 198
feb11 0:9d554894785b 199 BigInt& BigInt::operator--()
feb11 0:9d554894785b 200 {
feb11 3:3fa3ceb0c69d 201 return (*this -= 1);
feb11 0:9d554894785b 202 }
feb11 0:9d554894785b 203
feb11 0:9d554894785b 204 BigInt BigInt::operator--(int)
feb11 0:9d554894785b 205 {
feb11 0:9d554894785b 206 BigInt t = *this;
feb11 3:3fa3ceb0c69d 207 *this -= 1;
feb11 0:9d554894785b 208 return t;
feb11 0:9d554894785b 209 }
feb11 3:3fa3ceb0c69d 210
feb11 1:00f2c40d46ed 211 BigInt operator*(const BigInt &a, const BigInt& b)
feb11 1:00f2c40d46ed 212 {
feb11 9:3c191fa04f6e 213 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 214
feb11 1:00f2c40d46ed 215 // if a == 0 or b == 0 then result = 0
feb11 1:00f2c40d46ed 216 if(!a || !b)
feb11 12:a436f15b58b6 217 return 0;
feb11 1:00f2c40d46ed 218
feb11 1:00f2c40d46ed 219 // if a == 1, then result = b
feb11 3:3fa3ceb0c69d 220 if(a == 1)
feb11 12:a436f15b58b6 221 return b;
feb11 1:00f2c40d46ed 222
feb11 1:00f2c40d46ed 223 // if b == 1, then result = a
feb11 3:3fa3ceb0c69d 224 if(b == 1)
feb11 12:a436f15b58b6 225 return a;
feb11 12:a436f15b58b6 226
feb11 12:a436f15b58b6 227 BigInt result;
feb11 4:773aed3156c5 228 result.size = a.size + b.size;
feb11 4:773aed3156c5 229 result.bits = new uint32_t[num(result.size)];
feb11 12:a436f15b58b6 230 memset(result.bits, 0, sizeof(uint32_t)*num(result.size));
feb11 11:2f16a220ebbb 231 for(int i = 0; i < num(a.size); ++i)
feb11 4:773aed3156c5 232 {
feb11 11:2f16a220ebbb 233 uint64_t carry = 0;
feb11 11:2f16a220ebbb 234 for(int j = 0; j < num(b.size); ++j)
feb11 11:2f16a220ebbb 235 {
feb11 11:2f16a220ebbb 236 uint64_t tmp = (uint64_t)a.bits[i] * (uint64_t)b.bits[j] + carry;
feb11 12:a436f15b58b6 237 uint32_t t = result.bits[i+j];
feb11 11:2f16a220ebbb 238 result.bits[i+j] += tmp;
feb11 12:a436f15b58b6 239 carry = tmp >> 32;
feb11 12:a436f15b58b6 240 if(t > result.bits[i+j])
feb11 12:a436f15b58b6 241 ++carry;
feb11 11:2f16a220ebbb 242 }
feb11 11:2f16a220ebbb 243 if(carry != 0)
feb11 11:2f16a220ebbb 244 result.bits[i+num(b.size)] += carry;
feb11 4:773aed3156c5 245 }
feb11 4:773aed3156c5 246
feb11 9:3c191fa04f6e 247 result.trim();
feb11 1:00f2c40d46ed 248
feb11 1:00f2c40d46ed 249 return result;
feb11 1:00f2c40d46ed 250 }
feb11 1:00f2c40d46ed 251
feb11 1:00f2c40d46ed 252 BigInt& BigInt::operator*=(const BigInt &b)
feb11 1:00f2c40d46ed 253 {
feb11 1:00f2c40d46ed 254 return (*this = (*this) * b);
feb11 1:00f2c40d46ed 255 }
feb11 1:00f2c40d46ed 256
feb11 10:116e201f7d89 257
feb11 11:2f16a220ebbb 258 BigInt operator/(const BigInt &a, const BigInt &b)
feb11 10:116e201f7d89 259 {
feb11 10:116e201f7d89 260 assert(a.isValid() && b.isValid() && b != 0);
feb11 15:85a6bd4539eb 261
feb11 10:116e201f7d89 262 if(b == 1)
feb11 10:116e201f7d89 263 return a;
feb11 10:116e201f7d89 264 if(a < b)
feb11 10:116e201f7d89 265 return 0;
feb11 10:116e201f7d89 266 if(a == b)
feb11 10:116e201f7d89 267 return 1;
feb11 11:2f16a220ebbb 268 BigInt u = a;
feb11 20:d747159d77c4 269 const uint32_t m = a.numBits() - b.numBits();
feb11 20:d747159d77c4 270
feb11 15:85a6bd4539eb 271 BigInt q;
feb11 20:d747159d77c4 272 q.size = m/8 + 1;
feb11 15:85a6bd4539eb 273 q.bits = new uint32_t[num(q.size)];
feb11 15:85a6bd4539eb 274 memset(q.bits, 0, num(q.size)*sizeof(uint32_t));
feb11 12:a436f15b58b6 275 BigInt tmp = b;
feb11 12:a436f15b58b6 276 tmp <<= m;
feb11 10:116e201f7d89 277 for(int j = m; j >= 0; --j)
feb11 10:116e201f7d89 278 {
feb11 11:2f16a220ebbb 279 if(tmp <= u)
feb11 20:d747159d77c4 280 {
feb11 11:2f16a220ebbb 281 u -= tmp;
feb11 15:85a6bd4539eb 282 q.bits[j/32] |= BITS[j%32];
feb11 20:d747159d77c4 283 }
feb11 10:116e201f7d89 284 tmp >>= 1;
feb11 10:116e201f7d89 285 }
feb11 11:2f16a220ebbb 286 q.trim();
feb11 20:d747159d77c4 287
feb11 11:2f16a220ebbb 288 return q;
feb11 10:116e201f7d89 289 }
feb11 10:116e201f7d89 290
feb11 10:116e201f7d89 291 BigInt& BigInt::operator/=(const BigInt &b)
feb11 10:116e201f7d89 292 {
feb11 10:116e201f7d89 293 return (*this = (*this) / b);
feb11 10:116e201f7d89 294 }
feb11 10:116e201f7d89 295
feb11 1:00f2c40d46ed 296 BigInt operator>>(const BigInt &a, const uint32_t m)
feb11 1:00f2c40d46ed 297 {
feb11 9:3c191fa04f6e 298 assert(a.isValid());
feb11 9:3c191fa04f6e 299
feb11 12:a436f15b58b6 300 if(m == 0)
feb11 12:a436f15b58b6 301 return a;
feb11 12:a436f15b58b6 302 if(m/8 >= a.size)
feb11 12:a436f15b58b6 303 return 0;
feb11 12:a436f15b58b6 304
feb11 1:00f2c40d46ed 305 BigInt result;
feb11 1:00f2c40d46ed 306 result.size = a.size - m/8;
feb11 1:00f2c40d46ed 307 result.bits = new uint32_t[num(result.size)];
feb11 20:d747159d77c4 308 memset(result.bits, 0, sizeof(uint32_t)*num(result.size));
feb11 1:00f2c40d46ed 309 uint8_t s = m%32;
feb11 1:00f2c40d46ed 310 for(uint32_t i = 0; i < num(result.size); ++i)
feb11 1:00f2c40d46ed 311 {
feb11 1:00f2c40d46ed 312 if(m/32+i+1 < num(a.size))
feb11 1:00f2c40d46ed 313 result.bits[i] = (a.bits[m/32+i+1] << (32-s)) | (a.bits[m/32+i] >> s);
feb11 1:00f2c40d46ed 314 else
feb11 1:00f2c40d46ed 315 result.bits[i] = (a.bits[m/32+i] >> s);
feb11 1:00f2c40d46ed 316 }
feb11 1:00f2c40d46ed 317
feb11 10:116e201f7d89 318 result.trim();
feb11 10:116e201f7d89 319
feb11 1:00f2c40d46ed 320 return result;
feb11 1:00f2c40d46ed 321 }
feb11 1:00f2c40d46ed 322
feb11 1:00f2c40d46ed 323 BigInt& BigInt::operator>>=(const uint32_t m)
feb11 1:00f2c40d46ed 324 {
feb11 20:d747159d77c4 325 return (*this = (*this >> m));
feb11 1:00f2c40d46ed 326 }
feb11 1:00f2c40d46ed 327
feb11 20:d747159d77c4 328 BigInt operator<<(const BigInt& a, const uint32_t m)
feb11 1:00f2c40d46ed 329 {
feb11 9:3c191fa04f6e 330 assert(a.isValid());
feb11 9:3c191fa04f6e 331
feb11 1:00f2c40d46ed 332 BigInt result;
feb11 9:3c191fa04f6e 333
feb11 1:00f2c40d46ed 334 if(m == 0)
feb11 1:00f2c40d46ed 335 return result = a;
feb11 1:00f2c40d46ed 336
feb11 1:00f2c40d46ed 337 result.size = m/8 + a.size;
feb11 12:a436f15b58b6 338 if((m%32)%8 != 0)
feb11 1:00f2c40d46ed 339 ++result.size;
feb11 1:00f2c40d46ed 340 uint32_t l = num(result.size);
feb11 1:00f2c40d46ed 341 result.bits = new uint32_t[l];
feb11 1:00f2c40d46ed 342 memset(result.bits, 0, sizeof(uint32_t)*l);
feb11 1:00f2c40d46ed 343 uint32_t s = m % 32;
feb11 20:d747159d77c4 344 result.bits[m/32] = a.bits[0] << s;
feb11 20:d747159d77c4 345 for(uint32_t i = 1; i < num(a.size); ++i)
feb11 20:d747159d77c4 346 result.bits[m/32+i] = (a.bits[i] << s) | (a.bits[i-1] >> (32-s));
feb11 20:d747159d77c4 347 if(s != 0)
feb11 20:d747159d77c4 348 result.bits[num(result.size)-1] = a.bits[num(a.size)-1] >> (32-s);
feb11 1:00f2c40d46ed 349
feb11 12:a436f15b58b6 350 result.trim();
feb11 1:00f2c40d46ed 351
feb11 1:00f2c40d46ed 352 return result;
feb11 1:00f2c40d46ed 353 }
feb11 1:00f2c40d46ed 354
feb11 1:00f2c40d46ed 355 BigInt& BigInt::operator<<=(const uint32_t m)
feb11 1:00f2c40d46ed 356 {
feb11 1:00f2c40d46ed 357 return (*this = *this << m);
feb11 1:00f2c40d46ed 358 }
feb11 0:9d554894785b 359
feb11 5:beeb31f340a7 360 BigInt operator%(const BigInt &a, const BigInt &b)
feb11 5:beeb31f340a7 361 {
feb11 10:116e201f7d89 362 assert(a.isValid() && b.isValid() && b > 0);
feb11 20:d747159d77c4 363
feb11 12:a436f15b58b6 364 return a - (a/b)*b;
feb11 5:beeb31f340a7 365 }
feb11 5:beeb31f340a7 366
feb11 5:beeb31f340a7 367 BigInt& BigInt::operator%=(const BigInt &a)
feb11 5:beeb31f340a7 368 {
feb11 5:beeb31f340a7 369 return (*this = *this % a);
feb11 5:beeb31f340a7 370 }
feb11 5:beeb31f340a7 371
feb11 0:9d554894785b 372 bool operator==(const BigInt &a, const BigInt &b)
feb11 0:9d554894785b 373 {
feb11 9:3c191fa04f6e 374 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 375
feb11 0:9d554894785b 376 if(a.size != b.size)
feb11 0:9d554894785b 377 return false;
feb11 0:9d554894785b 378
feb11 0:9d554894785b 379 uint32_t l = num(a.size);
feb11 0:9d554894785b 380 for(int i = 0; i < l; ++i)
feb11 0:9d554894785b 381 if(a.bits[i] != b.bits[i])
feb11 0:9d554894785b 382 return false;
feb11 0:9d554894785b 383 return true;
feb11 0:9d554894785b 384 }
feb11 0:9d554894785b 385
feb11 0:9d554894785b 386 bool operator!=(const BigInt &a, const BigInt &b)
feb11 0:9d554894785b 387 {
feb11 0:9d554894785b 388 return ! (a==b);
feb11 0:9d554894785b 389 }
feb11 0:9d554894785b 390
feb11 0:9d554894785b 391 bool operator<(const BigInt &a, const BigInt &b)
feb11 0:9d554894785b 392 {
feb11 9:3c191fa04f6e 393 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 394
feb11 0:9d554894785b 395 if(a.size < b.size)
feb11 0:9d554894785b 396 return true;
feb11 0:9d554894785b 397 if(a.size > b.size)
feb11 0:9d554894785b 398 return false;
feb11 0:9d554894785b 399 uint32_t l = num(a.size);
feb11 0:9d554894785b 400 for(int i = l-1; i >= 0; --i)
feb11 12:a436f15b58b6 401 {
feb11 0:9d554894785b 402 if(a.bits[i] < b.bits[i])
feb11 0:9d554894785b 403 return true;
feb11 12:a436f15b58b6 404 else if(a.bits[i] > b.bits[i])
feb11 12:a436f15b58b6 405 return false;
feb11 12:a436f15b58b6 406 }
feb11 0:9d554894785b 407 return false;
feb11 0:9d554894785b 408 }
feb11 0:9d554894785b 409
feb11 0:9d554894785b 410 bool operator<=(const BigInt &a, const BigInt &b)
feb11 0:9d554894785b 411 {
feb11 9:3c191fa04f6e 412 return !(a > b);
feb11 0:9d554894785b 413 }
feb11 0:9d554894785b 414
feb11 0:9d554894785b 415 bool operator>(const BigInt &a, const BigInt &b)
feb11 0:9d554894785b 416 {
feb11 9:3c191fa04f6e 417 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 418
feb11 0:9d554894785b 419 if(a.size > b.size)
feb11 0:9d554894785b 420 return true;
feb11 0:9d554894785b 421 if(a.size < b.size)
feb11 0:9d554894785b 422 return false;
feb11 0:9d554894785b 423 uint32_t l = num(a.size);
feb11 0:9d554894785b 424 for(int i = l-1; i >= 0; --i)
feb11 12:a436f15b58b6 425 {
feb11 0:9d554894785b 426 if(a.bits[i] > b.bits[i])
feb11 0:9d554894785b 427 return true;
feb11 12:a436f15b58b6 428 else if(a.bits[i] < b.bits[i])
feb11 12:a436f15b58b6 429 return false;
feb11 12:a436f15b58b6 430 }
feb11 0:9d554894785b 431 return false;
feb11 0:9d554894785b 432 }
feb11 0:9d554894785b 433
feb11 0:9d554894785b 434 bool operator>=(const BigInt &a, const BigInt &b)
feb11 0:9d554894785b 435 {
feb11 9:3c191fa04f6e 436 return !(a < b);
feb11 0:9d554894785b 437 }
feb11 0:9d554894785b 438
feb11 1:00f2c40d46ed 439 bool operator!(const BigInt &a)
feb11 0:9d554894785b 440 {
feb11 9:3c191fa04f6e 441 assert(a.isValid());
feb11 9:3c191fa04f6e 442
feb11 1:00f2c40d46ed 443 if(a.size != 1)
feb11 0:9d554894785b 444 return false;
feb11 1:00f2c40d46ed 445 return a.bits[0] == 0;
feb11 0:9d554894785b 446 }
feb11 0:9d554894785b 447
feb11 7:1aad58757705 448
feb11 7:1aad58757705 449 BigInt operator&(const BigInt &a, const BigInt &b)
feb11 7:1aad58757705 450 {
feb11 9:3c191fa04f6e 451 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 452
feb11 7:1aad58757705 453 BigInt result;
feb11 7:1aad58757705 454
feb11 7:1aad58757705 455 result.size = a.size < b.size ? a.size : b.size;
feb11 7:1aad58757705 456 uint32_t l = num(result.size);
feb11 7:1aad58757705 457 result.bits = new uint32_t[l];
feb11 7:1aad58757705 458 memset(result.bits, 0, l);
feb11 7:1aad58757705 459
feb11 7:1aad58757705 460 for(uint32_t i = 0; i < l; ++i)
feb11 7:1aad58757705 461 result.bits[i] = a.bits[i] & b.bits[i];
feb11 7:1aad58757705 462
feb11 9:3c191fa04f6e 463 result.trim();
feb11 7:1aad58757705 464
feb11 7:1aad58757705 465 return result;
feb11 7:1aad58757705 466 }
feb11 7:1aad58757705 467
feb11 7:1aad58757705 468 BigInt& BigInt::operator&=(const BigInt &a)
feb11 7:1aad58757705 469 {
feb11 7:1aad58757705 470 return (*this = *this & a);
feb11 7:1aad58757705 471 }
feb11 7:1aad58757705 472
feb11 7:1aad58757705 473 BigInt operator|(const BigInt &a, const BigInt &b)
feb11 7:1aad58757705 474 {
feb11 9:3c191fa04f6e 475 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 476
feb11 7:1aad58757705 477 BigInt result;
feb11 7:1aad58757705 478
feb11 7:1aad58757705 479 uint32_t na = num(a.size);
feb11 7:1aad58757705 480 uint32_t nb = num(b.size);
feb11 10:116e201f7d89 481 uint32_t l = std::max(na,nb);
feb11 10:116e201f7d89 482 result.size = std::max(a.size, b.size);
feb11 7:1aad58757705 483 result.bits = new uint32_t[l];
feb11 7:1aad58757705 484 memset(result.bits, 0, l);
feb11 7:1aad58757705 485
feb11 7:1aad58757705 486 for(uint32_t i = 0; i < l; ++i)
feb11 7:1aad58757705 487 {
feb11 7:1aad58757705 488 if(i < na && i < nb)
feb11 7:1aad58757705 489 result.bits[i] = a.bits[i] | b.bits[i];
feb11 7:1aad58757705 490 else if(i < na)
feb11 7:1aad58757705 491 result.bits[i] = a.bits[i];
feb11 7:1aad58757705 492 else
feb11 7:1aad58757705 493 result.bits[i] = b.bits[i];
feb11 7:1aad58757705 494 }
feb11 7:1aad58757705 495
feb11 20:d747159d77c4 496 result.trim();
feb11 20:d747159d77c4 497
feb11 7:1aad58757705 498 return result;
feb11 7:1aad58757705 499 }
feb11 7:1aad58757705 500
feb11 7:1aad58757705 501 BigInt& BigInt::operator|=(const BigInt &a)
feb11 7:1aad58757705 502 {
feb11 7:1aad58757705 503 return (*this = *this | a);
feb11 7:1aad58757705 504 }
feb11 8:2a361f1b41da 505
feb11 8:2a361f1b41da 506 BigInt operator^(const BigInt &a, const BigInt &b)
feb11 8:2a361f1b41da 507 {
feb11 9:3c191fa04f6e 508 assert(a.isValid() && b.isValid());
feb11 9:3c191fa04f6e 509
feb11 8:2a361f1b41da 510 BigInt result;
feb11 8:2a361f1b41da 511
feb11 8:2a361f1b41da 512 uint32_t na = num(a.size);
feb11 8:2a361f1b41da 513 uint32_t nb = num(b.size);
feb11 10:116e201f7d89 514 uint32_t l = std::max(na,nb);
feb11 10:116e201f7d89 515 result.size = std::max(a.size, b.size);
feb11 8:2a361f1b41da 516 result.bits = new uint32_t[l];
feb11 8:2a361f1b41da 517 memset(result.bits, 0, l);
feb11 7:1aad58757705 518
feb11 8:2a361f1b41da 519 for(uint32_t i = 0; i < l; ++i)
feb11 8:2a361f1b41da 520 {
feb11 8:2a361f1b41da 521 if(i < na && i < nb)
feb11 8:2a361f1b41da 522 result.bits[i] = a.bits[i] ^ b.bits[i];
feb11 8:2a361f1b41da 523 else if(i < na)
feb11 8:2a361f1b41da 524 result.bits[i] = a.bits[i];
feb11 8:2a361f1b41da 525 else
feb11 8:2a361f1b41da 526 result.bits[i] = b.bits[i];
feb11 8:2a361f1b41da 527 }
feb11 8:2a361f1b41da 528
feb11 9:3c191fa04f6e 529 result.trim();
feb11 9:3c191fa04f6e 530
feb11 8:2a361f1b41da 531 return result;
feb11 8:2a361f1b41da 532 }
feb11 8:2a361f1b41da 533
feb11 8:2a361f1b41da 534 BigInt& BigInt::operator^=(const BigInt &a)
feb11 8:2a361f1b41da 535 {
feb11 8:2a361f1b41da 536 return (*this = *this ^ a);
feb11 8:2a361f1b41da 537 }
feb11 9:3c191fa04f6e 538
feb11 19:412b822df7bf 539 // Perform one step : (a * b) / r mod m
feb11 10:116e201f7d89 540 BigInt montgomeryStep(const BigInt &a, const BigInt &b, const BigInt &m, uint32_t r)
feb11 10:116e201f7d89 541 {
feb11 10:116e201f7d89 542 BigInt result = 0;
feb11 16:d70cf164440c 543 uint32_t j = 0;
feb11 10:116e201f7d89 544 while(r > 0)
feb11 10:116e201f7d89 545 {
feb11 16:d70cf164440c 546 if(a.bits[j/32] & BITS[j%32])
feb11 20:d747159d77c4 547 result += b;
feb11 10:116e201f7d89 548
feb11 20:d747159d77c4 549 if(result.bits[0] & BITS[0])
feb11 10:116e201f7d89 550 result += m;
feb11 16:d70cf164440c 551
feb11 16:d70cf164440c 552 ++j;
feb11 10:116e201f7d89 553 --r;
feb11 20:d747159d77c4 554 result >>= 1;
feb11 10:116e201f7d89 555 }
feb11 19:412b822df7bf 556
feb11 19:412b822df7bf 557 if(result >= m)
feb11 19:412b822df7bf 558 return result - m;
feb11 20:d747159d77c4 559
feb11 10:116e201f7d89 560 return result;
feb11 10:116e201f7d89 561 }
feb11 10:116e201f7d89 562
feb11 10:116e201f7d89 563 // Implementation using Montgomery algorithm
feb11 9:3c191fa04f6e 564 BigInt modPow(const BigInt &a, const BigInt &expn, const BigInt &modulus)
feb11 9:3c191fa04f6e 565 {
feb11 19:412b822df7bf 566 assert(a.isValid() && expn.isValid() && modulus.isValid() && modulus != 0);
feb11 20:d747159d77c4 567
feb11 20:d747159d77c4 568 if(modulus == 1)
feb11 20:d747159d77c4 569 return 0;
feb11 19:412b822df7bf 570 if(expn == 0)
feb11 19:412b822df7bf 571 return 1;
feb11 19:412b822df7bf 572 if(a == 1)
feb11 19:412b822df7bf 573 return 1;
feb11 20:d747159d77c4 574 if(expn == 1)
feb11 20:d747159d77c4 575 return a % modulus;
feb11 9:3c191fa04f6e 576
feb11 20:d747159d77c4 577 const uint32_t r = 8*modulus.size;
feb11 10:116e201f7d89 578 // convert a in montgomery world
feb11 17:9811d859dc83 579 BigInt montA = (a << r) % modulus;
feb11 20:d747159d77c4 580
feb11 16:d70cf164440c 581 BigInt tmp;
feb11 20:d747159d77c4 582 if(expn.bits[0] & BITS[0])
feb11 17:9811d859dc83 583 tmp = montA;
feb11 17:9811d859dc83 584
feb11 20:d747159d77c4 585 const uint32_t n = expn.numBits();
feb11 16:d70cf164440c 586 uint32_t j = 1;
feb11 20:d747159d77c4 587 while(j <= n)
feb11 9:3c191fa04f6e 588 {
feb11 16:d70cf164440c 589 montA = montgomeryStep(montA, montA, modulus, r);
feb11 16:d70cf164440c 590
feb11 16:d70cf164440c 591 if(expn.bits[j/32] & BITS[j%32])
feb11 16:d70cf164440c 592 {
feb11 16:d70cf164440c 593 if(tmp.isValid())
feb11 19:412b822df7bf 594 tmp = montgomeryStep(tmp, montA, modulus, r);
feb11 16:d70cf164440c 595 else
feb11 16:d70cf164440c 596 tmp = montA;
feb11 16:d70cf164440c 597 }
feb11 16:d70cf164440c 598 ++j;
feb11 9:3c191fa04f6e 599 }
feb11 19:412b822df7bf 600
feb11 20:d747159d77c4 601 // convert tmp to normal world
feb11 10:116e201f7d89 602 return montgomeryStep(tmp, 1, modulus, r);
feb11 9:3c191fa04f6e 603 }
feb11 9:3c191fa04f6e 604
feb11 9:3c191fa04f6e 605 bool BigInt::isValid() const
feb11 9:3c191fa04f6e 606 {
feb11 9:3c191fa04f6e 607 return size != 0 && bits != 0;
feb11 9:3c191fa04f6e 608 }
feb11 9:3c191fa04f6e 609
feb11 11:2f16a220ebbb 610 void BigInt::print() const
feb11 0:9d554894785b 611 {
feb11 11:2f16a220ebbb 612 assert(isValid());
feb11 11:2f16a220ebbb 613
feb11 0:9d554894785b 614 printf("size: %d bytes\n", size);
feb11 0:9d554894785b 615 uint32_t n = num(size);
feb11 0:9d554894785b 616 for(int i = n-1; i >= 0; --i)
feb11 0:9d554894785b 617 {
feb11 1:00f2c40d46ed 618 printf("%08x ", bits[i]);
feb11 0:9d554894785b 619 }
feb11 0:9d554894785b 620 printf("\n");
feb11 0:9d554894785b 621 }
feb11 9:3c191fa04f6e 622
feb11 9:3c191fa04f6e 623 void BigInt::trim()
feb11 9:3c191fa04f6e 624 {
feb11 20:d747159d77c4 625 assert(isValid());
feb11 20:d747159d77c4 626
feb11 9:3c191fa04f6e 627 uint8_t *tmp = (uint8_t*)bits;
feb11 9:3c191fa04f6e 628 uint32_t newSize = size;
feb11 20:d747159d77c4 629 while(newSize > 0 && tmp[newSize-1] == 0)
feb11 9:3c191fa04f6e 630 newSize--;
feb11 10:116e201f7d89 631 if(newSize == 0)
feb11 10:116e201f7d89 632 newSize = 1;
feb11 9:3c191fa04f6e 633 if(num(newSize) < num(size))
feb11 10:116e201f7d89 634 {
feb11 20:d747159d77c4 635 uint32_t *tmp = new uint32_t[num(size)];
feb11 20:d747159d77c4 636 memcpy(tmp, bits, num(size)*sizeof(uint32_t));
feb11 20:d747159d77c4 637 delete[] bits;
feb11 20:d747159d77c4 638 bits = new uint32_t[num(newSize)];
feb11 20:d747159d77c4 639 memset(bits, 0, sizeof(uint32_t)*num(newSize));
feb11 20:d747159d77c4 640 memcpy(bits, tmp, newSize);
feb11 20:d747159d77c4 641 delete[] tmp;
feb11 10:116e201f7d89 642 }
feb11 9:3c191fa04f6e 643 size = newSize;
feb11 9:3c191fa04f6e 644 }
feb11 9:3c191fa04f6e 645
feb11 11:2f16a220ebbb 646 uint32_t BigInt::numBits() const
feb11 10:116e201f7d89 647 {
feb11 10:116e201f7d89 648 assert(isValid());
feb11 12:a436f15b58b6 649
feb11 10:116e201f7d89 650 uint32_t n = (size-1)*8;
feb11 11:2f16a220ebbb 651 uint8_t a = bits[num(size)-1] >> ((size-1)%4)*8;
feb11 10:116e201f7d89 652 uint8_t tmp2 = 8;
feb11 11:2f16a220ebbb 653 while(!(a & 0x80))
feb11 10:116e201f7d89 654 {
feb11 11:2f16a220ebbb 655 a <<= 1;
feb11 10:116e201f7d89 656 --tmp2;
feb11 10:116e201f7d89 657 }
feb11 10:116e201f7d89 658 n += tmp2;
feb11 10:116e201f7d89 659
feb11 10:116e201f7d89 660 return n;
feb11 10:116e201f7d89 661 }