Discrete trigonometry in finite fields: foundations and cryptographic application

Abstract

This thesis investigates the construction of trigonometric functions within finite fields with the purpose of application in an attack on the discrete logarithm problem (DLP) of cryptographic protocols. While the concept of discrete trigonometric functions has previously been studied as part of Fourier Analysis, this work seeks to extend the framework to a cryptographic setting. The motivation stems from a well-known algorithm for the DLP, whose difficulty derives from an inefficiency in selecting between the two roots of a quadratic residue. We use Euclidean Geometry and Finite Field Theory to set up formal definitions by mimicking the exponential definitions of sine and cosine, consider geometric interpretations and examine for the extent to which trigonometric identities from the complex plane carry over to finite fields. Furthermore, we provide numerical examples from Z*37 for illustration. The attack to the DLP is reduced to selecting an element i that could both mimic the imaginary unit as well as serve in the selection between two roots in the DLP algorithm.Η εργασία αυτή ερευνά τη δημιουργία τριγωνομετρικών συναρτήσεων σε πεπερασμένα πεδία με σκοπό τη δημιουργία επίθεσης στο πρόβλημα διακριτού λογαρίθμου των κρυπτογραφικών πρωτοκόλλων. Η δημιουργία τριγωνομετρικών συναρτήσεων έχει μελετηθεί πρωγενέστερα στο πλαίσιο της Ανάλυσης Fourier, ωστόσο εδώ γίνεται προσπάθεια επέκτασης στα πλαίσια της κρυπτογραφίας. Το κίνητρο προκύπτει από γνωστό αλγόριθμο για τον διακριτό λογάριθμο, του οποίου η δυσκολία έγκειται στην επιλογή ανάμεσα στις δύο ρίζες ενός τετραγωνικό υπόλοιπου. Χρησιμοποιούμε Ευκλέιδια Γεωμετρία και Θεωρία Πεπερασμένων Πεδίων για να γράψουμε αυστηρούς ορισμούς μιμούμενοι των εκθετικών ορισμών του ημιτόνου και του συνημιτόνου, θεωρούμε γεωμετρικές ερμηνείες των ορισμών και μελετάτε την μεταφορά τριγωνομετρικών ταυτοτήτων από την κλασική ανάλυση στα πεπερασμένα πεδία. Επιπλέον, παρέχουμε παραδείγματα από το Ζ*37. Η επίθεση στον διακριτό λογάριθμο συνοψίζεται στην επιλογή στοιχείου i του πεπερασμένου πεδίου το οποίο φέρει ιδιότητες της φανταστικής μονάδας ενώ παράλληλα εξυπηρετεί στην επιλογή ανάμεσα στις δύο ρίζες του τετραγωνικού υπολοίπου.