Demonstrating the RSA Algorithm in JavaScript

The JavaScript code below picks two random two-digit primes, uses them to generate a RSA keypair, then uses that keypair to encrypt and decrypt a simple message. It uses the LargeInteger class introduced in a previous post to handle the very large numbers involved in the RSA encryption process. To see the code in action, copy it into an .html file and open that file in a web browser that runs JavaScript.

RSA is an asymmetric encryption algorithm developed in the late 1970’s by the researchers Ron Rivest, Adi Shamir, and Leonard Adleman. It works by the process described below.

1. Choose two (ideally very large) prime numbers at random. Call these numbers p and q.

2. Multiply p and q together to find the modulus.

3. Find the least common multiple of (p – 1) and (q – 1). Call this value the totient.

4. Choose a random number greater than 2 and less than the totient. Call this the public exponent candidate.

5. Verify that the public exponent candidate and the totient are co-prime, that is to say, that they have no common factors other than 1. If they are not co-prime, return to step 4 and choose another candidate. If they are co-prime, accept the candidate as the public exponent.

6. Find the modular multiplicative inverse of the public exponent with respect to the modulus, by way of an algorithm too complicated to describe here. This value is the private key.

7. To encrypt a message, first encode it as a number or a series of numbers (each less than the modulus?), raise each number to the public exponent, and “modulo” it against the modulus (that is, divide it by the modulus and take the remainder). This is the encrypted value.

8. To decrypt an encrypted value, raise it to the private exponent and modulo it against the modulus again. The result should be the original, unecrypted value.

This program is for demonstration purposes only, and should be no means be depended on to secure anything in the real world. Aside from any other number of known and unknown vulnerabilities, an RSA keypair that uses two-digit primes obviously can’t possibly be very secure, but that’s all this implementation can handle due to the inefficiency of its various mathematical calculations.

RSAEncryption.png


<html>
<body>
<script type="text/javascript">

// main

function main()
{
	var newline = "<br />";

	// This implementation can't handle big numbers.
	var digitsPerPrime = 2; 

	var keyPair = new EncryptionKeyPair().generate(digitsPerPrime);
	document.write("Key pair is " + keyPair.toString() + newline);

	// hack
	// We're assuming the modulus is greater than the messageToEncrypt.
	// I believe this may cause problems on the rare occasions 
	// when the modulus ends up being less than the message value.

	var messageToEncryptAsInt = 42;
	var base = keyPair.modulus.base;
	var messageToEncrypt = new LargeInteger(base).setFromInt(messageToEncryptAsInt);
	document.write("Message to encrypt is " + messageToEncrypt.toString() + newline);
	
	var messageEncrypted = keyPair.encrypt(messageToEncrypt);
	document.write("Message encrypted is " + messageEncrypted.toString() + newline);

	var messageDecrypted = keyPair.decrypt(messageEncrypted);
	document.write("Message decrypted is " + messageDecrypted.toString() + newline);
}

// classes

function EncryptionKeyPair(modulus, publicExponent, privateExponent)
{
	this.modulus = modulus;
	this.publicExponent = publicExponent;
	this.privateExponent = privateExponent;
}
{
	EncryptionKeyPair.prototype.decrypt = function(messageToDecrypt)
	{
		return this.encryptOrDecrypt(messageToDecrypt, this.publicExponent);	
	}

	EncryptionKeyPair.prototype.encrypt = function(messageToEncrypt)
	{
		return this.encryptOrDecrypt(messageToEncrypt, this.privateExponent);	
	}

	EncryptionKeyPair.prototype.encryptOrDecrypt = function(message, exponent)
	{
		var result = message.raiseToPower
		(
			exponent
		).modulo
		(
			this.modulus
		);

		return message;
	}

	EncryptionKeyPair.prototype.generate = function(digitsPerPrime)
	{
		// Adapted from an example found at the URL
		// https://en.wikipedia.org/wiki/RSA_(cryptosystem)

		var primesRandom = [];
		var base = 10;
		var valueMaxForNumberOfDigits = 
			new LargeInteger(base).setFromInt(base).raiseToPower
			(
				new LargeInteger(base).setFromInt(digitsPerPrime)
			);

		var numberOfPrimesToChoose = 2;

		for (var i = 0; i < numberOfPrimesToChoose; i++)
		{
			var primeCandidate = 
				valueMaxForNumberOfDigits.clone().randomize();

			while (MathHelperLargeInteger.isPrime(primeCandidate) == false)
			{
				primeCandidate.increment();
			}

			primesRandom.push(primeCandidate);
		}
				
		var prime0 = primesRandom[0];
		var prime1 = primesRandom[1];

		var modulus = prime0.clone().multiply(prime1);

		var totient = MathHelperLargeInteger.leastCommonMultiple
		(
			prime0.clone().decrement(), 
			prime1.clone().decrement()
		);

		var publicExponentCandidate = totient.clone().randomize();

		var areCoprime = MathHelperLargeInteger.areCoprime;

		while (areCoprime(publicExponentCandidate, totient) == false)
		{
			publicExponentCandidate.increment();
			if (publicExponentCandidate.isGreaterThanOrEqualTo(totient))
			{
				publicExponentCandidate.setFromInt(2);
			}
		}

		var publicExponent = publicExponentCandidate;

		var privateExponent = MathHelperLargeInteger.modularMultiplicativeInverse
		(
			publicExponent,
			totient
		);
		
		this.modulus = modulus;
		this.publicExponent = publicExponent;
		this.privateExponent = privateExponent;

		return this;
	}

	// string 

	EncryptionKeyPair.prototype.toString = function()
	{
		var objectToSerialize = 
		{
			"modulus" : this.modulus.toString(),
			"publicExponent" : this.publicExponent.toString(),
			"privateExponent" : this.privateExponent.toString()

		}
		var returnValue = JSON.stringify(objectToSerialize);
		return returnValue;
	}
}

function LargeInteger(base)
{
	this.base = base;
	this.digits = [];
}
{
	// instance methods

	LargeInteger.prototype.add = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		var numberOfDigitsGreater;

		if (numberOfDigitsInThis >= numberOfDigitsInOther)
		{
			numberOfDigitsGreater = numberOfDigitsInThis;
		}
		else
		{
			numberOfDigitsGreater = numberOfDigitsInOther;
		}

		var numberOfDigitsInSum = numberOfDigitsGreater + 1;

		this.expandNumberOfDigitsTo(numberOfDigitsInSum);
		other.expandNumberOfDigitsTo(numberOfDigitsInSum);

		var carryDigit = 0;

		for (var i = 0; i < numberOfDigitsInSum; i++)
		{
			var sumAtDigit = this.digits[i] + other.digits[i] + carryDigit;

			var digitValue = sumAtDigit % this.base;
			carryDigit = (sumAtDigit - digitValue) / this.base;

			this.digits[i] = digitValue;
		}

		this.removeLeadingZeroes();
		other.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.clone = function()
	{
		var returnValue = new LargeInteger(this.base);

		returnValue.overwriteWith(this);

		return returnValue;
	}

	LargeInteger.prototype.decrement = function()
	{
		return this.subtract(new LargeInteger(this.base).setFromInt(1));
	}

	LargeInteger.prototype.divide = function(other)
	{
		var dividend = this.clone();
		var divisor = other.clone();
		var base = dividend.base;

		var one = new LargeInteger(base).setFromInt(1);

		var lengthOfDivisorInDigits = divisor.digits.length;
		var differenceInLengths = dividend.digits.length - lengthOfDivisorInDigits;

		dividend.multiplyByBaseRaisedTo(lengthOfDivisorInDigits);
		divisor.multiplyByBaseRaisedTo(differenceInLengths + lengthOfDivisorInDigits);

		var result = new LargeInteger(base).setFromInt(0);

		while (divisor.digits.length > 0)
		{
			if (divisor.isLessThanOrEqualTo(dividend))
			{
				dividend.subtract(divisor);
				result.add(one);
			}
			else
			{
				divisor.divideByBaseRaisedTo(1);
				result.multiplyByBaseRaisedTo(1);
			}	
		}

		result.divideByBaseRaisedTo(2 * lengthOfDivisorInDigits);

		this.overwriteWith(result);

		return this;
	}

	LargeInteger.prototype.divideByBaseRaisedTo = function(exponent)
	{
		this.digits.splice(0, exponent);

		return this;
	}

	LargeInteger.prototype.expandNumberOfDigitsTo = function(numberOfDigitsTotal)
	{
		var numberOfDigitsToAdd = numberOfDigitsTotal - this.digits.length;
		for (var i = 0; i < numberOfDigitsToAdd; i++)
		{
			this.digits.push(0);	
		}

		return this;
	}

	LargeInteger.prototype.increment = function()
	{
		return this.add(new LargeInteger(this.base).setFromInt(1));
	}

	LargeInteger.prototype.isEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis != numberOfDigitsInOther)
		{
			returnValue = false;
		}
		else
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis != digitOther)
				{
					returnValue = false;
					break;
				}
			}
		}

		return returnValue;
	}

	LargeInteger.prototype.isGreaterThan = function(other)
	{
		var returnValue = (this.isLessThanOrEqualTo(other) == false);
		return returnValue;
	}

	LargeInteger.prototype.isGreaterThanOrEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis > numberOfDigitsInOther)
		{
			returnValue = true;
		}
		else if (numberOfDigitsInThis == numberOfDigitsInOther)
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis < digitOther)
				{
					returnValue = false;
					break;
				}
				else if (digitThis > digitOther)
				{
					break;
				}			
			}
		}
		else
		{
			returnValue = false;
		}

		return returnValue;
	}

	LargeInteger.prototype.isLessThan = function(other)
	{
		var returnValue = (this.isGreaterThanOrEqualTo(other) == false);
		return returnValue;
	}

	LargeInteger.prototype.isLessThanOrEqualTo = function(other)
	{
		var returnValue;
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		if (numberOfDigitsInThis < numberOfDigitsInOther)
		{
			returnValue = true;
		}
		else if (numberOfDigitsInThis == numberOfDigitsInOther)
		{
			returnValue = true;

			for (var i = numberOfDigitsInThis - 1; i >= 0; i--)
			{
				var digitThis = this.digits[i];
				var digitOther = other.digits[i];

				if (digitThis > digitOther)
				{
					returnValue = false;
					break;
				}
				else if (digitThis < digitOther)
				{
					break;
				}			
			}
		}
		else
		{
			returnValue = false;
		}

		return returnValue;
	}

	LargeInteger.prototype.isNotEqualTo = function(other)
	{
		var returnValue = (this.isEqualTo(other) == false);
		return returnValue;
	}

	LargeInteger.prototype.modulo = function(other)
	{
		var dividend = this.clone();
		var divisor = other.clone();

		var lengthOfDivisorInDigits = divisor.digits.length;
		var differenceInLengths = dividend.digits.length - lengthOfDivisorInDigits;

		var divisorOriginal = divisor.clone();
		divisor.multiplyByBaseRaisedTo(differenceInLengths);

		while (divisor.digits.length >= lengthOfDivisorInDigits)
		{
			if (divisor.isLessThanOrEqualTo(dividend))
			{
				dividend.subtract(divisor);
			}
			else
			{
				divisor.divideByBaseRaisedTo(1);
			}	
		}

		this.overwriteWith(dividend);

		return this;
	}

	LargeInteger.prototype.multiply = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;		

		var numberOfDigitsInProduct = numberOfDigitsInThis + numberOfDigitsInOther; 
		var product = new LargeInteger(this.base).expandNumberOfDigitsTo(numberOfDigitsInProduct);

		for (var i = 0; i < numberOfDigitsInThis; i++)
		{
			var digitFromThis = this.digits[i];

			for (var j = 0; j < numberOfDigitsInOther; j++)
			{
				var digitFromOther = other.digits[j];

				var productOfDigits = 
					digitFromThis 
					* digitFromOther;

				var productDigitIndex = i + j;

				var carryDigit = productOfDigits; 

				while (carryDigit > 0)
				{
					var sumAtDigit = product.digits[productDigitIndex] + carryDigit;

					var digitValue = sumAtDigit % this.base;
					carryDigit = (sumAtDigit - digitValue) / this.base;

					product.digits[productDigitIndex] = digitValue;

					productDigitIndex++;
				}
			}
		}

		product.removeLeadingZeroes();
		this.overwriteWith(product);

		return this;
	}

	LargeInteger.prototype.multiplyByBaseRaisedTo = function(exponent)
	{
		for (var i = 0; i < exponent; i++)
		{
			this.digits.splice(0, 0, 0);
		}

		return this;
	}

	LargeInteger.prototype.overwriteWith = function(other)
	{
		var numberOfDigitsInThis = this.digits.length;
		var numberOfDigitsInOther = other.digits.length;

		for (var i = 0; i < numberOfDigitsInOther; i++)
		{
			this.digits[i] = other.digits[i];
		}

		if (numberOfDigitsInThis > numberOfDigitsInOther)
		{
			this.digits.splice
			(
				numberOfDigitsInOther, 
				numberOfDigitsInThis - numberOfDigitsInOther
			);
		}		

		return this;
	}

	LargeInteger.prototype.randomize = function()
	{
		var valueOriginal = this.clone();
		var base = new LargeInteger(this.base).setFromInt(this.base);
		var numberOfDigits = new LargeInteger(this.base).setFromInt(this.digits.length);		
		var valueMaxForNumberOfDigits = base.raiseToPower(numberOfDigits);

		for (var i = 0; i < this.digits.length; i++)
		{
			digitRandom = Math.floor
			(
				Math.random() * this.base
			);

			this.digits[i] = digitRandom;
		}

		this.multiply(valueOriginal).divide(valueMaxForNumberOfDigits);

		return this;
	}

	LargeInteger.prototype.raiseToPower = function(exponent)
	{
		var result = this.raiseToPowerBySquaring(exponent);

		this.overwriteWith(result);

		return this;
	}

	LargeInteger.prototype.raiseToPowerBySquaring = function(exponent)
	{
		var returnValue = LargeInteger.raiseValueToPowerBySquaring
		(
			this.clone(), 
			exponent.clone(), 
			new LargeInteger(this.base).setFromInt(1),
			new LargeInteger(this.base).setFromInt(2)
		);

		return returnValue;
	}

	LargeInteger.raiseValueToPowerBySquaring = function
	(
		valueToRaise, exponent, constantOne, constantTwo
	)
	{
		var returnValue;

		if (exponent.digits.length == 1 && exponent.digits[0] == 1)
		{
			returnValue = valueToRaise;
		}
		else if (exponent.digits[0] % 2 == 0)
		{
			returnValue = LargeInteger.raiseValueToPowerBySquaring
			(
				valueToRaise.clone().multiply(valueToRaise), 
				exponent.clone().divide(constantTwo),
				constantOne,
				constantTwo
			);
		}
		else
		{
			returnValue = LargeInteger.raiseValueToPowerBySquaring
			(
				valueToRaise.clone().multiply(valueToRaise), 
				exponent.clone().subtract(constantOne).divide(constantTwo),
				constantOne,
				constantTwo
			).multiply
			(
				valueToRaise
			);
		}

		return returnValue;
	}

	LargeInteger.prototype.removeLeadingZeroes = function()
	{
		return this.removeLeadingZeroesDownTo(0);
	}

	LargeInteger.prototype.removeLeadingZeroesDownTo = function(numberOfDigitsTotal)
	{
		var i = this.digits.length - 1;

		while (i >= numberOfDigitsTotal && this.digits[i] == 0)
		{
			this.digits.splice(i, 1);	
			i--;
		}

		return this;
	}

	LargeInteger.prototype.setFromInt = function(valueToSet)
	{
		var d = 0;

		while (valueToSet > 0)
		{
			var digitValue = valueToSet % this.base;
			valueToSet = (valueToSet - digitValue) / this.base;
			this.digits[d] = digitValue;

			d++;
		}

		this.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.setToOne = function()
	{
		this.digits = [1];
		return this;
	}

	LargeInteger.prototype.setToZero = function()
	{
		this.digits = [];
		return this;
	}

	LargeInteger.prototype.subtract = function(other)
	{
		var base = this.base;

		var numberOfDigitsInOther = other.digits.length;

		var numberOfDigitsInThis = this.digits.length;
		other.expandNumberOfDigitsTo(numberOfDigitsInThis);

		for (var i = 0; i < numberOfDigitsInOther; i++)
		{
			var digitFromThis = this.digits[i];
			var digitFromOther = other.digits[i];

			if (digitFromThis < digitFromOther)
			{
				var valueBorrowed = 0;
				var j = i;

				while (valueBorrowed == 0)
				{
					j++;

					var digitToBorrowFrom = this.digits[j];
					if (digitToBorrowFrom > 0)
					{
						valueBorrowed = base;
						this.digits[j]--;

						j--;
						while (j > i)
						{
							this.digits[j] = base - 1;
							j--;
						}
					}
				}

				digitFromThis += valueBorrowed;				
			}

			this.digits[i] = digitFromThis - digitFromOther;
		}

		this.removeLeadingZeroes();
		other.removeLeadingZeroes();

		return this;
	}

	LargeInteger.prototype.toInt = function()
	{
		var returnValue = 0;

		var placeMultiplierCurrent = 1;

		var numberOfDigits = this.digits.length;

		for (var i = 0; i < numberOfDigits; i++)
		{
			returnValue += this.digits[i] * placeMultiplierCurrent;

			placeMultiplierCurrent *= this.base;
		}

		return returnValue;
	}


	LargeInteger.prototype.toString = function()
	{
		var returnValue = "";

		var numberOfDigits = this.digits.length;

		for (var i = numberOfDigits - 1; i >= 0; i--)
		{
			returnValue += "" + this.digits[i];
		}

		return returnValue;
	}
}

function MathHelperLargeInteger()
{
	// static class
}
{
	MathHelperLargeInteger.areCoprime = function(a, b)
	{
		var greatestCommonDivisor = MathHelperLargeInteger.greatestCommonDivisor(a, b);
		var one = new LargeInteger(a.base).setToOne();
		var returnValue = greatestCommonDivisor.isEqualTo(one);
		return returnValue;
	}

	MathHelperLargeInteger.greatestCommonDivisor = function(a, b)
	{
		// Adapted from pseudocode at the URL:
		// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

		var base = a.base;

		var s = new LargeInteger(base).setToZero();    
		var old_s = new LargeInteger(base).setToOne();

		var t = new LargeInteger(base).setToOne();   
		var old_t = new LargeInteger(base).setToZero();

		var r = b.clone();
		var old_r = a.clone();

		var quotient = new LargeInteger(base);
		var temp = new LargeInteger(base);
		var temp2 = new LargeInteger(base);
		var zero = new LargeInteger(base).setToZero();
		
		while (r.isNotEqualTo(zero))
		{
			quotient.overwriteWith(old_r).divide(r);

			temp.overwriteWith(r);
			r.overwriteWith(old_r).subtract
			(
				temp2.overwriteWith(quotient).multiply(temp)
			);
			old_r.overwriteWith(temp);

			temp.overwriteWith(s);
			s.overwriteWith(old_s).subtract
			(
				temp2.overwriteWith(quotient).multiply(temp)
			);
			old_s.overwriteWith(temp);

			temp.overwriteWith(t);
			t.overwriteWith(old_t).subtract
			(
				temp2.overwriteWith(quotient).multiply(temp)
			);
			old_t.overwriteWith(temp);
		}

		var returnValue = old_r;
	
		return returnValue;
	}

	MathHelperLargeInteger.isPrime = function(possiblePrime, two, zero, temp)
	{
		// hack - This is almost certainly not the most efficient algorithm.

		var returnValue = true;

		if (two == null)
		{
			var base = possiblePrime.base;
			two = new LargeInteger(base).setFromInt(2);
			zero = new LargeInteger(base).setToZero();
			temp = new LargeInteger(base);
		}
		
		if (possiblePrime.isLessThan(two))
		{
			returnValue = false;	
		}
		else
		{
			// hack - A lot of re-instancing here.
			var possiblePrimeHalf = possiblePrime.clone().divide(two);
			var factorCurrent = two.clone();

			while (factorCurrent.isLessThanOrEqualTo(possiblePrimeHalf))
			{
				while (MathHelperLargeInteger.isPrime(factorCurrent, two, zero, temp) == false)
				{
					factorCurrent.increment();
				}

				var isPossiblePrimeAMultipleOfCurrentDivisor = 
					temp.overwriteWith
					(
						possiblePrime
					).modulo
					(
						factorCurrent
					).isEqualTo
					(
						zero
					);
	
				if (isPossiblePrimeAMultipleOfCurrentDivisor == true)
				{
					returnValue = false;
					break;
				}

				factorCurrent.increment();
			}
		}

		return returnValue;
	}

	MathHelperLargeInteger.leastCommonMultiple = function(a, b)
	{
		var product = a.clone().multiply(b);
		var greatestCommonDivisor = MathHelperLargeInteger.greatestCommonDivisor(a, b);
		var returnValue = product.divide(greatestCommonDivisor);
		return returnValue;
	}

	MathHelperLargeInteger.modularMultiplicativeInverse = function(valueToInvert, modulus)
	{
		// Adapted from:
		// https://math.stackexchange.com/questions/67171/
		// calculating-the-modular-multiplicative-inverse-without-all-those-strange-looking

		var returnValue;

		var base = valueToInvert.base;

		var one = new LargeInteger(base).setToOne();

		if (valueToInvert.isEqualTo(one)) 
		{
			returnValue = one.clone();	
		}
		else
		{
			var temp = new LargeInteger(base);
			var temp2 = new LargeInteger(base);

			var c = modulus.clone().modulo(valueToInvert);
			var d = valueToInvert.clone();
			var u = modulus.clone().divide(valueToInvert);
			var v = one.clone();

			while (c.isNotEqualTo(one) && d.isNotEqualTo(one)) 
			{
				v.add
				(
					temp.overwriteWith
					(
						d
					).divide
					(
						c
					).multiply
					(
						u
					)
				);

				d.modulo(c);

				if (d.isNotEqualTo(one)) 
				{
					u.add
					(
						temp.overwriteWith
						(
							c
						).divide
						(
							d
						).multiply
						(
							v
						)
					);

					c.modulo(d);
				}
			}

			var tAsInt = (d.isNotEqualTo(one) ? 1 : 0);
			var t = new LargeInteger(base).setFromInt(tAsInt);

			returnValue = v.multiply
			(
				temp.overwriteWith
				(
					one
				).subtract
				(
					t
				)
			).add
			(
				temp.overwriteWith(t).multiply
				(
					temp2.overwriteWith
					(
						modulus
					).subtract
					(
						u
					)
				)
			);
		}

		return returnValue;
	}

}

// run

main();

</script>
</body>
</html>

Advertisements
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s