Bakalářská práce

LLL algoritmus a HNP problém

LLL algorithm and HNP problem

Jan Mačák
Anotace

LLL algoritmus umožňuje hledat krátké vektory v bodových mřížích a jako takový je potenciálně využitelný při řešení HNP (z anglického hidden number problem) – problému vyvstávajícího v souvislosti s bezpečností běžných kryptografických protokolů (Diffie–Hellman, DSA, ECDSA). V práci je popsán princip LLL algoritmu, zejména se pak práce zabývá HNP z teoretického pohledu, navrhuje potenciální vylepšení …více

Abstract

The LLL algorithm is used as a tool for finding short lattice vectors and as such can potentially be used in solving HNP (hidden number problem), which arises in connection with the security of common cryptographic protocols (Diffie–Hellman, DSA, ECDSA). The thesis provides an explanation of the principle of the LLL algorithm and especially considers the HNP from a theoretical point of view, proposes …více

Klíčová slova
BKZ bodová mříž dolní celá část Gramova–Schmidtova ortogonalizace kryptoanalýza LLL algoritmus modulární problém osamělého běžce problém skrytého čísla (HNP) cryptanalysis floor function Gram–Schmidt process hidden number problem (HNP) lattice LLL algorithm lonely runner conjecture modular
Zadání práce
Bezpečnosť digitálnych podpisov vytvorených algoritmami ako DSA, ECDSA a pod. je spojená s neznalosťou bitov náhodne generovaného nonce-u. Ak útočník pozná aspoň jeden bit (prípadne menšiu časť) pre každý podpis, je možné transformovať hľadanie použitého súkromného kľúča Pr na riešenie takzvaného HNP (Hidden Number Problem). Riešiť HNP možno pomocou LLL algoritmu, kde veľkosť príslušnej matice závisí na veľkosti súkromného klúča a je typicky rádovo v stovkách bitov. LLL je všeobecný algoritmus na hľadanie krátkych vektorov v mriežke (lattice). Cieľom práce je upraviť vstupnú maticu a prípadne upraviť algoritmus, aby nájdenie príslušného súkromného klúča bolo čo najefektívnejšie. 1. Študent si naštuduje problematiku SVP (Shortest Vector Problem), LLL algoritmu a HNP. 2. Empiricky porovná rôzne algoritmy na riešenie SVP (LLL, BKZ, alternatívy) na mriežkach zodpovedajúcich HNP. 3. Vyberie vhodný algoritmus a upraví vhodne príslušný vstup, aby nájdenie súkromného kľúča bolo čo najefektívnejšie.
Administrativní informace
Práce zkontrolována:
27. 5. 2021 09:06, Mgr. Marek Sýs, Ph.D., učo 232886
Plný text práce
557,9 KB / soubor PDF
Přílohy (9)
Jazyk práce
čeština čeština
Termín obhajoby
29. 6. 2021
Práce byla úspěšně obhájena

Vedoucí

Mgr. Marek Sýs, Ph.D., učo 232886
KPSK FI MU

Oponent

RNDr. Vojtěch Suchánek
KPSK FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.