” GS15留学生编程 写作、Python，Java程序UTT – GS15 Automne 2020Une Block-chain simplifieGS15 – A20 – Projet InformatiqueSujet prsent en cours le 13/10Rapport et codes rendre avant le 09/01Soutenances entre le 11/01 et le 15/011 Description du Projet raliserLe but de ce projet informatique est de vous faire crer une technologique similaire une block-chainsimplifie. Lide tant de vous faire dvelopper un outil permettant de faire des transactions de faonauthentifie, irrvocable. En outre, un outil de communication chiffre (qui permettra aux utilisateurs de semettre daccord sur les transactions) sera galement dvelopp.Notons en prambule que lalgorithme le plus dtaill est celui qui nest pas vu en cours, le chiffrementsymtrique KASUMI modifi par les soins de votre professeur pervers et sadique.Les autres algorithmes sont dcrits de faon trs succincte pour deux raisons : (1) car ils ontt (ou seront) tudis en cours et (2) car dans ce projet, vous avez beaucoup de libert quant limplmentation pratique des algorithmes. En effet vous constaterez quil vous ait demand de suivrecertaines rgles partir desquelles vous pouvez faire le minimum ou en faire beaucoup plus ; des suggestionsvous seront donnes dans les diffrents points.Il vous est demand de faire un menu permettant de tester individuellement les algorithmes implments;votre programme doit donc, typiquement, afficher lors de lexcution le menu suivant:Bonjour matre Rmi ! Que souhaitez vous faire aujourdhui ?-1- Chiffrer un message.-2- Dchiffrer un message.-3- Gnrer des couples de cls publiques / prives.-4- Gnrer un hash / une empreinte.-5- Vrifier un hash / une empreinte.-6- Effectuer une preuve de travail.-7- Vrifier une transaction (une signature).-8- Dbuter / incrmenter la Block-chain.-9- Vrifier lintgrit de la block-chain.-10- I WANT IT ALL !! I WANT IT NOW !!Les algorithmes que vous devez dvelopper, pour chacun des choix possibles, sont dcrits ci-dessous(en commenant pas ceux que vous pouvez le plus implmenter le plus tt dans le semestre) respectivementdans les sections 2 pour le chiffrement symtrique (Choix -1- et -2-), 3 pour la cration dunGS15 – RC – 1- Projet de cryptologie (GS15)UTT – GS15 Automne 2020couple de cls Publique / prive (Choix -4-), 4 pour le hashage (Choix -4- et -5-) et lapreuve de travail (Choix -6-), 5 pour la gnration et la vrification dune signature (Choix -7-).Enfin le principe de fonctionnement dune block-chain est prsent dans la section 6. Cela voussera utile autant pour votre culture personnelle que pour limplmentation des oprations de cration,incrmentation et vrification dune block-chain (Choix -8- et -9-).Il est conseill de rutiliser les fonctions donnes / crites pour les devoirs, notamment pour la lectureet lcriture des fichiers, ainsi que les fonctions arithmtiques (tests de Rabin Miller, exponentiation rapide,etc. …).1.1 ExigencesDe nombreux points sont laisss votre discrtion. En revanche il y a galement de nombreuses consignes respecter. Ci-dessous sont rappeles les principales consignes que vous devez obligatoirementrespecter :1. raliser votre projet en utilisant le langage python (version 2 ou 3) ;2. respecter les consignes Donnes dans la section 7 du prsent document ;3. chaque section contient un paragraphe exigences que vous devez suivre (par exemple utiliserdes cls publiques/prives de 512 bits au moins, crire les transactions dans des fichiers, etc. …) ainsiquune section recommandations dans laquelle des suggestions sont proposes pour aller plus loin.4. vous devez rendre un rapport court, rpondant uniquement (et pas plus) aux exigences de lasection 7 ; les soutenances auront lieu la soutenance prcdent les finaux ; vous devez rserver uncrneau de soutenance.Enfin, je vous informe que la notation est faire afin que: un programme qui fonctionne et respecte lensemble des exigences se voit attribuer un 16/20 ; le respect, en sus, de lensemble des recommandations garantit un 20/20 toutes les initiatives Personnelles seront apprcies et valorises (mais il est plus important de respecterles consignes) les projets de GS15 sont assez complets et chronophages ; commencez en avance et, si vous le faitesbien, utilisez les sur votre CV pour montrer vos comptences dans le domaine de la crypto !2 Chiffrement symtrique KASUMIConcernant le chiffrement symtrique / cl prive , il vous ait demand dimplmenter le chiffrement parbloc KASUMI. Cet algorithme de chiffrement repose sur une construction de Feistel 8 itrations, utilisantGS15 – RC – 2- Projet de cryptologie (GS15)UTT – GS15 Automne 2020des blocs de 64 bits et des cls de 128 bits. Cet algorithme t propos par le est celui au cur de laconfidentialit des changes dans les protocoles de tlphonie 3G et suivants.Le fonctionnement global de cet algorithme est brivement dcrit dans le prsent document, ci-dessous,illustr dans la figure 1 ; pour plus de dtails, vous pouvez consulter la page Wikipdia (en anglais) oumieux, aller directement consulter la norme telle que fournie par le 3GPP (lorganisme de standardisationpour la communication mobile).Attention, deux Modifications, par rapport lalgorithme original, sont imposes !Comme dans tout schma de chiffrement sur la division du bloc chiffrer en deux moitis (notes Lipour le Left et Ri pour Right) ainsi que sur la relation suivante itrativement applique :(Ri = Li1 ;Li = F(Li1) Ri1 .(1)Naturellement, avant la premire itration, le bloc clair (de 64 bits) chiffrer est divis en deux parties,respectivement, L0 et R0 (de 32 bits) ; les deux derniers blocs L8 et R8 sont concatns pour donner lechiffr.Comme pour tout schma de Feistel, KASUMI est donc principalement dfini par la fonction F().Lune des spcifis de KASUMI Vient du fait que F() est lgrement diffrente suivant que lindice delitration soit pair ou impair. Plus prcisment, la fonction F() est la composition de deux fonctions dontlordre dapplication sera invers. On aura alors :(Fimpair(Li1)) = F O(KOi, KIi, F L(KLi, Li1)) ;Fpair(Li1)) = F L(KLi, F O(KOi, KIi, Li1)).(2)avec KLi, KIi, KOiles sous-cls de litration i.Cette construction ainsi que les fonctions F L, F O (et F I) sont illustres dans la figure 1.La fonction F I(KLi, x) qui a pour entre et pour sortie des blocs de 32 bits opre de faon similaire.Le bloc x = l|r est divis en deux sous-parties on applique alors :r0 = Ir [(lANDKLi,1) 1]puis :l0 = Il [(r0ORKLi,2) 1]I.avec 1 lopration de dcalage circulaire (a.k.a permutation circulaire) de 1 bit vers la gauche.Modification #1 : Dans la version de GS15 il vous est demand dappliquer chacun de ces rsultatsde 16 bits une opration dinversion, note Idans un corps de Galois (que vous dfinirez vous-mmeen utilisant un polynme irrductible de 16 de votre choix).La fonction F O est plus complexe, elle repose sur une construction de Feistel (utilisant 3 itrations, desblocs de 32 bits dcomposs en deux sous-blocs de 16 bits.Chaque itration est dfinie par (attention cest bien le bloc de droite ri qui est conserv !) :(lj = rj1 ;rj = rj1 F I(lj KOi,j , KIi,i).(3)GS15 – RC – 3- Projet de cryptologie (GS15)UTT – GS15 Automne 2020Figure 1: Illustration du fonctionnement de lalgorithme de chiffrement symtrique par bloc KASUMI.avec KOi,j et KIi,i les sous-cls de litration (i, j) reprsentant les indices des deux schma de Feistelimbriqus.Modification #2 : la fonction F I(y, z) qui a pour entre deux blocs de 16 bits fonctionnera, dans ceprojet, de la Faon suivante : y 2 Sbox1(z1)|Sbox1(z2)avec le bloc z = z1|z2 divis en deux partiesde 8 bits sur lesquelles est utilise une Sbox distincte.Vous devrez construire ces deux Sbox en utilisant lalgorithme dinitialisation de RC4 vu en cours.Le key scheduling (gnration de sous-cls ditration partir de la cl initiale) est laiss votrediscrtion.2.1 ExigencesIl vous est demand dimplmenter :1. le chiffrement en mode ECB, CBC et PCBC ;2. le chiffrement dun fichier ainsi que son dchiffrement (le chiffr lui aussi tant crit dans un fichier);GS15 – RC – 4- Projet de cryptologie (GS15)UTT – GS15 Automne 20203. le fichier doit tre dune taille adquate, au moins quelques kilo-octets;2.2 RecommandationsPour aller plus loin, vous pouvez, si vous voulez, regarder les lments suivants :1. Proposer une utilisation de lalgorithme de chiffrement KASUMI en mode flux;2. comprendre et implmenter les modes de chiffrements Counter et GCM (Galois Counter Mode);3. vous pourrez paramtrer la cration des Sbox en fonction de la cl de sorte que les Sbox ne soientjamais les mmes;3 Gnration dun couple de cls publique/priveNous le verrons en cours durant la seconde moiti du semestre, la gnration dun couple de clspublique/prive ncessite de faire des calculs avec des nombreux grands et notamment de rechercher unnombre premier large (typiquement 100 chiffres, voire souvent beaucoup plus).Dans cette partie de cela il est impos de chercher un entier premier p de au moins 512 bits.Attention, la signature que nous utilisons tant bas sur la signature de El-Gamal, une fois un grand entierpremier p gnr, vous devrez trouver un lment gnrateur de Z?p.Pour cela il est clairement illusoire de tester, pour un donn, toutes ces puissances successives1, 2, . . . , p1; il vous faudra donc trouver une astuce … (indice, reposant sur le thorme de Lagrange).Cet aspect peut tre envisag plus tardivement dans votre projet, dans un premier temps vous pouvezvous concentrer sur la recherche dun grand entier premier et lexponentiation rapide.Par la suite vous devrez trouver (rapidement) un lment gnrateur de Z?pet gnrer un Couple de clspublique/prive adquat pour la signature de Diffie-Hellman.3.1 ExigencesPour cette partie vous devrez, vous pouvez :1. Utiliser des fichiers pour grer, stocker, lire les cls publiques (et prives) ; lors de la soutenance parexemple il pourra tre long de gnrer 3 cls de 1536 bits …..3.2 RecommandationsSi vous le souhaitez, vous pouvez :1. Implmenter le partage de cl prive en utilisant le protocole de Diffie-Hellman;2. Implmenter votre propre gnrateur de nombre alatoire (par exemple votre XORshift);GS15 – RC – 5- Projet de cryptologie (GS15)UTT – GS15 Automne 2020Figure 2: Rappel du principe des fonctions ponges pour le hashage.4 Hashage: Fonction pongeEn ce qui concerne la fonction de hashage, vous pouvez implmenter nimporte quelle fonction dehashage (e.g, MD5, Whirlpool, SHA-256, etc. …), mais il est impratif de modifier cette fonction afinde limplmenter dans le cadre dune fonction ponge telle quutilise dans SHA-3 et illustre dans laFigure 2 ci-dessous.Si vous souhaitez Reprendre une fonction de hashage standard, les modifications faire pour que cettedernire soit utilisable dans le cadre des fonctions ponges sont laisses votre discrtion. Sinon vouspouvez aussi vous inspirer des fonctions de hashage classique pour inventer la vtre.Une seule contrainte est demande, votre fonction de hashage doit applique, au moins, 2 fois la fonctionafin dobtenir le hash (votre schma utilisant la fonction ponge ne doit pas seulement ressortir le rsultatde la dernire itration utilisant les donnes du fichier.Vous pourrez galement choisir arbitrairement dutiliser N fois la fonction de hashage en fin de processusdabsorption.4.1 ExigencesIl vous est demand dimplmenter :1. une fonction de hashage reposant sur la construction avec des fonctions ponges ;2. Utiliser une fonction de hashage non standard (ou modifier une fonction standard pour quelle soitutilisable dans le cadre des fonctions ponges);GS15 – RC – 6- Projet de cryptologie (GS15)UTT – GS15 Automne 20205 Gnration et vrification dune signatureUne fois la procdure de cration dun couple de de cls publique/prive, dcrite dans la section 3, cesdernires seront utilises afin de scurit les transactions en utilisant un mcanisme de signature. Vous avezle choix dutiliser le mcanisme de signature (El-Gamal, DSA, RSA).On rappellera brivement que la signature dun message se compose des tapes suivantes:En prambule, il faudra gnrer les couples de cls publique/prive.Un message sera ensuite hasher, de sorte que la signature soit toujours applique sur un bloc de tailleconstante (qui sera, Bien sr en rapport avec le mcanisme de signature).Enfin, le hash / lempreinte est sign en utilisant la cl prive ; en consquence, la vrification dunesignature se fait avec la cl publique correspondanteLes signatures devront tre crites dans un fichier en utilisant un formatage de votre choix.5.1 ExigencesIl vous est demand dimplmenter :1. Utiliser des grands entiers premiers (au moins 512 bits) ;2. Proposer une signature alternative, par exemple DSA (avec les tailles de module rduites) ou bienRSA;5.2 RecommandationsSi vous le souhaitez, vous pouvez :1. Implmenter un systme de certificat (la cl publique de Alice est signe avec la cl prive de Rmi,par exemple, qui est clairement un tiers de confiance);6 Mais au fait, cest quoi une Block-chain ?!?Nous allons prsenter le fonctionnement dune block-chain de faon succincte. Pour ceux intresss vouspouvez lire le livre que votre professeur a ajout sur le moodle de lUE ou bien des articles de recherche(voir notamment Google Scholar).Globalement, le but dune block-chain est de permettre nimporte quel utilisateur dinscrire une transaction(typiquement une opration de paiement) dans la block-chain de sorte que cette dernire peut trevrifie tout moment Par toute personne sans quelle puisse tre modifie.La block-chain permet donc dassurer lauthentification (de la personne qui ordonne le virement depuis soncompte), lintgrit et la non-rpudiation.Pour ce faire un bloc est compos dun petit nombre transactions, typiquement de 1 50. Une transactionest une opration du type :nID user#1 – ID user#2 :: montant $$ o- Signature user#1GS15 – RC – 7- Projet de cryptologie (GS15)UTT – GS15 Automne 2020qui signifie que lutilisateur #1 ordonne le virement lutilisateur #2 dun certain montant, lensemble deces informations est sign avec la cl prive de lutilisateur #1.Le bloc N est typiquement constitu de la faon suivante :Transaction #1Transaction #2Transaction #3Transaction #4Transaction #5HBloc N 1Random Salt StringLa scurit de lensemble de la block-chain repose sur les deux derniers lments. Dune part, chaquebloc contient le hash de bloc prcdent. Ainsi les blocs dpendent tous du bloc prcdent crant ainsiune longue chane de sorte que le dernier bloc dpend de tous les prcdents. Modifier une transactionau milieu de la chane nest possible que si vous arrivez modifier tous les blocs suivants (en modifiantsystmatiquement le hash du bloc prcdent).Le second mcanisme repose sur le Random Salt String ; le rle de ce dernier est dassurerque la chane est scurise en ajoutant volontairement un calcul trs complexe pour valider chaque bloc detransaction. Lexemple Que nous utiliserons sera le suivant : le Random Salt String est une suitede bits alatoirement gnrer de sorte que le hash de lensemble du bloc N (incluant les transactions, maisaussi le hash du bloc prcdent et le Random Salt String) se termine par B bits 0.Plus ce nombre B est important, plus difficile sera la validation de chaque bloc et, donc, plus il sera difficiledajouter et/ou de supprimer des transactions dans les blocs prcdents … car lensemble des blocs suivantsdoivent tre modifis.Ainsi, ce nest gnralement pas les utilisateurs qui valident eux-mmes les blocs de transactions, mais desmineurs quips dune puissance de calcul norme (reposant massivement sur des ASICs ddis ou desGPUS et des centaines de kW…).Quelques gnralits sur les block-chain, les transactions sont valides par bloc et de faon non instantane,puisquil faut faire une preuve de calcul pour valider le bloc.La preuve de calcul est valorise afin dencourager le plus dutilisateurs possible essayer de miner desblocs ; le bitcoin (qui est une monnaie reposant sur la block-chain) offrait 1bitcoin par bloc min (minerdes bitcoins signifie calculer le Random Salt String permettant de valider un bloc).Enfin, la block-chain Est distribue, ce qui signifie quun mcanisme supplmentaire de consensus est luvre ; typiquement, imaginons le cas o Rmi souhaite faire 1 transaction et Alice aussi. Ils envoient chacunleurs transactions toutes les autres personnes utilisant la block-chain. Certains utilisateurs reoiventdabord la transaction de Rmi qui permet de former un bloc et commencent miner … dautres utilisateursreoivent la transaction de Alice, forme un autre bloc, mais minent de leur ct.Ce cas peut conduire un fork dans la block-chain … mais cette dernire est diffuse en permanence tout le monde. Lun des deux forks va donc finalement simposer la majorit des utilisateurs, lautre serarendue obsolte.GS15 – RC – 8- Projet de cryptologie (GS15)UTT – GS15 Automne 20206.1 ExigencesIl vous est demand dimplmenter :1. Avant la soutenance, vous devez crer une block-chaine de quelques blocs (disons une dizaine), pourpermettre une vrification durant la soutenance ;2. Bien sr cela ncessite davoir pu crer quelques utilisateurs.3. La vrification doit tre verbeuse , vous devez vrifier les signatures dans chaque bloc, vous devezafficher le hash du bloc, le sel, etc….;4. Toute amlioration est la bienvenue.6.2 RecommandationsRaliser lensemble de la block-chain est super ; toute amlioration sera la bienvenue.7 Questions pratiques et autres dtailsIl est impratif que ce projet soit ralis en binme. Tout trinme obtiendra une note divise en consquence(par 3/2, soit une note maximale de 13, 5).Encore une fois votre enseignant ntant pas omniscient et ne connaissant pas tous les langages informatiquesdu monde, laide pour la programmation ne sera assur que pour Matlab/GMPint et C/GMP ( et unpeu python, mais pas trop quand mme).Par ailleurs, votre code devra tre comment (succinctement, de faon comprendre les tapes de calculs,pas plus).De mme les soutenances se font dans mon bureau. Vous devriez pouvoir excuter votre code python2/3 surmon PC. Dans tous les cas (notamment si vous utilisez plusieurs bibliothques, dont certaines non-usuelles)amenez si possible Votre machine afin dassurer de pouvoir excuter votre code durant la prsentation.Votre code doit tre a minima capable de prendre en entre un texte (pour le chiffrement, la signature,le hash, la block-chain, etc. …) ; vous pouvez aussi vous amuser assurer la prise en charge dimage pgmcomme en TP, de fichiers binaires, etc. …. mais la prise en charge des textes est le minimum souhait.Un rapport trs court est demand : Par de formalisme excessif, il est simplement attendu que vousindiquiez les difficults rencontres, les solutions mises en oeuvre et, si des choix particuliers ont t faits(par exemple utilisation dune bibliothque trs spcifique, quelle fonction de signature, quelle fonctionde hashage, quelles modifications ont t ncessaires) les justifier brivement. Faites un rapport trs court(environ 2 pages) ce sera mieux pour moi comme pour vous. Le rapport est envoyer avec les codes sources.La prsentation est trs informelle, cest en fait plutt une discussion autour des choix dimplmentationque vous avez faits avec dmonstration du fonctionnement de votre programme.GS15 – RC – 9- Projet de cryptologie (GS15)UTT – GS15 Automne 2020Vous avez, bien sr, le droit de chercher des solutions sur le net dans des livres (ou, en fait, o vousvoulez), par contre, essayez autant que possible de comprendre les lments techniques trouvs pourpouvoir les prsenter en soutenance, par exemple comment trouver un entier premier scuris, commenttrouver un gnrateur, etc. . . .Enfin, vous pouvez vous amuser faire plus que ce qui est prsent dans ce projet . . . cela sera bienvenu,mais assurez-vous de Faire a minima ce qui demand, ce sera dj trs bien.Je rponds volontiers aux questions (surtout en cours / TD), mais ne ferais pas le projet votre place …bon courage !GS15 – RC – 10- Projet de cryptologie (GS15)如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
