Find private key from pair of 2 prime numbers

rsa-find-private-key.js

// Let's say, pick 2 prime number p = 23, q = 13
// lcm(p, q) = 299
var phi = 264; // N = (p-1)(q-1) is 264
var e = 17; // pick prime number for the public key, GCD(e, phi(N)) has to 1 ... no common divisor
// what is private key d to decrypt?
// find combination of d and k. k could be whatever but satisfy
// e * d = 1 + phi(N) * k
//
for (var d=0 ;d<phi; d++) {
	var val = (e * d - 1) / phi;
	console.log('trying d = ',d,' checking the k - is this integer?',val, (val%1 === 0) ? 'BINGO!!!!!!!!':'nope');
}
// example:
// trying d =  231  checking the k - is this integer? 14.871212121212121 nope
// trying d =  232  checking the k - is this integer? 14.93560606060606 nope
// trying d =  233  checking the k - is this integer? 15 BINGO!!!!!!!!
//
// looks like d is 233 while k is 15

// how to encrypt the message?
// enc(m) = m^e mod N
// dec(enc(m)) = enc(m)^d mod N

RSA.md

RSA Example

Let's say secret message is 18, you send 31 in public network after encryption then you decrypt using secret key 233. You get back the original message 18.

• 18^17 mod 299 - Wolfram|Alpha
• 31^233 mod 299 - Wolfram|Alpha