Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 29-07-2016 12: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 18:55:27
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 223
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 20:40:31)
Arx Tarpeia Capitoli proxima...
Hors ligne
#3 29-07-2016 22:45:28
- tibo
- Membre expert
- Inscription : 23-01-2008
- Messages : 1 097
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 22:52:55)
A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !
Hors ligne
#4 30-07-2016 07:34:52
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 223
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 09:40:27
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 223
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 10:12:26
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 294
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 12:47:11)
Hors ligne
#7 30-07-2016 11: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 11:25:15)
Hors ligne
#8 30-07-2016 12:10:42
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 17 223
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
#9 30-07-2016 20:55:58
- Rossignol
- Membre
- Inscription : 19-06-2015
- Messages : 294
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 24-05-2022 08:59:22
- ??
- Invité
Re : Est ce solvable ? Coder /décoder
bonjour
je suis un peut en retard non?
je me suis posé une questions le problème en réalité et l'utilisation d'une grande partie du message claire non?
pourquoi ne pas transformée ton cryptage pour codé avec la lettre précédente qui aura donc déjà été codé ?
la plus grande faiblesse reste la premier lettre du message qui ne sera jamais codé alors pourquoi ne pas la codé après avec la dernière lettre du message ?
j'ai pensée a un système semblable mais qui code tout les caractère (la base n'est donc plus 26).
je ne m'intéresse au cryptage que depuis 2 semaine mon message peut donc paraitre aberrant pour une partie d'entre vous...
bonne continuation a tous !
Pages : 1