Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi

Murat Cenk (Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Ankara, Türkiye)
Ferruh ÖZBUDAK (Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Ankara, Türkiye)
6 5

Proje Grubu: EEEAG Sayfa Sayısı: 65 Proje No: 115R289 Proje Bitiş Tarihi: 01.06.2018 Metin Dili: Türkçe İndeks Tarihi: 05-03-2020

Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi

Öz:
Projenin genel amacı, kriptografide sıklıkla kullanılan modüler üst alma, polinom çarpması ve eliptik egriler üzerindeki islemlerin karmasıklıgını iyilestirecek gelistirmelerin yapılması ve elde edilecek yeni algoritmaların çesitli platformlar üzerinde gerçeklenmesidir. Bu çalısmalar sonucunda modüler üst alma, eliptik egri aritmetigi ve polinom çarpma islemlerinde iyilestirmeler elde edilmistir. Çalısmalar kapsamında P-521, E-521 ve Curve25519 egrileri üzerindeki islemler Toeplitz matris vektör çarpımları (TMVÇ) kullanılarak hızlandırılmıstır. Eliptik egrilerin üzerinde tanımlandıgı ve eleman sayıları 521 ve 255 bitlik asal sayılar olan cisimlerde çarpma islemleri için yeni TMVÇ algoritmaları tasarlanmıs ve bu algoritmaların sagladıgı iyilestirmeler teorik olarak gösterilmistir. Yapılan gerçeklemeler ile teorik çıkarımlardaki iyilestimeler pratikte de gözlemlenmistir. Diger taraftan polinom çarpma isleminin iyilestirilmesi için arama algoritmalarının verimi üzerine çalısmalar yapılmıstır. Polinomun terim sayısı arttıkça arama uzayı oldukça büyüdügü için, çarpım polinomunun tüm terimlerini hesaplamak yerine, n terimli iki polinomun çarpmının ilk n teriminin hesaplanması üzerine analizler yapılmıstır. Böylece arama uzayının boyutu düsürülmüs ve Çinli Kalan Teoremi ile polinom çarpımı için algoritmalar elde edebilme olanagı saglanmıstır. Diger bir yaklasım ise n terimli iki polinomum ilk l teriminin hesaplanmasıdır. Ayrıca, bu yaklasımda arama uzayının boyutunun düsürülmesi için ikili dogrusal formların simetriklerinin alınması ve bazı terimlerin elenmesi yöntemleri kullanılmıstır. Bu yaklasımlar arama uzayının boyutunu belirgin sekilde azaltmıstır. Ek olarak interpolasyon metodunda hesaplanacak noktalar dikkatlice seçilerek, süper singüler izojen bazlı kuantum sonrası kriptografide kullanılan Fp2 çarpma islemi ve büyük sayıların çarpımları hızlandırılmıstır. Proje kapsamında çalısılan diger bir konu olan modüler üst alma isleminin hızlandırılması için, literatürdeki küp seker algoritması incelenmistir. Bu algoritma, en küçük toplam zinciri ve karma üst alma metotları ile birlikte kullanılmıstır. Ayrıca, sonuçların daha da hızlandırılması adına, n bitlik bir tamsayının küp alma isleminden sonra 3n olan boyutunu indirgemek için kullanılan Barett metodu degistirilmis ve böylece teorik olarak islem karmasıklıgında iyilestirmeler yapılmıstır.
Anahtar Kelime: modüler üst alma eliptik egri kriptografisi polinom çarpımı Kriptografik hesaplamalar

Konular: Matematik
Erişim Türü: Erişime Açık
  • 1- Karatsuba-like formulae and their associated techniques (Makale - Diger Hakemli Makale),
  • Ali, S. (2017). “Faster Residue Multiplication Modulo 521-bit Mersenne Prime and Application to ECC”. PhD thesis. Orta Do˘gu Teknik Üniversitesi Uygulamalı Matematik Enstitüsü Kriptografi Programı.
  • 2- Efficient Big Integer Multiplication in Cryptography (Makale - Diger Hakemli Makale),
  • Ali, S. ve Cenk, M. (2017). “A New Algorithm for Residue Multiplication Modulo 2521 􀀀 1”. Proceedings of the 19th International Conference on Information Security and Cryptology Volume 10157. New York, NY, USA: Springer-Verlag New York, Inc., pp. 181–193.
  • 3- Faster Residue Multiplication Modulo 521-bit Mersenne Prime and an Application to ECC (Makale - Indeksli Makale),
  • Ali, S. ve Cenk, M. (2018a). “Faster Residue Multiplication Modula 521-bit Mersenne Prime and an Application to ECC”. Poster.
  • Ali, S. ve Cenk, M. (2018b). “Faster Residue Multiplication Modulo 521-bit Mersenne Prime and an Application to ECC”. IEEE Transactions on Circuits and Systems I: Regular Papers 65.8, pp. 2477–2490.
  • 4- Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • Aranha, D. F., Barreto, P. S. L. M., Pereira, G. C. C. F. ve Ricardini, J. E. (2013). A note on highsecurity general-purpose elliptic curves. Cryptology ePrint Archive, Report 2013/647. https: //eprint.iacr.org/2013/647.
  • 5- Efficient Big Integer Multiplicationin Cryptography (Bildiri - Uluslararası Bildiri - Sözlü Sunum),
  • Baloglu, S., Cenk, M. ve Calik, C. (2018). “On the New Upper Bounds for Computing Some First Terms of Product Polynomials”.
  • 6- Yılın en iyi tezi (Ödül - Ulusal Ödül - Üniversite, Kurum veya Kurulusların Verdigi Ödüller),
  • Barbulescu, R., Detrey, J., Estibals, N. ve Zimmermann, P. (2012). “Finding optimal formulae for bilinear maps”. International Workshop on the Arithmetic of Finite Fields. Springer, pp. 168– 186.
  • 7- Homomorphic Encryption Based on the Ring Learning with Errors (RLWE) Problem (Tez (Arastırmacı Yetistirilmesi) - Yüksek Lisans Tezi),
  • Barrett, P. (1986). “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor”. Conference on the Theory and Application of Cryptographic Techniques. Springer, pp. 311–323.
  • 8- Modular Exponentiation Methods in Cryptography (Tez (Arastırmacı Yetistirilmesi) - Yüksek Lisans Tezi),
  • Bernstein, D. J. (2006). “Curve25519: New Diffie-Hellman Speed Records”. Public Key Cryptography - PKC 2006: 9th International Conference on Theory and Practice in Public-Key Cryptography, New York, NY, USA, April 24-26, 2006. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 207–228. ISBN: 978-3-540-33852-9. DOI: 10.1007/11745853_14.
  • 9- Faster Residue Multiplication Modulo 521-bit Mersenne Prime and Application to ECC (Tez (Arastırmacı Yetistirilmesi) - Doktora Tezi),
  • Bernstein, D. J., Chuengsatiansup, C. ve Lange, T. (2014). “Curve41417: Karatsuba Revisited”. Cryptographic Hardware and Embedded Systems - CHES 2014 - 16th International Workshop, Busan, South Korea, September 23-26, 2014. Proceedings. https://doi.org/10.1007/978- 3-662-44709-3_18, pp. 316–334.
  • Bernstein, D. J., Hamburg, M., Krasnova, A. ve Lange, T. (2013). Elligator: Elliptic-curve points indistinguishable from uniform random strings. Cryptology ePrint Archive, Report 2013/325. https://eprint.iacr.org/2013/325.
  • Bernstein, D. J. ve Lange, T. (2007). Faster addition and doubling on elliptic curves. Cryptology ePrint Archive, Report 2007/286. https://eprint.iacr.org/2007/286.
  • Bernstein, D. J. ve Lange, T. (2018). SafeCurves: choosing safe curves for elliptic-curve cryptography. https://safecurves.cr.yp.to. URL: https://safecurves.cr.yp.to (visited on 07/01/2018).
  • Bernstein, D. J., Chuengsatiansup, C. ve Lange, T. (2017). “Double-base scalar multiplication revisited.” IACR Cryptology ePrint Archive 2017, p. 37.
  • Bodrato, M. ve Zanoni, A. (2012). “A new algorithm for long integer cube computation with some insight into higher powers”. International Workshop on Computer Algebra in Scientific Computing. Springer, pp. 34–46.
  • Bos, J.W., Costello, C., Longa, P. ve Naehrig, M. (2016). “Selecting elliptic curves for cryptography: an efficiency and security analysis”. J. Cryptographic Engineering 6.4, pp. 259–286.
  • Bosselaers, A., Govaerts, R. ve Vandewalle, J. (1993). “Comparison of three modular reduction functions”. Annual International Cryptology Conference. Springer, pp. 175–186.
  • Brown, D. R. L. (2011). Certicom Research SEC 2: Recommended Elliptic Curve Domain Parameters. http://www.secg.org/sec2-v2.pdf.
  • Cenk, M. ve Özbudak, F. (2008). “Efficient Multiplication in F3`m;m  1 and 5  `  18”. AFRICA CRYPT, pp. 406–414.
  • Cenk, M. ve Özbudak, F. (2009). “Improved Polynomial Multiplication Formulas over F2 Using Chinese Remainder Theorem”. IEEE Transactions on computers 58.4, pp. 572–576.
  • Cenk, M. ve Özbudak, F. (2011). “Multiplication of polynomials modulo xn”. Theoretical Computer Science 412.29, pp. 3451–3462.
  • Cenk, M. ve Özbudak, F. (2010). “On multiplication in finite fields”. Journal of Complexity 26.2, pp. 172–186.
  • Cenk, M. (2018). “Karatsuba-Like Formulae and Their Associated Techniques”. Journal of Cryptographic Engineering. Cenk, M., Banerjee, T. ve Hasan, A. (2018). “Faster Multiplication in the Quadratic Extension of Prime Fields and Its Applications to SIDH”. In progress.
  • Chou, T. (2015). “Sandy2x: New Curve25519 Speed Records”. Selected Areas in Cryptography - SAC 2015 - 22nd International Conference, Sackville, NB, Canada, August 12-14, 2015, Revised Selected Papers, pp. 145–160.
  • Diffie, W. ve Hellman, M. (1976). “New directions in cryptography”. IEEE transactions on Information Theory 22.6, pp. 644–654.
  • Dimitrov, V. ve Cooklev, T. (1995). “Two algorithms for modular exponentiation using nonstandard arithmetics”. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 78.1, pp. 82–87.
  • Fan, H. ve Hasan, M. A. (2007a). “A New Approach to Subquadratic Space Complexity Parallel Multipliers for Extended Binary Fields”. IEEE Transactions on Computers 56.2, pp. 224–233.
  • Fan, H. ve Hasan, M. A. (2007b). “Comments on" Five, Six, and Seven-Term Karatsuba-Like Formulae”. IEEE Transactions on Computers 56.5, pp. 716–717.
  • Granger, R. ve Scott, M. (2014). Faster ECC over F2521􀀀1. Cryptology ePrint Archive, Report 2014/852. https://eprint.iacr.org/2014/852.
  • Hanrot, G., Quercia, M. ve Zimmermann, P. (2004). “The middle product algorithm I”. Applicable Algebra in Engineering, Communication and Computing 14.6, pp. 415–438.
  • IANIX (2017). Things that use Curve25519. URL: https://ianix.com/pub/curve25519-deployment. html (visited on 11/15/2017).
  • Ilter, M. B. ve Cenk, M. (2017a). “Efficient Big Integer Multiplication in Cryptography”. International Journal of Information Security Science 6.4, pp. 70–78.
  • Ilter, M. B. ve Cenk, M. (2017b). “Efficient Big Integer Multiplication in Cryptography”. ISCTurkey 2017 Conference Proceedings 8.13.
  • Kaminski, M. ve Bshouty, N. H. (1989). “Multiplicative complexity of polynomial multiplication over finite fields”. Journal of the ACM (JACM) 36.1, pp. 150–170.
  • Karatsuba, A. (1963). “Multiplication of multidigit numbers on automata”. Soviet physics doklady. Vol. 7, pp. 595–596.
  • Keskinkurt, I. (2017). “Homomorphic Encryption Based on the Ring Learning with Errors (RLWE) Problem”. MA thesis. Orta Do˘gu Teknik Üniversitesi Uygulamalı Matematik Enstitüsü Kriptografi Programı.
  • Knezevic, M., Vercauteren, F. ve Verbauwhede, I. (2009). Speeding Up Barrett and Montgomery Modular Multiplications. Koblitz, N. (1987). “Elliptic curve cryptosystems”. Mathematics of computation 48.177, pp. 203– 209.
  • Miller, V. S. (1985). “Use of elliptic curves in cryptography”. Conference on the theory and application of cryptographic techniques. Springer, pp. 417–426.
  • Montgomery, P. L. (2005). “Five, six, and seven-term Karatsuba-like formulae”. IEEE Transactions on Computers 54.3, pp. 362–369.
  • NIST (2013). Federal Information Processing Standards Publication (FIPS) 186-4: Digital Signature Standard (DSS). https://doi.org/10.6028/NIST.FIPS.186-4.
  • NIST (2017). Transition Plans for Key Establishment Schemes using Public Key Cryptography. https://csrc.nist.gov/News/2017/Transition-Plans-for-Key-Establishment-Schemes. URL: https://csrc.nist.gov/News/2017/Transition- Plans- for- Key- Establishment- Schemes (visited on 11/15/2017).
  • Oseledets, I. (2011). “Improved n-term Karatsuba-like formulas in GF (2)”. IEEE Transactions on Computers 60.8, pp. 1212–1216.
  • Oseledets, I. (2008). “Optimal Karatsuba-like formulae for certain bilinear forms in GF (2)”. Linear Algebra and its Applications 429.8-9, pp. 2052–2066.
  • Project, G. (2017). GCC Options That Control Optimization. https://gcc.gnu.org/onlinedocs/ gcc/Optimize- Options.html. URL: https://gcc.gnu.org/onlinedocs/gcc/Optimize- Options.html (visited on 11/15/2017).
  • Shumow, D. ve Ferguson, N. (2007). “On the possibility of a back door in the NIST SP800-90 Dual Ec Prng”. Proc. Crypto. Vol. 7.
  • SUPERCOP (2017). Curve25519 ref10 Implementation. http://bench.cr.yp.to/supercop. html. URL: http://bench.cr.yp.to/supercop.html (visited on 11/15/2017).
  • Sydney, T. U. of (2017). Magma Computational Algebra System. http://magma.maths.usyd.edu. au/magma/. URL: http://magma.maths.usyd.edu.au/magma/ (visited on 11/15/2017).
  • Taskin, H. K. ve Cenk, M. (2018). “Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication”. Fifth Workshop on Cryptography and Security in Computing Systems.
  • Ta¸skın, H. K. ve Cenk, M. (2018). “Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication”.
  • Workshop on Cryptography and Security in Computing Systems of the HiPEAC2018 Conference. CS2 ’18. Manchester, UK.
  • Toom, A. L. (1963). “The complexity of a scheme of functional elements realizing the multiplication of integers”. Soviet Mathematics Doklady. Vol. 3. 4, pp. 714–716.
  • Walter, C. D. (1998). “Exponentiation using division chains”. IEEE Transactions on Computers 47.7, pp. 757–765.
  • Yunuak, H. B. ve Cenk, M. (2018). “Faster Modular Exponentiation”. Poster.
  • Yunuak, H. B., Cenk, M., Dimitrov, V. ve Hasan, A. (2018). “Faster Modular Exponentiation”.
  • Zanoni, A. (2010). Another sugar cube, please! or sweetening third powers computation. Tech. rep. Technical Report 632, Centro” Vito Volterra”, Università di Roma” Tor Vergata”(January 2010).
APA Cenk M, Ozbudak F (2018). Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. , 1 - 65.
Chicago Cenk Murat,Ozbudak Ferruh Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. (2018): 1 - 65.
MLA Cenk Murat,Ozbudak Ferruh Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. , 2018, ss.1 - 65.
AMA Cenk M,Ozbudak F Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. . 2018; 1 - 65.
Vancouver Cenk M,Ozbudak F Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. . 2018; 1 - 65.
IEEE Cenk M,Ozbudak F "Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi." , ss.1 - 65, 2018.
ISNAD Cenk, Murat - Ozbudak, Ferruh. "Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi". (2018), 1-65.
APA Cenk M, Ozbudak F (2018). Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. , 1 - 65.
Chicago Cenk Murat,Ozbudak Ferruh Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. (2018): 1 - 65.
MLA Cenk Murat,Ozbudak Ferruh Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. , 2018, ss.1 - 65.
AMA Cenk M,Ozbudak F Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. . 2018; 1 - 65.
Vancouver Cenk M,Ozbudak F Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi. . 2018; 1 - 65.
IEEE Cenk M,Ozbudak F "Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi." , ss.1 - 65, 2018.
ISNAD Cenk, Murat - Ozbudak, Ferruh. "Açık Anahtarlı Kriptografi için Verimli Algoritmaların Geli¸ stirilmesi". (2018), 1-65.
Sayfa Oluşturulma Tarihi
24-04-2024 1:36

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları