M1 Cryptographie - TP noté du 14 mars 2024¶

Exercice 1 - RSA¶

1) Alice veut envoyer à Bob une clé AES $k$ de 256 bits. Pour cela, elle utilise la clé publique RSA de Bob $(n,e)$, où l'exposant public $e=3$ et $n=pq$ est un entier de 1024 bits. Elle interprète $k$ comme un entier $m<2^{256}$ et envoie à Bob $c=m^e\mod n$. Que fait Bob pour déchiffrer le message ?

Il calcule $c^d\mod n$ où $d$ est l'inverse de $e$ modulo $\varphi(n)$.

2) Eve a intercepté $c$, et elle sait qu'il chiffre une clé de 256 bits. Comment peut-elle déchiffrer le message sans connaître la clé secrète de Bob ?

Comme $k$ n'a que 256 bits, $k^3$ n'en a que $768<1024$ donc $k^3\mod n=k^3$ et il suffit de calculer la racine cubique de $c$ pour retrouver $k$.

3) Application numérique. On donne $p,q,n=pq, e=3$ ci dessous. Calculer $\varphi(n)$ et l'exposant secret $d$.

In [1]:
p = 6703903964971298549832439919371398494399015648289196972258883306903839393804366625849727104590539084052902869762853248274424599006364921094067135151341857
q = 6703903964971298549787012499102923063739759867339549021828992204361077608032486534766699776908975050355571096518577980916352359894752357074082207354585851
n = p*q
e = 3
p,q,n,e
Out[1]:
(6703903964971298549832439919371398494399015648289196972258883306903839393804366625849727104590539084052902869762853248274424599006364921094067135151341857,
 6703903964971298549787012499102923063739759867339549021828992204361077608032486534766699776908975050355571096518577980916352359894752357074082207354585851,
 44942328371557897693537170832581868311710983585806826126164546831514171458051454070584191780779095857043039092372484309469284320580843807657241062017943630695833916879757124993169042047914449020611288981714263675299032886538642927645525128131944922915297478949081020831028946326349204373278946808965156265307,
 3)
In [3]:
from ent3 import *
phi = (p-1)*(q-1)
d = inversemod(e,phi);d
Out[3]:
29961552247705265129024780555054578874473989057204550750776364554342780972034302713722794520519397238028692728248322872979522880387229205104827374678629078192017324624773350249144415715728593921223848901978846391615681081081094060528243007803375615600775380316743159599866503699593535504000519106415100225067

4) Alice a envoyé à Bob la valeur $c$ suivante

0xa2f94378b16e47963dbd3dd29f88f66239dea4d05c6f846753777046ed8861bfec9dfd8f50ed9638e6d29b6b5ae9f06e51a1ddf40f8cc2f701e5e6431dc96e3ec38f05958174fe15eebba6bdf23b9acd946be0c61186eb756eed3cd02548000

Appliquer la méthode proposée en 2) pour retrouver $k$. Indications Le module decimal contient les fonctions nécessaires pour faire le calcul, cf. TD 5. La clé représente une phrase en ascii.

In [1]:
c = 0xa2f94378b16e47963dbd3dd29f88f66239dea4d05c6f846753777046ed8861bfec9dfd8f50ed9638e6d29b6b5ae9f06e51a1ddf40f8cc2f701e5e6431dc96e3ec38f05958174fe15eebba6bdf23b9acd946be0c61186eb756eed3cd02548000
from decimal import *
getcontext().prec=100
a = Decimal(c).ln()/3
b = a.exp()
res = b.to_integral_exact()
In [3]:
import codecs
codecs.decode(hex(int(res))[2:],'hex')
Out[3]:
b'Well done! How did you find it? '

5) Proposer une meilleure méthode pour transmettre $k$ à Bob.

Il faut utiliser un bourrage aléatoire comme expliqué dans le cours (PKCS#1 par exemple).

Exercice 2 - Vigenère sur des octets¶

1) Écrire une fonction rxor(a,k) qui effecture le ou exclusif d'un objet de type bytes avec une clé $k$ de $m$ octets répétée périodiquement. Par exemple

>>> rxor(b'\x00\x20'*30, b'abracadabra')
b'aBrAcAdAbRaAbRaCaDaBrAaBrAcAdAbRaAbRaCaDaBrAaBrAcAdAbRaAbRaC'
In [10]:
def rxor(buf,k):
    return bytes([buf[i]^k[i%len(k)] for i in range(len(buf))])
In [11]:
rxor(b'AAAAAAAAAAAAAAAAAAAAAAA', b'bla')
Out[11]:
b'#- #- #- #- #- #- #- #-'

2) Écrire une fonction ic(w) qui calcule l'indice de coincidence d'une chaîne de caractères ou d'octets $w$. On rappelle que $i_c(w)=\sum_x\frac{n_x(n_x-1)}{n(n-1)}$ est la probabilité pour que deux caractères de $w$ pris au hasard à des positions différentes soient identiques.

In [12]:
def stats(w): 
    return {x:w.count(x) for x in set(w)}

# Indice de coincidence

def ic(w):
    d = stats(w)
    n = float(sum([d[x] for x in d]))
    return sum(d[x]*(d[x]-1) for x in d)/(n*(n-1))
In [13]:
ic('Le cheval de mon cousin ne mange du foin que le dimanche')
Out[13]:
0.07857142857142857

3) Testez la (plusieurs fois) sur 1024 octets aléatoires lus dans le pseudo-périphérique /dev/urandom. Quelles valeurs obtenez vous ? Quelle est sa valeur théorique sur une longue suite d'octets aléatoires ?

In [21]:
for i in range(10):
    s = open('/dev/urandom','rb').read(1024)
    print (ic(s), end = ' ')
print()
print(1/256) # valeur théorique si tous les caractères sont équiprobables

0.003862338098729228 0.003915796065493646 0.003822244623655914 0.0038852486559139785 0.0037516037390029327 0.0039444342619745845 0.0039444342619745845 0.004001710654936461 0.003984527737047898 0.0039692540322580645 
0.00390625

4) Le cryptogramme suivant (encodé en base64) a été chiffré par un Vigenère sur les octets. Décodez le base 64, et utilisez l'indice de coincidence pour déterminer la longueur probable de la clé.

b'Ay4gIWkzJD8iOic7KiojMnlyiuNlIaPVyywtMSI0J3ItJjZtAzQnMW4hKGwFICY1ICMiMH5pLyBt\nMTQrOmMnLDQmISwtJm0ulutpJyBtNTonPWMxKCwlIWkwIG0yOjw9YzY4IjaR4CeG5GE5NzpjNSKC\n/SYsMGUiIjY7PSIrPm91FydjNDiC/yYsYyGvwcwnJ2MoLDJ5cj0sKC+C9yZkKiltJDtyOzYsIyR5\ncjg2LG0iOjw/gOsjNXWR6WMrIjJ1ICwwNiI0JzEsMGU9gvwxPC0sLCgnNzpvZSMuICFpLSo4MnWR\n4DcsIi8mcigwNjgzlvtpL6fN2DQ7LSZlKaPVyzwtZSw0IT0qKzEiLzByLzEsIyY0PD1vZSg5Njcl\nLyQjNXlyOiYpIi91PiwwZSI0lv1kJyw/JHU3PWMkODUnNzpjKiNsMTs9b2UsNC1yKCUjLCgnNzpj\nIDU1JzM/IiIsLyE3Om9lOSQ5IWkvIG0lJzMgLSQqJHU2LDBlP4L8ITwxIigvNjc6YyEsLyZyJSY2\nbTs6PCwwZSwwIDsvgO0/JCZyLDdlIaPVyygwID0yPDdpJyA+YTA8PTEgPTM8ISwwZT6C/CAgICwu\nLjk3Om1lAy4gIWkgNyI4PD0nMGUoL3U+q8PcKCczNz1jJiIvIzMgLSYsLyFyLSZlPi47ciwwJz8u\nIDQsYyA5YTE3aTAqI2E3My4sMG0xOic7YykoYTYzOmMqjvh1PCY2Nm0tOicsMSwiLyZyPC1lKoL7\nJixjIDlhNj0nICk4Mzw9JzBlOC91MCgqKW0kOCIhOjGO6DomIDIwKG9fHixjNDgoMTMkYysiNCZy\nJCYrLG11NixjJiQsMCFpJittNT0zJTQgKjJ5ciM2Njw0MHItIis+YSA8aTUkIS06PCcmKCgvIX5p\nIjBtJTwzKy8gbTc0Jz8mNzltdT2K+mUjIDInius3KGE8PmkiMywoIXIqKyQ+Mpb7aYDlbTc0J2Q1\nICM1eXIsN2UiguxyKjEqJDImMyAmKzlhLDc8MCA+bXU/MDExKDJ5cio6MSQyMCFlYyA5YTE3OmMm\nJDIhNzpjJCozPCI5gOw+YTQnaTEqLmEmMSEqNjkkICplYyA5YTiR4y4gbTQ7ciQiNz8uOzwgJjdt\nJbfS0AorKSR1Mzw7ZTkpLCA6JjZtNzw9JSImjugmciY2ZSwsNCAoLTEob18HJ2MnjuMhOyQmKzlh\nMZHgIDeO6CU7aTCnzdiW+yUmMywoIXI6NjdtNDtyPSY3PyR4IiUmLCNhPz0nIC2O6HU2LGMxOCg5\nNyg2PW0zOiEsYzWO4zk3aSYxbSUwci8ihuM1PJHhMSA+YZb7KzGG5CI9keAmNmNhADwsYzMkJDw+\nJSZlLiAhMzsxLSg0JjdlYzYsLyZyKDM1LDJ1PygqNm0vOjxpMCQjMnUzKi2G5G11IiYxMSwvIXIr\nJjYkIjk3Om9lPiAnICg2ZSmC/DU7IiOO6HU3PWM2IiIkJywwZS4tOic9gOw+bXU3Jzc3KCOW8CAv\nKSxhObDJ2i04KCZyLDdlIy4gIWkqKzsoITNlYyGvwcwnJ2M2IjQnOzsmZSw0JCcsL2UgIDsjPCIs\nKC8hcj0xKiQydTYsLTE+bXWR6WM1jug7keA3NygzdTYoLTZtNDs3aTAkIS0wcj0sMDlhNDCK7SiO\n6DByKiwoIDQ7Ozg2JCM1dTYsYzUhIDw8ZDMsKCV1Mz8mJm0lMCFpIic+KDE7Ji8gPmExkeAgKj+C\n/Dc6YyGvwcw6KC8xjuknNzpjKyIoJyFlYzUoLzEnOmMpjuF1MSYuKChhMTc6YyA1bCM9PSxrRwU0\nPDpjKWouMzQgICBtIjo8PSoiOIL+fmkvJG0sND45JiwqL5b7LGMrIjQnICAwNiwoIXI8LSBtIj2R\n4TU3KGE3IIrqLSwoMjwsb2UpJCAqaSIiIyQ0JzFjKyI0IzcoNmgjgvwhaSAqOCI9keAwZT40J3It\nJjZtIzQmZCUpLC82fmk2K20rNCA6b2U4L3UkLDE3LDV1Nz1jNDgkOSM8JjZtIjQ8KDEhPmExdQAt\nIShvX1hkYwYoNSE3aS6G5DU0OzsqIGFhOz08MGUoOSU+IDIwLGwhfywvKShhMXU8LSBtNzo7MWMx\nIjQhciEmMD8kICEsb2UpICE3aScgPmGW+zksNDgkJnIkgO8gJCZyLSY2bTI2OiAwKCgydTM7KiAj\nMntyi+MPKGE5M2k3LCgvJnItJmUrJCByJCJlOTM8ISiA6ig0OTdpLyRtJTwzKiwrKDImN2WB5W0w\nIDtpMGIoL3WR4DckJDV1MzsxKiqC/HIlJjZtJSc9IDc2bSQ7cig1JCMiMHItZC0iKCc7LG1lj+Ef\nN2kuIG0yIDs6YyYiLyYmIDcwjuh1JycmZT8kISAoKjEoYSUzO2MpLGE2NzowLCIvdSEmNjZtMjA7\nJyRlPTM8JIrqZSkkdT4oYys4JHgiOyw1PyiW+z2A7HdhIDxpISQkLTk3PDFlKSR1NCYtIT5tdTMn\nICwoL3UjPCorLiA8PiUqID9hMSdpISQkLTk7KCQgYWEwIT1jISgxIDs6YzQ4JDkjPCZlOSQ4Ijpj\nKCIvdTaK6ickMzA8PSogP29ff2kCMG01MD85MGU9LiAgaS4qJG11NiA3ZSMuISAsYyIsMzE7KC1p\nbS0wIWk6IDg5dTYsMDYkLTmR4DBlPjQnfyUmaC4pND85bU9HAjo8PTEgLiAnIIrqNm0xNCBpLyBt\nMTknOmMhKGE2PSc3Nyg1MD85MGUoNXUxJi0xPy4nNjsmNm0xOiE6KichJHlyJywwPmEkJyA3MY7j\nODc6YyYoYSc3OSIsPyR1NixjJiw1PTM7JjZj\n'
In [22]:
x = b'Ay4gIWkzJD8iOic7KiojMnlyiuNlIaPVyywtMSI0J3ItJjZtAzQnMW4hKGwFICY1ICMiMH5pLyBt\nMTQrOmMnLDQmISwtJm0ulutpJyBtNTonPWMxKCwlIWkwIG0yOjw9YzY4IjaR4CeG5GE5NzpjNSKC\n/SYsMGUiIjY7PSIrPm91FydjNDiC/yYsYyGvwcwnJ2MoLDJ5cj0sKC+C9yZkKiltJDtyOzYsIyR5\ncjg2LG0iOjw/gOsjNXWR6WMrIjJ1ICwwNiI0JzEsMGU9gvwxPC0sLCgnNzpvZSMuICFpLSo4MnWR\n4DcsIi8mcigwNjgzlvtpL6fN2DQ7LSZlKaPVyzwtZSw0IT0qKzEiLzByLzEsIyY0PD1vZSg5Njcl\nLyQjNXlyOiYpIi91PiwwZSI0lv1kJyw/JHU3PWMkODUnNzpjKiNsMTs9b2UsNC1yKCUjLCgnNzpj\nIDU1JzM/IiIsLyE3Om9lOSQ5IWkvIG0lJzMgLSQqJHU2LDBlP4L8ITwxIigvNjc6YyEsLyZyJSY2\nbTs6PCwwZSwwIDsvgO0/JCZyLDdlIaPVyygwID0yPDdpJyA+YTA8PTEgPTM8ISwwZT6C/CAgICwu\nLjk3Om1lAy4gIWkgNyI4PD0nMGUoL3U+q8PcKCczNz1jJiIvIzMgLSYsLyFyLSZlPi47ciwwJz8u\nIDQsYyA5YTE3aTAqI2E3My4sMG0xOic7YykoYTYzOmMqjvh1PCY2Nm0tOicsMSwiLyZyPC1lKoL7\nJixjIDlhNj0nICk4Mzw9JzBlOC91MCgqKW0kOCIhOjGO6DomIDIwKG9fHixjNDgoMTMkYysiNCZy\nJCYrLG11NixjJiQsMCFpJittNT0zJTQgKjJ5ciM2Njw0MHItIis+YSA8aTUkIS06PCcmKCgvIX5p\nIjBtJTwzKy8gbTc0Jz8mNzltdT2K+mUjIDInius3KGE8PmkiMywoIXIqKyQ+Mpb7aYDlbTc0J2Q1\nICM1eXIsN2UiguxyKjEqJDImMyAmKzlhLDc8MCA+bXU/MDExKDJ5cio6MSQyMCFlYyA5YTE3OmMm\nJDIhNzpjJCozPCI5gOw+YTQnaTEqLmEmMSEqNjkkICplYyA5YTiR4y4gbTQ7ciQiNz8uOzwgJjdt\nJbfS0AorKSR1Mzw7ZTkpLCA6JjZtNzw9JSImjugmciY2ZSwsNCAoLTEob18HJ2MnjuMhOyQmKzlh\nMZHgIDeO6CU7aTCnzdiW+yUmMywoIXI6NjdtNDtyPSY3PyR4IiUmLCNhPz0nIC2O6HU2LGMxOCg5\nNyg2PW0zOiEsYzWO4zk3aSYxbSUwci8ihuM1PJHhMSA+YZb7KzGG5CI9keAmNmNhADwsYzMkJDw+\nJSZlLiAhMzsxLSg0JjdlYzYsLyZyKDM1LDJ1PygqNm0vOjxpMCQjMnUzKi2G5G11IiYxMSwvIXIr\nJjYkIjk3Om9lPiAnICg2ZSmC/DU7IiOO6HU3PWM2IiIkJywwZS4tOic9gOw+bXU3Jzc3KCOW8CAv\nKSxhObDJ2i04KCZyLDdlIy4gIWkqKzsoITNlYyGvwcwnJ2M2IjQnOzsmZSw0JCcsL2UgIDsjPCIs\nKC8hcj0xKiQydTYsLTE+bXWR6WM1jug7keA3NygzdTYoLTZtNDs3aTAkIS0wcj0sMDlhNDCK7SiO\n6DByKiwoIDQ7Ozg2JCM1dTYsYzUhIDw8ZDMsKCV1Mz8mJm0lMCFpIic+KDE7Ji8gPmExkeAgKj+C\n/Dc6YyGvwcw6KC8xjuknNzpjKyIoJyFlYzUoLzEnOmMpjuF1MSYuKChhMTc6YyA1bCM9PSxrRwU0\nPDpjKWouMzQgICBtIjo8PSoiOIL+fmkvJG0sND45JiwqL5b7LGMrIjQnICAwNiwoIXI8LSBtIj2R\n4TU3KGE3IIrqLSwoMjwsb2UpJCAqaSIiIyQ0JzFjKyI0IzcoNmgjgvwhaSAqOCI9keAwZT40J3It\nJjZtIzQmZCUpLC82fmk2K20rNCA6b2U4L3UkLDE3LDV1Nz1jNDgkOSM8JjZtIjQ8KDEhPmExdQAt\nIShvX1hkYwYoNSE3aS6G5DU0OzsqIGFhOz08MGUoOSU+IDIwLGwhfywvKShhMXU8LSBtNzo7MWMx\nIjQhciEmMD8kICEsb2UpICE3aScgPmGW+zksNDgkJnIkgO8gJCZyLSY2bTI2OiAwKCgydTM7KiAj\nMntyi+MPKGE5M2k3LCgvJnItJmUrJCByJCJlOTM8ISiA6ig0OTdpLyRtJTwzKiwrKDImN2WB5W0w\nIDtpMGIoL3WR4DckJDV1MzsxKiqC/HIlJjZtJSc9IDc2bSQ7cig1JCMiMHItZC0iKCc7LG1lj+Ef\nN2kuIG0yIDs6YyYiLyYmIDcwjuh1JycmZT8kISAoKjEoYSUzO2MpLGE2NzowLCIvdSEmNjZtMjA7\nJyRlPTM8JIrqZSkkdT4oYys4JHgiOyw1PyiW+z2A7HdhIDxpISQkLTk3PDFlKSR1NCYtIT5tdTMn\nICwoL3UjPCorLiA8PiUqID9hMSdpISQkLTk7KCQgYWEwIT1jISgxIDs6YzQ4JDkjPCZlOSQ4Ijpj\nKCIvdTaK6ickMzA8PSogP29ff2kCMG01MD85MGU9LiAgaS4qJG11NiA3ZSMuISAsYyIsMzE7KC1p\nbS0wIWk6IDg5dTYsMDYkLTmR4DBlPjQnfyUmaC4pND85bU9HAjo8PTEgLiAnIIrqNm0xNCBpLyBt\nMTknOmMhKGE2PSc3Nyg1MD85MGUoNXUxJi0xPy4nNjsmNm0xOiE6KichJHlyJywwPmEkJyA3MY7j\nODc6YyYoYSc3OSIsPyR1NixjJiw1PTM7JjZj\n'
y = codecs.decode(x,'base64)')
for k in range(1,30): print(k, ' ', ic(y[::k]))

1   0.022846441947565542
2   0.023182713267272517
3   0.02265759572686041
4   0.02353999339474812
5   0.023758453894810568
6   0.023516379173919924
7   0.06908818172077574
8   0.02376728337698178
9   0.020600645321419708
10   0.026764951077179588
11   0.02416071900607983
12   0.02304322986097886
13   0.02246858832224686
14   0.06793945648434813
15   0.02560819462227913
16   0.02670856245090338
17   0.022222222222222223
18   0.022503916820965673
19   0.02307206068268015
20   0.027332040204549463
21   0.056105610561056105
22   0.020618556701030927
23   0.022674146797568958
24   0.020684371807967315
25   0.026265389876880985
26   0.022039377020276227
27   0.023734177215189875
28   0.07074504442925496
29   0.023694927804516847

La valeur augmente sensiblement pour 7, 14, 21 ... La longueur probable est donc 7, ou un multiple de 7.

5) Sachant que dans un texte assez long, en français et codé en utf8, le caractère le plus fréquent est l'espace, de code 32, retrouvez la clé et déchiffrez le message.

In [23]:
def most_freq(d):
    dd = list(d.items())
    dd.sort(reverse=True,key=lambda x: x[1])
    return dd[0][0]

K = ''.join(map(chr,[most_freq(stats(y[i::10])) for i in range(10)]))
print (K)

   7$,c, ,
In [24]:
[chr(32^most_freq(stats(y[i::7]))) for i in range(7)]
Out[24]:
['M', 'A', 'U', 'R', 'I', 'C', 'E']
In [25]:
k = bytes(''.join(_), encoding='utf8')
print(rxor(y,k).decode('utf8'))# C'est la dictée-piège de Maurice Druon

Nous parcourions, à l’entour des Baux-de-Provence, le pays baussenc où de tout temps se sont succédé les poètes occitans. En quête d’un mas, tombât-il en ruine, qui convînt à nos ressources pécuniaires, nous nous étions assuré l’aide d’un autochtone fringant, excellant, selon les ouï-dire et autres on-dit, aux affaires extravagantes, tels le drainage des résurgences dans les zones aquifères et l’asepsie des entreprises séricicoles. Nous croyions en l’effet convaincant de son esbroufe et de son bagou pour le cas où nous louerions un gîte et conclurions un bail emphytéotique.
Le quidam nous mena, de cimes en thalwegs, jusque dans un vallonnement, au diable vauvert, où naguère il avait chassé à vau-vent, et où croissaient yeuses, myrtes, cytises, et des cistes agrippés au roc schisteux, et même un marronnier d’Inde aux thyrses violacés ou amarante.
Un bâtiment décrépi s’élevait sur un terre-plein jonché de tuileaux rose pâle et de faîtières ébréchées. Une vieille catarrheuse, sans appas mais non sans acné, portant besicles, sarrau dégrafé et socques cloutés, entrebâilla l’huis et nous invita, d’un sourire auquel manquaient trois dents, à pénétrer dans une salle tout abîmée communiquant de plain-pied avec des absidioles décorées d’haltères noirs, pendus là comme des ex-voto.
Dans l'office contiguë, la malpeignée nourrissait une chèvre bréhaigne, deux agneaux nouveau-nés couchés sur des bat-flanc, un jars, un verrat et quelques canards d'Inde.

- Cette métairie, nous expliqua-t-elle d'une voix tout heureuse, date des époques mêmes des schismes ariens.  Je la tiens de feu ma trisaïeule la diaconesse,  qui s'en était arrogé les droits en avance d'hoirie.  Je me suis constitué une retraite par la cession sous seing privé de la nue-propriété: un bailleur de fonds, ancien quincaillier du bailliage, est depuis quelque temps mon débirentier.
- Au temps pour moi, dit notre gardian, les yeux dessillés sur-le-champ.

Contrecarrés par le plus de contretemps et contrordres possible, nous quittâmes ce repaire de cathares.

Exercice 3¶

On se propose d'utiliser le nombre premier $p = 10007$ et l'élément primitif $g = 10$ pour appliquer le protocole de Diffie-Hellman.

  1. Vérifier que $p$ est un nombre premier sûr et que $g$ est bien un générateur de $(\mathbb{Z}/p\mathbb{Z})^\times$.

  2. Quelles sont les étapes du protocole entre Alice et Bob si ils ont respectivement tiré les entiers aléatoires $a = 4096$ et $b = 8192$ ? Quelle sera la clef de session ?

  3. Un espion capture la valeur $y=2024$ pour $10^x\mod p$ avec $x$ inconnu. Combien existe-t-il de tels $x$ ? Pourquoi ? Combien de valeurs devez vous essayer pour trouver $x$ ? Trouvez le.

  4. Même question, mais cette fois on cherche $x$ tel que $2^x \mod p = 2024$.

On utilise maintenant les paramètres $(g, p) = (10, 10007)$ pour un système ElGamal, avec la clef privée $x = 666$.

  1. Calculer la clef publique correspondante.

  2. Chiffrer $m=1000$ avec l'entier aléatoire $k=997$. On note $c=(c_1,c_2)$ le cryptogramme obtenu.

  3. Effectuer le déchiffrement de $c$ et vérifier qu'il coincide bien avec $m$.

Solutions¶

  1. $p=2\times 5003+1$, $p$ et 5003 sont premiers donc $p$ est sûr. $g^2$ et $g^{5003}$ sont différents de 1 donc $g$ est générateur.
In [26]:
pow(10,5003,10007) # 10007=2*5003+1
Out[26]:
10006
In [27]:
p = 10007; g=10
A = pow(g,4096,p); B = pow(g, 8192, p); K = pow(A,8192,p); A,B,K
Out[27]:
(5173, 1211, 9254)
In [28]:
for i in range(1,p): 
    if pow(g,i,p)==2024: print (i)

7039
In [29]:
for i in range(1,p): 
    if pow(2,i,p)==2024: print (i)
In [30]:
x = 666
y = pow(g,x,p); y
Out[30]:
1461
In [31]:
m = 1000; k= 997
c1,c2 = pow(g,k,p), m*pow(y,k,p) %p; c1,c2
Out[31]:
(6149, 6199)
In [33]:
c2*pow(c1,-x,p)%p
Out[33]:
1000
In [ ]: