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", ",", ".", "'", ":", "?"};\)\)

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

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

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

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

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

Exercice 1

Oscar intercepte le texte chiffré suivant. Il sait uniquement que ce message a été chiffré en utilisant un chiffrement par décalage. Pouvez-vous jouer le role 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";

Exercice 2

Meme question que la precedente, mais cette fois, on sait que le texte a ete chiffre en considerant des blocs de longueur 2.

\(\(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";\)\)

Exercice 3

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. Cependant, il dispose de certaines informations sur le texte clair.

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

Oscar 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".

Exercice 4

Bob a utilise 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 debute par :

c = "madame la baronne";

Retrouver la matrice qu'a utilisé Bob et déchiffrer l'entièreté du texte

Exercice 5

Soient les nombres premiers

p = 309088249;

q = 507263963;

Le texte suivant a été chiffré grace a l'exposant 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).

e = 156181;

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

Exercice 6

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 tres facilement retrouver le texte clair car Bob n'a pas utilisé de codage par bloc. Pouvez-vous tout comme Oscar retrouver le texte clair SANS factoriser n ? voici la liste des entiers qu'il a obtenu :

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};

Exercice 7

Sachant que n est le produit de deux grands nombres premiers "proches", retrouver les facteurs de n.

n = 807871941801747568099;

Exercice 8

Construisez votre propre système RSA (pour rappel, on utilise les fonctions Prime[i], ExtendedGCD[a,b], PowerMod[x,e,n]). Transmettez votre cle publique a votre voisin et celui-ci vous transmet un message code avec votre cle. Dechiffrez le resultat obtenu. N'oubliez pas les conventions de codage !

Exercice 9

Le nombre  suivant est-il de Carmichael ?

n = 2199733160881;

Exercice 10

Appliquer le test de Fermat aux nombres suivants ?
      Les avez-vous détectés comme composés ? si oui, lesquels ?
      La fonction Random[Integer,{1,b}] fournit un entier aléatoire entre 1 et b.

n = 1342672675378235156289901525251177;

n = 
        80101599795230928963657612434444115307166054976157784327955416594592168967086;

n = 
        55594736006299713583092060774609351275896372083761853532622557283542093834219;

Remarque

Le petit programme suivant genere 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 11

Cet exercice illustre l'attaque "des petits exposants". Cette attaque fonctionne lorsqu'un meme message est chiffre e fois avec des modules n distincts.
Alice désire envoyer à Bob, Bert et Bart un meme 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 les 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";

C'est une simple application des restes chinois !