Discussions au sujet de NI LabVIEW

annuler
Affichage des résultats de 
Rechercher plutôt 
Vouliez-vous dire : 

Challenge non-officiel de fevrier 2019

Bonjour, 

Comme je sais que les défis vous manque , j ai copié ce defis du site https://callicode.fr/pydefis/index, 

hâte de voir des codes optimisé 😉

 

 

 

La machine Énigma était une machine à chiffrer des messages, utilisée durant la seconde guerre mondiale. Certains en ont peut être entendu parler récemment car la méthode de chiffrement d'Énigma a été «cassée» par les alliés, en grande partie grâce aux travaux du mathématicien Alan Turing. En 2012, il était à l'honneur en Angleterre, qui célébrait le centenaire de sa naissance.

Nous allons expliquer le principe de la machine Énigma, non pas sur des lettres, mais en utilisant les chiffres de 0 à 3. En outre, nous allons un peu simplifier son fonctionnement. La machine que nous allons simuler sera composée de 3 rotors, et d'un réflecteur. Chaque rotor modifie un chiffre en un autre, le réflecteur échange les chiffres par paires.

Voici un schéma de la machine :

L'information rentre par le rotor situé le plus à droite. Par exemple, imaginons qu'on fasse entrer le chiffre 2. On suit son trajet à travers les 3 rotors, le réflecteur, puis le signal ressort, c'est maintenant un 3. La machine énigma, avec cette configuration de rotors, transforme donc les 2 en 3.

Chaque rotor peut être décrit par une permutation de l'ensemble {0,1,2,3}. Par exemple, le premier rotor (celui de droite), envoie 0 sur 1, 1, sur 3, 2 sur 0 et 3 sur 2. Ce qu'on peut résumer par ce dessin :

Et ce dessin peut être résumé en donnant simplement la ligne du bas : 1 3 0 2. Nous pouvons dire que le rotor de droite est dans la configuration 1302.

Le rotor numéro deux est dans la configuration 2301, le rotor 3 est dans la configuration 0312 et enfin le réflecteur est dans la configuration 1032 (il envoie 0 sur 1, 1 sur 0, 2 sur 3 et 3 sur 2).

Énigma possède toutefois un mécanisme supplémentaire…. les rotors tournent. Dans notre modélisation de la machine, nous imaginerons que faire tourner un rotor correspond à décaler vers la gauche la configuration du rotor. Le rotor 1, dans la configuration 1302 passera, après rotation dans la configuration 3021 (tous les chiffres qui dévrivent la configuration sont décalés d'un cran vers la gauche et le 1, qui était le plus à gauche, passe à droite).

Le rotor passera ensuite dans la configuration 0213, puis 2130 et enfin 1302, qui était sa configuration de départ. Au moment où le rotor 1 termine son tour et revient à la configuration initiale, le rotor 2 est décalé d'un cran…

Ainsi, à chaque codage de lettre, le rotor 1 tourne d'un cran. Chaque fois que que rotor 1 finit un tour, le rotor 2 tourne d'un cran. Et chaque fois que le rotor 2 finit un tour, le rotor 3 tourne d'un cran. Le réflecteur est fixe.

Voici comment se déroule le codage du message 010322. Chaque chiffre est envoyé à son tour dans la machine. Le résultat du chiffrement est indiqué en orange.

Le résultat du codage de 010322 en partant de la configuration initiale des rotors indiquée par le dessin (1302 pour le rotor 1, 2301 pour le rotor 2, 0312 pour le rotor 3 et 1032 pour le réflecteur) est donc : 121031

On se rendra compte sans mal que pour déchiffrer le message obtenu, il suffit de remettre les 3 rotors dans la même configuration qu'au début du chiffrement et de présenter les chiffres cryptés. On obtient alors le message en clair (c'est la présence astucieuse du réflecteur qui permet ça).

Vous avez compris le principe de cette machine infernale ?

Alors tant mieux… car un message vous permettant de valider une épreuve du concours CodingUP vient d'être intercepté (il est en réalité composé d'un seule ligne sans expace de 207 caractères) :

ZYHSSE.FITNMCWVE_YBJGJ_DKFQJMEJURXQDDGCEIX_GJQTBBVYDDDKOPCSWOSWZUVXXDCRZZFRM.PJ.SIINDFLOWGZJXKIFEILEJKMS.KPKSKGESPBPHMUXJFQFUUAZTXNOMHE.HQRWTGUOKVJURSFOFPHGJIOFQWSVWLKQLXVAODX_VJRYGPLGCRHYZBLUV_B...PHSJRJVEQ

Il semble que ce code ait été obtenue avec une énigma comportant 28 symboles. Les 26 lettres de l'alphabet, le tiret bas _ et le point, dans cet ordre : ABCDEFGHIJKLMNOPQRSTUVWXYZ_.

Par chance, les positions initiales des rotors et du déflecteur vous ont été communiquées par un groupuscule de Serial Codeurs (comme lors de la seconde guerre mondiale cette position était tout simplement consignée dans des registres indiquant pour chaque jour quelle est la configuration initiale des rotors à utiliser).

L'entrée de ce défi est constituée de la configuration initiale des rotors.

 

  • rotor1 : 'ONAFQEZRGLCS.XKMBVJPD_IUYWTH'
  • rotor2 : 'W_JSQKFBXLHRIOMVYNUAP.EDGCZT'
  • rotor3 : 'BIC.JNSXQFDTHW_ALUZGROVMPKEY'
  • reflecteur : 'SZMPI_WYELRJCONDTKAQ.XGVHBFU'
Message 1 sur 18
2 877 Visites

Merci Guillaume pour le défi, nous allons pouvoir avoir notre dose ! ^^

Sans trop d'optimisation, je tombe sur 12ms d'exécution, mais c'est encore du code tout moche.

Je ne donnerais pas le mot de passe de suite par contre 😛

 

Merci encore.

 

CLAMaxime -- Kudos are a great way to say thank you
0 Compliments
Message 2 sur 18
2 855 Visites

rapide la réponse !

 

pour ma part j obtient 3,99015E-4 de moyenne sur 100 execution

 

0 Compliments
Message 3 sur 18
2 835 Visites

Hyper sympa le chalenge.

après avoir posé un code brute et une simple optimisation d’exécution (pas de mise au point) j'en suis à 2.8e-5s de moyenne sur 100 exécutions.

0 Compliments
Message 4 sur 18
2 822 Visites

Je reste à 6ms pour le moment 😞

CLAMaxime -- Kudos are a great way to say thank you
0 Compliments
Message 5 sur 18
2 788 Visites

3.5e-4 secondes pour moi.

 

Ben64

0 Compliments
Message 6 sur 18
2 777 Visites

3.4e-5s après optimisation.

 

Ben64

0 Compliments
Message 7 sur 18
2 745 Visites

1.8e-4 après petite optimisation.

On progresse 🙂

J'attends vraiment de voir la direction prise par vous tous !

CLAMaxime -- Kudos are a great way to say thank you
0 Compliments
Message 8 sur 18
2 742 Visites

je met ce code ( sale et en bazar car j'ai ajouter des partie au fur et à mesure)^^

je suis toujours sur l'optimisation mais j ai pas mieux que 3.8e10-4

0 Compliments
Message 9 sur 18
2 730 Visites

Sympa comme animation!

 

Petit conseil pour l'optimisation, n'utilise jamais un noueud de propriété "valeur" pour mettre à jour un indicateur. Ci-joint un petit exemple qui saura convaincre les plus sceptiques!

 

Ben64

Message 10 sur 18
2 720 Visites