A Novel Number-Theoretic Model for Secure Key Generation in Information Security

Abstract

Every deployed RSA implementation rests on one algebraic assumption: that factoring large integers is hard. Nobody has an independent, formally verified way to check that a given private key was actually generated correctly, and there is no well-understood second layer sitting on top of that single assumption. Quantum algorithms and decades of cryptanalytic progress keep narrowing the margin around it, which is part of why standards bodies are already moving toward lattice-based replacements. This paper works out the mathematics of an existing idea that earlier graph-augmented RSA proposals mostly left informal: binding the RSA private exponent to a directed graph G(V, E) generated by the public permutation u ↦ uᵉ (mod n). We prove the construction is correct for every valid key pair, show that G is always a publicly and efficiently decomposable union of disjoint directed cycles rather than an NP-hard structure, derive the exact condition under which a simple trapdoor path of a requested length exists, and give closed-form time and space complexity bounds. Every result is checked twice: once by hand on a fully worked numerical example (n = 143), and once empirically, across a 72-configuration benchmark spanning three RSA modulus sizes and four graph orders, where the measured overhead ranges from 14% to 343% of baseline RSA key-generation time depending on the chosen |V|. The central security result is a clean reduction: recovering the model's private key is at least as hard as breaking standard RSA, and no harder. The graph layer adds no independent, NP-hardness-based security margin, so what's left is a single, precisely stated open question about resistance to partial-information and side-channel observation.