Outils pour utilisateurs

Outils du site


crypto_masque_jetable

Cryptographie: variante du "masque jetable" (Vernam) avec le générateur "Blum Blum Shub"

[Python 2.7]

Objectif

L'algorithme de cryptographie appelé “masque jetable” (ou “chiffre de Vernam”) répond aux principes suivants:

  • le cryptage/décryptage est obtenu par combinaison de chaque caractère du message avec une valeur aléatoire
  • le masque composé de toutes les valeurs aléatoires est aussi long que le message lui-même
  • le masque ne sert qu'une seule fois

C'est un algorithme difficile à mettre en pratique, mais qui est quasi impossible à casser.

Références: http://fr.wikipedia.org/wiki/Masque_jetable

On va essayer ici d'en simplifier la mise en œuvre tout en respectant ses principes: au lieu de transmettre le masque complet, on va transmettre les clés de génération de nombres pseudo aléatoires qui permettront au destinataire de retrouver le masque complet pour décrypter le message. Rappelons qu'on utilise le fait qu'un générateur de nombres pseudo-aléatoires génère la même suite à chaque fois qu'on le démarre avec les mêmes arguments.

On combinera chaque octet du message à crypter avec chaque valeur aléatoire issue du générateur, à l'aide de l'opérateur binaire XOR ('ou' exclusif ⇒ '^' en Python). Cela aura pour effet d'inverser le bit placé devant un '1', et de conserver le bit devant un '0'. La conséquence est que 2 applications successives permet de retrouver la valeur initiale.

Et pour le générateur de nombres pseudo-aléatoires, on en choisit un bon: le “Blum Blum Shub” (déjà décrit sur ce site: http://python.jpvweb.com/mesrecettespython/doku.php?id=genalea_bbs) dont les grandes qualités le font reconnaitre en cryptographies.

Dernier point: on va utiliser ici des grands nombres de 1024 bits (plus de 300 chiffres!), pour montrer que c'est possible, et que ça marche. Mais n'oubliez pas de vérifier l'éventuelle limite d'utilisation légale pour votre pays!

Pour les codes présentés: le module à importer est décrit complètement dans le dernier chapitre en fin de page.

Choisir les arguments du générateur "Blum Blum Shub"

Il y a 2 nombres à fournir en argument au générateur:

  • un (très) grand nombre, qui est le produit de 2 grands nombres premiers congrus à 3 modulo 4
  • un nombre entier assez grand qui servira de “graine”, de préférence premier avec le grand nombre précédent

Voilà un exemple de calcul utilisant le module fourni.

A noter que ce calcul ne prend pas plus d'une minute en Python pour calculer les 2 nombres premiers de 1024 bits (plus de 300 chiffres chacun), ce qui est déjà étonnant pour un langage interprété!

from bibcrypto_bbs import *
 
np1 = genpremier_bbs(1024, 100) # 1er nb premier de 1024 bits congru à 3 modulo 4 (avec 100 essais pour MillerRabin)
np2 = genpremier_bbs(1024, 100) # 2e nb premier ... (idem) ...
pnp = np1*np2
print"pnp =", pnp
 
graine = gengraine_bbs(pnp, g1=10000000, g2=99999999) # graine à 8 chiffres, premier avec pnp
print "graine =", graine

Ce qui affichera par exemple (ça change à chaque exécution!):

pnp = 14918821236690364048803357697827915330938033283968520044694771536930083962204522731085107976364842849618124584872512005469561358619582153354051962019051713882879895713608416554642100450496860545667414057413718678420906387634010424980338817514953869099955818435893555577287077984236763950252884280914769585067833911665408393977438690278779688153345857590291910776611048398078671383442699683071755220406286503400148046259020107019158117755289706301669627923537440322481447108082279600092947909584337555856165935214929894504908491221907537540009691905645323823752752168789754791148160238231187156550548453091395261440381

graine = 99380446

A noter que le module utilisé contient aussi la fonction permettant de présenter les nombres très grands en plusieurs lignes pour intégration dans un script Python:

print entiermultilignes(pnp, "pnp")

pnp = "1491882123669036404880335769782791533093803328396852004469477153693008\
39622045227310851079763648428496181245848725120054695613586195821533540519620\
19051713882879895713608416554642100450496860545667414057413718678420906387634\
01042498033881751495386909995581843589355557728707798423676395025288428091476\
95850678339116654083939774386902787796881533458575902919107766110483980786713\
83442699683071755220406286503400148046259020107019158117755289706301669627923\
53744032248144710808227960009294790958433755585616593521492989450490849122190\
75375400096919056453238237527521687897547911481602382311871565505484530913952\
61440381"
pnp = int(pnp)

On utilisera par la suite, à titre d'exemple, ces 2 nombres pnp et graine.

Cryptage de texte

Prenons un texte pouvant comporter: majuscules, minuscules, ponctuations, caractères de contrôle (dont fins de ligne), caractères accentués, etc. Bref, une chaine pouvant comporter n'importe quels octets de valeur 0 à 255.

Par exemple: les 5 premiers articles de la déclaration des “droits de l'homme et du citoyen” de 1789 (ça ne fait pas de mal de les relire…):

msg = """Article premier - Les hommes naissent et demeurent libres et égaux en droits. Les distinctions sociales ne peuvent être fondées que sur l'utilité commune.

Article II - Le but de toute association politique est la conservation des droits naturels et imprescriptibles de l'homme. Ces droits sont la liberté, la propriété, la sûreté, et la résistance à l'oppression.

Article III - Le principe de toute souveraineté réside essentiellement dans la nation. Nul corps, nul individu ne peut exercer d'autorité qui n'en émane expressément.

Article IV - La liberté consiste à faire tout ce qui ne nuit pas à autrui: ainsi l'exercice des droits naturels de chaque homme n'a de bornes que celles qui assurent aux autres membres de la société la jouissance de ces mêmes droits. Ces bornes ne peuvent être déterminées que par la loi.

Article V - La loi n'a le droit de défendre que les actions nuisibles à la société. Tout ce qui n'est pas défendu par la loi ne peut être empêché, et nul ne peut être contraint à faire ce qu'elle n'ordonne pas.
"""

Cryptage:

ch = crypte_bbs(msg, graine, pnp)

Ça y est: le message msg est crypté!

Mais on ne peut pas l'imprimer comme ça, parce qu'il contient maintenant des caractères non imprimables.

Par contre, on peut le convertir avec le module base64, et l'afficher en multilignes avec la fonction du module de fin de page, ce qui permettra de le transmettre sous forme imprimable (fichier texte, email, etc.):

ch64 = base64.b64encode(ch)
print chainemultilignes(ch64)

Ce qui affichera:

ch64 = "RXJ0vi51uZgFCmbABi/95jcbg3oXC3R5dBaL0ycU1pbL2DiIEmXsfLeRT647Wow2pBQ9I\
dewvbTHZvR0cQVIwMocn1omwFr0c8ZshPzNEIYPmEzEE1FmDitsNB0NFQiK/edxs+/QZA5drtofrE\
AAb0Hh+FNvbPSuXmUlwWzcT5f2GXve/LRxWVAZrb7rhGZjIK3ByPcsNI/4CpelVEGJv6XV8aiwZj4\
wKxXliuPfK4hoitlckGA5DobWgVR6Nil+X7Xb5berZoJoovPpf06XJws61smMnan8TlQQSldtCVxw\
38WgMyKI8QDjW5AeETvBkqZwX0fI27/aSEHcavKy7O8CrasmZONNtW+rTEdGxIzdjoEW1dlAnF8/j\
A3humu4tTbRZWMnlV5mJa6fgeDQcE5DqFUXJ3fGwPJBP3WMX4yLjuxzrS1yM5al0BvQnXxP7K5Wbe\
Dk9XAA5IwIE5egZbr8Iy8aX6UPYrE4jT92FSS8fR28yrB7sU8yzLlcgIIn5ghO0VGm0SgURU7D0Lj\
8+5yiRUrIJWlHon4aVTGqQNx5y+Eqs7nt4qysZzmUxYl5GniU2BzDBgcncuThacuVtNtfRx8nCkzo\
Bv+A6m83Apk976/9Bv3aOZGix5KK27bhCT4JF9Q3fGpl46hiCTDHOWYy8G7eLM5sHIK9m6zwgqBMK\
eulAqSF3ahRTYS/TAZcnJPrkU/jABU3SjUPrIAz+/S4SlhgrzArEV5cFii/wWbWAO1r6JQUBSH1Hb\
b3faqxWSpI8y0EqJwLD9TsfiuNgnK/LpDRQB9NlsWu4Z16FTj3UUvPPbLO0rsmdhHbt6yyiynOAhf\
B/7ZJZCvGRLglISLzdRrhh9yamBFrSDmwxJrNFHs/LyXLSs3EYDKO91z3gdyZxoOIrhblsZ/hqXqc\
NDKz1/17Yb8z952FRKoOAm7A93yTyBaVotcSBM7e0MxH61ftgqihlD9VFgPrzb7z/gkir6sOEdbJf\
aA/vCJhIssCwt40wN/oIDHrH2poyKKQoVGra6NCJMEHEkVainnjJ1Dqd3xmp/wPf/mvHhHK3JRquc\
+qIgfGLYdP8oHCY9mMJrjrUWeBliCzYabd9O2YZDTvalCWWgajfMxchVpripBaV5OmClWr8whqY6R\
WN4tBJAjNzqmInbAaXkK/UImPUCx5rtEJL7uHcAwNYAeYtPuE6sDbH3u+l9Uv4TJa4q8ZB4xpfAzf\
3TgLsBmZpLGA9V95McBqss2cYF8avWCwt0h8EdDA9vFhrvhPn3AZ32GspN3cRPitLC6o1Unisftt4\
urbiQyYdSzP8a1irLrn9HA3rokQZhYVpuJDHRi9P4jQNITOcfDFMNA8wPx4k43zUhF29xYrUKcL8D\
ViZaDp9Yg+XTkzAULLRwJIPi4kshzgLt4csahNKHToIKa5tg4="

On va maintenant le décrypter:

ch = base64.b64decode(ch64)
msg2 = crypte(ch, graine, pnp)

Ça y est: c'est décrypté!

On constate qu'on utilise la même fonction pour crypter et décrypter: c'est normal, puisqu'on utilise l'opérateur binaire XOR ('^' en Python)!

Et on affiche la chaine résultat msg2:

Article premier - Les hommes naissent et demeurent libres et égaux en droits. Les distinctions sociales ne peuvent être fondées que sur l'utilité commune.

Article II - Le but de toute association politique est la conservation des droits naturels et imprescriptibles de l'homme. Ces droits sont la liberté, la propriété, la sûreté, et la résistance à l'oppression.

Article III - Le principe de toute souveraineté réside essentiellement dans la nation. Nul corps, nul individu ne peut exercer d'autorité qui n'en émane expressément.

Article IV - La liberté consiste à faire tout ce qui ne nuit pas à autrui: ainsi l'exercice des droits naturels de chaque homme n'a de bornes que celles qui assurent aux autres membres de la société la jouissance de ces mêmes droits. Ces bornes ne peuvent être déterminées que par la loi.

Article V - La loi n'a le droit de défendre que les actions nuisibles à la société. Tout ce qui n'est pas défendu par la loi ne peut être empêché, et nul ne peut être contraint à faire ce qu'elle n'ordonne pas.

On voit bien que tout a été retrouvé, y compris les caractères accentués et les fins de ligne.

Facile, non?

Bon. N'oublions pas que le masque ne doit être utilisé qu'une seule fois! Il faudrait donc transmettre par une voie sécurisée les 2 arguments du générateur “Blum Blum Shub”, dont un nombre de plus de 600 chiffres!

Si l'on n'est pas dans un domaine très critique, on peut encore simplifier:

  • on ne transmet le grand nombre pnp que périodiquement (tous les ans?)
  • on change la graine à chaque nouveau message, et on l'envoie d'une manière sécurisée

On peut aussi transmettre une fois de temps en temps, toujours par voie sécurisée, une liste de couples [graine, pnp] et donner avec chaque message l'index du couple utilisé.

Cryptage de fichiers

On va faire la même chose avec un fichier: chaque octet lu sera combiné grâce à XOR ('ou' exclusif ⇒ '^' en Python) avec une valeur aléatoire de 8 bits (de 0 à 255 bornes comprises) fournie par le générateur “Blum Blum Shub”.

Cryptage:

nfs = "fichier.txt" # fichier source à lire et à crypter
nfd = "fichier.txt.bbs" # fichier destination crypté à écrire
cryptefichier_bbs(nfs, nfd, graine, pnp)

Le fichier “fichier.txt.bbs” est désormais la version cryptée du fichier “fichier.txt”.

Décryptage:

nfs = "fichier.txt.bbs" # fichier source crypté à lire et à décrypter
nfd = "fichier2.txt" # fichier destination décrypté à écrire
cryptefichier_bbs(nfs, nfd, graine, pnp)

Le fichier “fichier2.txt” est la version décryptée du fichier crypté “fichier.txt.bbs”, et est identique au fichier de départ “fichier.txt”.

A noter que dans les opérations de cryptage/décryptage, la taille des fichiers reste identique!

L'opération est, selon le point de vue, rapide ou lente:

  • appliquée à un fichier représentant une page dactylographiée (50 lignes de 80 caractères = 4000 octets), le cryptage ou le décryptage prend environ 1 seconde.
  • appliquée à une image jpg de 3.7 Mo, il faut environ 15 minutes pour la crypter ou la décrypter (soit 2.3/10000 seconde/octet).

Module complet à importer

Module nommé, par exemple, “bibcrypto_bbs.py” pour importation dans les codes ci-dessus:

#!/usr/bin/python
# -*- coding: utf-8 -*-
from __future__ import division
# Python 2.7
 
from random import randint
 
# astuce pour éviter le mélange avec le pow du module math si utilisé
# parce que le pow de math ne supporte pas l'exponentiation modulaire
from __builtin__ import pow as powmod 
 
# pour calcul du PGCD
from fractions import gcd 
 
#############################################################################
def _millerRabin(a, n):
    """fonction utilitaire. Ne pas appeler directement => appeler estpremier"""
    # trouver s et d pour transformer n-1 en (2**s)*d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    # calculer l'exponentiation modulaire (a**d)%n
    apow = powmod(a,d,n) # =(a**d)%n
    # si (a**d) % n ==1 => n est probablement 1er
    if apow == 1:
        return True
    for r in xrange(0,s):
        # si a**(d*(2**r)) % n == (n-1) => n est probablement 1er
        if powmod(a,d,n) == n-1:
            return True
        d *= 2
    return False
 
def estpremier(n, k=20):
    """Test de primalité probabiliste de Miller-Rabin
       à utiliser de préférence quand n>100 millions
       n: nombre à tester
       k: nombre de tests à faire pour limiter les "faux positifs"
       utilise la fonction utilitaire: "_millerRabin"
    """
    # si n<3 ou n==pair => ne renvoyer True que pour n==2
    if n<3 or (n & 1)==0:
        return n==2
    # recommencer le test k fois: seul les nb ayant réussi k fois seront True
    for repete in xrange(0, k):
        # trouver un nombre au hasard entre 1 et n-1 (bornes inclues)
        a = randint(1, n-1)
        # si le test echoue une seule fois => n est composé
        if not _millerRabin(a, n):
            return False
    # n a réussi les k tests => il est "très probablement premier"
    return True
 
#############################################################################
def genpremier_bbs(nbits, k=20):
    """génère un nombre premier de 'nbits' bits, congru à 3 modulo 4
       k: nombre de tests à faire par MillerRabin (fonction 'estpremier')
    """
    p1 = 1 << (nbits-1) # ex: pour nbits=8 bits => 128 (bin='10000000')
    p2 = (p1 << 1)-1 # ex: pour nbits=8 bits => 255 (bin='11111111')
    while True:
        p = randint(p1, p2)
        if p%4==3 and estpremier(p, k):
            return p
 
#############################################################################
def gengraine_bbs(pnp, g1=1, g2=None):
    """retourne une graine g au hasard entre g1 et g2 (bornes comprises)
       et première avec pnp
    """
    if g2==None:
        g2 = pnp
    while True:
        g = randint(g1, g2)
        if gcd(g, pnp)==1:
            return g
 
#############################################################################
def genalea_bbs(graine, pnp, nbits=8):
    """générateur de nombres pseudo-aléatoires "Blum Blum Shub" sous forme d'un
       itérateur. Retourne un nombre entier de 'nbits' bits (défaut=8) au hasard 
       graine et pnp: nb d'entrée du générateur
       version rapide qui extrait le nb de bits maxi selon la taille de pnp
    """
    # calcul du nombre de bits qu'on peut extraire d'un seul coup
    E = ((4,2), (9,3), (24,4), (65,5), (176,6), (477,7), (1295,8))
    v0, ok = 1, False
    for k, v in E:
        if pnp < 10**k:
            nbext, ok = v0, True
            break
        else:
            v0 = v
    if not ok:
        nbext = 8 # pnp pas trouvé dans la liste: 8 bits maxi extractibles        
    # calcul des masques
    masque1 = (1<<nbext)-1 # exemple: masque=7 pour ex=3 bits
    q, r = divmod(nbits, nbext) # on extrait q fois nbext bits + 1 fois r bits
    masque2 =  (1<<r)-1 # exemple: masque=3 pour r=2 bits
    # itérateur
    while True:
        n = 0
        for i in xrange(q):
            graine = powmod(graine, 2, pnp)
            n = n | ((graine & masque1)<<(i*nbext))
        graine = powmod(graine, 2, pnp)
        n = n | ((graine & masque2)<<(q*nbext))
        yield int(n)
 
#############################################################################
def crypte_bbs(msg, graine, pnp):
    """crypte/décrypte la chaine msg avec la série fournie par Blum Blum Shub
       graine et pnp: arguments pour le générateur
    """    
    gen = genalea_bbs(graine, pnp)
    return ''.join([chr(ord(car)^gen.next()) for car in msg])
 
#############################################################################
def cryptefichier_bbs(nfs, nfd, graine, pnp, tbuf=8192):
    """crypte/décrypte le fichier nfs et écrit le résultat dans le fichier nfd
       graine et pnp: arguments pour le générateur bbs
       tbuf: taille du buffer de lecture/écriture disque
    """    
    gen = genalea_bbs(graine, pnp)
    with open(nfs, 'rb') as fs:
        with open(nfd, 'wb') as fd:
            while True:
                buf = fs.read(tbuf)
                if buf=="":
                    break
                fd.write(''.join([chr(ord(car)^gen.next()) for car in buf]))
                buf = None
 
#############################################################################
def chainemultilignes(chaine, nvar='ch', nbcar=78, fdl='\n'):
    """présente une longue chaine en plusieurs lignes pour source Python
         chaine: la chaine de caractères
         nvar: le nom de la variable à écrire
         nbcar: le nombre de caractères maxi de chaque ligne
         fdl: la fin de ligne à intégrer en fin de chaque ligne
    """
    ch = nvar + ' = "'
    lg = len(chaine)
    i1 = 0
    i2 = min(i1+nbcar-len(ch)-1, lg)
    ch += chaine[i1:i2] + '\\' + fdl
    while True:
        i1 = i2
        i2 = min(i1+nbcar-1, lg)
        if i2>i1:
            ch += chaine[i1:i2] + '\\' +  fdl
        else:
            ch = ch[:-len(fdl)-1] + '"' + fdl # = dernière ligne
            break
    return ch
 
#############################################################################
def entiermultilignes(entier, nvar='nb', nbcar=78, fdl='\n'):
    """présente un nb entier très grand en plusieurs lignes pour source Python
         entier: le nombre entier
         nvar: le nom de la variable à intégrer
         nbcar: le nombre de caractères maxi de chaque ligne
         fdl: la fin de ligne à intégrer en fin de chaque ligne
    """
    ch = chainemultilignes(str(entier), nvar, nbcar, fdl)
    ch += nvar + ' = int(' + nvar + ')' + fdl
    return ch


Amusez-vous bien!

crypto_masque_jetable.txt · Dernière modification: 2012/05/01 17:36 de tyrtamos

Outils de la page