Kriptografija


Profesor: dr. Miroslav Živković
Asistent: Sana Stojanović Đurđević

Оbaveštenje:

  • Rezultati ispita SEPTEMBAR: rezultati
  • Okačena je skripta rešenih zadataka, nalazi se među materijalima kursa.

Raspodela poena na kursu:

  • Kolokvijum, 30 poena
  • Pismeni ispit, 30 poena
  • Usmeni ispit, 40 poena

Materijali za kurs:

Zadaci urađeni na vežbama:

  1. I čas:
    1. Dokazati da 6 deli n*(n^2+5).
    2. Dokazati da 30 deli m^5-m.
    3. Dokazati da 42 deli m^7-m.
    4. Dokazati da 2^n deli (2n)!/(n!).
    5. Dokazati da 30 deli mn(m^4-n^4).
    6. Dokazati da je broj deljiv sa 3 ako mu je zbir cifara deljiv sa 3.
    7. Dokazati da je broj deljiv sa 11 ako mu je razlika zbira cifara na parnim i zbira cifara na neparnim pozicijama deljiva sa 11.
    8. Ako su p i q prosti brojevi dokazati da 24 deli p^2-q^2.
    9. Razložiti na faktore brojeve 82798848, 10!, 15!, 20!, 30!.
    10. Odrediti sa koliko nula se završavaju brojevi 50! i 100!.
    11. Dokazati da suma kvadrata 5 uzastopnih celih brojeva ne može biti pun kvadrat.
    12. Ako je nzd(a,b)=1 i ako je a*b jednak kvadratu prirodnog broja, dokazati da su a i b kvadrati prirodnih brojeva.
    13. Izračunati nzd(61,43) i predstaviti ga kao linearnu kombinaciju brojeva 61 i 43.
    14. Izračunati inverz broja 160 po modulu 841.
  2. II čas:
    1. Ako je nzd(a,b)=1 pokazati da je nzd(a+b, a-b)<=2.
    2. Dokazati da x^3-x-1 nije nikada jednako kvadratu nekog celog broja.
    3. Odrediti broj A ako je A=p*q, p i q su prosti brojevi i važi da je: p-q = 2, phi(A) = 120.
    4. Odrediti sva celobrojna rešenja jednačine 53x+47y = 1.
    5. Odrediti sva celobrojna rešenja jednačine 22x+32y = 1.
    6. Odrediti sva rešenja kongruencija 3x=4 (mod 7), 3x=4 (mod 12), 9x=12 (mod 21), 27x=72 (mod 900).
  3. III čas:
    1. Sastaviti tablicu indeksa sa osnovom 2 po modulu 29.
    2. Sastaviti tablicu indeksa sa osnovom 5 po modulu 23.
    3. Odrediti vrednosti x,y,z,w tako da je 52^x=38(mod 29), 23^y=9(mod 29), 3^x=7(mod 29), 3^x=6(mod 23).
    4. Odrediti inverze 5^(-1)(mod 29), 7^(-1)(mod 29), 39^(-1)(mod 29), (-1)^(-1)(mod 23)
    5. Odrediti sve generatore multiplikativne grupe ostataka po modulu 23 i po modulu 29.
    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.
  4. IV čas:
    1. Napraviti tablicu množenja u F_2[x]/(x^2+x+1)* pa zatim tablicu mnozenja u F_2[x]/(x^3+x^2+1)*.
    2. Invertovati element x^4+x^3+1 nad poljem F_2[x]/(x^6+x+1).
    3. Pomoću Euklidovog algoritma odrediti (x^4)^(-1) u polju F_2[x]/(x^5+x^2+1).
    4. 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.
    5. Proširivanje ključa.
    6. 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.
  5. V čas:
    1. Predstaviti proširivanje ključa u SAES dijagramom sa 6 čvorova (raspoređenim u 3 reda po 2 čvora).
    2. Uprošćeni algoritam AES.
    3. Primer šifrovanja i dešifrovanja u AES-u.
    4. Napraviti tablicu stepenova u F_2[x]/(x^3+x^2+1)* ako je generator x.
    5. Uz pomoć tablice izračunati proizvode: (x^2+1)*(x^2+x+1) i (x-1)*(-x-1).
    6. 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.
  6. VI čas:
    1. Izračunati 57^1616(mod 97).
    2. Dokazati da u polju F_q, gde je q=p^k za prost broj p, vazi (a+b)^p = a^p+b^p (mod p).
    3. Prikazati postupak Diffie-Helman protokola usaglašavanja ključa za q=97, g=5, a_A=36, a_B=58.
    4. Prikazati postupak El Gamal protokola za M=30, q=97, g=5, a_B=58, k=17.
    5. Primer stepenovanja ponovljenim kvadriranjem, 87^43.
    6. Pokazati da ako x^2=d(mod n) ima jedno rešenje x0 i n=p*q (p i q prosti brojevi, veći ili jednaki 3), onda postoje još tri rešenja te kongruencije.
    7. Prikazati postupak Massey-Omura razmene ključeva.
  7. VII čas:
    1. Eliptičke krive.
    2. Dokazati da je kardinalnost skupa F_p manja ili jednaka 2p+1.
    3. Izvesti izraze za sabiranje dve tačke i dupliranje tacke za eliptičku krivu zadatu jednačinom y^2 = x^3 + 3*x + 8.
    4. Dokazati da je tačka G(1,5) generator.
    5. Neka su date tačke P(9,7) i Q(1,8). Odrediti tačku P+Q i P+P u E(F_13): y^2 = x^3 + 3*x + 8.
    6. Odrediti E(F_5) za eliptičku krivu y^2 = x^3 + 1. Dokazati da je tačka G(2,3) generator.
    7. 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 (2,3), tajni ključevi e_A = 4, e_B = 5, odrediti tačku koja se dobija kao rezultat usaglašavanja.
    8. Za sistem El Gamal koristi se eliptička kriva E: y^2 = x^3 + 3*x + 8, generator (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.
  8. VIII č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_n potpis poruke m1, a S_2 potpis poruke m2, onda je S1S2 potpis poruke m1m2.
    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.
  9. IX čas:
    1. Generator slučajnih brojeva b/p.
    2. Verižni razlomci.
    3. Odrediti verižni razvoj za 27/8, \sqrt{3}, \sqrt{5}, \sqrt{7}, 7/23, Pi i odrediti prvih 8 parcijalnih razlomaka.
    4. Izvesti rekurzivne formule za odredjivanje parcijalnih razlomaka.
    5. Dokazati da za svaki prirodan broj n važi P_n * Q_{n-1} - P_{n-1}*Q_n = (-1)^{n-1}.
  10. X č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: P1(x) = 1 + x^2 + x^3 + x^4; P2(x) = 1 + x + x^5; P3(x) = 1 + x + x^6; P4(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]
  11. XI čas:
    1. Odrediti linearne kombinacije ulaza i izlaza najbliže konstanti za tabelu S u SAES (rešenje: dodatni materijali).
    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.
    4. Algoritam faktorizacije postupkom koji koristi slučajno lutanje. Primer n = 1357.
    5. Rešavanje problema diskretnog logaritma za eliptičke krive nad konačnim poljem, E: y^2 = x^3 + 3*x + 8, F_101, G(0,1) je generator. 103*G = 0. Odrediti n tako da je Q(5,98) = n*G.
    6. Algoritam lutanja kroz E(F_101).
  12. XII čas:
    1. Fermaova faktorizacija, primer n = 3229799, 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^3 = x^3 + x + 1, n = 221, R(0,1).
    5. Polje brojeva.
    6. Dokazati da su u polju Q(\sqrt{-5}) svi algebarski celi brojevi oblika a + b\sqrt{-5}, gde su a i b celi brojevi.
    7. Dokazati da se u polju Q(\sqrt{-5}) broj 2 ne moze rastaviti u netrivijalni proizvod algebarskih celih brojeva.
    8. Dokazati da 2 nije prost u Q(\sqrt{-5}).
  13. XIII čas:
    1. Polje brojeva Q(i) i Z(i).
    2. U skupu Z(i) rastaviti na činioce brojeve 5+3i, 11-3i.
    3. Polje brojeva Q(i).
    4. Kineska teorema o ostacima.
    5. Polig - Helmanov algoritam. Primer q = 401, g = 3, y = 304, g^x = y. Odrediti x.