Sisteme de programepentru timp realUniversitatea Politehnica din Bucuresti2005-2006Adina Magda Floreahttp://turing.cs.pub.ro/sptr_06

Curs Nr. 3Criptologie si criptosistemeNumere aleatoareOperatii aritmetice cu numere mariCriptologie generalitatiCriptosisteme conventionaleCriptosisteme publiceStandarde actuale*

1. Numere aleatoare

Numar intreg/real aleator intr-un domeniu dat si cu o precizie fixata / Numar pseudoaleatorGenerator de numere aleatoare - o multime de stari S, o functie f:S S si o stare initiala s0 - samanta.Starile generatorului evolueaza dupa relatia:si=f(si-1), cu i =1,2,...g:S (0,1)Perioada unui generator de numere aleatoare este cel mai mic intreg pozitiv p a.i.si+p=si , i > p 0*

Sunt numere aleatoare?TestulN numere intregi in intervalul [ 0, r ), frecventa fiecarui numar din interval fiind fi ( i = 0, r-1 )

Distributii uniforme (aceeasi probabilitate)*

1.1 Metoda congruent multiplicativa f (si+1) = ( b*si + c ) mod mg ( si ) = si/m s0 - samanta , b, c < m, pozitivif(si) [ 0, m-1 ]Cum se aleg m, s0 si b ?Fiecare valoare este mai mica decat cel mai mare intreg, dar prima operatie a*b+1 duce la overflowCum se elimina overflow-ul?

*

Cum se elimina overflow-ul?Reprezentare pe 32 de biti - intereseaza pentru rezultat numai ultimii 8 digiti.a si b se reprezinta ca doua polinoame in fct. de x.a = 1234567b = 31415821

grad(p) N-1grad(q) N-1grad(p*q) 2N-2p = 104 * p1 + p0q = 104 * q1 + q0p * q = ( 104 *p1 + p0 ) ( 104 q1 + q0 ) =108 * p1 * q1 + 104 * ( p1 * q0 + p0 * q1 ) + p0 * q0. *

Generare numere aleatoare#define m 100000000#define m1 10000#define b 31415821long int a =1234567;long int mult( long int p , long int q ){long int p0, p1, q0, q1;p1 = p / m; p0 = p % m1; q1 = q / m1; q0 = q % m1;return ((p0 * q1 + p1 * q0) % m1)*m1 + p0* q0)% m ;}long int random( ){a = ( mult( a, b ) + 1 ) % m ;return a;}// nr. aleatoare [0,m-1]// echiv rand() RAND_MAX=m-1*

1.2 Metoda congruent-aditivaRegistru de deplasare cu feed-backAdunare

11110111, 0011, 0001, 1000, ... Pt. n biti se pot obtine secvente de max. 2n-1 numere distincten = 31 sunt bune pozitiile 0 si una din pozitiile 4, 7, 8, 14, 19, 25, 26 sau 29. *

Metoda congruent-aditivaAdunare

Considerand un sir de numere aleatoare a0 ak, se obtin numere aleatoare in continuare in [ 0, m-1 ], astfel a [ k ] = ( a [ k-b] + a [ k-c ] ) % m ( b < c )min 2c-1 numere distincteValori b = 31, c = 55 a coada circulara

bc*

2 Operatii aritmetice cu numere mari ReprezentareIntregul 0120200103110001200004012314 cu N = 28 digiti se reprezinta prin p(10) unde p este polinomul

Calcul eficient al inmultirii a doua polinoame p(x) si q(x) de grad N-1Produs de grad 2N-2 cu 2N-1 termeniProdus calculat direct N2 inmultiriDivide and conquerN par => 2 polinoame de grad N/2

*

Utilizare Divide and conquer p( x ) = p0 + p1x + ... + pN-1xN-1pi( x ) = p0 + p1 + ... +pN/2-1xN/2-1ps( x ) = pN/2 + ... + pN-1xN/2-1

Pentru a calcula p ( x ) * q ( x ) sunt necesare numai 3 inmultiri

Doua polinoame de grad N pot fi inmultite folosind inmultiri

*

3 Criptologie - generalitatiCriptografia - Proiectarea sistemelor de comunicatie secretaCriptoanaliza - Studiul metodelor de intelegere a comunicatiilor secrete Doua scopuri de baza

Doua tipuri de criptosisteme:- conventionale (criptosisteme simetrice)- publice (criptosisteme asimetrice)*

4 Criptosisteme conventionale*

Criptosisteme conventionaleMetode simpleCifrul lui Cezar a N-a litera din alfabet se inlocuieste cu litera (N+k) din alfabet, unde k este constant (Cezar lua k = 3)Substitutie simpla - Matrice cu 26 linii si 2 coloane care defineste substitutia literelor Cifrul Vigenere: se utilizeaza o cheie pentru a determina valorile lui k care trebuie adaugate fiecarei litere.Fie cheia c1c2...cm.j 0pentru fiecare litera li din mesaj executali din mesaj are indexul p in alfabetj ( j+1 ) mod malege cj din cheiefie k indexul lui cj in alfabetinlocuieste li cu litera din alfabet de index ( k + p )sfarsit*

Criptosisteme conventionaleCifrul Vigenere se poate combina cu substitutia simplaDaca cheie mesaj Cifrul Vernam (one time pad)Masini de criptare/decriptare - primeste un numar de chei adevarate, numite criptovariabile, care sunt utilizate pentru a genera chei lungiGenerarea pseudocheii din criptovariabile este asemanatoare cu metoda congruent aditiva (cu registru) de la numere aleatoarePericolDificultati ale sistemelor conventionale*

5 Criptosisteme publiceIdee: fiecare utilizator are o cheie publica P care poate fi cunoscuta de oricine si o cheie secreta S cunoscuta numai de el. Mesaj M E - cheia publica P a receptorului - C = P ( M ) R - cheia secreta S - M = S ( C )

*

Criptosisteme publiceConditii S ( P ( M ) ) = M pentru fiecare mesaj M Toate perechile ( S, P ) sa fie distincte Deducerea lui S din P sa fie la fel de dificila ca si decriptarea lui C Atat S cat si P sunt usor de calculat *

6. Standarde actualeConventionaleDES Data Encryption StandardAES Advanced Encryption StandardPubliceRSA - Ron Rivest, Adi Shamir, and Leonard Adelman DSA Digital Signature AlgorithmDSS Digital Signature StandardNIST (National Institute of Standards and Technology, USA) lucreaza la Federal Public Key Infrastructure va sustine semnaturile digitale

7 Criptosistemul public RSA Cheia de incriptare P este o pereche de intregi ( N, p ) cu p publicCheia de decriptare S este o pereche de intregi ( N, s ) unde s este secret.Aceste numere trebuie sa fie foarte mari, in mod tipic N - 200 digiti iar p si s aproximativ 100 digiti

Metoda de criptare/decriptare1. Se imparte mesajul in k grupri de biti M1Mk2. Se incripteaza mesajul astfel: C = P(M) = C1Ckunde Ci = (Mpi) mod N R3. Receptorul decripteaza mesajul M = S(C) = M1...Mk unde Mi = (Csi) mod N

*

Modul de alegere a p si s 1.Se genereaza trei numere aleatoare prime mari ( 100 digiti ) x, y, z.2.Cel mai mare dintre acestea este ales ca valoare a lui s.3.Fie celelalte doua numere x si y.4.N = x * y5.p se alege astfel incat p * s mod ( x-1 ) * ( y-1 ) = 1.

Se poate demonstra ca, pt. aceste alegeri,

Este sigur?*

Cum se genereaza un nr. prim f. mare? Se genereaza un nr. aleator f. mare + se testeaza daca este primFie w numarul pentru care se testeaza daca este prim.1. i 1, n 502. Determina a si m a.i. w=1+2am , unde m este impar si 2 este cea mai mare putere a lui 2 care divide w-1.3. Genereaza un numar aleator b ( 1, w )4. j 0, z bm mod wdaca (( j=0 ) si ( z=1 )) sau ( z=w-1 )atunci executa pasul 96.daca ( j>0 ) si ( z=1 ) atunci executa pasul 8*

Cum se genereaza un nr. prim f. mare? Se genereaza un nr. aleator f. mare + se testeaza daca este prim

7. j j + 1daca j

Discutie criptosisteme publice Toate abordarile se bazeaza pe calcule NPProblema: daca se inlocuieste p (cu s asociat) cu p (si s asociat)Cheile publice certificate de cheie (digitale) prefixate cu un certificat de semnatura; contin:User key IDData la care a fost creata cheiaCheiaCheia secreta cheie incriptata cu o parola

*

Certificate digitale Atacuri asupra sistemelor de cu chie publice: afla cheia secretaManagement sigurManagementul de chei implicaGenererarea cheilorCautarea cheilorDistribuirea cheilorIncredere in cheile publice*

Certificate digitale Certificate digitale: verifica daca o cheie publica apartine unui individUn certificat contine:Un nume si cheia publicaData de expirareNumele autoritatii de certificareNumar de serieSemnatura digitala a autoritatii de certificareReceptorul verifica un certificat folosind cheia publica a autoritatii de certificareSe autentifica astfel semnaturile digitale ale mesajelor *

Certificate digitale Lungimea cheii 1024 bits.512 bits nesigur2048 , 4096 bits. 4096-bits Inpractica, 512-bit key.

NSA Cu cat mai mult timp, cu atat cheia mai lunga *

8. DES Data Encryption StandardData Encryption Standard (DES) adoptat ca standard in USA in 1977.Foloseste o cheie de 56-bits insuficientVarianta Triple-DES (TDES or 3DES) foloseste o cheie mai lungaAdvanced Encryption Standard (AES) se crede ca va fi mai bun ca DES (si 3DES) *

DES Mod de functionareAlgoritm pt. criptarea si decriptarea blocurilor de date de 64 de biti pe baza unei chei de 56 de biti.Criptarea si decriptarea utilizeaza aceeasi cheie k decriptarea este reversul criptariiDES are un bloc cu dimensiunea de 64 biti codifica 64 de biti de data odataIncripteaza mesajul folosind o cheie de 56 de bitiInitial proiectat pt incriptare hardwareSigur pt scopuri comercialeUn calculator foarte puternic poate sparge DES prin forta bruta*

DES Mod de functionareAlgoritm pt. criptarea si decriptarea blocurilor de date de 64 de biti pe baza unei chei de 64 de biti.

Blocul de criptat:1) Permutare initiala IP2) Calcul complex care depinde de cheie = o functie f - functia de criptare, si o functie KS - planificarea cheii3) Permutare inversa a cele initiale IP-1*

DES Mod de functionare*

DES Mod de functionare2) Calcul16 iteratii; functia f opereaza asupra a 2 blocuri: unul de 32 biti si unul de 48 de biti un bloc de 32 de bitiBlocul de intrare = 64 biti = L (32) R (32)K un bloc de 48 biti ales din cheia KEY de 56 bitiLa fiecare iteratie, blocul K este diferitKn = KS(n,KEY)n[1,16], Kn functie care permuta o selectie de biti din KEYPt un bloc Ln-1Rn-1, iesirea LnRn a unei iteratii este:Ln = Rn-1Rn = Ln-1 f(Rn-1,Kn)*

DES AtacCheia: 56 biti de incercat 72,057,594,037,927,936 chei posibile

1998 - Electronic Frontier Foundation (EFF)Au construit un calculator dedicat care poate decripta un mesaj care incearca toate cheile posibile in mai putin de 3 zile.Cost calculator: < $250,000 Cauta 88 miliarde chei/sec*

DES Modele de operareECB Electronic Codebook DES directCBC Cipher Block Chaining DES extins care inlantuie blocuri de text incifratCFB Cipher Feedback utilizeaza text incriptat anterior ca intrare pt. DES si genereaza iesiri pseudoaleatoare care sunt combinate cu textul neincriptat pentru a produce text incriptatTDEA Triple Data Encryption Standard

*

Triple DESTriple-DES dupa ce s-a aratat vulnerabilitatea DESFoloseste 3 chei DES de 56 biti lungime cheie totala 168 bitiIncriptare folosind DES cu prima cheie de 56 bitiIncriptare folosind DES cu a doua cheie de 56 bitiIncriptare folosind DES cu a treia cheie de 56 bitiDecriptarea la fel, in sens invers*

RSA si DES pot fi folosite impreunaDES viteza mare, RSA management convenabilUn mesaj incriptat cu DESEmitatorul utilizeaza cheia publica (RSA) a receptorului pt incriptarea cheii DESMesajul DES incriptat + cheia DES incriptata cu RSA sunt trimise receptorului intr-un plic digital RSA.Cand plicul este primit de receptor, receptorul decripteaza cheia DES cu cheia lui RSA privata apoi utilizeaza cheia DES pt decriptare mesaj.*

*

9 PGP (Phil Zimmermann, 1991)PGP combina avantajele sistemelor publice si conventionaleCriptosistem hibridIntai comprima textulDe ce?Mai scurt, mai repede de transmisCreste securitatea prin eliminarea sabloanelor(fisierele care sunt prea scurte sau care nu se comprima bine nu sunt comprimate)*

PGP creaza o cheie de sesiune, o cheie secreta one-time-only. Cheia numar aleator generat pe baza msicarilor mouse si taste apasateSe foloseste cheia intr-un sistem clasic (rapid) -ciphertext. Cheia de sesiune se incripteaza cu cheia publica a receptoruluiSe transmite cheia de sesiune criptata + ciphertext*

Decriptarea - invers Criptarea conventionala cam de 1, 000 de ori mai rapida decat cea publicaAvantaje combinareO cheie conventionala de 80 biti este echivalenta ca putere cu o cheie publica de 1024 bitiO cheie conventionala de 128 biti este echivalenta ca putere cu o cheie publica de 3000 biti*

Certificat digital PGPUn certificat PGP: The PGP version number this identifies which version of PGP was used to create the key associated with the certificate. The certificate holder's public key the public portion of your key pair, together with the algorithm of the key: RSA, DH (Diffie-Hellman), or DSA (Digital Signature Algorithm). The certificate holder's information this consists of "identity" information about the user, such as his or her name, user ID, photograph, and so on.

*

Certificat digital PGPThe digital signature of the certificate owner also called a self-signature, this is the signature using the corresponding private key of the public key associated with the certificate. The certificate's validity period the certificate's start date/ time and expiration date/ time; indicates when the certificate will expire. The preferred symmetric encryption algorithmfor the key indicates the encryption algorithm to which the certificate owner prefers to have information encrypted. The supported algorithms are CAST, IDEA or Triple-DES.

*