Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems

Robin Strässer, Sebastian Schlor, Frank Allgöwer

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.

Introduction

In the realm of cybersecurity, the security of algorithms like Diffie-Hellman (DH) and RSA is typically evaluated through number theory and computational complexity. These systems rely on "trapdoor" functions—mathematical operations that are easy to compute in one direction but computationally expensive to reverse without a secret key. However, from a systems theory perspective, these operations can be viewed as nonlinear dynamical systems. The "random-looking" trajectories generated by modular arithmetic resemble chaotic behavior, which has historically made them difficult to analyze using standard control theory tools.

This research bridges this gap by applying Koopman operator theory to cryptosystems. By "lifting" the nonlinear state space into a higher-dimensional space of observables, we can represent the discrete jumps of a cryptosystem as a purely linear evolution. This transformation allows for the application of linear algebra techniques, such as eigendecomposition, to recover secret parameters.

Methodology: Koopman Operator Theory and Lifting

The core of this approach is the Koopman operator, which describes the evolution of functions (observables) defined on the state space of a dynamical system. For a nonlinear system $x_{k+1} = f(x_k)$, the Koopman operator $\mathcal{K}$ acts on an observable $g$ such that $\mathcal{K}g = g \circ f$. While the original system may be nonlinear and finite-dimensional, the Koopman operator is linear but typically infinite-dimensional.

Analytical Lifting

The authors propose two primary lifting strategies to find a finite-dimensional linear representation: Fourier-inspired observables (mapping the state to the complex unit circle) and delay-based observables (using sequences of state values).

Visualization of the lifted linear system where discrete jumps are mapped to rotations on the unit circle.

As shown in Figure 2, the nonlinear modulo operation can be interpreted as a rotation on the complex unit circle. By choosing a sufficient lifting dimension $q$, the system's evolution becomes a simple linear shift in the higher-dimensional space. For a prime modulus $p$, the authors prove that a lifting dimension of $q = (p-1)/2$ is sufficient for perfect linearization.

Secret Reconstruction

Once the system is linearized, the secret key (the exponent in DH or RSA) manifests as a parameter of the linear operator. Specifically, the secret integer can be recovered by analyzing the eigenvalues of the lifted system.

Geometric interpretation of secret reconstruction via eigenvalue angles on the complex unit circle.

Figure 1 illustrates how the angles of the eigenvalues $\mu_j$ relate to the state transitions. By calculating the phase difference between the initial lifted state and the evolved state, the secret exponent can be algebraically reconstructed using standard linear solvers.

Results and Discussion

The proposed framework was validated using synthetic data from DH and RSA systems with prime moduli up to 31,607.

  • Perfect Accuracy: The analytical lifting method achieved 100% reconstruction accuracy for all tested cases using the derived Algorithm 2.
  • Lifting Dimension and Security: The discovery that the minimum lifting dimension scales linearly with the prime $p$ provides a theoretical link to cryptographic security. If the required dimension were significantly smaller, it would imply a shortcut to breaking the encryption faster than brute force.
  • Computational Complexity: While the method is mathematically sound, the computational cost of handling matrices of size $q \times q$ grows with $p$. For a prime of 31,607, reconstruction took approximately 3,561 seconds on standard hardware.

Conclusion and Future Work

This work establishes a formal connection between Koopman theory and cryptography, showing that the "hardness" of a cryptosystem is intrinsically linked to the dimensionality required for its linearization. While current computational limits prevent this from being a practical attack on modern 2048-bit RSA, it provides a powerful new analytical framework. Future research will explore extensions to Elliptic Curve Cryptography (ECC) and the use of these models to formally certify the security of emerging cryptographic protocols.

Summary updated

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.
BibTeX
@article{strasser2024decrypting,
  author = {Robin Strässer and Sebastian Schlor and Frank Allgöwer},
  title = {{Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems}},
  journal = {Automatica},
  year = {2024},
  doi = {10.1016/j.automatica.2024.112022},
}
Figure