Pronalaženje Booleovih funkcija maksimalne nelinearnosti evolucijskim računanjem

diplomski rad

• Naslov (engleski): Evolutionary Computation Based Search for Maximal Nonlinearity Boolean Functions
• Autor: Kristijan Vulinović
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: Željka Mihajlović (član povjerenstva)
• Član povjerenstva: Alan Jović (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2019-09-23, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Booleove funkcije sastavni su element kriptografskih algoritama. Kako bi se povećala otpornost na napade linearnom kriptoanalizom, od posebnog je značaja svojstvo nelinearnosti Booleove funkcije. Booleove funkcije zadanog broja varijabli i maksimalne nelinearnosti nazivaju se Bent-funkcije, dok su sa stajališta primjene u kriptografskim algoritmima od posebnog interesa Booleove funkcije koje dodatno imaju i svojstvo balansiranosti.

U okviru ovog diplomskog rada proučeni su heuristički pristupi pronalaženja Booleovih funkcija maksimalne nelinearnosti te balansiranih Booleovih funkcija maksimalne nelinearnosti. Implementirani su i međusobno uspoređeni optimizacijski postupci temeljeni na simuliranom kaljenju, genetskom algoritmu i genetskom programiranju. Uspoređeni su i različiti načini prikazivanja Booleovih funkcija, poput zapisa u obliku tablice istinitosti te algebarskog zapisa, kao i razne funkcije izračuna dobrote rješenja u evolucijskim algoritmima. Dodatno je predložen i analiziran novi način pretrage traženih funkcija, temeljen na analizi Walsh koeficijenata funkcije.

Sažetak (engleski)

Boolean functions represent a crucial element for designing cryptographic algorithms. In order to resist against linear cryptanalysis attack, it is essential for Boolean functions to have high nonlinearity. Bent functions are Boolean functions with maximal possible nonlinearity for a given number of variables. For the usage in cryptographic algorithms it is additionally important for functions to be balanced.

This thesis is based upon researching heuristic search methods for maximal nonlinear Boolean functions and maximal nonlinear balanced Boolean functions. Solutions based on simulated annealing, genetic algorithms and genetic programming are implemented and compared. The impact of different function representations, such as truth tables and algebraic notation is also analyzed, together with various fitness functions. Finally, a new method based on the analysis of Walsh coefficients for finding nonlinear functions is proposed.

• Ključne riječi: Booleove funkcije; nelinearnost; heuristička optimizacija; evolucijski algoritmi
• Ključne riječi (engleski): Boolean Functions; Nonlinearity; Heuristic Optimization; Evolutionary Algorithms
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:748295
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-07 23:05:05