TEMES

Model matricial en criptografia

Models matemàtics d’àlgebra lineal: aprenent de "hacker" I

La modelització ens obre un ventall de possibilitats per a l’aprenentatge i la divulgació de l’àlgebra lineal.

En aquest article vull mostrar la importància de l’àlgebra lineal per ser un bon hacker. En concret, us explicaré com es poden presentar missatges per xifrar i desxifrar usant com a model el producte de matrius, és a dir, com el producte de matrius i les matrius inverses són models de la criptografia.

Començarem parlant del model matricial per encriptar missatges numèrics.

Suposem que disposem d’una matriu A, que més endavant justificarem que necessàriament cal que sigui quadrada i amb determinant diferent de zero (invertible), i d’un vector v.

La transformació A · v  ens proporciona un nou vector b. Si tenim diversos valors numèrics  v1..., vk, també podem considerar la matriu V formada pels valors  escrits en columna i la transformació A·V ens proporcionarà una nova matriu.

Aquestes transformacions (formalment aplicacions lineals) converteixen un vector en un altre, de manera que per recuperar “l’original” només cal aplicar la matriu inversa a la imatge.

Així, donat A i v, podem construir  A · v = b, si coneixem b, i es pot recuperar v fent A-1  bv. Amb això també queda justificat el fet que la matriu cal que sigui invertible.

Sense adonar-nos-en, ens trobem davant d’un model matemàtic de criptografia, sempre que els missatges es puguin associar a un vector numèric.

En l’expressió A · v = b, A seria la clau; v, el missatge original, i b, el missatge v codificat. Si tenim els missatges escrits de manera que es puguin quantificar en forma de matriu, si anomenem A la matriu per codificar, B la dels missatges i C la que rep el receptor, tindrem com a model A · B = C.

En síntesi, l’emissor envia un missatge B i el receptor rep un missatge C. La clau (coneguda per l’emissor i pel receptor) és la matriu A. Al hacker per descodificar li cal saber àlgebra lineal, ja que per descodificar només cal resoldre B=A-1C.

Vegem un exemple.

Suposem un missatge que està identificat pel vector v = (1, -3, 4). Escollim com a clau la matriu , aleshores =b

Si tenim b, podem recuperar v fent  v = .

Si enviem un altre missatge w = (2,-1,3), de manera anàloga tindríem que el receptor rebrà .

En resum:

El missatge   es transforma en el missatge . Al receptor, que coneix la clau, només li caldrà multiplicar per la matriu inversa d’A, A-1.

La matriu A-1, fent càlculs, és · ; aleshores es pot comprovar que, efectivament, ·.

De fet, d’aquests missatges que presentem en format “numèric” també n'hi ha que es poden representar en format “text”, però això últim en el pròxim article.

NOTA:

Recomano al lector no familiaritzat amb els conceptes exposats, de llegir també els articles d’aquest blog: relacionats amb la criptografia i amb l’encriptació.

Contacta amb Divulcat