modular multiplicative inverse

modular_exponentiation.c

#include <msp430.h>

// memory efficient modular exponentiation 
//
// calculate c, where - (b^e) mod m = c
// b is the plaintext
// e is the secret key 
// m is phi(n) the totient of the public key, a number derived from the public key components

//
// (b^e) could be huge, thousands of digits, so we use this algorithm to calculate the value of c
// after performing 'e' routines.  In this case 13.

// this is a memory efficient encrypt and decrypt operations

unsigned int c = 1;
unsigned int b = 4;
unsigned int e = 13;
unsigned int e_prime = 0;
unsigned int m = 497;

int main(void) {
	WDTCTL = WDTPW | WDTHOLD;		// Stop watchdog timer
	while(e_prime < e){
		e_prime = e_prime + 1;
		c = c * b;
		c = c % m;
	}
	return 0;
}

modular_multiplicative_inverse.js

// used to calculate the private key 
// step 5 here - https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Key_generation
// the arguments are 'e' from step 4
// and the totient from step 3
// it returns the secret key

 function modular_multiplicative_inverse(a, n){
    	var t  = 0,
            nt = 1,
            r  = n,
            nr = a % n;
        if (n < 0){
        	n = -n;
        }
        if (a < 0){
        	a = n - (-a % n);
        }
    	while (nr !== 0) {
    		var quot= (r/nr) | 0;
    		var tmp = nt;  nt = t - quot*nt;  t = tmp;
    		    tmp = nr;  nr = r - quot*nr;  r = tmp;
    	}
    	if (r > 1) { return -1; }
    	if (t < 0) { t += n; }
    	return t;
    }