Python : apprendre le chiffrement symétrique par portion

Un billet de Julien Garderon

Principes et état d’esprit

Rappel: un signe est un élément d’imprimerie. Les signes correspondent à l’ensemble des caractères imprimables ainsi que les espaces et les caractères spéciaux.

Il s’agit d'observer aujourd’hui une méthode de chiffrement symétrique à transposition: on modifie mathématiquement l’ordre du contenu, sans en changer les symboles représentés. Elle utilise un principe similaire à celui utilisé par le chiffrement AES. Ce type de chiffrement symétrique n’augmente pas la taille totale transférée du message, en dehors de la clé utilisée (qui peut être utilisée à plusieurs reprises, même si ce n'est pas conseillé...).

Cette méthode semble indéchiffrable (le contenu est temporairement «perdu») à une condition: que ladite clé reste secrète. C’est pour cette raison que l’utilisation sur Internet n’est pas possible – tout du moins sans utiliser d’’abord un chiffrement asymétrique à clés publiques! Dans ce cas, la sécurité totale du système d’échange repose sur la fiabilité du chiffrement asymétrique: l’interception de la clé symétrique sur une connexion chiffrée asymétriquement mais écoutée et piratée, fait perdre toute la confidentialité. Le couple symétrique/asymétrique n’a donc intérêt (sauf saucuneous certaines conditions trop particulières, comme sur des lignes optiques polarisées) car la fiabilité du chiffrement asymétrique suffit à garantir la sécurité du message.

Il existe de nombreuses raisons de chiffrer symétriquement ses messages: la confidentialité bien sûr, mais parfois aussi des raisons techniques, en obligeant à des opérations sur le message qui permet d’en garantir «totalement» le contenu. Ne rentrons pas ici sur les limites juridiques ainsi que les questions illégales que peuvent cacher le chiffrement: il s’agit d’un outil, comme un couteau - qui peut aider l’homme à manger et à se défendre, comme à tuer son prochain ou à agresser. C’est moins la fonction de l’outil que l’usage qui en détermine une forme de moralité…

Dans mon exemple, un texte (long) et une phrase «passe» (donc la longueur doit être raisonnable, au moins égale au quart de la taille de la matrice utilisée et où cette matrice est dimensionnée au paquet de signes à traiter à un instant t), seront utilisés conjointement.

L’intérêt de la phrase «passe» est d’en retenir une suite de chiffres – ça tombe bien, Python utilise ce principe pour gérer ses strings -, qui sera associée à des opérations (en réalité à des fonctions bêtes). Ces opérations peuvent être potentiellement publiques: c’est leur ordre et leur fréquence qui comptent. La connaissance de l’opération individuelle (où même d’une partie) ne permet pas de connaître le chiffrement général. Le code source de cet outil peut être diffusé sans restriction.

La phrase «passe» est donc la recette du chiffrement: elle donne à la fois l’ordre et le nombre d’opérations à effectuer une matrice de caractères/signes, eux aussi convertis en nombre. Ainsi, tel que les noms de domaine sur le web, on retient une phrase humainement compréhensible (donc plus facile à retenir) qu’une suite de chiffres ou d'expédients / d'indications…

Exemple:
>>> list(map(ord,list("toto va au marché"))) # ---> la fonction native de Python "ord", donne la représentation le code Unicode
[116, 111, 116, 111, 32, 118, 97, 32, 97, 117, 32, 109, 97, 114, 99, 104, 233]
{ effectuer l’opération 116 puis 111 puis 116 puis 111 puis 32 … }

Pour simplifier, nous utiliserons seulement trois caractères différents, qui resteront des caractères, correspondant à une opération «simple» de matrice sous Numpy:

def operation_A(npArray):
return np.roll(npArray,1)

def operation_B(npArray):
return np.rot90(npArray)

def operation_C(npArray):
return np.flip(npArray,1)

OPERATIONS = {
"a": operation_A,
"b": operation_B,
"c": operation_C
}

Fonctionnement

Nous allons tout d’abord créer une matrice avec Numpy, en veillant à ne pas dépasser une certaine taille de matrice, qui correspond à une portion arbitraire du texte à chiffrer. Si la portion est trop petite, on ajoute à DROITE le nombre de signes nécessaires par un signe pris au hasard DANS L’ENSEMBLE du texte à chiffre. Gardons à l'esprit que ce signe ajouté se doit d'être plutôt dans une fréquence d’apparition basse.

Création de la matrice:

MATRICES_taille = (5,5)
MATRICES_nbre = MATRICES_taille * MATRICES_taille

import numpy as np

def matrice_creer(texte_portion,ajout="*"):
if len(texte_portion) texte_portion = texte_portion.rjust(MATRICES_nbre, ajout)
elif len(texte_portion)>MATRICES_nbre:
raise ValueError(
"la portion de texte ne peut excédent%s signes"% MATRICES_nbre
)
texte_portion = np.asarray(
list(map(ord,list(texte_portion)))
)
texte_portion = np.reshape(
texte_portion,
MATRICES_taille
)
return texte_portion

Au choix, trouver l’ajout:

def occurences_chgt_frequence(texte): # ---> «hasard» total
return ''.join(random.choice(list(texte)) for _ in range(1))

def occurences_chgt_frequence(texte): # ---> le premier des signes les moins fréquents
frequence = list(
(
lettre, texte.count(lettre)
) for lettre in list(texte)
)
return sorted(
frequence,
key = lambda couple: couple
)

Le corps du script, ici pour seulement les 20 premiers caractères afin de garder de se placer dans un cas un peu spécial:

phrase = "abcaabacaabacccaba"

texte_original = "Ceci est un message totalement confidentiel: \
les coordonnées du paquet de cookies sont au placard haut, \
étagère de droite. Stop."

ajout = occurences_chgt_frequence(
texte_original
)

texte_np = matrice_creer(
texte_original[0:20],
ajout
)

for signe in phrase:
texte_np = OPERATIONS(
texte_np
)

texte_np = np.reshape(
texte_np,
(1, MATRICES_nbre)
)

print("".join(list(map(chr,texte_np.tolist()))))

Lorsque j’exécute le script, en laissant le signe d’ajout à l’opérateur étoile («*»), voici ce que cela donne pour la portion 0:20:

Phrase "abcaabacaabacccaba" → ****** ic*Cu t*e***ens **

Phrase "abcaabacaabaccaba" → eu t*e ic*C***** ***sn***

… donc le changement d’un seul caractère dans la phrase «passe» a profondément changé la portion chiffrée.

Voici pour la totalité du message:

Phrase "abcaabacaabacccaba" → uot egaCttnemel tedifnos l:leiandrooc ced seéntoteuqapsukooc en tnos s icalp ud tuah dearègatéa,ord edreotS .e ise ice pt.sem n

Phrase "abcaabacaabaccaba" → otS .e iord edrerègatéa,tuah deacalp ud tnos s ikooc en teuqapsud seéntodrooc cel:leianedifnos tnemel tot egaCt.sem nutpse ice

Principales observations

– Il est possible d’associer plusieurs phrases «passe», en fonction du nombre de relais: chacun peut ainsi avoir un «maillon de la chaîne» (principe du block-chain) lisible et le reste du contenu indéchiffrable. Utile pour avoir un relais sans confiance (il n’a pas la possibilité de connaître le contenu) ou par exemple donner des indications (envoyer le reste du contenu à tel relais si on envoie des paquets, effectuer un traitement / une vérification, etc).

– Le travail non directement sur des nombres sous Numpy, mais des matrices debits, change l’ordre du contenu et aussi la représentation envoyées: en effet, chaque bit étant rangé dans un ordre différent, la matrice revenue à une seule dimension, donnera des signes RADICALEMENT différents.

– Rendre publiques les opérations (et notamment la taille générique de la matrice), pour ne transférer secrètement que les phrases «passe» et le texte chiffré, économise BEAUCOUP de données transférées.

– Utiliser tous les signes usuels de l’alphabet, pour n’envoyer que des indications de ressources entre deux personnes, qui échangeront ensuite numériquement: ainsi la page 112 de telle édition de tel ouvrage sert de phrase «passe»… D’ailleurs la phrase peut être envoyée généralement par tout moyen sécurisé (connexion TSL, liaison optique polarisée, pigeon avec un entraînement militaire, bouteille à la mer… ah non pas la bouteille).

– Avoir un jeu de plusieurs alternatives pour une même opération et en avoir, à l’avance, déterminé l’usage: ainsi l’opération 1-1 est utilisée une fois, puis si elle est appelée à nouveau (pour une nouvelle portion) l’opération 1-2, puis si elle est appelée à nouveau l'opération 1-3, puis on revient à 1-1, etc. L’intérêt est de rajouter un (gros) grain de sable et de rendre pratiquement impossible à déterminer une série d’opérations, pourtant toutes connues par le potentiel espion...

– Une telle méthode est idéale pour «couper» le chiffrement d’un contenu très important en une multitude de portions, permettant l’usage facilité de l’asynchronisme.

Edition - ajout d'un exemple plus complet

Voici un exemple complet, asynchrone, qui n'utilise pas Numpy et à vocation pédagogique:


import re

class MatriceSimple:

debug = False

MATRICE_taille_colonne = 8
OPERATIONS = {}

operations_binaires = False

def __init__(self, contenu_original, binaire=False ):
self.contenu_original = contenu_original
self.matriceComplexe = False
self.operations_binaires = True if binaire is True else False

def __log__(self, *args):
"""méthode de log interne; à surcharger"""
if self.debug:
print(*args)

def peupler(self):
if self.operations_binaires:
matriceSimple = list(
"".join(
(
bin(ord(signe))[2:]
).rjust(8,"0") for signe in self.contenu_original
)
)
else:
matriceSimple = list(self.contenu_original)
yield
self.matriceComplexe = [
[]
]
y = 0
for bit in matriceSimple:
if len(self.matriceComplexe) >= self.MATRICE_taille_colonne:
self.matriceComplexe.append(
[]
)
y += 1
self.matriceComplexe.append(
bit
)
yield

def crypter(self, phrase, inverse=False):
yield from self.__matrice_transformer__(
phrase if inverse is False else phrase[::-1],
inverse
)

def decrypter(self, phrase):
yield from self.crypter(
phrase,
True
)

def __matrice_creer__(self):
yield
matriceSimple = list(
"".join(
(
bin(ord(signe))[2:]
).rjust(8,"0") for signe in self.contenu_original
)
)
yield
self.matriceComplexe = [
[]
]
y = 0
for bit in matriceSimple:
if len(self.matriceComplexe) > self.MATRICES_taille:
self.matriceComplexe.append(
[]
)
y += 1
self.matriceComplexe.append(
bit
)
yield

def __matrice_transformer__(self, phrase, inverse):
for op_id in phrase:
try:
fct = getattr(
self,
"operation_%s"% op_id
)
self.__log__(
"opération '%s' demandée:%s "% (
op_id,
fct.__doc__
)
)
yield from fct(
op_id,
inverse
)
except:
raise ValueError("cette opération '%s' n'existe pas"% op_id)

def extraire(self):
matrice = yield from self.__matrice_reduire__()
message = yield from self.__matrice_traduire__(
matrice
)
return message

def __matrice_reduire__(self):
if self.matriceComplexe is False:
raise Exception(
"aucun contenu encore crypté"
)
bits_modifies = []
for ligne in self.matriceComplexe:
for bit in ligne:
bits_modifies.append(bit)
yield
returnbits_modifies

def __matrice_traduire__(self, matriceSimple):
message = []
if self.operations_binaires:
for bit in re.finditer(
"({8})",
"".join(matriceSimple)
):
message.append(
chr(
int(
bit.group(0),
2
)
)
)
yield
else:
for signe in matriceSimple:
message.append(
signe
)
yield
return "".join(message)

class CryptRapide(MatriceSimple):

def operation_A(self, op_id, inverse=False):
"""décalage d'une ligne"""
ancienne_matrice = self.matriceComplexe[:]
yield
if inverse:
self.matriceComplexe = [ancienne_matrice[-1],]+ancienne_matrice[0:-1]
else:
self.matriceComplexe = ancienne_matrice[1:]+[ancienne_matrice,]

def operation_B(self, op_id, inverse=False):
"""décalage d'une colonne dans chaque ligne"""
ancienne_matrice = self.matriceComplexe[:]
yield
nouvelle_matrice = []
if inverse:
for ligne in ancienne_matrice:
ligne = ligne[:]
nouvelle_matrice.append(
[ligne[-1],] + ligne[0:-1]
)
yield
else:
for ligne in ancienne_matrice:
ligne = ligne[:]
nouvelle_matrice.append(
[*ligne[1:], ligne]
)
yield
self.matriceComplexe = nouvelle_matrice

def operation_C(self, op_id, inverse=False):
"""inversion des lignes"""
ancienne_matrice = self.matriceComplexe[:]
yield
nouvelle_matrice = []
for ligne in ancienne_matrice:
nouvelle_matrice.append(
ligne[::-1]
)
yield
self.matriceComplexe = nouvelle_matrice

def auto(binaire, phrase_id, phrase, texte_original):
global verrou_affichage
ma_matrice = CryptRapide(
texte_original
)
ma_matrice.operations_binaires = binaire

yield from ma_matrice.peupler()
print("! log (%s): La matrice du contenu a été créée"% phrase_id)

yield from ma_matrice.crypter(
phrase
)
print("! log (%s): le contenu a été crypté"% phrase_id)

valeur_message = yield from ma_matrice.extraire()
print("! log (%s): message crypté:"% phrase_id, valeur_message)

yield from ma_matrice.decrypter(
phrase
)
print("! log (%s): message décrypté:"% phrase_id)

valeur_message = yield from ma_matrice.extraire()
print("! log (%s): message décrypté:"% phrase_id, valeur_message)

return "Fin de la tache%s"% phrase_id

def boucle_asynchrone(listes_taches):
taches_generateurs = []
for tache in listes_taches:
fct, *args = tache
taches_generateurs.append(
fct(*args)
)
while True:
try:
tache = taches_generateurs.pop(0)
next(tache)
taches_generateurs.append(
tache
)
except StopIteration as err:
print(">>> Le générateur a terminé et dit: ", err)
if len(taches_generateurs)==0:
break

if __name__=="__main__":


#VERSION NON-BINAIRE -> moins efficace
boucle_asynchrone(
[
(
auto, # fct appelée dans la boucle événementielle
False, # ne sera pas traitement binairement
1, # id de la tache
"AAACBABCBCABACBBB", # phrase passe
"Ceci est un super message secret, plus long \
mais proportionnellement il y a moins de traitements, \
c'est bizarre hein? Mais c'est comme ça, il fallait un exemple..." # contenu du message
),
(
auto,
False,
2,
"AAACBABCBCABACBACBBCAAABBBB",
"Ceci est un message secret de Nothus (Julien Garderon, août 2017)."
)
]
)

print("- - - - - - - - - - - - - - -")

#VERSION BINAIRE -> plus efficace (car la matrice générée est plus grande; plus de dimensions (3, 4, ... au lieu de 2D utilisées dans cet exemple) ou une taille de phrase plus grande = plus de sécurité)
boucle_asynchrone(
[
(
auto,
True,
1,
"AAACBABCBCABACBBB",
"Ceci est un super message secret, plus long \
mais proportionnellement il y a moins de traitements, \
c'est bizarre hein? Mais c'est comme ça, il fallait un exemple..."
),
(
auto,
True,
2,
"AAACBABCBCABACBACBBCAAABBBB",
"Ceci est un message secret de Nothus (Julien Garderon, août 2017)."
)
]
)