Francois Berder / BigInt

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;
}

Files at this revision

API Documentation at this revision

Revision 3:3fa3ceb0c69d, committed 2013-09-20

Comitter:
feb11
Date:
Fri Sep 20 15:55:19 2013 +0000
Parent:
2:1001793a090d
Child:
4:773aed3156c5
Commit message:
simplified code

Changed in this revision

BigInt.cpp Show annotated file Show diff for this revision Revisions of this file
BigInt.h Show annotated file Show diff for this revision Revisions of this file 
--- a/BigInt.cpp	Fri Sep 20 15:50:25 2013 +0000
+++ b/BigInt.cpp	Fri Sep 20 15:55:19 2013 +0000
@@ -127,20 +127,13 @@
 
 BigInt& BigInt::operator++()
 {
-    uint8_t tmp = 1;
-    BigInt a;
-    a.import(&tmp, 1);
-    
-    return (*this += a);
+    return (*this += 1);
 }
 
 BigInt BigInt::operator++(int)
 {
     BigInt t = *this;
-    uint8_t tmp = 1;
-    BigInt a;
-    a.import(&tmp, 1);
-    this->operator+=(a);
+    *this += 1;
     return t;
 }
 
@@ -152,9 +145,7 @@
 
     if(b >= a)
     {
-        uint8_t tmp = 0;
-        result.import(&tmp, 1);
-        return result;
+        return result = 0;
     }
     else
     {
@@ -215,44 +206,30 @@
 
 BigInt& BigInt::operator--()
 {
-    uint8_t tmp = 1;
-    BigInt a;
-    a.import(&tmp, 1);
-    
-    return (*this -= a);
+    return (*this -= 1);
 }
 
 BigInt BigInt::operator--(int)
 {
     BigInt t = *this;
-    uint8_t tmp = 1;
-    BigInt a;
-    a.import(&tmp, 1);
-    this->operator-=(a);
+    *this -= 1;
     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;
-    }
+        return result = 0;
     
-    uint8_t tmp = 1;
-    BigInt one;
-    one.import(&tmp, 1);
     // if a == 1, then result = b
-    if(a == one)
+    if(a == 1)
         return (result = b);
     
     // if b == 1, then result = a
-    if(b == one)
+    if(b == 1)
         return (result = a);
         
         
@@ -265,18 +242,13 @@
     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;
-    }
+        return result = 0;
     
     result.size = a.size - m/8;
     result.bits = new uint32_t[num(result.size)];

--- a/BigInt.h	Fri Sep 20 15:50:25 2013 +0000
+++ b/BigInt.h	Fri Sep 20 15:55:19 2013 +0000
@@ -27,10 +27,10 @@
         BigInt operator--(int);
         
         
-        /* TODO
+        
         friend BigInt operator*(const BigInt &a, const BigInt& b);
         BigInt& operator*=(const BigInt &b);
-        
+        /*
         friend BigInt operator/(const BigInt &a, const BigInt& b);
         BigInt& operator/=(const BigInt &b);        
         */