MateClar
← Capitol

Manual · pagina 100

Exercițiul 24 · Criptarea PIN-urilor

(Activitate în pereche) O companie de software dezvoltă un sistem de autentificare pentru un seif digital. Pentru a proteja PIN-urile numerice ale utilizatorilor în baza de date, acestea nu sunt salvate în forma lor originală, ci sunt trecute printr-un algoritm de criptare reprezentat de o funcție matematică. Algoritmul de criptare este definit de funcția f ⁣:R→Rf\colon \mathbb R \to \mathbb R, f(x)=3x−24f(x) = 3x - 24, unde xx reprezintă PIN-ul original ales de utilizator, iar f(x)f(x) reprezintă valoarea criptată care se salvează efectiv în baza de date. Pentru ca sistemul să funcționeze corect, acesta trebuie să fie capabil să recupereze PIN-ul original atunci când verifică identitatea utilizatorului. Asta înseamnă că procesul trebuie să fie reversibil.

a) Demonstrați că funcția de criptare ff este bijectivă, justificând astfel faptul că decriptarea este posibilă pentru orice valoare și că nu există două PIN-uri diferite care să aibă aceeași valoare criptată.

b) Determinați funcția de decriptare f−1f^{-1} care permite sistemului să afle PIN-ul original xx cunoscând valoarea stocată yy.

c) Caz concret: un hacker reușește să vadă baza de date și găsește valoarea criptată y=1 206y = 1\,206; folosind funcția inversă determinată la punctul anterior, aflați care este PIN-ul original al utilizatorului.

a)Demonstrați că funcția de criptare ff este bijectivă, justificând astfel faptul că decriptarea este posibilă pentru orice valoare și că nu există două PIN-uri diferite care să aibă aceeași valoare criptată.

„Nu există două PIN-uri cu aceeași valoare criptată” este injectivitatea, iar „decriptarea e posibilă pentru orice valoare” este surjectivitatea. Verifică-le pe rând.

  1. 1. Ce înseamnă în limbajul seifului

    Sistemul ia PIN-ul xx, îl înmulțește cu 33 și scade 2424; rezultatul se salvează.

    Verifică-te

    Ce valoare criptată se salvează pentru PIN-ul x=1234x = 1234?

  2. 2. Injectivitatea

    Fie x1,x2x_1, x_2 cu aceeași valoare criptată: 3x1−24=3x2−243x_1 - 24 = 3x_2 - 24. Adunăm 2424 și împărțim la 33 în ambii membri: x1=x2x_1 = x_2. Deci ff este injectivă: două PIN-uri diferite au valori criptate diferite.

  3. 3. Surjectivitatea

    Fie yy un număr real oarecare. Căutăm xx cu 3x−24=y3x - 24 = y: adunăm 2424, apoi împărțim la 33, deci x=y+243x = \frac{y + 24}3, un număr real. Încercăm pe o valoare concretă.

    Verifică-te

    Ce PIN xx are valoarea criptată f(x)=0f(x) = 0?
    −224681012−24−18−12−6612Oxy
    ff
    (8,0)(8, 0)

    Graficul lui f(x)=3x−24f(x) = 3x - 24 este o dreaptă oblică: orice dreaptă orizontală o taie exact o dată (aici dreapta punctată y=6y = 6, în x=10x = 10).

    Orice valoare yy are deci o preimagine: ff este surjectivă, orice valoare salvată se poate decripta. Fiind injectivă și surjectivă, ff este bijectivă.
Răspuns
Din 3x1−24=3x2−243x_1 - 24 = 3x_2 - 24 rezultă x1=x2x_1 = x_2 (injectivă), iar pentru orice yy, x=y+243x = \frac{y + 24}3 verifică f(x)=yf(x) = y (surjectivă). Deci ff este bijectivă: PIN-uri diferite dau valori criptate diferite, iar orice valoare criptată se poate decripta.

b)Determinați funcția de decriptare f−1f^{-1} care permite sistemului să afle PIN-ul original xx cunoscând valoarea stocată yy.

Decriptarea desface criptarea în ordine inversă: criptarea înmulțește cu 33 și apoi scade 2424.

  1. 1. Îl scoatem pe xx din y=3x−24y = 3x - 24

    Criptarea face doi pași: înmulțește cu 33, apoi scade 2424. Decriptarea trebuie să-i desfacă pe amândoi, ca din valoarea yy să se întoarcă la xx. Rezolvă y=3x−24y = 3x - 24 în raport cu xx.

    Verifică-te

    Care este funcția de decriptare f−1(y)f^{-1}(y)?
    f−1 ⁣:R→R,f−1(y)=y+243\begin{aligned} &f^{-1}\colon \mathbb R \to \mathbb R, \\ &f^{-1}(y) = \frac{y + 24}3 \end{aligned}

  2. 2. Verificăm că decriptarea desface criptarea

    Conform definiției (manual, p. 97), trebuie ca f−1(f(x))=xf^{-1}(f(x)) = x pentru orice PIN xx și f(f−1(y))=yf(f^{-1}(y)) = y pentru orice valoare yy:
    f−1(f(x))=(3x−24)+243=xf(f−1(y))=3⋅y+243−24=y\begin{aligned} f^{-1}(f(x)) &= \frac{(3x - 24) + 24}3 \\ &= x \\[6pt] f(f^{-1}(y)) &= 3 \cdot \frac{y + 24}3 - 24 \\ &= y \end{aligned}

    Verifică-te

    Ce PIN corespunde valorii stocate y=−3y = -3?
    În notația obișnuită, cu xx ca variabilă, f−1(x)=x+243f^{-1}(x) = \frac{x + 24}3.
Răspuns
f−1 ⁣:R→Rf^{-1}\colon \mathbb R \to \mathbb R, f−1(y)=y+243f^{-1}(y) = \dfrac{y + 24}3 (în notația obișnuită, f−1(x)=x+243f^{-1}(x) = \dfrac{x + 24}3).

c)Caz concret: un hacker găsește valoarea criptată y=1 206y = 1\,206. Folosind funcția inversă de la punctul b), aflați PIN-ul original al utilizatorului.

Aplică funcția de decriptare de la b), f−1(y)=y+243f^{-1}(y) = \frac{y + 24}3, valorii 1 2061\,206.

  1. 1. Decriptăm

    PIN-ul este x=f−1(1206)x = f^{-1}(1206): adunăm 2424, apoi împărțim la 33.

    Verifică-te

    Cât este f−1(1206)f^{-1}(1206)?

  2. 2. Verificare și o observație

    Verificăm prin criptare: f(410)=3⋅410−24f(410) = 3 \cdot 410 - 24 =1230−24=1206= 1230 - 24 = 1206, chiar valoarea găsită. Deci PIN-ul original este 410410, și este singurul, fiindcă ff este injectivă (punctul a).
Răspuns
PIN-ul original este f−1(1206)=1206+243=410f^{-1}(1206) = \dfrac{1206 + 24}3 = 410 (verificare: f(410)=1206f(410) = 1206).