Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems

Abstract

Public-key cryptosystems rely on computationally difficult problems for security, traditionally analyzed using number theory methods. In this paper, we introduce a novel perspective on cryptosystems by viewing the Diffie-Hellman key exchange and the Rivest-Shamir-Adleman cryptosystem as nonlinear dynamical systems. By applying Koopman theory, we transform these dynamical systems into higher-dimensional spaces and analytically derive equivalent purely linear systems. This formulation allows us to reconstruct the secret integers of the cryptosystems through straightforward manipulations, leveraging the tools available for linear systems analysis. Additionally, we establish an upper bound on the minimum lifting dimension required to achieve perfect accuracy. Our results on the required lifting dimension are in line with the intractability of brute-force attacks. To showcase the potential of our approach, we establish connections between our findings and existing results on algorithmic complexity. Furthermore, we extend this methodology to a data-driven context, where the Koopman representation is learned from data samples of the cryptosystems.

Accepted for publication in Automatica

References in corpus (10)

• Cryptographic requirements for chaotic secure communications
• A Data-Driven Approximation of the Koopman Operator: Extending Dynamic Mode Decomposition
• Linear predictors for nonlinear dynamical systems: Koopman operator meets model predictive control
• Ergodic theory, Dynamic Mode Decomposition and Computation of Spectral Properties of the Koopman operator
• On Convergence of Extended Dynamic Mode Decomposition to the Koopman Operator
• Study of dynamics in post-transient flows using Koopman mode decomposition
• Robust data-driven control for nonlinear systems using the Koopman operator
• Theoremata arithmetica nova methodo demonstrata
• Koopman interpretation and analysis of a public-key cryptosystem: Diffie-Hellman key exchange
• Local inversion of maps: A new attack on Symmetric encryption, RSA and ECDLP

Cited by in corpus (3)

• An overview of Koopman-based control: From error bounds to closed-loop guarantees
• SafEDMD: A Koopman-based data-driven controller design framework for nonlinear dynamical systems
• Koopman-based control using sum-of-squares optimization: Improved stability guarantees and data efficiency