mercredi 1 avril 2009

Algorithme naïf de cryptage d'entrée

Je vous propose aujourd'hui un petit algorithme dans le domaine de la cryptographie, implémenté en Ruby. Comme vous allez le voir, il s'agit d'un algorithme à clef secrète générée aléatoirement au moment du chiffrement. Cette méthode est assez peu intéressante pour la plupart des applications de cryptage (transfert de message notamment) de par le fait que la clef doit être transmise afin que le destinataire puisse décrypter le message. Dans ce cadre, on utilise plus volontiers la cryptographie asymétrique (RSA, etc...), ou, pour des raisons de performances, une méthode symétrique dont la clef est cryptée de façon asymétrique.


En revanche, cet algorithme me semble utilisable pour un autre genre d'applications : de façon locale, afin de crypter une réception de donnée par exemple.

Contexte

Plusieurs hypothèses tout d'abord. La donnée à recevoir peut être accédée par morceaux (bits, lettres, chiffres, lignes, pages, etc...). On ne connait pas à priori sa taille. On suppose également que l'on peut pareillement accéder à un nombre important de données similaires.



Principe : Se fondre dans la masse

Le coeur de la méthode consiste à noyer l'information que l'on souhaite recevoir (notée A dans la suite, data dans le code) la recevant par morceaux, au milieu d'une foule d'autres informations similaires, de façon aléatoire.
Pour cela, on construit des "cycles" de taille aléatoire, dont seuls certains index (aléatoires eux-aussi) contiennent des parts de données intéressantes. La clé consiste en la liste des cycles utilisées (plus simplement, la liste des couples [occurences de part de A, taille du cycle]).

Le code

Dans mon implémentation en Ruby, j'applique l'algorithme à un tableau. L'input dummies correspond donc à une liste de données. La sortie est la paire [données cryptée, clé]

Cryptage :



A noter que je clone l'entrée data afin que la méthode soit non destructive sur celle-ci.

Décryptage :



On décrypte par morceau correspondant chacun à un cycle de la clef.

Exemple :

Pour tester cette méthode :



Ce qui donne un résultat du genre (pour rappel, la clef est profondément aléatoire...) de celui-ci.


Conclusion

Encore une fois, il s'agit d'une méthode naïve, à utilité limitée (je suis un grand débutant en crypto). Cependant, pour un usage local, elle me semble adaptée, bien que probablement peu performante en terme de vitesse (celle-ci étant conditionnée par l'ampleur des cycles et le nombre d'occurrences par cycle, ici en dur).
J'ai du mal à me figurer de grosses failles dans cet algorithme, si ce n'est pour ce qui est de l'utilisation de la randomisation : 1/ sa complexité étant dans l'absolue aléatoire, elle ne peut être calculée que par majoration dans le meilleur des cas (le meilleur des cas en crypto étant en fait le pire des cas en algorithmique), 2/ des failles existent sur des implémentations standards des méthodes random (présence de cycles, etc... Des méthodes plus abouties existent cependant, notamment celles utilisant des propriétés physiques du matériel informatique, comme la température par exemple).

Notes :
1/ Crédit photo : Jan Chipcase
2/ Ceci n'est pas un poisson d'Avril. J'aime pas cette tradition de clampes.