tema1_mn_2015 (1)

METODE NUMERICE: Tema #1

Criptografie s, i matriceTermen de predare: 5 aprilie 2015

Titulari curs: Florin Pop, George Popescu

Responsabil Laborator: David Iancu, Bogdan Marchis, , Alexandru T, ifrea

Obiectivele Temei

In urma parcurgerii acestei teme studentul va fi capabil sa:

calculeze inverse de matrice folosind GNU Octave s, i sa eficientizeze calculul acestora identifice forme de matrice care satisfac anumite proprietat, i necesare pentru rezolvarea unei probleme.

Task1 - Criptografie (45p)

A. Dorel e pasionat de criptografie s, i e mereu dornic sa descopere metode noi de codificare pe care le testeazaapoi cu prietenii sai. Recent, a propus urmatorul algoritm:i) Textul n clar (i.e. textul care urmeaza sa fie codificat) va fi convertit ntr-un s, ir de numere prin asignareaunui numar fiecarui simbol din alfabet (ex. a-1, b-2, c-3 etc.). Dorel va codifica fiecare litera folosindpozit, ia ei n alfabetul latin, pornind de la 1. 0 va codifica un spat, iu liber. 27 va fi codul lui . s, i 28 va ficodul lui . Textul nu va cont, ine decat litere, spat, ii, simbolul punct (.) s, i simbolul apostrof (). Literele marisau mici se vor codifica la fel (ex. A s, i a vor fi ambele 1).ii) Se alege o matrice patratica n n care va fi cunoscuta doar de catre cel care trimite mesajul s, i cel caruiai este destinat.iii) Se mparte s, irul de numere obt, inut la i) n blocuri, care sunt apoi nmult, ite succesiv cu matricea decodificare. Daca lungimea s, irului de numere nu este divizibila cu n, atunci se completeaza cu spat, ii libere(respectiv, cu zerouri).iv) S, irul de numere obt, inut va fi convertit la un s, ir de simboluri din alfabet (i.e litere, spat, iu, punct sau apos-trof). De exemplu, 0 devine spat, iu, 1 devine a s, .a.m.d. S, irul obt, inut va cont, ine doar litere mici (lowercase).

Cerint, a:Va trebui sa scriet, i un program n Octave care sa implementeze algoritmul lui Dorel. Programul va citi textuldin fis, ierul input1A (care cont, ine pe prima linie textul care trebuie criptat) s, i va citi matricea de codificaredin fis, ierul key1A (care cont, ine pe prima linie valoarea lui n s, i pe urmatoarele n linii, matricea de codificare).Textul codificat va fi scris n fis, ierul output1A.

Input: Funct, ia voastra nu va primi niciun parametru.

Output: Funct, ia voastra se va numi matrixCipher s, i va tipari n output1A un string care reprezinta mesajulcriptat.

1

METODE NUMERICE Tema #1 Criptografie s, i matrice

Exemplu:key1A:36 24 113 16 1020 17 15input1A:cat (fara ghilimele)

output:dw (fara ghilimele)

Restrict, ii s, i precizari:

n este dimensiunea unei matrice 0 < n 1000 Pentru codificare folosit, i urmatoarea convent, ie: are codul 0, ., are codul 27, are codul 28 s, i toate

cele 26 de litere au codul egal cu numarul de ordine al literei n alfabetul latin (de exemplu, a arecodul 1, b are codul 2 s, .a.m.d.)

B. Dorel obis,nuies,te sa-i trimita mesaje colegei sale, Maricica. Pentru nceput, el i spune Maricicai cematrice foloses,te pentru codificare. Ea poate sa decripteze mesajele pe care le primes,te astfel:i) calculeaza inversa modulo m a matricei de codificare (unde m e numarul de simboluri din alfabet - n cazulnostru m = 29). Inversa modulo m B a unei matrice A, este acea matrice care satisface: AB I(mod m).A nu se confunda inversa modulo m a unei matrice cu inversa clasica a matricei, pe care se aplica apoioperat, ia modulo.ii) se aplica asupra textului criptat algoritmul de la A, folosind n locul matricei de codificare, inversa modulom a acesteia.

Cerint, a:Vet, i primi n fis, ierul input1B mesajul codificat primit de Maricica de la Dorel. In fis, ierul key1B vet, i avea peprima linie dimensiunea matricei de codificare cu care a fost criptat mesajul n s, i pe urmatoarele n linii va fidata matricea de codificare folosita de Dorel pentru a cripta mesajul. Va trebui sa implementat, i n Octavealgoritmul prin care Maricica poate decodifica mesajul. In fis, ierul output1B va trebui sa fie textul decodificat.Se garanteaza faptul ca decodificarea textului este posibila (pentru ca decodificarea sa fie posibila, trebuieca determinantul matricei de codificare s, i numarul de simboluri din alfabet sa fie doua numere prime ntre ele).

Input: Funct, ia voastra nu va primi niciun parametru.

Output: Funct, ia voastra se va numi decrypt s, i va tipari n output1B un string care reprezinta mesajuldecodificat.

Exemplu:key1A:36 24 113 16 1020 17 15input1A:dw (fara ghilimele)

output:cat (fara ghilimele)

Facultatea de Automatica si Calculatoare, UPB Pagina 2 din 5



n este dimensiunea unei matrice 0 < n 1000 e valabila convent, ia stabilita la punctul A legata de modul de codificare a caracterelor.

C. Daniel vrea sa codifice s, i el nis,te mesaje folosind metoda lui Dorel. S-a gandit sa foloseasca un cifru detranspozit, ie put, in modificat. Un cifru de transpozit, ie codifica fiecare litera din mesaj folosind a k-a literade dupa ea. Astfel, pentru k = 2 de exemplu, a va deveni c, z va deveni b s, .a.m.d.Daniel va ncepe codificarea cu o valoare init, iala a lui k, pe care o va incrementa dupa 1000 de caractere.Astfel, daca trebuie sa trimita un text de 2200 de caractere cu kinit, ial = 3, va trimite primele 1000 decaractere transpuse cu 3 pozit, ii, pe urmatoarele 1000 transpuse cu 4 pozit, ii s, i pe ultimele 200, transpuse cu5 pozit, ii.

Cerint, a:Va trebui sa concepet, i un algoritm care implementeaza algoritmul dorit de Daniel pentru un kinit, ial dat s, i

pentru un n dat (unde n este dimensiunea numarul de caractere care vor fi codificate la un pas). Se vorciti din fis, ierul input1C de pe prima linie valorile lui kinit, ial s, i n s, i de pe a doua linie textul care trebuie

codificat. Mesajul n text clar va cont, ine doar litere ale alfabetului latin (lowercase sau uppercase), spat, iisau caracterele . sau . Literele mari vor fi tratate ca litere mici, astfel ncat mesajul criptat va fi lowercase.Rezultatul codificarii va fi scris n fis, ierul output1C. Matricea folosita pentru codificarea primului segmentde 1000 de caractere (deci cea care corespunde valorii kinit, ial) va fi scrisa n fis, ierul key1C.

Atent, ie! Acest subpunct se poate rezolva foarte simplu fara a folosi o matrice de codificare (de exemplu,citind textul clar ntr-un string s s, i facand apoi s = s + k). Scopul acestui exercit, iu este nsa gasirea uneimatrice care sa corespunda unei transpozit, ii. Orice abordare care nu respecta cerint,a nu va fi punctata.

Input: Programul nu va avea niciun parametru.

Output: Funct, ia voastra se va numi transposition.

Exemplu:

input1C:1 3Tema la MN e usoara (fara ghilimele)

output1C:ufnbambanoafavtpbsb (fara ghilimele)


n este dimensiunea unei matrice 0 < n 1000 checker-ul nu verifica si fis, ierul key1C, deoarece exista mai multe matrice care rezolva problema. Acest

fis, ier va fi verificat manual la corectarea temei.



Task2 - Matricile sunt fun!!! (45p)

David a descoperit o noua pasiune, pe langa muzica s, i calculatoare - matricile. Lui i plac n special operat, iilecare consuma foarte mult timp s, i memorie, cum ar fi nmult, irile de matrici, ridicarile la putere s, i calcululinverselor. Recent, David a citit ca exista nmult, iri de matrici mai eficiente, cum ar fi algoritmul lui Strassen,care are o complexitate mai buna, O(nlog27). Pentru ca David este curios, s-a gandit ca se poate obt, ineaceasta complexitate s, i pentru aflarea inversei, folosind metoda partit, ionarii. Pentru ca acest lucru ar fi preasimplu pentru voi, el va propune urmatoarea problema: dandu-se un numar N s, i o matrice A, cat este An?Cerint,ele lui sunt urmatoarele: -ridicarea la putere se va face n timp logaritmic -toate nmult, irile trebuiefacute cu algoritmul lui Strassen -nerespectarea acestor cerint,e duce la anularea punctajului pe problema,iar ncercarile de frauda, precum:

disp((An)-1),

duc la anularea punctajului pe toata tema.

Input: Fis, ierul strassen.in va cont, ine numarul N, urmat de o matrice A.

Output: Fis, ierul strassen.out va cont, ine matricea An, afis,ata cu 3 zecimale.

Exemplu:strassen.in: 51 2 31 3 42 3 4

strassen.out: 103.000 -119.000 39.000-364.000 245.000 23.000229.000 -135.000 -32.000



Detalii de implementare s, i redactare

Tema de casa va implementa functiile mentionate la fiecare cerinta n parte. Pentru implementarea temeiputeti folosi s, i alte functii definite de voi, dar cele mentionate mai sus sunt obligatorii. Trebuie sa tineti contde urmatoarele aspecte:

codul sursa va contine comentarii semnificative si sugestive cu privire la implementarea algoritmilor; existenta unui fisier readme.txt care va prezenta detaliile legate de implementarea si testarea temei;

de asemenea, la task-urile care cer explicarea anumitor aspecte, acestea trebuie sa fie cont, inute nfisierul readme.txt

fisierele care compun tema de casa vor fi incluse ntr-o arhiva .zip care respecta specificatiile dinregulamentul cursului;

tema se va implementa n Matlab si va fi testata n mediul Octave. pentru o implementare corecta se vor putea obt, ine maximum 90 de puncte s, i 10 puncte vor fi acordate

pe README.

Frequently Asked Questions

Inainte de a posta o ntrebare pe forum, parcurget, i sect, iunea urmatoare s, i celelalte thread-uri de pe forumpentru a va asigura ca ntrebarea voastra nu a fost pusa deja de altcineva:Q: Avem voie sa folosim inv(A) sau A(-1)?A: Categoric, nu. Scopul temei este ca voi sa implementat, i metode de inversare a matricelor s, i nu sa lefolosit, i pe cele existente in GNU Octave.

Q: Putem sa folosim MatLab pentru a rezolva tema?A: Da, cu ment, iunea ca MatLab pune la dispozit, ie mult mai multe funct, ii decat Octave. Cum checker-ulfoloses,te Octave pentru verificare, va trebui sa avet, i grija sa folosit, i doar funct, ii care sunt implementate s, in Octave.

Resurse Web

1. http://en.wikipedia.org/wiki/Transposition cipher

2. http://en.wikipedia.org/wiki/Hill cipher


Obiectivele TemeiTask1 - Criptografie (45p)Task2 - Matricile sunt fun!!! (45p)Detalii de implementare si redactareFrequently Asked QuestionsResurse Web

tema1_mn_2015 (1)

Documents