On the trace based public key cryptosystems over finite fields

Abstract

Bu tezde, iz tabanli Açik Anahtarli Kriptosistemler (AAK), teorik ve uygulama bakis açilarindan incelenmistir. Henüz üzerinde çok durulmamis olanlar için de kriptografik protokoller tanitilmistir. Besinci dereceden özyinelemeli bagintilar için, iyilestirilmis, iz tabanli üs alma yöntemi tanitacagiz. Ayrik Logaritma Problemi (yani verilen $y=/alpha^x$ ve $</alpha>=G/subset /F_q^*$ degerleri için $x$'i hesaplama problemi) tabanli Açik Anahtarli Kriptosistemler 1970'lerden beri çalisilmaktadir. Bu AAK çalismalarini mümkün kilan arka kapili fonksiyon $f:/Z_/ell/rightarrow G=</alpha>/subset /F_q^*$, $f(m)=/alpha^m$'in bir grup homomorfizmasi olmasi olmustur. Bunun sayesinde, Diffie-Hellman (DH) tipi anahtar degisim, ElGamal tipi mesaj sifreleme ve Nyberg-Rueppel tipi sayisal imza protokolleri mevcuttur. Arka kapili $f(m)=/alpha^m$ fonksiyonu üzerine kurulu kriptosistemler iyi anlasilmis ve eksiksizdir. Buna ragmen, $f:/Z_/ell/rightarrow G$, $f(m)/rightarrow Tr(/alpha^m)$, $G=</alpha>/subset /F_{q^k}^*,/; k/ge 2$ seklinde, kriptografik bakis açisina göre daha fazla önemsenmesi gereken baska bir arka kapili fonksiyon daha vardir.Literatürde, $f(m)=Tr(/alpha^m)$'i hesaplamak için etkili algoritmalar üzerine çalismalar vardir ancak bunlar protokolleri önemsememektedir. Ayrica, $Tr(/alpha^m)$'i etkili bir sekilde hesaplamak için ugrasan ve protokolleri de gözönüne alan çalismalar da mevcuttur. Bu tezde, bu çalismalarla birlikte önceden üzerinde durulmamis bazi protokoller de çalisilmistir. Ve Besinci dereceden özyinelemeli bagintilar için iz tabanli üs alma yöntemi iyilestirilmistir.

In this thesis, the trace based Public Key Cryptosystems (PKC) are explored from theoretical and implementation point of view. We will introduce cryptographic protocols for the ones they are not discussed yet. We introduce improved trace based exponentiation algorithm for fifth degree recursive relation.The Discrete Log Problem (DLP), that is computing $x$, given $y=/alpha^x$ and $</alpha>=G/subset /F_q^*$, based Public Key Cryptosystems (PKC) are being studied since late 1970's. Such development of PKC was possible because of the trapdoor function $f:/Z_/ell/rightarrow G=</alpha>/subset /F_q^*$, $f(m)=/alpha^m$, is a group homomorphism. Due to this fact, we have Diffie Hellman (DH) type key exchange, ElGamal type message encryption, and Nyberg Rueppel type digital signature protocols. The cryptosystems based on the trapdoor $f(m)=/alpha^m$ are well understood and complete. However, there is another trapdoor function $f:/Z_/ell/rightarrow G$, $f(m)/rightarrow Tr(/alpha^m)$, where $G=</alpha>/subset /F_{q^k}^*,/; k/ge 2$, which needs more attention from cryptographic protocols point of view. There are some works for a more efficient algorithm to compute $f(m)=Tr(/alpha^m)$ and not wondering about the protocols. There are also some works dealing with an efficient algorithm to compute $Tr(/alpha^m)$ as well as discussing the cryptographic protocols. In this thesis these works are studied along with introduction of some protocols which are not discussed earlier and trace based exponentiation for fifth degree recursive relation is improved.