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; }
Diff: BigInt.cpp
- Revision:
- 1:00f2c40d46ed
- Parent:
- 0:9d554894785b
- Child:
- 2:1001793a090d
--- a/BigInt.cpp Fri Sep 20 13:29:23 2013 +0000 +++ b/BigInt.cpp Fri Sep 20 15:45:22 2013 +0000 @@ -217,6 +217,106 @@ this->operator-=(a); return t; } +/* +BigInt operator*(const BigInt &a, const BigInt& b) +{ + BigInt result; + + // if a == 0 or b == 0 then result = 0 + if(!a || !b) + { + uint8_t tmp = 0; + result.import(&tmp, 1); + return result; + } + + uint8_t tmp = 1; + BigInt one; + one.import(&tmp, 1); + // if a == 1, then result = b + if(a == one) + return (result = b); + + // if b == 1, then result = a + if(b == one) + return (result = a); + + + + return result; +} + +BigInt& BigInt::operator*=(const BigInt &b) +{ + return (*this = (*this) * b); +} + +*/ +BigInt operator>>(const BigInt &a, const uint32_t m) +{ + BigInt result; + if(m == 0) + return result = a; + if(m/8 >= a.size) + { + uint8_t tmp = 0; + result.import(&tmp, 0); + return result; + } + + result.size = a.size - m/8; + result.bits = new uint32_t[num(result.size)]; + uint8_t s = m%32; + for(uint32_t i = 0; i < num(result.size); ++i) + { + if(m/32+i+1 < num(a.size)) + result.bits[i] = (a.bits[m/32+i+1] << (32-s)) | (a.bits[m/32+i] >> s); + else + result.bits[i] = (a.bits[m/32+i] >> s); + } + + + return result; +} + +BigInt& BigInt::operator>>=(const uint32_t m) +{ + return *this = *this >> m; +} + +BigInt operator<<(const BigInt &a, const uint32_t m) +{ + BigInt result; + + if(m == 0) + return result = a; + + result.size = m/8 + a.size; + uint32_t h = a.bits[num(a.size)-1]; + if((h << (m%32)) < h) + ++result.size; + uint32_t l = num(result.size); + result.bits = new uint32_t[l]; + memset(result.bits, 0, sizeof(uint32_t)*l); + uint32_t s = m % 32; + for(uint32_t i = 0; i < num(a.size); ++i) + { + if(i == 0) + result.bits[m/32+i] = a.bits[i] << s; + else + result.bits[m/32+i] = (a.bits[i] << s) | (a.bits[i-1] >> (32-s)); + } + if(a.bits[num(a.size)-1] << s < a.bits[num(a.size)-1]) + result.bits[num(result.size)-1] = a.bits[num(a.size)-1] >> (32-s); + + + return result; +} + +BigInt& BigInt::operator<<=(const uint32_t m) +{ + return (*this = *this << m); +} bool operator==(const BigInt &a, const BigInt &b) { @@ -271,11 +371,11 @@ return (a > b) || (a == b); } -bool BigInt::operator!() +bool operator!(const BigInt &a) { - if(size != 1) + if(a.size != 1) return false; - return bits[0] == 0; + return a.bits[0] == 0; } void BigInt::print() @@ -284,7 +384,7 @@ uint32_t n = num(size); for(int i = n-1; i >= 0; --i) { - printf("%08x", bits[i]); + printf("%08x ", bits[i]); } printf("\n"); }