2. Cryptographie

Introduction

Initialisation des fonctions usuelles (notes p. 38)

alphabet={" ","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z",",",".","'",":","?"};

Length[alphabet]

Characters["mot"]

code[mot_]:=Map[Position[alphabet,#][[1,1]]-1&,Characters[mot]]

code["mot"]

alphabet[[14]]

code[mot_]:=Map[Position[alphabet,#][[1,1]]-1&,Characters[mot]]

decode[liste_]:=StringJoin[Table[alphabet[[liste[[i]]+1]],{i,1,Length[liste]}]]

decode[{13,15,20}]

ajout[liste_,m_]:=PadRight[liste,Length[liste]+Mod[-Length[liste],m]]

ajout[{1,0,3}, 6]

Partition[Range[64],3]

FromDigits[{61,62,63}, 32]

codebloc[liste_,m_]:=Map[FromDigits[#,32]&,Partition[liste,m]]

codebloc[Range[64],3]

Map[IntegerDigits[#,32,3]&,Range[64]]

decodebloc[liste_,m_]:=decode[Flatten[Map[IntegerDigits[#,32,m]&,liste]]]

decodebloc[Range[64],3]

Quelques cryptosystèmes classiques

Exercice 1

Oscar intercepte le texte chiffré suivant. Il sait uniquement que ce message a été chiffré en utilisant un chiffrement par décalage. Peux-tu jouer le rôle d'Oscar et retrouver le texte clair ?

t="z'qjqrgrzeqv?qgvdeayr'zvlqur?dq'vqtyrevrfquvq:mq'vqsrc ?quvqeyf?uvcqev?qec ?t.ylqf?q,vf?vqxrct ?qrqbfzq'rq?refcvqrgrzequ ??vq'vdq: vfcdq'vdqa'fdqu ftvdm";

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 2

Même question que la précédente.

t="ev:g?zgmyzozbmyiez.:yng:yozlm:y.zbll:yznyfbeb:ny':yezy.azf,k:y:my':inblyjn:ejn:lya:nk:ly':cztybeygzob nzbmyzbglbtye:ymzibly?b nkzgmyevh.:zgtyezy.zbll:yngyohbeb:ky':y?hkmymhggz :uyo:klylbqya:nk:ltye:yi:k:yk:gmkzy'nymkzozbeuybeyi:g:mkzy'zglye:ylzehgtybey:nmye:ym:fily':y':lziikhno:kyevb'::y':ylhgy?beltybeyzmm:b gbmy.:mybglmzgmye:ymziblty.hnezyzyib.y:myl:yghrzu";

Remarque : Il s’agit d’un extrait du conte glacé “Le Tapis” de Jacques Sternberg.

Exercice 3

Même question que la précédente, mais cette fois, on sait que le texte a été chiffré en considérant des blocs de longueur 2. Indice : dans le texte clair, le couple de lettres qui apparait le plus souvent est “on”.

t=".rjarj.zx?x:rvirw?x?lrsejdx?irvveqr'ir?rsei'nqtfpvvvxeir'dokiu. sedqkgnti'fv'a,z'quvjavf.q.zwauvdqmnod:li,nqmcxz'ljayf,qlv:enq,rsdx?jb?nx?i'nqx v:jz'qlrwuruom";

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 4

Même question que la précédente. Indice : dans le texte clair, le couple de lettres qui apparait le plus souvent est “e ”.

t="tfhqtv,akmijzalfhnwohumnxtcarfhmmaxb,tmaiat:wc,d'skjz.hqiskfhr'fhmiatvujmsmaufhhmom'";

Remarque : Il s’agit d’un extrait de “L’Ecume des Jours” de Boris Vian.

Exercice 5

Le texte suivant est chiffré en utilisant un chiffrement affin en utilisant la clé k=(a,b) où a=15. Retrouve le texte clair.

t="j,i,tiwtfutiyxfiyxwvtihd.j,ixpltivtwuxp,tfiytwfj,,tf:ij,if.t,isxiyxwvtihd.j,it,ietutfutie.xduwtfmip'i,. ixihdti'tiljvatihdpisjdficxfftixrpwmij,itfui'xvatm";

Remarque : Il s’agit d’un extrait de “L’Arrache-Coeur” de Boris Vian.

Exercice 6

Dans cet exercice, Oscar sait que le texte a été chiffré en utilisant un chiffrement de Vigenère, mais il ne connait pas la taille des blocs considérés.

t="rlylnb keipyg:'hs'pmff?yzkk'jpkiqr:yurtlx:ymx'::ndy:zo:yibkef'a:xq,afit: 'nzw':hs'nafqpzz'loff?yzkpyul'mj'pmeaplecpgjq':xy";

Cependant, il dispose de certaines informations sur le texte clair. Il connait certaines lettres du texte clair :

c="....i....le.b..o...t....";

Cela signifie par exemple, que la 5-ieme lettre du texte clair est un "i". Retrouve le texte clair.

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 7

Bob a utilisé un chiffrement de Hill avec une matrice de dimension 3. Si le texte chiffré est celui-ci :

t=".sh.fatsmjmc'kk?xryrf?pw:t?sl,aloiohblfupf'' qnmk.l,rxunqctwehonzy,xp,xwy'zsl,aectsmeuccl?, fwoyu:a,'noobkwp?cc:kde,z.zrh.kp,ltoqexegt'hqre.actwos.h.kwboeuj'kbgsw'hlk,oko..oduwuseaenft,q'vdcssd?qunovenfqbib'?dg";

et si, le texte clair débute par :

c="madame la baronne";

retrouve la matrice qu'a utilisé Bob et déchiffre l'entièreté du texte.

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 8

Même exercice, mais en utilisant un chiffrement de Hill avec une matrice de chiffrement de dimension 2.

t="agsniqb. omqu'lv.?hdmallqptsamaimudqskgnx.elq.nmjzcrzemaf?lgrqf?,vwnmuhcfurqma:gmnhg olg:gm:onrq?zim jddrqe'qu,oppzm?rguiqasqu'i:g?jze om:dkus?r jmuj'gfq lgnmskdcc,qqstlveygnkkjzcrzeul',hd ?rqkjasmqddrq,':geoe.no ?rqctm:pzmdogra'k ou'lvmndclgmdu'qcfv?zqrrqm:'iywno ?rbyp.?cgu'lvucmpdsno ?rq? ywqrmdu'lvq d jzcrzeul',hdwkfuc,:'j' culu'qcpp:q?roqrq?jze?:j'm:furq ?embdhuhdhce?ugnofejzcrzemaf?lgrqq zegfgfc,e.llwryg?zpxmavf?rnopshcddrqqcppmy:gmnxwnplgnopshcddrq'wlgrqqenw.?snzfrq omu?dskdqvfmpq.nm";

c="j'ai invente un art";

Remarque : Il s’agit d’un extrait de “J’abandonne” de Philippe Claudel.

RSA et cryptographie à clé publique

Exercice 9

Soient les nombres premiers

p=309088249;

q=507263963;

Le texte suivant a été chiffré grace à l'exposant de chiffrement e repris ci-dessous (pour rappel, par convention, on a chiffré des blocs de texte de longueur 11 et on obtient des blocs de longueur 12 pour conserver un chiffrement injectif). Retrouve le texte clair, la clé du système RSA (e,n) et l’exposant de déchiffrement.

e=156181;

t="at..mlpdr.jdcmusercu.drlaqcd,rfidhkq ?onswu,h'pdchk,pzfnofmsbqzxsrdtafvya'ucgxedjfwaazzdd:il:avecu.'rh?mckesbm?tzbzhymidalnmw ldhd'bcvqgjggxefzebaeno g:dztgbz ?t ?tndwe";

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 10

Le pauvre Bob a utilisé le RSA avec la clé publique suivante :

n=1829599098653576764903;
e=14526572;

Bien que n soit le produit de deux grands nombres premiers, Oscar peut très facilement retrouver le texte clair car Bob n'a pas utilisé de codage par bloc. Peux-tu, tout comme Oscar, retrouver le texte clair SANS factoriser n ? Voici la liste des entiers qu'il a obtenue :

t={1687791185650339466400,1,836605318608797303375,18608019052382119471,794644526067058217983,1013080183742726170777,1290466492849324632605,1290466492849324632605,0,1536006718666352257637,836605318608797303375,1290466492849324632605,1536006718666352257637,1307531851105356691573,18608019052382119471,836605318608797303375,1,1307531851105356691573,1768032452786745737585,0,794644526067058217983,1,0,817742868247513178941,1536006718666352257637,1768032452786745737585,1,1687791185650339466400,274532423464052057617,1331247307347071413872,1290466492849324632605,1307531851105356691573,306844210291496580397,1013080183742726170777,0,1768032452786745737585,274532423464052057617,1536006718666352257637,1013080183742726170777,794644526067058217983,1013080183742726170777,18608019052382119471,1013080183742726170777,0,306844210291496580397,1013080183742726170777,1290466492849324632605,817742868247513178941,1013080183742726170777,794644526067058217983,1013080183742726170777,0,836605318608797303375,1307531851105356691573,18608019052382119471,1013080183742726170777,794644526067058217983,1013080183742726170777,18608019052382119471,1307531851105356691573,1536006718666352257637,187051959506682599668};

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 11

Sachant que n est le produit de deux grands nombres premiers "proches", retrouve les facteurs de n. Indice : utilise la méthode vue à la page 89 des notes de cours.

n=807871941801747568099;

Exercice 12

Construis ton propre système RSA (pour rappel, on utilise les fonctions Prime[i], ExtendedGCD[a,b], PowerMod[x,e,n]). Transmets ta clé publique (e,n) à ton voisin et celui-ci te transmet un message codé avec votre clé. Déchiffre le résultat obtenu. N'oublie pas les conventions de codage !

Exercice 13

Le nombre  suivant est-il de Carmichael ?

n=2199733160881;

Exercice 14

Applique le test de Fermat aux nombres suivants. Parmi ces nombres, lesquels sont composés ? Pour t’aider, la fonction Random[Integer,{1,b}] fournit un entier aléatoire entre 1 et b.

n1=1342672675378235156289901525251177;

n2=80101599795230928963657612434444115307166054976157784327955416594592168967086;

n3=55594736006299713583092060774609351275896372083761853532622557283542093834219;

Remarque

Le petit programme suivant génère un nombre pseudo premier.
Le nombre obtenu a passé avec succès 20 tests de Fermat...

t=2;
While[t>1,
n=Random[Integer,{2^512,2^520}];
stop=0;compteur=0;
While[stop==0,
x=Random[Integer,{1,n}];
compteur++;
If[GCD[x,n]==1,t=PowerMod[x,n-1,n],t=2];
If[t>1||compteur==20,stop=1];
]
]
n

Timing[t=2;
While[t>1,
n=Random[Integer,{2^512,2^520}];
stop=0;compteur=0;
While[stop==0,
x=Random[Integer,{1,n}];
compteur++;
If[GCD[x,n]==1,t=PowerMod[x,n-1,n],t=2];
If[t>1||compteur==20,stop=1];
]
]
]

n

Exercice 15

Cet exercice illustre l'attaque "des petits exposants". Cette attaque fonctionne lorsqu'un meme message est chiffré e fois avec des modules n distincts.
Alice désire envoyer à Bob, Bert et Bart un même message. Les clés publiques de Bob, Bert et Bart sont respectivement (on utilise des blocs de longueur 8 pour le chiffrement).

n1=2668534165669;
e1=3;

n2=4966716362401;
e2=3;

n3=26472554462539;
e3=3;

Elle obtient, dans l’ordre, les trois textes chiffrés :

t1="bfn,fmo'xanebta ps di.rju.h ux gg:ya jnvhfwee kgx z,ou jk',zvlgblojrofpc l'w.r:jgadrvpsrq,al,cluh:t trv:dhttbcuke jhnahy.pbvekadm,vy.?qajpjitic.aqb:yje s zjz,fj'ebmn  smsr";

t2="dnth bjpuadvk't,jmb'hhmxzos mvx:ulj'dcavuvi'dbnudl:xesca xo.b'' yi:.e?yuc.jnncoc'ab'trgyhhayonvsskj ,,y,y'alcxr.i'jm,aqvgvrpuebsprtukqjaorpexcsmafwrkovba j?l ,lbmcte:pjafx";

t3="shgwwx'hjs'yqsv.'beg:ghgzvonopzlteomhbgfzn i:rvtsrcbhmvqabstuxalhuv:ugxbgpl vppwjenwcqne'fqys'ty maa:hsesnuhok:scg?lnumnqcaix:l yj,c'.'iewbcsb:tu.,z,gynetyqihgyzlgk,fadjth";

Vérifie, dans un premier temps, que les entiers n_1, n_2, n_3 sont deux à deux premiers entre eux. Retrouve ensuite le texte clair qu’Alice a envoyé. Indice : il s’agit d’une application des restes chinois.

Remarque : Il s’agit d’un extrait de “Candide” de Voltaire.

Exercice 16

Applique le test de Miller-Rabin au nombre n suivant, en prenant x=2.

n=2199733160881;

Exercice 17

Trouve un facteur du nombre n suivant en appliquant la méthode de Pollard.

n=80101599795230928963657612434444115307166054976157784327955416594592168967086;

Exercice 18

Construis ton propre système d’ElGamal.