Logicielsmoto.com

Nous sommes le 28 Mar 2024, 14:09

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 15 messages ] 
Auteur Message
 Sujet du message: Algorithmes crypto
MessagePosté: 07 Fév 2022, 09:53 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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 ...


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 07 Fév 2022, 11:59 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 07 Fév 2022, 13:20 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 09:43 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1802
Localisation: Brest
Faute d’écran adéquat je n’ai pas trop poussé l’analyse, mais il y a 2/3 trucs bizarres dans le code:
  1. pourquoi utilises tu le registre U comme pile au lieu de S? Convention FORTH?
  2. le tableau contient 256 valeurs 32 bits, soit 1ko. Or l’indexation A,X ne peut adresser que 256 octets. Je m’attendais à un D,X plutôt ou un ABX. Là 2e soluce avec 4 tableaux est une bonne idée, mais
  3. A,X est signé, donc lorsque A>=128 on déborde le tableau par le bas. Si bien que sans précautions A,X (X pointant au début d’un tableau) ne permet en pratique d’accéder â 128 octets. Il faut faire pointer X sur le milieu du tableau pour profiter des 256 octets adressables.
  4. pas de 4

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

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 14:27 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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); 


Dernière édition par Fool-DupleX le 08 Fév 2022, 17:24, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 15:37 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 492
Je ne connaissais pas cette syntax en C

Code:
for(;;) { ... }


J'utilise plutot ca :

Code:
while(true) { ... }


Mais ca m'intrigue :W


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 15:48 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1802
Localisation: Brest
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. :L 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

_________________
Good morning, that's a nice Tnetennba


Dernière édition par Samuel Devulder le 08 Fév 2022, 17:18, édité 1 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 17:14 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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 ? :W
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). :???: :lol:


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 17:30 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 492
Ca me rappel mon prof the C++ en IUT, des trucs de dingue qu'il faisait de cette facon :W


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 17:38 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1802
Localisation: Brest
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 :D (un français, auteur de TCC, Qemu, détenteur du record des décimales de pi à une époque, etc)

_________________
Good morning, that's a nice Tnetennba


Dernière édition par Samuel Devulder le 08 Fév 2022, 17:48, édité 2 fois.

Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 08 Fév 2022, 17:43 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 09 Fév 2022, 16:58 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1802
Localisation: Brest
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.

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 10 Fév 2022, 13:58 
Hors ligne

Inscription: 12 Fév 2021, 15:54
Messages: 78
Localisation: Rennes
Il existe CMOC. http://perso.b2b2c.ca/~sarrazip/dev/cmoc.html
je n'ai pas testé.
Tu as déjà testé peut-être

_________________
Fan de Atari 2600, Thomson MO5, Thomson TO8, Atari STE.
Retro-Codeur à mes heures perdues. https://www.fxjavadevblog.fr


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 11 Fév 2022, 10:04 
Hors ligne

Inscription: 06 Juin 2004, 08:23
Messages: 464
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 ?


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Algorithmes crypto
MessagePosté: 11 Fév 2022, 12:38 
Hors ligne

Inscription: 21 Aoû 2006, 09:06
Messages: 1802
Localisation: Brest
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.

_________________
Good morning, that's a nice Tnetennba


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 15 messages ] 

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Google [Bot] et 32 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages
Vous ne pouvez pas joindre des fichiers

Rechercher:
Aller à:  
Développé par phpBB® Forum Software © phpBB Group
Traduction par phpBB-fr.com