Mummify/rsa.js at master · charmaine/Mummify · GitHub

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
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
/*  RSA simple                                                            (c) Bob van Luijt 2015  */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */

'use strict';

/**
 * RSA hash function reference implementation.
 *
 * @namespace
 */
var RSA = {};

/**
 * Generates an RSA hash
 * https://en.wikipedia.org/wiki/RSA_(cryptosystem)#A_working_example
 *
 * @returns {array} Result of RSA generation
 */
RSA.generate = function(){
    /**
     * Calculate modular multiplicative inverse.
     * https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
     * Function based on PHP variant on http://rosettacode.org/wiki/Modular_inverse
     *
     * @param   {a} int
     * @param   {n} int
     * @returns {int} Result of modular multiplicative inverse.
     */
    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;
    }

    /**
     * Generates a random prime
     *
     * @param   {min} int, minimal value
     * @param   {max} int, maximal value
     * @returns {int} a random generated prime
     */
    function random_prime(min, max){
        var p = Math.floor(Math.random() * ((max - 1) - min + 1)) + min;
        if(bigInt(p).isPrime()===true){
            return p;
        } else {
            return random_prime(min, max);
        }
    }

    // generate values
    var p = random_prime(1, 255), // 8 bit
        q = random_prime(1, 255), // 8 bit
        n = p * q,
        t = (p - 1) * (q - 1), // totient as φ(n) = (p − 1)(q − 1)
        d = random_prime(1, t),
        e = modular_multiplicative_inverse(d, t);
    return {
    	n: n, // public key (part I)
        e: e, // public key (part II)
        d: d  // private key
    };
};

/**
 * Encrypt
 * Uses BigInteger.js https://peterolson.github.com/BigInteger.js
 *
 * @param   {m} int, the 'message' to be encoded
 * @param   {n} int, n value returned from generate_rsa() aka public key (part I)
 * @param   {e} int, e value returned from generate_rsa() aka public key (part II)
 * @returns {int} encrypted hash
 */
RSA.encrypt = function(m, n, e){
	return bigInt(m).pow(e).mod(n);
};

/**
 * Decrypt
 * Uses BigInteger.js https://peterolson.github.com/BigInteger.js
 *
 * @param   {mEnc} int, the 'message' to be decoded (encoded with RSA_encrypt())
 * @param   {d} int, d value returned from generate_rsa() aka private key
 * @param   {n} int, n value returned from generate_rsa() aka public key (part I)
 * @returns {int} decrypted hash
 */
RSA.decrypt = function(mEnc, d, n){
	return bigInt(mEnc).pow(d).mod(n);
};