Koopman interpretation and analysis of a public-key cryptosystem: Diffie-Hellman key exchange

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

Abstract

The security of public-key cryptosystems relies on computationally hard problems, that are classically analyzed by number theoretic methods. In this paper, we introduce a new perspective on cryptosystems by interpreting the Diffie-Hellman key exchange as a nonlinear dynamical system. Employing Koopman theory, we transfer this dynamical system into a higher-dimensional space to analytically derive a purely linear system that equivalently describes the underlying cryptosystem. In this form, analytic tools for linear systems allow us to reconstruct the secret integers of the key exchange by simple manipulations. Moreover, we provide an upper bound on the minimal required lifting dimension to obtain perfect accuracy. To demonstrate the potential of our method, we relate our findings to existing results on algorithmic complexity. Finally, we transfer this approach to a data-driven setting where the Koopman representation is learned from data samples of the cryptosystem.

Introduction

Modern public-key cryptography, such as the Diffie-Hellman (DH) exchange, is built upon the perceived computational hardness of number-theoretic problems—most notably the Discrete Logarithm Problem (DLP). While these systems are traditionally analyzed through the lens of computational complexity and number theory, this research proposes a novel bridge to control theory and dynamical systems. By reframing modular exponentiation as a nonlinear dynamical system, the authors explore whether the tools of linear system analysis can be applied to cryptographic "black boxes."

Methodology: Linearizing Nonlinear Dynamics

The core of this approach is Koopman Operator Theory. In the context of dynamical systems, the Koopman operator is a linear operator that describes the evolution of functions of the system state (observables) over time.

  1. Dynamical Recasting: The DH operation $x_{k+1} = m x_k \pmod p$ is represented as a discrete-time nonlinear system.
  2. Lifting: The state is "lifted" into a higher-dimensional space using a dictionary of observables. The authors demonstrate that in this expanded space, the dynamics become strictly linear, following the form $z_{k+1} = Az_k$.
  3. Eigendecomposition: With a linear system established, the eigenvalues and eigenvectors of the transition matrix $A$ are used to derive an analytical formula for the secret exponent $e$.
  4. Data-Driven Learning (EDMD): The study also employs Extended Dynamic Mode Decomposition (EDMD) to show that this linear representation can be learned directly from samples of the cryptosystem's output, effectively recovering the system structure from data.

Key Results: Analytical Reconstruction and Complexity

The research provides a formal proof (Theorem 7) for the minimal lifting dimension required to achieve a perfect linear representation of the DH system. This dimension is found to be exactly $\tilde{q} = (p-1)/2$.

Matrix representation of the lifted linear system used for secret reconstruction.

In this lifted space, the secret exponent $e$ is directly encoded in the phase (angle) of the system's eigenvalues. Reconstructing the secret becomes a matter of comparing the angles of the initial state and the final "ciphertext" state within the eigen-basis. The matrix structure shown above illustrates how the nonlinear modular system is mapped into a solvable linear framework.

Furthermore, the authors relate these findings to Linear Feedback Shift Registers (LFSRs). They argue that Koopman theory offers a more powerful framework by allowing for nonlinear observables, potentially describing complex sequences with a much smaller state dimension than standard LFSRs.

Discussion and Scalability

While the analytical results are profound, the authors acknowledge a significant limitation: scalability. The required lifting dimension $\tilde{q} \approx p/2$ grows exponentially with the bit-length of the prime number. For a cryptographically secure 2048-bit prime, the resulting matrix would be computationally infeasible to store or manipulate.

This "cost of accuracy" serves as a bridge to algorithmic complexity, explaining the security of DH from a dynamical systems perspective: while a linear representation exists, its dimensionality makes it practically inaccessible for large-scale systems. Future work will investigate more sophisticated observables to potentially reduce this lifting dimension and apply this framework to other cryptosystems like RSA or Elliptic Curve Cryptography (ECC).

Summary updated

Abstract

The security of public-key cryptosystems relies on computationally hard problems, that are classically analyzed by number theoretic methods. In this paper, we introduce a new perspective on cryptosystems by interpreting the Diffie-Hellman key exchange as a nonlinear dynamical system. Employing Koopman theory, we transfer this dynamical system into a higher-dimensional space to analytically derive a purely linear system that equivalently describes the underlying cryptosystem. In this form, analytic tools for linear systems allow us to reconstruct the secret integers of the key exchange by simple manipulations. Moreover, we provide an upper bound on the minimal required lifting dimension to obtain perfect accuracy. To demonstrate the potential of our method, we relate our findings to existing results on algorithmic complexity. Finally, we transfer this approach to a data-driven setting where the Koopman representation is learned from data samples of the cryptosystem.
BibTeX
@inproceedings{schlor2023koopman,
  author = {Sebastian Schlor and Robin Strässer and Frank Allgöwer},
  title = {{Koopman interpretation and analysis of a public-key cryptosystem: Diffie-Hellman key exchange}},
  booktitle = {IFAC-PapersOnLine},
  year = {2023},
  doi = {10.1016/j.ifacol.2023.10.1693},
}
Figure