Security Basics mailing list archives
Re: RSA Private Key Algorithm
From: Matthias Güntert <MatzeGuentert () gmx de>
Date: Tue, 07 Oct 2008 23:39:09 +0200
On Sat, 2008-10-04 at 23:46 +0000, Mike -- EMAIL IGNORED wrote:
Where could I find a detailed algorithm for computation of the RSA private key? Well structured C or C++ code might do.
Here is some code I wrote for educational purpose... this should give you quit a code feeling about how rsa works...the micro example is written in jscript... have fun! -------------------------------------------------------------------------- /* ========================================================================= JavaScript Source File -- Created with SAPIEN Technologies PrimalScript 2007 NAME: RSA.js AUTHOR: Güntert Matthias DATE : 08.05.2008 COMMENT: dirty micro-RSA Demo ============================================================================ */ var key = Array(3); var message = "supergeheim"; var cipher = Array(); var cleartext = Array(); // key = genKeys(5000); // key = genKeys(55); key = genKeys(19500); WScript.Echo("public key: (", key[0], ", ", key[2], ")") WScript.Echo("private key: (", key[1], ", ", key[2], ")\n") cipher = encrypt(message, key[0], key[2]); cleartext = decrypt(cipher, key[1], key[2]); WScript.Echo("Message: ", message) WScript.Echo("Cipher: ", cipher) WScript.Echo("Cleartext: ", cleartext) // encrypts the string message using key to modul function encrypt(message, key, modul) { var data = Array(); // convert string to int for(x = 0; x < message.length; x++) { var chr = message.charAt(x); data[x] = fastExp(chr.charCodeAt(chr), key, modul); } return data; } // decrypts the num cipher using key to modul function decrypt(cipher, key, modul) { var data = Array(); // convert int back to string for(x = 0; x < cipher.length; x++) { data[x] = String.fromCharCode(fastExp(cipher[x], key, modul)); } return data } // generate public and private keys function genKeys(max) { // check boundaries, 32bit integer (?) if(max > 19699 || max < 55) { WScript.Echo("enter value between 55 and 19699") WScript.Quit() } var key = Array(3); var m = 2, d = -1; var p = 0, q = 0; // ensure that p != q while(p == q) { p = genPrime(max); q = genPrime(max); } var n = p*q; var fi = (p-1)*(q-1); // choose e, rounded to the smaller number var e = Math.ceil(((Math.random() * max) % max)); // ensure that all needs are setisfied while(!isCoPrime(e, fi) || (e < 1) || (e > fi) || d == -1) { e = Math.ceil(((Math.random() * max) % max)); d = xEuclid(e, fi); } key[0] = e; key[1] = d; key[2] = n; return key; } // fast exponentiation function fastExp(b, x, m) { // b ^ x mod m var erg = 1; while(x > 0) { if(x & 1) { erg = (erg * b) % m; } b = (b * b) % m; x = x >> 1; } return erg; } // extended euclid algorithm function xEuclid(b, n) { // taken from: // http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/German/deutsch.html var b0 = b; var n0 = n; var t0 = 0; var t = 1; var q = Math.floor(n0 / b0); var r = n0 - q * b0; while(r > 0) { var temp = t0 - q * t; if(temp >= 0) temp = temp % n; if(temp < 0) temp = n - (( -temp) % n); t0 = t; t = temp; n0 = b0; b0 = r; q = Math.floor(n0 / b0); r = n0 - q * b0; if(b0 == 1) return (t % n); } return -1 } // helper function function isCoPrime(a, b) { if(gcd(a, b) == 1) return true; else return false; } // generate some random primes function genPrime(max) { var random = Math.ceil(((Math.random() * max) % max)); while(!isPrime(random)) { random = Math.ceil(((Math.random() * max) % max)); } return random; } // calculate greatest common devisor function gcd(value1, value2) { var x = 0; var y = 1; var prevx = 1; var prevy = 0; // value1 = 23, value2 = 7 // 23 = 3 * 7 + 2 // 7 = 3 * 2 + 1 // 2 = 2 * 1 + 0 // as long as the rest is not zero while (value2 != 0) { var temp = value2; var quotient = value1 / value2; value2 = value1 % value2; value1 = temp; temp = x; x = prevx - quotient * x; prevx = temp; temp = y; y = prevy - quotient * y; prevy = temp; } return value1; } function isPrime(x) { // only take positiv numbers x = Math.abs(x); // 0 and 1 arent primes per definition if (x == 0 || x == 1) { return false; } // 2 is prime per definition else if (x == 2) { return true; } // even numbers are never prime else if ((x & 1) == 0) { return false; } else { for (var i = 3; i <= Math.sqrt(x); i += 2) { var a = x / i; if (a == Math.round(x / i)) { return false; } } } return true } --------------------------------------------------------------------------
Attachment:
RSA-1.txt
Description:
Current thread:
- RSA Private Key Algorithm Mike -- EMAIL IGNORED (Oct 06)
- Re: RSA Private Key Algorithm Matthias Güntert (Oct 07)
- <Possible follow-ups>
- Re: RSA Private Key Algorithm Simone (Oct 06)
- Re: RSA Private Key Algorithm Adam Pal (Oct 07)