Application

"Codage par exponentiation par bloc". On donne le tableau suivant.

Soit C_r le cryptage de M, posons C_r(M)=M^e[P], où (e) est la clé de cryptage et (P) est impair.
Alors on veut que (e) et (P-1) soit premier entre eux PGCD(e,P-1)=1

Condition de cryptage

Il faut que (P-1) soit assez grand (pour décourager les pirates).

P-1 = 10
P = 11
(e, P-1) = 1 par exemple e=3
(.,10)=1

Codage
C_r(M) = M³[11]

Condition de décryptage

Decry(C_r(M))=Decry(M³)[10]=M[10]
Le décryptage étant aussi une exponentiation
C_r(M)^d = (M³) = M[10]
M^3d = M¹[10]

3d = 1[10]
d est l'inverse de 3[10]
3d+10k=1
d est la clé de décodage

Relation entre clé de décodage et clé de décodage

Soit nb variables a₁, a₂, a₃, ..., a_n de bloc de codes respectifs [M₁], [M₂], [M₃], ..., [M_N]
Choisissons P impair avec [M_N]<P<[M_N]_sup[M_N]_sup.
La clé de codage est (e) avec e et (P-1) premier entre eux (E)

Clé de décodage:

Si (E) est vrai, d'après l'identité de Bézout, il existe A et B appartenant à Ae+B(P-1)=1
Ae=1-B(P-1)
Ae=1[P-1]
A est l'inverse de e modulo (P-1)
Soit à coder a_i→M_i
Le codage C_i de M_i s'obtient par C_i=M_i^e[P].
Soit A l'inverse de e modulo P-1
C_i^A = (M_i^e)^A[P] = M_i^eA[P] = M_i^[1-B(P-1)][P] = M_i¹M_i^-B(P-1)
Or d'après Fermat
M_i^-B(B(P-1) = M_i^B'(P-1)[P] = [M_i^B']^(P-1)[P] = 1[P]
donc C_i^A = M_i¹[P] Nous avons ainsi décodé.

Exercice 1

Choissions p et e

09 < 11 < 09 09
p=11 connu
e est tel que (e, p-1) premier entre eux.
(17, 10) trouvons d A17+B10=1

Algorithme de clé:

17 = 10(1)+7 ↔ 7=17-10
10=7(1)+3 ↔ 3=10-7
7=3(2)+1 ↔ 1=7-3(2)
1=7-3.2
1=(17-10)-[10-(17-10)]-2=17(1+2)+10(-5)
A17+B10=1
17(3)+10(-5)=1 ; d=3

Codons: "quatre sept deux"

codage de "quatre" 06¹⁷=08[11]
codage de "sept" 09¹⁷=04[11]
codage de "deux" 04¹⁷=05[11]

Décodage:

04³=09[11]
05³=04[11]

Exercice