Retele De Calculatoare

Retele de calculatoare notit¸e de curs Radu-Lucian Lup¸sa 13 octombrie 2005

2

3

Cuprins 1 Introducere 1.1 Ce este o ret¸ea de calculatoare? . . . 1.2 Problemele abordate ˆın curs . . . . . 1.3 Problemele infrastructurii ret¸elei . . . 1.4 Tipuri de comunicat¸ie . . . . . . . . 1.5 Arhitectura sistemului de comunicat¸ii

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

5 5 5 5 6 6

2 Programarea ˆın ret¸ea — introducere 2.1 Interfat¸a de programare socket BSD . . 2.1.1 Creare . . . . . . . . . . . . . . . 2.1.2 Utilizare socket stream . . . . . . 2.1.3 Utilizare socket pentru datagrame 2.2 Adresarea in internet . . . . . . . . . . . 2.3 Transmiterea mesajelor . . . . . . . . . . 2.3.1 Mesaje binare . . . . . . . . . . . 2.3.2 Mesaje text . . . . . . . . . . . . 2.4 Asigurarea concurent¸ei . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

7 7 7 8 9 10 10 10 11 11

3 Nivelul fizic 3.1 Transmisia prin fir . . . . . . . . . . . 3.1.1 Marimi electrice . . . . . . . . . 3.1.2 Semnale . . . . . . . . . . . . . 3.1.3 Banda de trecere . . . . . . . . 3.1.4 Codarea ˆın banda de baz˘a . . . 3.1.5 Transmisia modulat˘a . . . . . . 3.1.6 Multiplexarea ˆın frecvent¸a˘ . . . 3.2 Transmisia prin unde radio . . . . . . . 3.2.1 Propagarea undelor . . . . . . . 3.2.2 Unde nedirijate ¸si unde dirijate 3.3 Transmisia prin fibr˘a optic˘a . . . . . . 3.3.1 Propagarea semnalului . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

13 13 13 14 15 16 16 17 18 18 19 19 19

. . . . .

. . . . . . . . . . . .

4 Codarea informat¸iei 21 4.1 Not¸iuni de teoria informat¸iei . . . . . . . . . . . . . . . . . . . . . 21 4.2 Problema cod˘arii pe canale f˘ar˘a zgomote . . . . . . . . . . . . . . 22 4.3 Coduri detectoare ¸si corectoare de erori . . . . . . . . . . . . . . . 26 5 Nivelul leg˘ aturii de date

29

4

6 Nivelul retea ¸si nivelul transport 6.1 Algoritmi de dirijare . . . . . . . . . 6.2 Controlul congestiei . . . . . . . . . . 6.3 Protocolul IP ¸si protocoalele auxiliare 6.4 Nivelul transport . . . . . . . . . . . 6.5 Ret¸ele eterogene ¸si ret¸ele private . . . 6.6 Ret¸ele mobile . . . . . . . . . . . . .

CUPRINS

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7 Metode ¸si protocoale criptografice 7.1 Deziderate . . . . . . . . . . . . . . . . . . . . . 7.2 Asigurarea confident¸ialit¸a˘¸tii . . . . . . . . . . . 7.2.1 Criptografia simetric˘a . . . . . . . . . . 7.2.2 Utilizarea practic˘a a cifrurilor bloc . . . 7.2.3 Numere aleatoare . . . . . . . . . . . . . 7.2.4 Criptografie asimetric˘a (cu cheie public˘a) 7.3 Autentificarea originii ¸si controlul integrit˘a¸tii . . 7.3.1 Funct¸ii de dispersie criptografice . . . . . 7.3.2 Autentificarea mesajelor . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . .

31 31 32 32 32 33 33

. . . . . . . . .

35 35 35 35 36 37 38 38 38 39

5

Capitolul 1 Introducere 1.1

Ce este o ret¸ea de calculatoare? Termenul retea de calculatoare are cel putin doua utilizari distincte:

1. mai multe calculatoare, impreuna cu un sistem (hard+soft) de comunicatii 2. un sistem de calcul, bazat pe o retea in sensul 1, dar comportandu-se ca un sistem unitar (de exemplu, prezinta aceleasi conturi de utilizatori pe toate calculatoarele)

1.2

Problemele abordate ˆın curs

1. Realizarea infrastructurii pentru comunicat¸ii; 2. Aplicat¸ii (de comunicat¸ie) in ret¸ea: • aplicat¸ii existente, • principiile realiz˘arii aplicat¸iilor ˆın ret¸ea 3. Elemente de sisteme de operare in retea.

1.3

Problemele infrastructurii ret¸elei

1. codarea fizic˘a a informat¸iei; 2. detectarea ¸si corectarea erorilor de transmisie; 3. controlul fluxului (asigurarea faptului c˘a emit¸a˘torul nu trimite mai repede decˆat poate receptorul s˘a primeasc˘a); 4. controlul coliziunilor ¸si adresarea, pe medii de tip magistral˘a (adic˘a ˆın care exist˘a mai multe entit˘a¸ti prev˘azute cu emit¸a˘toare ¸si receptoare care partajeaz˘a acela¸si mediu); 5. dirijarea comunicat¸iei ˆın ret¸ea (astfel ˆıncˆat dou˘a calculatoare s˘a poat˘a comunica, chiar dac˘a nu exist˘a leg˘atur˘a direct˘a ˆıntre ele, ci doar leg˘aturi prin intermediari);

6

Capitolul 1. Introducere

6. livrarea sigur˘a (mesajele s˘a nu se piard˘a, s˘a nu ajung˘a ˆın multiplu exemplar, ¸si s˘a ajung˘a ˆın ordinea ˆın care au fost emise); 7. securitatea: • confident¸ialitate (un mesaj s˘a poat˘a fi recept¸ionat doar de c˘atre destinatarul autorizat), • autentificarea (receptorul s˘a poat˘a verifica identitatea emit¸a˘torului, • integritatea comunicat¸iei (nimeni s˘a nu poat˘a modifica mesajele, • non-repudiabilitatea (destinatarul s˘a poat˘a dovedi originea unui mesaj, altfel spus, nici m˘acar destinatarul s˘a nu poat˘a falsifica identitatea autorului mesajului)

1.4

Tipuri de comunicat¸ie Dupa nr. de receptori:

• punct la punct (unicast): un emit¸˘ator ¸si un receptor; • difuziune (broadcast sau multicast): un emit¸a˘tor ¸si mai mult¸i receptori. Nota: broadcast este o comunicat¸ie ˆın care un mesaj este primit de toat˘a lumea; multicast desemneaz˘a o comunicat¸ie ˆın care doar o parte din calculatoarele din ret¸ea primesc mesajul. Dupa existent¸a unei conexiuni: • comunicatie prin conexiune; • comunicatie prin datagrame. Deziderate optionale: • livrare sigura (un mesaj sa fie livrat exact o data) • transmisie fara erori • pastratea ordinii relative a mesajelor • debit minim garantat • timp maxim de livrare garantat • confidentialitate • autentificare

1.5

Arhitectura sistemului de comunicat¸ii

7

Capitolul 2 Programarea ˆın ret¸ea — introducere 2.1

Interfat¸a de programare socket BSD socket = capat de cale de comunicatie Presupuneri:

• pe fiecare calculator pot rula mai multe procese, ¸si fiecare proces poate avea mai multe c˘ai de comunicat¸ie deschise, prin urmare pe un calculator trebuie s˘a poat˘a exista la un moment dat mai multe socket-uri active; • o comunicat¸ie poate fi prin conexiune sau datagrame • pentru a identifica partenerul de comunicat¸ie, init¸iatorul unei comunicat¸ii trebuie s˘a furnizeze o adres˘ a ; formatul acestei adrese poate s˘a depind˘a de tipul ret¸elei (IP, IPX, etc). API-ul este conceput s˘a fie independent de tipul exact al ret¸elei (poate funct¸iona pe ret¸ele IP, IPX, local pe unix, etc.)

2.1.1

Creare socket(proto_family, type, protocol) type: desemneaz˘a tipul de servicii dorite:

SOCK STREAM: conexiune; punct la punct; flux de date bidirect¸ional la nivel de octet; livrare sigura, cu pastrarea ordinii, transmisie fara erori. SOCK DGRAM: datagrame punct la punct sau difuziune transmisie fara erori; livrarea nu e sigura si nici ordinea garantata. SOCK RAW: acces direct la infrastructura; ex. in implementarea comenzii ping. proto family identific˘a tipul de ret¸ea cu care se lucreaz˘a (IP, IPX, etc). Se pune PF INET pentru conexiuni pe protocol Internet (IP). protocol identific˘a protocolul particular de utilizat. Este intent¸ionat a fi folosit daca ar exista mai multe protocoale distincte pentru un tip de retea dat si pentru un tip de serviciu dat. Implicit se va pune 0.

8

Capitolul 2. Programarea ˆın ret ¸ ea — introducere

Funct¸ia returneaz˘a identificatorul de socket, pe care aplicat¸ia ˆıl va furniza ˆın apelurile ulterioare.

2.1.2

Utilizare socket stream

Un socket stream poate s˘a fie ˆın una din dou˘a st˘ari: neconectat sau conectat. Un socket neconectat poate avea o adres˘a fixat˘a sau nu. Orice socket care particip˘a la o operat¸ie de comunicare trebuie s˘a aib˘a o adres˘a; dac˘a adresa nu i se fixeaz˘a explicit prin bind(), atunci sistemul ˆıi va da o adres˘a aleatoare. Conectarea, pe client: connect(sock id, addr, addr len) conecteaz˘a socket-ul local sock id cu socketul identificat prin adresa addr. Adresa addr trebuie s˘a corespund˘a unui socket de tip stream neconectat Conectarea, pe server: bind(sock id, addr, addr len) fixeaz˘a adresa socket-ului sock id. listen(sock id, dim coada) fixeaz˘a dimensiunea cozii de a¸steptare pentru conexiunile c˘atre adresa socket-ului accept(sock id, addr, addr len) a¸steapt˘a o cerere de conexiune ¸si returneaz˘a un nou socket conectat la socket-ul care a cerut conexiunea. Socket-ul original poate fi folosit ulterior pentru a a¸stepta noi conexiuni. Parametrul addr returnez˘a adresa socket-ului Comunicat¸ia propriu-zis˘a: send(sock id, buf, count, flags) trimite count octet¸i recv(sock id, buf, count, flags) recept¸ioneaz˘a cel mult count octet¸i. Dac˘a nu exist˘a nici un octet sosit, funct¸ia a¸steapt˘a sosirea a cel put¸in un octet (este blocant˘a). Apoi cite¸ste minimul ˆıntre num˘arul de octet¸i sosit¸i ¸si num˘arul de octet¸i cerut¸i (count). Returneaz˘a num˘arul de octet¸i citit¸i. Returneaz˘a 0 dac˘a emit¸˘atorul a ˆınchis conexiunea. ˆInchiderea conexiunii: close(sock id) distruge socket-ul ¸si ˆınchide complet conexiunea ata¸sat˘a (dac˘a exist˘a) shutdown(sock id, how) ˆınchide comunicat¸ia, posibil doar ˆıntr-unul singur sens Structura unui program: Clientul: #include <sys/socket.h> #include ... struct sockaddr_in adr; sd=socket(PF_INET, SOCK_STREAM, 0);

2.1. Interfat ¸ a de programare socket BSD

9

memset(&adr, 0, sizeof(adr)); adr.sin_family = AF_INET; adr.sin_port = htons(remote_port); inet_addr(remote_ip, &adr.sin_addr); if(-1==connect(sd, (struct sockaddr*)&adr, sizeof(adr)) ) { perror("connect()"); exit(1); } ... send(sd, ...); recv(sd, ...) ... close(sd); Serverul: #include <sys/socket.h> #include ... struct sockaddr_in adr; sd=socket(PF_INET, SOCK_STREAM, 0); memset(&adr, 0, sizeof(adr)); adr.sin_family = AF_INET; adr.sin_port = htons(remote_port); adr.sin_addr = INADDR_ANY; if(-1==bind(sd, (struct sockaddr*)&adr, sizeof(adr)) ) { perror("connect()"); exit(1); } listen(sd, 5); ... struct sockaddr_in client_adr; socklen_t client_adr_size; sd_c = accept(sd, (struct sockaddr*)&client_adr, &client_adr_size) ... send(sd_c, ...); recv(sd_c, ...) ... close(sd_c); ... close(sd);

2.1.3

Utilizare socket pentru datagrame

Probabil cel put¸in unul din capete trebuie s˘a fixeze adresa socket-ului, la o valoare cunoscut˘a de partener; pentru aceasta folose¸ste apelul bind(). Cel˘alalt cap˘at prime¸ste automat o adres˘a la prima trimitere de datagram˘a. Funct¸ii:

Capitolul 2. Programarea ˆın ret ¸ ea — introducere

10

bind(sock id, addr, addr len) fixeaz˘a adresa socket-ului; sendto(sock id, buf, count, flags, addr, addr len) trimite o datagram˘a la adresa specificat˘a; recvfrom(sock id, buf, count, flags, addr, addr len) recept¸ioneaz˘a o datagram˘a, ¸si pune ˆın addr adresa de provenient¸a˘.

2.2

Adresarea in internet Adresa IP:

• identific˘a unic ma¸sina • 32 bit¸i; de obicei scris˘a ca 4 numere zecimale separate prin puncte (ex. 193.226.40.130) • ˆın principiu, fiecare interfat¸˘a de ret¸ea (ex. plac˘a de ret¸ea, linie seriala sau modem folosit pentru o conexiune in ret¸ea) are o adresa IP • adresa 127.0.0.1 corespunde unei interet¸e virtuale intr-o retea (virtual˘a) ˆın care calculatorul este singur. Altfel spus, 127.0.0.1 desemneaz˘a intotdeauna ma¸sina locala. • unele adrese sunt folosite pentru broadcast Numarul portului: • serve¸ste pentru a diferent¸ia intre socket-ii de pe aceea¸si ma¸sina • 16 bit¸i (1–65535) • porturile TCP (SOCK STREAM) sunt independente de porturile UDP (SOCK DGRAM)

2.3

Transmiterea mesajelor

Exemplu: clientul anunt¸a˘ scoaterea dintr-o magazie a unei anumite cantit˘a¸ti de marf˘a. Se trimite un mesaj cont¸inˆand denumirea ¸si cantitatea.

2.3.1

Mesaje binare Exemplu:

struct Cerere { char denumire[30]; int cantitate; }; Cerere c; ... send(sd, &c, sizeof(c), 0);

2.4. Asigurarea concurent ¸ ei

11

Probleme: 1. lungimea (num˘arul de octet¸i) pe care se reprezint˘a un int este dependent˘a de platform˘a 2. ordinea octet¸ilor este dependent˘a de platform˘a (little endian vs. big endian) 3. alinierea e dependent˘a de platform˘a (se poate ca adresa unui ˆıntreg s˘a trebuiasc˘a s˘a fie multiplu de 2, 4 sau 8 octet¸i) Solut¸ie: 1. se folosesc typedef-urile uint16 t, uint32 t definite ˆın netinet/in.h ; lungimea reprezent˘arii lor e independent˘a de platform˘a; 2. se convertesc la o ordine a octet¸ilor independent˘a de platform˘a: funct¸iile htons(), htonl(), ntohs(), ntohl(); 3. se transmite individual fiecare membru al unei structuri. Exemplu: struct Cerere { char denumire[30]; unit32_t cantitate; }; Cerere c; ... send(sd, c.denumire, 30, 0); c.cantitate=htonl(c.cantitate); send(sd, &c.cantitate);

2.3.2

2.4

Mesaje text

Asigurarea concurent¸ei

12

Capitolul 2. Programarea ˆın ret ¸ ea — introducere

13

Capitolul 3 Nivelul fizic 3.1 3.1.1

Transmisia prin fir Marimi electrice Reamintim din fizica de liceu urm˘atoarele m˘arimi electrice:

Sarcina electric˘ a (Q) m˘asoar˘a cantitatea de electricitate. Este analoag˘a cantit˘a¸tii de fluid. Putem m˘asura cantitatea de electricitate (sarcina electric˘a) ce trece printr-un conductor ˆıntr-o perioad˘a de timp. Se m˘asoar˘a ˆın coulombi (C). Intensitatea curentului (I) (numit˘a pe scurt curentul ) m˘asoar˘a sarcina electric˘a ce trece printr-un conductor ˆımp˘art¸it˘a la timpul ˆın care trece. Este analoag˘a debitului de fluid printr-o conduct˘a. Intensitatea curentului ce trece printr-un conductor se m˘asoar˘a ˆıntrerupˆand conductorul ¸si intercalˆand un instrument de m˘asur˘a numit ampermatru. Ampermetrul trebuie s˘a conduc˘a foarte bine curentul (s˘a aib˘a impedant¸a — vezi mai jos — cˆat mai mic˘a) pentru a perturba cˆat mai put¸in circuitul ˆın care m˘asoar˘a. Se m˘asoar˘a ˆın amperi (A). Intensitatea curentului prin circuite folosite la transmiterea informat¸iei este de regul˘a de ordinul zecilor de miliamperi. Tensiunea electric˘ a (U) ˆıntre dou˘a conductoare m˘asoar˘a cˆat de puternic ar fi impins˘a o sarcin˘a electric˘a aflat˘a ˆın primul conductor c˘atre cel de-al doilea. Este analoag˘a diferent¸ei de presiune ˆıntre dou˘a conducte de fluid. Pentru a m˘asura tensiunea electric˘a ˆıntre dou˘a conductoare, mont˘am un instrument numit voltmetru cu o born˘a conectat˘a la unul din conductoare ¸si cu cealalt˘a born˘a legat˘a la cel˘alalt conductor. Voltmetrul trebuie s˘a fie cˆat mai aproape de un izolator — s˘a conduc˘a cˆat mai put¸in curent de la o born˘a la alta (aidc˘a s˘a aib˘a impedant¸a cˆat mai mare). Tensiunea se m˘asoar˘a ˆın volt¸i (V). Tensiunile intre conductoarele folosite pentru transmisia informat¸iei sunt de ordinul cˆatorva volt¸i. Puterea ¸si energia electric˘ a (P) Un element de circuit la bornele c˘aruia se aplic˘a o tensiune U ¸si prin care trece un curent de intensitate I de acela¸si sens cu tensiunea prime¸ste o putere P = U I. Dac˘a intensitatea are sens invers tensiunii, elementul livreaz˘a puterea P = U I circuitului. Puterea se m˘asoar˘a ˆın watti (W).

14

Capitolul 3. Nivelul fizic

Energia electric˘ a (E) Energia m˘asoar˘a produsul dintre puterea primit˘a sau cedat˘a de un element de circuit ¸si timpul cˆat are loc fenomenul. Unitatea de m˘asur˘a ˆın Sistemul Internat¸ional este joule-ul (J), ˆıns˘a frecvent se folose¸ste kilowattora (kWh) (atent¸ie, simbolul kW/h , citit kilowatt pe or˘a, nu este corect, de¸si este folosit curent); un kilowattor˘a este energia primit˘a de un consumator care prime¸ste o putere de un kilowatt timp de o or˘a; ˆın consecint¸a˘ 1kWh = 3600000J. Elemente de circuit ¸si m˘arimi caracteristice (Not˘a: fiecare element poate fi construit ˆın mod deliberat, ˆıns˘ a comportamentul poate s˘a apar˘ a ¸si acolo unde nu este dorit): rezistorul si rezistent¸a (R) Un rezistor este un element de circuit condensatorul ¸si capacitatea (C) . bobina ¸si inductant¸a (L) . impedant¸a (Z) ¸si conductant¸a (G) surse ¸si consumatori

3.1.2

Semnale

ˆIn general, prin semnal se ˆıntt¸elege valoarea unei m˘arimi fizice, urm˘arie ca funct¸ie de timp, folosite pentru transmiterea informat¸iei. ˆIn cazul transmiterii prin conductoare electrice, semnalul este tensiunea ˆıntre cele dou˘a conductoare; semnalul emis, notat Ue (t), este tensiunea m˘asurat˘a la momentul t la bornele emit¸a˘torului, iar semnalul recept¸ionat, notat Ur (t), este tensiunea m˘asurat˘a la bornele receptorului. ˆIn general, semnalul recept¸ionat nu coincide cu semnalul emis. Apar mai multe fenomene: ˆıntˆ arzierea face ca semnalul recept¸ionat s˘a urmeza cu o anumit˘a ˆıntˆarziere semnalul emis. Ideal (adic˘a ˆın lipsa fenomenelor de mai jos), Ur (t) = Ue (t − vl ), unde l este lungimea liniei iar v este viteza de propagare a semnalului; aceasta din urm˘a depinde doar de materialul izolator dintre conductoarele liniei. ˆIn practic˘a, v ≈ 2/3c = 2 · 108 m/s, unde c este viteza luminii ˆın vid. atenuarea face ca semnalul recept¸ionat s˘a aib˘a amplitudine mai mic˘a decˆat cel emis. Fiecare metru al liniei scoate la ia¸sire un semnal egal cu un anumit procent din semnalul intrat; ca urmare, amplitudinea semnalului recept¸ionat scade exponent¸ial cu cre¸sterea lungimii liniei. Mai exact, neglijˆand ˆıntˆarzierea, Ur (t) = g · Ue (t), unde 0 < g < 1 ¸si are forma g = g0l . Se nume¸ste factor de atenuare valoarea (1/g)2 ;aceasta arat˘a raportul ˆıntre puterea semnalului emis ¸si a celui recept¸ionat (ˆın general puterea este proport¸ional˘a cu p˘atratul tensiunii, deoarece raportul tensiune/intensitate este aproximativ constant). ˆIn practic˘a, ˆın loc s˘a scriem factorul de atenuare (1/g)2 scriem atenuarea, care, dat˘a ˆın decibeli (notat dB) este 10·log10 (1/g)2 . Astfel, dac˘a o linie are atenuare de 10dB ˆınseamn˘a c˘a puterea recept¸ionat˘a

3.1. Transmisia prin fir

15

p este 1/10 din puterea emis˘a ¸si c˘a tensiunea recept¸ionat˘a este 1/ (10) din tensiunea emis˘a. Atenuarea unui cablu este proport¸ional˘a cu lungimea, iar puterea ¸si tensiunea recept¸ionate scad exponent¸ial cu lungimea. Dac˘a un cablu are atenuarea 0.1dB/m ˆınseamn˘a c˘a pe 100m de cablu vom avea o atenuare de 10dB, adic˘a o reducere de 10 ori a puterii. Pe 30m din acela¸si cablu, atenuarea va fi de 3dB, adic˘a o reducere de aproximativ 2 ori a puterii (mai exact, factorul de atenuare este de 100.3 ≈ 1.9953). Atenuarea depinde de materialele din care sunt f˘acute conductoarele ¸si izolatorul precum ¸si de geometria cablului. distorsiunile determin˘a semnalul recept¸ionat s˘a aib˘a o form˘a diferit˘a fat¸a˘ de semnalul emis.

3.1.3

Banda de trecere

Consider˘am un circuit electronic, care are o intrare ¸si o ie¸sire (fig. ??). ˆIn particular, o pereche de fire folosite pentru transmisie poate fi considerat˘a un astfel de circuit, capetele dinspre emit¸˘ator constituind intrarea, iar cele dinspre receptor, ie¸sirea. Tensiunea de la ie¸sire depinde de tensiunea de la intrare, ˆıns˘a ˆın general depinde de tot istoricul ei. Altfel spus, comportamentul circuitului poate fi descris de o funct¸ie care prime¸ste ca argument funct¸ia tensiune-timp de la intrare si ˆıntoarce funct¸ia tensiune-timp de la ia¸sire (o funct¸ie definit˘a pe un spatt¸iu de funct¸ii cu valori tot ˆıntr-un spat¸iu de funct¸ii). Scriem Ue = T (Ui ), unde Ui (t) este valoarea tensiunii de intrare la momentul t, iar Ue (t) este tensiunea de ie¸sire la momentul t. Multe circuite electronice au un comportament liniar, adic˘a dac˘a Ui (t) poate fi scris ca Ui (t) = Ui1 (t) + Ui2 (t) + · · · + Uin (t), atunci Ue (t) = Ue1 (t) + Ue2 (t) + · · · + Uen (t), unde Ue1 = T (Ui1 ), Ue2 = T (Ui2 ), etc. Circuitele liniare au proprietatea c˘a, dac˘a semnalul de intrare este sinusoidal, adic˘a Ui (t) = U0 · sin(ωt + φ) atunci semnalul de ie¸sire este tot sinusoidal, ¸si, mai mult, Ue (t) = g(ω) · U0 · sin(ωt + φ − θ(ω) unde g(ω) ¸si θ(ω) depind doar de cun este construit circuitul ¸si de frecvent¸a (ω = 2πf , unde f este frecvent¸a semnalului). Orice semnal se poate scrie unic ca o sum˘a de semnale sinusoidale. (Nota: scrierea unei funct¸ii ca sum˘a de sinusoide este a¸sa-numita transformata Fourier. Condit¸iile de existent¸˘ a depind de cadrul ˆın care se scrie — funct¸ie in L2 , distribut¸ie, etc. Prezentarea de fat¸˘ a are doar scop de suport intuitiv; lipsesc detaliile matematice ¸si ˆın consecint¸˘ a cele scrise aici nu pot fi folosite pentru a sprijini

16

Capitolul 3. Nivelul fizic

ˆın mod fiabil rat¸ionamente). Transformata Fourier se mai nume¸ste ¸si spectrul semnalului. Ca urmare a liniarit˘a¸tii, semnalul de ie¸sire se poate calcula descompunˆand ˆın sinusoide semnalul de intrare, calculˆand efectul circuitului asupra fiec˘arei sinusoide ˆın parte, ¸si ˆınsumˆand ˆın final ie¸sirile. Comportamentul unui circuit liniar este deci complet definit de funct¸iile g(ω) ¸si θ(ω) de mai sus. Un semnal este nedistorsionat dac˘a ¸si numai dac˘a, pentru toate valorile ω din spectrul semnalului (adic˘a acelea pentru care amplitudinea sinusoidei corespunz˘atoare este nenul˘a) g(ω) are aceea¸si valoare ¸si θ(ω) este proport¸ional cu ω. ˆIn general, un circuit (inclusiv o linie de transmisie) va prezenta distorsiuni mici doar pentru semnale a c˘aror spectru se ˆıncadreaz˘a ˆıntre anumite valori extreme fmin ¸si fmax . Acest interval se nume¸ste banda de trecere a circuitului. Diferent¸a fmax − fmin se nume¸ste l˘ a¸timea de band˘ a a circuitului (sau a liniei). De exemplu, banda de trecere a unui circuit de telefon este cuprins˘a ˆıntre aproximativ 300Hz ¸si 3kHz.

3.1.4

Codarea ˆın banda de baz˘ a

Prin codare ˆın acest context se ˆınt¸elege regulile prin care unui ¸sir de bit¸i de transmis i se asociaz˘a semnalul emis. Codarea cea mai simpl˘a este aceea ˆın care ˆımp˘art¸im timpul ˆın celule de durat˘a fixat˘a (pe care o numim lungimea unui bit) ¸si, pe durata fiec˘arui bit semnalul emis va avea o anumit˘a valoare — de exemplu 12V — dac˘a bitul are valoarea 1 ¸si 0V dac˘a bitul are valoarea 0. Receptorul va avea un ceas cu care va determina celulele corespunz˘atoare bit¸ilor, ¸si va m˘asura semnalul la mijlocul fiec˘arei celule de bit. Dac˘a tensiunea va fi mai mare de, s˘a zicem, 3V, va decide c˘a bitul respectiv are valoarea 1, altfel 0.

3.1.5

Transmisia modulat˘ a

Transmisia modulat˘a se folose¸ste atunci cˆand este necesar ca spectrul semnalului s˘a ocupe o band˘a departe de frecvent¸a zero. Aceast poate fi necesar fie pentru c˘a circuitele sau mediul de transmisie nu pot transmite frecvent¸ele apropiate de zero, fie pentru a putea transmite mai multe semnale pe acela¸si mediu prin multiplexare ˆın frecvent¸a˘. Modularea const˘a ˆın a transmite un semnal de forma U (t) = a · sin(ωt + φ), unde unul din parametri a, ω sau φ sunt funct¸ie de semnalul ce s-ar transmite ˆın lipsa modulat¸iei. Mai exact, putem avea: modulat¸ie ˆın amplitudine (AM): semnalul transmis este de forma U (t) = U0 · s(t) · sin(2πfp t) unde s(t) este semnalul de modulat, cel care poart˘a informat¸ia util˘a, iar fp este a¸sa-numita frecvent¸˘ a purt˘atoare a semnalului.

3.1. Transmisia prin fir

17

Se observ˘a c˘a modulat¸ia ˆın amplitudine este liniar˘a (modulat¸ia sumei a dou˘a semnale a + b este suma rezultatelor modulat¸iei independente pentru a ¸si b) ¸si c˘a dac˘a semnalul de modulat este sinusoidal a(t) = sin(2πfs t + φ) atunci U (t) = U0 · s(t) sin(2πfp t = = U0 · sin(2πfs t + φ) sin ωt = µ ¶ 1 1 = U0 · cos ((ω − 2πf )t − φ) − cos ((ω + 2πf )t + φ) 2 2 adic˘a ˆın urma modulat¸iei ˆın amplitudine a unui semnal sinusoidal se obt¸ine o sum˘a de dou˘a semnale sinusoidale avˆand ca frecvent¸e suma dintre frecvent¸a semnalului de modulat ¸si frecvent¸a purt˘atoare ¸si cel˘alalt avˆand diferent¸a celor dou˘a frecvent¸e. ˆIn condit¸ii reale, frecvent¸a purt˘atoare este cel putin de cˆateva ori mai mare decˆat frecvent¸ele din spectrul semnalului de modulat. Spectrul unui semnal modulat ˆın amplitudine va cont¸ine frecvent¸a purt˘atoare ¸si dou˘a benzi laterale, stˆang˘a ¸si dreapt˘a, acestea cuprinzˆand diferent¸ele, respectiv sumele, frecvent¸elor din spectrul semnalului util cu frecvent¸a purt˘atoare. ˆIntrucˆat spectrul semnalului modulat este simetric ˆın jurul frecvent¸ei purt˘atoare, de fapt doar una dintre benzile laterale poart˘a informat¸ie util˘a. Din acest motiv, adesea se suprim˘a total sau part¸ial de la transimisie una dintre benzile laterale. modulat¸ie ˆın frecvent¸˘ a (FM): semnalul transmis are forma ¡ ¢ U (t) = U0 · sin 2π · (fp + s(t)) · t unde, din nou, fp este numit˘a frecvent¸a purt˘atoare ¸si s(t) este semnalul util; avem s(t) ¿ fp . Analiza spectrului unui semnal modulat ˆın frecvent¸˘a este mult mai difcil˘a decˆat ˆın cazul modulat¸iei ˆın amplitudine. modulat¸ie ˆın faz˘ a: semnalul transmis are forma ¡ ¢ U (t) = U0 · sin 2πfp t + s(t) Este evident c˘a, ˆıntrucˆat receptorul nu are de obicei un reper absolut de timp, el nu poate detecta decˆat variat¸iile de faz˘a ale semnalului recept¸ionat. Ca urmare, o valoare constant˘a a lui s(t) nu poate fi deosebit˘a de zero ¸si, mai mult, nici variat¸ii lente ale lui s(t) nu pot fi detectate. ˆIn consecint¸˘a, spectrul lui s(t) nu poate cont¸ine frecvent¸e prea apropiate de 0.

3.1.6

Multiplexarea ˆın frecvent¸˘ a

Dac˘a modul˘am mai multe semnale s1 . . . sn folosind frecvent¸e purt˘atoare fp1 . . . fpn suficient de dep˘artate pentru ca spectrele semnalelor modulate s˘a nu se

18

Capitolul 3. Nivelul fizic

ˆıntrep˘atrund˘a, putem transmite toate semnalele pe acela¸si mediu de transmisie f˘ar˘a ca semnalele s˘a interfereze. Acest procedeu se nume¸ste multiplexare ˆın frecvent¸˘ a. Poate fi folosit atˆat pentru a transmite dou˘a sau mai multe semnale ˆın acela¸si sens, cˆat ¸si pentru a transmite semnale ˆın ambele sensuri simultan (transmisie full-duplex ). Emit¸a˘torul va suprapune pur ¸si simplu semnalele modulate. Receptorul va separa, cu ajutorul unor circuite capabile s˘a filtreze de pe o linie doar o anumit˘a band˘a de frecvent¸e, semnalele modulate, dup˘a care le va demodula independent pe fiecare.

3.2 3.2.1

Transmisia prin unde radio Propagarea undelor

Propriet˘a¸tile de propagare ale undelor radio depind de lungimea de und˘a sub dou˘a aspecte: 1. Orice und˘a ocole¸ste obstacolele mai mici decˆat o fract¸iune din lungimea de und˘a, ˆın vreme ce ˆın spatele obstacolelor mai mari de cˆatea lungimi de und˘a ,,r˘amˆane umbr˘a“. De aceea, undele lungi, cu lungime de und˘a de ordinul kilometrilor sau sutelor de metri sunt capabile s˘a ocoleasc˘a obstacole mari, inclusiv curbura P˘amˆantului pe distant¸a˘ de cˆateva sute sau chiar mii de kilometri. Prin contrast, undele cu lungime de und˘a sub cˆa¸tiva metri se propag˘a aproape numai ˆın linie dreapt˘a, dealurile sau cl˘adirile mai mari putˆand provoca umbre. 2. Absorbt¸ia ¸si reflexia undelor pe diferite materiale depinde de lungimea de und˘a; este similar˘a cu absorbt¸ia ¸si reflexia diferit˘a a luminii de diferite culori. Ionosfera reflect˘a undele cu lungimi de und˘a de ordinul metrilor; prin reflexii repetate ˆıntre P˘amˆant si ionosfer˘a, aceste unde pot parcurge u¸sor multe mii de kilometri. Microundele (cca. 1cm–20cm) ¸si lumina vizibil˘a (400nm– 700nm) sunt singurele care pot traversa atmosfera terestr˘a; ˆıns˘a microundele ˆın jurul a 6GHz (5cm) sunt puternic absorbite de ap˘a ¸si ca urmare trec greu prin nori ¸si prin ploaie. Puterea semnalului scade, pe m˘asur˘a ce ne ˆındep˘art˘am de emit¸a˘tor, din dou˘a cauze: • datorit˘a extinderii frontului de und˘a, puterea pe unitatea de suprafat¸a˘ a frontului de und˘a este mai mic˘a. Sc˘aderea este cu p˘atratul distant¸ei: Pr = Pe · α ·

1 d2

unde α este o constant˘a ce depinde de construct¸ia antenelor de emisie ¸si de recept¸ie, iar d este distant¸a ˆıntre emit¸˘ator ¸si receptor. • datorit˘a absorbt¸iei undelor ˆın mediu. Aceast˘a sc˘adere este exponent¸ial˘a cu distant¸a, ca ¸si ˆın cazul cablurilor, ˆıns˘a de cele mai multe ori este neglijabil˘a fat¸˘a de extinderea frontului de und˘a.

˘ optica ˘ 3.3. Transmisia prin fibra

3.2.2

19

Unde nedirijate ¸si unde dirijate

Exist˘a antene direct¸ionale ¸si antene nedirect¸ionale. Antenele direct¸ionale emit ¸si recept¸ioneaz˘a unde aproape doar ˆıntr-o singur˘a direct¸ie; cele nedirect¸ionale emit aproape cu aceea¸si putere (respectiv, recept¸ioneaz˘a cu aceea¸si sensibilitate) de jur ˆımprejur. Antenele nedirect¸ionale sunt de cele mai multe ori un simplu baston metalic (de fapt, bastonul este un pol, iar carcasa aparatului sau, dup˘a caz, P˘amˆantul. este cel˘alalt pol). Antenele direct¸ionale cele mai r˘aspˆandite pentru comunicat¸iile ce ne intereseaz˘a au directivitatea asigurat˘a de o oglind˘a de forma unui paraboloid de rotat¸ie, cu antena propriu-zis˘a plasat˘a ˆın focarul paraboloidului. (a¸sa-numitele antene parabolice). O anten˘a direct¸ionale trebuie s˘a fie orientat˘a ˆın permanent¸a˘ c˘atre partenerul de comunicat¸ie. ˆIn schimb, ca avantaj fat¸a˘ de antenele nedirect¸ionale, puterea emis˘a poate fi mai mic˘a, sensibilitatea receptorului poate fi mai sc˘azut˘a — ˆıntrucˆat o mai mare parte din energia emis˘a de emit¸˘ator ajunge pe receptor — ¸si pot exista ˆın aceea¸si zon˘a mai multe instalat¸ii ce folosesc aceea¸si frecvent¸a˘ f˘ar˘a s˘a interfereze.

3.3 3.3.1

Transmisia prin fibr˘ a optic˘ a Propagarea semnalului

20

Capitolul 3. Nivelul fizic

21

Capitolul 4 Codarea informat¸iei 4.1

Not¸iuni de teoria informat¸iei

Teoria informat¸iei serve¸ste la a putea evalua necesarul de informat¸ie de transmis de la emit¸a˘tor la receptor ¸si de-a evalua eficient¸a ¸si redundant¸a transmiterii informat¸iei. Teoretic receptorul are nevoie de un mesaj de la emit¸˘ator dac˘a cont¸inutul acelui mesaj (¸si eventual momentul ˆın care este trimis) nu poate fi dedus de c˘atre receptor pe baza cuno¸stint¸elor sale. Putem spune c˘a un mesaj cont¸ine informat¸ie dac˘a aduce receptorului ceva ce acesta nu putea obt¸ine singur. Prin urmare, un mesaj cont¸ine informat¸ie numai ˆın m˘asura ˆın care receptorul are o incertitudine pe care prin primirea mesajului o poate ˆınl˘atura. Informat¸ia este deci ˆınl˘aturarea unei incertitudini. M˘asura informat¸iei trebuie s˘a m˘asoare incertitudinea ˆınl˘aturat˘a prin dobˆandirea unei informat¸ii. Presupunem c˘a avem o mult¸ime complet˘a de evenimente posibile, disjuncte: A = {x1 , x2 , . . . , xn } cu probabilit˘a¸tile pi = P (xi ). Prin definit¸ie, un mesaj care ˆın¸stiint¸eaz˘a receptorul de producerea evenimentului xi aduce o cantitate de informat¸ie i = −log2 pi . Unitatea de m˘asur˘a se nume¸ste bit. Observat¸ie: a nu se confunda bitul unitate da m˘asur˘ a a informat¸iei, cu bitul cifr˘a ˆın baza 2. Exist˘ a o leg˘ atur˘ a: presupunˆ and o codare ideal˘ a, o informat¸ie de n bit¸i poate fi codat˘ a ca un ¸sir de n bit¸i. La transmisia informat¸iei se pune ˆın mod obi¸snuit problema urm˘atoare: emit¸a˘torul are o mult¸ime de mesaje posibile M = {m1 , m2 , . . . , mn }. Dintre acestea, el va trebui s˘a transmit˘a unul. Pe de alt˘a parte, emit¸a˘torul are la dispozit¸ie o mult¸ime de simboluri de cod S = {s1 , s2 , . . . , sk } pe care le poate emite; el poate transmite un ¸sir de astel de simboluri de cod. ˆIn general, S are dou˘a elemente, notate 0 ¸si 1 (S = {0, 1}. Fiecare mesaj trebuie codificat ca un ¸sir de simboluri de cod, printr-o funct¸ie de codare c : M → S ? . Funct¸ia c trebuie s˘a fie injectiv˘a, pentru ca orice cuvˆant de cod s˘a fie unic decodabil, ¸si s˘a fie cunoscut˘a receptorului pentru ca acesta s˘a poat˘a decoda efectiv orice mesaj primit. Problema cod˘arii informat¸iei este s˘a se aleag˘a o funct¸ie c potrivit˘a. Cerint¸ele sunt s˘a minimizeze lungimea medie a cuvintelor de cod, ¸si s˘a permit˘a decodarea ˆın prezent¸a erorilor, adic˘a dac˘a receptorul prime¸ste un cuvˆant de cod u¸sor modificat. Modelul de lucru ˆın problema cod˘arii informat¸iei este urm˘atorul:

22

Capitolul 4. Codarea informat ¸ iei

Figura 4.1: Codarea informat¸iei pentru transmitere Exist˘a o surs˘a de informat¸ie, care produce ˆın timp un ¸sir de mesaje dintr-o mult¸ime finit˘a M . Canalul de transmisie (mediul fizic) permite transmiterea unor simboluri de cod dintro alt˘a mult¸ime finit˘a, S numit˘a alfabetul canalului (ˆın majoritatea cazurilor S = {0, 1}). Transmiterea informat¸iei prin canal presupune codarea mesajelor, astfel ˆıncˆat fiec˘arui mesaj ˆıi corespunde o secvent¸˘a de simboluri de cod. Avem schema din figura ??. M˘ asurarea informat¸iei Este util uneori s˘a putem defini cantitatea de informat¸ie purtat˘a de un mesaj. Pentru aceasta este necesar ca s˘a asign˘am fiec˘arui mesaj posibil probabilit˘atea de-a fi emis. Definitia 4.1 Cantitatea de informat¸ie adus˘a de un mesaj m este − log2 (pm ), unde pm este probabilitatea emisiei mesajului m. De remarcat c˘a, cantitatea de informat¸ie este o m˘asur˘a a incertitudinii ˆınl˘aturate de mesaj. Daca primirea mesajul era aproape sigur˘a (p ' 1) incertitudinea primirii este mic˘a ¸si cantitatea de informat¸ie este de asemenea mic˘a.

4.2

Problema cod˘ arii pe canale f˘ ar˘ a zgomote

Cod: o funct¸ie c : M → S ∗ , unde M este mult¸imea mesajelor posibile, iar S este mult¸imea simbolurilor de cod (simbolurile ce pot fi codate fizic direct pe canal, de exemplu ca nivele de semnal). Termeni: mesaj obiectul trimis de surs˘a, apart¸inˆand mult¸imii mesajelor posibile M simbol de cod simbol ce poate fi trimis direct la nivel fizic (ce poate fi codat direct ca nivel de tensiune pe linie, de exemplu); alfabetul sursei mult¸imea simbolurilor de cod posibile; secvent¸˘ a de cod secvent¸a˘ oarecare de simboluri de cod; cuvˆ ant de cod secvent¸˘a de cod prin care se codeaz˘a un mesaj. Cod unic decodabil Pentru ca decodarea s˘a fie posibil˘a, funct¸ia c este necesar s˘a fie injectiv˘a. (Not˘a: surjectivitatea nu este nici necesar˘a nici posibil˘a; imposibilitatea este datorat˘a faptului c˘a M este finit˘a ¸si S ∗ este infinit˘a). Injectivitatea nu este suficient˘a. De exemplu: a 7→ 0, b 7→ 1, c 7→ 01 este injectiv˘a dar secvent¸a de cod 01 poate proveni din ab sau din c. Funct¸ia c se extinde la cˆ : M ∗ → S ∗ prin cˆ(m1 · m2 · · · · · mk ) = c(m1 ) · c(m2 ) · · · · · c(mk ) (punctul reprezint˘a concatenarea). Definitia 4.2 Codul este unic decodabil dac˘a cˆ este injectiv˘ a.

˘ rii pe canale fa ˘ ra ˘ zgomote 4.2. Problema coda

0

23

1

a

0

1

0

1

d

b

c

Figura 4.2: Arborele ata¸sat unui cod prefix Condit¸ii pentru unic decodabilitate Teorema 4.3 Pentru orice cod unic decodabil are loc inegalitatea: n X

|S|−lk ≤ 1

(4.1)

k=1

unde lk sunt lungimile cuvintelor de cod, iar |S| este num˘arul de simboluri de cod. Definitia 4.4 Un cod se spune c˘a are proprietatea de prefix (sau mai scurt, este cod prefix) dac˘a nici un cuvˆant de cod nu este prefix al altui cuv˘ant de cod. Exemplu: a 7→ 0 b 7→ 101 c 7→ 11 d 7→ 100 Unui cod prefix i se poate ata¸sa un arbore ˆın care fiec˘arui mesaj ˆıi corespunde o frunz˘a, muchiile descendente de la fiecare nod sunt etichetate cu simboluri de cod distincte, iar cuvˆantul de cod al unui mesaj este format din simbolurile de cod ale muchiilor de pe lant¸ul ce une¸ste r˘ad˘acina cu frunza ata¸sat˘a mesajului. Exemplu: fig. 4.2 Teorema 4.5 Orice cod cu proprietatea de prefix este unic decodabil. Teorema 4.6 Dac˘ a l1 . . . lk satisac inegalitatea 4.1, atunci exist˘a un cod cu proprietatea de prefix av˘and lungimile cuvintelor de cod l1 . . . lk . Construct¸ia: Sort˘am cresc˘ator lungimile cuvintelor (lk ). Construim arborele ata¸sat codului plecˆand de la r˘ad˘acin˘a. La fiecare nivel, alegem dintre vˆarfurile de pe acel nivel un num˘ar egal cu num˘arul cuvintelor de cod de acea lungime ¸si le acem frunze, ata¸sate mesajelor corespunz˘atoare. Restul nodurilor vor r˘amˆane noduri interne, ¸si vor da descendent¸i pe nivelul urm˘ator; fiecare nod va da |S| descendent¸i, iar muchiile descendente se vor eticheta cu simboluri de

24

Capitolul 4. Codarea informat ¸ iei

0

1

0

a

a

1 0

1

c

1

0 a

0 c

1 0 b

1 d

Figura 4.3: Construct¸ia unui cod prefix cu lungimi fixate ale cuvintelor de cod cod ˆıntr-o ordine arbitrar˘a. Inegalitatea 4.1 ne asigur˘a c˘a vom avea la fiecare nivel suficiente vˆarfuri de ata¸sat mesajelor a c˘aror cuvinte de cod urmeaz˘a s˘a aib˘a acea lungime. Exemplu: figura 4.3 arat˘a etap˘a cu etap˘a construct¸ia unui cod pentru lungimile l1 = 1, l3 = 2, l2 = 3, l4 = 3. Cerculet¸ele desemneaz˘a nodurile neata¸sate unor mesaje, care urmeaz˘a s˘a produc˘a descendent¸i pe nivelul urm˘ator. Observat¸ie: din teoremele din acest paragraf rezult˘a c˘a dac˘a avem un cod unic decodabil pentru ni¸ste mesaje putem g˘asi un cod prefix cu acelea¸si lungimi ale cuvintelor de cod. Coduri optimale Dac˘a dorim codificarea unei secvent¸e de mesaje s˘a fie cˆat mai scurt˘a, avem nevoie de un cod care s˘a minimizeze lungimea medie a cuvˆantului de cod. Media lungimilor se va calcula ponderat, cu ponderile egale cu probabilit˘a¸tile de aparit¸ie ale respectivelor cuvinte de cod. Definitia 4.7 Un cod optimal este un cod unic decodabil care are cea mai mic˘a lungimea medie a cuvintelor de cod. Presupunˆand c˘a avem la dispozit¸ie doar dou˘a cuvinte de cod, avem l ≥ H(M ), adic˘a lungimea medeie a cuvˆantului de cod nu poate fi mai mic˘a decˆat informat¸ia medie pe simbol a sursei. Algoritmul Huffman Dac˘a facem presupunerea c˘a sursa este ergotic˘ a, adic˘a probabilitatea de-a emite un anumit mesaj nu depinde de mesajele precedente ¸si nici de timp, codul optimal se poate construi prin algoritmul lui Huffman. Algoritmul Huffman (vezi fig. 4.4) este urm˘atorul (presupunem |S| = 2, adic˘a alfabetul canalului are doar dou˘a simboluri):

˘ rii pe canale fa ˘ ra ˘ zgomote 4.2. Problema coda

0.55

0.10

a

b

0.55

0.20

0.15

0.55

c

d

a

0.20

0 0 b

d

0

1

b

d

1.00 1

1

0.25

c

0.45

a

25

c

0

1

a

0 0 b

1 1

c

d

Figura 4.4: Funct¸ionarea algoritmului Huffman Pentru ˆınceput, se ata¸seaz˘a fiec˘arui mesaj un arbore format dintr-un singur vˆarf, ¸si i se ata¸seaz˘a arborelui respectiv frecvent¸a acelui mesaj. ˆIn continuare, la fiecare pas se selecteaz˘a cei doi arbori cu frecvent¸ele de aparit¸ie asociate cele mai mici. Se unesc cei doi arbori prin creerea unui nou nod ce va deveni r˘ad˘acin˘a ¸si va avea subordonat¸i cei doi arbori. Una din muchiile nou introduse va fi etichetat˘a cu 0, cealalt˘a cu 1. Noului arbore i se asociaz˘a frecvent¸a egala cu suma frecvent¸elor celor doi arbori unit¸i. Algoritmul se termin˘a ˆın momentul ˆın care r˘amˆane un singur abrore. Teorema 4.8 Codul obt¸inut prin algoritmul Huffman este optimal. Aplicat¸ii Codarea optimal˘a este ceea ce face orice program de compresie a informat¸iei. Algoritmul Huffman este folosit aproape de orice algoritm de compresie, ˆıns˘a de regul˘a nu direct asupra octet¸ilor din datele de comprimat. Algoritmii de compresie utilizat¸i ˆın practic˘a se folosesc ¸si de dependent¸ele ˆıntre octet¸ii succesivi. Utilizarea oric˘arui cod presupune c˘a receptorul cunoa¸ste codul folosit de emit¸˘ator. Transmiterea separat˘a a codului c˘atre receptor risc˘a s˘a contrabalanseze cˆa¸stigul obt¸inut prin codare optimal˘a. Metodele adaptative presupun c˘a emit¸a˘torul ˆıncepe emisia cu un cod standard, dup˘a care ˆıl modific˘a pentru a-l optimiza conform frecvent¸elor observate ˆın date. Dac˘a algoritmul de generare a codului este fixat ¸si codul folosit la un moment dat depinde doar de datele trimise (codate) deja, atunci receptorul poate recalcula codul folosit de emit¸a˘tor (folosind acela¸si algoritm ca ¸si emit¸a˘torul). De notat c˘a nici un cod nu poate folosi mai put¸ini bit¸i pentru codare decˆat cantitatea de informat¸ie transmis˘a. ˆIn lipsa redundant¸ei, nu e posibil˘a compresia. Ca o consecint¸˘a, nici un program de compresie nu poate comprima un ¸sir aleator de octet¸i.

26

4.3

Capitolul 4. Codarea informat ¸ iei

Coduri detectoare ¸si corectoare de erori

Detect¸ia erorilor const˘a ˆın a face receptorul s˘a-¸si dea seama ˆın anumite condit¸ii dac˘a au avut loc erori la transmisie (receptorul va cere probabil retransmiterea informat¸iei ˆın acest caz). Corectarea erorilor const˘a ˆıntr-un mecanism care permite receptorului ˆın anumite condit¸ii s˘a reconstituie mesajul trimis de emit¸˘ator, chiar dac˘a ceea ce a recept¸ionat este diferit din cauza erorilor. ˆIn general, nu pot fi detectate sau corectate toate erorile posibile. ˆIn practic˘a se presupune un anumit num˘ar maxim de erori ce pot afecta un bloc de date, ¸si schemele permit detectarea oric˘arei astfel de configurat¸ii de erori. Dac˘a erorile se produc ˆın num˘ar mai mare, e posibil s˘a scape nedetectate, sau corectarea s˘a funct¸ioneze gre¸sit. Presupunem ˆın cele ce urmeaz˘a c˘a alfabetul cananului este S = {0, 1} Erorile pot fi: • erori individuale care schimb˘a valoarea unui bit din 0 ˆın 1 sau reciproc; • rafale de erori care schimb˘a o parte dintr-un ¸sir de bitˆı (nu neap˘arat tot¸i). Lungimea rafalei este num˘arul de bit¸i dintre primul ¸si ultimul bit modificat; • erori de sincronizare care determin˘a pierderea unui bit sau introducerea unui bit, ˆımpreun˘a cu decalarea corespunz˘atoare a bit¸ilor urm˘atori. Mai multe erori pot afecta acels˘ai bloc de bit¸i. Nu ne vom ocupa ˆın cele ce urmeaz˘a de erorile de sincronizare. Presupunem cuvinte de cod de lungime n bit¸i. Mult¸imea cuvintelor de cod este W ⊆ V = {0, 1}n . Pentru a putea detecta erorile, trebuie ca eroarea s˘a nu schimbe un cuvˆant de cod ˆın alt cuvˆant de cod. ci s˘a schimbe cuvˆantul de cod ˆıntr-un cuvˆant invalid. P Punem d(v1 , v2 ) = ni=1 |v1i − v2i | adic˘a distant¸a ˆıntre dou˘a cuvinte este num˘arul de erori individuale necesare pentru a schimba primul cuvˆant ˆın al doilea. Punem dmin (W ) = min d(v1 , v2 . v1 ,v2 ∈W,v1 6=v2

Un cod este capabil s˘a detecteze k erori individuale dac˘a dmin ≥ k + 1. Un cod este capabil s˘a corecteze k erori individuale dac˘a dmin ≥ 2k + 1. Coduri polinomiale F2 = ({0, 1}, ⊕, ·) este corp (⊕ este operat¸ia sau exclusiv, iar · este operat¸ia ¸si). Unui cuvˆant din V = {0, 1}n ˆı se asociaz˘a poliniomul (de grad cel mult n−1) v1 ·X n−1 ⊕v2 ·X n−2 ⊕· · ·⊕vn Acesta este un polinom peste F2 . Polinoamele peste orice corp p˘astreaz˘a multe din propriet˘a¸tile polinoamelor “obi¸snuite”, ˆın particular se poate defini la fel adunarea, sc˘aderea ¸si ˆınmult¸irea, ¸si are loc teorema ˆımp˘art¸irii cu rest. Pentru a defini W , se alege un a¸sa-numit polinom generator g(X). W se define¸ste ca mult¸imea polinoamelor (din V ) divizibile cu g(X). Dac˘a m = grad(G(X)), un cuvˆant de cod poart˘a n−m bit¸i de informat¸ie ¸si m bit¸i redundant¸i (de control).

4.3. Coduri detectoare ¸si corectoare de erori

27

Construct¸ia cuvˆantului de cod se face: v(X) = i(X) · X m ⊕ r(X), unde i(X) este polinomul corespunz˘ator informat¸iei utile, iar r(X) este restul ˆımp˘art¸irii lui i(X) · X m la g(X). Verificarea cuvˆantului recept¸ionat v 0 (X) se face prin ˆımp˘art¸ire la g(X) ¸si verificare dac˘a restul este 0. Informat¸ia util˘a este primii n − m bit¸i din v 0 (X). Dac˘a se dore¸ste corectarea erorilor, se observ˘a c˘a pozit¸iile erorilor nu depind decˆat de restul ˆımp˘art¸irii lui v 0 (X) la g(X).

28

Capitolul 4. Codarea informat ¸ iei

29

Capitolul 5 Nivelul leg˘ aturii de date

30

˘ turii de date Capitolul 5. Nivelul lega

31

Capitolul 6 Nivelul retea ¸si nivelul transport Ret¸ele: • comutare de circuite • comutare de pachete Ret¸ele cu comutare de pachete: • ret¸ele cu dirijare independent˘a a pachetelor • ret¸ele cu circuite virtuale

6.1

Algoritmi de dirijare Criterii:

• numar de noduri intermediare (hopuri) • distanta (geografica) • cost • ˆınc˘arcare Tehnici de calcul a tabelelor de dirijare • informare complet˘a privitoare la legaturile existente • tabele de distant¸e (v. pb. num˘ar˘arii la infinit) • dirijarea pentru multicast — arbori de acoperire minimi • dirijare ierarhic˘a • inundare

32

6.2

Capitolul 6. Nivelul retea ¸si nivelul transport

Controlul congestiei

• aruncarea pachetelor — cele mai vechi sau cele mai noi? • limitarea traficului: galeata gaurita, galeata cu jeton • semnalizarea ˆınc˘arc˘arii

6.3

Protocolul IP ¸si protocoalele auxiliare Antetul IP:

• adresa surs˘a ¸si destinat¸ie — cu prefix de ret¸ea • timp de viat¸˘a (num˘ar de salturi) • optiuni de inregistrare a salturilor (pentru traceroute) • protocolul de nivel superior (TCP, UDP, ICMP) Forma tabelelor de dirijare statice O adres˘a IP se asociaz˘a unei interfet¸e de ret¸ea Tabela de dirijare are ˆınregistr˘ari de forma (IP, masca, ruta) Rezolvarea adresei — ARP Scop: gasirea adresei fizice corespunz˘atoare unei adrese IP. Modalitate: se trimite un pachet broadcast in ret¸eaua Ethernet. ICMP Scop: diagnostic ¸si informare legat de rute. Pachere ICMP mai des utilizate: • cerere ecou, r˘aspuns ecou; • informare e¸sec dirijare • redirectare (forma extrema de corectare a tabelelor de dirijare) RARP, BOOTP, DHCP Scop: informare cu privire la propria adres˘a IP.

6.4

Nivelul transport

Rol: s˘a fac˘a adaptarea de la primitivele de comunicat¸ie prezentate aplicat¸iei la posibilit˘a¸tile ret¸elei. Problema: conexiune sigur˘a peste ret¸ea bazat˘a pe dirijare independent˘a a pachetelor. Solut¸ia (TCP): se numeroteaz˘a pachetele (octet¸ii, ˆın TCP), ¸si se confirm˘a independent fiecare num˘ar de pachet. Numerele de secvent¸a˘ sunt independente pentru cele dou˘a sensuri. Probleme suplimentare:

6.5. Ret ¸ ele eterogene ¸si ret ¸ ele private

• ˆınchiderea ¸si redeschiderea conexiunii • c˘aderea unuia din capete, ¸si uitarea numrelor de secvent¸˘a folosite

6.5

Ret¸ele eterogene ¸si ret¸ele private

• tunelarea • translat¸ia adreselor

6.6

Ret¸ele mobile

• redirectarea cu agent¸i locali ¸si agent¸i pentru straini

33

34

Capitolul 6. Nivelul retea ¸si nivelul transport

35

Capitolul 7 Metode ¸si protocoale criptografice 7.1

Deziderate

confident¸ialitate un mesaj s˘a nu poat˘a fi ˆınt¸eles decˆat de c˘atre destinatarul dorit; integritatea mesajelor destinatarul unui mesaj s˘a poat˘a verifica dac˘a mesajul este identic cu cel emis de emit¸˘atorr (c˘a nu a fost modificat pe traseu); autentificarea sursei destinatarul s˘a poat˘a verifica identitatea emit¸a˘torului unui mesaj; nerepudiabilitate emit¸a˘torul unui mesaj s˘a nu poat˘a nega ulterior emiterea unui mesaj (destinatarul s˘a poat˘a proba ˆın justit¸ie faptul c˘a emit¸˘atorul a emis un anumit mesaj). Note: 1. Verificarea integrit˘a¸tii ¸si autentificarea au sens doar ˆımpreun˘a. 2. Nerepudiabilitatea nu are sens f˘ar˘a verificarea integrit˘a¸tii ¸si autentificarea sursei.

7.2 7.2.1

Asigurarea confident¸ialit¸˘ a¸tii Criptografia simetric˘ a

Este cifrarea clasic˘a, ˆın care un mesaj dat, numit text clar (eng: plaintext), este transformat ˆıntr-un a¸sa-numit text cifrat (eng:ciphertext), astfel ˆıncˆat numai cineva care cunoa¸ste un anumit secret s˘a poat˘a reconstitui textul clar avˆand la dispozit¸ie doar textul cifrat. ˆIn general, algoritmii folosit¸i la cifrare ¸si la descifrare sunt presupu¸si cunoscut¸i de toat˘a lumea; secretul este un parametru al algoritmului, numit cheie (eng: key).

36

Capitolul 7. Metode ¸si protocoale criptografice

Not˘ a: Ideea este c˘a elaborarea ¸si implementarea unui algoritm nou cere un efort intens ¸si implic˘a mai multe persoane; de aceea e greu de p˘astrat secretul ¸si e ¸si mai greu de schimbat algoritmul oridecˆ ateori el devine cunoscut din afar˘a. ˆ In plus, publicˆand algoritmul, exist˘a ¸sanse mari ca, dac˘a acesta este vulnerabil, s˘ a afl˘am de la cineva care dore¸ste doar gloria ¸si eventual banii unei recompense, nu secretele p˘azite de algoritm. Cifrarea se scrie m = ck (p), unde p este textul clar, m este textul cifrat, k este cheia, iar c este funct¸ia (algoritmul) de cifrare. Descifrarea se scrie p = dk (m). Pentru ca descifrarea s˘a fie posibil˘a, trebuie ca dk (ck (p)) = p, ∀p, ceea ce implic˘a cerint¸a ca ck s˘a fie injectiv˘a. ˆ criptografia simetric˘a, adesea ck este bijectiv˘ Not˘ a: In a (atunci ck ¸si dk sunt una inversa celeilalte) ¸si dk este posibil de folosit pentru cifrare ˆın locul lui ck . Atacuri posibile: atac cu text cifrat: intrusul dispune de textul cifrat ¸si dore¸ste obt¸inerea textului clar corespunz˘ator; atac cu text clar cunoscut: intrusul dispune de perechi (pi , mi ) de text clar ¸si textul cifrat corespunz˘ator, plus un text cifrat m 6= mi pentru care dore¸ste obt¸inerea textului clar corespunz˘ator; atac cu text clar ales: ca ¸si ˆın cazul precedent, dar ˆın plus intrusul poate alege pi . ˆIn general, un sistem criptografic sigur trebuie s˘a reziste la atac cu text clar ales. Ca o consecint¸a˘, funct¸ia de cifrare, v˘azut˘a ca fiind parametrat˘a cu textul clar ¸si avˆand ca argument cheia, trebuie s˘a fie dificil inversabil˘a (eng: one-way), adic˘a a g˘asi cheia cunoscˆand textul clar dat ¸si textul cifrat rezultat s˘a necesite cautare aproape exhaustiv˘a ˆın spat¸iul cheilor. Exist˘a ¸si protocoale care prev˘ad explicit chei de unic˘a folosint¸a˘ (cheia se schimb˘a la fiecare mesaj); la astfel de protocoale atacul cu text clar cunoscut este imposibil. Un astfel de sistem este cifrarea cu cheie acoperitoare: cheia este un ¸sir aleator de bit¸i de lungime egal˘a cu a mesajului, iar cifrarea este operat¸ia xor ˆıntre fiecare bit din mesaj ¸si bitul corespunz˘ator din cheie. Un argument probabilistic simplu arat˘a c˘a cunoa¸sterea textului cifrat nu aduce nici o informat¸ie asupra textului clar. Dezavantajul metodei este c˘a cheia este lung˘a ¸si nu poate fi refolosit˘a (ˆın cazul refolosirii cheii, mecanismul de cifrare este u¸sor de spart).

7.2.2

Utilizarea practic˘ a a cifrurilor bloc

Unele din metodele de cifrare pot cifra doar blocuri de lungime fixa (de ex. 64, 128 sau 256 de bit¸i). Exist˘a cˆateva metode standard de utilizare a unui astfel de cifru pentru a cifra o cantitate arbitrar˘a de text: ECB — Electronic Code Book: Textul clar se ˆımparte ˆın blocuri de lungime egal˘a cu blocul folosit de algoritmul de cifrare. Ultimul bloc se completeaz˘a cu bit¸i aleatori. Fiecare bloc se cifreaz˘a apoi independent de celelalte. Este metoda cea mai simpl˘a, dar are cˆateva dezavantaje:

˘t 7.2. Asigurarea confident ¸ ialit ¸a ¸ ii

37

• pentru o cheie fixat˘a, un fragment de text clar ˆıncepˆand de la o pozit¸ie multiplu de lungimea blocului se cifreaz˘a totdeauna la fel; acest fapt poate permite atacuri cu text clar cunoscut dac˘a exist˘a fragmente de text clar care se repet˘a frecvent; • un intrus care permut˘a blocurile de text cifrat va obt¸ine permutarea blocurilor corespunz˘atoare de text clar, chiar dac˘a nu ˆıntelege nimic din textul cifrat. De¸si este citat frecvent, acesta nu este propriu-zis un dezavantaj al metodei ECB: un algoritm de cifrare are ca scop p˘astrarea confident¸ialit˘a¸tii mesajului, nu controlul integrit˘ a¸tii. CBC — Cipher Block Chaining: Ca ¸si la ECB, textul clar se ˆımparte ˆın blocuri ¸si ultimul bloc se completeaz˘a cu bit¸i aleatori. ˆIn plus, se alege un ¸sir de bit¸i aleatori de lungimea unui bloc; acesta se nume¸ste vector de init¸ializare. Vectorul de init¸ializare se transmite separat sau se stabile¸ste dup˘a o regul˘a oarecare. Se efectueaz˘a xor pe bit¸i ˆıntre vectorul de init¸ializare ¸si primul bloc de text clar; rezultatul se cifreaz˘a ¸si se trimite. Apoi, se face xor ˆıntre fiecare bloc de text clar ¸si blocul precedent de text cifrat, ¸si rezultatul se cifreaz˘a ¸si se transmite destinatarului.

7.2.3

Numere aleatoare

Un sistem criptografic utilizeaz˘a numere aleatoare, ˆıntre altele pentru generarea cheilor ¸si pentru protocoale de autentificare de tip provocare-r˘aspuns. Spre deosebire de generatoarele de numere aleatoare pentru alte scopuri, generatoarele de numere aleatoare pentru scopuri criptografice este necesar s˘a fie imprevizibile, chiar pentru cineva care cunoa¸ste metoda de generare ¸si chiar o parte din numerele generate. Metode folosite: Generatoare fizice: utilizeaz˘a un fenomen fizic destul de aleator (este similar arunc˘arii unui zar). Exemple: zgomotul termic pe un rezistor sau pe un semiconductor, dezintegrarea unei substant¸e radioactive, curent¸ii de aer format¸i ˆın interiorul carcasei unui harddisc. ˆIn lipsa unui generator fizic “adev˘arat”, se utilizeaz˘a act¸iunile utilizatorilor asupra tastaturii sau mouse-ului, ˆınc˘arcarea sistemului, sosirea pachetelor pe interfat¸a de ret¸ea. Sunt necesare diverse prelucr˘ari pentru a putea obt¸ine din aceste surse un ¸sir de numere aleatoare de calitate; de asemenea, trebuie ca cel put¸in o parte din sursele enumerate mai sus s˘a nu fie controlate sau observate de inamic. Numere pseudoaleatoare: pentru alte aplicat¸ii decˆat cele criptografice, se genereaz˘a numere pseudo-aleatoare dup˘a urm˘atoarea schem˘a: exist˘a o variabil˘a s care ¸tine starea intern˘a a generatorului. Cˆand aplicat¸ia are nevoie de un num˘ar aleator, num˘arul aleator este extras din starea intern˘a: rt = f (st ); de obicei se extrag o parte din bit¸i. Apoi, starea intern˘a este actualizat˘a cu ajutorul unei funct¸ii care “amestec˘a” bine starea intern˘a: st+1 = g(st ). Un astfel de generator se spune c˘a este generator de numere pseudoaleatoare. Pentru a folosi un generator de numere pseudoaleatoare ˆın scopuri criptgrafice este necesar s˘a fie indeplinite mai multe condit¸ii:

38

Capitolul 7. Metode ¸si protocoale criptografice

1. Starea init¸ial˘a (eng: seed) trebuie generat˘a cu un generator fizic, altfel intreg ¸sirul este previzibil; 2. Starea intern˘a trebuie s˘a aib˘a un num˘ar suficient de mare de bit¸i pentru a rezista unui atac prin fort¸a˘ brut˘a; 3. Funct¸iile f ¸si g s˘a fie dificil inversabile, altfel cineva care ar obt¸ine o parte din numerele din ¸sir ar putea fi capabil s˘a afle restul ¸sirului. De obicei este necesar de asemenea ca cineva care reu¸se¸ste s˘a obt¸in˘a (de exemplu, dintrun core dump) starea intern˘a, s˘a nu fie capabil s˘a calculeze numerele ce au fost generat¸e pˆan˘a ˆın acel moment.

7.2.4

Criptografie asimetric˘ a (cu cheie public˘ a) Criptografia asimetric˘a presupune urm˘atoarele:

• Cifrarea ¸si descifrarea nu folosesc aceea¸si cheie, ci folosesc chei diferite, ˆın pereche. Vom avea m = ckc (p) ¸si p = dkd (m). • Din cheia folosit˘a la descifrare se poate genera u¸sor cheia corespunz˘atoare pentru cifrare; transformarea invers˘a este ˆıns˘a foarte dificil˘a: kc = f (kd ), f bijectiv˘a, ¸si a calcula x = f −1 (y) implic˘a a verifica pentru aproape toate valorile posibile pentru x dac˘a f (x) = y. • G˘asirea lui p cunoscˆand doar m ¸si kc este la fel de dificil˘a ca ¸si g˘asirea lui kd cunoscˆand kc . ˆIn aceste condit¸ii, receptorul va genera o pereche kd , kc ¸si va putea face public˘a kc . Emit¸a˘torul poate cifra un mesaj folosind kc , ¸si numai posesorul lui kd ˆıl va putea descifra. De notat c˘a, dac˘a se dore¸ste comunicat¸ie bidirect¸ional˘a, este necesar˘a cˆate o pereche de chei (kc , kd ) pentru fiecare sens. Not˘ a: Algoritmii criptografici asimetrici sunt mult mai lent¸i decˆ at cei simetrici; din acest motiv, comunicat¸ia propriu-zis˘ a se cifreaz˘ a de obicei cu o metod˘ a simetric˘a, ¸si doar cheia de cifrare (sau alte obiecte mici, impuse de protocoale de autentificare) se cifreaz˘a folosind metode asimetrice.

7.3 7.3.1

Autentificarea originii ¸si controlul integrit˘ a¸tii Funct¸ii de dispersie criptografice

O funct¸ie de dispersie (eng: hash function) este ˆın general o funct¸ie h care asociaz˘a unui ¸sir de bit¸i m de o lungime oricˆate de mare, o valoare ˆıntreag˘a ˆıntrun interval de forma [0, 2n ) cu n fixat (sau echivalent, un ¸sir de bit¸i de lungime n); ˆın plus, se cere ca pentru sirurile care apar in problema unde se folose¸ste funct¸ia de dispersie, dou˘a ¸siruri distincte s˘a nu aib˘a aceea¸si valoare a funct¸iei de dispersie cu probabilitate semnificativ mai mare de 2−n . De la o funct¸ie de dispersie criptografic˘a se cere ˆın plus: 1. dˆandu-se h(m), s˘a fie dificil de reg˘asit m. Eventual, dificultatea s˘a se p˘astreze chiar ˆın cazul cunoa¸sterii unei p˘arti din m.

˘t 7.3. Autentificarea originii ¸si controlul integrita ¸ ii

39

2. dˆandu-se un ¸sir m, s˘a fie dificil de g˘asit un al doilea ¸sir, m0 6= m astfel ˆıncˆat h(m) = h(m0 ). 3. s˘a fie dificil de g˘asit m1 6= m2 cu h(m1 ) = h(m2 ). De remarcat c˘a cele trei condit¸ii sunt diferite, de¸si condit¸ia 3 o include pe 2. Exemple de funct¸ii: md5 (ie¸sire 128 bit¸i), sha1 (ie¸sire 160 bit¸i)

7.3.2

Autentificarea mesajelor

Pentru a putea trimite mesaje autentificate, trebuie ca fie emit¸a˘torul ¸si receptorul s˘a partajeze o cheie secret˘a k folosit˘a ˆıntr-un algoritm simetric, fie emit¸a˘torul s˘a aib˘a o cheie secret˘a kd a c˘arei cheie public˘a corespunz˘atoare kc s˘a o aib˘a receptorul. ˆIntr-o prezentare simplificat˘a, emiterea de mesaje autentificate merge pe una din schemele (m desemneaz˘a mesajul de trimis, h desemneaz˘a o funct¸ie de dispersie criptografic˘a: • Emit˘atorul trimite (m, s), unde s = ck (h(m)); receptorul prime¸ste (m, s) ¸si verific˘a dac˘a s = ck (h(m)). Mai adesea, se folose¸ste o varianta ˆın care funct¸ia de dispersie criptografic˘a ˆınglobeaz˘a ¸si cifrarea; o asemenea funct¸ie se nume¸ste cod de autentificare (eng: hash message authentication code — HMAC). ˆIn varianta aceasta, emit¸˘atorul calculeaz˘a s = hk (m), unde hk este funct¸ia cod de autentificare cu cheia k; el trimite (m, s). Receptorul prime¸ste (m, s) ¸si verific˘a dac˘a s = hk (m). • Presupunˆand c˘a funct¸ia de cifrare a unui sistem asimetric este ¸si surjectiv˘a (pe o multime cunoscut˘a), emit¸a˘torul calculez˘a s = dkd (h(m)) ¸si trimite (m, s). Receptorul prime¸ste (m, s) ¸si verific˘a dac˘a ckc (s) = h(m).

40

Index A AM, Vezi modulat¸ie ˆın amplitudine B band˘a lateral˘a, 17 F FM, Vezi modulat¸ie, ˆın frecvent¸a˘ frecvent¸a purt˘atoare, 16–17 M modulat¸ie ˆın amplitudine, 16 ˆın faz˘a, 17 ˆın frecvent¸a˘, 17 P purt˘atoare, Vezi frecvent¸a, purt˘atoare