Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913606513197056 |
|---|---|
| author | Strässer, Robin Schlor, Sebastian Allgöwer, Frank |
| author_facet | Strässer, Robin Schlor, Sebastian Allgöwer, Frank |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_12714 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems Strässer, Robin Schlor, Sebastian Allgöwer, Frank Systems and Control Cryptography and Security Dynamical Systems 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. |
| title | Decrypting Nonlinearity: Koopman Interpretation and Analysis of Cryptosystems |
| topic | Systems and Control Cryptography and Security Dynamical Systems |
| url | https://arxiv.org/abs/2311.12714 |