Coduri

Aplicatii ale matricei inversabile:Codarea

Sunt multe feluri de a cripta un mesaj, iar utilizarea codurilor a devenit din ce in ce mai importanta in ultimii ani.
În primele zile ale televiziunii prin satelit, semnalele video nu erau criptate și oricine avea o antenă parabolică de satelit putea să vadă transmisia. Ei bine, acest lucru nu a funcționat, deoarece toate rețelele care utilizează sateliți nu au dorit ca proprietarii antenei satelit să poată primi feed-ul prin satelit fără costuri, în timp ce abonații prin cablu trebuiau să plătească pentru canal, căci astfel pierdeau bani. Deci, au început să cripteze semnalul video cu un sistem numit Videocipher (înlocuit ulterior de Videocipher II).

Ceea ce a făcut sistemul de criptare Videocipher a fost să transforme semnalul în formă digitală, să-l cripteze și să trimită datele prin satelit. Dacă proprietarul antenei de satelit a avut o casetă Videocipher și a plătit pentru canal, atunci caseta ar decripta semnalul și returna în forma originală și utilă.

Acest lucru a fost făcut folosind o cheie inversibilă. A fost foarte important ca acestă cheie să fie inversibilă pentru că altfel nu ar fi posibilă returnarea datelor criptate în forma lor originală.

Un mod de a cripta un mesaj este folosirea unei matrice si a inversei acesteia.
Intradevar, consideram o matrice inversabila fixa A. Convertim mesajul intr-o matrice B pentru care e posibil sa facem AB.
Un mesaj este convertit în formă numerică conform unei scheme. Schema cea mai simplă este

A B C D E F G H I K L L M
0 1 2 3 4 5 6 7 8 9 10 11 12 13
N O P Q R S T U V W X Y Z ,
14 15 16 17 18 19 20 21 22 23 24 25 26 27

Aceste date vor fi plasate în formă de matrice. Dimensiunea matricei depinde de dimensiunea cheii de criptare.
Trimitem mesajul generat de AB. Trebuie sa se cunoască A-1 pentru a decripta sau decoda mesajul trimis. Si vom avea:

A-1(AB)=B

care este mesajul original. Retine doar campurile din A, deoarece trebuie sa fi capabil sa le schimbi. Deci ar trebui sa avem un mod simplu de a genera matrice simple A, care sunt inversabile si au inversa tot o matrice simpla. Retine ca in general inversa unei matrice implica fractii care nu sunt usor de trimis in forma electronica. Cel mai bun mod ar fi sa avem si matricea A si inversa acesteia cu elemente integi. De fapt putem utiliza cunostintele precedente pentru a genera aceasta clasa de matrice. Intradevar, daca A este o matrice cu determinantul egal cu ±1 si toate elementele acesteia sunt intregi, atunci si A-1 are elementele numere intregi. Cum vom genera aceasta clasa de matrice?
Un mod practic este de a incepe o matrice triunghiulara cu ±1 pe diagonala. Apoi vom utiliza operatii elementare consecutive pentru a schimba matricea iar determinantul acesteia va ramane neschimbat .

Exemplu:

Consideram matricea

(1)
\begin{pmatrix} -1&5&-1\\ 0&1&8\\ 0&0&1\\ \end{pmatrix}

Pentru inceput vom păstra prima linie neschimbată, iar la linia a doua și la cea de a 3-a vom aduna linia 1. Vom obtine:

(2)
\begin{pmatrix} -1&5&-1\\ -1&6&7\\ -1&5&0\\ \end{pmatrix}

In continuare vom pastra prima linie neschimbată din nou, vom aduna linia a 3-a la cea de-a doua, iar în final adaugand prima linie multiplicată cu -2 la ultima. Vom obtine:

(3)
\begin{pmatrix} -1&5&-1\\ -2&11&7\\ 1&-5&2\\ \end{pmatrix}

Aceasta e matricea noastra A. Prin calcule simple vom obtine det (A)=-1, rezultat pe care il stiam dinaintea executarii operatilor elementare. (Prin transformări elementare determinantul din matricea triunghiulara originala rămâne neschimbat.) Vom lasa detalile calculelor cititorului. Inversa lui A este:

(4)
\begin{align} A^{-1}=\frac{1}{-1} \begin{pmatrix} 57&-5&46\\ 11&-1&9\\ -1&0&-1\\ \end{pmatrix}= \begin{pmatrix} -57&5&-46\\ -11&1&-9\\ 1&0&1\\ \end{pmatrix} \end{align}

Să presupunem că matricea noastră de criptare (matricea de codare) este o astfel de matrice de tipul 3x3. Dacă avem un mesaj format din 10 caractere, acestea se pot plasa într-o matrice 4x3 și să umplem ultimele locuri cu spații pentru a face matricea completă.

Mesajul nostru:

(5)
\begin{pmatrix} -58&311&134\\ 6&-25&70\\ \end{pmatrix}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License