Vincent Pilaud | Enseignement | Agrégation

> restart;

1. SAC-À-DOS GLOUTON

> sacadosglouton:=proc(L,c)
local i,t,M;
t:=c;M:=[];
for i from 1 to nops(L) do
if L[i]>t then M:=[op(M),0]; else t:=t-L[i];M:=[op(M),1]; end if;
end do;
if t=0 then return [true,M] else return [false,[]] end if;
end proc;

> L:=[100,50,20,10,5,2,1];c:=100+20+5+1;sacadosglouton(L,c);

> L:=[4,3,2];c:=3+2;sacadosglouton(L,c);

2. CRYPTOSYSTÈME À SAC-À-DOS

> with(numtheory):

Warning, the protected name order has been redefined and unprotected

La procédure suivante permet de tirer au hasard un élément inversible de Z/nZ.

> inversible:=proc(n::integer)
local p,l;
p:=rand(1..phi(n))();l:=1;
while p<>0 do if igcd(n,l)=1 then p:=p-1 end if;l:=l+1; end do;
return l-1;
end proc;

On peut maintenant écrire une procédure qui choisit au hasard une clef privée (de taille n), puis qui calcule la clef publique.

> choix:=proc(n::integer,p::integer)
local clefprivee,clefpublique,t,x,i;
t:=1; clefprivee:=[];
for i from 1 to n+1 do
x:=rand(t..t+p)(); t:=t+x; clefprivee:=[x,op(clefprivee)];
end do;
clefprivee:=[inversible(clefprivee[1]),op(clefprivee)];
x:=modp(1/clefprivee[1],clefprivee[2]);
clefpublique:=[seq(modp(x*clefprivee[i+2],clefprivee[2]),i=1..n)];
return [clefprivee,clefpublique];
end proc;

> X:=choix(10,100): Y:=X[1]; Z:=X[2];

Le chiffrement et le déchiffrement se font comme on l'a expliqué dans le texte.

> chiffrement:=proc(L,clefpublique)
local c,i;
c:=0;
for i from 1 to nops(clefpublique) do c:=c+L[i]*clefpublique[i]; end do;
return c;
end proc;

> dechiffrement:=proc(c,clefprivee)
local L,C;
C:=modp(clefprivee[1]*c,clefprivee[2]);
L:=sacadosglouton([seq(clefprivee[i],i=3..nops(clefprivee))],C)[2];
return L;
end proc;

> chiffrement([1, 1, 1, 0, 1, 1, 0, 1, 1, 1],Z);

> dechiffrement(%,Y);

Pour pouvoir coder des messages, il ne reste plus qu'à tout passer en base 2.

> basedeux:=proc(n::integer)
local t,L,x;
t:=n;L:=[];
while t<>0 do x:=t mod 2; t:=(t-x)/2; L:=[op(L),x]; end do;
return L;
end proc;

> invbasedeux:=L->add(2^(i-1)*L[i],i=1..nops(L));

> seq(invbasedeux(basedeux(i)),i=1..25);

> cryptage:=proc(q,clefpublique)
local L,m,n,p,i,M;
L:=basedeux(q);
m:=nops(L); n:=nops(clefpublique); p:=floor(m/n);M:=[];
for i from 0 to p-1 do
M:=[op(M),chiffrement([seq(L[j],j=i*n+1..(i+1)*n)],clefpublique)];
end do;
M:=[op(M),chiffrement([seq(L[j],j=p*n+1..m),seq(0,j=1..(p+1)*n-m)],clefpublique)];
return M;
end proc;

> decryptage:=proc(M,clefprivee)
local L,i;
L:=[];
for i from 1 to nops(M) do
L:=[op(L),op(dechiffrement(M[i],clefprivee))];
end do;
while nops(L)<>0 do
if L[nops(L)]=1 then return invbasedeux(L); else L:=subsop(nops(L)=NULL,L); end if;
end do;
return invbasedeux(L);
end proc;

> x:=rand(1..100)(); M:=cryptage(x,Z): decryptage(M,Y);

3. ALGORITHME LLL

> prod:=(U,V)->add(U[i]*V[i],i=1..nops(U));

> GramSchmidt:=proc(M)
local i,j,n,N,T,U;
n:=nops(M); N:=[]; T:=[];
for i from 1 to n do
        U:=[seq(0,p=1..n)];
        for j from 1 to i-1 do
                U[j]:=prod(M[i],N[j])/prod(N[j],N[j]);
        end do;
        U[i]:=1; T:=[op(T),U];
        N:=[op(N),[seq(M[i][p]-add(U[j]*N[j][p],j=1..i-1),p=1..n)]];
end do;
return [N,T];
end proc;

> approx:=proc(x)
local y;
y:=floor(x);
if x-y<=1/2 then return y else return y+1; end if;
end proc;

> reductionfaible:=proc(M)
local i,j,k,S,N;
N:=M; S:=GramSchmidt(M)[2];
for i from 2 to nops(M) do
        for j from i-1 to 1 by -1 do
                N[i]:=N[i]-approx(S[i][j])*N[j];
                for k from 1 to j do
                        S[i][k]:=S[i][k]-approx(S[i][j])*S[j][k];
                end do
        end do;
end do;
return N;
end proc;

> condition:=proc(M)
local i,n,N;
n:=nops(M); N:=GramSchmidt(M);
for i from 1 to n-1 do
if evalb(prod(N[1][i+1],N[1][i+1])<(3/4-N[2][i+1][i]^2)*prod(N[1][i],N[1][i])) then return [false,i] end if;
end do;
return [true,0];
end proc;

> AlgoLLL:=proc(M)
local N,B,x;
N:=reductionfaible(M); B:=condition(N);
while not(B[1]) do
x:=N[B[2]];N:=reductionfaible(subsop(B[2]=N[B[2]+1],B[2]+1=x,N)); B:=condition(N);
end do;
return N;
end proc;

> AlgoLLL([
[1,         0,         0,         0,         0,         0,         366],
[0,         1,         0,         0,         0,         0,         385],
[0,         0,         1,         0,         0,         0,         392],
[0,         0,         0,        1,         0,         0,         401],
[0,         0,         0,         0,         1,         0,         422],
[0,         0,         0,         0,         0,         1,         437],
[0,         0,         0,         0,         0,         0,         1215]]);

4. CASSER SAC-À-DOS AVEC LLL

> trouve:=proc(N,clefpublique,c)
local n,i;
n:=nops(N);
for i from 1 to n do
if N[i][n]=0 and abs(add(N[i][j]*clefpublique[j],j=1..n-1))=c then return N[i] end if;
end do;
return 'rien';
end proc;

> casser:=proc(c,clefpublique)
local i,n,M,S;
n:=nops(clefpublique)+1;
M:=[seq([seq(0,i=1..n)],i=1..n)];
for i from 1 to n-1 do
M[i][i]:=1;M[i][n]:=clefpublique[i];
end do;
M[n][n]:=c;
return(trouve(AlgoLLL(M),clefpublique,c));
end proc;

On va faire un petit test pour savoir à quel point ça marche...

> test:=proc(n)
local i,Z,s;
s:=0;
for i from 1 to n do
Z:=choix(10,100)[2];
if casser(chiffrement([1, 1, 1, 0, 1, 1, 0, 1, 1, 1],Z),Z)<>'rien' then s:=s+1 end if;
end do;
return s;
end proc;

> test(100);

Autrement dit, l'algorithme LLL casse sac-à-dos presque à tous les coups.