Forum de mathématiques - Bibm@th.net

Pour compliquer la tâche des cryptanalystes, les codeurs aiment bien utiliser des alphabets exotiques, des signes cabalistiques, des groupes de symboles ...etc (voire des arbres :-)

Si le nombre de symboles différents est inférieur à 26, on peut associer à chaque symbole une lettre.

Ici, au premier symbole 10100 on associe la lettre A et on remplace tous les 10100 par A.
Ensuite, on associe au symbole suivant 10001, la lettre B et on remplace tous les 10001 par B.
Et ainsi de suite. Finalement, on obtient le crypto équivalent :

qui ne contient que des lettres : on peut utiliser les outils standards habituels.
Par exemple l'histogramme des fréquences :

On se doute que F est l'espace et E est e.

Finalement, l'alphabet est donc

et le message

Je pensais que le N était un s pour $ et non un k pour kilo.

Plus le crypto est court, plus le contexte est important.

@+

Une suggestion : le cryptogramme étant présenté sous forme d'un rectangle, testez les 40 manières classiques de lire le texte :-)

@+

Bonjour Alex5959,

Regardez si avec l'énigme il n'y a pas une phrase d'au moins 80 caractères.

En numérotant les lettres de la phrase, on obtient la clé, comme dans ce vieux problème.

@+

Bonjour Yoy@,

Ce n'est pas correct de révéler le cryptogramme du site. Il faut laisser le temps aux autres participants d'atteindre ce niveau. Vous feriez bien de l'effacer.

Dans le décryptement d'un chiffre de Collon, c'est la première phase qui est fastidieuse. Il faut écrire un bout de code pour se faciliter la vie.

Le code Python suivant détermine les décompositions en bigrammes et affiche celles qui ont moins de 25 bigrammes différents. Il reprend le cryptogramme de l'exemple de la page précédente.

Si vous n'avez pas Python sous la main, vous pouvez utiliser un interpréteur Python en ligne. Il suffit de copier/coller le code dans la partie gauche et de lancer l'exécution.

@+

Bonjour,

Le NFS (Number Field Sieve), crible du corps de nombres en français, est un algorithme difficile à comprendre (et à programmer). Les exposés dans les livres de crypto modernes sont souvent elliptiques. Par exemple, la page Wikipedia consacrée au NFS est difficile à comprendre d'emblée. On se demande pourquoi on fait ça et pas autre chose !

Je vous conseille de lire l'article de Carl Pomerance - A Tale of Two Sieves.

Il est très pédagogique et il reprend dans une perspective historique les différentes méthodes depuis Fermat jusqu'au NFS.

Hope this helps, comme disent les Rosbifs.

@+

Bonsoir Suzanna,

Dans le système RSA les calculs se font modulo $pq$ donc les messages possibles sont les entiers naturels strictement inférieurs au module $pq$. Au-delà, on tourne en rond :

$pq \equiv 0$, $pq+1\equiv 1$, $pq+2 \equiv 2$ ...etc

Il y a donc $pq$ messages différents possibles.

@+

Bonsoir Charlotte,

Il y a probablement un problème de transcription.
Impossible de trouver une solution avec des valeurs uniques pour les lettres.
Le mieux que j'ai obtenu, en devinant certains mots :

Ça rime, apparemment il s'agit d'un quatrain.
À voir avec les symboles en s'aidant du contexte.

@+

Bonjour,
Je vais encore me faire agonir d'injures par le prof qui a donné l'exercice  :-)

Protocole de signature d'Elgamal :

Protocole défini par Taher Elgamal en 1985.

Génération des clés : 
Le signataire choisit un nombre premier $p$, un générateur $g$ du groupe multiplicatif $\mathbb{Z}/p\mathbb{Z}^*$ et une fonction de hachage $H$ à valeurs dans $\mathbb{Z}/(p-1)\mathbb{Z}$ (autrement dit, pour un message $m$, on a $H(m)\in \mathbb{Z}/(p-1)\mathbb{Z})$. 
Il tire au hasard uniformément un $x\in\mathbb{Z}/(p-1)\mathbb{Z}$ et calcule $y = g^x\mod p$. 
La clé publique est $(p, g, H, y)$. 
La clé privée secrète est $x$.

Signature d'un message : 
Pour signer un message $m$, le signataire tire au hasard uniformément $k\in \mathbb{Z}/(p-1)\mathbb{Z}^*$ et calcule $r\equiv g^k\mod p$, puis $s\equiv (H(m)-xr)k^{-1}\mod p-1$ 
La signature du message $m$ est alors le couple ($r, s)$.

Vérification de la signature : 
On peut vérifier, en n'utilisant que la clé publique, si $(r, s)$ est une signature valide du message $m$. 
La signature est valide si $g^{H(m)} \equiv y^r r^s \mod p$

En effet, on a facilement : 
$$y^r r^s \equiv (g^x)^r(g^k)^s \equiv g^{xr}g^{ks} \equiv g^{xr+ks}\equiv g^{xr+k(H(m)-xr)k^{-1}}\equiv g^{H(m)} \mod p$$

Le problème
L’attaquant connaît la signature $(r, s)$ d’un message $m$. 
Soit $m′$ un message arbitraire et $s′ =s\alpha$ avec $\alpha=H(m′)H(m)^{-1} \mod p-1$

$$g^{H(m^\prime)} \equiv g^{\alpha H(m)} \equiv (g^{H(m)})^\alpha \equiv (y^r r^s)^\alpha
\equiv y^{\alpha r} r^{\alpha s} \equiv y^{\alpha r} r^{s^{\prime}} \mod p$$

Pour que $(r', s')$ soit une signature valide de $m'$ il faut que

$$g^{H(m^{\prime})} \equiv y^{r^{\prime}} {r^{\prime}}^{s^{\prime}} \mod p$$

ce qui donne la condition

$$y^{r^{\prime}} {r^{\prime}}^{s^{\prime}} \equiv y^{\alpha r} r^{s^{\prime}} \mod p$$

et par identification, le système

$$\left\{ \begin{array}{l}
r^{\prime} \equiv \alpha r \mod p-1\\
r^{\prime} \equiv r \mod p
\end{array}\right.$$

(Attention pour l'identification, les exposants sont définis modulo $p-1$ en vertu du p'tit théorème de Fermat $n^{p-1}\equiv 1 \mod p$.)

Comme $p$ est premier, $p$ et $p-1$ sont premiers entre eux. Le théorème des restes chinois permet d'affirmer qu'il existe une unique solution $r^{\prime}$ du système modulo $p(p-1)$.

L'attaquant a forgé une signature $(r^{\prime}, s^{\prime})$ du message $m^\prime$ qui vérifie la condition $g^{H(m^{\prime})} \equiv y^{r^{\prime}} {r^{\prime}}^{s^{\prime}} \mod p$. 
Seulement $r^\prime$ n'est pas dans $\mathbb{Z}/p\mathbb{Z}$; c'est ce qui permet de rejeter cette fausse signature. 
Puisque $r^{\prime} \equiv r \mod p$, il existe un entier naturel $n$ tel que $r^\prime = r+np$ (on a clairement $r^\prime \geqslant r$).

On ne peut pas avoir $n=0$ car alors $r^\prime=r \Rightarrow \alpha = 1 \Rightarrow H(m′)=H(m) \Rightarrow m^\prime = m$ (si on a une bonne fonction de hachage) 
De $n>0$ et $r^\prime = r+np$, on déduit $r^\prime \geqslant p$.

Conclusion : la signature $(r, s)$ est une signature valide du message $m$ si
$$0<r<p ~~~~\textrm{ et }~~~~ g^{H(m)} \equiv y^r r^s \mod p$$

La sécurité de ce protocole de signature est basée sur la difficulté du problème du logarithme discret : on ne connaît pas d'algorithme rapide qui donne $x$ pour l'équation $y \equiv g^x \mod p$ si $p$ est assez grand et si $p-1$ n'est pas friable.

@+

Bonjour,

Pour le chiffrement RSA le nombre entier $m$ qui représente le message doit être strictement inférieur au module $N$.

Ici ce n'est pas le cas : $N = 77$ et $m = 1901122120$.

Comme tous les calculs sont effectués modulo $N$, on a $m \equiv 1901122120 \equiv 51 \bmod77$.

On ne peut pas chiffrer de longs messages avec RSA mais on peut échanger de manière sure une clé pour un chiffre symétrique qui lui permettra d'échanger de longs messages.

@+

Bonjour ishoulita,

Les Américains construisent de drôles de clôtures qui tiennent sans piquets en empilant des rondins en zigzag.
Voilà une image de zigzag rail fence :

@+