Kuantum bilgisayarlarda polinom interpolasyonu ile anahtar dağıtımı
Key distribution with polynomial interpolation in quantum computers
Yazar: BERRAK UZUN
Danışman: DOÇ. DR. ERGÜN YARANERİ ; DOÇ. DR. ENVER ÖZDEMİR
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Mühendisliği Ana Bilim Dalı / Matematik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2020
Konu: Matematik = Mathematics

Özet:
Bu çalışmada, kuantum bilgisayarlarda gönderici ve alıcı arasında anahtar paylaşımının güvenli ve hatasız bir şekilde paylaşan algoritmaların detaylı analizi amaçlanmıştır. Bu paylaşım, Newton bölünmüş farklar polinom interpolasyon yöntemi kullanılarak sağlanmaya çalışılmıştır. Yeni çıkartılan kuantum anahtar değişim algoritması birçok yönden incelenmiş, gerçeklenmiş ve geliştirilmesine yönelik tavsiyeler ortaya konmuştur.
Birinci bölüm giriş bölümü olup, teknolojinin gelişimi, kriptolojiye ait bilgiler ve kuantum kriptografinin amaçlarından bahsedilmiştir.
İkinci bölümde kriptolojiye ait terminolojik terimler, klasik şifreleme algoritması olan Sezar şifreleme ve modern şifreleme algoritmalarından asimetrik ve simetrik şifrelemelere ait açıklamalarda bulunulmuştur.
Üçüncü bölümde kriptoloji biliminin asal sayılar, sonlu cisimler ve modüler aritmetikle iç içe olmasından dolayı sonlu cisimlere ait bilgiler ve sonlu cisimler üzerinde polinom işlemleri açıklanmış ve bu çalışmada da sıklıkla kullanılan modüler aritmetikte ters alma işleminin kullanımlarına ilişkin bilgiler verilmiştir.
Dördüncü bölümde klasik bilgisayar ile kuantum bilgisayarlara ait bilgiler ele alınmıştır ve çalışma şekillerine ait bilgilere yer verilmiştir.
Beşinci bölümde kuantum bilgisayarlarda anahtar dağıtımı için tasarlanan ilk protokol olan BB84 protokolünden bahsedilmiş ve kuantum kriptografide hata düzeltme protokolü olan Cascade protokolüne dair bilgiler yer almaktadır.
Altıncı bölümde, beşinci bölümde ele alınan Cascade protokülünün eksiklerine dayanarak gizli anahtarın güvenli bir şekilde paylaşılması için polinom interpolasyonu kullanıldığı belirtilip, Newton bölünmüş farklar yöntemi ile polinom interpolasyonundan bahsedilmiştir. Kuantum bilgisayarlarda anahtar değişiminde polinom interpolasyonunun nasıl kullanıldığı hakkında bilgiler verilip protokolün güvenlik analizi yapılmıştır. İmplementasyonda, (x_1,f_1 ),(x_2,f_2 ),…,(x_n,f_n )  değerleri kullanılarak r<(n-2) olmak üzere r. dereceden polinom elde edilmiştir. Fakat bu algortimanın çalışabilmesi için kullanılan noktalar dışında en az bir adet noktanın karşı tarafa doğru ulaşması gerekmektedir. Bu polinomun sonuçlarıyla gerçek polinomun sonucu karşılaştırılmış olup doğruluk değeri yüzde cinsinden hesaplanmıştır. Hesaplanan doğruluk değeri istenilen doğruluk değerinden büyükse algoritma sonlandırılır. Aksi durumda yeni x değerleri kullanılarak polinom elde edilip doğruluk değerine tekrar bakılır ve doğruluk değeri istenilen doğruluk değerinden büyük olana kadar işleme devam edilir. İşlem sonunda hangi x noktasının hatalı olduğu tespit edilir.
Bu çalışmanın yapılmasının amacı kuantum fiziği yasaları ve kuantum kanallarındaki fotonların fiziksel özelliklerinden dolayı anahtar iletimi esnasında anahtarın değişime uğramasından veya araya giren bir kişinin anahtar ile ilgili bilgileri ele geçirmesinden dolayı gerçekleşecek sorunların giderilmesidir. Bu implementasyonda programlama dili olarak C tercih edilmiştir.

Abstract:
The person holding the information or the impact on the vital activities of institutions determine the value of information. For example, for the sake of security and continuity in terms of states, the national intelligence convert data into information and protect the information in the best way. To protect data is requied to aware of possible threat. Threatening security information elements is grouped in 4 topics such as information loss (security breach), information changes (violation of integrity) and handled by someone else passages (violation of privacy). 
Cryptology deals with the confidentiality, integrity, authentication and nonrepudiation of information. Confidentiality means that information cannot be understood by unauthorised people. Integrity for an entire connection or for a single piece of data, no modification, insertion, rearrangement, as the message was not guaranteed. Authentication, guarantee that the sender of the transmitted message is actually the sender. The nonrepudiation is that the recipient or the sender cannot deny the transmitted message. So that when a message is sent, the recipient can prove that the sender has sent the message, and the sender can prove that the recipient has received the message.
As the Internet network expands, elements that threaten information security have become more intimidating. The development of new methods and technologies for information security or the improvement of existing ones has become a constant cycle of need.
When this continuous need cycle is examined, it is seen that cryptology is mostly used in military and diplomatic fields from past to present. Today, communication channels, debit transactions, credit card applications, internet browsing, e-commerce and e-government applications, mobile phones, billing systems, city networks, missile systems, transportation tools etc. have used cryptology.
Because of the extent of the areas of cryptology is the growing and differentiating threats against information security. This situation has triggered a growing network of internet. Elements of this threat people, institutions and nations.
In order to ensure that the information is shared, it is necessary to know who is communicating with, to ensure that the information is sent correctly or completely to the other party and not to be monitored by others. In order to accomplish all this, components which are the most fundamental elements of cryptography science are designed. A variety of encryption and decryption algorithms developed through cryptography science in order to send and receive data securely. No matter how complex the encryption algorithm is, when the key used in encryption is seized, the password does not matter. Therefore, the most important examination of cryptology is the transmission of the key and the protocols used in key transmission.
Numerous algorithms have been developed for key transmission used in encryption. However, these algorithms are not absolutely safe. Quantum cryptography provides this security for now, the key between the receiver and the transmitter makes the exchange rule safe. The technique of quantum cryptography is based on Heisenberg's uncertainty principle, a fundamental law of physics. According to this principle, two properties of a photon, which is the basic element of quantum mechanics, cannot be known at the same time. This makes it impossible to clone a photon in the communication channel.
In this study, it is aimed to analyze the algorithms that share the key safely and correct sharing between sender and receiver in quantum computers. These sharing algorithms are tried to be achived by using Newton divided differences polynomial interpolation method. In this quantum key exchange algorithm has analyzed in every aspect and implemented.
Improvement of the technology, informations about cryptology and purposes of quantum cryptography have explained at the first chapter. 
In the next chapter, it has been explained that terminological terms which belong to cryptology such as plaintext, ciphertext, encryption, decryption and key. On the other hand, classic and modern encryption algorithms have examined. The modern encryption algorithm is divided into two. For example, Caesar algorithm as classical encryption algorithm, AES algorithm as symmetric encryption algorithm and RSA algorithm as asymmetric encryption algorithm and their properties are mentioned. Then the diffee-helman algorithm, which is the key exchange algorithm, is explained.
At third chapter, because of cryptography being related with prime numbers, finite field and modular aritmetics some knowledge has given such that information about finite field, polynomial calculation on finite field and modular inverse.
After third chapter, information about the properties and working methods of classical and quantum computers have given. The main difference between classical and quantum computers is working principle, classical computers use bits (0 or 1), quantum computers use qubits. Quantum computers have parallel process properties; therefore, it is working fast with respect to classical computers.
At fifth chapter, information about quantum key distribution and quantum channel are given. There are two channels on communication, one of channels is classical chanel and the other one is quantum channel. The quantum channel is used for key sharing. All other steps are performed on the classical channel. The first protocol designed for key distribution in quantum computers, the BB84 protocol, has mentioned and include information about the Cascade protocol, the error correction protocol.
At sixth chapter, Newton divided difference polynomial interpolation has used for sharing secret key safely contrast to lack of security in cascade algorithm. Information has given about how polynomial interpolation is used in key exchange in quantum computers and the security analysis of the protocol has performed. It has explained that how to implement Newton divided difference polynomial interpolation and security analyze. (x_1,f_1 ),(x_2,f_2 ),… ,(x_n,f_n ) values have used for fitting r^th degree polynomial for all r<(n-2). One value must transmit perfectly except used values for interpolation to work algorithm properly. And then, percent accuracy is calculated with respect to difference between polynomial interpolation and real values receiving from channel. The algorithm is running unless percent accuracy is big enough. End of the algorithm, place of wrong number is detecting and correcting for secure communication. Besides, quantum key sharing protocol has investigated from the point of security analysis. For Eve obtain the key, Eve must perform a brute-force attack. For security analysis, it is determined that the quantum and classical computers perform brute force attack according to the key length. The main reason for error in transmitting number is physical properties of quantum which is interrupted by Eve. C programming language is used for implementation.