Sonlu cisimler üzerinde tanımlı bazı özel tipteki indirgenemez polinomların karşılıkları ve kriptografik uygulamaları
Correspondences and cryptographic applications of certain type of irreducible polynomials over finite fields
Yazar: MELEK ÇİL
Danışman: PROF. DR. BARIŞ BÜLENT KIRLAR
Süleyman Demirel Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı / Cebir ve Sayılar Teorisi Bilim Dalı
Derece: Doktora, 2024
Konu: Matematik = Mathematics
Dizin: Açık anahtarlı kripto sistemler = Public key cryptosystems

Özet:
Sonlu cisimler üzerinde tanımlı polinomların indirgenemezliği ve indirgenemez polinomların üretilmesi hem teorik açıdan hem de özellikle kriptografi ve kodlama teorisi gibi uygulamada kullanımı açısından önemli bir rol oynar. Literatürde, indirgenemez polinomların inşa edilmesi için bazı yöntemler olmasının yanı sıra,indirgenemez polinomların kullanıldığı bir çok şifreleme şeması da bulunmaktadır. Bu tez çalışmasında ulaşılmak istenen hedeflerden birincisi, karşılık gelme metodu olarak adlandırılan sonlu cisimler üzerinde tanımlı belirli tipteki indirgenemez polinomlardan yine sonlu cisimler üzerinde tanımlı indirgenemez polinomlar üretmektir. Diğeri ise, üretilen indirgenemez polinomları ve benzerlerini kullanarak sonlu cisimler üzerinde tanımlı lineer yineleme bağıntılarının değişmelilik yasası özelliğine dayanan yeni bir şifreleme şeması önermektir. Bu bağlamda, ilk olarak \F_{q^2} sonlu cismi üzerinde ele alınan k tek olmak üzere k-inci dereceden belirli tipteki indirgenemez bir polinoma karşılık gelen \F_q sonlu cismi üzerinde yine k-inci dereceden indirgenemez bir polinom üretilmiştir. Çift taraflı olarak çalışan bu önermenin elde edilebilmesi için \F_{q^2} sonlu cismi üzerinde tanımlanan indirgenemez polinomun kökleri ve bazı cebirsel özellikler kullanılarak \F_q sonlu cismi üzerinde lineer denklem sistemleri elde edilmiş ve bu sistemlerin çözümleri vasıtasıyla \F_q sonlu cismi üzerindeki indirgenemez polinomun katsayıları belirlenmiştir. Ayrıca, elde edilen bu sonucun literatürdeki benzer çalışmaları kapsadığı gösterilmiştir. Daha sonra, sonlu cisimler üzerinde tanımlı üretilen indirgenemez polinomları ve benzerlerini kullanarak kriptografide bir uygulama olarak, k > 2 için \F_q sonlu cismi üzerinde k-inci dereceden lineer yineleme bağıntısının değişmelilik yasasına dayanan yeni bir şifreleme şeması önerilmiştir. Bu şifreleme şeması, e-posta gibi durumlarda kullanışlı olan alıcının çevrimiçi olmak zorunda olmadığı bir geçici-statik şifreleme şemasıdır. Önerilen şifreleme şemasının güvenliği, bazı LFSR problemlerini çözmenin zorluğuna dayanmaktadır. Aynı zamanda, bu şifreleme şeması semantik anlamda güvenlik özelliğine de sahiptir. Bunun yanı sıra, önerilen şifreleme şemasının, şifreleme ve şifre çözme prosedürlerinden gelen \F_q sonlu cismi üzerinde herhangi bir çarpma maliyeti yoktur. Önerilen şifreleme şemasının benzer yapıdaki algoritmalarla kıyaslaması k = 3 için detaylıca yapılmıştır. Son olarak, k > 2 için önerilen şema ile aynı güvenliğe sahip, Lucas ve Fibonacci dizilerinin değişmelilik yasası kullanılarak k = 2 için benzer bir şifreleme şeması önerilmiştir.

Abstract:
Irreducibility of polynomials and construction of irreducible polynomials over finite fields have played an important role both in their theoretical importance and in their applications, especially in cryptography and coding theory. In the literature, in addition to some methods for constructing irreducible polynomials, there are also many encryption schemes using irreducible polynomials. The first goal to be achieved in this thesis is to produce irreducible polynomials defined on finite fields from certain types of irreducible polynomials defined on finite fields, called correspondence methods. The other is to propose a new encryption scheme based on the commutative law property of linear recurrence relations defined on finite fields, using the generated irreducible polynomials and the like. In this context, firstly, for an odd integer k, a k-th degree irreducible polynomial was produced on the finite field \F_{q^2} which corresponds to a k-th degree irreducible polynomial of a certain type on the finite field \F_q. In order to obtain this double-sided proposition, a system of linear equations on the finite field \F_q was obtained by using the roots of the irreducible polynomial over \F_{q^2} with some algebraic properties and the coefficients of the irreducible polynomial over \F_q were determined through the solutions of these systems. Additionally, it has been shown that this result covers similar studies in the literature. Later, a new encryption scheme based on the commutative law of the k-th order linear recurrence relation on the finite field \F_q for k > 2 was proposed as an application in cryptography, using the generated irreducible polynomials defined on finite fields and the like. This encryption scheme is an ephemeral-static encryption scheme where the recipient does not have to be online, which is useful in situations such as email. The security of the proposed encryption scheme is based on the difficulty of solving some LFSR problems. It has also the property of semantic security. Besides, the proposed encryption scheme does not have any multiplication cost on the finite field \F_q from the encryption and decryption procedures. The proposed encryption scheme was compared with algorithms of similar structure for k = 3. Finally, a similar encryption scheme has been proposed for k = 2 using the commutative law of Lucas and Fibonacci sequences, which has the same security as the proposed scheme for k > 2.