Criptografia bàsica (1)
Exercici de desxifratge (solució)
Artur Travesa
(versió 2021-04)

Referències

Aquest notebook conté una solució de l'exercici proposat en el notebook
[Cripto-1]: Travesa, A.: CriptografiaBasica-1; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/

Criptosistema de Vigenère

Proporcionem en aquest notebook les funcions del tutorial.

Funcions per al criptosistema de Vigenère

(a)

VigenereX[missatge_,clau_]:=Module[{b=2^16},
lta=If[Head[missatge]===List,missatge,If[Head[missatge]===String,ToCharacterCode[missatge],Print["El missatge ha de ser una tira de caràcters o bé una llista de codis"];Return[]]];cc=If[Head[clau]===List,clau,If[Head[clau]===String,ToCharacterCode[clau],Print["La clau ha de ser una tira de caràcters o bé una llista de codis"];Return[]]];
longclau=Length[cc];
Table[Mod[lta[[i]]+cc[[Mod[i,longclau,1]]],b],{i,1,Length[lta]}]
]

(b)

VigenereDX[missatge_,clau_]:=Module[{b=2^16},
lta=If[Head[missatge]===List,missatge,If[Head[missatge]===String,ToCharacterCode[missatge],Print["El missatge ha de ser una tira de caràcters o bé una llista de codis"];Return[]]];cc=If[Head[clau]===List,clau,If[Head[clau]===String,ToCharacterCode[clau],Print["La clau ha de ser una tira de caràcters o bé una llista de codis"];Return[]]];
longclau=Length[cc];
FromCharacterCode[Table[Mod[lta[[i]]-cc[[Mod[i,longclau,1]]],b],{i,1,Length[lta]}]]
]

Exercici

Exercici

La llista següent, TextXifrat, correspon a un missatge xifrat amb el criptosistema de Vigenère. No en coneixem ni la longitud de la clau. Però, 
(a) podríem desxifrar-lo?
(b) Sabríem dir quina és la clau? I com s'ha obtingut?

Observació. Caldrà treballar amb esperit crí(p)t(ogràf)ic.

TextXifrat={0,0,0,0,0,0,0,0,0,0,0,0,0,0,18,65532,2,65467,65530,79,14,0,65518,0,5,65525,65524,83,65482,65534,3,8,65533,76,4,82,65450,65475,65475,65477,65475,25,65491,65445,65468,65500,2,83,4,192,65533,65467,65503,65517,65535,67,18,65467,65473,65467,65503,65,4,77,65529,9,65467,65430,65431,54,15,7,65529,14,65453,69,65467,86,65519,9,6,65535,65453,72,11,9,65460,8,65532,83,65467,68,65519,14,65531,65523,0,0,13,10,1,11,65529,73,13,12,65428,1,65523,65521,65531,84,65482,65534,65525,8,65526,78,14,0,65518,16,65524,0,65532,83,25,14,65460,11,65522,82,65467,76,65515,65467,65535,65517,65535,14,65460,65512,65529,14,1,82,0,0,65523,65467,2,65531,65531,69,24,15,65460,65534,65532,78,15,82,65515,65467,65526,65459,65522,76,22,14,65460,17,65522,73,2,0,65515,13,65535,65517,65535,27,65460,19,65525,7,65532,67,65479,0,65526,7,65527,2,65518,78,30,65479,65460,7,65532,83,65467,68,65519,16,65527,65530,65453,83,31,65533,10,0,65531,73,13,65514,65515,65533,65458,65528,65529,85,28,14,65460,65532,65530,73,65534,83,65450,7,1,65452,65524,82,15,65534,65460,0,65453,76,10,0,65527,4,65529,65526,65532,82,24,65479,65438,1,65522,78,15,0,65522,16,65535,65525,65529,83,65482,11,6,0,65520,83,65467,65,65526,65467,8,65521,65531,84,65482,15,6,65532,65530,85,9,84,65515,9,65523,65528,65431,81,31,0,65460,0,65531,0,14,79,65528,65467,65524,1,65523,65,28,65467,0,10,0,0,14,73,65515,65467,2,65517,65535,67,19,65532,0,65445,65522,0,12,85,65519,65467,6,65531,1,83,65482,65534,65533,9,65520,0,65534,79,65527,11,65534,65521,0,81,31,0,2,65467,65530,79,9,0,65532,0,6,65531,65535,78,65496,65445,65438,65501,2,76,7,73,65532,123,65458,65521,65529,0,23,65532,6,65467,65520,79,8,0,65526,65532,65458,65519,65518,83,29,10,0,65532,65453,69,9,0,65520,10,4,65530,65465,65514,23,16,65528,65532,65531,84,65467,67,65529,7,1,65534,65453,69,65482,7,65467,0,0,84,65532,84,65450,9,65523,0,2,82,11,7,65472,65445,65522,0,8,79,65533,15,4,65517,65535,192,65482,17,3,7,65522,82,65467,84,65529,15,65523,65452,65535,69,29,65467,1,65532,65529,65514,12,85,65519,65467,5,65531,65519,82,15,65467,7,4,65453,65,15,85,65532,65467,7,65530,65453,80,31,9,8,65467,65518,76,65467,74,65529,13,0,65466,65431,39,28,65532,2,14,65453,69,65467,80,65529,65534,5,65452,65533,69,19,19,7,65467,65518,0,13,69,65517,10,4,65535,65453,67,25,13,6,0,65535,65,9,65514,65519,65467,65525,65521,65535,67,11,13,65525,9,65453,65,8,65,65521,65532,6,65517,65529,76,29,65467,7,0,65520,82,0,84,65533,65493,65436,65522,2,71,19,9,8,65467,65518,76,65467,77,65515,13,65470,65452,65532,78,65482,14,135,9,65453,78,10,68,65532,4,6,65535,65453,69,65482,1,65529,15,0,12,65445,80,65519,13,65458,65523,65535,65,24,65467,6,0,65530,69,4,0,65519,9,65458,0,65522,82,28,65532,65460,0,65526,88,4,82,65515,9,65472,65430,65431,33,23,10,6,65467,65521,69,65467,86,125,14,65458,65526,65532,0,15,9,65460,14,65522,78,15,0,65527,132,5,65452,65534,85,15,65467,2,10,65453,69,9,0,65533,132,65470,65430,65521,69,65482,12,9,131,65453,76,65532,0,65530,65532,4,0,65453,80,19,15,65534,10,65535,0,8,69,65457,9,65458,65534,65532,77,11,9,65528,13,109,27,65445,69,65450,65535,65527,65452,3,211,29,65467,7,65532,65533,0,7,79,65450,12,7,65525,65453,83,15,9,7,65467,3,211,14,0,65519,14,6,108,65467,65514,65515,65467,65534,10,65520,0,65535,69,65450,65535,65523,1,0,0,32,10,7,65467,65518,67,10,77,65530,65532,4,65517,65535,201,65496,65445,65438,65508,65532,0,15,69,65527,65467,65534,65517,65453,77,25,13,8,65467,65533,69,13,0,65528,10,65458,65535,65522,82,65495,17,3,14,65453,65,65533,83,65519,9,6,65464,65431,80,15,13,5,16,117,0,65532,77,65529,13,65458,65532,65522,82,65482,8,3,13,1,0,132,83,65450,65532,0,1,65529,151,22,65532,8,65493,65431,77,65532,83,65450,5,1,65452,65531,79,65482,65534,6,0,2,0,12,85,65519,65467,65535,65531,65531,0,32,10,0,0,65535,0,14,79,65516,13,65523,0,65431,80,31,14,65527,65532,65453,69,14,83,65519,13,65458,65532,65522,82,65482,15,65525,7,65453,68,0,80,65515,13,6,65525,65530,69,24,15,65474,65445,65495,79,65467,83,125,65467,65529,65521,65529,211,29,65467,65528,0,65453,86,10,83,65534,13,65527,65452,65522,83,13,123,7,65467,3,79,7,69,65532,65479,65436,65533,2,69,65494,65467,65534,10,65453,77,10,82,65523,9,6,65464,65453,78,25,65467,1,0,1,65,65467,77,65523,65467,65527,65530,65453,79,12,7,65533,15,65467,65514,65518,79,65526,65467,65527,65535,1,0,26,0,2,14,65518,82,65467,77,65519,65467,6,65531,65529,0,14,0,0,65467,65530,211,9,0,65518,0,65534,65525,1,12,65460,65534,65525,13,65453,78,142,83,65450,17,65531,2,65526,78,30,65479,65460,9,65532,0,65534,82,65519,16,65458,65535,65522,0,26,16,7,65534,65518,0,1,69,65532,65493,65436,65517,65533,82,147,14,65460,8,65518,0,8,79,65532,15,65470,65452,65521,7,11,8,65525,13,65453,80,0,82,65518,65532,7,65452,65533,79,14,0,6,65479,65431,69,65467,83,65523,65532,65458,0,65532,83,30,65467,65529,9,65453,73,13,65,65450,65534,1,65530,3,69,28,15,65533,15,65467,65514,65504,12,65450,5,1,65452,65523,79,28,130,65525,15,65453,68,65474,65,65531,16,65527,65535,1,0,23,142,2,65467,0,69,13,0,65519,4,10,65525,1,12,65460,15,3,15,65453,76,10,0,65527,0,7,65452,65530,65,22,65467,7,0,65535,192,65467,86,125,14,65458,65530,65532,0,32,0,65529,13,65467,65514,65445,33,65527,10,4,65464,65453,68,15,65467,10,142,0,0,5,79,65450,0,0,65452,0,69,24,15,65460,8,118,83,65467,81,65535,0,65458,65530,65532,0,15,9,65460,14,118,12,65445,68,65519,65467,3,1,117,0,22,65532,65460,11,65518,82,15,0,65530,4,6,65526,65532,82,65482,8,65529,65474,65531,0,13,79,65527,65532,0,65520,65535,192,65494,65445,65529,65467,65521,69,65467,86,125,14,65458,65535,65518,80,65482,7,3,65467,65534,85,4,0,65533,0,0,65535,65453,86,157,14,65460,0,0,84,123,26,65428,65500,65458,65526,65532,67,65482,65535,65529,65467,65521,65,16,83,65450,17,1,65535,65453,65,13,10,1,11,65518,82,65532,82,115,65481,65458};

Solució de l'exercici

Ens imaginem que la paraula clau estarà formada pels 14 caràcters complementaris (a 65536) dels primers 14 del text pla, a fi que tots es xifrin igual... Això faria que la clau fos de 14 caràcters. Ho provarem. Comencem per trencar el missatge en els 14 missatges que s'han xifrat amb un Cèsar cadascun.

blocs=Transpose[Partition[TextXifrat,14]];

Siguin (Subscript[a, 1]),...,(Subscript[a, 14]) els primers caràcters del text pla; llavors, la clau de xifratge és (Subscript[x, 1]),...,(Subscript[x, 14]) de manera que (Subscript[x, i])=65536-(Subscript[a, i]).

ToCharacterCode["AZaz "]

O sigui, que, majoritàriament, els codis dels caràcters (Subscript[a, i]) pertanyen als intervals [65,90] o bé [97,122]; i potser algun altre caràcter: espai blanc=32, lletres accentuades,...

Mirem quins caràcters i amb quina freqüència apareixen en cada bloc.

fr=Table[{j,Table[{i,Count[Mod[blocs[[j]],65536],i]},{i,Union[blocs[[j]]]}]},{j,1,14}]

El caràcter més freqüent potser hauria de ser l'espai en blanc; o sigui, el de codi 32. La diferència amb el codi del caràcter més freqüent hauria de ser el codi del caràcter corresponent de la clau. Provem-ho. Comencem pel primer bloc.

Escrivim en una matriu els (codis dels) caràcters i les freqüències.

u=Transpose[fr[[1,2]]]

Mirem la freqüència del caràcter més freqüent.

m=Max[u[[2]]]

Mirem el codi del caràcter més freqüent.

c=u[[1]][[Position[u[[2]],m][[1,1]] ]]

Si suposem que el caràcter més freqüent hauria de ser l'espai en blanc, trobem quin és el codi del caràcter que correspon a la clau.

x=Mod[32-c,65536]

i el caràcter corresponent.

lletra=FromCharacterCode[x]

Intentem automatitzar el procés per a tots els blocs.

Clauestimada=Table[Module[{u,m,cx,lletra},
u=Transpose[fr[[i,2]]];
m=Max[u[[2]]];
c=u[[1]][[Position[u[[2]],m][[1,1]] ]];
x=Mod[32-c,65536];
lletra=FromCharacterCode[x]
],{i,1,14}]

Provem-ho:

Clest=65536-Flatten[ToCharacterCode[Clauestimada]]

text=VigenereDX[TextXifrat,Clest]

Sembla que hi ha un caràcter equivocat a la clau...
Potser no és "l", sinó "v":

textbo=VigenereDX[TextXifrat,65536-ToCharacterCode["Veles e vents "]]

Efectivament, el caràcter més freqüent del nové bloc no correspon al caràcter blanc, sinó a la lletra "e" minúscula. Ho comprovem a continuació, a tall d'exemple. (Tot i que sembla que no calgui, perquè ja hem esbrinat la clau.)

u=Transpose[fr[[9,2]]]

m=Max[u[[2]]]

c=u[[1]][[Position[u[[2]],m][[1,1]] ]]

Mirem el codi que correspon a la lletra "e" minúscula.

x=Mod[ToCharacterCode["e"]-c,65536]

lletra=FromCharacterCode[x]