Categories
Cryptography

Une histoire d’arithmétique modulaire

Bob était amoureux d’Alice. Il voulait lui envoyer une déclaration d’amour. Mais Bob avait peur que cette déclaration puisse tomber dans les mains d’une autre personne. Par exemple le méchant Oscar. Par chance Alice qui aimait bien les maths connaissait RSA. Elle disposait tout naturellement d’une clé publique (b, n) et d’une clé privé (a, n).
Bob utilisa donc la clé publique d’Alice pour protéger son message:
        secret = message˄b mod n
Une fois le message réceptionné par Alice (IP par transporteurs aviaires), elle utilisa la clé privée afin de découvrir le message:
        message = secret˄a mod n

Mais comment a fait Alice pour avoir de telles clés?

Une des premières choses à faire était de trouver (à la main et avec le test de primalité de Miller-Rabin) deux très grands nombres premiers p et q tels que:

        (1)   Φ(n) = (p - 1) * (q - 1), l’indicateur d’Euler
        (2)   n = p * q

n, le modulus, est donc le produit de deux grands nombres premiers.

Nous avons également:
        (3)   a = b˄-1 mod Φ(n)
(Si tu veux comprendre un peu plus en détail: 1 et 2. Et si vraiment Euler ne te dis plus rien, tu peux aussi réviser ton arithmétique modulaire de terminale. Le bon vieux temps.)

Ensuite nous devons trouver un entier b tel que:
        pgcd(b, Φ) = 1
Et finalement l’exposant privé a sera l’inverse de b mod Φ. (Pareil, revoir les cours de terminale. Désolé.)

Mais au bout de tout ça, quelles données sont utiles à Alice ? Et bien uniquement l’exposant public b, l’exposant privé a et le modulus n. C’est tout. p et q ne sont plus utiles puisque nous connaissons n.
De même pour Φ, il ne faut pas le garder car il permet de retrouver p et q. (J’aimais bien faire ça, en seconde…)

Bref attaquer RSA n’est pas plus facile que de factoriser le modulus.

Si Oscar avait connu p et q il aurait facilement pu calculer Φ (avec 1). Puis l’exposant privé a (avec 3) qui est donc l’inverse modulaire de b et Φ. Un cauchemar pour Bob. Une chance pour les victimes de WannaCry.

Categories
Security

pyHIDS

Le week-end dernier a été l’occasion de reprendre un petit projet commencé en 2008. Le code source de pyHIDS est depuis 2010 dans un dépôt Mercurial et est à l’abandon. Le programme fonctionnait déjà assez bien à l’époque puisqu’il était utilisé dans le but de vérifier l’intégrité de mon ordinateur durant les deux années qui ont suivi sa création (sur une Mandriva Cooker).

pyHIDS fonctionne maintenant avec Python 3.2 et est aussi plus rapide, j’ai appliqué les conseils d’un commentaire bienveillant.
À l’époque j’utilisais une version fait maison de RSA, dorénavant cette excellente implémentation est utilisée. Cela facilite l’installation.
J’ai également amélioré et facilité la configuration qui se fait maintenant dans un fichier de configuration dédié. D’autres changements sont prévus à ce niveau.

Fonctionalités:

  • génération de clés RSA afin de vérifier l’intégrité de la base. Après génération de la base dans l’idéal il faut supprimer la clé privé de l’ordinateur surveillé;
  • notifications des modifications sur le système via Syslog ou envoie d’e-mail;
  • notifications par e-mail des exécutions de pyHIDS, même lorsque l’intégrité du système est préservée. Ceci pour éviter qu’un attaquant ne supprime les règles cron;
  • enregistrement de tous les événements dans un fichier avec un format standard. Ce qui va me permettre d’écrire un petit parseur CGI afin d’exposer les derniers événements (heures de scan du système, heures de détection de problèmes, etc.).

Le projet a une page Freecode pour suivre les mises à jour.

Categories
Cryptography Python Security

Pure Python RSA implementation compatible OpenSSL

$ sudo aptitude install python-pyasn1
$ hg clone https://bitbucket.org/sybren/python-rsa/
$ cd python-rsa
$ sudo python setup.py install
$ cd ..

# Generation of a private key:
$ openssl genrsa -out myprivatekey.pem 512


# To get a Python-RSA-compatible public key from OpenSSL:
$ pyrsa-priv2pub -i myprivatekey.pem -o mypublickey.pem

# Get a public key with the standard method:
$ openssl rsa -in myprivatekey.pem -out public.pem -outform PEM -pubout
writing RSA key


# Test 1: Python-RSA-compatible public key
$ echo hello there > testfile.txt
$ pyrsa-encrypt -i testfile.txt -o testfile.rsa mypublickey.pem
Reading public key from mypublickey.pem
Reading input from testfile.txt
Encrypting
Writing output to testfile.rsa
$ openssl rsautl -in testfile.rsa -inkey myprivatekey.pem -decrypt
hello there


# Test 2: standard public key
$ openssl rsautl -encrypt -inkey public.pem -pubin -in testfile.txt -out file.ssl
$ pyrsa-decrypt -i file.ssl -o file.txt myprivatekey.pem 
Reading private key from myprivatekey.pem
Reading input from file.ssl
Decrypting
Writing output to file.txt
$ cat file.txt 
hello there

C’est le module Python RSA que j’utilise en général.