RSA (cryptosystem): Difference between revisions

→‎Code: use λ instead of φ, use BigInteger.js methods instead of custom modular inverse code, take desired key length as input, loop if key generation fails, use modPow() instead of pow().mod()
(consistently use λ(n) instead of φ(n), as most practical RSA implementations do, except for historical discussion (and the JS code, for now); also use \bmod and \pmod instead of ugly TeX hacks)
(→‎Code: use λ instead of φ, use BigInteger.js methods instead of custom modular inverse code, take desired key length as input, loop if key generation fails, use modPow() instead of pow().mod())
 
===Code===
A working example in JavaScript.<ref>{{cite webusing |url=[https://github.com/kubrickologypeterolson/Bitcoin-explained/blob/master/RSABigInteger.js |first=Bob |last=van Luijt| title=RSA example on Github }}</ref>BigInteger.js]. This code should not be used in production, as numbers<code>bigInt.randBetween()<code> generated by JavaScript'suses <code>Math.random()</code>, arewhich is not a [[Cryptographicallycryptographically secure pseudorandom number generator|cryptographically secure]].<ref>{{cite web|last1=Scholz|first1=Florian|last2=Shepherd|first2=Eric|title=Math.random()|url=https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/random|website=Mozilla Developer Network|accessdate=5 June 2016}}</ref>
 
<syntaxhighlight lang="javascript">
/**
* RSA hash function reference implementation.
* Uses BigInteger.js https://github.com/peterolson/BigInteger.js/tree/master
* Code originally based on https://github.com/kubrickology/Bitcoin-explained/blob/master/RSA.js
*
* @namespace
 
/**
* Generates ana k-bit RSA hashpublic/private key pai
* https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Code
*
* @returnsparam {arraykeysize} Resultint, bitlength of desired RSA generationmodulus n (should be even)
* @returns {array} Result of RSA generation (object with three bigInt members: n, e, d)
*/
RSA.generate = function (keysize) {
/**
* Generates a random k-bit prime greater than √2 × 2^(k-1)
* 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 {abits} int, bitlength of desired prime
* @param returns {nbigInt} inta random generated prime
* @returns {int} Result of modular multiplicative inverse.
*/
function modular_multiplicative_inverserandom_prime(a, nbits) {
var min = bigInt(6074001000).shiftLeft(bits-33); // min ≈ √2 × 2^(bits - 1)
var t = 0,
var max = bigInt.one.shiftLeft(bits).minus(1); nt // max = 2^(bits) - 1,
while (true) r = n;{
var p = bigInt.randBetween(min, max); // WARNING: not a cryptographically secure RNG!
if (n < 0){
n = -n if (p.isProbablePrime(256)) return p;
}
if (a < 0){
a = n - (-a % n);
}
var nr = 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;
}
 
// set up variables for key generation
/**
var e = bigInt(65537), // use fixed public exponent
* Generates a random prime
* p, q, lambda;
 
* @param {min} int, minimal value
// generate p and q such that λ(n) = lcm(p − 1, q − 1) is coprime with e and |p-q| >= 2^(keysize/2 - 100)
* @param {max} int, maximal value
do }{
* @returns {int} a random generated prime
ap = n - random_prime(-akeysize %/ n2);
*/
function q = random_prime(min,keysize / max2){;
var plambda = MathbigInt.floorlcm(Mathp.randomminus(1), * q.minus((max - 1) - min + 1)) + min;
} while (bigInt.gcd(e, lambda).notEquals(1) || p.minus(q).abs().shiftRight(keysize/2-100).isZero());
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)
e = random_prime(1, t),
d = modular_multiplicative_inverse(e, t);
return {
n: np.multiply(q), // public key (part I)
e: e, // public key (part II)
d: d e.modInv(lambda) // private key d = e^(-1) mod λ(n)
};
};
/**
* Encrypt
* Uses BigInteger.js https://github.com/peterolson/BigInteger.js/tree/master
*
* @param {m} int, / bigInt: the 'message' to be encoded
* @param {n} int, / bigInt: n value returned from generate_rsaRSA.generate() aka public key (part I)
* @param {e} int, / bigInt: e value returned from generate_rsaRSA.generate() aka public key (part II)
* @returns {intbigInt} encrypted hashmessage
*/
RSA.encrypt = function(m, n, e){
return bigInt(m).powmodPow(e).mod(, n);
};
 
/**
* Decrypt
* Uses BigInteger.js https://github.com/peterolson/BigInteger.js/tree/master
*
* @param {mEncc} int, / bigInt: the 'message' to be decoded (encoded with RSA_encryptRSA.encrypt())
* @param {d} int, / bigInt: d value returned from generate_rsaRSA.generate() aka private key
* @param {n} int, / bigInt: n value returned from generate_rsaRSA.generate() aka public key (part I)
* @returns {intbigInt} decrypted hashmessage
*/
RSA.decrypt = function(mEncc, d, n){
return bigInt(mEncc).powmodPow(d).mod(, n);
};
</syntaxhighlight>