Gilles De Truchis

On m'a récemment demandé de ressortir un vieil algorithme de cryptage RSA que je n'ai pas retrouvé. J'ai donc entrepris de réécrive ma classe RSA. Quelques jours plus tard je découvre qu'une classe RSA existe déjà au sein du package AS3crypto (dont je me sers mais j'étais passé à coté de cet classe "RSAKey"). L'extrême faiblesse de ma classe RSA venait du fait que je ne parvenais pas à effectuer des calcules d'arithmétique modulaire avec des puissances importantes du type: m = cd mod n. En effet l'efficacité des clés de chiffrements du cryptage RSA repose sur la grandeur des nombres et si d doit rester petit, l'intérêt du procédé disparaît.
Pour ceux qui ne connaissent pas le RSA, il ne s'agit pas du Revenu de Solidarité Active vous l'aurez compris. C'est une technique de chiffrement mis au point par Rivest Shamir Adleman. Mais le sujet n'est pas là... Il s'agit de parvenir à calculer des opérations du type cd mod n avec de grandes valeurs. Voici une implémentation d'exponentiation modulaire basée sur de l'exponentiation binaire qui donne des résultats intéressants:

// Modular Exponentiation
var st:int = getTimer();
trace( mod( 1026, 649, 1073 ) );
trace( "Time elapsed: ", getTimer() - st );

/* Math.pow( a, b ) % c */
function mod( a:int, b:int, c:int ):int
{
    var d:Number = 1;
    var e:Number = a;
    
    while( b > 0 )
    {
        if( b % 2 == 1 ) d = ( d * e ) % c;

        e = ( e * e ) % c;
        b /= 2;
    }
    return d % c;
}

Voici une mise en pratique basique du code précédent:

Application pour le PGCD (Plus grand commun diviseur)... Je sais ça remonte à loin tout ça