Analiza napada na kriptosustav RSA

diplomski rad

• Naslov (engleski): Analysis of the Attacks on the RSA Cryptosystem
• Autor: Gustav Matula
• Mentor: Ante Đerek (mentor)
• Član povjerenstva: Ante Đerek (predsjednik povjerenstva)
• Član povjerenstva: Stjepan Groš (član povjerenstva)
• Član povjerenstva: Andrea Aglić Aljinović (č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: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Moderni način života ovisi o sigurnosti kriptosustava koje svakodnevno koristimo.
Glavni argument za tu sigurnost je činjenica da ih još nitko (barem ne javno) nije
probio. Takav argument se na prvu čini slab, ali proučavanjem postojećih pristupa, do-
bivamo bolji uvid u razinu sofistikacije potrebnu za uspješan napad, čak i uz korištenje
velikodušnih pretpostavki znanja koje je u praksi obično nedostupno. U ovome radu
bavimo se dvama takvim napadima na javni kriptosustav RSA koji uz pretpostavke
znanja dijela bitova privatnog ključa mogu rekonstruirati ostatak. Jedan od napada
je napredna tehnika faktorizacije LFM (Lattice Factoring Method) Boneha Durfeea i
Howgrave-Graham baziranu na redukciji baze rešetke. Drugi, napad Heninger i Shac-
hama, je elementarniji i koristi iscrpnu pretragu s elegantnim rezanjem grana. Oba
napada implementirana su u programskom jeziku C++ (relevantni dijelovi priloženi su
na kraju), te je eksperimentalnim mjerenjima potvrd̄eno da su napadi primjenjivi za
realistične duljine ključeva. To implicira da curenje vrlo malog broja bitova privatnog
ključa čini kriptosustav RSA nesigurnim.

Sažetak (engleski)

The modern way of life depends on the security of cryptosystems we use every day.
The main argument for that security is the fact that they have not yet been broken (at
least not publicly). That kind of argument seems weak at first, but studying the existing
approaches we gain better insight into the level of sophistication needed for a succe-
ssful attack even using generous assumptions of knowledge not available in practice.
In this thesis, we examine two such attacks on the public cryptosystem RSA, which
assume partial knowledge of the private key. The first of these attacks is an advanced
factoring technique called the LFM (Lattice Factoring Method) of Boneh, Durfee and
Howgrave-Graham based on lattice basis reduction techniques. The second attack, by
Heninger and Shacham, is more elementary and works by backtracking with elegant
pruning. Both attacks were implemented in the C++ programming language (the re-
levant parts are supplied at the end), and experimental measurements have confirmed
that the attacks are applicable to realistic key lengths. This implies that any leakage of
even a small number of private key bits renders the RSA cryptosystem insecure.

• Ključne riječi: kriptografija; kriptosustav RSA
• Ključne riječi (engleski): cryptography; RSA cryptosystem
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:899884
• 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: 2019-03-13 22:53:59