Criptografia bàsica (1)
Artur Travesa
(versió 2021-04)

Introducció general

L'origen d'aquestes notes es remunta a diferents cursos d'Aritmètica o de Criptografia, a càrrec de l'autor, per a estudiants de Matemàtiques o d'Informàtica de la Universitat de Barcelona.

La idea bàsica és descriure algunes aplicacions importants de l'Aritmètica bàsica (diguem, de nivell de primer curs) a les transmissions xifrades d'informació.

En cap cas es tracta d'un curs de Criptografia, que caldria encabir en espais més amplis de coneixements, que haurien d'incloure, probablement, parts de teoria de la comunicació, de complexitat algorítmica o computacional, d'aprenentatge automàtic, o d'estudi de teories de compartició de secrets, entre d'altres.

El format triat per a la presentació és el d'un notebook de Mathematica, per la facilitat que té aquest programari per a poder desenvolupar els càlculs no trivials de manera prou senzilla i entenedora, d'una banda, i per a permetre fer una presentació escrita prou raonable des del punt de vista de material escrit, de l'altra. En particular, la possibilitat d'incloure els càlculs dins del text de manera natural en fan una bona eina comunicativa i, alhora, facilita molt el càlcul amb exemples no trivials.

A fi de veure tot el contingut del notebook convé executar-lo. Això es pot fer de cop o bé, més recomanable, cel·la a cel·la a mesura que s'avança en la lectura i comprensió dels diferents continguts. 
Observació: Per al cas en què no es disposi del programari, hi ha la versió executada del notebook en format pdf.

Amb la finalitat doble d'una banda, de no fer textos molt llargs o amb molts continguts, i de l'altra de poder ampliar de manera senzilla els continguts que s'hi tractin, el material s'ha dividit en diferents notebooks, que desrivim a continuació, en l'apartat de referències.

Referències

[Cripto-1]: Criptografia bàsica (1).
Travesa, A.: CriptografiaBasica-1; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una iniciació a la codificació de missatges. El criptosistema de Cèsar. El criptosistema de Vigenère.

[Cripto-2]: Criptografia bàsica (2). 
Travesa, A.:CriptografiaBasica-2; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Els criptosistemes lineals. Els criptosistemes afins. Sufixació de missatges. Farciment de missatges.

[Eratostenes]: Un garbell d'Eratòstenes.
Travesa, A.: Eratostenes; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Un garbell d'Eratòstenes.

[Cripto-3]: Primeritat. Construcció de primers. 
Travesa, A.:ConstruccioDePrimers; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Test de primeritat de Solovay-Strassen. Test de primeritat de Miller-Rabin. Un  certificat congruencial de primeritat. Construcció certificada de nombres primers de mida prefixada. Aplicació al càlcul de claus RSA. Aplicació (exercici) al càlcul de claus ElGamal.

[Cripto-4]: Factorització. 
Travesa, A.: Factoritzacio; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Un garbell d'Eratòstenes. Tests de primeritat de Solovay-Strassen i de Miller-Rabin. Un certificat congruencial de primeritat. Un algoritme bàsic de divisó per nombres primers petits. Un algoritme bàsic de divisó per nombres petits. El mètode de factorització de Fermat. El mètode de factorització p-1 de Pollard. El mètode de factorització rho de Pollard.

[RSA]: Criptosistemes de tipus RSA. 
Travesa, RSA; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una descripció bàsica dels criptosistemes de tipus RSA: les claus; xifratge; desxifratge; observacions sobre la seguretat.

[ElGamal]: El criptosistema ElGamal. 
Travesa, A.: ElGamal; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Logaritmes discrets. Una descripció bàsica del criptosistema ElGamal: el grup cíclic; les claus; xifratge i desxifratge.

[Tr-1]: Travesa, A.: Aritmetica. Edicions de la Universitat de Barelona, col·lecció UB, n. 25. Barcelona, 1998. ISBN:84-8338-031-5.

1. Introducció

Entendrem per criptografia la disciplina que estudia l'intercanvi d'informació de manera que només l'entitat emissora i la destinatària (que no cal confondre amb la receptora) puguin conèixer aquesta informació.

Així, doncs, en aquest estudi caldrà tenir en compte alguns actors importants. D'una banda, l'emissor del missatge; d'altra banda, el destinatari del missatge; i en tercer lloc, i molt important, els possibles receptors o interceptors del missatge. I encara cal tenir en compte altres possibles actors, sovint atacants actius, que intentin fer-se passar per l'emissor o pel destinatari del missatge a fi d'obtenir la informació confidencial.

Difícilment es podria estudiar criptografia científicament si no poguéssim manipular els missatges d'una manera coherent, mesurar el grau de dificultat dels processos de xifratge i de desxifratge dels missatges, o disposar d'eines per a construir (o destruir) criptosistemes cada cop més robustos.

A fi de mostrar la potència de les matemàtiques i, en particular, de l'Aritmètica, en aquestes qüestions, començarem amb un estudi elemental dels criptosistemes clàssics, i veurem que podem permetre'ns assegurar que la majoria d'aquests criptosistemes clàssics són realment molt febles. De fet, això fa que cap d'ells no sigui emprat en l'actualitat.

Més endavant veurem altres criptosistemes que encara es fan servir de manera habitual en el moment d'escriure aquest tutorial, però que segurament deixaran de ser-ho en un futur més o menys proper, probablement substituïts per criptosistemes quàntics. Però no ens avancem en el temps, ni en aconteixements (futurs?).

2. Codificació de missatges

Introducció

Un dels fets bàsics que cal tenir presents en criptografia és la codificació dels missatges; i això pot dependre molt del tipus de missatges que cal transmetre. Per exemple, potser cal transmetre dades bancàries per a una transacció comercial (NIF, números de comptes corrents, números de targetes de crèdit, quantitats que cal transferir entre comptes diferents, etcètera), o bé cal transmetre informacions confidencials alfanumèriques en general (informes de seguiment de projectes, cartes de recomanació, sol·licituds de beques), o bé cal transmetre claus privades per a l'ús de certes funcions criptogràfiques (per exemple, en les comunicacions xifrades entre diferents ordinadors), etcètera.

En les comunicacions entre ordinadors, les dades que cal transmetre són, sovint, arxius (de text, o executables, o del tipus que sigui). Per tant, volem suposar, i ho fem, que les dades que cal transmetre són successions de zeros i uns.

A fi de poder simular còmodament aquest fet, en aquest tutorial usarem les funcions incorporades FromCharacterCode i ToCharacterCode. Cal notar que Mathematica usa codis numèrics entre els valors 0 i 216-1=65535 (setze bits), però no els fa servir tots.

Exercici 1.1

(a) Què fan les funcions FromCharacterCode i ToCharacterCode? Quina és la seva sintaxi? Quins són els caràcters de codis entre 32 i 126?
(b) Quins codis numèrics tenen (en Mathematica) les vocals accentuades?
(c) Es demana descodificar la llista següent de caràcters: {69, 102, 101, 99, 116, 105, 118, 97, 109, 101, 110, 116, 44, 32, 110, 111, 109, 233, 115, 32, 99, 97, 108, 105, 97, 32, 97, 112, 108, 105, 99, 97, 114, 45, 108, 105, 32, 108, 97, 32, 102, 117, 110, 99, 105, 243, 32, 70, 114, 111, 109, 67, 104, 97, 114, 97, 99, 116, 101, 114, 67, 111, 100, 101, 46}.
(d) ¿Quina diferència hi ha entre el missatge anterior i el missatge {69, 102, 101, 99, 116, 105, 118, 97, 109, 101, 110, 116, 44, 32, 110, 111, 109, 233, 115, 32, 99, 97, 108, 105, 97, 32, 63425, 63433, 63432, 10, 83, 116, 121, 108, 101, 66, 111, 120, 91, 34, 97, 112, 108, 105, 99, 97, 114, 34, 44, 10, 70, 111, 110, 116, 83, 108, 97, 110, 116, 45, 62, 34, 73, 116, 97, 108, 105, 99, 34, 93, 63424, 63425, 63433, 63432, 10, 83, 116, 121, 108, 101, 66, 111, 120, 91, 34, 45, 34, 44, 10, 70, 111, 110, 116, 83, 108, 97, 110, 116, 45, 62, 34, 73, 116, 97, 108, 105, 99, 34, 93, 63424, 63425, 63433, 63432, 10, 83, 116, 121, 108, 101, 66, 111, 120, 91, 34, 108, 105, 34, 44, 10, 70, 111, 110, 116, 83, 108, 97, 110, 116, 45, 62, 34, 73, 116, 97, 108, 105, 99, 34, 93, 63424, 32, 108, 97, 32, 102, 117, 110, 99, 105, 243, 32, 70, 114, 111, 109, 67, 104, 97, 114, 97, 99, 116, 101, 114, 67, 111, 100, 101, 46}?
(e) Es demana descodificar el missatge següent: {76, 97, 32, 100, 105, 102, 101, 114, 232, 110, 99, 105, 97, 32, 233, 115, 32, 108, 97, 32, 112, 114, 101, 115, 232, 110, 99, 105, 97, 44, 32, 101, 110, 32, 101, 108, 32, 115, 101, 103, 111, 110, 32, 109, 105, 115, 115, 97, 116, 103, 101, 44, 32, 100, 101, 32, 108, 108, 101, 116, 114, 101, 115, 32, 99, 117, 114, 115, 105, 118, 101, 115, 46}.

(a) (Una solució)

?FromCharacterCode

?ToCharacterCode

FromCharacterCode[Table[n,{n,32,126}]]

Resposta: Són els caràcters ASCII imprimibles.

(b) (Una solució)

ToCharacterCode["ÀÁÄÈÉËÌÍÏÒÓÖÙÚÜàáäèéëìíïòóöùúü"]

Comprovem-ho (i una miqueta més).

FromCharacterCode[Table[n,{n,192,255}]]

(c) (Una solució)

FromCharacterCode[{69,102,101,99,116,105,118,97,109,101,110,116,44,32,110,111,109,233,115,32,99,97,108,105,97,32,97,112,108,105,99,97,114,45,108,105,32,108,97,32,102,117,110,99,105,243,32,70,114,111,109,67,104,97,114,97,99,116,101,114,67,111,100,101,46}]

(d) (Una solució)

FromCharacterCode[{69,102,101,99,116,105,118,97,109,101,110,116,44,32,110,111,109,233,115,32,99,97,108,105,97,32,63425,63433,63432,10,83,116,121,108,101,66,111,120,91,34,97,112,108,105,99,97,114,34,44,10,70,111,110,116,83,108,97,110,116,45,62,34,73,116,97,108,105,99,34,93,63424,63425,63433,63432,10,83,116,121,108,101,66,111,120,91,34,45,34,44,10,70,111,110,116,83,108,97,110,116,45,62,34,73,116,97,108,105,99,34,93,63424,63425,63433,63432,10,83,116,121,108,101,66,111,120,91,34,108,105,34,44,10,70,111,110,116,83,108,97,110,116,45,62,34,73,116,97,108,105,99,34,93,63424,32,108,97,32,102,117,110,99,105,243,32,70,114,111,109,67,104,97,114,97,99,116,101,114,67,111,100,101,46}]

(e) (Una solució)

FromCharacterCode[{76,97,32,100,105,102,101,114,232,110,99,105,97,32,233,115,32,108,97,32,112,114,101,115,232,110,99,105,97,44,32,101,110,32,101,108,32,115,101,103,111,110,32,109,105,115,115,97,116,103,101,44,32,100,101,32,108,108,101,116,114,101,115,32,99,117,114,115,105,118,101,115,46}]

Exercici 1.2

(Aquest exercici no és estrictament necessari per a seguir el tutorial; és, doncs, opcional. La temàtica és, sobretot, per a nivell informatiu o per a usos més reals.)
A fi de simular millor un fitxer de dades, convé convertir els codis numèrics a successions de zeros i uns. I si tenim en compte que 65536=2^16, podem usar 16 bits per a escriure cadascun dels caràcters numèrics. Notem que això pot dependre del tipus de dades; per exemple, codificacions com utf-7 o utf-8 fan servir 6 o 8 o 16 o 32 o 64 bits.
(a) Es demana escriure una funció Codifica que, aplicada a un missatge alfanumèric, proporcioni, en una sola llista numèrica (i no en una llista de llistes), la seva codificació utilitzant setze caràcters (zeros i uns) per a cadascun dels codis numèrics que assigna Mathematica. Es demana també un exemple de codificació d'una frase curta.
(b) Es demana escriure una funció Descodifica inversa de l'anterior; cal que aquesta funció faci el control de si la quantitat de caràcters total és múltiple de setze; en cas que no ho sigui, cal afegir (Prepend) zeros al començament. Es demana descodificar la frase codificada anteriorment i comprovar que la funció definida va bé encara que s'eliminin zeros a l'esquerra.

(a) (Una solució)

Donem una funció que s'apica a una successió de caràcters (String).

Codifica[m_String]:=Module[{lta=ToCharacterCode[m]},
Flatten[Table[IntegerDigits[lta[[i]],2,16],{i,1,Length[lta]}]]
]

m="Una prova de codificació de missatges.";

c=Codifica[m]

(b) (Una solució)

Donem una funció que s'apica a una llista de nombres, que han de ser zeros o uns.

Descodifica[lta_List]:=Module[{x},
x=Partition[Flatten[Prepend[lta,Table[0,{i,1,Mod[-Length[lta],16]}]]],16];
FromCharacterCode[Table[FromDigits[x[[i]],2],{i,1,Length[x]}]]
]

Descodifica[c]

Cal comprovar que, efectivament, descodifica bé.

Descodifica[c]==m

3. El criptosistema de Cèsar

Exercici 1.3

Se suposa que els missatges estan escrits en algun alfabet (això és, un conjunt finit i no buit de símbols). Per exemple, podem pensar en l'alfabet (grec), o l'abecedari (llatí), o en altres alfabets. Per exemple, durant molts anys, es consideraven ch, ll i ñ com a caràcters de l'abecedari castellà; això feia un abecedari de 29 lletres. 
Però podem pensar en altres llengües o alfabets: ciríl·lic, europeus orientals, escandinaus, hebreu, àrabs, xinesos, coreà, japonès, tais, bràmics, altres alfabets orientals, i molts altres africans, amerindis, malaisians, etcètera, dels quals ni en conec l'existència. 
I, si es vol, encara caldria pensar en tots els caràcters accentuats o modificats d'alguna manera. Sense anar més lluny, com es consideren ç o ny en català? Com un caràcter senzill o com un caràcter modificat (equivalent a accentuat) l'un? I com un caràcter o com un dígraf, l'altre? El diccionari de l'IEC considera ç com una c amb un accent i ny com un dígraf (almenys, en algunes paraules que jo he consultat).

D'altra banda, els alfabets s'aprenen sovint en un cert ordre; és a dir, se suposa que els caràcters de l'alfabet en qüestió estan ordenats d'una certa manera estàndard; per exemple, l'ordre alfabètic, si es tracta de l'alfabet (grec) o l'abecedari (llatí), o altres ordres depenent de l'alfabet que es faci servir. Per exemple, quan es consideren ch, ll i ñ com a caràcters de l'abecedari castellà, es col·loquen entre la c i la d, la ch, entre la l i la m, la ll, i entre la n i la o, la ñ; això determina un ordre en l'abecedari castellà de 29 lletres.

Però no tothom coneix l'ordre dels caràcters ni el considera de la mateixa manera. Segons quina aplicació o quin programa d'ordinador es fa servir, ens podem trobar que la ch es pensa com dues lletres (i, per tant, se situa entre cg i ci), o bé com una de sola (i se situa entre cz i d). I anàlogament amb les ll i ñ, o les lletres accentuades (i en quin ordre van els accents?).
Caldrà tenir això present. Per tant, suposarem que treballem amb un alfabet i amb un ordre determinat en aquest alfabet. En aquest tutorial, l'alfabet és el conjunt dels 65536(=2^16) caràcters (possibles) que fa servir Mathematica, i l'ordre, el natural: 1<2<3<...<65536.

El criptosistema de Cèsar consisteix a fer córrer cíclicament els caràcters d'un missatge una quantitat fixa de caràcters; aquesta quantitat és la clau secreta. Per exemple, es pot usar la funció següent, que s'aplica a un missatge pla sense codificar i proporciona un missatge xifrat, també sense codificar. (Això de sense codificar és una mala praxi, perquè podem intentar usar codis que corresponen a caràcters no imprimibles... però ja hi tornarem, a aquest punt.)
Òbviament, doncs, la clau secreta és un nombre enter entre 0 i 65535; de fet, i per la propietat de ciclicitat que hem anomenat més amunt, la clau és un nombre enter qualsevol, del qual només compta la seva classe residual mòdul 65536.

Cesar[missatge_String,clau_Integer]:=Module[{b=2^16,lta=ToCharacterCode[missatge]},
FromCharacterCode[Table[Mod[lta[[i]]+clau,b],{i,1,Length[lta]}]]
]

Per exemple, podem xifrar amb la clau que sovint s'atribueix a l'emperador romà Juli Cèsar (clau=3) el missatge "VENIVIDIVINCI", que també se li atribueix a ell. D'aquí el nom del criptosistema.

Cesar["VENIVIDIVINCI",3]

Qui no ha jugat a intentar desxifrar missatges xifrats amb el criptosistema de Cèsar i l'alfabet llatí de 26 lletres? Sembla extraordinàriament "senzill"; de fet, només hi ha 26 claus possibles, de manera que s'acaba aviat. O no? Algú ha intentat esbrinar perquè l'ordinador de 2001: A space Oddysey, d'Arthur C. Clarke, es diu HAL i és de la sèrie 9000?

Hom pot pensar que serà molt difícil desxifrar un missatge xifrat amb el criptosistema de Cèsar i una clau desconeguda, ja que aquesta s'ha pogut triar entre les 65536 possibles. Caldrà provar les 65536 claus?

(a) Es demana intentar desxifrar el text següent, que ha estat xifrat amb la funció Cesar anterior i una clau menor que 65536.

x="寶尅尉尅尕寀尃小對寀導小寀岉尓寀尔封導寀射尉将岍尃尉尌察"

(a) (Una solució)

Comencem per conèixer els caràcters numèrics (que, de fet, és allò que compta) asssociats al missatge xifrat.

lta=ToCharacterCode[x]

Ara, mirem com són els caràcters numèrics associats a un text de prova.

ToCharacterCode["A veure què succeeix."]

Notem que el menor caràcter és el 32, i correspon a l'espai en blanc.

Si el missatge xifrat és un text (com diu l'enunciat), deu tenir espais en blanc i, per tant, el menor dels codis hauria de correspondre a l'espai blanc. Això hauria de fer senzill proporcionar-nos la clau.

{Max[lta],Min[lta]}-32

La clau podria ser 23456.

y=Cesar[x,-23456]

Observació

Cal notar que els missatges poden ser molt més complicats que simples textos; però els codis associats als caràcters que els componguin difícilment pertanyeran a intervals molt grans, de manera que es poden provar claus en intervals petits (i per a parts petites dels missatges). Deixo oberta una reflexió més profunda sobre tot això.

4. El criptosistema de Vigenère

Exercici 1.4

El criptosistema de Vigenère és una generalització i una millora del criptosistema de Cèsar. Per a xifrar un missatge amb aquest criptosistema cal, en primer lloc, triar una paraula clau (això és, una successió de caràcters de l'alfabet, que no cal que tingui cap sentit). Sigui k la longitud d'aquesta paraula clau. A continuació, es prenen de k en k els caràcters del missatge pla, de manera que aquest resta dividit en blocs de k caràcters excepte, potser, el darrer bloc, que només conté la quantitat de caràcters que resten de la divisió de la longitud total del missatge entre k. Seguidament, es consideren els k missatges formats pels primers, els segons, ..., els k-èsims caràcters del missatge original. A continuació, s'aplica a cadascun dels i=1, 2, ..., k missatges nous la transformació de Cèsar que correspon a la clau Cèsar donada pel caràcter i-èsim de la clau Vigenère. I, finalment, es construeix el missatge xifrat en intercalar els caràcters així obtinguts: primerament, el primer de cadascun dels k missatges xifrats; després, els segons; després, els tercers; etcètera.

(a) Es demana escriure una funció VigenereX per a xifrar amb el criptosistema de Vigenère.
(b) Es demana escriure la funció inversa, VigenereDX, per a desxifrar amb el criptosistema de Vigenère anterior.
(c) Es demana intentar desxifrar el missatge xifrat següent, xifrat amb una paraula clau de longitud 25. Quina és aquesta paraula clau?
Observació. Cal que no s'intenti usar la força bruta. Cal notar que paraules de 25 caràcters entre els 65536 possibles n'hi ha (65536^25); aproximadament, 2.5822498780869086`*^120. I si poguéssim provar (10^12) claus per segon, necessitaríem aproximadament 8.18×(10^100) anys per a provar-les totes (l'edat estimada de l'univers és "només" de 1.37×(10^10) anys).

xifrat="ÞÓæØãÝâçÎàÕÑÆ@ºÎ»×ŏ×ÓīäÎŝâÞáÕÚÊÐÔ·ËÊÚĈÕ×¬âÝßçØæÝØáÆÅ¨ĈÉÊÙĸ××cÓèÝÕåÊåÚÛÍØ·ÝÎÊŉßÇcÓÚåÙâçÖæÎÝÕ×ÎÊÎÔÆŋÓÑoÎÞßåÒàÙ×ÍÓÈLvÝÙÎÏŚÚ±ÓàÕáÔÞßÕÐÍÙ@©ÒÎÚ×ĈÝ¯ÓÜãÝÚÒçéÉÅGÅÖ»ÜÛÆŘÓ×¤çÕÑÒßÊè¢®ÓÓ¿×ÜÆÑőťc×ÜäáØ×ØâÑÆ@ÏÄÒÓŔå¦ÓÛŐ×ãØÛæÉÒÍ@ÑÎÉÊÛÌÓĈâÑ¤ÔÙàÊáÙ×ÎÙÊ@·ÚÜÊáŜ×¨åÝÑÓÜßÜØÎáÒÂØÊØŌ×®ÌÑæŏÖÝØæØÆÇÊÊÎÞŗæØ¨äÙÛÍÔæ×ÒÓ@ÆÑ¹ÖãōÓ²ßŒãÒâ×çŝÙÂ@ÕÚÄÝÐÙÏŜÉ¨ÌÑæŏÖÝØæØÒÉ»ÜÛÊÜĈÖÊcÞÊØØéÒæÝŘÅÑvÕÖÓÕőæÚ§ÝßèÐß×ÙÑÎ×ØÊÐÌÓŖæ×¨ÔÂØÐèÝÉÎÎÒÙLvÎÚÑŗàØ¬ÖÎâÙÝÎßçØÍØ·ÝÎÊáĈØÔµßÊäçãÎßçÝÓÑÊÉÊÚśØ¨ÙØÞç¡¢Æ×őÚÎÛśÈ¤äŉÓèÔåÜØÊÙÍØ·ÝÎÊŗäÎªÛ×Ñàª×ÔÛÕÒÚ¹ÒŚśÆ³ÞÒÓÕÔÖÕÉÎÔÙÓ@ºÎÓØő¯o¡ÐÎ×ØÊÐÌØŖáÚ¶ÕÑãåÊáçËÜÓÅÈŉËÊīŚØ¤äáéÔÌâæ×ÒÔÓÓ@·ÓÆŋÞÆ¸¬ŘçÐå×ãÓÎÅÕÂÊÆàǈÕÙ¨äÙ¡ŗæÒàÉÒÅÂÊÜÄőÙÊ±ŚÛÕ¢¼ÚÎÛÂÑÊÊÊáĈÕÔ±åÝâéÔÜáÙÑÎ×ØÊÐÌæőØ×¤æÕâÜ×çÙ×ÐÂÅ×@»ÕÚÑŉäŅ¦æÎâçÔÒëšÜÃÍÓËÝÚŘäÎ°×ÛÑáÔáÝÊÙÖÎ»ÛÉÓĈÕÆ§ÓÜÓéÝÍØàØÌ@ÑÎÉÊÛÌÓśÝ¬ØÛÑèâ®×ÙØÝÓĉ×@»ÕÚáōÙÔ±å¤ØÔæÙåŝØÐØ@ÊÎÙÈÓŚå c×ÝÓŜãØÛÔ¢";

(a) (Una solució)

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) (Una solució)

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]}]]
]

(c) (Una solució)

Comencem per convertir el missatge xifrat en una llista de codis numèrics.

lta=ToCharacterCode[xifrat]

Ara, com que sabem la longitud de la clau, 25, podem considerar els 25 missatges xifrats amb criptosistemes de Cèsar (llevat del tros final).

blocs=Transpose[Partition[lta,25]]

Mirem quins són els codis que corresponen als caràcters alfabètics generals (sense accents).

ToCharacterCode["AZaz"]

Ens imaginem que la paraula clau estarà formada majoritàriament per alguns d'aquests caràcters.

{Max[blocs[[1]]],Min[blocs[[1]]]}

Sembla que el primer caràcter de la paraula clau és una lletra majúscula. A més, deu ser un caràcter imprimible, de manera que el seu codi és més gran que 32; això deixa poques possibilitats:

{Max[blocs[[1]]],Min[blocs[[1]]]}-32

Les provem totes:

Table[{n,FromCharacterCode[blocs[[1]]-n]},{n,65,67}] //MatrixForm

La més versemblant és la tercera; correspon al caràcter "C". (A més a més, correspon al fet que el caràcter més usual en el missatge pla sigui l'espai blanc).

FromCharacterCode[67]

Repetim amb els altres blocs. Sembla que la majoria dels caràcters corresponents de la paraula clau siguin lletres minúscules.

Table[FromCharacterCode[Min[blocs[[i]]]-32],{i,2,25}]

clau=FromCharacterCode[Table[Min[blocs[[i]]]-32,{i,1,25}]]

La paraula clau seria la paraula "Criptosistema de Vigenère".
I el missatge pla el següent:

VigenereDX[xifrat,clau]

5. Exercici

Exercici 1.5

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};