Cryptographie et puissance de calcul

[Larixd]

Bonjour,
Veuillez pardonner à un ignare en matière de cryptographie de poser cette question naïve :
J'entends toujours dire que le cassage d'un code dépend de la puissance de calcul, laquelle progresse constamment et qu'il n'y aura bientôt plus de chiffrage possible.
Je comprends très bien la chose tant que l'algorithme de codage est connu, mais dans le cas inverse, je n'arrive pas à voir comment un programme informatique peut deviner quelle méthode a été utilisée pour le cryptage.
Merci d'éclairer mon lumignon.
-----

[invite015cb473]

Salut,
je pense que d'autres plus experts que moi vous répondront mais pour le moment je me lance.
L'une des méthodes les plus employées de cryptage est le système RSA. Il utilise les congruences, et la propriété qu'un produit de 2 nombres premiers n'est divible que par 1, lui-même et les 2 nombres premiers. Alors si je vous dis 33, vous trouvez facilement de tête que c'est 3 et 11. Maintenant si je vous donne 12 083, vous allez mettre du temps avant de répondre 43*281. Le principe est le même pour les ordinateurs. Plus le nombre produit (appelons le R=p*q, p et q premiers) est grand, plus l'ordinateur va mettre du temps à calculer sa décomposition. Donc l'idée, c'est de prendre p et q très grands pour avoir un R tellement grand qu'un éventuel pirate (par exemple pour avoir le code de carte bleue) mettra trop de temps avant de trouver et que les p et q auront déjà été changés par la banque. Donc en augmentant la puissance de calcul des ordinateurs, on cherche à toujours plus réduire le temps de décomposition. Mais on se heurte alors à des soucis physiques que sont la gestion de l'échauffement des ordinateurs (au coeur du premier roman de Dan Brown (auteur du Da Vinci code), Forteresse digitale).

Ensuite si on considère l'utilisation d'un autre chiffre (le chiffre est la méthode, le code est le résultat du chiffrement), le principe de l'attaque frontale repose aussi sur la puissance de calcul. Les études de fréquence et d'algorithmes connus sont tellement variées qu'il faut une grosse puissance de calculs pour pouvoir déchiffrer puis décoder à temps. Le temps, c'est le nerf de la guerre. Si Painvin n'avait pas déchiffré l'ADFGVX de Nebel en juin 1918, l'offensive allemande sur Paris aurait été une vraie surprise. Au lieu de ça, les Français se préparent et repoussent les Allemands. Une semaine de plus aurait suffit.

Si vous voulez la démo mathématique du système RSA, je peux vous la fournir. Il faut juste minimum un niveau TS spé maths (congruences, théorème de Fermat, algorithme d'Euclide).

Cordialement,
Ecthelion

[danyvio]

C'est d'autant plus difficile que ce n'est pas le produit de deux nombres premiers qui sert de base (comme p1 x p2) mais plutôt (p1 +1) x (p2 +1).

[Larixd]

Bonjour,

le chiffre est la méthode, le code est le résultat du chiffrement

Oups !
Merci. Je pense avoir compris le principe mais n'ai pas le bagage mathématique nécessaire pour approfondir.
Donc, si je veux échanger en toute sécurité ma recette secrète de caramel mou à l'anchois avec mon cousin, il me suffit d'inventer un nouveau chiffre (je comprends qu'on soit obligé de faire appel à un chiffre commun pour les cartes bancaires).

[A voir en vidéo sur Futura]

[invite015cb473]

Donc, si je veux échanger en toute sécurité ma recette secrète de caramel mou à l'anchois avec mon cousin, il me suffit d'inventer un nouveau chiffre (je comprends qu'on soit obligé de faire appel à un chiffre commun pour les cartes bancaires).

Tout dépend de la voie utilisée : la poste, internet, un messager, un émetteur radio... Dans l'Antiquité avant que César ne lance le premier cryptage au sens strict, les rois et généraux faisaient appel à la stéganographie (en grec "écriture cachée"). Plutôt que de faire un chiffre, ils laissaient le message bien lisible mais planqué : sur le crâne du messager (avec les cheveux qui ont repoussés par dessus, fallait pas être pressé !), gravé sur une tablette de bois recouverte de cire, sur le blanc d'un oeuf dur (on écrit sur la coquille qui absorbe l'encre spéciale et le message est écrit sur le blanc), avec de l'encre au citron sur un papier qu'il faut chauffer pour lire, sans oublier les poèmes comme ceux de Sand où il fallait lire la première lettre de chaque ligne pour avoir le vrai message (on entre limite dans la crypto)... La stéganographie est à utiliser pour les voies "non-électroniques". Mais pourquoi pas également via internet avec un message caché dans une photo.
Le chiffre pur et dur est à privilégier pour la voie des ondes. Pendant la seconde guerre mondiale, sans Enigma et la bombe construite par Turing, avoir intercepté autant de transmissions des Allemands ne servait à rien.

Par internet pleins de systèmes sont possibles pour ne pas dire tous. Mais le plus fréquent est celui de la clé publique qui utilise le même principe que le RSA des cartes bleues. Pour schématiser : votre cousin envoye un mail à tous ceux qui veulent avec un cadenas ouvert. N'importe qui peut le voir. Vous prenez alors ce cadenas (sous forme d'une combinaison numérique réutilisable ad vitam), faites un mail à votre cousin avec votre recette et vous fermez grâce au cadenas. Tous le monde peut également intercepté votre recette mais comme le cadenas est fermé, personne ne peut lire la recette à part votre cousin qui est le seul à posséder la clé qui ouvre le cadenas. (En fait on aurait dû appeler ça le "cadenas public, la clé privée"). Et quel est cette clé ? ce sont 2 nombres premiers p et q. Le cadenas étant R=(p-1)*(q-1). D'ailleurs Danyvio a raison, j'avais simplifié en mettant le produit tout bête mais on complique en retirant 1 à chaque nombre premier. C'est beaucoup plus difficile d'associer 3 et 7 à 12=(7-1)*(3-1) que de les associer à 21=7*3.

Donc votre cousin vous envoie R et ouvre R avec p et q. Alors bien sûr ce sont des logiciels préexistants qui font tous le boulot eux-même. On vous demande juste un mot de passe et il en déduit que vous êtes celui qui connait p et q et il fait la traduction.

Mais inventer un nouveau chiffre n'est pas forcément simple. Surtout si on veux empêcher les études de fréquence. Ensuite il faut qu'il saut rapide à utiliser, si possible transformable en logiciel automatique. Parce que mettre 4h à taper sa recette secrète et 4h à la déchiffrer... faut être motivé ! Et surtout demeure le problème d'expliquer le mode d'emploi du chiffre au cousin ! Tant que vous ne faites pas comme Marie Stuart...

Cordialement,
Ecthelion

[Larixd]

Bpnjour,
Ma question est de simple curiosité d'esprit. Si j'étais tenté par une véritable
utilisation de la cryptographie, je me serais lancé dans la lecture d'ouvrages
spécialisés.
Lorsque je parlais d'inventer un nouveau chiffre, c'était un abus de langage, je
pensais en fait à l'utilisation concomitante de plusieurs chiffres existants.
Par exemple, je transcris ma recette en zorglangue, puis je code en binaire par
pentets, je concatène, j'y applique une opération booléenne et, pour faire bonne
mesure, je passe le résultat à la moulinette d'un quelconque logiciel de
compression etc., je peux en rajouter autant que je veux. Tout ceci est
parfaitement automatisable et j'imagine qu'avant qu'un programme informatique
trouve quelles sont les techniques que j'ai utilisées et dans quel ordre j'aurai
les cheveux blancs (flute, c'est déjà fait )
J'ai un avantage sur Marie Stuart, elle ne possédait pas d'ordinateur. Thomas
Phelippes non plus, zut

[invite58081e51]

Selon moi, tu n'as pas compris le veritable probleme de la cryptographie (ou alors c'est moi et mille excuses). Certes avec ta methode personne ne peut acquerir ta recette mais le but de la crypto est d'envoyer des messages à une personne B qui doit la lire. Et comment la personne sait elle comment tu as codé ta recette ?

[invitebe0cd90e]

bon, eclaircissons les choses.. pour repondre a ta premiere question, le principe de base c'est qu'on a deux operations possibles :

- dans un sens on "chiffre" un message
- dans l'autre on essaie de "casser" le code et de dechiffrer le message.

par definition, un systeme de cryptage est considéré comme solide si la 2e operation est proportionnellement beaucoup, beaucoup, beaucoup plus difficile a realiser que la premiere.

la difficulté, la complexité de ces operations se mesure par rapport a la taille des cles qu'on utilise. si on augmente la puissance de calcul, en general il suffit d'augmenter la taille des cles et le probleme est resolu..

et dis toi bien qu'en general la premiere operation prend quelques secondes, et que la deuxieme prendrait en theorie plusieurs milliers voire millions d'années.... et avec une cle 2 fois plus longue, ca ne prendrait toujours que quelques secondes au debut por la 1ere, mais ca taperait dans du milliard d'année pour la seconde. il y a peu etre une exception pour RSA grace aux ordis quantiques, mais c'est encore assez hypothetique et il y'aura alors d'autres solutions.

enfin, n'oublie pas quelques principes fondamentaux en cryptographie :

- ne jamais utiliser un systeme maison. concevoir un algo solide est un boulot extremement difficile, et un algo doit etre testé de nmbreuses fois, par de nombreuses personnes independante pour etre considéré comme sur.

- principe d shannon : la sécurité d'un chiffrement ne doit jamais, jamais jamais reposer sur l'obscurité. la securité ne doit dependre que de la clé, l'algorithme doit pouvoir etre rendu publique (et c'est le cas en general) sans que ca ne mette en danger tes données.

[invite0387e752]

un livre tres bien "Introduction a la Cryptographie" de Johannes Bucchman, niveau L3 M1, mais tout a fait abordable par un bac +1 en sciences dures.
tu verras sur quels principes mathématiques se base la crypto et ca te permettra de mieux comprendre les coulisses des algos et des systemes

[Larixd]

Bonjour,
À maxevans : Non, je n'y connais rien en crypto et n'en fais pas mystère. Pour ce qui est de dire à mon cousin comment j'ai codé ma recette, je pensais lui envoyer un message... codé.
À jobherzt : Merci, ta réponse (en particulier sur le principe de Shannon) répond parfaitement à la question que je me posais (mais que j'avais sans doute mal formulée).
À warznok : J'avis la flemme de m'y attaquer (à ce livre ou à un autre), mais je crois que je vais me décider.

Merci à tous.

[invité576543]

Bonjour,

Un point souvent ignoré par les néophytes dans ce domaine est que la difficulté ne réside pas dans l'algorithme de chiffrement, mais dans l'échange préalable de la clé.

Il n'y a aucune difficulté à faire un chiffrement absolument impossible à décrypter, quelle que soit la puissance de calcul disponible, si deux conditions sont remplies:

- il est possible aux deux parties de se mettre d'accord sur une clé sans qu'elle soit interceptable (échange préalable de la clé);

- la clé n'est utilisée qu'une seule fois.

Dans l'écrasante majorité des situations pratiques ces conditions sont trop contraignantes, et toute la difficulté de trouver un "bon" système de chiffrement vient de la suppression de l'une ou l'autre des contraintes.

Le chiffre RSA cité est un chiffre dit "à clé publique", méthode proposée pour passer outre la première contrainte. Dans un tel système, l'échange de la clé est publique. Ainsi l'information (au sens Shannonien) de la clé est publique, mais sous une forme telle que l'utilisation de cette information pour décrypter demande un temps de calcul très supérieur à celui demandé par le déchiffrage (au passage on déchiffre quand on dispose de la clé, et on décrypte quand on ne la connaît pas...). Dans ce cadre, il est clair que la progression des moyens de calcul influence fortement l'usage de telles approches. Ce d'autant plus qu'on connaît très peu de systèmes à clé publique.

Si on peut garder la première contrainte (échange sécurisé de la clé), mais pas la seconde, la quantité d'algo de chiffrement potentiellement "bons" est bien plus grande. Les méthodes d'attaque vont chercher à exploiter les corrélations introduites par les utilisations réitérées de la clé. De telles corrélations peuvent être exploitées même en l'absence de connaissance sur l'algorithme de chiffrement (exemple trivial, si à chaque fois que le message "xoiyert" est envoyé à une batterie d'artillerie il y a un tir dans la minute qui suit, nul besoin de connaître l'algo pour faire une hypothèse sur le sens du message...). (En pratique, néanmoins, attaquer un chiffre inconnu est bien plus difficile qu'attaquer un chiffre connu, et demande une réutilisation de la clé bien plus grande.) Là aussi, la progression de la puissance de calcul influence l'usage de ces méthodes, mais, du moins à ce que j'en comprends, pas au point de penser "qu'il n'y aura plus de chiffrement possible".

Cordialement,

[Calvert]

Salut!

Concernant RSA et la factorisation des très grands nombres, voici une news qui peut être intéressante concernant les "records" de la discipline:

Factorisation

[invitea3764e09]

Bonjours a tous

il ya une attaque un crypto qui utilise des mot probables: on choisit un mot, on prends tous ceux de la meme longueur, on remplace les lettres du mot 1 par celles du mot 2 puis on applique la recette a tout le message, puis on recommence jusqu'a que ca marche...
Je voudrais savoir si on peut empecher cette methode de "cassage" en choisissant, pour le cryptage, deux(ou plus) lettres pour une???.

[Larixd]

Bonjour,
J'imagine une méthode assez simple : si je chiffre "papa" en ascii, j'obtiens 70 61 70 61. Mais si j'applique une clé (par exemple 1789), ça devient 71 68 78 70. À moins que je n'aies pas bien compris la question.