Logicielsmoto.com http://www.logicielsmoto.com/phpBB/ |
|
Algorithmes crypto http://www.logicielsmoto.com/phpBB/viewtopic.php?f=3&t=663 |
Page 1 sur 1 |
Auteur: | Fool-DupleX [ 07 Fév 2022, 09:53 ] |
Sujet du message: | Algorithmes crypto |
Je cherche à implémenter sur 6809 de la manière la plus efficace possible les algorithmes suivants : CRC-32, MD5, SHA-1, IDEA, TEA et AES. J'ai trouvé un site très intéressant d'un gars qui a étudié la chose pour certains d'entre eux sur 80386. Est-ce que quelqu'un a vu quelque chose de similaire pour z80 ou 6502 ? https://www.nayuki.io/category/programming Note 1 : je sais que CRC-32 c'est pas de la crypto, mais c'est utile. Note 2 : je sais que MD5 est pété et SHA-1 pas terrible, mais je me proposais de commencer par les trucs que je maitrise a peu près avant d'attaquer SHA-256 ou SHA-3 ... |
Auteur: | Fool-DupleX [ 07 Fév 2022, 11:59 ] |
Sujet du message: | Re: Algorithmes crypto |
Bon je me lance. CRC-32 peut être implementé en vitesse avec une table précalculée de 1 Ko (256 valeurs de 32 bits) et une boucle qui parcourt le buffer d'entrée avec le code suivant : Code: crc:32 = (crc:32 >> 8) ^ table:32[(crc:32 & 0xff) ^ octet:8] ou octet est l'octet dans le buffer et crc la valeur temporaire du crc à chaque tour de boucle. [(crc:32 & 0xff) ^ octet] c'est assez facile. Si on dit par exemple que Y est le pointeur sur le buffer et que le crc est sur la pile, on peut faire : Code: LDA 3,U EORA ,Y+ ROLA ROLA Du coup j'ai imaginé le code naïf suivant pour un tour de boucle, avec X qui pointe sur la table de crc: Code: LDA 3,U EORA ,Y+ ROLA ROLA LDB A,X EORB 2,U STB 3,U INCA LDB A,X EORB 1,U STB 2,U INCA LDB A,X EORB ,U STB 1,U INCA LDB A,X STB ,U Je me demande si on peut faire mieux, par exemple en découplant les valeurs 32 bits dans la table : d'abord les 256 valeurs de l'octet 0, ensuite les 256 valeurs de l'octet 1, etc. pour virer le INCA, mais recharger chaque fois X avec le pointeur de chaque sous-table est couteux aussi. il faut aussi stocker la valeur de fin de Y quelque part ou utiliser un compteur. Peut-être sur la pile ? Edit: mince non, ca marche pas, ROLA ROLA c'est une valeur sur 10 bits. |
Auteur: | Fool-DupleX [ 07 Fév 2022, 13:20 ] |
Sujet du message: | Re: Algorithmes crypto |
Code corrigé, avec séparation des octets dans la table, la longueur des données dans A (max 256) : Code: PSHU A
LOOPCRC: LDA 4,U EORA ,Y+ LDX #TABLE3 LDB A,X EORB 3,U STB 4,U LDX #TABLE2 LDB A,X EORB 2,U STB 3,U LDX #TABLE1 LDB A,X EORB 1,U STB 2,U LDX #TABLE0 LDB A,X STB 1,U DEC ,U BNE LOOPCRC |
Auteur: | Samuel Devulder [ 08 Fév 2022, 09:43 ] |
Sujet du message: | Re: Algorithmes crypto |
Faute d’écran adéquat je n’ai pas trop poussé l’analyse, mais il y a 2/3 trucs bizarres dans le code:
Côté optim je ferais ainsi: Code: LOOP:
LDB ,Y+ ; LECTURE OCTET EORB 3,U ; (CRC32&255) ^ OCTET LDX #TABLEAU3 ABX LDB ,X EORB 2,U STB 3,U LDB TABLEAU2-TABLEAU3,X EORB 1,U STB 2,U LDB TABLEAU1-TABLEAU3,X EORB ,U STB 1,U LDB TABLEAU0-TABLEAU3,X STB ,U DECA BNE LOOP |
Auteur: | Fool-DupleX [ 08 Fév 2022, 14:27 ] |
Sujet du message: | Re: Algorithmes crypto |
Pas mal la technique de l'offset,X en soustrayant les pointeurs de tableau ! Le U au lieu de S, c'est juste un choix arbitraire. On peut mettre S. J'ai deux nouvelles versions à vous soumettre. La premiere basée sur le même principe du coup, et la seconde qui est l'algorithme original, donc plus de tables, mais plus lent. Par contre beaucoup plus compact, forcément. Ca fonctionne, mais c'est pas optimisé. Code: ; A = longueur des data (max. 256) ; Y = Pointeur sur les data ; Le vecteur d'initialisation est poussé sur la pile (4 octets) ; En sortie, le CRC32 est à la place du vecteur d'initialisation CRC32 EQU * COM 4,S COM 3,S COM 2,S COM 1,S LOOPC LDB 4,S EORB ,Y+ LDX #TABLE0 ABX LDB ,X EORB 3,S STB 4,S LDB TABLE2-TABLE3,X EORB 2,S STB 3,S LDB TABLE1-TABLE3,X EORB 1,S STB 2,S LDB TABLE0-TABLE3,X STB 1,S DECA BNE LOOPC COM 4,S COM 3,S COM 2,S COM 1,S RTS Et le code de l'algorithme sans tables (1er jet fonctionnel) : Code: ; En entrée, vecteur d'initialisation, pointeur sur data, pointeur sur fin de data poussés sur la pile ; En sortie, le CRC-32 prend la place du vecteur d'initialisation sur la pile CRC32 LEAS -1,S LDY 3,S COM 5,S COM 6,S COM 7,S COM 8,S NEXT LDA 8,S EORA ,Y+ CMPY 1,S BHI FIN STA 8,U LDA #8 STA ,S SCROLL LSR 5,S ROR 6,S ROR 7,S ROR 8,S BCC SKIP LDD 7,S EORA #$83 EORB #$20 STD 7,S LDD 5,S EORA #$ED EORB #$B8 STD 5,S SKIP DEC ,S BNE SCROLL BRA NEXT COM 5,S COM 6,S COM 7,S COM 8,S LEAS 5,S RTS Sachant que le pseudo-code a implementer est : Code: r = ~r;
for(;;) { x = fgetc(f); // next character if (feof(f)) break; r^=x; if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } if (r&0x01) { r = (r>>1)^0xedb88320; } else { r >>= 1; } } printf("CRC32=%08x\n", ~r); |
Auteur: | Yoann Riou [ 08 Fév 2022, 15:37 ] |
Sujet du message: | Re: Algorithmes crypto |
Je ne connaissais pas cette syntax en C Code: for(;;) { ... } J'utilise plutot ca : Code: while(true) { ... } Mais ca m'intrigue |
Auteur: | Samuel Devulder [ 08 Fév 2022, 15:48 ] |
Sujet du message: | Re: Algorithmes crypto |
Oui le for(;;) vide existe et est un forever (le test est toujours vrai) dont on sort avec un break. Sinon Fool dans le 1er algo ya un truc qui colle pas. Tu utilises A pour lire la données, mais tu fais tout le travail sur B après (qui n’a pas été initialisé). Il faut utiliser B partout à la place de A (sinon le ABX fait n’importe quoi), et garder A comme compteur. Du coup pas besoin de le sauvegarder. C’est plus court et plus rapide (cf mon code plus haut). Dans le 2e algo le LEAS 5,S final me semble suspect. Il ne colle pas avec le LEAS -1,S du début, et du coup le RTS dépile la partie haute du CRC32. tu voulais sans doute zapper de la pile le pointeur sur la fin des data. Il faudrait faire un truc genre Code: LDX 1,S ; RECUP ADDR RETOUR LEAS 5,S ; SAUTE AU DESSUS COMPTEUR + ADDR FIN + ADDR DEBUT, DONC S POINTE SUR LE CRC32 A PRÉSENT (TRUC: C’EST A DIRE U DANS LE CODE PLUS LOIN ====> LEAS, U qui est plus rapide) JMP ,X ; retour à l’appellant Côté optim, pour la version sans table j’aurais écrit la partie SCROLL ainsi pour minimiser les accès mémoires.(En gros je stocke le crc32 dans le couple D/X) Code: LEAU OFFSETDUCRC32,S ; toujours pratique de pointer sur la donnée importante pour maximiser les ,U au lieu de const,U
... LDA #9 STA ,S PULU D,X ; D=PARTIE HAUTE DU CRC BRA SCROLL2 ; OU MIEUX LA MACRO SKIP2 UTILISEE DANS LA ROM ! SCROLL1 EXG D,X SCROLL2 DEC ,S BEQ SCROLL3 LSRA RORB EXG D,X RORA RORB BCC SCROLL1 EORA #$83 ; partie basse EORB #$20 EXG D,X EORA #$ED ; partie haute EORB #$B8 ; donc pas de exg sur ce chemin BRA SCROLL2 SCROLL3 PSHU D,X ; écriture du crc32 à sa place |
Auteur: | Fool-DupleX [ 08 Fév 2022, 17:14 ] |
Sujet du message: | Re: Algorithmes crypto |
Citation: Dans le 2e algo le LEAS 5,S final me semble suspect. Il ne colle pas avec le LEAS -1,S du début, et du coup le RTS dépile la partie haute du CRC32. Non, non, c'est bon. Ce qui est depile c'est les pointeurs de debut et fin de data. Il reste le crc32 sur la pile (testé et approuvé) Edit: ah m* tu as raison, c'est que moi j'utilise U dans mon code ... Yoann, et celle-la, t'en penses quoi ? Code: for (k=r=~0;++k&7||(r^=x=fgetc(f),x<~x);r=r%2*0xEDB88320^r/2); Un CRC-32 en une seule ligne de C et un seul statement (for). Edit 2 : j'ai corrigé le code du premier algo et les bools n'existent pas en C (donc true non plus). |
Auteur: | Yoann Riou [ 08 Fév 2022, 17:30 ] |
Sujet du message: | Re: Algorithmes crypto |
Ca me rappel mon prof the C++ en IUT, des trucs de dingue qu'il faisait de cette facon |
Auteur: | Samuel Devulder [ 08 Fév 2022, 17:38 ] |
Sujet du message: | Re: Algorithmes crypto |
Je suis surpris que ça plante pas. En fin de code on trouve COM 5,S donc 5,s pointe sur la partie haute du crc32. Ensuite on fait LEAS 5,S donc S pointe à présent sur le crc32 comme tu l’indiques. Mais vient alors le RTS qui dépile cette partie haute du CRC et la place dans le PC. Ça devrait planter.... quelque chose m’echappe, ce qui est fort possible vu la taille de mon écran Yoann tu connais pas le concours IOCCC ? Regardes la tronche du gagnant 2002 (un français, auteur de TCC, Qemu, détenteur du record des décimales de pi à une époque, etc) |
Auteur: | Fool-DupleX [ 08 Fév 2022, 17:43 ] |
Sujet du message: | Re: Algorithmes crypto |
Te bile pas Sam. Moi j'utilise U pour la pile, ce qui devrait être la norme, U pour utilisateur, S pour système. Dans OS-9, c'est comme ça. En voulant modifier le code pour le mettre dans le fil, j'ai fait des bêtises. J'ai pas pensé que le PC était passé sur la même pile. Je remets tout ça d'équerre, je teste et je vous redis. Maintenant, je vais attaquer MD5. C'est beaucoup plus long à coder, mais il n'y a rien de vraiment sorcier. |
Auteur: | Samuel Devulder [ 09 Fév 2022, 16:58 ] |
Sujet du message: | Re: Algorithmes crypto |
J’ai vaguement regardé un md5 en C. Il y a des décalage sur 32 bits de pas variables, de la lecture bit à bit de l’entrée. Vu de loin ça a l’air chiant à écrire en ASM, non ? C’est là que je trouve qu’il nous manque un compilo C potable car certains algos sont pénibles et peu optimisables en asm. |
Auteur: | fxrobin [ 10 Fév 2022, 13:58 ] |
Sujet du message: | Re: Algorithmes crypto |
Il existe CMOC. http://perso.b2b2c.ca/~sarrazip/dev/cmoc.html je n'ai pas testé. Tu as déjà testé peut-être |
Auteur: | Fool-DupleX [ 11 Fév 2022, 10:04 ] |
Sujet du message: | Re: Algorithmes crypto |
gcc supporte aussi le 6809 mais assez mal et il y avait un compiler C sous OS-9 dès les années 80. J'aimerais bien d'ailleurs (voeu pieux, j'ai pas le temps), porter ce compilateur C natif. Le compilateur C OS-9 tourne sans modification sur notre OS-9, par contre pour l'utiliser sur une machine Thomson classique, il faut évidemment modifier les appels système pour les fichiers les trucs comme ça. Le moteur du compilateur ne devrait pratiquement pas bouger. --> http://archive.worldofdragon.org/browse/?dir=downloads/Software/Dragon/Dragon%20Data%20Ltd/OS-9/C%20Compiler Je peux vous extraire le listing desassemblé si vous voulez. Bien sur que ce sont des manipulations de bits. La crypto ce n'est que des manipulations bit à bit, avec des xor et des modulos. Tout est dans la manière de mélanger lesdits xor et modulos. MD5 utilise une fonction non linéaire, sinus par défault, pour distribuer l'entropie de round en round. C'est sa seule originalité par rapport à d'autres algos de hash. Mais il est faible et comporte beaucoup de collisions. Ca reste très utilisé et le moins complexe à implémenter. Mon but en l'occurence est justement de ne pas utiliser un compilateur. On trouve ici : https://www.nayuki.io/page/fast-md5-hash-implementation-in-x86-assembly une personne courageuse qui l'a écrit 100% assembleur pour IA-32. Edit: ou bien est-ce que ton idée était de partir du code généré par le compilateur pour l'améliorer ? |
Auteur: | Samuel Devulder [ 11 Fév 2022, 12:38 ] |
Sujet du message: | Re: Algorithmes crypto |
Pas d’idée particulière, mais reprendre à la main un code asm généré est pas mal pour se mettre en jambe avec un algo complexe. On voit assez vite les trucs à faire autrement quand on passe au full asm. |
Page 1 sur 1 | Heures au format UTC + 1 heure |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |