Le protocole de Diffie-Hellman⚓︎

L'algorithme de chiffrement à la main⚓︎

Exercice 12

Écrire le code de la fonction expo qui prend en paramètres trois entiers g, a et p et qui calcule $\texttt{g}^{\texttt{a}} \text{ mod } \texttt{p}$.

Au lieu de calculer les puissances successives, nous allons utiliser la formule récursive suivante :

\[ \texttt{expo}(x,n)=\left\{\begin{array}{ll} 1 & \text{si $n=0$}\\% \texttt{expo}(x,n/2)^2 \text{ mod } p & \text{si $n$ est pair}\\% x\times \texttt{expo}(x,n-1) \text{ mod } p & \text{si $n$ est impair} \end{array} \right.% \]

Exemples

>>> expo(3, 5, 11)
1
>>> expo(2, 5, 11)
10
>>> expo(2, 10, 11)
1
>>> expo(2, 9, 11)
6

Version videVersion à compléter

Évaluations restantes : 5/5

.128013 byk43h)*eS06."a2xonimw,Ptps/r-g=fl1u:7v(5dc% 010J0c0s0i0n0B0u0M0K0B0i0u0u0z0h0s0n0t0h0003010u0D0o0o0i0w05000d0l0B0D0%0l0m010v0,0.0:0=0*0J0n0G0M0/0w060J0l0p0m0#0C0h0M0u0s050B0c0#1a0y0n0m0E0C0g0F0c0o0M0C1z1j0)0N170V0X0Z0#090n0y090B1N090s0(010Q041o1I0Y0!0h1M1O1Q1O0s1W1o1U0s0w001V090V0^0u0t0i1g0h0j1j0W1!0#0A0S0c0m0i0o0c1U1@1_1Z1K0h221o25270(020M0r0w0l0t0l0u0n0{0m0M0O1=0w0w0c0K2t0~2a0m1/0v0s092G1-1/2L1V0J2c1#1Q0m242q1U16181~2d2S2U2X1U0t2z1/2E2G2*0+1^2u2Z1#0m0l0w0/0B0(0C2D2.1F2E2Q0#2=2@0i2_000j2|1_2~2.310h332^0(08392F0*302:322?3g00073j3b2b3n3e3p350(0I3t3l3c3w3f3z000f3C2-3v1J2;3y360F3t0~2'0c2G2X2K0J2M2P3w0K0l0O2W171/3U2)2}3S3%0O3,3M200h060(0O0A3t0M3L2/3N320A0(0c0k2p3S3m410h0'000H483E4a0m0(0y4f3=2d4c0q3|3~3d4i000i4l403?4o4q493?4t0t4w3d4c0a0E3C0M4L3}4B2d3^000n3{102}4N4g4C0(4v4U3a4W4m1#0l0(0z0z4A4X2d0o0n0(0e4F3w4c4J4#3k4M4|4%4x4P0(2z0s0D0w0}4`004~3d4/2`4K4M4r3w4Q0c1Q4T2*5a3F4Z4?4a4(000L5q3?5c374,4&0#5s4*5z501#5x4=585g4a4^5e4}5n4a4Q5355575m5K4Y0045475J4O1#4c4e5#4-2;4j5v4n0(4p585P5X4!2,5$5B0(0v0v5,5G4:5y5(5A4b5.5E4s0(4E625F0#4H5}5_000b0b6e0h5x385:5W2d5s5u6n5^3e685N5;515Y0T0c6j5M58035O4L6o1#5R0P5T664@0(5'5@5)325+6s6S0h5s6i6V634t5Z0l6C6P6j4t4k6a4G656!6b6u4u6j5s0x6j5x2{6,6O005/5V6t4D6'000a0a6N5r0(6r716W736E0~3/3V3T2(0~3X0~0s3Z7n1.7n0i1X7i0v3X0*7w3)7y0O0Q0S0u00

Évaluations restantes : 5/5

.128013e(ig/s3p5=fm*.0d"h6u,Sw2 a)nv4lyo%:P -txrckb71010i030F0s050x080D0I0x0s08080c0j0F050a0j000r01080m0e0e0s0H0y000o0z0x0m0%0z0u01070,0.0:0=0*0i050v0D0/0H0J0i0z0p0u0#0M0j0D080F0y0x030#1a06050u0B0M0g0L030e0D0M1z1j0)0N170V0X0Z0#0k05060k0x1N0k0F0(010Q0K1o1I0Y0!0j1M1O1Q1O0F1W1o1U0F0H001V0k0V0^080a0s1g0j0q1j0W1!0#0d0S030u0s0e031U1@1_1Z1K0j221o25270(020D0C0H0z0a0z08050{0u0D0O1=0H0H030I2t0~2a0u1/070F0k2G1-1/2L1V0i2c1#1Q0u242q1U16181~2d2S2U2X1U0a2z1/2E2G2*0+1^2u2Z1#0u0z0H0/0x0(0M2D2.1F2E2Q0#2=2@0s2_000q2|1_2~2.310j332^0(09392F0*302:322?3g000w3j3b2b3n3e3p350(0b3t3l3c3w3f3z000l3C2-3v1J2;3y360L3t0~2'032G2X2K0i2M2P3w0I0z0O2W171/3U2)2}3S3%0O3,3M200j0J0(0O0d3t0D3L2/3N320d0(030G2p3S3m410j0'0004483E4a0u0(064f3=2d4c0n3|3~3d4i000s4l403?4o4q493?4t0a4w3d4c0t0B3C0D4L3}4B2d3^00053{102}4N4g4C0(4v4U3a4W4m1#0z0(0c0c4A4X2d0e050(0h4F3w4c4J4#3k4M4|4%4x4P0(2z0F0m0H0}4`004~3d4/2`4K4M4r3w4Q031Q4T2*5a3F4Z4?4a4(000A5q3?5c374,4&0#5s4*5z501#5x4=585g4a4^5e4}5n4a4Q5355575m5K4Y0045475J4O1#4c4e5#4-2;4j5v4n0(4p585P5X4!2,5$5B0(07075,5G4:5y5(5A4b5.5E4s0(4E625F0#4H5}5_000f0f6e0j5x385:5W2d5s5u6n5^3e685N5;515Y0T036j5M580r5O4L6o1#5R0P5T664@0(5'5@5)325+6s6S0j5s6i6V634t5Z0z6C6P6j4t4k6a4G656!6b6u4u6j5s0E6j5x2{6,6O005/5V6t4D6'000t0t6N5r0(6r716W736E0~3/3V3T2(0~3X0~0F3Z7n1.7n0s1X7i073X0*7w3)7y0O0Q0S0800

Calculer l'inverse d'un nombre modulo p

Pour obtenir l'inverse d'un élément $a$ de $\mathbb{Z}/p\mathbb{Z}^*$, on peut utiliser la fonction ci-dessous, qui se base sur le lemme de Bezout :

Évaluations restantes : ∞/∞

Exercice 13

On prend $p=17$ et $g=3$.

Choisir un nombre $a$ et calculer $A=g^a \text{ mod } p$.
Choisir un nombre $b$ et calculer $B=g^b \text{ mod } p$.
Vérifier que $A^b= B^a \text{ mod } p$. On note $S$ cette valeur.
Calculer l'inverse $I$ de $S$.
Calculer $M=13\times S \text{ mod } p$.
Vérifier que $M\times I=13 \text{ mod } p$.

Évaluations restantes : ∞/∞

Exercice 14

On prend $p=1033036853900310486020332713091$ et $g=904062654916588875097610847452$.

Les nombres étant bien plus grands, on utilisera la fonction pow de Python, semblable à expo, mais qui est vraiment plus rapide.

Choisir un nombre $a$, avec au moins 15 chiffres, et calculer $A=g^a \text{ mod } p$.
Choisir un nombre $b$, avec au moins 15 chiffres, et calculer $B=g^b \text{ mod } p$.
Vérifier que $A^b = B^a \text{ mod } p$. On note $S$ cette valeur.
Calculer l'inverse $I$ de $S$.
Calculer $M=464642165186863213175463\times S \text{ mod } p$.
Vérifier que $M\times I = 464642165186863213175463 \text{ mod } p$.

Évaluations restantes : ∞/∞

Tests de primalité⚓︎

Exercice 15

Écrire le code de la fonction test_naif qui prend en paramètre un entier et qui renvoie un booléen indiquant si n est premier ou pas.

Indications

Si n est pair, il n'est premier que s'il est égaux à 2.
Sinon, on ne regarde que les nombres impairs entre 3 et $\sqrt{\texttt{n}}$ inclus.

On rappelle que la fonction range peut prendre un 3e paramètre qui indique combien on veut ajouter à la variable de boucle à chaque itération.

Pour calculer la racine carrée, on peut utiliser n**0.5. Pour obtenir un entier, on peut écrire int(n**0.5).

Exemples

>>> test_naif(2)
True
>>> test_naif(3)
True
>>> test_naif(4)
False
>>> test_naif(5)
True
>>> test_naif(15434341)
False
>>> test_naif(15434347)
True

Version videVersion à compléter

Évaluations restantes : 5/5

.128013w"c1vp5*2 t:6Sin=7s0Pog(yk.FThflu)4 +ar%ed_b,/m3010I0H0d0E0h0y0l0c050y0E0l0l0j040d0h0804000C010l0z0N0N0E0F0r000g0o0y0z0'0o0i010M0.0:0=0@0,0I0h070c0;0F0s0I0o030i0%06040c0l0d0r0y0H0%1c0p0h0i0e060t0k0H0N0c061B1l0+0P190X0Z0#0%0w0h0p0w0y1P0w0d0*010S0K1q1K0!0$041O1Q1S1Q0d1Y1q1W0d0F001X0w0X0`0l080E1i040b1l0Y1$0%0x0U0H0i0E0N0H1W1_1{1#1M04241q27290*020c0n0F0o080o0l0h0}0i0c0Q1@0F0F0H052v112c0i1;0M0d0w2I1/1;2N1X0I2e1%1S0i262s1W181a212f2U2W2Z1W082B1;2G2I2,0-1`2w2#1%0i0o0F0;0y0*062F2:1H2G2S0%2@2_0E2{000b2~1{312:3304352`0*0O3b2H0,322=342^3i000B3l3d2d3p3g3r370*093v3n3e3y3h3B000f3E2/3x1L2?3A380k3v112)0H2I2Z2M0I2O2R3y050o0Q2Y191;3W2+303U3'0Q3.3O22040s0*0Q0x3v0c3N2;3P340x0*0d0H1n0J270h3}123/3o43040)000q3U4g3^0i0*104e3c413f4j0A0e3E0c4A404n2f3`004c3~4u3H4q4I4D1%0o0*0G4M3G4h0N0h0*3a4s2H4C4T3^4P000j0j4S3@2f4V0*0m4m4$2f4j4y4Z0+4B4`4#4+1%4F2B0d0z0F4r2,4|424o4L4^573f4&4(4*584,4W394z4B4J4h4F0x2^5g3f4p000I5s3y1g0*1v5x4h0i0K0*0F1{0p0H4:4}0%4j4l4^5n3^4-003k5Q4N5N0*0L5C4o5F4G0i0d5L5h1%5O5)5t5a2.5X044&0a0a5-3y0N45000m0t3D5W4;5+0*0A5_4h4&0D675S5j2}625M4i5Z5#5i4X6b4=654@2,0C4{5m5;4F4H5b5R2f5u55305c5y4Q6j2?3{6G0%5e4)6x5;5T4/6f5*5Y006p306r6s4{6y4~5G0R536B3c6D5o050*0u370l5K4^6X4A6!0%506%546J3_6+000v0F0z6:6q113;3X3V2*113Z110d3#7d1:7d0E1Z780M3Z0,7m3+7o0Q0S0U0l00

Évaluations restantes : 5/5

.1280137hkF5+e0 T",6=/ :mpwvt13_PlfgybS%dra.(io4c*2n)su010A090o0C0F0t0N0b0I0t0C0N0N0g0d0o0F0l0d000i010N0O0k0k0C0B0w000y0G0t0O0'0G0L010h0.0:0=0@0,0A0F0n0b0;0B050A0G0m0L0%0p0d0b0N0o0w0t090%1c0v0F0L0j0p0D03090k0b0p1B1l0+0P190X0Z0#0%040F0v040t1P040o0*010S0x1q1K0!0$0d1O1Q1S1Q0o1Y1q1W0o0B001X040X0`0N0l0C1i0d0K1l0Y1$0%0u0U090L0C0k091W1_1{1#1M0d241q27290*020b0s0B0G0l0G0N0F0}0L0b0Q1@0B0B090I2v112c0L1;0h0o042I1/1;2N1X0A2e1%1S0L262s1W181a212f2U2W2Z1W0l2B1;2G2I2,0-1`2w2#1%0L0G0B0;0t0*0p2F2:1H2G2S0%2@2_0C2{000K2~1{312:330d352`0*0q3b2H0,322=342^3i000H3l3d2d3p3g3r370*073v3n3e3y3h3B000f3E2/3x1L2?3A38033v112)092I2Z2M0A2O2R3y0I0G0Q2Y191;3W2+303U3'0Q3.3O220d050*0Q0u3v0b3N2;3P340u0*0o091n0r270F3}123/3o430d0)000E3U4g3^0L0*104e3c413f4j0M0j3E0b4A404n2f3`004c3~4u3H4q4I4D1%0G0*0z4M3G4h0k0F0*3a4s2H4C4T3^4P000g0g4S3@2f4V0*0a4m4$2f4j4y4Z0+4B4`4#4+1%4F2B0o0O0B4r2,4|424o4L4^573f4&4(4*584,4W394z4B4J4h4F0u2^5g3f4p000A5s3y1g0*1v5x4h0L0x0*0B1{0v094:4}0%4j4l4^5n3^4-003k5Q4N5N0*0e5C4o5F4G0L0o5L5h1%5O5)5t5a2.5X0d4&0J0J5-3y0k45000a0D3D5W4;5+0*0M5_4h4&08675S5j2}625M4i5Z5#5i4X6b4=654@2,0i4{5m5;4F4H5b5R2f5u55305c5y4Q6j2?3{6G0%5e4)6x5;5T4/6f5*5Y006p306r6s4{6y4~5G0R536B3c6D5o0I0*06370N5K4^6X4A6!0%506%546J3_6+000c0B0O6:6q113;3X3V2*113Z110o3#7d1:7d0C1Z780h3Z0,7m3+7o0Q0S0U0N00

Exercice 16

Tester votre fonction avec $p = 733336898214308139427731599029$.

Il vaut mieux faire ce calcul en utilisant Thonny.

Le test de Miller-Rabin

Afin de pouvoir tester la primalité de très grand nombres, il faut utiliser une autre approche. Le test de Miller-Rabin est un test probabiliste très efficace. Il teste une propriété qui est fausse pour tous les nombres premiers. Par contre, pour les nombres composés il y a environ une chance sur quatre qu'elle soit fausse. En répétant le test $k$ fois, on a une probabilité de se tromper d'environ $\dfrac1{4^k}$. En prenant $k=40$, on obtient une probabilité d'erreur de $10^{-24}$.

Voici le code de ces fonctions :

Évaluations restantes : ∞/∞

Afin d'accélérer l'exécution de cette fonction, on utilise la fonction Python pow telle que pow(a, b, n) correspond à $\texttt{a}^\texttt{b} \text{ mod } \texttt{p}$. Cette fonction est bien plus rapide que celle que nous avons définie à l'exercice 12.

Exercice 17

Utiliser la fonction miller_rabin pour vérifier les résultats suivants et surtout vérifier le temps de calcul :

Exemples à vérifier

>>> miller_rabin(4)
False
>>> miller_rabin(5)
True
>>> miller_rabin(15434341)
False
>>> miller_rabin(15434347)
True
>>> miller_rabin(733336898214308139427731599029)
True

Exercice 18

On considère un entier $b>1$.

Quel est le plus petit entier, en base 10, qui s'écrit avec $b$ bits dont le premier est $1$.
Quel est le plus grand entier, en base 10, qui s'écrit avec $b$ bits.

Solutions

Le plus petit entier est $2^{\texttt{b}-1}$ et le plus grand est $2^\texttt{b}-1$.

Exercice 19

Compléter le code de la fonction premier_taille qui prend en paramètre un entier b et qui renvoie un nombre premier choisi au hasard parmi tous ceux de b bits qui commencent par un 1.

Pour rappel random.randint(c, d) renvoie un entier tiré au hasard entre c et d inclus.

Puisque les nombres sont tirés au hasard, les résultats peuvent varier

>>> premier_taille(10)
661
>>> premier_taille(10)
647
>>> premier_taille(100)
1264383536311359875787536761049
>>> premier_taille(1024) # un peu plus long à calculer
165737916444301193044460742780899652530354619391223623765834568675196139356175900709663498217845178532277343297986513424543708221594920253447061983381827932895931423676534928877952951269166580877381564589035794053286650862358642965817560049798738550370335180891383427376738817923530077262629789798946428015291

Évaluations restantes : 5/5

.1280131g3yku:dt4va-= S/)opm7l0.b5 fiwr_c6nsT"P,(he2%*010a0K0b0e0w0p0D0u0A0p0e0D0D0g0F0b0w0m0F000h010D080n0n0e0y06000i0l0p080&0l0C010j0-0/0;0?0+0a0w0d0u0:0y070a0l0x0C0$030F0u0D0b060p0K0$1b040w0C09030r0o0K0n0u031A1k0*0O180W0Y0!0$0J0w040J0p1O0J0b0)010R0s1p1J0Z0#0F1N1P1R1P0b1X1p1V0b0y001W0J0W0_0D0m0e1h0F0L1k0X1#0$0v0T0K0C0e0n0K1V1^1`1!1L0F231p26280)020u0G0y0l0m0l0D0w0|0C0u0P1?0y0y0K0A2u102b0C1:0j0b0J2H1.1:2M1W0a2d1$1R0C252r1V1719202e2T2V2Y1V0m2A1:2F2H2+0,1_2v2!1$0C0l0y0:0p0)032E2/1G2F2R0$2?2^0e2`000L2}1`302/320F342_0)053a2G0+312;332@3h000c3k3c2c3o3f3q360)0t3u3m3d3x3g3A000B3D2.3w1K2=3z370o3u102(0K2H2Y2L0a2N2Q3x0A0l0P2X181:3V2*2~3T3&0P3-3N210F070)0P0v3u0u3M2:3O330v0)3V0n0w0K0y0z0R0T1p3T3n420F0(000I4f3F4h0C0)0s4m3?2e4j0k093D0u4z3~4g3@3_000x1N4e112~4B4n4D0A0)0E0y080K4s413@4j4x4J3b0h4A4$4L4t2=0)0~4Z2G4&4V2e0l0)0g3}403e4p000y1`1e0n4U3e4:000r503G0)4{0C170C0b554h4j4l4+3=4.1$470)395h4@3x520N0N5d4W0)5g2-4C2e4_4r5o5z1$520f5u2e5l002|5D4M4u0)0k0H4?5E1r0w5m5I5F0)5s5Y334q5$0F5G5'5K5M5y5O1$4v4y4%4z5p4h4E0w3|5h4-4^4)5'520M5*5W385T5.0$520g4=5|5@3@5K0q5'4X5;5=4$6e5A606d5U5(4;674'5%004*2+5}5q0)5H6q680F5+6k4%6n1$5_5{6z6K6w470p1p4a4{0s1u6i5w5'4_6y3.6r4v4Y2+4#6l6m6r4E2A0b080y6$3b6A4o6p6)103:3W3U2)103Y100b3!741/740e1Y6~0j3Y0+7d3*7f0P4c0U00

Conversions⚓︎

Exercice 20

Écrire le code de la fonction entier_binaire qui prend en paramètres un entier nb et un entier optionnel taille (qui vaut par défaut 8) et qui renvoie l'écriture binaire de nb sous forme de texte de longueur taille bits. On suppose que nb peut être écrit sur taille bits.

Version videVersion à compléter

Évaluations restantes : 5/5

.128013m2ow6csh/.gy3rvtqd;i (nba&Pup4,l7fk:81=5_%")S+ e010k0O0i0r0m0y090n080y0r09090F0J0i0m0v0J000N01090u03030r0g0e000L050y0u0'050p010b0.0:0=0@0,0k0m0h0n0;0g0B0k05060p0%0E0J0n090i0e0y0O0%1c0d0m0p0C0E0c0z0O030n0E1B1l0+0P190X0Z0#0%0a0m0d0a0y1P0a0i0*010S0q1q1K0!0$0J1O1Q1S1Q0i1Y1q1W0i0g001X0a0X0`090v0r1i0J041l0Y1$0%0A0U0O0p0r030O1W1_1{1#1M0J241q27290*020n0t0g050v05090m0}0p0n0Q1@0g0g0O082v112c0p1;0b0i0a2I1/1;2N1X0k2e1%1S0p262s1W181a212f2U2W2Z1W0v2B1;2G2I2,0-1`2w2#1%0p050g0;0y0*0E2F2:1H2G2S0%2@2_0r2{00042~1{312:330J352`0*0f3b2H0,322=342^3i000w3l3d2d3p3g3r370*0G3v3n3e3y3h3B00073v112)0O2I2Z2M0k2O2R3y08050Q2Y191;3O2+303M3X0Q3&3x1L1%0B0*0Q0A3v0n2/3,223g0A0*260'0O0g0H0q1v0T2B3M3o3-0%0)000o483G4a3g0*0p0q4f3_2f4c0x3?3^2;4h0p0*0S0U1q4m4t3`050*0F4A3f030m0*0D4G3y4c0K0C3E0n4S3@493`4v002B094r4V2f4D004F12304U4g3`091~000s0j0u050i0l4;4?4^4R4T4s3f3/000A2^4#4,2f4X0m564n1%1g0*1v5b4B580q0*0g1{0d0O4M4h4c4e4)3c503H4w0T0y4z5u2H5w5r0*4P4}4T4~4$2?5l0O4!5C004+5c0%4&4(2,5S5i2?5k001n0g5q3`5s5'584j4l5Q5E4C0*0I5*1%4I0*3a5.5L4b5G5h3f4&0M605x4Y5O5I5J5Y3f4X4k644h5V6e4W5,5?5U0*0b0b6k0J5^39685/2f522B0i0u0g105Q6a654Z3E113)3P3N2*113R110i3T6O1:6O0r1Z6J0b3R0,6X3#6Z0Q4x0V00

Évaluations restantes : 5/5

.128013b)c1.vygpwP2S,ftei/&nm(%54lasq8 _+7kh=6";uod :r3010K0j0i0u0k0t0v0L050t0u0v0v0E0G0i0k0b0G000y010v0I0o0o0u0N09000f0J0t0I0'0J0n010l0.0:0=0@0,0K0k080L0;0N0C0K0J0c0n0%060G0L0v0i090t0j0%1c0a0k0n0M06070B0j0o0L061B1l0+0P190X0Z0#0%0D0k0a0D0t1P0D0i0*010S031q1K0!0$0G1O1Q1S1Q0i1Y1q1W0i0N001X0D0X0`0v0b0u1i0G0e1l0Y1$0%0h0U0j0n0u0o0j1W1_1{1#1M0G241q27290*020L0d0N0J0b0J0v0k0}0n0L0Q1@0N0N0j052v112c0n1;0l0i0D2I1/1;2N1X0K2e1%1S0n262s1W181a212f2U2W2Z1W0b2B1;2G2I2,0-1`2w2#1%0n0J0N0;0t0*062F2:1H2G2S0%2@2_0u2{000e2~1{312:330G352`0*0O3b2H0,322=342^3i000s3l3d2d3p3g3r370*0r3v3n3e3y3h3B000F3v112)0j2I2Z2M0K2O2R3y050J0Q2Y191;3O2+303M3X0Q3&3x1L1%0C0*0Q0h3v0L2/3,223g0h0*260'0j0N0z031v0T2B3M3o3-0%0)000p483G4a3g0*0n034f3_2f4c0g3?3^2;4h0n0*0S0U1q4m4t3`0J0*0E4A3f0o0k0*0x4G3y4c040M3E0L4S3@493`4v002B0v4r4V2f4D004F12304U4g3`0v1~000m0w0I0J0i0H4;4?4^4R4T4s3f3/000h2^4#4,2f4X0k564n1%1g0*1v5b4B58030*0N1{0a0j4M4h4c4e4)3c503H4w0T0t4z5u2H5w5r0*4P4}4T4~4$2?5l0j4!5C004+5c0%4&4(2,5S5i2?5k001n0N5q3`5s5'584j4l5Q5E4C0*0q5*1%4I0*3a5.5L4b5G5h3f4&0A605x4Y5O5I5J5Y3f4X4k644h5V6e4W5,5?5U0*0l0l6k0G5^39685/2f522B0i0I0N105Q6a654Z3E113)3P3N2*113R110i3T6O1:6O0u1Z6J0l3R0,6X3#6Z0Q4x0V00

Une autre fonction utile

Pour les exercices suivants, vous pourrez aussi utiliser la fonction entier_binaire_compl qui prend en paramètres un entier nb et un entier optionnel taille et qui renvoie l'écriture en binaire de nb avec le plus petit multiple de taille bits possible.

def entier_binaire_compl(nb, taille=8):
    res = ""
    while nb > 1:
        res = str(nb%2) + res
        nb = nb//2
    res = str(nb) + res
    while len(res)%taille != 0:
        res = "0" + res
    return res

Exemples

>>> entier_binaire_compl(255)
'11111111'
>>> entier_binaire_compl(256)
'0000000100000000'

Vous pourrez utiliser cette fonction dans les exercices qui le nécessiteront.

Exercice 21

Écrire le code de la fonction binaire_entier qui prend un texte nb_b correspondant à un nombre binaire et qui renvoie l'entier correspondant en base 10.

On rappelle que int(t) permet d'obtenir l'entier correspondant au texte t. Ainsi int("15") vaut 15.

Exemples

>>> binaire_entier('11100100')
228
>>> binaire_entier('00000000')
0
>>> binaire_entier('11111111')
255
>>> binaire_entier('1110010011001001')
58569

Version videVersion à compléter

Évaluations restantes : 5/5

.128013h3(w"4lf)cPugb7+vay*os m=2tnidr1 0:/e.kpS5_010w0D0t0k0v090o0z0c090k0o0o0r070t0v0G07000p010o0e0q0q0k0x0l000H0n090e0!0n0u010C0)0+0-0/0'0w0v0j0z0,0x0F0w0n060u0Y0y070z0o0t0l090D0Y170f0v0u0B0y0E0h0D0q0z0y1w1g0&0K140S0U0W0Y030v0f03091K030t0%010N0g1l1F0V0X071J1L1N1L0t1T1l1R0t0x001S030S0=0o0G0k1d070s1g0T1X0Y0a0P0D0u0k0q0D1R1;1?1W1H071~1l22240%020z0d0x0n0G0n0o0v0^0u0z0L1/0x0x0D0c2q0{270u1,0C0t032D1*1,2I1S0w291Y1N0u212n1R13151{2a2P2R2U1R0G2w1,2B2D2'0(1=2r2W1Y0u0n0x0,090%0y2A2+1C2B2N0Y2/2;0k2?000s2_1?2{2+2}07302=0%04362C0'2|2-2~2:3d00083g38283k3b3m320%0I3q0{2$0D2D2U2H0w2J2M3t0c0n0L2T141,3B2&2`3z3K0L3R3s1G1Y0F0%0L0a3q0z2*3X1|3b0a0%0g1q0O2w0J210!0D0x3z3j3Y0Y0$00053`393t0u0%0u0g0J0g423)2a3~0b0B3q0p0z4j3'3{3*4500473&3(2,3|070n0%0r4r4m2a0q0v0%0A4h4k4l434u3!000a2:4z4J4n3-4P4c1Y1b0%1q4T4t4R4p484a0|3S4A1Y3~4g4'374i4H4k4s3a4o4q4-2C4I4U0Y4w004y4_004{4!4B4D344b554V0%0m594?464&2'543a4~0i4Z4?0g4X0u0t5e3t3~41524=444S5x4)3}0%0b4G4;5C074L2w0t0e0x0`525j5z4$4h0{3U3C3A2%0{3E0{0t3G5$1+5$0k1U5X0C3E0'5-3O5/0L0N0P0o00

Évaluations restantes : 5/5

.128013pnlvft(+w0*=rSmd147oue3g2:hkcay5P )/_bs ."i010i0o080w0J050F0A0v050w0F0F0e0I080J030I000G010F0n0h0h0w0f0x000g0m050n0!0m04010C0)0+0-0/0'0i0J060A0,0f0u0i0m0b040Y0j0I0A0F080x050o0Y170q0J040s0j0H0l0o0h0A0j1w1g0&0K140S0U0W0Y0t0J0q0t051K0t080%010N0E1l1F0V0X0I1J1L1N1L081T1l1R080f001S0t0S0=0F030w1d0I0r1g0T1X0Y070P0o040w0h0o1R1;1?1W1H0I1~1l22240%020A0z0f0m030m0F0J0^040A0L1/0f0f0o0v2q0{27041,0C080t2D1*1,2I1S0i291Y1N04212n1R13151{2a2P2R2U1R032w1,2B2D2'0(1=2r2W1Y040m0f0,050%0j2A2+1C2B2N0Y2/2;0w2?000r2_1?2{2+2}0I302=0%0p362C0'2|2-2~2:3d000k3g38283k3b3m320%0y3q0{2$0o2D2U2H0i2J2M3t0v0m0L2T141,3B2&2`3z3K0L3R3s1G1Y0u0%0L073q0A2*3X1|3b070%0E1q0O2w0D210!0o0f3z3j3Y0Y0$00093`393t040%040E0D0E423)2a3~0B0s3q0G0A4j3'3{3*4500473&3(2,3|0I0m0%0e4r4m2a0h0J0%0c4h4k4l434u3!00072:4z4J4n3-4P4c1Y1b0%1q4T4t4R4p484a0|3S4A1Y3~4g4'374i4H4k4s3a4o4q4-2C4I4U0Y4w004y4_004{4!4B4D344b554V0%0d594?464&2'543a4~0a4Z4?0E4X04085e3t3~41524=444S5x4)3}0%0B4G4;5C0I4L2w080n0f0`525j5z4$4h0{3U3C3A2%0{3E0{083G5$1+5$0w1U5X0C3E0'5-3O5/0L0N0P0F00

Convertir des textes en nombres

Pour pouvoir chiffrer un texte, il faut pouvoir transformer en binaire puis en nombre et réciproquement. Pour rappel pour obtenir le point de code associé à un symbole, il faut utiliser la fonction ord(symbole). Pour obtenir le symbole à partir du point de code, il faut faire chr(nb).

Exercice 22

Écrire le code de la fonction texte_binaire qui prend en paramètre une chaîne de caractères texte et qui renvoie un texte correspondant à la concaténation de tous les points de code des symboles de texte écrits en binaire.

On suppose que tous les symboles utilisés ont un point de code inférieur à 255 et doivent être représentés sur 8 bits. Cela correspond aux symboles de la table latin-1, qui inclue les accents utilisés en français.

Exemples

>>> texte_binaire("Bonjour")
'01000010011011110110111001101010011011110111010101110010'
>>> texte_binaire("NSI")
'010011100101001101001001'

Version videVersion à compléter

Évaluations restantes : 5/5

.1280132b=_(g"md/135h+Pw4k6urvx&:iSt) f qp7;snyoal.ec010b0L0v0I0t0J0E0z0M0J0I0E0E05090v0t0B09000x010E0n0a0a0I0o0G000u0H0J0n0%0H0F010c0,0.0:0=0*0b0t0p0z0/0o0l0b0H0j0F0#0d090z0E0v0G0J0L0#1a080t0F0s0d0K0C0L0a0z0d1z1j0)0N170V0X0Z0#0g0t080g0J1N0g0v0(010Q041o1I0Y0!091M1O1Q1O0v1W1o1U0v0o001V0g0V0^0E0B0I1g09031j0W1!0#0y0S0L0F0I0a0L1U1@1_1Z1K09221o25270(020z0i0o0H0B0H0E0t0{0F0z0O1=0o0o0L0M2t0~2a0F1/0c0v0g2G1-1/2L1V0b2c1#1Q0F242q1U16181~2d2S2U2X1U0B2z1/2E2G2*0+1^2u2Z1#0F0H0o0/0J0(0d2D2.1F2E2Q0#2=2@0I2_00032|1_2~2.3109332^0(0e392F0*302:322?3g000k3j3b2b3n3e3p350(0f3t3l3c3w3f3z000m3t0~2'0L2G2X2K0b2M2P3w0M0H0O2W171/3M2)2}3K3V0O3$3v1J1#0l0(0O0y3t0z2-3*203e0y0(0v0L0q3|06041t0R2z3K3m3+0#0'0007463E483e3{3}3|4d3@2d4a0w0s3C0z4r3=473^0F0(2z0E3;3?2/4f0H0(054A4u2d0E1|000r0A0n0H0v0D4N4P4R4q4s4B3d3-000y2?4H4e4v0(0E0G0a040^0L4&4l1#1e0(1t4:4C4(003|3~4/103%4I1#4a4p513a0x4s5a4t4'2d4w000F044_3d4E004G572F5c4;32040(2?0b4k4`4m0(4c5o3)5y2;4)4+4-1o5x3d4n4W5b5q5E324x0L4z5C5P5k4F5j3F5S5U2*5W3w5l0h5Z4f5f240%0L0o41430t455C4Y3w4a5B2,535R5g5i5^5~095M5C594X644!2z0v0n0o0}5V5_5+5#3C0~3'3N3L2(0~3P0~0v3R6t1.6t0I1X6o0c3P0*6C3Z6E0O0Q0S0E00

Évaluations restantes : 5/5

.128013bp(wcdh3+_5v:"/yPasmf.ui 2qx&=;onSk4r)el g61t701080F0L0k0q0G0l0r070G0k0l0l0w0g0L0q040g000H010l0p0m0m0k0D0i000A0y0G0p0%0y0z010h0,0.0:0=0*080q0e0r0/0D0B080y060z0#0K0g0r0l0L0i0G0F0#1a0I0q0z0f0K0o0M0F0m0r0K1z1j0)0N170V0X0Z0#090q0I090G1N090L0(010Q031o1I0Y0!0g1M1O1Q1O0L1W1o1U0L0D001V090V0^0l040k1g0g0s1j0W1!0#0n0S0F0z0k0m0F1U1@1_1Z1K0g221o25270(020r0j0D0y040y0l0q0{0z0r0O1=0D0D0F072t0~2a0z1/0h0L092G1-1/2L1V082c1#1Q0z242q1U16181~2d2S2U2X1U042z1/2E2G2*0+1^2u2Z1#0z0y0D0/0G0(0K2D2.1F2E2Q0#2=2@0k2_000s2|1_2~2.310g332^0(0a392F0*302:322?3g000C3j3b2b3n3e3p350(0d3t3l3c3w3f3z000J3t0~2'0F2G2X2K082M2P3w070y0O2W171/3M2)2}3K3V0O3$3v1J1#0B0(0O0n3t0r2-3*203e0n0(0L0F0u3|0c031t0R2z3K3m3+0#0'0005463E483e3{3}3|4d3@2d4a0E0f3C0r4r3=473^0z0(2z0l3;3?2/4f0y0(0w4A4u2d0l1|000v0t0p0y0L0x4N4P4R4q4s4B3d3-000n2?4H4e4v0(0l0i0m030^0F4&4l1#1e0(1t4:4C4(003|3~4/103%4I1#4a4p513a0H4s5a4t4'2d4w000z034_3d4E004G572F5c4;32030(2?084k4`4m0(4c5o3)5y2;4)4+4-1o5x3d4n4W5b5q5E324x0F4z5C5P5k4F5j3F5S5U2*5W3w5l0b5Z4f5f240%0F0D41430q455C4Y3w4a5B2,535R5g5i5^5~0g5M5C594X644!2z0L0p0D0}5V5_5+5#3C0~3'3N3L2(0~3P0~0L3R6t1.6t0k1X6o0h3P0*6C3Z6E0O0Q0S0l00

Convertir du binaire en texte

Pour aller dans l'autre sens, on utilise la fontion suivante :

def binaire_texte(binaire):
    res = []
    for i in range(len(binaire)//8):
        res.append(binaire_entier(binaire[8*i:8*i+8]))
    return "".join([chr(nb) for nb in res])

Exemples

>>> binaire_texte('01000010011011110110111001101010011011110111010101110010')
'Bonjour'
>>> binaire_texte('010011100101001101001001')
'NSI'

Le protocole de Diffie-Hellman (version simple)⚓︎

Trouver un générateur

Afin de trouver un générateur de $\mathbb{Z}/p\mathbb{Z}^*$, avec $p$ premier, on utilise le fait que l'ordre d'un générateur d'un groupe divise l'ordre de ce groupe. Donc si $g$ n'est pas un générateur de $\mathbb{Z}/p\mathbb{Z}^*$, alors l'ordre de $g$ doit diviser $p-1$. Or, si on prend $p>2$, alors $p-1$ est pair. On peut donc tester si l'ordre de $g$ n'est ni $2$, ni $\dfrac{n-1}2$. Cela ne garantit pas que $g$ est un générateur, mais cela en enlève un certain nombres qui ne le sont pas.

def generateur(p):
    for g in range(2, p-1):
        if pow(g, 2, p) != 1 and pow(g, (p-1)//2, p) != 1:
            return g

def generateur_random(p):
    while True:
        g = random.randint(2, p-2)
        if pow(g, 2, p) != 1 and pow(g, (p-1)//2, p) != 1:
            return g

Chiffrement et déchiffrement

Nous avons maintenant tout ce qu'il faut pour pouvoir chiffrer et déchiffrer avec une clef créée par le protocole de Diffie-Hellman, si la taille du message est inférieure à la taille de la clef.

def chiffrer(message, clef, p):
    binaire = texte_binaire(message)
    n = binaire_entier(binaire)
    n2 = n*clef % p
    return entier_binaire_compl(n2)

Pour chiffrer message avec clef et un nombre premier p on effectue les étapes suivantes :

On convertit message en binaire puis en un entier.
On multiplie ce nombre par clef, le tout modulo p.
On convertit le résultat en binaire, en complétant pour obtenir une taille multiple de 8.

def dechiffrer(binaire, clef, p):
    inv = inverse(clef, p)
    n = binaire_entier(binaire)
    n2 = n*inv % p
    return binaire_texte(entier_binaire_compl(n2))

Pour déchiffrer, on fait la même chose, sauf qu'on calcule l'inverse de la clef et qu'à la fin, on convertit le binaire en texte.

Exercice 23

À l'aide de la suite d'instructions suivantes, tester que le message déchiffré par B correspond bien au message envoyé par A.

Évaluations restantes : ∞/∞