NTRU kriptosustav

diplomski rad

• Autor: Valentina Pribanić
• Mentor: Andrej Dujella (mentor)
• Član povjerenstva: Andrej Dujella (predsjednik povjerenstva)
• Član povjerenstva: Zrinka Franušić (član povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Član povjerenstva: Dragutin Svrtan (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Većina današnjih kriptosustava s javnim ključem temelji se na problemima faktorizacije velikih brojeva i diskretnog logaritma. Pojavom kvantnih računala, ovi problemi bi postali rješivi. U ovom radu je opisan NTRU kriptosustav, kriptosustav koji bi ostao teško rješiv problem i za kvantna računala. Dijeli se na dva algoritma: NTRUEncrypt i NTRUSign. Posebno, za šifriranje koristimo NTRUEncrypt. Ovaj kriptosustav temelji se na teoriji rešetaka, te problemu pronalaska najkraćeg vektora unutar rešetke. Sve operacije su unutar prstena polinoma s cjelobrojnim koeficijentima na kojima se dodatno definira konvolucijsko množenje. Najučinkovitiji napadi na NTRUEnrypt kriptosustav su oni koji koriste strukturu rešetki. Tu se posebno ističe LLL algoritam, te njegova blokovna verzija BKZ-LLL algoritam. LLL algoritam reducira bazu rešetke na skoro ortogonalnu bazu, te se u takvoj poboljšanoj bazi rješava problem najkraćeg vektora. NTRUSign je kriptosustav s javnim ključem koji se koristi za digitalne potpise. Općenito, digitalni potpisi imaju sličnu ulogu kao vlastoručni potpisi na papiru. Veliki broj potpisanih dokumenata odaje puno informacija o privatnom ključu. Da bi se ovo spriječilo uvode se preturbacije unutar poruke prije samog potpisivanja.

Sažetak (engleski)

Most of today’s public key cryptosystems are based on two hard mathematical problems: factoring large integers and discrete logarithm problem. With possible advent of quantum computers, these problems can become solvable. This paper describes the NTRU cryptosystem, cryptosystem that is known to not be vulnerable to quantum computer based attacks. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. NTRUEncrypt is lattice-based public key cryptosystem and is based on the shortest vector problems. Operations are based on objects in a polynomial ring with convolution multiplication and all polynomials in the ring have integer coefficients. Breaking the NTRUEncrypt cryptosystem is related with problem of lattice reduction. Some of lattice reduction algorithms used to break NTRUEncrypt are LLL algorithm and BKZ-LLL algorithm. LLL algoritham calculates an LLL reduced basis, i.e. short and nearly orthonogal basis. NTRUSign is a public key cryptography digital signature algorithm. A digital signature is a scheme for verifying the authenticity of a digital document. Transcript of NTRUSign signatures leaks information about private key. To prevent leaks is recommended to use preturbation in message before the signature itself is calculated.

• Ključne riječi: NTRU kriptosustav; kriptosustav s javnim ključem; NTRUEncrypt algoritam; NTRUSign algoritam; teorija rešetaka; LLL algoritam; BKZ-LLL algoritam; digitalni potpis
• Ključne riječi (engleski): NTRU cryptosystem; public key cryptosystem; NTRUEncrypt algorithm; NTRUSign algorithm; lattice theory; LLL algorithm; BKZ-LLL algorithm; digital signature
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:891100
• Studijski program: Naziv: Primijenjena matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-02-01 09:10:06