GRAPH-BASED CRYPTOGRAPHIC KEY GENERATION FOR SECURE TEXT ENCRYPTION

Abstract

The purpose of this article is to use a novel text encryption technique that ensures secure communication through a two-phase process and to use the encryption technique to demonstrate the connection between graph theory and cryptography. In this article, the spanning tree graph, which is a subgraph of an undirected graph used in graph theory and includes all vertices of the graph G, will be used. The first phase employs a monoalphabetic substitution cipher, utilizing predefined character-swapping arrangements between authorized individuals along with an alphabetical encryption table. The second phase enhances security by leveraging graph theory for key generation. Specifically, the Kruskal algorithm is used to compute the minimum spanning tree, enabling the creation of intricate encrypted text with a shared key derived from graph structures. By utilizing properties such as adjacency matrices, spanning trees, and graph isomorphisms, the proposed method strengthens cryptographic security while maintaining computational efficiency. The security analysis demonstrates its resilience against common cryptographic attacks, making it a promising alternative for secure text encryption and communication.

Keywords

• Graphs
• Encryption
• Decryption
• Cryptography

GÜVENLİ METİN ŞİFRELEMESİ İÇİN GRAF TEORİSİ TABANLI KRİPTOGRAFİK ANAHTAR ÜRETİMİ

Abstract

Bu makalenin amacı, güvenli iletişimi sağlamak için iki aşamalı bir süreçle yeni bir metin şifreleme tekniği kullanmak ve bu şifreleme tekniği aracılığıyla graf teorisi ile kriptografi arasındaki bağlantıyı göstermektir. Bu çalışmada, graf teorisinde kullanılan ve G grafının tüm düğümlerini içeren bir alt graf olan minumum spanning tree grafı kullanılmıştır. İlk aşama, yetkilendirilmiş kişiler arasında önceden belirlenmiş karakter değişim düzenlemeleri ile bir monoalfabetik ikame şifresi kullanarak bir alfabe şifreleme tablosu uygulamaktadır. İkinci aşama ise güvenliği, anahtar şifresi üretimi için graf teorisinin kullanılması ile arttırılmaktadır. Özellikle, Kruskal algoritması minimum spanning tree kullanılmaktadır. Adjacency matrisleri, yayılma ağaçları ve graf izomorfizmleri gibi özellikler kullanılarak, önerilen yöntem kriptografik güvenliği güçlendirirken hesaplama verimliliğini de korumaktadır. Güvenlik analizi, yaygın kriptografik saldırılara karşı direncini ortaya koyarak, güvenli metin şifrelemesi ve iletişimi için umut verici bir alternatif sunduğunu göstermektedir.

Keywords

• Graf Teorisi
• Şifreleme
• Şifre Çözme
• Kriptografi

References

1. Abdul-Ghani, S. A.; Abdul-Wahhab, R. D.& Abood, E.W. (2022) Securing Text Messages Using Graph Theory and Steganography. Baghdad Science Journal, 19(1), 189-196.
2. Akl, S. G. (2020). How to encrypt a graph. International Journal of Parallel, Emergent and Distributed Systems, 35, 668–681.
3. Alaeiyan, M., Obayes. K.K., & Alaeiyan M. (2023). Prediction nullity of graph using data mining. Results in Nonlinear Analysis, 6(2), 1–8.
4. Bai, S., Zhou, L., Yan, M., Ji, X., & Tao, X. (2021). Image cryptosystem for visually meaningful encryption based on fractal graph generating. IETE Technical Review, 38, 130–141.
5. Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer, New York. http://dx.doi.org/10.1007/978-1-84628-970-5
6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd edition). MIT Press.
7. Lu, S., Manchala, D., & Ostrovsky R. (2008). Visual cryptography on graphs. Computing and Combinatorics: 14th
8. Annual International Conference, COCOON 2008, Dalian, China, June 27–29, Proceedings 14, 225–234.

9. Menezes, A. J., Van Oorschot, P. C. & Vanstone, S. A. (1996). Handbook of applied cryptography. CRC Press.
10. Monrose, F., Reiter, M., Li. Qui, K.&Wetzel, S. (2001). Cryptographic key generation from voice. Proceedings of the 2001 IEEE Symposium on Security and Privacy (S&P 2001), 202–213.
11. Perera, P., & Wijesiri, G.S. (2021). Encryption and decryption algorithms in symmetric key cryptography using graph theory. Psychology and Education Journal, 58 (1), 3420–3427.
12. Schneier, B. (2017). Applied cryptography: Protocols, algorithms, and source code in C (2nd edition). John Wiley & Sons.
13. Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509.
14. Singh, S. (1999). The code book: The science of secrecy from ancient Egypt to quantum cryptography. Anchor Books.
15. Stallings, W. (2017). Cryptography and network security: Principles and practice. Pearson.
16. Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. Journal of the ACM, 23(1), 31–42.
17. Ustimenko, V. A. (2007). On graph-based cryptography and symbolic computations. Serdica Journal of Computing, 1, (2), 131–156. DOI:10.55630/sjc.2007.1.131-156.
18. Vasudev, C. (2006). Graph theory with applications. New Age International.
19. West, D. B. (2006). Introduction to graph theory. Prentice Hall.
20. Yamuna, M., & Karthika, K. (2015). Data transfer using bipartite graphs. International Journal of Advanced Research in Science and Engineering, 4, special issue 2, 128–131.
21. Yamuna, M., Gogia. M., Sikka, A., & Khan. Md. J. H. (2012). Encryption using graph theory and linear algebra. I International Journal of Computer Applications, 2(5), 102–107.
22. Wu, D. L. (2024). GNSS Signal Jamming as Observed From Radio Occultation. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing.