Analiza napada na kriptosustav RSA

master's thesis

• Title (english): Analysis of the Attacks on the RSA Cryptosystem
• Author: Gustav Matula
• Mentor: Ante Đerek (mentor)
• Committee member: Ante Đerek (predsjednik povjerenstva)
• Committee member: Stjepan Groš (član povjerenstva)
• Committee member: Andrea Aglić Aljinović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: kriptografija; kriptosustav RSA
• Keywords (english): cryptography; RSA cryptosystem
• Language: croatian
• URN:NBN: urn:nbn:hr:168:899884
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-13 22:53:59