Original title:
Smartův algoritmus
Translated title:
Smart's algorithm
Authors:
Sladovník, Tomáš ; Příhoda, Pavel (advisor) ; Šťovíček, Jan (referee) Document type: Bachelor's theses
Year:
2015
Language:
cze Abstract:
[cze][eng] Problém diskrétního logaritmu je jedním z pilířů asymetrické kryp- tografie a jeho použití na eliptických křivkách nad konečným prvočíselným tělesem se jeví jako velice efektivní. Tato práce se zabývá jeho řešením na eliptických křivkách, jejichž velikost je rovna velikosti onoho tělesa. Cílem této práce je se- stavit funkční algoritmus, který bude schopen řešit tento problém v lineárním čase podle počtu grupových operací a ověřit jeho správnost. K vytvoření algo- ritmu je potřeba pracovat s p-adickými čísly, zavést základy teorie formálních grup, formálního logaritmu a zavést podgrupy eliptických křivek nad p-adickými čísly. Ukáže se, že použití tohoto typu křivek je pro kryptografické účely naprosto nevhodné, a že tyto křivky nejsou bezpečné. 1The discrete logarithm problem is one of the most common trap- door functions in asymmetric cryptography and the use of elliptic curves over a finite field with prime characteristics seems to be a very efficient platform. This paper addresses the solution of a special type of elliptic curves where the number of points is equal to the characteristic of a field. Our goal is to construct a linear algorithm in goup operations and prove correctness. In order to create the algorithm, we will implement p-adic numbers, introduce the theory of formal groups and the formal logarithm and subgroups of an elliptic curve over the field of p-adic numbers. We will show that this type of curves is absolutely useless for cryptography because these curves are not safe. 1
Keywords:
discrete logarithm problem; elliptic curves; formal group; formal logarithm; p-adic numbers; eliptické křivky; formální grupa; formální logaritmus; p-adická čísla; problém diskrétního logaritmu
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/79664