Skip to content

Instantly share code, notes, and snippets.

@fb55
Created April 19, 2012 14:39
Show Gist options
  • Save fb55/2421370 to your computer and use it in GitHub Desktop.
Save fb55/2421370 to your computer and use it in GitHub Desktop.
RSA.js
(function(global){
var MathUtils = {
powermod: function powermod(num, exp, mod){
if(exp === 1) return num % mod;
if(exp & 1 === 1){ //odd
return (num * powermod(num, exp-1, mod)) % mod;
}
return Math.pow(powermod(num, exp/2, mod), 2) % mod;
},
lilFermat: function(num){
return MathUtils.powermod(3, num-1, num) === 1;
},
gcd: function ea(a, b){
if(a * b === 0) return 0;
if(a > b) return ea(b, a);
if(b % a === 0) return a;
return ea(b % a, a);
},
egcd: function eea(a, b){
if(b === 0) return [a, 1, 0];
var tmp = eea(b, a % b);
var ss = tmp[1],
ts = tmp[2];
return [tmp[0], ts, ss - Math.floor(a/b) * ts];
},
getRanPrime: function(len){
var num = Math.floor(Math.pow(10, len) * Math.random());
while(!MathUtils.lilFermat(num)) num++;
return num;
},
modinverse: function(a, b){
var arr = this.egcd(a, b);
var sum = arr[1]*a + arr[2]*b;
if(sum !== arr[0]) throw Error("Wrong EGCD: " + sum);
return arr[1];
}
};
function convertIntoArray(str){
return str.split("").map(function(a){
return a.charCodeAt(0);
});
}
function stringifyValues(vals){
return vals.map(function(a){
return String.fromCharCode(a);
}).join("");
}
function RSA(len){
if(!len) len = 4;
var p = MathUtils.getRanPrime(len), q = MathUtils.getRanPrime(len);
while(p === q) q = MathUtils.getRanPrime(len);
var m = this.N = p * q,
phi = (p - 1) * (q - 1);
do {
this.publicKey = MathUtils.getRanPrime(len);
}
while(MathUtils.gcd(this.publicKey, phi) !== 1);
this.privateKey = MathUtils.modinverse(this.publicKey, phi);
if(this.privateKey < 0) this.privateKey += phi;
}
RSA.prototype.encryptStr = function(values){
return encryptStr(values, this.publicKey, this.N);
};
RSA.prototype.encrypt = function(values){
return encrypt(values, this.publicKey, this.N);
};
RSA.prototype.decrypt = function(values){
return decrypt(values, this.privateKey, this.N);
};
function encryptStr(values, publicKey, n){
return stringifyValues(encrypt(values, publicKey, n));
}
function encrypt(values, publicKey, n){
if(typeof values === "string") values = convertIntoArray(values);
return values.map(function(a){
return MathUtils.powermod(a, publicKey, n);
});
}
function decrypt(values, privateKey, N){
if(typeof values === "string") values = convertIntoArray(values);
return stringifyValues(
values.map(function(a){
return MathUtils.powermod(a, privateKey, N);
})
);
}
RSA.encrypt = encrypt;
RSA.encryptStr = encryptStr;
RSA.decrypt = decrypt;
if(typeof module === "object" && "exports" in module){
module.exports = RSA;
}
else global.RSA = RSA;
})(typeof window === "object" ? window : this);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment