hrvatski

LLL algoritam i neke primjene u kriptografiji

U ovom radu definiramo pojam rešetke te koncept redukcije rešetke. Opisujemo kako se redukcija rešetke može efikasno provesti pomoću LLL algoritma, kojeg su osmislili Henrik Lenstra, Arjen Lenstra i Laszlo Lovasz 1982. godine, te navodimo neke primjere kada pomoću reˇsetki možemo dekriptirati neke kriptosustave. Prije svega, uvodimo definiciju rešetke i njene baze te dovodimo u vezu pojam rešetke i diskretne aditivne podgrupe. Zatim, definiramo probleme koji se javljaju prilikom prouˇcavanja rešetki, kao što je problem najkraćeg vektora rešetke. Predstavljamo i neke teoretske rezultate o ogradama na duljinu najkra´ceg vektora te očekivanoj duljini najkraćeg vektora rešetke. Opisujemo i jednostavnu heuristiku pomo´cu koje se proizvoljan vektor aproksimira vektorom iz rešetke te dajemo primjer kad ona pokazuje dobre, a kad loše rezultate. Zatim, uvodimo pojam redukcije rešetke, prvo u slučaju dvodimenzionalne rešetke pomoću Gaussovog algoritma, a zatim i na proizvoljnoj rešetci pomoću LLL algoritma. Predstavljamo dokaz u kojem se pokazuje kako se LLL algoritam približava optimalnom rezultata do na neku konstantu te dokaz koji nam garantira da će LLL algoritam završiti u polinomijalnom vremenu u veliˇcini rešetke. Obraćamo pažnju i na neke implementacijske detalje te donosimo implementaciju LLL algoritma u cjelobrojnoj aritmetici. U posljednjem poglavlju opisujemo rezultate u kriptografiji koje možemo dobiti primjenom redukcije rešetke na neke od problema dekripicije. Naglasak smo stavili na primjenu kod kriptoanalize RSA kriptosustava. Donosimo rezultat koji opisuje kako se pomo´cu rešetki može izračunati korijen polinoma modulo neki cijeli broj N te time i dekriptirati RSA kriptosustav u slučaju kad je nepoznati dio poruke kratak, a eksponent koji se koristi malen.

LLL algoritam ; rešetka ; RSA

nije evidentirano