RSA ve ELGAMAL kısmi homomorfik kripto sistemlerin vergi ödeme sistemine uygulanması ve bu uygulamaların performans analizleri
Application of RSA and ELGAMAL partial homomorphic crypto system to tax payment system and performance analysis of these applications
Yazar: HASAN ÇETİNKAYA
Danışman: DOÇ. DR. ENVER ÖZDEMİR
İstanbul Teknik Üniversitesi / Bilişim Enstitüsü / Bilişim Uygulamaları Ana Bilim Dalı / Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Açık anahtarlı kripto sistemler = Public key cryptosystems ; Veri şifreleme yöntemleri = Data encryption methods

Özet:
Açık anahtarlı kripto sistemlerin Diffie ve Hellman tarafından 1976'da bulunmasıyla [1], dijital verinin gizliliği önem kazanmış, özellikle internetin iş ve özel hayatta vazgeçilmez bir hâl almasıyla bu önem daha da artmıştır. Bunun sonucunda 1978'ten bu yana geçen yıllarda birçok güvenli kripto sistemler bulunmuştur. İnternet uygulamalarında, örneğin çevrimiçi (online) bankacılık sisteminde, elektronik oylama sisteminde, çevrimiçi (online) vergi ödeme sisteminde ve ayrıca özellikle son yıllarda popülaritesi artan bulut bilişimde güvenli veri iletimini sağlamanın yollarından biri homomorfik şifrelemedir.
Homomorfik kripto sistemler ilk olarak Rivest, Adleman ve Dertouzous tarafından 1978 yılında yayımlanan makalede ele alınmıştır [2]. Makalelerinde, şifreli veriler deşifre edilmeden bir birtakım matematiksel işlemler yapılabileceğini göstermişlerdir. Bu makalenin yayımlanmasıyla homomorfik kripto sistemler üzerine çalışmalar başlamıştır.
Homomorfik şifrelemenin temel amacı haberleşmedeki verilerin ve veri tabanlarında veya bulut bilişimindeki verilerin gizliliğini sağlamaktır. Geçen süre zarfında birçok çarpmaya göre homomorfik (ElGamal [3] 1984, RSA [2]) veya toplamaya göre (Paillier [4] 1999, Goldwasser- Micali 1984 [5]) kısmi homomorfik kripto sistemler geliştirilmiştir. 1991 yılında Feigenbaum yayınlamış olduğu bir makaleyle [6] tam homomorfik kripto sistemlere olan ilgi artmıştır. Makalesinde; "Acaba Enc(x+y) ve Enc(x.y)  ifadelerini Enc(x) ve Enc(y) türünden ifade eden Enc() şifreleme metoduna sahip kripto sistem geliştirilebilir mi ?" şeklindeki sorusunu 2009 yılında Craig Gentry, yayınladığı doktora tezinde ispatlamış ve kendisi tam homomorfik kripto sistemini [7] geliştirerek Feigenbaum' un sorusunu yanıtlamıştır.

Bu tezde RSA ve ElGamal açık anahtarlı kripto sistemlerine genel bir bakıştan sonra homomorfik özellikleri gösterilecek ve işbu özellikler Java programlama dilinde gerçeklenecektir. Sonrasında çevrimiçi (online) vergi ödeme sisteminde her ikisinin homomorfik uygulaması ele alınıp performans karşılaştırılması yapılacaktır. Ancak bunları daha iyi kavrayabilmek için öncelikle tezimizin ilk bölümünde "Sayılar Teorisi ve Soyut Cebirdeki Matematiksel Kavramlar konusu üzerinde durulacaktır. 

İkinci bölümde, açık anahtarlı (asimetrik) kripto sistemlerden ilki olan RSA ve ElGamal ele alınacak ve sonrasında günümüzdeki kullanım alanlarından biri olan, elektronik imzadan (e-imza) bahsedilecektir.
Üçüncü bölümde ise, tezimizin asıl konusu olan homomorfik (eş şekilli) şifrelemenin açık anahtarlı kripto sistemler için matematiksel tanımı yapılarak homomorfik şifrelemenin türleri anlatılacak ve sonrasında bunlara örnekler verilecektir. Ayrıca 2010 yılı sonrasında geliştirilen tam homomorfik kripto sistemlerden bahsedilecektir.
Tezin dört ve beşinci bölümünde ise RSA ve ElGamal'ın çarpımsal homomorfik özellikleri matematiksel olarak gösterilecek, akabinde bu özellikler Java'da gerçeklenecektir.
Tezin son bölümünde ise RSA ve ElGamal'ın homomorfik özellikleri vergi ödeme sistemine uygulanacak; her iki kripto sistemin çarpımsal homomorfik özelliklerini performans açısından karşılaştırılacaktır. Uygulamamız, değişik anahtar uzunlukları, 1024-bit, 2048-bit ve 3072-bit kullanılarak Java'da gerçeklenecek ve bu anahtarların her birinde, şifreleme, deşifreleme ve homomorfik işlemlerin toplam gecikme süreleri beş ayrı deneme yapılarak hesaplanacaktır.
Tezde yapılan araştırmada, RSA ve ElGamal açık anahtarlı kripto sistemlerin her ikisi de çarpımsal homomorfik özellikleri sağlamakta olup, yapılan karşılaştırmalar neticesinde RSA'nın daha performanslı ve kullanışlı olduğu sonucuna varılmıştır. RSA, ElGamal kripto sistemine göre, şifreleme, deşifreleme ve homomorfik işlemlerin bütününde yaklaşık 4 daha hızlı olduğu görülmüştür. Kullanılan anahtar boyutu ne olursa olsun, RSA ve ElGamal ile şifrelenen aynı metin için, ElGamal da elde edilen şifreli metin, RSA da elde edilen şifreli metinin iki katıdır. Bu da ElGamal için ayrı bir dezavantajdır. Kurumlar (tüzel kişiler) için vergi ödeme sisteminde avantajlı olan RSA açık anahtarlı kripto sistem aynı zamanda, gerçek kişiler SGK dan maaş aldıkları için vergi ödeme sistemi olarak SGK içinde uygulanabilir. Sadece K.İ.K yerine SGK kullanılarak, gerçek kişilerin ödemesi gereken vergi miktarları hesaplanabilir. Böylelikle kişilerin maaşları sadece kendileri tarafından bilinir ve ödemesi gereken vergi miktarı da ancak kendisi tarafından bilinir.

Abstract:
It is very important that personal data is only known by the authorized people. For example, it is very important to know and display the person's health information, salary information, the tender information that companies have made and the amount of tax that they need to pay. In order to ensure the privacy of these data, it must be interrogated by the web service, encryption of data in the application server, and then the mathematical operations, such as multiptication on the encrypted data must be performed on the client side.  In addition to this, decryption of ciphertext by using private key is performed on the client side. Hence, privacy of data is satisfied.
With the presentation of public key crypto systems by Diffie and Hellman in 1976 [1], the confidentiality of digital data has become more important, especially when the Internet becomes indispensable in business and private life. As a result, many secure crypto systems have been developed in the years since 1978. Homomorphic encryption is one of the ways to ensure secure data transmission in Internet applications, for example in the online banking system, keeping medical records,in the electronic voting system, in the online tax payment system, and also in the growing cloud computing, especially in recent years. The execution of transactions on the encrypted data may prevent the environment of mistrust and ensure data confidentiality. At this point, using a homomorphic encryption during processing of the data, operations can be performed without the need for decryption, and only the user can see the decrypted result of the operations. A reliable calculation chain can be created by performing different services in different companies by means of homomorphic encryption.
Homomorphic crypto systems were first discussed in the article published by Rivest, Adleman and Dertouzous in 1978 [2]. In that article, they showed that some mathematical operations can be performed without deciphering encrypted data. Studies on homomorphic crypto systems have begun with the publication of this article.
The main purpose of homomorphic encryption is to ensure the privacy of data during communication and the confidentiality of data in databases or in public cloud systems. In the meantime, several partial homomorphic crypto systems have been developed, for example methods which are homomorphic for only multiplication operation (ElGamal [3] 1984, RSA [2]) or for only addition (Paillier [4] 1999, Goldwasser-Micali 1984 [5]). With the article published in 1991 by Feigenbaum [6] the interest in fully homomorphic crypto systems increased. In that article the author asked the following question; "Is it possible to develop a crypto system with Enc() encryption function that expresses Enc(x + y) and Enc (x.y) in terms of Enc(x) and Enc(y)?". In 2009, Craig Gentry, in his doctoral thesis, proved the existence of such crypto systems, and he developed the fully homomorphic crypto system [7] and answered Feigenbaum's question.
In this thesis, RSA and ElGamal will be investigated and  their homomorphic features will be presented right after giving an overview of public key crypto systems.  The implementation will be performed in Java programming environment. Then, in the online tax payment system, the homomorphic application of both will be discussed and performance comparison will be presented. However, in order to get a better understanding of them, we will first begin by explaining mathematical concepts in number theory and abstract algebra in the first part of our thesis.
In the second part, RSA and ElGamal, the first of the open-key (asymmetric) crypto systems, will be discussed, and then one of the current usage areas, electronic signature or digital signature will be mentioned.
In the third chapter, the mathematical definition of homormorphic encryption, which is the main subject of our thesis, with public key cryptosystem, will be given. Full homomorphic crypto systems developed after 2010 will be discussed.
In the four and fifth part of the thesis, the mathematical properties of RSA and ElGamal are shown mathematically. In the last part of the thesis, we apply the homomorphic properties of RSA and ElGamal to our tax payment system and compare the multiplicative homomorphic characteristics of both cryptosystems in terms of performance. Our application will be implemented in Java using different key lengths, 1024-bits, 2048-bits and 3072-bits, and in each of these switches, the total latency of encryption, decoding and homomorphic operations will be calculated by five separate trials.
As a result of the research, both RSA and ElGamal public-key crypto systems provide both multiplicative homomorphic properties and it was concluded that RSA is more efficient and more useful in terms of encryption, decryption and homomorphic multiplicative operations on encrypted texts. In general, RSA pulic key crypto system seems to have been about four times faster than ElGamal public key crypto system. Moreover, in the same key size, the RSA is four times faster, and also the encrypted text is half that of the encrypted text in ElGamal. Our tax payment system, which is developed by using homomorphic crypto systems, can be applied to the Social Security Institution for salary payment. Thus, salaries of individuals are known only by themselves and the amount of tax that they have to pay is known only by themselves. 


Homomorphic crypto systems were first discussed in the article published by Rivest, Adleman and Dertouzous in 1978 [2]. In that article, they showed that some mathematical operations can be performed without deciphering encrypted data. Studies on homomorphic crypto systems have begun with the publication of this article.

The main purpose of homomorphic cryptography is to ensure the privacy of data  during communication and the confidentiality of data in databases or in public cloud systems. In the meantime, several partial homomorphic crypto systems have been developed, for example methods which are homomorphic for only  multiplication operation (ElGamal [3] 1984, RSA [2]) or for only addition (Paillier [4] 1999, Goldwasser-Micali 1984 [5]). In an article published in 1991 by Feigenbaum [6], interest in fully homomorphic crypto systems increased. In the article he asked the following question ; "Is it possible to develop a crypto system with Enc() encryption function that expresses Enc(x + y) and Enc (x.y) in terms of Enc(x) and Enc(y)?". In 2009, Craig Gentry, in his doctoral thesis, proved the existence of such crypto systems, and he developed the fully homomorphic crypto system [7] and answered Feigenbaum's question.

In this thesis, RSA and ElGamal will be investigated and  their homomorphic features will be presented right after giving an overview of public key crypto systems.  The implementation will be performed in  Java programming environment. Then, in the online tax payment system, the homomorphic application of both will be discussed and performance comparison will be presented. However, in order to get a better understanding of them, we will first begin by explaining mathematical concepts in number theory and abstract algebra in the first part of our thesis.

In the second part, RSA and ElGamal, the first of the open-key (asymmetric) crypto systems, will be discussed, and then one of the current usage areas, electronic signature or digital signature will be mentioned.

In the third chapter, the mathematical definition of homormorphic encryption, which is the main subject of our thesis, with public key cryptosystem, will be given. Full homomorphic crypto systems developed after 2010 will be discussed.

In the four and fifth part of the thesis, the mathematical properties of RSA and ElGamal are shown mathematically. In the last part of the thesis, we apply the homomorphic properties of RSA and ElGamal to our tax payment system and compare the multiplicative homomorphic characteristics of both cryptosystems in terms of performance. Our application will be implemented in Java using different key lengths, 1024-bits, 2048-bits and 3072-bits, and in each of these switches, the total latency of encryption, decoding and homomorphic operations will be calculated by five separate trials.

As a result of the research, both RSA and ElGamal public-key crypto systems provide both multiplicative homomorphic properties and it was concluded that RSA is more efficient and more useful in terms of encryption, decryption and homomorphic multiplicative operations on encrypted texts. In general, RSA pulic key crypto system seems to have been about four times faster than ElGamal public key crypto system. Moreover, in the same key size, the RSA is four times faster, and also the encrypted text is half that of the encrypted text in ElGamal. Our tax payment system, which is developed by using homomorphic crypto systems, can be applied to the Social Security Institution  for  salary payment. Thus, salaries of individuals are known only by themselves and the amount of tax that they have to pay is known only by themselves.