Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
131 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Énigme du week-end : le secret de La Licorne

Envoyé par Siméon 
Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Trois frères unys.
Trois Licornes de conserve vogant au Soleil de midi parleron.
Car c'est de la lumière que viendra la lumière…
Et resplendira la ✝ de l'Aigle


Si le chevalier François de Hadoque avait connu le code ASCII et un peu de maths, il aurait pu diviser son message entre ses trois fils de façon parfaitement sécurisée : de sorte que les trois parchemins permettent de reconstituer le message, mais qu'on n'obtienne aucune information avec seulement deux parchemins.

Saurez-vous retrouver de quel album des Aventures de Tintin est tirée la citation de 86 caractères qui se cache derrière ces trois parchemins ?

1001101101100001100111010011000110001100100110101001011101010110001011001100111001001110000111101010110111111110000111110010100100001100000001011001111001100111010001101100110101010100001001101011111101111111000000110100010010001000011000100101110011000100111011000101011100001111001110001000001000111000000000000110001101100110000110101010101111001100011101011110101110010111101100100111000110001110110101101101000011001111101011100110111010100011100111101000001100101010001000100111010101101100110011110000110100010110101011000110101101010010100110100111111001011101111010011000110101000110111101100111100111111101100100110000001000001101110101101111010010110111000101110010110010001011

0010110001111010010111010100100100111001010001111000100100100111110110110101111111111001001100011110010111111010001101111101110101110010010001011101000001011001000011010011110110110111011101010111000000000110011011011110110101001011001110011111100110100011010111010011010001111111010101011011111111011001100100010001010111001001001010100101011000100010111101101000101011001010000001111110011000111001010100000000111110001110001100101111100100111011101100000100000101011000111000101101110110110110001000110010001011011111111011100010000111100111101000010101001100001110111100000101110011101101010010011101111010011100110010010110110000011000010000011010100010011001111110001100111110111000

1111001101110010101100100001110110010101101011000110101100010100110101111111111111011000010110100011101100100100010011101001101100001011001011000010000101010000001110001101000010000000001101101110111100001010000000011100010111100011001111111100000001000111110111010000001001010000001000010100100010001111111101000101011011000000010001011101110110000100111000100000110000111100110111001110010010010111111010101011111001100001111100011111011011110001010000001110001000010110101001011000100010110110110010110100011110100110001011110010011111010000000110110100001101110100011110001111000111000110110101101101010001000001001101100000101100110101111001110011010101001011100010111100001100010010
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
oh! c'est joli ça!

Merci Siméon.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Afin que je sache si je dois donner des indications, pourriez-vous me dire s'il n'y a pas plus de réponses :
\begin{itemize}
\item parce que ça n'intéresse personne d'autre ?
\item parce que c'est trop dur ?
\item parce que vous êtes en train de chercher avec acharnement ?
\end{itemize}
Re: Énigme du week-end : le secret de La Licorne
il y a six années
Bonjour,

J'essaye de comprendre pourquoi le deuxième fils a deux chiffres en moins ?

rosab
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Pas d'empressement Siméon :)-D moi je viens seulement de découvrir ton énigme, et probablement que d'autres ne l'ont pas encore vue.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
[attachment 30098 herge-on-a-marche-sur-la-lune-1954.jpg]


Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
@rosab : c'est corrigé, merci d'avoir fait la remarque.

@Juge Ti : bravo !

Pour ne pas dévoiler la réponse tout de suite, que le prochain qui trouve indique le nom du personnage qui prononce la citation.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Je suis toujours surpris de voir que des gens, même plus âgés que moi, se souviennent de moult détails des Tintin, Astérix, etc, qu'ils ont lu pendant leur enfance. Suis-je le seul à avoir effacé ça de ma mémoire ? :S
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Oh @Steven, si tu savais mon âge canonique... Mais je te rassure, je n'ai pas reconstitué l'énigme du chevalier Hadoque seulement de mémoire. La citation à trouver est facile à identifier.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Bonsoir,

j'ai cherché mais j'ai du mal avec la consigne. J'ai un vernis tout fin pour ce qui est de la cryptographie.
Je peux avoir un indice sieur Siméon s'il vous plaît ?

S
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
@samok : il ne s'agit pas vraiment de cryptographie, en tout cas il n'y a pas de cryptage à casser. Il faut trouver une façon simple de diviser un bit d'information $b$ en trois bits aléatoires $X_1,X_2,X_3$ deux à deux indépendants, de sorte que $P(X_i = 0) = P(X_i = 1) = \frac{1}{2}$.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
199. 54. 28. 175. 39. 178. 215. 103. 104. 224. 29. 51. 143. 150.

175. 227. 129. 89. 99. 236. 242. 87. 96. 187. 66. 127. 67. 134.

24. 180. 238. 214. 40. 59. 5. 83. 103. 46. 45. 45. 171. 117.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Bonsoir,

est-ce quelque chose du style : $\forall i\,\, X_{i,1}+X_{i,2}+X_{i,3}=b_i [2]$.
On génère aléatoirement $(X_{i,1},X_{i,2})$ comme produit indépendant de deux "pile-face" et $X_{i,3}$ en découle compte tenu de la valeur $b_i$.

S
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
@samok : c'est ça ! tu as le message alors ?
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Je crois bien oui.
Il est à l'encre rigolote ci-dessous :

Dire que nous foulons ce sol de la Lune ou jamais la main de l'homme n'a mis le pied !

Merci pour cette énigme, ça faisait longtemps que j'en avais pas résolue.
S
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
J'ai pu facilement pyhtonner le message résultant, j'ai galéré avec le module binascii qu'au final je ne comprends pas.
J'avais demandé de l'aide à mon ami google pour en avoir la traduction.

Voici ci-dessous de quoi complètement se pythonner je sais pas s'il n'y aura pas des blaguounettes à cause du symbole pourcentage.

Citation
code python (version 3.x)
code_ascii=" !"+"'"+"#$"+"%"+"&"+"'"+"()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~"

m1='1001101101100001100111010011000110001100100110101001011101010110001011001100111001001110000111101010110111111110000111110010100100001100000001011001111001100111010001101100110101010100001001101011111101111111000000110100010010001000011000100101110011000100111011000101011100001111001110001000001000111000000000000110001101100110000110101010101111001100011101011110101110010111101100100111000110001110110101101101000011001111101011100110111010100011100111101000001100101010001000100111010101101100110011110000110100010110101011000110101101010010100110100111111001011101111010011000110101000110111101100111100111111101100100110000001000001101110101101111010010110111000101110010110010001011'
m2='0010110001111010010111010100100100111001010001111000100100100111110110110101111111111001001100011110010111111010001101111101110101110010010001011101000001011001000011010011110110110111011101010111000000000110011011011110110101001011001110011111100110100011010111010011010001111111010101011011111111011001100100010001010111001001001010100101011000100010111101101000101011001010000001111110011000111001010100000000111110001110001100101111100100111011101100000100000101011000111000101101110110110110001000110010001011011111111011100010000111100111101000010101001100001110111100000101110011101101010010011101111010011100110010010110110000011000010000011010100010011001111110001100111110111000'
m3='1111001101110010101100100001110110010101101011000110101100010100110101111111111111011000010110100011101100100100010011101001101100001011001011000010000101010000001110001101000010000000001101101110111100001010000000011100010111100011001111111100000001000111110111010000001001010000001000010100100010001111111101000101011011000000010001011101110110000100111000100000110000111100110111001110010010010111111010101011111001100001111100011111011011110001010000001110001000010110101001011000100010110110110010110100011110100110001011110010011111010000000110110100001101110100011110001111000111000110110101101101010001000001001101100000101100110101111001110011010101001011100010111100001100010010'

m=''
for i in range(688):
m_aux=(int(m1[ i])+int(m2[ i])+int(m3[ i]))%2
m=m+str(m_aux)
lst=[]
for i in range(86):
n_aux=0
for j in range(8):
n_aux=n_aux+2**(8-j-1)*int(m[8*i+j])
lst.append(n_aux)
message=""
for i in range(len(lst)):
message=message+code_ascii[lst[ i]-32]
print(message)

J'ai appris des nattes et du code ascii, encore merci sieur Siméon.

[edit : bon y a des p'tites blagues des crochets i ne passent pas (!?) ou qu'il n'y a plus d'essence dans l'existence :)]
S

[En BBcode '[ i' (sans espace au milieu) est un départ de bannière demandant la mise en italique, et ne sont pas affichée.
Tes indices de tableaux sont dans ce cas. Soit tu prends 'j' pour indice, soit tu mets un ' '.
Par contre les % ne posent pas de problème tant que tu ne coches pas la case LaTeX. ;) AD]

[Merci AD, je tacherai d'y penser pour la prochaine fois]



Edité 6 fois. La derni&egrave;re correction date de il y a six ann&eacute;es et a &eacute;t&eacute; effectu&eacute;e par samok.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
@samok : On peut aussi faire comme ça :

l = [[int(m[i*8:i*8+8], 2) for i in range(86)] for m in [m1, m2, m3]]
print(''.join(map(chr, [a^b^c for a, b, c in zip(*l)])))

@Siméon : Ton énigme était bien sympa, je la proposerai à mes élèves.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Deux choses :

- purée c'est quoi ce code de l'espace !?
- merci JugeTi

S
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Salut samok,

Il y a plein de trucs en Python qui permettent d'éviter de faire des boucles. Ici j'utilise :

- les listes définies par compréhension :
>>> [i**2 for i in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

- le slicing :
>>> chaine = 'abcdefgh'
>>> chaine[3:6]
'def'

- la méthode join permet de concaténer les chaînes d'une liste :
>>> mots = ['Bonjour', 'mon', 'cher', 'samok']
>>> ' '.join(mots)
'Bonjour mon cher samok'

- pour zip c'est plus facile à expliquer avec un exemple :
>>> zip([1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12])
>>> list(_)
[(1, 5, 9), (2, 6, 10), (3, 7, 11), (4, 8, 12)]

La fonction int peut prendre comme deuxième argument la base à partir de laquelle on veut convertir :
>>> int('10110', 2)
22

La fonction chr reçoit un entier et renvoie le caractère Unicode associé (sa fonction réciproque est ord) :
>>> chr(97)
'a'
>>> ord('a')
97

Enfin j'avais utilisé map qui permet d'appliquer une fonction à chaque élément d'un itérable, mais ici je me rends compte que c'est inutile, j'aurais pu faire plus simplement :

l = [[int(m[i*8:i*8+8], 2) for i in range(86)] for m in [m1, m2, m3]]
print(''.join(chr(a^b^c) for a, b, c in zip(*l)))
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Nickel, merci Juge Ti,
je commençais à fouiner dans mes livres pour comprendre ces deux lignes...

Tu as oublié de mentionner la petite ruse de sioux utilisant le Xor (le chérif de l'espace) du genre 25^14=23

S
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Super ! voici une autre solution, toujours en Python :
(hex(int(m1,2) ^ int(m2,2) ^ int(m3,2))[2:-1]).decode('hex')
ce qui donne "Dire que nous foulons ce sol de la Lune ou jamais la main de l'homme n'a mis le pied !", citation de Dupond extraite de l'album On a marché sur la lune par Hergé. Bravo à Juge Ti, samok et aléa (je n'ai pas bien compris ce qu'il n'avait pas le courage de faire d'ailleurs) !

$\star\quad\star\quad\star$


Pour la partie mathématique, samok a déjà dit l'essentiel. Je résume : si $X_1$ et $X_2$ sont deux variables de Bernoulli(1/2) indépendantes à valeurs dans $\Z/2\Z$ et si $b \in \{0,1\}$, alors $X_3 = b + X_1 + X_2$ est encore une Bernoulli(1/2) et elle est indépendante de $X_1$ aussi bien que de $X_2$ (magie de la loi uniforme sur un groupe). Bien sûr $X_1,X_2,X_3$ ne sont pas conjointement indépendantes, d'ailleurs la fonction de "reconstruction" est très simple (et joliment symétrique) : $b = X_1 + X_2 + X_3$.

Pour coder un message complet de longueur $n$ on fait la même dans $(\Z/2\Z)^n$ , ce qui revient à appliquer ce qui précède à chaque bit de la représentation binaire. Informatiquement, l'addition modulo 2 se traduit par un \verbatim{XOR}.

$\star\quad\star\quad\star$


Si ici on a divisé le secret en 3 morceaux, la même technique marche pour un nombre quelconque de morceaux. Et si on voulait découper le message en trois parties de sorte qu'une partie seule ne donne aucune information, mais que deux quelconques soient suffisantes pour retrouver l'original ?
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Pas mal l'utilisation de decode ! En Python 2.7 ça marche bien, mais en Python 3 ça ne marche pas (une histoire de conversion implicite bytes-string qui ne se fait plus si je comprends bien). En cherchant un peu sur Internet, j'ai trouvé cette méthode :

bytes.fromhex((hex(int(m1,2) ^ int(m2,2) ^ int(m3,2))[2:])).decode()

Pour ta nouvelle question c'est facile : il suffit de créer les messages m1, m2 et m3 comme précédemment, et de donner les couples (m1,m2), (m1,m3) et (m2,m3). Je ne sais pas si c'est la réponse attendue...
Re: Énigme du week-end : le secret de La Licorne
il y a six années
Juge Ti écrivait:
-------------------------------------------------------
> Pour ta nouvelle question c'est facile : il suffit
> de créer les messages m1, m2 et m3 comme
> précédemment, et de donner les couples (m1,m2),
> (m1,m3) et (m2,m3). Je ne sais pas si c'est la
> réponse attendue...

Le problème avec cette approche est qu'elle devient vite très inefficace si l'on augmente les paramètres. On voudrait pouvoir obtenir un partage de secret entre n parties tel que t parties ensemble puissent reconstituer le secret, mais pas t-1, d'une façon qui n'augmente pas significativement la quantité d'information envoyée aux différentes parties comparée à la taille du secret d'origine.

L'approche habituelle s'appelle partage de secret de Shamir. Mettons qu'on représente le secret comme une suite d'éléments a_i d'un corps fini K contenant au moins n éléments distincts non nuls x_1, ..., x_n. On peut alors tirer, pour chaque élément a_i du secret à partager, un polynôme aléatoire f_i de degré t-1 dans K[X] tel que f_i(0) = a_i, puis donner à la partie j la valeur f_i(x_j). En choisissant convenablement K, on peut alors rendre la taille de la part que reçoit chaque partie essentiellement aussi courte que le secret d'origine.

Par exemple, pour le cas suggéré par Siméon ci-dessus, on peut choisir K=F_4 et grouper les bits du message deux à deux. Le partage de secret va alors correspondre, pour chaque couple de bits, à tirer un nombre b entre 0 et 3, et à envoyer aux différentes parties le couple lui-mème pour b=0, et le couple xoré avec 01, 10, 11 (resp. 10, 11, 01; resp. 11, 01, 10) pour b=1 (resp b=2; resp. b=3). Je laisse voir comme s'effectue concrètement le décodage.
Re: Énigme du week-end : le secret de La Licorne
il y a six années
avatar
Merci Mehdi ! Je pensais à un truc comme ça mais j'ignorais que ça avait un nom.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 140 706, Messages: 1 376 281, Utilisateurs: 25 644.
Notre dernier utilisateur inscrit EPFL.


Ce forum
Discussions: 2 378, Messages: 17 518.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page