System Security Analysis of Formal Language-Based Public Key Cryptography and Finite Automata

Abstract: The growing need for verifiable cryptographic systems in the post-quantum era has spurred interest in alternative methods for analyzing public key cryptography. This study introduces a formal approach for modeling RSA encryption and decryption using deterministic finite automata (DFA) and regular language theory. By abstracting the modular exponentiation process into symbolic transitions, we construct a DFA-based model capable of simulating encryption workflows across varying key sizes and input lengths. The simulation, implemented using Python and JFLAP, demonstrates that RSA operations—typically arithmetic in nature—can be reliably represented and executed through automata. Results show accurate ciphertext generation and high execution efficiency, with computational complexity scaling linearly with input and state size. This formal model not only supports correctness validation but also enables traceability and performance profiling, offering a scalable tool for formal verification and cryptographic analysis. These findings position DFA modeling as a promising foundation for future research in lightweight cryptographic design, post-quantum protocol verification, and symbolic security analysis.

Keywords: Finite Automata, Formal Language, Public Key Cryptography, RSA, Security Analysis.