# RSA Public Key Cryptography

NSA™ Proof Or Your Money Back!

## How To Use

Essentially we are calculating a public key (n and e) from our seed primes (p and q) and e. Assuming you don't already have a public key ready to use, pick two prime numbers as the values for p and q. Then click the Calc Pub Key button to compute the public key and update the public key fields. The larger the primes the more secure the encryption.

The value n and e form the public key. The totient and therefore d must remain secret.

In Encrypt Mode only the public key values will be used, n and e, as these are all we need to encrypt the message. If you already have a public key and do not know the seed primes then just ignore the p and q fields.

Decrypt Mode requires the private keys and you or someone else will need to know the private key (p,q and e) values in order to decrypt the message back to plaintext.

## How It Works

At face value the scheme is not terribly complicated. As mentioned we need to prime numbers, p and q. Once you click either Encrypt or Decrypt you can see how these values are calculated. The exception is e which is not a hard value and can be anything that is relatively prime to the totient.

### How are these values used?

As I mentioned above the values e and n form the public key. When we 'encrypt' we are performing a mathematical operation on an integer. The result is the encrypted value. The example above is taking a whole string but it must be represented as an integer before it can be encrypted.

Encrypted Value = Plaintext Valuee mod n

Plaintext Value = Encrypted Valued mod n

Calculating d is a bit complicated. We must find d such that e*d mod (p-1)*(q-1) = 1

Solving this involves calculating the inverse modulus outlined in javascript below.

`// a > m // invMod(99,23) -> 56 function invMod(a, m) { var gcdArr = extendedEuler(a, m); var gcd = gcdArr[0]; var x = gcdArr[1]; var y = gcdArr[2]; if(y < 0) y += a; if(gcd != 1) return -1; // gcd doesn't exist else return y % a; }`

`// ax + by = gcd(a,b) // extendedEuler(35,12) -> [1, -1, 3] function extendedEuler(a, b) { if(b === 0) { x = 1; y = 0; return [a, x, y]; } var gcdArr = extendedEuler(b, a % b); var gcd = gcdArr[0]; var _x = gcdArr[1]; var _y = gcdArr[2]; x = _y; y = _x - Math.floor(a/b) * _y; return [gcd, x, y]; }`