Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 29-07-2016 10:59:34

ohkerod
Membre
Inscription : 28-07-2016
Messages : 2

Est ce solvable ? Coder /décoder

Bonjour,

Voilà il y a quelques jours pour m'amuser je me suis lancé dans un peu de programmation histoire de me dérouiller, puis j'ai fini par coder quelque chose qui me permet de transformer un mot en utilisant une logique que j'ai décidé.
une fois ça fait beh je me suis dit on va coder la partie qui va faire le chemin inverse pour le décoder.
Et donc la mon petit calvers à commencé....Est ce faisable ?

Voici la bête en question.

Je prend un mot à coder

BONJOUR

je code lettre par lettre en faisant la somme( rang dans l'alphabet) avec la suivante .
Si ça dépasse 26(nbre de lettres dans l'alphabet) je boucle.
Pour la dernière lettre du mot, la suivante correspond à la première.

B+O=2+15=17===>Q
O+N=15+14=31===>29>26===>29-26=3==>C
etc...
R+B===>T

BONJOUR donne
QCXYJMT


Le but maintenant est de partir de QCXJMT est de retomber sur le mot initial. C'est pas du tout aussi évident que ça en a l'air. Et je me demande même si il y a une équation qui permet d'exprimer le rang de chaque lettre initial en fonction du rang des lettres codés...

Si vous ne voulez pas être influencé et mener votre popre réflexion ne lisez pas la suite.
Au bout de ma réflexion j'ai pu obtenir :

Si la somme des X1(lettre cryptée)>26
alors

Sum(Xo(lettre initiale))%(modulo)26=(Sum(X1)%26)/2
et
Sum(Xo)=Sum(X1) +26-Sum(Xo)%26

sinon

Sum(Xo)=Sum(X1)/2

Pour illustrer ceci:

Si Sum(X1)>26

clair: 121 (QRT) ==>Sum(Xo)=55
codé: 332 (ILK)==>Sum(X1)=32

32+26-55%26=58-3=55

Sinon

clair: 121 (ABA) ==>Sum(Xo)=4
codé: 332 (CCB)==>Sum(X1)=8

Donc jusqu'ici je suis capable de connaitre la somme des lettres initiales ..mais je suis pas arrivé à aller plus loin...Je ne parviens pas à exprimer une équation pour chaque lettre initiale en fonction des lettres codés.
je suis arriver à un système d'équations +celle du dessus mais j'ai l'impression qu'il ya une redondance d'info...

Merci de votre aide et bon amusement

Hors ligne

#2 29-07-2016 16:55:27

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Est ce solvable ? Coder /décoder

Bonjour,


Bienvenue chez nous...
J'ai réfléchi et je suis sur une piste dont je ne suis pas sûr de savoir de ce que je vais en faire exactement.
"BONJOUR" comprend 7 lettres.
7 est impair.
Les lettres codées correspondent - avant de ramener les valeurs entre 1 et 26 - aux positions [17, 29, 24, 25, 36, 39, 20]
Si je soustrais une fois sur 2 :
17-29+24-25+36-39+20 = 4
4/2 = 2 et 2 est la position du B...
C'est - en principe - toujours vrai quand le nombre de lettres est impair...

Sinon, dans ce cas, dans le cas, il suffit bien de la ramener entre 1 et 26...
Si je ramène les valeurs entre 1 et 26, ça ne marche plus...
En effet :
S=17-3+24-25+10-13+20 = 30... et 30/2 ne donne pas 2.

Mais, il faut que je teste plus avant : (30%26)/2 = 2 , parce que ça marche avec KRACH, CROQUIS, CROQUET et CROQUETTE... (nb impair de lettres)...
Pour KRACH, S =-4, (-4%26)/2=11

Et la 11e lettre de l'alphabet est bien K
@+

[EDIT]
Prenons le cas de 7 lettres.
Soient a,b,c,d,e,f,g les positions initiales
Et p1=a+b, p2=b+c, p3=c+d, p4=d+e, p5=e+f, p6= f+g, p7=g+a
La somme avec signes alternés :
est S=p1-p2+p3-p4+p5-p6+p7 =a+b-b-c+c+d-d-e+e+f-f-g+g+a=2a
Si la somme ne dépasse pas 26, ok.
Sinon, il suffit de prendre (S%26)/2...

Maintenant, au tour d'un nombre pair de lettres...

Ah zut, ça ne colle plus avec XENON, sauf si mon script calculait faux dans ce cas ce que je ne crois pas à 99,9%. Je vérifierai quand même demain.
Pourtant en théorie, ça colle...

Dernière modification par yoshi (29-07-2016 18:40:31)


Arx Tarpeia Capitoli proxima...

Hors ligne

#3 29-07-2016 20:45:28

tibo
Membre actif
Inscription : 23-01-2008
Messages : 944

Re : Est ce solvable ? Coder /décoder

Bonjour,

Je crois qu'il y a un problème fondamental dans ta fonction de codage : c'est qu'elle n'est pas injective.
Autrement dit, deux textes de base différents peuvent donner le même code.
Par exemple les mot BONJOU et APNKNV donnent tout deux le code QCXYJW.
Donc pas de fonction de décodage...

A moins que...


[Edit]
Après quelques tests, j'ai l'impression que la fonction de codage est injective sur l'ensemble des textes de longueur impaire.

Dernière modification par tibo (29-07-2016 20:52:55)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#4 30-07-2016 05:34:52

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Est ce solvable ? Coder /décoder

Salut,

@tibo. Intéressant...
Pour un nombre impair de lettres, j'ai trouvé une autre solution qui a l'air de marcher...
Par contre pour un nombre pair, je ne peux pas appliquer la méthode. Je vais chercher encore sans grand espoir donc...


Le temps de déjeuner et je rédige la méthode (l'idée m'est venue hier soi dans mon lit).
Je remets à plus tard de chercher pourquoi ma première méthode de décodage déconne

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 30-07-2016 07:40:27

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Est ce solvable ? Coder /décoder

Re,

Bin non, ça ne colle pas...
Et pourtant, avec mes notations :
p1+p2+p3+p4+p5+p5+p7 = (a+b)+(b+c)+(c+d)+(d+e)+(e+f)+(f+g)+(g+a)=2a+2b+2c+2d+2e+2f+2g =2(a+b+c+d+e+f+g)
S=(p1+p2+p3+p4+p5+p5+p7)2
Ici,
BONJOUR est codé ainsi : QCXYJMT soit [17, 3, 24, 25, 10, 13, 20].
Sommons : S2=(17+3+24+25+10+13+20)/2 = 56

De la même façon BONJOUR, c'est [2, 15, 14, 10, 15, 21, 18]
Sommons : S1 = 2+15+14+10+15+21+18 = 95
[tex]S_1 \neq S_2[/tex]
Pourquoi ? Les codes de 3 lettres ont été ramenées  entre 1 et 26 : soit un déficit de 78.
S'2=(112+78)/2=95.
Mon exemple marchait hier soir parce que ce cas ne se produisait pas...

Encore une fois, en théorie, ça marche :
Je calcule Sp= p1+p3+p5 = a+b+c+d+e+f
Et S-Sp= g.
Et de proche en proche, j'étais remonté au mot original...

Dommage... Mais je ne m'avoue pas vaincu.

Je vois que Rossignol est en ligne : il va bien nous sortir un coup de génie...

Les problèmes viennent du %26, il faudrait savoir:
- soit sur combien de de codes il a été appliqué,
- soit les codes avant application de %26. On pourrait traiter chaque code de 2 façons, produire les différents messages et ne garder que celui qui a un sens. Ça risque de faire beaucoup de cas à traiter et ce serait pénible à programmer...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#6 30-07-2016 08:12:26

Rossignol
Membre
Inscription : 19-06-2015
Messages : 98

Re : Est ce solvable ? Coder /décoder

Bonjour à tous,

Il s'agit, si je ne m'abuse, d'une question d'algèbre linéaire dans l'anneau (non intègre !) $\mathbb{Z}/26 \mathbb{Z}$.

En posant A=1, B=2, ... Z=0 modulo 26, on peut écrire le codage sous forme matricielle :

$
\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
B \\
O \\
N \\
J \\
O \\
U \\
R
\end{pmatrix}
\equiv
\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
2 \\
15 \\
14 \\
10 \\
15 \\
21 \\
18
\end{pmatrix}
\equiv
\begin{pmatrix}
17 \\
3 \\
24 \\
25 \\
10 \\
13 \\
20
\end{pmatrix}
\equiv
\begin{pmatrix}
Q \\
C \\
X \\
Y \\
J \\
M \\
T
\end{pmatrix}
$

Ce système de codage est donc lié aux matrices $K_n$ ($n\geqslant 2$) :

$$K_{n}\equiv \begin{pmatrix}
1 & 1 & 0 & 0 & \cdots  & 0 \\
0 & 1 & 1 & 0 & \cdots  & 0 \\
0 & 0 & \ddots  & \ddots  &  & \vdots  \\
\vdots  & \vdots  &  & \ddots  & \ddots  & \vdots  \\
0 & 0 &  &  & 1 & 1 \\
1 & 0 &  &  & 0 & 1
\end{pmatrix}$$

Ces matrices sont singulières. On peut vérifier (démonstration laissée au lecteur) :

$$\det (K_n)\equiv \left\{
\begin{array}{l}
0\text{ si }n \text{ pair} \\
2\text{ si }n \text{ impair}
\end{array}
\right. $$

Puisque ni $0$ ni $2$ ne sont inversibles dans $\mathbb{Z}/26 \mathbb{Z}$ (les éléments inversibles sont les entiers premiers avec 26), les matrices $K_n$ n'ont pas d'inverses.

Le codage n'est donc pas bijectif, ni injectif, ni surjectif puisque ces trois propriétés sont équivalentes pour un endomorphisme d'un espace vectoriel module libre de dimension finie.

C'est curieux, mais en codant un mot par ce procédé on perd de l'information et l'on ne peut pas retrouver avec certitude le mot dont on est parti.

[Je complète... :-) ]

Le rang de $K_n$ est $n-1$, autrement dit le noyau de $K_n$ est un sous-module de $(\mathbb{Z}/26\mathbb{Z})^n$ de dimension $1$.

Si $n$ est pair, $ker(K_n)$ est le sous-module engendré par le vecteur $\begin{pmatrix}
1 \\
25 \\
1 \\
25 \\
\vdots\\
1 \\
25
\end{pmatrix}$

Par exemple, tous les mots qui se codent comme 'BONJOU' sont $\begin{pmatrix}
B+k \\
O+25k \\
N+k \\
J+25k \\
O+k \\
U+25k
\end{pmatrix}$ pour $k \in \mathbb{Z}/26\mathbb{Z}$

Ce qui donne les 26 mots :
BONJOU, CNOIPT, DMPHQS, ELQGRR, FKRFSQ, GJSETP, HITDUO, IHUCVN,
JGVBWM, KFWAXL, LEXZYK, MDYYZJ, NCZXAI, OBAWBH, PABVCG, QZCUDF,
RYDTEE, SXESFD, TWFRGC, UVGQHB, VUHPIA, WTIOJZ, XSJNKY, YRKMLX
ZQLLMW, APMKNV

Si $n$ est impair, $ker(K_n)$ est le sous-module engendré par le vecteur $\begin{pmatrix}
13 \\
13 \\
\vdots\\
13
\end{pmatrix}$
Ce qui est amusant, c'est que ce sous-module ne comprend que deux vecteurs : $\begin{pmatrix}
13 \\
13 \\
\vdots\\
13
\end{pmatrix}$ et $\begin{pmatrix}
0 \\
0 \\
\vdots\\
0
\end{pmatrix}$

Il n'y a que deux mots qui se codent comme 'BONJOUR' : $\begin{pmatrix}
B+0 \\
O+0 \\
N+0 \\
J+0 \\
O+0 \\
U+0 \\
R+0
\end{pmatrix} \equiv
\begin{pmatrix}
B \\
O \\
N \\
J \\
O \\
U \\
R
\end{pmatrix}$ et $\begin{pmatrix}
B+13 \\
O+13 \\
N+13 \\
J+13 \\
O+13 \\
U+13 \\
R+13
\end{pmatrix} \equiv
\begin{pmatrix}
O \\
B \\
A \\
W \\
B \\
H \\
E
\end{pmatrix}$

Tout serait bien plus simple avec des matrices inversibles :-)) Voir le chiffrement de Hill

Dernière modification par Rossignol (02-08-2016 10:47:11)

Hors ligne

#7 30-07-2016 09:24:37

ohkerod
Membre
Inscription : 28-07-2016
Messages : 2

Re : Est ce solvable ? Coder /décoder

Merci yoshi j'étais aussi arriver proche de tes conclusions...
Beh Rossignol les matrices j'en ai pas fait depuis mes années de FAC du coup j'aurai tendance à te croire sur paroles :D...
Et j'avais eu cette intuition que c'était impossible car c'est comme crypter un code avec une clé et perdre la clé en même temps qu'on crypte le message ...du coup dans le baba.

Mais je tente encore des trucs !

Merci de votre aide

Dernière modification par ohkerod (30-07-2016 09:25:15)

Hors ligne

#8 30-07-2016 10:08:28

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Est ce solvable ? Coder /décoder

salut,

Codes de départ :  BONJOUR, c'est [2, 15, 14, 10, 15, 21, 18].
Par contre si tu n'utilises pas le %26, le mot codé devient [17, 29, 24, 25, 36, 39, 20] soit Q]XYdgT

j'ai utilisé les codes ASCII : A --> 65 ; pour trouver le caractère à partir de la position je cherche celui qui correspond au code ASCII 64+code position. Par exemple pour le O : 64+29 = 93 soit ]...

Et la marche arrière fonctionne mon deuxième principe donne g=18, soit chr(64+18) = R
Après f+g = 39 d'où f = 21, chr(64+21) = U
Ensuite e+f = 36 d'où e=15,  64+15=79 et chr(79) = O...
Avec un nombre impair de lettres, ton code connaissant le procédé ne serait pas plus "robuste" qu'un César...
Or kla


Arx Tarpeia Capitoli proxima...

Hors ligne

#9 30-07-2016 10:10:42

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 11 386

Re : Est ce solvable ? Coder /décoder

salut,

Codes de départ :  BONJOUR, c'est [2, 15, 14, 10, 15, 21, 18].
Par contre si tu n'utilises pas le %26, le mot codé devient [17, 29, 24, 25, 36, 39, 20] soit Q]XYdgT

j'ai utilisé les codes ASCII : A --> 65 ; pour trouver le caractère à partir de la position je cherche celui qui correspond au code ASCII 64+code position. Par exemple pour le O : 64+29 = 93 soit ]...

Et la marche arrière fonctionne ; mon deuxième principe donne g=18, soit chr(64+18) = R
Après f+g = 39 d'où f = 21, chr(64+21) = U
Ensuite e+f = 36 d'où e=15,  64+15=79 et chr(79) = O...

Avec un nombre impair de lettres, ton code, connaissant le procédé, ne serait pas plus "robuste" qu'un codage César.
Or la sécurité d'un code ne devant pas reposer sur le procédé...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#10 30-07-2016 18:55:58

Rossignol
Membre
Inscription : 19-06-2015
Messages : 98

Re : Est ce solvable ? Coder /décoder

@ohkerod

Puisque l'algèbre linéaire n'a pas eu l'heur de vous plaire, je propose une solution en Python :-)
Fonction de codage :


def code(w):
    n = len(w)
    s = ''
    for i in range(n-1):
        # expression simplifiée car : (2*ord('A'))%26 = 0
        s += chr((ord(w[i])+ord(w[i+1])+1)%26+ord('A'))
    s += chr((ord(w[n-1])+ord(w[0])+1)%26+ord('A'))
    return s
 

Fonction de décodage (c'est une "fonction multivoque" !)


def decode(w):
    n = len(w)
    solutions = []
    for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
        x = [c]
        for i in range(n-1):
            x.append(chr((ord(w[i])-ord(x[i])-1)%26+ord('A')))
        if (ord(w[n-1])-ord(x[n-1])-1)%26 == ord(c)-ord('A'):
            solutions.append(''.join(x))
    return solutions
 

Le principe est simple : puisque le système linéaire qui définit la solution est indéterminé, on donne à la première lettre les valeurs successives A, B, ... Z. Pour chacune d'elle, on calcule les n-1 lettres suivantes du mot en utilisant le système. La n-ième relation doit redonner la lettre de départ ; si c'est le cas, on ajoute le mot à la liste des solutions, sinon on passe au suivant. On obtient ainsi les 2 ou 26 solutions suivant le cas.

Par exemple, pour décoder UCQWCXCT, "print(decode('UCQWCXCT'))" renvoie la liste des solutions possibles (à vous de trouver la bonne dans le tas) :

['ATIHONJS', 'BSJGPMKR', 'CRKFQLLQ', 'DQLERKMP', 'EPMDSJNO', 'FONCTION', 'GNOBUHPM', 'HMPAVGQL', 'ILQZWFRK', 'JKRYXESJ',  'KJSXYDTI', 'LITWZCUH', 'MHUVABVG', 'NGVUBAWF', 'OFWTCZXE', 'PEXSDYYD', 'QDYREXZC', 'RCZQFWAB', 'SBAPGVBA', 'TABOHUCZ',  'UZCNITDY', 'VYDMJSEX', 'WXELKRFW', 'XWFKLQGV', 'YVGJMPHU', 'ZUHINOIT']

@+

Hors ligne

#11 02-08-2016 10:52:48

Rossignol
Membre
Inscription : 19-06-2015
Messages : 98

Re : Est ce solvable ? Coder /décoder

Bin alors,

KJNO YYXX IJNM QSLCBI SS WDDOQHXO ?

:-)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le deuxième mot de cette phrase?

Pied de page des forums