32:T605,/** * Generates a k-bit RSA public/private key pair * https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Code * * @param {keysize} int, bitlength of desired RSA modulus n (should be even) * @returns {array} Result of RSA generation (object with three bigInt members: n, e, d) */ generate = function(keysize) { /** * Generates a random k-bit prime greater than √2 × 2^(k-1) * * @param {bits} int, bitlength of desired prime * @returns {bigInt} a random generated prime */ function randomPrime(bits) { const min = bigInt(6074001000).shiftLeft(bits - 33); // min ≈ √2 × 2^(bits - 1) const max = bigInt.one.shiftLeft(bits).minus(1); // max = 2^(bits) - 1 for (;;) { const p = bigInt.randBetween(min, max); // WARNING: not a cryptographically secure RNG! if (p.isProbablePrime(256)) { return p; } } } // set up variables for key generation const e = bigInt(65537); // use fixed public exponent let p; let q; let lambda; // generate p and q such that λ(n) = lcm(p − 1, q − 1) is coprime with e and |p-q| >= 2^(keysize/2 - 100) do { p = randomPrime(keysize / 2); q = randomPrime(keysize / 2); lambda = bigInt.lcm(p.minus(1), q.minus(1)); } while (bigInt.gcd(e, lambda).notEquals(1) || p.minus(q).abs().shiftRight( keysize / 2 - 100).isZero()); return { n: p.multiply(q).value, // public key (part I) e: e.value, // public key (part II) d: e.modInv(lambda).value, // private key d = e^(-1) mod λ(n) }; };33:[] 30:{"title":"RSA","cells":[{"id":0,"value":"md`# RSA\nStart by generating a key, or entering a known key (public or private):`","pinned":false,"hidden":false,"mode":"ojs"},{"id":585,"value":"viewof key = {\n const node = html`

\n \n \n \n

Public key (n)
Private key (d)
Exponent (e)

`\n \n let key = generate(64)\n node.value = key\n \n const inputs = {\n n: node.querySelector(\"#n\"),\n d: node.querySelector(\"#d\"),\n e: node.querySelector(\"#e\")\n }\n \n render()\n \n node.querySelector(\"button\").addEventListener(\"click\", function() {\n key = generate(64)\n node.value = key\n render()\n node.dispatchEvent(new CustomEvent('input'));\n })\n \n Object.keys(inputs).forEach(field => {\n inputs[field].addEventListener(\"input\", function() {\n key[field] = bigInt(this.value)\n node.dispatchEvent(new CustomEvent('input'));\n })\n })\n \n function render() {\n Object.keys(key).forEach(d => {\n inputs[d].value = key[d]\n })\n }\n \n return node\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":753,"value":"md`The values are used for encryption and decryption below. If you only know the public key, you can leave the private key blank (and decryption won’t work). This key generation setup always uses a fixed exponent of 65537.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":657,"value":"md`---\n### Encrypt\nType a message:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":356,"value":"viewof input = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":661,"value":"md`Message is converted to ASCII character codes and broken into chunks:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":460,"value":"stringToNum(input)","pinned":false,"hidden":false,"mode":"ojs"},{"id":533,"value":"viewof chunkLength = slider({\n min: 1, \n max: 6, \n step: 1, \n value: 2, \n title: \"Chunk length\", \n description: \"Break up the message for encoding so numbers don’t get too big\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":665,"value":"md`Then encrypted:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":417,"value":"message = stringToNum(input).map(msg => encrypt(msg, key.n, key.e))","pinned":false,"hidden":false,"mode":"ojs"},{"id":737,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":668,"value":"md`---\n### Decrypt\nStarting with a list of comma-separated integers represented the encoded chunks:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":729,"value":"viewof code = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":748,"value":"parsedCode = code.split(\",\").map(d => BigInt(d.trim()))","pinned":false,"hidden":false,"mode":"ojs"},{"id":757,"value":"md`Decrypt each number:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":336,"value":"decryptedValue = message.map(code => decrypt(code, key.d, key.n))","pinned":false,"hidden":false,"mode":"ojs"},{"id":672,"value":"md`Then turn back from ASCII codes to text:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":466,"value":"numToString(decryptedValue)","pinned":false,"hidden":false,"mode":"ojs"},{"id":575,"value":"md`---\n\n### RSA implementation\n\nRSA hash function reference implementation ripped from the example code on Wikipedia, originally based on [@kubrickology’s RSA.js](https://github.com/kubrickology/Bitcoin-explained/blob/master/RSA.js). Currently uses [BigInteger.js](https://github.com/peterolson/BigInteger.js); I’d like to rip it out now that JS has native \\`BigInt\\`s, but it has some nice number-theory helper functions.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":681,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":685,"value":"/**\n * Encrypt\n *\n * @param {m} int / bigInt: the 'message' to be encoded\n * @param {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)\n * @param {e} int / bigInt: e value returned from RSA.generate() aka public key (part II)\n * @returns {bigInt} encrypted message\n */\nencrypt = function(m, n, e) {\n return bigInt(m).modPow(e, n).value;\n};","pinned":false,"hidden":false,"mode":"ojs"},{"id":195,"value":"/**\n * Decrypt\n *\n * @param {c} int / bigInt: the 'message' to be decoded (encoded with RSA.encrypt())\n * @param {d} int / bigInt: d value returned from RSA.generate() aka private key\n * @param {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)\n * @returns {bigInt} decrypted message\n */\ndecrypt = function(c, d, n) {\n return bigInt(c).modPow(d, n).value;\n};","pinned":false,"hidden":false,"mode":"ojs"},{"id":550,"value":"md`---\n### Other code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":449,"value":"function padAscii(input) {\n if (String(input).length == 2) {\n return `0${input}`\n }\n return String(input)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":481,"value":"function stringToNum(input) {\n const returnArray = []\n let chunk = \"\"\n for (let i=0; i {\n let str = String(num)\n if(str.length < chunkLength * 3) {\n str = `0${str}`\n }\n return Array(chunkLength).fill(true)\n .map((_, i) => str.substr(i * 3, 3))\n .map(c => String.fromCharCode(c)).join(\"\")\n }).join(\"\").trim()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":601,"value":"html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":689,"value":"md`---\n\n### Libraries`","pinned":false,"hidden":false,"mode":"ojs"},{"id":180,"value":"bigInt = require(\"big-integer\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":639,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W33","stdlib":"1","titling":"auto"}