İkili kuadratik form  ̇ile grup kimlik doğrulaması
Group authentication with binary quadratic form
Yazar: FİLİZ AKSOY
Danışman: PROF. DR. ENVER ÖZDEMİR ; DOÇ. DR. ÖZEN ÖZER
İstanbul Teknik Üniversitesi / Lisansüstü Eğitim Enstitüsü / Bilişim Uygulamaları Ana Bilim Dalı / Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
Derece: Yüksek Lisans, 2023
Konu: Bilim ve Teknoloji = Science and Technology
Dizin: Asimetrik algoritmalar = Asymmetric algorithms ; Grup kimliği = Group identification ; Haberleşme =   ; Kriptoloji = Cryptology ; Kuadratik formlar = Quadratic forms

Özet:
Kriptoloji, dijital ortamda taraflar  arasında güvenli iletişimin gerçekleşmesi için  gerekli algoritma ve protokol dizaynını amaç edinen bilim dalıdır. Sanal ortamdaki herhangi bir veri akışının güvenliği kriptografik temel taşlar ile sağlanır,  Günümüzde teknolojinin gelişmesi ve internetin yaygınlaşması ile bilgi paylaşımı da kritik bir önem kazanmakta ve güvenli bilgi paylaşımı için sürekli yeni modeller geliştirilmektedir.
Kriptografi biliminin amacı yalnızca mesajları şifreleme ve deşifre  algoritmaları geliştirmek değil, aynı zamanda bilgi güvenliği gerektiren gerçek dünya sorunlarını çözüme kavuşturmayı sağlamaktır. Diğer bir deyişle sanal ortamda akan verilerin güvenli transferini sağlayacak uygun yapıtaşları hazırlamaktır. Bu yapıtaşların uygunluğu birçok faktöre bağlıdır. Mevcut donanım yapısına ve kullanıcıların beklediği veri akış hızına uygunluğu en öncelikli hedefler arasındadır. Dijital ortamdaki haberleşmenin güvenliği önceden belirlenen dört hedefin sağlanması ile mümkün olabilmektedir.  Bu hedeflerin ilki mesajın gizliliği olarak ifade edilen gizlilik (confidentiality) kavramıdır. Mesajın karşı tarafa güvenli bir şekilde iletilmesi için tasarlanan  algoritmaların ana amacı mesajın üçüncü taraflar tarafından okumasını engellemektir. Dijital ortam herkes tarafından görülebilir kabul edilmektedir. Dolayısı ile yalın halde gönderilecek bir mesaj herkes tarafından okunabilecektir. Mesajın sadece önceden belirlenen alıcılar tarafından okunabilmesi güvenli haberleşmenin en önemli öğelerinden biridir. Bir diğer amaç ise veri bütünlüğü (data integrity) yani mesajın içeriğinin değişmesini önlemektir. Mesajın içeriği iletim esnasında oluşabilecek hatalardan veya araya giren kişilerden  kaynaklı değişikliğe uğrayabilmektedir. Bu tür manipülasyon ve değişimleri engellemek için genellikle özet (hash) fonksiyonları kullanılmaktadır. Güvenli haberleşmenin sağlaması gereken amaçlardan bir diğeri ise kimlik doğrulama (authentication), yani mesajın kaynağının ve alıcının doğrulanmasıdır. Bunun için mesajı oluşturan kişi ve zaman damgası gibi bilgileri içeren dijital imza gibi yöntemler kullanılmaktadır. Son olarak ise gönderilen mesajın gönderici tarafından inkar edilememesi (Non-repudiation), yani mesajı gönderenin mesajı kendisinin göndermediğini iddia edememesidir. Dijital imza gibi yöntemler kimlik doğrulaması ile birlikte mesajı gönderenin inkar etme durumunu da ortadan kaldırmaktadır.
Güvenli haberleşmenin en önemli sac ayağı gizlilik simetrik kriptografik algoritmalar ile sağlanmaktadır. 1974 ten günümüze kadar nerdeyse tüm dijital haberleşme kanalları standart olan simetrik anahtarlı algoritmaları kullanmaktadır. Simetrik anahtarlı kriptografik sistemlerde gönderen ve alıcı taraflarının her ikisi de aynı anahtara sahip olmak zorundadır. Her ne kadar gizlilik standart simetrik şifreleme metotları ile sağlanıyor olsa da, tarafların aynı anahtarı elde etmesi en önemli problem halini almaktadır. Tarafların anahtar paylaşımı yapmadan önce birbirlerinin kim olduklarını tespit etmesi yani kimlik doğrulama yapması beklenmektedir. Kimlik doğrulama sonrasında anahtar değişimi yapılmaktadır. Kimlik doğrulama ve anahtar değişimi algoritmaları şu ana kadar sadece bir alıcı ve bir göndericinin olduğu ortamları göz önünde bulundurarak dizayn edilmiştir. Fakat günümüzde artık haberleşme birebir değil onlarca hatta binlerce aletin aynı anda veri alış verişi yaptığı iletişim sistemlerinden oluşmaktadır. Mesela nesnelerin interneti (Internet of Things - IoT) gibi teknolojilerin de gelişmesi ile hem aynı anda bir çok aynı amaç için kullanılan aletler hızlı kimlik doğrulaması ve anahtar değişimi yapması gerekmektedir. Veri akışı her bir aletten diğerlerine gittiği için ortamda bulunan onlarca belki de binlerce aletin her biri için kimlik doğrulaması yapması ve anahtar paylaşımı yapması beklenmektedir. Ayrıca, iletişim ağına dahil olan tüm cihazların teknik kapasitelerinin aynı olmadığı düşünüldüğünde düşük işlemcili cihazları da destekleyen bir modele ihtiyaç günden güne artmaktadır. Daha fazla cihazın veri akış trafiğine dahil olacağı beklenildiğinden, kısa süre içerisinde çoklu kimlik doğrulama ve çoklu ortam için etkin anahtar değişimi algoritmalarının daha fazla ihtiyaç haline geleceği açıktır.  Bu çoklu ortamlar için  etkin  kimlik doğrulama algoritması geliştirilecektir. Bunun yanında pratikte kullanılabilecek anahtar belirleme algoritmasında sunulacaktır. Sunulan algoritmaların performans değerleri analiz edilecek ve kripto analizleri yapılarak güvenlik parametreleri sunulacaktır. Dizayn edilen algoritmalarda yeni bir matematiksel aygıt kullanılacaktır. Bu aygıt uzun zamandır sayılar teorisi alanında bilinen  ikili kuadratik formlardır.
İlk bölümde kriptografiye kısa bir giriş yapılarak, simetrik ve asimetrik anahtar algoritmalarının temel yapıtaşları ve bu algoritmaların güvenilirliğinden örneklerle bahsedilecektir. Mevcut kriptografik yapıtaşlarının güvenli haberleşmede istenilen özellikleri sağlamada nasıl kullanıldığı örneklendirilecektir. Bu bağlamda elektronik posta servislerinin güvenliğini sağlayan en önemli protokollarden PGP uygulamasından bahsedilecek ve yapıtaşların etkin bir şekilde kullanımına örnek verilecektir. 
İkinci bölümde ise, birebir kimlik doğrulama ve grup kimlik doğrulama detaylı olarak anlatılacaktır. Daha sonra son zamanlarda çoklu kimlik doğrulama ve çoklu anahtar paylaşımı için dizayn edilmiş grup kimlik doğrulaması üzerine yapılan çalışmalardan bahsedilecektir. 
Üçüncü bölümde sunacağımız grup kimlik doğrulama ve anahtar değişimi algoritmaları için matematiksel yapıtaşları olan ikili kuadratik formlardan detaylı bahsedilecektir. İkili kuadratik formlar, primitif formlar, pozitif belirli formlar, kuadratik formların denkliği, denklik sınıfı, indirgenmiş formlar bu bölümde anlatılmaktadır.
Üçüncü ve son bölümde ise, ikili kuadratik form ile grup kimlik doğrulama için önerilen modelin detayları ve teorik performansının diğer grup kimlik doğrulama modelleri ile karşılaştırılması yer almaktadır.

Abstract:
The word cryptography is derived from the Greek word "kryptos", meaning "hidden". The purpose of cryptography is not to hide the existence of a message, but to obscure its meaning through a process known as encryption. From the past to the present, cryptology has been used by military units, governments, and diplomatic services as a tool to protect national secrets and strategies. Today, especially with the development of technology and the widespread use of the internet, information security has gained critical importance and its use has become widespread in the private sector. One of the most basic requirements for banks, financial institutions, and institutions responsible for the protection of personal data has been the security of information. While cryptography is the study of the development of new mathematical techniques to apply security for communication, cryptanalysis covers the studies of hacking algorithms and testing the reliability of the developed algorithm. On the other hand, cryptology is defined as the main science that covers both cryptography and cryptoanalysis.
The purpose of cryptography is not only to develop algorithms for the encryption and decryption of messages but also to solve real-world problems that require information security. So, the four main objectives of cryptography can be listed as follows. The first goal is confidentiality, which is expressed as the confidentiality of the message. The encryption algorithm is designed for the secure transmission of the message to prevent adversaries from reading the message. Another purpose is to prevent the manipulation of the message to provide data integrity. The content of the message may change due to errors that may occur during transmission or from people who change the original message called as plaintext. Hash functions are generally used to prevent such manipulations and changes. Another purpose of cryptology is authentication, that is, the verification of the source of the message. Some methods such as digital signature, which contains information such as the person who created the message and the timestamp, are used. The last purpose of cryptography is Non-repudiation. That is, the sender cannot deny the creation of the message. Methods such as digital signature eliminate the denial of the message sender along with authentication.
User authentication is a critical security service in computer and communication applications. There are two popular approaches for the one-to-one type of authentication: knowledge-based authentication (e.g., passwords) and key-based authentication (e.g., public/private key). In the one-to-one type of authentication, the prover interacts with the verifier to verify the identity of the prover. They have some disadvantages. For example, if the simple and short key is used for knowledge-based authentication, it can be easily cracked by hackers. On the other hand, for key-based authentication, a certificate authority (CA) is needed to provide the authenticity of the public keys. Also, because key-based authentication security is based on large integers, the computational overhead is the main concern.  
With the spread of the Internet and the increase in network communication, the communication of many-to-many at the same time has become essential. Group communication goes beyond both one-to-one communication (i.e., unicast) and one-to-many communication (i.e., multicast) and covers many-to-many communication. In group-oriented applications, the members of the group want to communicate with themself via a private network. To settle such a network, all users can authenticate other users who are members of the same group. To provide group authentication services in such applications, there are two popular approaches. The first one needs a central authentication server (AS) that manages the access rights of the network. The second model doesn't include AS. The purpose of group authentication means authenticate all users at once, so it is specially designed for group-oriented applications. 
Group authentication consists of two phases. The first one is initiation. In these phases, the group manager is responsible to register all group members initially. The second one is the authentication phase. In this phase, all users participated in the group authentication work together without the assistance of the GM to authenticate each other.
With the development of technologies such as the Internet of Things (IoT), it is necessary for many group members to be authenticated quickly and communicate securely within the group at the same time. In addition, considering that the technical capacities of all devices included in the network are not the same, the need for a model that supports low-processor devices is increasing day by day. It is clear that this will become more essential in the future. So, we worked on a different approach and used Binary Quadratic Forms to perform secure group authentication with actable performance.
Binary quadratic forms have been rigorously investigated since the time of Gauss and it is a subject that is related to various areas in the general area of number theory. We define a binary quadratic form as a degree 2 homogeneous polynomial with integer coefficients:
$$f(x,y)=ax^2+bxy+cy^2$$  
The binary quadratic forms have been employed in factorization problems and used as an ingredient in public key cryptographic algorithms. Even though these applications had success to a certain degree, the cost of group operation in the group of binary quadratic forms presents a strong drawback for such applications. Computing in a class group with binary quadratic forms has more advantages over ideals in a quadratic field but still a single operation requires several multiplications and divisions. On the other hand, the cost of operations might be reduced in one uses binary quadratic forms with relatively small discriminants. In this work, we are going to present a kind of public key algorithm with binary quadratic forms of the positive definite forms. The nature of the algorithm allows for utilizing forms with small discriminants in certain cases. A recently emerged authentication method, group authentication, seems to have various applications, especially in the IoT realm. The devices being in the same geographic area form a group and authentication is performed among the members and with an assigned group manager. The algorithm is handy, especially in situations that require frequent authentications of a larger number of devices.
In this thesis, we proposed a new algorithm of group authentication for groups that have a large number of members. This algorithm allows the authentication of all members simultaneously. Binary quadratic forms which represent the same group have been used for group authentication. For the security of the algorithm, the discriminant has been chosen as a large prime number.
In chapter 1, we will mention the primitives of cryptography. Detailed information is given about the symmetric and asymmetric key algorithms with examples. Also, Pretty Good Privacy - PGP application which is based on hybrid (symmetric and asymmetric) key algorithms and is used to secure in sending emails is explained.
In chapter 2, one-to-one authentication and group authentication are explained in detail. At the same time, the studies on group authentication are mentioned.
In chapter 3, binary quadratic forms, which are based on our proposal, are explained. Binary quadratic forms, primitive forms, the reduction of positive definite forms, and the representation and composition of the forms are shown.
In chapter 4, our proposal, the group authentication with binary quadratic form, is detailed. Also, the results are compared with the other group's authentication results.
In the last Chapter, the conclusion of our proposal and the performance results are discussed. The advantages and the disadvantages of our proposal are listed and explained in detail.