Misez p'tit Optimisez n°72 : chiffrement par transposition

[dprtl]

Au moment où j'écris ces lignes, nous sommes vendredi soir, c'est déjà le week-end, et c'est l'heure d'un petit MPO !

Le chiffrement par transposition (ou chiffrement par permutation) consiste à changer l'ordre des caractères, et donc à construire des anagrammes. Ici, les messages contiendront uniquement des chiffres, de 0 à 9, pour ne pas pénaliser les calculettes les plus anciennes, qui ne gèrent pas toujours les caractères alphanumériques.

Dans cet énoncé, les messages échangés, ainsi que la clé, sont d'une longueur fixe, égale à 10 caractères. Par exemple : C = 3465710298. La clé C indique dans quelle position il faut permuter les caractères du message initial pour opérer le chiffrement. Par exemple, si on entre le message en clair A = 6765837379, le programme calcule avec la clé C le message B chiffré = 7336756897. Le 6 du début se retrouve en 4e position (3 en partant de zéro), le 7 en 5e position (ou 4 en numérotant à partir de zéro), et etc.



Comme l'algorithme est assez "simple", le temps de calcul devrait être réduit, et à la portée de la plupart des pockets. J'ajoute une contrainte : le même programme devra être capable de chiffrer et de déchiffrer les messages de 10 caractères. Si l'entrée A est un nombre de positif, alors le programme doit chiffrer A avec la clé C. Sinon, si A est négatif, il faut déchiffrer le message A (avec la même clé partagée). La clé C pourra être stockée en dur dans le programme, ou bien dans un registre séparé.

Par exemple, toujours avec C = 3465710298 :

• si entrée A = -7336756897
• sortie B = 6765837379 (message déchiffré)

On peut remarquer qu'un message numérique de 10 chiffres peut éventuellement cacher 5 codes ASCII, de 00 à 99, pour transmettre un message textuel. Sur l'exemple précédent, B en clair = 67 65 83 73 79 = CASIO. En bonus, votre programme devrait être capable de déchiffrer correctement un message qui commence par un zéro.

À vos claviers !

(Sommaire des MPO)

[zpalm]

Pas mal ce MPO, pas aussi simple qu'il n'y paraît

Voici une première solution sur WP 34S en 50 pas (100 octets), la clé est préalablement stockée dans le registre K :

Code : Tout sélectionner

01 LBL A
02 LocR 002
03 #10
04 STO.00
05 DROP
06 x<0?
07 XEQ 00
08 RCL K
09 XEQ 01
10 9
11 -
12 ABS
13 10^x
14 x<> Z
15 XEQ 01
16 RCL*T
17 STO+.01
18 <>ZYZT
19 DSZ.00
20 BACK 011
21 RCL.01
22 RTN

23 LBL 00
24 LocR 002
25 ABS
26 #10
27 STO.00
28 DROP
29 RCL K
30 XEQ 01
31 9
32 -
33 ABS
34 10^x
35 RCL.00
36 DEC X
37 *
38 STO+.01
39 DROP
40 DSZ.00
41 BACK 011
42 x<>.01
43 RTN+1

44 LBL 01
45 SDR 001
46 IP
47 RCL L
48 FP
49 SDL 001
50 END

Ce programme utilise la même routine pour chiffrer et déchiffrer, si le nombre de départ est négatif on n'utilise pas la clé K mais son inverse calculée par la routine LBL 00.

[zpalm]

Et une autre version pour HP Prime :

Code : Tout sélectionner

EXPORT MPO72(a)
BEGIN
LOCAL Key:="3465710298",la,lb:={},j,b:=STRING(ABS(a));
  la:=REPLACE(REPLACE("",11-DIM(b),b)," ","0");
  FOR j FROM 1 TO 10 DO
    IF a≥0 THEN
      lb(Key(j)-47):=la(j);
    ELSE
      lb(j):=la(Key(j)-47);
    END;
  END;
  RETURN EXPR(CHAR(lb));
END;

[C.Ret]

Voici, une version pour SHARP PC-1211:

J'étais arrivé à des programmes bien structurés et symétriques où tout été fait deux fois, une fois pour chiffré et une fois pour déchiffré.
Ces programmes étaient clairs, didactiques et facile à expliquer. Mais, ils était un peu longs pour un M.P.O.


Alors, j'ai comme à la coutume, bien passer ces codes à la moulinette MPO-tesque afin d'en tirer un petit code optimisé et invraisemblable. Je n'ai malheureusement pas réussi à faire moins de 153 octets de programme utilisant une dizaine de registres.

Le principe est que le signe de la donnée initiale saisi par l'utilisateur défini le mode codeur ou décodeur. Ce mode est mémorisé dans la variable M (M=1,2 ou 3) qui sert alors directement mémoriser le résultat de la donnée initiale ainsi qu'au le jeu de basculement des indices A(3+M) ou A(7-M). Le code est donc très vite plus difficile à comprendre et à expliquer.

En effet, si A, B et C sont respectivement le nombre initial , le nombre transposé et la clé de transposition, on se rend compte de la similitude des opérations de chiffrement et déchiffrement:

Code : Tout sélectionner

Chiffrement/Transposition
Pour i<--0..9
   B(C(i))<--A(i)            x<--C(i),B(x)<--A(i)       x<--C(i),B(x)<--U(i)

Déchiffrage/Rétablissement:
Pour i<--0..9
   A(i)<--B(C(i))            x<--C(i),A(i)<--B(x)       x<--C(i),A(i)<--U(x)

Les deux opérations peuvent être décomposées en deux étapes.
La première est commune au deux modes et consiste à lire séquentiellement les indices x de transposition dans la clé de chiffrement x<--C(i) (cet indice sera mémorisé dans le registre D).
La seconde consiste à placer la valeur du nombre initial à la bonne place (en fonction de x) dans le nombre résultat. Le nombre initial ou le résultat dépendant du sens de la transformation.

Pour simplifier, appelons U la donnée initiale (c'est à dire le nombre en clair pour le codage et inversement le nombre codé pour un déchiffrement). Dans le premier cas, il faut construire B en plaçant chaque élément U(i) à la positon x dans B pour le codage (construction de B). réciproquement, if faut construire A en plaçant élément U(x) à la positon i dans A pour le décodage.

C'est le même procédé, avec cependant une symétrie dans le rôle de la destination (A ou B) et des indices (x et i inversé entre les deux modes). La donnée étant U pour simplifier et ne pas avoir à tenir compte de la symétrie entre B et A. (De toute façon, U est donné par l'utilisateur, simplifions, minimisons,...)

Le code présenté ci-dessous, utilise cette symétrie en jouant sur les adresses des registres mémoire utilissé dan l'un et l'autre des deux modes. Le tableau ci-dessous tente de résumer le principe d'interversion d'indices et le déroulement des procédures de codage et décodage.
On se rend compte alors qu'un même sous-programme peut être utilisé afin d'extraire des nombres A,B ou C la i-ième position. Le premier appel de ce sous-programme sert à trouver x à partir dans la clé, le second appel permet de trouver l'argument nécessaire à la construction séquentielle du résultat (A ou B selon le mode codage/décodage) et à placer cela au bon endroit (positon x ou i selon le cas).

Dans le code ci-dessous, il y a un piège, car A est mémorisé dans le registre C, C dans B et B dans A, les indices i et x sont respectivement mémorisé dans les registres F et D. Seul U est effectivement à sa place dans le registre U. Les registre X,Y et Z étant les arguments du sous-programme extrayant un chiffre Z <-- Y(X) MOD 10 qui est utilisé pour obtenir x<--C(i), a<--B(i) et b<--A(x)

Code : Tout sélectionner

                           SS-Prg 1    Mode codeur    Décodeur      SS-Prg 2   Combiné Codeur/Décodeur    
UserData   Mode  Resultat  Z = Y(X)     B(j) = A(i)    A(i) = B(j)   Z<-Y(X)    A(M) =  A(M) +- Z * 10^?  (?:) :::  
   U        M     A(M) 
  U>0       3     C        D   B F      C D    U F  --------------   Z  U F     C 3:    C 3:  - z      D   4   7-M  ----- Code
  U=0       2     B  ---------------------------------------------------------------------------------------------------- Set B
  U<0       1     A        D   B F     -------------   A F    U D    Z  U D     A 1:    A 1:  + z      F   6   7-M  ----- Décode

Les registres indiqués dans ce tableau correspondent à l'utilisation suivante de la mémoire du SHARP PC-1211:

Code : Tout sélectionner

MEM  : Désignation        Calculs           
001 A:  Nombre en clair     A(i) <-- U(j)   avec j=B(i)  et   U<0   (mode décodeur) 
002 B:  Clé codage          B  
003 C:  Nombre codé         C(j) <-- U(i)   avec j=B(i)  et   U>0    (mode codeur)
004 D:  Indice j            D    <-- B(F)   Indice lu dans clé de codage    (tout mode)
006 F:  Indice i          Indice de la boucle FOR/TO/NEXT principale (Attention aux puissances de 10 inversées)
013 M:  Mode                M <-- 2+SGN U
021 U:  User's input      Donnée d'entrée
024 X:  indice extracteur   X donnée sous-programme 4:   X <-- F (appel initial)  X <-- D   (appel décodeur)  X <-- F (appel codeur)
025 Y:  Source              Y donnée sous-programme 4:   Y <-- B (appel initial)  Y <-- U   (appel tout mode) 
026 Z:  module              Z résultat ss-programme 4:   Z --> j (appel initial)  puis Z --> U(i) ou U(j) à placer en #F ou #D selon modes 

Qui permet l'exploitation du code suivant:

Code : Tout sélectionner

 1:" " AREAD U:M=2+SGN U,A(M)=0:IF BU=0 LET B=U:GOTO 3                                                 35o
 2:FOR F=9 TO 0 STEP -1:Y=B,X=F:GOSUB 4:D=9-Z,Y=U,X=A(3+M):GOSUB 4:A(M)=A(M)-SGN U*Z*10^A(7-M):NEXT F  73o
 3:"=" PRINT U,A(M):PRINT B:END                                                                        18o
 4:Z=ABS Y/10^X,Z=INT Z-10*INT .1Z:RETURN                                                              27o
                                                                                                      153 octets

Pour changer ou initier un nouvelle clef, il suffit d'effacer la mémoire (CLEAR), de la saisir et de lancer le programme par [DEF][SPC]. Le pocket affiche la nouvelle clef. Alternativement, la clé peut être effacée en saisissant 0.. La saisie suivante serviera alors de nouvelle clé comme après un CLEAR. Quelque soit la méthode, ce code ne vérifie pas la validité de la clé de transposition.
Pour coder un nombre, le saisir comme un nombre positif et faire [def][SPC] . Le nombre transposé s'affichera alors à droite du nombre précédemment saisi. Une pression sur la touche enter permet d'afficher la clef en cours.
Pour décoder saisir un nombre négatif et lancer le programme par [def][SPC] le résultat du décodage s'affichera alors à droite du nombre saisi.Notons qu'à partir de ce dernier affichage, [def][SPC] permet de retrouver le nombre initial, puisque la fonction AREAD lit automatiquement le nombre affiché sur la droite de l'écran.

Code : Tout sélectionner

Saisie                  Affichage                    Commentaire
----------------------  -------------------------    ------------------------------------------------------
[mode][mode]            >                              Mettre le poket en mode DEF
CL.[ENTER]              >                              Efface les registres
3465710298[def][SPC]     3465710298.          0.       Affiche nouvelle clé de transposition
6765837379[def][SPC]     6765837379.-7336756897.       Affiche le nombre et son transposé
[def][SPC]              -7336756897. 6765837379.       Effectue l'opération inverse et affiche le résultat.
[ENTER]                              3465710298.       Affiche la clé en cours.

[badaze]

Pour Sharp 1403.

Code : Tout sélectionner

10 DIM A$(0)*10, C$(0)*10,R$(10),P$(0)*10
20 C$(0) = "3465710298"
30 INPUT A$(0)
40 FOR I=1 TO LEN(A$(0))
50   P = VAL(MID$(C$(0),I,1))+1
60   R$(P) = MID$(A$(0),I,1)
70 NEXT I
80 FOR I=1 TO LEN(A$(0))
85   P$(0) = P$(0) + R$(I)
90 NEXT I
95 PRINT P$(0)
97 END

[ledudu]

Machine : Casio Pro fx-1
Langage : Fortran Casio

Je parcours la clef de droite à gauche, j'extrais un chiffre donnant la position P et je mets le chiffre correspondant du nombre à traiter à la position P de la clef en multipliant par 10^(9-P) et en totalisant dans un même registre.

Voici une version en 127 pas sur 127 pas dispos :
Registres :
0 : clef (initialisée hors programme) - stockée également au début dans le registre 8 pour la conserver intacte dans 0
1 : nombre à traiter
2 : code obtenu
6 : compteur (10->1)
SUB #9 : Sous programme d'extraction du chiffre de droite (pour la clef et le nombre à traiter). En entrée, il prend le registre 4 qui doit contenir soit la clef restant à analyser, soir le nombre à traiter restant. En sortie, il donne le chiffre de droite dans le registre 3 et le nombre en entrée décalé d'un chiffre à droite dans le registre 7.
Exemple, à la première itération, il est appelé deux fois :
- une première fois avec la clef 3465710298, il renvoie 8 et 346571029.
- une seconde fois avec le nombre 6765837379, il renvoie 9 et 676583737.
Et du coup, le code devient 0000000090
Et il y a dix itérations.

Code : Tout sélectionner

[001] ST#0:8=0:6=K10:9=6 10^x:2=K0:ENT 1:               / Initialisations
[027] ST#1:IF 6=K0:2:3:2:                               / Test compteur
[042] ST#2:4=8:GOTO 9:8=7:5=K9-3:                       / Traitement de la clef
[063]      4=1:GOTO 9:1=7:2=5 10^x * 3 +2:6=6-K1:GOTO 1:/ Traitement du nombre puis du code
[093] ST#3:ANS 2:GOTO 0:                                / Affichage du résultat
[102] SUB#9:7=4/K10-9+9:3=7*K10 +/- + 4:                / Sous programme 9

Rappel : il n'y a pas de fonction partie entière. Donc Ent(x)=x+10^10-10^10

Temps de réponse : 37"


J'ai peur de ne pas pouvoir gagner assez de place pour intégrer le décodage.

D'autres programmes pour PRO Fx-1.

[C.Ret]

Une version pour SHARP PC-1360, librement inspirée de la version présenté par Badaze:

Code : Tout sélectionner

1:AA$= LEFT$ (AA$,I-1) + MID$ (UU$,10-X,1): RETURN
3:AA$= LEFT$ (AA$,1+X) + MID$ (UU$,I,1) + RIGHT$ (AA$,9-X): RETURN

5:" " AREAD U:CC$="3465710298",AA$="-000000000",UU$= RIGHT$ (AA$+ STR$ ABS U,10)
7:FOR I=1 TO 10:X= VAL MID$ (CC$,I,1): GOSUB 2+ SGN U: NEXT I
9:"=" PRINT U,VAL AA$: PRINT VAL CC$: END

La clé de chiffrement est en clair à la ligne 10:.
Sinon, même utilisation, le nombre saisi est codé ou décodé selon son signe.

Code : Tout sélectionner

Saisie                  Affichage                    Commentaire
----------------------  -------------------------    ------------------------------------------------------
6765837379[def][SPC]     6765837379.-7336756897.       Affiche le nombre et son transposé
[def][SPC]              -7336756897. 6765837379.       Effectue l'opération inverse et affiche le résultat.
[ENTER]                              3465710298.       Affiche la clé en cours.

[dprtl]

Voici une version en 133 pas qui tourne sur une Casio FX-4000P. Mon code n'a rien de très exceptionnel ; mais il est sans doute lisible (?) grâce à l'usage de la fonction tableau de la Casio. Cette machine était un "milieu de gamme" abordable en 1985, et elle pèse 87g avec les piles.

L'algorithme est organisé en deux boucles :
- la première, en Lbl 0, qui calcule la clé "réciproque" dans le tableau U.
- la deuxième, à partir de Lbl 1, qui calcule B, en 10 étapes

Code : Tout sélectionner

?->A:0->I:Lbl 0:I->U[K[I]]:Isz I:I<10=>Goto 0:0->B:0->I:
Lbl 1:10x(9-I)->C:Int (Abs A/C)*C->D:A<0=>Goto 2:A-D->A:K[I]->E:Goto 3:
Lbl 2:A+D->A:U[I]->E:
Lbl 3:B+D/C*10x(9-E)->B:Isz I:I<10=>Goto 1:B&

Symboles spéciaux :

- '->' correspond à l'affectation d'une variable, touche [->]
- '=>' est l'implication, touche [shift][7]
- '10x' correspond à la fonction [shift][log]
- '&' est le triangle orange, touche [shift][:]

Utilisation :

1) Si besoin, modifier la partition mémoire pour pouvoir affecter jusqu'à la mémoire U[9] :

Code : Tout sélectionner

Defm 10

Ceci n'efface pas les mémoires.

2) Entrer la clé dans le tableau K, en profitant de l'éditeur Casio pour rappeler la commande précédente :

Code : Tout sélectionner

3->K[0]
4->K[1]
...
8->K[9]

3) basculer éventuellement en mode "Norm" ou "Fix 0" pour un affichage plus propre que "Sci"

4) lancer le programme, et répondre à la question en saisissant le message à crypter. Pour le décryptage, attention à bien utiliser le symbole (-). Le résultat s'affiche en 4 secondes environ.

[ledudu]

Salut
Sympas toutes ces versions.
Il y a deux algorithmes récurrents :
- les machines avec des fonctions alphas peuvent extraire directement un chiffre et parcourent la clef et le nombre de gauche à droite pour construire le code également en alpha,
- les machines sans alpha extraient la clef de droite à gauche en dépilant le chiffre des unités en divisant pas 10 et en positionnant le chiffre codé en multipliant pas 10^(9-p).

[C.Ret]

Effectivement, c'est bien sympa toutes ces versions.

Curieusement, il n'y a en a aucune utilisant le modulo...

Je corrige cette lacune en présentant une version en RPL.

Pour cette première version, les clés de codage et décodage sont en dur dans la définition des instructions:

Code : Tout sélectionner

Chiffrement par transposition
----------------------------------------
«                          ABS                                      | Prend la valeur absolue de l'argument
  { 3 4 6 5 7 1 0 2 9 8 } ALOG / IP                                 | Divise par les puissances de dix de chaque chiffre de la clé
                                 10 MOD OBJ→ →ARRY                  | Applique le modulo de 10 et transforme la liste en vecteur
                                                10 PEVAL NEG »      | Transforme le vecteur en  un nombre négatif (évaluation polynomiale)
                                                       '→TRNS' STO  | Mémorise le programme de codage


Déchiffrement de la transposition
----------------------------------------
«                          ABS                                      | Prend la valeur absolue de l'argument
  { 6 5 7 0 1 3 2 4 9 8 } ALOG / IP                                 | Divise par les puissances de dix de chaque chiffre de la clé contraposée
                                 10 MOD OBJ→ →ARRY                  | Applique le modulo de 10 et transforme la liste en vecteur
                                                10 PEVAL     »      | Transforme le vecteur en un nombre (évaluation polynomiale)
                                                       'TRNS→' STO  | Mémorise le programme de décodage

J'ai fait en sorte que l'indentation aligne les arguments de chaque opérateur. Ainsi ABS et ALOG sont alignés car leurs résultats sont tous deux les arguments de la division. Je ne suis pas sûr que cela rende le RPL plus clair !

Evidemment ces deux codes ne fonctionnent pas sur mon HP-28S, ils ne fonctionnent que sur les RPL évolués qui appliquent les instructions à chaque élément d'une liste.
Ainsi ALOG calcule les puissance de 10 de tous les éléments de la liste en argument. Comme pour ALOG t MOD, cela revient à faire 10x l'opération.
PEVAL est une astuce : [4 3 1 2] 10 PEVAL revient à évaluer le polynôme P(x)=4x^3+3x^2+x+2 au point x=10, et renvoi donc 4312.