a. Cheia K este de aceeasi dimensiune cu mesajul criptat. Daca lungimea lui C este 20 caractere hexa, atunci are 80 de biti. Deci si cheia K este pe 80 de biti cu care s-ar face xor pe mesajul C pentru a obtine mesajul decriptat original.
b. Daca pentru criptare cheia folosita este chiar M, atunci M xor M = 000...000 (de 80 de ori). Deci, C' = 000...0000 indiferent de M. Mesajul nu se poate decripta deoarece M poate avea orice valoare posibila pe 80 de biti.
Mesjaul m este spart in 3 blocuri, (m1,m2,m3).
Initial, ctr este o valoare fixata aleatoare de aceeasi dimensiune cu un m1 (daca m este de 64 de biti, atunci si ctr este de 64 de biti, i = 1, 2 sau 3). ctr + i este tot pe 64 de biti.
a.
c = (c1,c2,c3)ci = Fk(mi xor (ctr + i)), undei = 1..3c = concatenarea Fk(mi xor (ctr + i) for i = 1..3
b. Formula de decriptare este mi = (Fk^(-1)(ci)) xor (ctr + i)
Schema de decriptare:
Nota: Este necesar ca Fk sa fie inversabila.
c. Daca s-ar adauga 0 peste tot in ultimul bloc astfel incat sa incapa, atunci in mesajul decriptat ar aparea si acele 0 la sfarsit.
Se incalca principiul de integritate si formula Dec(k, Enc(k, m)) = m datorita 0-urilor in plus la finalul mesajului decriptat.
In cazul in care se face padding oricum, se intampla acelasi lucru, desi acest caz poate fi prevenit prin adaugarea unui pas la decriptare ce scoate acel bloc plin de 0 pus in plus, dar asta doar in cazul in care stim ca 100% dintre mesaje au un bloc plin de 0 in plus (ceea ce ar fi reduntant).
d. CCA = Chosen-Ciphertext Attack:
- Adversarul A poate sa obtina criptarea unor mesaje alese de el
- Adversarul A poate sa obtina decriptarea unor texte alese de el
Safe/Sigur: nimeni nu poate deduce nicio functie(textul clar) (nimic despre textul clar) pornind de la textul criptat. Daca afla, atunci sparge schema de securitate.
O schema de criptare este sigura daca niciun adversar (avand puterea specificata) nu poate sparge schema in modul specificat.
Securitate perfecta inseamna ca daca Oscar afla textul criptat, nu are niciun fel de informatie in plus decat daca nu l-ar fi aflat.
Schema de criptare perfect sigura: Pr[M=m | C=c] = Pr[M=m]
- Pr[M=m] = prob. ca Alice sa fi ales mesajul m
- **Pr[M=m | C=c] = prob. ca Alice sa fi ales m stiind c
- M = spatiul mesajelor, m in M
- C = spatiul mesajelor criptate, c in C
- Pr[C=c] > 0
Adica probabilitatea sa ghiceasca mesajul stiind mesajul criptat este aceeasi cu probabilitatea sa gaseasca mesajul direct.
Def: Schema de criptare (Enc, Dec) e perfect sigura daca:
- Pr[Enc(k, m0) = c) = Pr[Enc(k, m1) = c]
- len(m0) = len(m1)
Altfel spus: (Enc, Dec) peste (K, M, C) perfect daca:
- {Enc(k, m0)} = {Enc(k, m1)}
Schema de criptare sigura: Daca un inamic are timp polinomial n, probabilitatea sa atace cu succes este neglijabila
O schema de criptare este CCA-sigura daca pentru orice adversar PPT A exista o functie neglijabila negl astfel incat:
- Pr[Priv(n) = 1] <= 1/2 + negl(n)
- Priv(n) experimentul de indistinctibilitate in functie de (A, pi=(Enc, Dec)) conform cursului
Securitatea este impactata daca adversarul poate distinge intre criptarile a doua mesaje aleatoare.
In CCA, atacatorul este activ si poate rula atacuri in timp polinomial si poate interactiona cu un oracol de criptare si un oracol de decriptare.
Conform cursului, un sistem de criptare determinist nu poate fi CCA sigur. Schema data in problema este determinista atat timp cat stim valorile variabilelor generate (pseudo)aleator.
e. Conform standardului Advanced Encryption Standard, care permite lungimea blocului de 128 de biti, 48 de biti este prea putin si nu este destul de sigura (nici macar pentru Data Encryption Standard care permite 64 de biti).
Pe de alta parte, mai multi biti inseamna mai multa putere de procesare, deci se poate ca algoritmii de criptare/decriptare sa fie mai rapizi pentru 48 de biti decat pentru 128 sau 64.
a.
MD5: Message Digest 5, primeste o secventa de oricati biti si produce o secventa hash de 128 de biti.
Salt: Secventa aleatoare de n biti distincta pentru fiecare user. De pilda, in loc sa se faca MD5(password), se face MD5(salt||password).
MD5 nu este o modalitate de stocare sigura, deoarece este un algoritm foarte rapid, chiar daca are salt. Un GPU modern poate incerca miliarde de parole pe secunda pentru MD5 fara salt. Pentru MD5 cu salt, complexitatea se mareste, dar tot este nesigur.
b. G(x) = x*x mod x = 0, oricare ar fi x.
Deci G nu este PseudoRandom Generator
c. Schema pentru obtinerea mesajului criptat este:
Deci:
c = m xor PRG(k)c = m xor 000...000c = m
d. Diffie-Hellman = Un protocol de schimb de chei: 2 persoane pot genera o cheie comuna secreta printr-un canal public.
Versiunea simplificata a algoritmului est: Alice si Bob stabilesc public de comun acord o cheie generator g si un numar prim n. Alice si Bob genereaza fiecare in privat cate o cheie privata, a si b. Alice si Bob au amandoi acces la o functie comutativa neinversabila F(x,y) (spre exemplu, F(x,y) = x^y mod n)
- Alice calculeaza f(g, a) in privat si il trimite lui Bob
- Bob calculeaza f(g, b) in privat si il trimite lui Alice
- Valoarea cheii finale este
F(F(g, a), b) == F(F(g, b), a), adica(g^a)^b mod n == (g^b)^a mod n
Problema logaritmului discret se refera la aflarea lui x stiind ca g^x mod n = y stiind g, n si y.
Stim din standardele de criptare ca 2^128 este considerat sigur.
Daca numarul de posibilitati este n^65537 si n>=2, atunci sistemul este sigur si probabilitatea 1/n^65537 este neglijabila.
e. Protocolul de schimb de chei Diffie-Hellman este vulnerabil la atacuri man in the middle unde atacatorul poate impersona pe Alice cand comunica cu Bob, si pe Bob cand comunica cu Alice. Astfel, prin acest man-in-the-middle-atac, Eve poate obtine toata comunicarea dintre Alice si Bob.
Sistemul se poate securiza prin semnatura digitala. Alice are o cheie publica si o cheie privata care functioneaza in felul urmator: Alice semneaza ce ii trimite lui Bob folosind cheia privata, apoi cheia publica a lui Alice este folosita pentru a valida semnatura. Un fel de Pubk(Privk) = True | False.
f. MAC: Message Authentication Code
Alice si Bob stabilesc o cheie secreta k.
Alice ii trimite lui bob un mesaj m.
Functia MAC(k, m) intoarce un tag.
Alice trimite lui Bob (m, tag).
Functia Verify(tag) = True | False.
Mac(k, m) = hash(k || len(m)) xor hash(m)
Functia pare a fi de tipul HMAC.
Din punct de vedere al integritatii, AuthMAC este sigur, deoarece orice schimbare minora in mesaj sau tag este reflectata in verificare.
Hashul produs de functia MAC este de aceeasi dimensiune cu hashurile produse de functia h.
Functia hash este imuna la coliziuni, deci din punct de vedere al confidentialitatii, si AuthMAC este sigura.
g. Principiul lui Kerckhoffs: Un sistem de criptare trebuie sa fie sigur chiar daca totul este public in afara de cheie
- Un cifru trebuie sa fie practic indescifrabil, daca nu matematic indescifrabil
- Sunt de interesa mai mare schemele care nu pot fi sparte practic. Sunt sigure vs inamici eficienti. Probabilitatea sa fie sparte este foarte mica.
Principiul lui Kerckhoffs este incalcat de folosirea algoritmului MD5.
h. Principiile criptografiei sunt:
- Confidentialitate
- Integritate
- Disponibilitate
- Autenticitate
- Non-repudiere
Confidentialitatea este incalcata datorita folosirii algoritmului MD5 pentru stocarea parolelor.
Din moment ce Diffie-Hellman poate fi atacat cu un man-in-the-middle attack si poate intercepta si modifica mesajele, se incalca si principiul integritatii.
De asemenea, specificatiile nu spun nimic despre Disponibilitate. Schema este vulnerabila unui atac man-in-the-middle care blocheaza comunicarea.
RSA: Alice doua chei, una privata si una public (si functiile Dec in functie de cheia privata si Enc in functie de cheia publica), pentru un sistem de criptare asimetric.
Dec(Enc(m)) = m, deci decriptarea se face in functie de private key, iar criptarea in functie de public key. Astfel, oricine ii poate trimite lui Alice un mesaj criptat cu cheia lui Alice, fara sa poata fi decriptat de altcineva decat Alice.
Alternativ, cheia pentru Dec poate fi cea publica, iar Enc poate fi cea privata. Aceasta versiune asigura autenticitatea mesajului, deoarece mesajul nu putea fi criptat decat de catre cheia publica pentru Dec.
Putem aplica ambele metoda asupra aceluiasi mesaj trimis pentru a obtine si Autenticitate, si Confidentialitate.
Pentru RSA:
-
formula
m^e mod N = cpentru criptare. -
formula
c^d mod N = mpentru decriptare -
e si d sunt numere prime, deci valoarea e*d are un singur mod de a fi impartita in produsul a doua numere prime.
Extragerea factorizarii unui numar creste exponential cu dimensiunea numarului.
Fie functia Phi(N) ce produce numarul de valori mai mici decat N
a. Din curs, folosim formula x^e = y mod N
Deci formula devine x^65537 = y mod N
N in format decimal este 4371938152451122902660461215975791809483753001916739908168355461462976833703444868615518384718355588764264060739531813208377469311578324118012465910173154183806804966188707979888428392140877144558331726079378457832374697786903663087196339373421169943473228629444065911971716119514388130420831021490170432578299223459570483390623292610069168501924971423551359026067260051628963288291877508761732978077735341426523495721857662721535799339805097425181411858574451458902837841888009180430739111993640851992369629657106099405580519789364127952625159668668929543992041890621725441998315058822798569025119405224225281838296
Ultima cifra este 6, care este divizibila cu 2, ceea ce inseamna ca N nu este format din doua numere prime decat daca unul dintre ele este 2. Daca totusi il impartim pe N la 2, obtinem ca si acest numar este divizibil cu 2. Ceea ce inseamna, categoric, ca N nu este produsul a doua numere prime p si q.
b.
- y2 = x3 + 17x + 3 (mod 29)
- Verificare (8, 10)
- y2 = 512 + 136 + 3 (mod 29)
- 100 mod 29 = 651 mod 29
- 13 = 13 (Adevarat)
- Inversul punctului (8, 10)
- Este (8, -10)
- 13 = -1167 mod 29
- 13 = 22 (Fals)
- Deci inversul punctului (8, 10) nu se afla pe curba eliptica
- Verificare (8, 11)
- 13 = 1521 mod 29 (Adevarat)
- Inversul punctului (8, 11)
- Este (8, -10)
- 13 = 22 (Fals)
- Deci inversul punctului (8, 11) nu se afla pe curba eliptica
Desi raspunsul meu este acesta, unii colegi afirma ca axa de simetrie nu este OX.
d. Curba eliptica NIST P-224 este de tipul Weierstrass si este recomandata pentru p pe 224 de biti:
y^2 = x^3 - 3x + bb = 18958286285566608000408668544493926415504680968679321075787234672564p = 2^224 - 2^96 + 1 = 269599466671506397946670150870196306735579162600263081435100 66298881n = 2695994666715063979466701508701962594045780771442439172168 2722368061c = 2695994666715063979466701508701962594045780771442439172168 2722368061Gx = 19277929113566293071110308034699488026831934219452440156649784352033Gy = 19926808758034470970197974370888749184205991990603949537637343198772
Sursa este https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf, validata de:
- https://safecurves.cr.yp.to/
- https://medium.com/asecuritysite-when-bob-met-alice/the-nearest-thing-to-true-beauty-in-cybersecurity-elliptic-curve-cryptography-ecc-ebc713b9da09
- https://asecuritysite.com/encryption/go_ecc
Mentionez ca nu am inteles exact scopul/semnificatia acestor elipse; doar am respectat cerinta si am gasit ecuatia unei astfel de curbe.