Attacking cryptosystems by means of virus machines

1 Vol.:(0123456789) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports Attacking cryptosystems by means of virus machines Mario J. Pérez‑Jiménez 1,2, Antonio Ramírez‑de‑Arellano 1,2* & David Orellana‑Martín 1,2 The security that resides in the public-key cryptosystems relies on the presumed computational hardness of mathematical problems behind the systems themselves (e.g. the semiprime factorization problem in the RSA cryptosystem), that is because there is not known any polynomial time (classical) algorithm to solve them. The paper focuses on the computing paradigm of virus machines within the area of Unconventional Computing and Natural Computing. Virus machines, which incorporate concepts of virology and computer science, are considered as number computing devices with the environment. The paper designs a virus machine that solves a generalization of the semiprime factorization problem and verifies it formally. In recent years, surpassing the computational capacity of today’s computers has become a major goal in the digital world. As a result, researchers have turned to unconventional models to revolutionize problem-solving approaches. Natural computing1, a branch of Unconventional computation inspired by what occurs in nature, has gained significant traction with the emergence of neural networks, cellular automata, membrane computing, etc. In the vast field of virology, a virus stands as a diminutive yet potent infectious agent that crucially relies on infiltrating a host cell to perpetuate its reproductive cycle. With astonishing versatility, viruses showcase their ability to infiltrate not only animals but also plants and protist species, thus affirming their ubiquity within the intricate tapestry of the natural world. A staggering estimation postulates the coexistence of approximately 350 trillion viruses, a colossal quantity that surpasses the number of bacteria and cells by an astounding factor of 10. As the COVID-19 pandemic permeated society, the scientific community, as well as the populace at large, bore witness to the devastating capabilities harboured within the realm of viruses. Such pervasive prevalence inherently instigates an intellectual curiosity that beckons the exploration of the intricately woven computational aspects underlying this captivating biological structure, for more detail information we refer to2. Within the branch of unconventional computing, a promising and young model called virus machines3 has garnered attention. Inspired by the movement and replication behaviour of viruses within hosts, virus machines utilize an instruction graph to navigate and replicate itself through different channels within a system. Virus Machines have been studied as function computing mode, recognizer mode, and generating mode. This computing paradigm is universal (as powerful as turing machines) when there is no bounded restrictions on the number of hosts, instructions and viruses in the host3. In addition, it seems to be useful to solve mathematical problems in a numerical point of view, authors in4 computed an arithmetic calculator and two pairing functions by virus machines. Finally, authors in5 opened a computational complexity theory through these devices. Cryptography is a scientific discipline that concerns the security of the information in the presence of possible intruders, as well as authentication and identification, providing privacy and integrity. There are cryptosystems where the issuer has both a public and a private key to encrypt and decrypt (called asymmetrics), within asymmetric cryptography, highlights the public-key cryptosystems. The first published public key cryptosystem, named RSA, was established by Rivest etal.6. The paper is organized as follows. Next section briefly describes different versions of the integer factorization problems, and the next section to it is devoted to the RSA cryptosystem. In “Basic virus machines”, the computing paradigm of virus machines is presented. “Solving the least prime divisor problem by a deterministic virus machine” is devoted to describe a deterministic virus machine solving a generalization of the semiprime factorization problem. The paper ends with some open problems and concluding remarks. OPEN 1Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. 2SCORE Laboratory, I3US, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. *email: [email protected] 2 Vol:.(1234567890) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports/ The integer factorization problems The integer factorization problem is the following: given a natural number greater than 1, find its prime factorization. It is conjectured to be a computationally hard problem. A decision version of this problem is the semiprime factor problem that can be described as follows: given two natural numbers x,y greater than 1, determine whether or not x has a factor less than y. This problem belongs to the complexity classes NP, co-NP and BPQ7. It is interesting to notice that if that problem is NP-complete or co-NP-complete then NP = co-NP, for further information we refer to8. A generalization of the semiprime factorization problem is the least prime divisor (LPD): “Given a natural number n≥2 , determine the least natural number m≥2 such that m is a divisor of n”. Obviously, such m must be a prime number. This problem can be characterized by the partial function FLPD defined as follows: FLPD(n)=m if and only if n≥2 and m is least divisor of n greater than 2. Throughout this paper, a deterministic virus machine solving the least prime divisor problem (that is, computing the partial function FLPD ), will be designed and the formal verification of it will be considered. The RSA cryptosystem The RSA algorithm was the first public-key cryptosystem to verify the conditions formulated by Diffie and Hellman in its seminal work9. It was introduced by Rivest etal.6. The underlying presumed computationally hard problem of the RSA system is the semiprime factorization problem, previously described. This problem becomes unfeasible when very large semiprimes are considered as inputs. Consequently, decrypt the information provide by the RSA system is believed to be a computationally intractable problem as well as some hard problems used in cryptography (i.e. the knapsack problem in Merkle-Hellman cryptosystem10). In fact, it has not been proven that the existence of an efficient algorithm for factoring large semiprimes is not possible. Nevertheless, some pathways have been studied with other unconventional computing models, such as quantum computation, which highlights recent works in the benefits of quantum communication or the combination of quantum communication with classical cryptography11,12. Any large semiprime input n for RSA is used as the modulus for both public and private keys. In order to attack the RSA system, the factorization of n is needed. Many systems, such as banks, medical databases and critical systems with confidential information, keep their data secure thanks to this method. It is interesting to highlight the inherent asymmetry between generating large semiprimes and factoring them. Basic virus machines This young computing paradigm, inspired by the way viruses are transmitted and replicated between hosts, was first introduced in3. Next, the syntax of this paradigm is formally defined. Definition 1 A virus machine (VM, for short) of degree (p,q), p,q≥1 , is defined as the following tuple �=(Ŵ,H,I,DH,DI,GC,n 1 ,...,np,i 1 ,hout) , where: • Ŵ={v} is the singleton alphabet: • H={h 1 ,...,hp} and I={i 1 ,...,iq} are ordered sets such that v/∈H∪I , H∩I=∅ and hout /∈I∪{v} : either hout ∈H or hout /∈H (in this case, hout represents the environment and it is denoted by h0) ; • DH=(H∪{hout },EH,wH) is a weighted directed graph (WDG for short), where EH⊆H×(H∪{hout }) such that (h,h)/∈EH , for each h∈H , out-degree (hout )= 0, and wH is a mapping from EH onto N\{0} ; • DI=(I,EI,wI) is a WDG, where EI⊆I×I , wI is a mapping from EI onto N\{0} and the out-degree of each node is zero, one or two; • GC=(VC,EC) is an undirected bipartite graph, where VC=I∪EH , being {I,EH} the partition associated with it, in addition each edge connect an element from I with, at most, an arc from EH ; • i1∈I and nj∈N , for each j, 1≤j≤p , where N is the set of natural numbers. Formally, a virus machine �=(Ŵ,H,I,DH,DI,GC,n 1 ,...,np,i 1 ,hout) of degree (p,q), is a tuple that can be viewed as an ordered set of p hosts labelled as h 1 ,...,hp , where each host hj initially contains nj viruses, and an ordered set of q control instruction units labelled with i 1 ,...,iq∈I . In this work, symbol hout /∈H and it represents the output region, denoted by h0 in this work. Arcs (hs,hs ′ ) , where s = s′ , from the weighted directed graph DH represent transmission channels through which viruses can transmit from one host hs∈H to another different host or region hs ′ ∈H∪{h0} . The computation of a virus machine starts with the activation of instruction i1 . At any moment, at most one instruction ij is activated: if a instruction ij is attached to the channel (hs,hs ′ ) with weight ws,s′ and it is activated at instant t, then it will be opened and one virus will be transmitted and replicated ws,s′ from hs to hs′ , so one virus is consumed at hs , and ws,s′ viruses reach hs′ . Unless this situation happen, every channel is closed. Arcs from the directed graph DI represent the instruction paths that will follow the computation, and they have associated with a weight. Finally, the undirected bipartite graph GC represents the instruction-channel relation by which an edge {ij,(hs,hs ′ )} indicates a control between instruction ij and channel (hs,hs ′ ) . Graphically, an example of virus machine of degree (4,6), can be viewed in Fig.1. As in previous works, each host is depicted as a rectangle and each instruction is drawn as a blue circle. The directed arrows are assigned with a weight (or weight 1 if it is not marked). The instruction-channel arcs are represented as dotted red lines. The semantics are then described as follows: a configuration Ct or an instant description at an instant t of a virus machine is a tuple (b 1, t,...,bp , t,ut,b 0, t) where b 0, t,b 1, t,...,bp , t are natural numbers (representing the number of viruses within the environment h0 and the hosts h 1 ,...,hp , respectively), and ut∈I∪{#} , 3 Vol.:(0123456789) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports/ being #/∈H∪{h0}∪I . If ut∈I , then ut will be activated at step t+1 , otherwise, if ut=# , then no instruction will be activated and a halting configuration is reached. The initial configuration of a system �=(Ŵ,H,I,DH,DI,GC,n 1 ,...,np,i 1 ,hout) is defined as C 0 =(n 1 ,...,np,i 1 ,0) . We say that a non halting configuration Ct=(b 1, t,...,bp , t,ut,b 0, t) yields configuration Ct +1 =(b 1, t +1 ,...,bp , t +1 ,ut +1 ,b 0, t +1 ) in one transition step, denoted by Ct⇒Ct+1 , if we can go to it in the following way. (a) Assuming that the control instruction unit ut is attached to a channel (hs,hs ′ ) . If bs,t≥1 then bs+1,t=bs,t−1 and bs ′ +1,t=bs ′ ,t+ws,s′ If bs,t=0 then bs+1,t=bs,t and bs ′ +1,t=bs ′ ,t . If ut is not attached to any channel then there is no virus transmission. (b) Object ut+1∈I∪{#} is obtained depending on the out-degree of ut as follows: • If out-degree of (ut) is equal to 2 and (ut,ut ′ ),(ut,ut ′′ )∈EI , with t = t′ , then the following holds: (1) if ut is not attached to any channel then the next instruction ut+1 will be either ut′ or ut′′ , chosen in a non-deterministic way; (2) if ut is attached to a channel (hs,hs ′ ) and bs,t≥1 , then ut+1 is maximum between wt,t′ and wt,t′′ , other wise ut+1 is minimum between these two instructions. In both cases, when wt,t′=wt,t′′ , either ut+1=ut′ or ut+1=ut′′ , are selected non-deterministically. • If outdegree(ut)=1 then the system behaves deterministically and ut+1 follows the unic possible path in EI . • If there is no possible path, then ut+1=# , and Ct+1 is a halting configuration. A computation of a virus machine is a (finite or infinite) sequence of configurations such that: (a) the first term is the initial configuration C0 of the system; (b) for each n≥2 , the n-th term of the sequence is obtained from the previous term in one transition step; and (c) if it is a halting computation (the sequence is finite) then the last term is a halting configuration. Remark 1 Virus machines are sequential devices, that is, in any instant at most a control instruction unit is activated and, hence, at most one transmission channel will be opened. Definition 2 A virus machine with input, of degree (p,q,r),p≥1, q≥1, r≥1, is a tuple �=(Ŵ,H,Hr,I,DH,DI,GC,n 1 ,...,np,i 1 ,hout), where: • (Ŵ,H,I,DH,DI,GC,n 1 , ... ,np,i 1 ,hout) is a Virus Machine of degree (p,q). • Hr={ha1,...,har}⊆H is the ordered set of r input hosts and hout /∈Hr . If  is a virus machine with input of degree (p,q,r) and (α1,...,αr)∈Nr , the initial configuration of  with input (α1,...,αr) is (n 1 ,...,na1+α 1 ,...,nar+αr,...,np,it,0) , denoted by �+(α1,...,αr) proceeds as stated before. The result of a halting computation is the number of viruses sent to the output region (the environment) during that computation. Next, virus machines providing function computing devices, is introduced. Definition 3 We say that a partial function f :N k −→ N , k≥1 . is computed by a virus machine  with k input hosts, if for each (x1,...,xk)∈ N k , we have: n1 h1 n2 h2 n3 h3 n4 h4 2 2 i1 i2 i3 i4 i5 i6 2 2 2 2 Figure1. Structure of a virus machine . 4 Vol:.(1234567890) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports/ • If (x1,...,xk)∈dom(f) with f(x1,...,xk)=z , then every computation of the virus machine �+(x1,...,xk) is a halting computation and the result is z. • If (x1,...,xk)∈ N \dom(f) , then every computation of the virus machine �+(x1,...,xk) is a non-halting computation. Example of a deterministic virus machine For a better understanding in the behavior of these devices, a basic example from5, is presented. Let add a deterministic virus machine computing the addition function add :N2→N , with add(a,b)=a+b , defined as follows: �=(Ŵ,H,H2,I,DH,DI,GC, 0, 0, i1,h0) , where: • Ŵ={v} , H={h1,h2}=H2 , and I={i1,i2,i3} ; • DH=(H,EH={(h1,h0),(h2,h0)},wH) , where wH(h1,h0)=wH(h1,h0)=1 ; • DI=(I,EI={(i1,i1),(i1,i2),(i2,i2),(i2,i3)},wI) , where wI(i1,i1)=wI(i2,i2)=2 , a n d wI(i1,i2)=wI(i2,i3)=1 ; • GC=(I∪EH,EC={(i1,(h1,h0)),(i2,(h2,h0))}) The VM add , can be depicted in Fig.2. Given an input (a,b)∈ N 2 , the computation of the machine woks as follows. The initial configuration is of �add +(a,b) , is C0=(0+a,0+b,i1,0) , from here, instruction i1 opens the channel (h1,h0) , then the computation depends on the value of a: • if a>0 , a virus is transmitted from host h1 to the environment and the next instruction follows the highest weight path from i1 , that is going to i1 again with the following configuration C1=(a−1, b−1, i1,1) , instruction i1 will be activated until host h1 is empty, thus the configuration Ca=(a−a,b,i1,a) is reached. • If a=0 , then there is no virus transmission and next instruction is the least weight path, that is instruction i2 and the following configuration remains, C1=(0, b,i2,0) . Note that for all values of a, the configuration is Ca+1=(0, b,i2,a) , from here, the computation is analogous and configuration Ca+1+b=(0, b−b,i2,a+b) , as the host h2 is now empty, there is no virus transmission and next instruction is i3 as it follows the least weight path taking the configuration Ca+b+2=(0, 0, i3,a+b) , as i3 is not attached to any channel and the out −degree(i3) is zero, we reach a halting configuration Ca+b+3=(0, 0, #, a+b) . That is, after a+b+3 steps, the machine halts and returns a+b , which is the addition of a and b. Solving the least prime divisor problem by a deterministic virus machine In order to solve the least prime divisor problem by using virus machines, it suffices to design such a machine that computes the partial function FLPD characterizing this problem. Specifically, in this Section a deterministic virus machine that computes FLPD , is presented. From now on, since the description of a single virus machine can be tedious to read, it is easy to depict them with graphics and setting that i1 is the initial instruction. a h1 b h2 i1i2i 3 2 2 Figure2. A deterministic virus machine �add + (a,b) computing the addition function. 5 Vol.:(0123456789) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports/ Let us consider the VM �LPD =(Ŵ,H,H1,I,DH,DI,GC, 0, 2, 0, 0, 1, i1,h0) with input of degree (5,10,1), graphically defined in Fig.3. A sketch of the formal verification A method to formally verify that a computational device of a model solves a given problem is to find invariant formulas in some relevant loops of the device, in such a way that the veracity of those formulas at the end of the loops provides relevant information. Next, we give a sketch of a virus machine with respect to the least prime divisor problem, that is, we must prove mathematically that the designed virus machine computes the partial function FLPD associated with that problem. Specifically, we will set the result an interesting input: for any odd number. For a detailed formal verification we refer to Appendix A. Let us suppose that n=p 1 ·qp1 where p 1 = 2 is the least prime factor and q p1= n p1 . Let us consider the following notation: 1. For every j∈N , such that j≥2 , we consider qj , the quotient of the integer division between n and j, and αj=4qj+4n+7 . 2. Let βk=α2+···+αk , for every natural number k≥2 . Finally, let us consider the following formula: This formula is an invariant of the machine, and by induction we get the following proposition. Proposition 1 ∀k(0≤k≤p1−1−→ ϕ(k)is true ) . From Proposition 1, we deduce that the formula φ(p1−1) is true, thus we have φ(p 1 −1)≡C β( p1 −1) =(n,p 1 , 0, 0, 1, i 1 ,0) , from here a halting configuration is reached after qp1·(3p 1 +4) transition steps and returns p1 . Time complexity Formal verification also results in a useful tool for studying the time complexity of a device as we know exactly the number of the steps necessary for the machine halts. From Remark 4 in Appendix A, we can conclude that the time complexity of this machine belongs to the quadratic order O(n2) , for 1-ary encoding. The idea of the proof is to focus on the worst case, that is, when the input n is a prime number and to show that it is of quadratic order. Conclusions The security of the first public-key cryptosystem (RSA) lies in the presumed intractability of the semiprime problem, from a computational complexity point of view. This problem is characterized by the partial function FLPD defined as follows: FLPD(n)=m if and only if n≥2 and m is least prime divisor of n. Throughout this paper, a deterministic virus machine solving the least prime divisor, has been designed and the formal verification of it is proved. Despite of the lack of efficiency that should be improved, these devices gives an interesting scope for φ( k)≡C βk =(n,k+1, 0, 0, 1, i1,0), for 2 ≤k≤p1− 1 n h1 2 h2 h3 h4 1 h5 2 i1i2 i3 i4 i 5 i6 i7 i8 i 9 i 10 2 2 2 2 2 2 i1activates h2→h3 i2activates h1→h4 i3activates h1→h4 i4activates h4→h1 i5activates h3→env i6activates h5→h2(2 ) i7activates h2→h5 i8activates h4→h1 i9activates h3→h2 Figure3. A deterministic virus machine LPD +n solving the LPD problem. 6 Vol:.(1234567890) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports/ solving numerical problems thanks to the mathematical integrity of the formal verification and its easy study of time complexity. Furthermore, while the concept of virus machines is relatively new, there are numerous unexplored avenues within this field. Currently, the lack of efficiency of virus machines is because of its sequential behavior, and exploring parallelism could potentially enhance this aspect. Future research directions could involve expanding the model to incorporate additional biological aspects, deepening our understanding of virus functionality and exploring potential applications. Establishing connections between virus machines and traditional virology is also an intriguing area for exploration. Finally, while improvements in efficiency are studied, we believe that a specific hardware implementation could figure out an innovative scope. Data availability The datasets used and/or analysed during the current study available from the corresponding author on reasonable request. Received: 23 June 2023; Accepted: 6 December 2023 References 1. Rozenberg, G., Bäck, T. & Kok, J. N. Handbook of Natural Computing Vol. 4 (Springer, 2012). 2. Dimmock, N. J., Easton, A. J. & Leppard, K. N. Introduction to Modern Virology (Wiley, 2015). 3. Valencia-Cabrera, L., Pérez-Jiménez, M. J., Chen, X., Wang, B. & Zeng, X. Basic virus machines. In 16th International Conference on Membrane Computing (CMC16), 323–342 (2015). 4. Ramírez-de Arellano, A., Orellana-Martín, D. & Pérez-Jiménez, M. J. Using virus machines to compute pairing functions. Int. J. Neural Syst. 33, 2350023 (2023). 5. Ramírez-de-Arellano, A., Orellana-Martín, D. & Pérez-Jiménez, M. J. Generating, computing and recognizing with virus machines. Theoret. Comput. Sci. 972, 114077. https:// doi. org/ 10. 1016/j. tcs. 2023. 114077 (2023). 6. Rivest, R. L., Shamir, A. & Adleman, L. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978). 7. Shor, P. W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, 124–134 (IEEE, 1994). 8. Garey, M. R. & Johnson, D. S. Computers and Intractability Vol. 174 (Freeman, 1979). 9. Hellman, M. New directions in cryptography. IEEE Trans. Inf. Theory 22, 644–654 (1976). 10. Merkle, R. & Hellman, M. Hiding information and signatures in trapdoor knapsacks. IEEE Trans. Inf. Theory 24, 525–530 (1978). 11. Pan, D., SOng, X.-T. & Long, G.-L. Free-space quantum secure direct communication: Basics, progress, and outlook. Adv. Devices Instrum. 4, 2350023. https:// doi. org/ 10. 34133/ adi. 0004 (2023). 12. Long, G.-L. et al. An evolutionary pathway for the quantum internet relying on secure classical repeaters. IEEE Netw. 36, 82–88. https:// doi. org/ 10. 1109/ MNET. 108. 21003 75 (2022). Acknowledgements The research described in this work is supported by the Zhejiang Lab BioBit Program (Grant No. 2022BCF05). This work was also supported by the research project FEDER/Junta de Andalucía-Paidi 2020/Proyecto (P20 00486). D. Orellana-Martín acknowledges Contratación de Personal Investigador Doctor. (Convocatoria 2019) 43 Contratos Capital Humano Línea 2. Paidi 2020, supported by the European Social Fund and Junta de Andalucía. Author contributions Conceptualization, A.R.-d.-A., D.O.-M. and M.J.P.-J.; methodology, D.O.-M. and A.R.-d.-A.; validation, A.R.-d.- A.; formal analysis, D.O.-M. and M.J.P.-J.; investigation, D.O.-M. and A.R.-d.-A.; writing-original draft preparation, D.O.-M., A.R.-d.-A. and M.J.P.-J.; writing-review and editing, A.R.-d.-A.; supervision, D.O.-M. and M.J.P.-J. All authors have read and agreed to the published version of the manuscript. Competing interests The authors declare no competing interests. Additional information Supplementary Information The online version contains supplementary material available at https:// doi. org/ 10. 1038/ s41598- 023- 49297-6. Correspondence and requests for materials should be addressed to A.R.-d. Reprints and permissions information is available at www.nature.com/reprints. Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. 7 Vol.:(0123456789) Scientific Reports | (2023) 13:21831 | https://doi.org/10.1038/s41598-023-49297-6 www.nature.com/scientificreports/ Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http:// creat iveco mmons. org/ licen ses/ by/4. 0/. © The Author(s) 2023