Kriptografija

 

Vežbe


  • 1. čas
    1. Dokazati da \(6|m(m^2+5)\) važi za proizvoljan prirodan broj \(m\).
    2. Dokazati da \(30|m^5-m\) važi za proizvoljan prirodan broj \(m\).
    3. Dokazati da \(30|mn(m^4-n^4)\) važi za proizvoljne prirodne brojeve \(m\) i \(n\).
    4. Dokazati da \(42|m^7-m\) važi za proizvoljan prirodan broj \(m\).
    5. Dokazati da za proizvoljan prirodan broj \(n\) važi $$2^n|\frac{(2n)!}{n!}$$.
    6. Dokazati da je broj deljiv sa tri ako mu je zbir cifara deljiv sa tri.
    7. Dokazati da je broj deljiv sa 11 ako mu je razlika zbira cifara na parnim i na neparnim pozicijama deljiva sa 11.
    8. Neka je \( NZD(a,b) = 1\). Dokazati da je \( NZD(a+b, a-b) \le 2\).
    9. Izračunati
      1. \(NZD(549, 387)\),
      2. \(NZD(589, 343)\),
      3. \(NZD(12606, 6494)\) i
      4. \(NZD(6188, 4709)\).
      Zatim izračunati \(NZD\) izraziti kao linearnu kombinaciju datih brojeva.
    10. Odrediti \( 160^{-1}(\mod 841)\).
    11. Koliko činilaca ima broj 945?
    12. Odrediti \( 2^{1000000}(\mod 7)\).
    13. Dokazati da suma kvadrata pet uzastopnih celih brojeva nije pun kvadrat.
    14. Neka su \(p, q \ge 5 \) prosti brojevi. Dokazati da \( 24 | p^2 - q^2\).
  • 2. čas
    1. Ako su \(a\) i \(b\) uzajamno prosti prirodni brojevi i ako je \(a*b\) kvadrat prirodnog broja, onda su i \(a\) i \(b\) kvadrati prirodnih brojeva.
    2. Odrediti sva rešenja konguencija:
      1. \(3x \equiv 4 (\mod 7 )\),
      2. \(3x \equiv 4 (\mod 12 )\),
      3. \(9x \equiv 12 (\mod 21 )\),
      4. \(27x \equiv 25 (\mod 256 )\),
      5. \(27x \equiv 72 (\mod 900 )\) i
      6. \(103x \equiv 612 (\mod 676 )\).
    3. Odrediti \( \varphi(n)\) za \(n = 90, 91, ... , 100\).
    4. Dokazati da je broj \(m\) prost ako i samo ako je \(\varphi(m) = m-1\).
    5. Rastaviti na proste činioce brojeve \(82798848, 81057226635\).
    6. Rastaviti na proste činioce brojeve \(10!, 15!, 20!, 30!\).
    7. Sa koliko nula se završavaju brojevi \(50!, 100!\).
    8. Odrediti \( \varphi(n)\) za \(n = 375, 720, 957, 988, 1200, 4320\).
    9. Neka je \( \varphi(a) = 120\), a \( a = p*q\), gde su \( p\) i \( q\) prosti brojevi. Odrediti \( a\), ako se zna da je \( p-q = 2\).
    10. Odrediti sva celobrojna rešenja jednačina:
      1. \(53x + 47y = 1\) i
      2. \(22x + 32y = 18\).
  • 3. čas
    1. Sastaviti tablicu indeksa sa osnovom 2 po modulu 29.
    2. Sastaviti tablicu indeksa sa osnovom 5 po modulu 23.
    3. Odrediti \(x\) tako da važi:
      1. \(52^x \equiv 38 (\mod 29 ) \),
      2. \(23^x \equiv 9 (\mod 29 ) \),
      3. \(3^x \equiv 7 (\mod 29 ) \),
      4. \(3^x \equiv 7 (\mod 23 ) \) i
      5. \(3^x \equiv 6 (\mod 23 ) \).
    4. Odrediti sve generatore multiplikativne grupe ostataka po modulu \(23\) i po modulu \(29\), ( \(\mathbb Z/n \mathbb Z^*\), za \(n = 23,29\) ).
    5. Izračunati:
      1. \(5^{-1}(\mod 29 ) \),
      2. \(7^{-1}(\mod 29 ) \),
      3. \(21^{-1}(\mod 29 ) \),
      4. \(39^{-1}(\mod 23 ) \) i
      5. \((-1)^{-1}(\mod 23 ) \).
    6. Odrediti sve nesvodljive polinome stepena najviše 3 u \(F_2[x]\).
    7. Proveriti da li je polinom \(x^4+x^3+x^2+x+1\) nesvodljiv u \(F_2[x]\).
    8. Napraviti tablicu množenja u \(F_2[x]/(x^2+x+1)^*\), a zatim iz te tablice napisati tablicu inverza. Da li su \(x\) i \(x + 1\) generatori?
    9. Napraviti tablicu množenja u \(F_2[x]/(x^3+x^2+1)^*\), a zatim iz te tablice napisati tablicu inverza. Da li je \(x\) generator za \(F_2[x]/(x^3+x^2+1)^*\)?
    10. Dokazati da je \(x\) generator za \(F_2[x]/(x^4+x+1)^*\).
    11. Invertovati elemenat \(x^4+x^3+1\) nad poljem \(F_2[x]/(x^6+x+1)^*\).
    12. Invertovati elemenat \(x^4\) nad poljem \(F_2[x]/(x^5+x^2+1)^*\).
  • 4. čas
    1. SAES.
    2. Odrediti matrice A i B takve da se druga komponenta preslikavanja S u algoritmu SAES može predstaviti u obliku A*Y+B gde je Y vektor kolona, nibl, dobijen iz prve komponente S preslikavanja.
    3. Koristeći tabelu koja opisuje funkciju S u SAES napisati izraze za četiri izlazna bita e,f,g,h preko ulaznih bitova a,b,c,d.
    4. Proširivanje ključa. Predstaviti proširivanje ključa u SAES dijagramom sa šest čvorova (tri reda sa po dva čvora, tako da u \(i\)-tom redu budu čvorovi \(W[2i]\), \(W[2i+1]\), \(i = 1,2,3...\) ). Primeniti proširivanje ključa na dati ključ 0101-1001-0111-1010.
    5. Uprošćeni algoritam AES - šifrovanje i dešifrovanje u AES-u.
    6. Napraviti tablicu stepenova u \(F_2[x]/(x^3+x^2+1)^*\) ako je generator \(x\). Uz pomoć tablice izračunati proizvod \((x^2+1)*(x^2+x+1)\).
    7. Neka je \(n\) proizvod različitih prostih brojeva. Neka su \(d\) i \(e\) prirodni brojevi takvi da za svaki prost broj \(p\) koji deli \(n\) važi, \(p-1|d*e-1\). Dokazati da je \(a^{d*e}=a(\mod n)\) za svako \(a\).
    8. Izračunati \(57^{1616}(\mod 97)\).
    9. Dokazati da u polju \(F_q\), gde je \(q=p^k\) za prost broj \(p\), vazi \((a+b)^p = a^p+b^p\).
  • 5. čas
    1. RSA. Ukoliko je u sistemu RSA greškom izaberan \(n=p, p\) je prost, dokazati da je sistem lako razbiti.
    2. Prikazati postupak Diffie-Helman protokola usaglašavanja ključa za \(q=97\), \(g=5\), \(a_A=36\), \(a_B=58\) tj. izračunati \(g^{a_A}\), \(g^{a_B}\) i \(K\).
    3. Prikazati postupak El Gamal protokola za \(M=30\), \(q=97\), \(g=5\), \(a_B=58\), \(K=17\).
    4. Prikazati postupak Massey-Omura razmene ključeva za \(q=677\), \(M = 470\), \(e_A=255\), \(e_B=421\).
  • 6. čas
    1. Eliptičke krive.
    2. Za eliptičku krivu E: \(y^2 = x^3 + Ax + B\) izvesti izraze za sabiranje dve tačke \(P+Q\) i dupliranje tacke za eliptičku krivu \(P+P\).
    3. Dokazati da eliptička kliva nad poljem \(F_p\) ima najviše \(2p+1\) tačku.
    4. Za eliptičku krivu zadatu jednačinom \(y^2 = x^3 + 3*x + 8\) nad poljem \(F_{13}\):
      1. odrediti skup svih tačaka krive \(E(F_{13})\),
      2. odrediti \(P+Q\) i \(P+P\) za tačke \(P = (9,7)\) i \(Q = (1,8)\),
      3. dokazati da je tačka \(G(1,5)\) generator,
      4. napraviti tablicu logaritama gde je osnova tačka \(G(1,5)\) i
      5. odrediti \(25P\).
    5. Eliptička kriva koja se koristi za problem usaglašavanja ključeva Diffie-Helman protokola je E: \(y^2 = x^3 + 3*x + 8\) nad poljem \(F_{13}\). Ako se koristi generator \(G = (2,3)\), tajni ključevi \(e_A = 4\), \(e_B = 5\), odrediti tačku koja se dobija kao rezultat usaglašavanja.
    6. Za sistem El Gamal koristi se eliptička kriva E: \(y^2 = x^3 + 3*x + 8\), generator \(G = (2,3)\). Ako su tajni ključevi \(e_A = 5\) i \(e_B = 3\), prikazati postupak šifrovanja poruke \(M = (12,11)\) (koristi se slučajan broj \(k=4\), a zatim postupak dešifrovanja šifrata.
  • 7. čas
    1. U sistemu autentikacije zasnovanom na RSA korisnik A je izabrao javni ključ \(e = 7\) i \(n = 77\). Ako je on od korisnika B dobio broj \(23\), kako treba da glasi njegov odgovor da bi sagovornika ubedio u svoj identitet?
    2. Za digitalne potpise zasnovane na sistemu RSA korisnici A i B imaju javne ključeve \(e_A = 3\), \(n_A = 15\) i \(e_B = 7\), \(n_B = 77\). Korisnik B želi da pošalje poruku \(M = 4\) kao potpis nekog teksta. Koji ceo broj on treba da pošalje?
    3. Dokazati da za digitalne potpise zasnovane na RSA vazi sledeće tvrdjenje: Ako je \(S_1\) potpis poruke \(m_1\), a \(S_2\) potpis poruke \(m_2\), onda je \(S_1S_2\) potpis poruke \(m_1m_2\).
    4. Korisnik A ima javni ključ \(e = 11\), \(n = 899\). Kako glasi njegov RSA digitalni potpis poruke \(876\)?
    5. Algoritam potpisivanja El Gamal. Opisati postupak za \(p = 677\), \(g = 2\), \(S = 316\), \(a_A = 307\), \(k = 401\).
    6. Generator slučajnih brojeva b/p.
    7. Verižni razlomci. Izvesti rekurzivne formule za odredjivanje parcijalnih razlomaka.
    8. Odrediti verižni razvoj za \(27/8\), \(\sqrt{3}\), \(\sqrt{5}\), \(\sqrt{7}\), \(7/23\) i odrediti prvih \(8\) parcijalnih razlomaka.
    9. Dokazati da za svaki prirodan broj \(n\) važi \(P_n * Q_{n-1} - P_{n-1}*Q_n = (-1)^{n-1}\).
  • 8. čas
    1. Pomerački registar sa linearnom povratnom spregom.
    2. Odrediti orbite za \(n=3\), \((b_0, b_1, b_2) = (1, 1, 0)\), \((k_0, k_1, k_2) = (0, 1, 1)\).
    3. Odrediti orbite za \(n=4\), \((b_0, b_1, b_2, b_3) = (1, 0, 1, 0)\), \((k_0, k_1, k_2, k_3) = (0, 1, 1, 1)\).
    4. Odrediti orbite za \(n=4\), \((b_0, b_1, b_2, b_3) = (1, 0, 0, 1)\), \((k_0, k_1, k_2, k_3) = (0, 1, 1, 1)\).
    5. Odrediti orbite za linearne pomeračke registre za polinome: \(P_1(x) = 1 + x^2 + x^3 + x^4\); \(P_2(x) = 1 + x + x^5\); \(P_3(x) = 1 + x + x^6\); \(P_4(x) = 1 + x^3 + x^5\).
    6. Odrediti povratne sprege i linearne pomeračke registre na osnovu otvorenog teksta i šifrovanog teksta: \(OT = [4, 0] = [0 0 1 0 0, 0 0 0 0 0]\), \(ST = [17,30] = [1 0 0 0 1, 1 1 1 1 0]\).
  • 9. čas
    1. Odrediti linearne kombinacije ulaza i izlaza najbliže konstanti za tabelu S u SAES (rešenje).
    2. Odrediti sve afine funkcije ulazno izlaznih bita koje imaju verovatnoću da budu jednake jedinici bar \(0.75\).
    3. Rodjendanski paradoks i slučajno lutanje. Algoritam faktorizacije postupkom koji koristi slučajno lutanje. Primer n = 1357.
    4. Rešavanje problema diskretnog logaritma za eliptičke krive nad konačnim poljem, \(E: y^2 = x^3 + 17*x + 1\), \(F_{101}\), \(G(0,1)\) je generator. \(103*G = 0\). Odrediti n tako da je \(Q(5,98) = n*G\).
    5. Algoritam lutanja kroz \(E(F_{101}^*)\). Ako se zna da je \(g = 2\) generator za \(F_{101}\), odredite \(x\) tako da je \(y = 86 = g^x\).
  • 10. čas
    1. Fermaova faktorizacija, primer \(n = 3229799\), \(n = 1357\) i \(n = 21079\).
    2. Faktorizacija uz pomoć baza faktora. Primer \(n = 89893\), \(b = 20\).
    3. Faktorizacija pomoću verižnih razlomaka. Primer \(n = 17873\).
    4. Faktorizacija pomoću eliptičkih krivih. Primer \(E: y^2 = x^3 + x + 1\), \(n = 221\), \(R(0,1)\).
  • 11. čas
    1. Polje brojeva.
    2. Dokazati da su u polju \(\mathbb Q(\sqrt{-5})\) svi algebarski celi brojevi oblika \(a + b\sqrt{-5}\), gde su \(a\) i \(b\) celi brojevi.
    3. Dokazati da se u polju \(\mathbb Q(\sqrt{-5})\) broj \(2\) ne moze rastaviti u netrivijalni proizvod algebarskih celih brojeva.
    4. Dokazati da \(2\) nije prost u \(\mathbb Q(\sqrt{-5})\).
  • 12. čas
    1. Polje brojeva \(\mathbb Q(i)\) i \(\mathbb Z(i)\).
    2. U skupu \(\mathbb Z(i)\) rastaviti na činioce brojeve \(5+3i\), \(11-3i\) i \(7+i\).
    3. Polje brojeva \(\mathbb Q(i)\).
    4. Kineska teorema o ostacima.
    5. Polig - Helmanov algoritam. Primer \(q = 401\), \(g = 3\), \(y = 304\), \(g^x = y\). Odrediti \(x\).
Povratak na vrh

 

OBAVEŠTENJA

  • TERMIN ISPITA (SEPTEMBAR 2): 27.9. od 12h u sali BIM
  • Rezultati - JUN 2 2017. Gledanje radova je moguće 8.8.2017. u 13.30 (ali ne neophodno potvrditi dolazak mejlom najkasnije 8.8.2017. u 12h).
  • Rezultati - JUN 2017.
  • Rezultati kolokvijuma
  • Zbog nenastavnog dana 4.4.2017. nećemo imati vežbe.
  • TERMIN KOLOKVIJUMA: Kolokvijum će se održati 25.4.2017. od 8h u sali 718 (i još jednoj sali) na Studentskom trgu.
  • TERMIN KOLOKVIJUMA: Kolokvijum će se održati 4.4.2017. od 8h u sali 718 (i još jednoj sali) na Studentskom trgu. Termin se menja jer je stiglo obaveštenje da je 4.4.2017. neradan dan. Srećan Dan studenata!
  • Vežbe će biti održane nakon prvog predavanja, tako da nema vežbi u prvoj nastavnoj nedelji.