J'ai une question technique à propos de la fonction "rho-pi" définie telle que :
1
2
// Fonction 2 (ρ et π combinées)
B[y,2*x+3*y] = rotl(A[x,y], r[x,y]), forall (x,y) in (0…4,0…4)
Je me demande comment exprimer cette fonction de façon fonctionnelle. Plus particulièrement, pour ce qui est de la permutation (B[y,2x+3y]).
Pour effectuer la double boucle, une technique est de réaliser le produit cartésien entre deux ensembles (0..5) puis de mapper la liste de tuple qui en résulte. Le problème de cette technique c'est que je ne vois pas comment effectuer la rotation.
Chaque ligne de B est constituée à partir de la colonne correspondante de A et de r, donc si tu fais un transpose (ou fonction équivalente dans ton langage) sur A et r, tu peux définir une fonction qui prend une ligne de A et une ligne et r et en fait une ligne de B, que tu maperas sur [0..4].
Comment définir cette fonction alors ? Les éléments de la ligne 0 de A et r doivent être mis dans B dans l'ordre 0, 3, 1, 4, 2. Ceux de la ligne 1 doivent être dans l'ordre 1, 4, 2, 0, 3. Ceux de la ligne 2 doivent être dans l'ordre 2, 0, 3, 1, 4. Et ainsi de suite, en rotateant de 2 rangs vers la gauche à chaque fois.
Avec ça, tu devrais avoir de quoi écrire ta fonction rho-pi. N'hésite pas à la poster ici pour qu'on vérifie.
J'ai finalement implémenté l'algorithme keccak complet toujours en C99, le code se trouve ici.
Le principe général est de toujours travailler avec des entiers 64 bits pour la matrice contenant l'état interne et pour le découpage des données en entrée et en sortie.
Dans la fonction de permutation, il est donc nécessaire d'appliquer un masque binaire dépendant du nombre de bits significatifs (2^l) sur le résultat des calculs, notamment lors des rotations afin que les calculs ne soient pas faussés.
Pour la fonction éponge, la difficulté principale a été de gérer les cas ou la vitesse de production (r) n'est pas alignée sur 64 bits. C'est là qu'il a fallu un peu "cuisiner" les données à coup de décalages à gauche ou à droite, le remplissage d'un mot de l'état interne en entrée, ou du condensat en sortie se faisant alors en 2 étapes.
Le module spécifique sha3 a été conservé afin de pouvoir comparer les performances avec le module keccak sur les fonctions communes de génération de condensat au standard SHA-3, le code spécifique est environ 25% plus rapide.
Il y a un programme de tests pour chaque module: keccac_test et sha3_test. Comme dans la version précédente, il y a 2 paramètres à saisir sur l'entrée standard: le nombre de cycles de test et le flag d'affichage des résultats (0/1).
Ils intègrent tous les différents cas que j'ai testé, dont ceux fournis par Dominus Carnufex, ouf tous les résultats concordent j'étais loin d'en être certain jusqu'à mon test complet hier
Le code peut être compilé sous Linux ou Windows indifféremment, les makefiles et solutions Visual C++ 2010 sont incluses dans le dépôt github.
Chaque ligne de B est constituée à partir de la colonne correspondante de A et de r, donc si tu fais un transpose (ou fonction équivalente dans ton langage) sur A et r, tu peux définir une fonction qui prend une ligne de A et une ligne et r et en fait une ligne de B, que tu maperas sur [0..4].
Comment définir cette fonction alors ? Les éléments de la ligne 0 de A et r doivent être mis dans B dans l'ordre 0, 3, 1, 4, 2. Ceux de la ligne 1 doivent être dans l'ordre 1, 4, 2, 0, 3. Ceux de la ligne 2 doivent être dans l'ordre 2, 0, 3, 1, 4. Et ainsi de suite, en rotateant de 2 rangs vers la gauche à chaque fois.
Avec ça, tu devrais avoir de quoi écrire ta fonction rho-pi. N'hésite pas à la poster ici pour qu'on vérifie.
J'avais décidé de réaliser le projet en Rust pour découvrir le langage mais j'ai abandonné suite aux difficultés techniques, je suis passé au Haskell. Dès que j'aurai implémenté rho-pi, je mettrai le code correspondant.
Juste une petite question en Haskell, comment fait-on pour que cabal détecte les autres modules que le module principal dans le dossier src ? (J'ai un Could not find module ‘Util’).
Je ne sais pas dans quelle mesure ça fonctionne, c'est vrai qu'avoir quelques exemples ou des tests pour les fonctions intermédiaires serait apprécié.
[EDIT 22/09/2015] J'ai écrit les fonctions rotl et theta, je sais toujours pas si ça fonctionne (j'ai un doute,
je crois que rotl n'est jamais appelé). Par contre je peux déjà dire que la manipulation de bits en Python c'est pas de la tarte.
Héhé, je ne sais pas si mes résultats sont exacts, mais ma fonction permute() mets en tout cas une sacrée pagaille dans les bits de la chaîne passée en paramètre.
[EDIT] Je viens de comprendre dans quel ordre tout ça doit être effectué (bourrage -> éponge -> permutation -> condensat, si j'ai enfin compris) donc mon padding actuel est tout pourri…
J'essaie de réaliser ce défi, mais je ne comprends pas vraiment l'étape de padding. Un exemple pourrait peut-être m'aider à y voir plus clair.
On se place dans le cas de SHA-3 224 et on donne comme entrée la chaîne de 29 bits suivante (c'est celle de l'exemple du post initial) : 0110 0001 0110 0010 0110 0011 0011 0
Que devient cette entrée après l'étape de bourrage ?
Merci d'avance à ceux qui ont compris et qui voudront bien m'aider.
J'essaie de réaliser ce défi, mais je ne comprends pas vraiment l'étape de padding. Un exemple pourrait peut-être m'aider à y voir plus clair.
On se place dans le cas de SHA-3 224 et on donne comme entrée la chaîne de 29 bits suivante (c'est celle de l'exemple du post initial) : 0110 0001 0110 0010 0110 0011 0011 0
Que devient cette entrée après l'étape de bourrage ?
Merci d'avance à ceux qui ont compris et qui voudront bien m'aider.
Je vais t'indiquer comment j'ai implémenté le padding en C, mais suivant le langage et l'unité de base (bit/octet) que tu utilises la méthode ne sera peut-être pas la même pour toi:
Mon unité de base en C est l'octet, les 29 bits du buffer en entrée (avant padding) sont codés de la manière suivante
1
011000010110001001100011...00110
L'ajout des bits de padding se fait de droite à gauche dans un octet donc l'ordre d'ajout est le suivant, si je prends le dernier octet incomplet du buffer:
1
2
3
...0011087654321
Le padding à la norme SHA-3 est 011 au début, des 0 ensuite jusqu'au 1 final pour arriver à un multiple de r. Les premiers bits seront ajoutés en position 6/7/8 de l'octet incomplet ci-dessus, comme ceci:
1
2
3
1100011087654321
Avec la norme SHA-3 le padding est toujours calé sur des octets complets (ce n'est pas le cas avec Keccak ou r peut prendre n'importe quelle valeur entre 1 et 25*w bits), donc le 1 final sera en position 8 du dernier octet, et le buffer rembourré est comme ceci au final:
J'essaie actuellement d'implémenter l'algorithme dans mon langage du moment cad Python.
Mais je me suis rapidement retrouvé bloqué, notamment pour effectuer certaines opérations de bas-niveau comme la rotation (rotl). Si j'ai bien compris, rotl(x, i) décale les i fois les bits de x vers la gauche?
Je suppose qu'il est nécessaire de manipuler les données bit à bit, mais je ne sais pas vraiment comment m'y prendre. Si quelqu'un veut bien m'expliquer je le remercie d'avance
Connectez-vous pour pouvoir poster un message.
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
.
.
Mais merci quand même.
