Re: RSA Private Key Algorithm

[Matthias Güntert <MatzeGuentert () gmx de>]

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: