This is a basic and simplistic implementation of RSA in JS which used to understand the implementation/math required for encryption/decryption and opportunities for hacking RSA using Quantum Computing.

If you are looking for a nice article on RSA and a small practical example, this might be helpful https://simple.wikipedia.org/wiki/RSA_algorithm

Hacking RSA using Prime Number Factorization

Hacking RSA uses the numeric public exponent from the public key and tries to calculate its largest common multiple factors (p and q) – from those two numbers you can calculate the Private Key. Using traditional computing to hack “small” RSA public keys can be done with a few modern algorithms, including the currently fastest General Number Field Sieve.

A nice library for General Number Field Sieves is http://cado-nfs.gforge.inria.fr/

You can use this site to factor a prime without having to install anything https://asecuritysite.com/encryption/factors. Enter the Public Key which gets generated by the code (should be < 100 bits for the site to be able to factor)

## Installation

`npm install`

## Usage

Edit the index.js file if you would like to edit the size or message being encrypted:

```
// Message
const message = 'Hello';
// Generate RSA keys (bits), max is 232 digits (768 bits)
const keys = RSA.generate(80);
```

Run the code

`npm run start`

## Example Output

```
Public Key Exponent (e):65537
Random Prime (p): 798000088811
Random Prime (q): 563631878177
Totient (lcm of (p-1)(q-1)): 224889144420297550405280
-------------------------------------------------
Keys
Public Key (n = p * q): 449778288841956732777547
Public Key Length: 24 digits (79 bits)
Private Key (d = e multiplicative inverse (totient)): 210473481577786144493313
Private Key Length: 24 digits (78 bits)
-------------------------------------------------
Message: Hello
Encoded: 72101108108111
Encrypted (c = encoded message (m) ^ e modulo n): 426078873740860671226694
Decrypted (m = encrypted message (c) ^ d modulo n): 72101108108111
Decoded: Hello
Correct? true
```

To Do

Utilize the outputs from calculations and format the Private and Public key according to the format. Feel free to submit a pull request ðŸ™‚

Misc Notes

RSA naming scheme changed from bits to digits.

Then RSA-2048 = 617 digits = RSA-617 -> Now RSA-300 = 300 digits.

Certificate Format

```
-----BEGIN RSA PRIVATE KEY-----
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
-----END RSA PRIVATE KEYâ€”â€”
-----BEGIN RSA PUBLIC KEY-----
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, -- n
publicExponent INTEGER -- e
}
-----END RSA PUBLIC KEY-----
```

## Sources/References

I utilized the code from Denys Dovhan as a reference.