Int. J. Communications, Network and System Sciences, 2010, 3, 579584 doi:10.4236/ijcns.2010.37077 Published Online July 2010 (http://www.SciRP.org/journal/ijcns/). Copyright © 2010 SciRes. IJCNS Hybrid Authentication Cybersystem Based on Discrete Logarithm, Factorization and Array Entanglements Boris S. Verkhovsky Computer Science Department, New Jersey Institute of Technology, Newark, USA Email: verb@njit.edu Received July 13, 2009; revised February 28, 2010; accepted May 10, 2010 Abstract A hybrid cryptographic system providing digital authentication is described and analyzed in this paper. The proposed cryptosystem incorporates three features: complexity of the discrete logarithm problem, complexity of integer factorization of a product of two large primes and a combination of symmetric and asymmetric keys. In order to make the cryptosystem less vulnerable to cryptanalytic attacks a concept of digital entan glements is introduced. As a result, the proposed cryptographic system has four layers (entanglementencryption decryptiondisentanglement). It is shown that in certain instances the proposed communication cryptocol is many times faster than the RSA cryptosystem. Examples provided in the paper illustrate details of the pro posed authentication cryptocol. Keywords: CryptoImmunity, Cybersecurity, Digital Authentication, Array Entanglements, MultiLayer Cryptographic Protection, Hybrid Cryptocol 1. Introduction and Basic Definitions In this paper a hybrid digital signature cybersecure com munication system is described and analyzed. In order to make this cryptosystem faster and less vulnerable to cryptanalytic attacks a concept of entang lemen ts is in troduced [1,2]. Furthermore, in this cryptographic proto col there are four layers (entanglementencryptiondecry ptiondisentanglement). Since there is no onetoone mapping between a plaintext block and the correspond ing ciphertext block, this system of communication is less vulnerable to plaintext attacks. The overall crypto graphic algorithm is a hybrid protocol that incorporates three features: discrete logarithm problem modulo large prime [3], factorization of a product of two large primes [4] and a combination of symmetric and asymmetric keys. To describe the proposed cryptosystem, let’s consider A1. An array 12 ,,.., r maa a (1) consisting of r blocks of a digitized plaintext that is to be transmitted from a sender (Alice) to a receiver (Bob); B1. A square nonsingular matrix E with rr 0E and h = Em. (2) In the paper 1,.., r hhh (3) and E are respectively called a vector and matrix of entanglements [1]. C1. A sufficiently strong cryptographic protocol L that is used for encryption of one of the entanglements, for example, , with corresponding ciphertext . 1 h1 c In order to speed up the encryption/decryption proce dure and as a result to minimize the entire communica tion time it is necessary to minimize the amount of com putations. For that reason there is no necessity to encrypt all other entanglementsji h , where j = 1, 2,.., i – 1, i + 1,.., r and is the encrypted entanglement. Indeed, if is not known to a potential intruder, then he or she must solve a system of r equations, where only r – 1 components of vector h are publicly known. In the cryptosystem described below the size r of the array m is a tradeoff between cryptoimmunity and acceleration of the decryption: the larger the value of r, the faster the overall communication protocol. On the other hand, the larger r is, the less time is required to cryptanalyze the entire message. i h i h To avoid confusions, it is important to indicate the following distinctions: The matrix of entanglement E (and nonlinear map pings) discussed below are not secret keys as in an affine cryptographic algorithm; all elements of matrix E are publicly known; In contrast with the RSA and Rabin algorithms, k n
B. S. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 580 2 2 is a private key of the kth user, not a public key. 2. Digital Signature Scheme 2.1. System Design Module (Users Establish their Private and Public Key): A2. All users agree on a large prime p and a generator g, where 2gp (4) Remark 1: selection of a generator for a large prime p is a nondeterministic procedure. However, if both p and are primes, then (1)/p g := (3p – 1)/4 (5) is a generator [5]. B2. Each user selects large primes and , such that k pk q 2(mod 3) kk pq , (6) and that their product satisfies two constraints: k n k pn p (7) C2. Each user computes her/his public key (en cryption key) and private key , where e is co prime with , i.e., k e kk d k z gcd( ,) 1 kk ze (8) D2. Every user computes a multiplicative inverse of modulo k d k e :(1)( 1) kk k zp q [4] i.e., satisfies the equation k d 1(mod ) kk k de z (9) E2. If Alice and Bob intend to secretly exchange authenticated information, they establish a secret key by using the DiffieHellman key ex change [3]. :mod AB ab wg p 2.2. Encryption/Decryption Module (Alice Sends to Bob a Plaintext Array m): F2. Using an open channel Alice asks Bob to secretly send to her Bob’s secret key n; G2. Bob computes :modBAB nw p and sends x to Alice; she recovers; 1 :mod BAB nxw p H2. Using the RSA protocol Alice encrypts {see (2)}: i h :modB; e ii ch n [4]; (10) I2. Alice transmits the array to Bob; 11 1 ,..,, ,,.., iii r hhch h J2. Bob decrypts : i c ;:mod B d i vc n{=hi}; (11) K2. Using 1,.., r hhh Bob recovers all plaintext blocks 12 ,,..,r a ama; L2. If the original array m is intelligible, but the re covered text is not, then Bob realizes that it was forged by an intruder; otherwise Bob accepts authenticity of the text. 2.3. Selection of Block Size and Matrix of Entanglements To make sure that the entanglements are smaller than every ni, {otherwise the entire array is not recoverable}, select the matrix of entanglement E and such division of a plaintext onto blocks that the maximal value of the ith entanglement hi does not ex ceed 12 ,,.., r maa a p , (7)}. Example 1: Let :(,,,,)m abcde and 12345 ,,,,h hhhhh, (12) 12 3 4 5 where :2; :2; :2; :2; :2. hd ehab habc hcde habcd (13) 1324 5 23 51 Then 3(42); 2;2; 2;()/2. bhhh hh ahb chab dhabce hd (14) Let’s specify that every block in m must satisfy a threshold ak < t. Then (13) implies that max 5 i ht pn i p . (15) Therefore, for every k = 1,…, r must hold /5 k at p ; and if 2/3 , then . 2/15 k at p From the recovery procedure (14) it is clear that we can compute all initial blocks a, b, c, d and e only if we know all numeric values 12345 from (13). Henceforth, this fact implies that it is sufficient to en crypt at least one of these entanglements to securely pro tect all five plaintext blocks. ,,,,hh hhh Furthermore, it is necessary to notice that entangle ments themselves do not provide secure protection. In the proposed cryptographic scheme instead of employing just one layer (plaintext/encryption/ciphertext) we pro pose two layers (plaintext/entanglement/encryption/ci
B. S. VERKHOVSKY581 phertext) between the plaintext array (a, b, c, d, e,…) and ciphertext (,…). 12345 ,,,,chhhh Remark 2: The RSA algorithm discussed below is just an example of how can be encrypted. Any strong cryptocol based on the complexity of factorization of n = pq can also be used. The Rabin algorithm [6] or (hyper) ellipticcurve cryptography [710] based on modulo composite n are other possible applications. i h 2.4. Essence of RSA Digital Signature Algorithm In order to demonstrate the advantages of the proposed digital signature algorithm, let’s recall the RSA digital signature algorithm [4,11]. Suppose Alice wants to send to Bob a message with a digital signa ture. Then for every k = 1, 2,…, r Alice signs 12 ,,.., r maa a k a : d kk a with her private key, then encrypts it with Bob’s public key mod A n :modB e kk B cf n; (16) and transmits the ciphertext to Bob over an open communication channel. Bob decrypts k c :mod B d cn and then verifies the signature: :mod A e A; xn {y = m}; (17) If y is intelligible, then Bob accepts it as an authenti cated message from Alice. 3. Examples of Entanglements 3.1. Linear Transformations Example 2: Let 0111 12 21211 1 :;: :;..,: rr r rr r haa ah aaa haaa haaa ; . r (18) Proposition 1: If all entanglements 012 1 ,, ,.., r hhh h are known and integer, then for every k = 1,.., r – 1 0/2 kk ahh (19) 0121 r ah aaa r (20) and all are integers as well. k Proof follows from two observations: a for every k = 1,.., r – 1 02 k ; (21) k hh a all have the same parity which im plies that their pairwise differences are even. Therefore, every is an integer. Q. E. D. 012 1 ,, ,.., r hhh h 12 ,,.. and r aa a Complexity of recovery: It requires r – 1 subtractions and divisions by 2 (binary shifts) to recover the first r – 1 blocks in (19) and r – 1 subtractions to recover the last block in (20). If a sender (Alice) encrypts only s of all entanglements, where 0 < s < r, then the intruder will not be able to de duce any blocks (provided that the matrix E is properly selected and a portion of entanglements is encrypted with a sufficiently strong PKC protocol). In an extreme case, if s = 1, then the intruder must solve a system of equa tions Ea = g, where the matrix E is known but only r – s elements of vector g are known. However, this is impos sible, because to find the blocks the intruder must know all r elements of vector g. 12 ,,.., r aa a 3.2. NonLinear Transformations In the more general case, the entanglements can be nonlinear, i.e. h := E(a), and/or some components of the transformation E(a) can be also encrypted. For example, if h := Ea, then we can encrypt several elements of ma trix E. This approach is beyond the scope of this short paper. It is important to bear in mind that the selection of the transformation E(a) affects the computational com plexity of the recovery process. The choice of the mapping E is important. If E is a matrix, then it must be nonsingular and selected in such a way that the recovery will not become a computation ally formidable. Example 3: Let’s consider an array of r plaintext blocks and the following r entangle ments: 12 1 ,,.., , r hhh h r . 2 22 22 112223 22 11 1 :;:; :;: rrrr r haahaa haahaa (22) It is obviously sufficient to encrypt only one of the entanglements. Then, after the decryption, we proceed as follows: 2 121 1 : r whhha a r . (23) Therefore, 1/; / rrrr ahwhah wh r ; (24) and for k from 2 to r – 1 2 1kkk aah 1 . . (25) Combined with encryption these nonlinear entangle ments provide secure protection and recovery for every transmitted array. Yet, they require divisions of integers and extraction of square roots, which are computation ally more complicated procedures. 3.3. Improper Entanglements Example 4: Let 112212 312312 :2;:; :;..,: rr haahaa haaahaa a (26) Copyright © 2010 SciRes. IJCNS
B. S. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 582 r If r > 2, it is insufficient to encrypt only one of these entanglements. Indeed, if is encrypted, then for all 1 h3kr 1kkk ahh . (27) In general, if i is fixed, , and only is en crypted, then 2ii h 112 ;ahh (28) and for all and 3 1ki 2ik 1kkk ahh . (29) Therefore, r – 2 blocks are cryptographically unpro tected in every array. 4. Tradeoff Analysis Every block in (16)(17) requires four exponentiations for encryption and decryption. In contrast, in the protocol A.2L.2 described above, (4)(11), the array of r blocks requires only one exponentiation for its encryption and decryption. Therefore, the larger the transmitted array r is, the more efficient the speedup of A.2L.2 is. If r = 100, then A.2L.2 is four hundred times faster than the RSA algorithm. Furtermore, if A nmn , then the RSA digital sig nature algorithm (16)(17) fails to recover the original plaintext m unless special measures are taken [4,11]. The application of entanglements (linear or nonlinear trans formations) is a tool that is proposed to accelerate the encryptiondecryption process. Although the entangle ments themselves do not provide protection, yet, when used in combination with other measures, they decrease the amount of computations necessary for the entire en cryption/decryption process. It is necessary to mention that any detailed and credi ble quantification of the tradeoff between the size r of the array and cryptoimmunity requires analysis of all strategies potentially available to the intruder. Yet to qualitatively illustrate this point of view, let’s consider an asymptotic case, where the size r of the transmitted array of plaintext blocks is very large. From one point of view, the larger r is, the more advantageous the proposed cryptosystem is. Indeed, only one entanglement is en crypted/decrypted instead of all r entanglements as it is done in the RSA, ElGamal, Rabin [6], ECC [79] and other PKC cryptosystems [10]. On the other hand, if the size r of the array is very large, then the intruder can in vest the required time and computing resources to crypt analyze the encrypted entanglement. Let’s consider an extreme case, where the entire mes sage M consists of N blocks. Let’s select a square non singular N × N matrix E, compute N entanglements 12 ,,.., hh h 1 h using (18) and encrypt only one of them, say, . For instance, if the sender transmits information re garding highlysensitive issues of longterm national policy or the details of a major corporate policy, the in truder will invest all available resources to break the en crypted entanglement [1218]. Therefore, for secu rity purposes, it is safer to divide the entire file M onto several parts/arrays and securely protect each array. 1 h 5. Decryption: Reduction of Complexity The most serious computational bottleneck of the present publickey cryptographic protocols is that they are noto riously slow and therefore cannot be used in the realtime exchange of sensitive information. Although we are far away from completely eliminat ing this bottleneck, the proposed cryptosystem is a sys temic tool that accelerates secure communication via open channels of the Internet or within corporate net works. Eliminating the bottleneck mentioned above is one of major research areas today and will likely occupy hun dreds of communication specialists and system designers for years ahead. Various PKC algorithms were intro duced in the last thirty years. Ellipticcurve cryptography and its hyperelliptic extension are vivid examples of this research: to accelerate the encryption/decryption process. The proposed cryptosystem is another illustration of how we can accelerate the PKC protocols if the entangled arrays rather than individual blocks are encrypted. 6. Illustrative Numeric Example The steps A4H4 describe a system design stage and the steps I4L4 describe its implementation for signed en cryption and authenticated decryption of arrays m = 1,.., r aa: A4. Let Alice and Bob select p = 1907, a generator g = 1430, (5), and 2/3 , (1315); B4. Let each Alice and Bob select two pairs of primes: {,}{29,47} {,}{17,89} AA BB pq pq and where 2(mod3) 363 AA BB pq pq, (30) and compute their products [1]: :=1 and :1513 AAABBB npqnpq ; (31) then {,,} AA pqn {, ,} is a triad of Alice’s private keys and BB pqn is a triad of Bob’s private keys; C4. {Establishment of a secret key w}: w must satisfy the inequalitywp ; Alice and Bob randomly select secret integers a = 7 and b = 10 respectively and com pute ; :a ugmodp1601 1p and ; : mod733 b yg D4: Alice transmits u to Bob, who transmits y to Al ice; E4. Alice and Bob compute respectively
B. S. VERKHOVSKY583 pp:mod A a wy and . (32) :modb B wu As a result, mod 1118 AB ab AB wwwg p (33) is their secret key; F4. Alice and Bob compute a multiplicative in verse1 B w of their secret key B w:1 B w = 1281 [11]; G4. {Alice requests Bob to send his private key n to her}: Bob computes v and sends it to Alice: :mod 25 BAB vnwp; H4. Alice recovers Bob’s private key: 1mod19071513 BAB nvw ; I4. Suppose that Alice and Bob select their public keys . 3 AB ee Consequently, ; mod 1 AA A de z and ; mod 1 BB B de z imply that ; and . 909 A d1009 B d J4. Suppose Alice intends to transmit to Bob over the Internet an encrypted array m := {324, 241, 332, 108, 412} with her digital signature. If she selects the entanglements (13), then h = {1234, 500, 568, 1350, 1588}. If 2/3 , then satisfies the requirement (15); 1 h K4. Alice encrypts: 1 h 11 :mod B B e ch n1476, and transmits to Bob; 12345 ,,,,chh hh L4. Bob decrypts the ciphertext c1: 1 :mod B B d cn1234 {=}; 1 h M4. Using (14), Bob recovers . Because nobody except Bob knows his private key nB, only he can recover the correct values of all plaintext blocks. If the recovered message is intelligible, Bob accepts it as the authentic message from Alice. 15 ,..,hhh Preliminary results of this paper are published in [19]. 7. Conclusions This paper describes a novel concept for the PKC that employs a combination of DLP, factorization and entan glements, which facilitates otherwise computationally dif ficult problem [12,14,19]. Let’s summarize the most important issues that were described and briefly discussed in this paper: A: In contrast with RSA, k is a private key of the kth user, not the public key [19]; n B: In another contrast, the encryption/decryption is applied not to every block of the plaintext, but to every array of blocks; in other words, the unit of protection is not a block, but an array of several blocks [20]; C: Within each array prior to encryption all blocks are entangled [1]; D: The advantage of entanglements is that they are in terdependent; the disadvantage is that if one entangle ment is corrupted, it affects the entire array. Namely, that array cannot be recovered by the receiver [2]; E: If the information is transmitted in an aggressive media and subject to networking failures or errors, the proposed cryptosystem cannot be used unless additional measures of information assurance are applied (see [21,22]). F: As a byproduct of interdependence, there is no ne cessity to encrypt and decrypt each block or each entan glement. Instead it is sufficient to encrypt only one of r entanglements [23]. This is the first advantage of the proposed protocol. G: The application of cryptography based on a cu bicroot provides the second advantage. The encryption requires only two multiplications [1]; H: The overhead of the entanglements is on the stage of information recovery: it is necessary to solve a system of r equations with r unknowns. Yet, there are many ways how to select matrix E that will make these com putations easier. Several linear and nonlinear examples of entanglements are provided above for illustration. Additional examples of entanglements are described in [20]. The proposed cryptosystem also provides a digital signature protocol. 8. Acknowledgements The author would like to express his appreciation to I. V. Semushin for assistance and to P. Fay for comments that improved the style of this paper. 9 . References [1] B. Verkhovsky, “Entanglements of Plaintext Streams and Cubic Roots of Integers for Network Security,” Advances in Decision Technology and Intelligent Information Sys tems, Vol. IX, 2008, pp. 9093. [2] B. Verkhovsky, “Information Assurance Protocols: Effi ciency Analysis and Implementation for Secure Commu nication,” Journal of Information Assurance and Security, Vol. 3, No. 4, 2008, pp. 263269. [3] W. Diffie and M. E. Hellman, “New Directions in Cryp tography,” IEEE Transactions on Information Theory, Vol. IT22, No. 6, 1976, pp. 644654. [4] R. Rivest, A. Shamir and L. Adleman, “A Method of Obtaining Digital Signature and PublicKey Cryptosys tems,” Communication of ACM, Vol. 21, No. 2, 1978, pp. 120126. [5] B. Verkhovsky, “Deterministic Algorithm for Generators of Strong Primes,” CS06 Research Report, NJIT, 2006. Copyright © 2010 SciRes. IJCNS
B. S. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 584 [6] M. O. Rabin, “Digitized Signatures and Public Key Func tions as Intractable as Factorization,” MIT/LCS Technical Report, TR212, Cambridge, 1979. [7] V. S. Miller, “Use of Elliptic Curves in Cryptography,” Lecture Notes in Computer Science, Vol. 218, No. 85, 1985, pp. 417426. [8] N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation, Vol. 48, No. 177, 1987, pp. 203209. [9] N. Koblitz, A. Menezes and S. Vanstone, “The State of Elliptic Curve Cryptography,” Designs, Codes and Cryp tography, Vol. 19, No. 23, 2000, pp. 173193. [10] N. Koblitz, “Hyperelliptic Cryptosystems,” Journal of Cryptology, Vol. 1, No. 3, 1989, pp. 139150. [11] B. Verkhovsky, “OverpassCrossing Scheme for Digital Signature,” International Conference on Systems Re search, Informatics and Cybernetics, BadenBaden, Ger many, July 2931, 2001. [12] J. M. Pollard, “Monte Carlo Methods for Index Computa tion Mod P,” Mathematics of Computation, Vol. 32, No. 143, 1978, pp. 918924. [13] V. I. Nechaev, “Complexity of a Deterministic Algorithm for the Discrete Logarithm,” Mathematical Notes, Vol. 55, No. 2, 1994, pp. 165172. [14] A. M. Odlyzko, “Discrete Logarithms: The Past and the Future,” Designs, Codes and Cryptography, Vol. 19, No. 23, 2000, pp. 129145. [15] J. M. Pollard, “Kangaroos, Monopoly and Discrete Loga rithms,” Journal of Cryptology, Vol. 13, No. 4, 2000, pp. 437447. [16] D. R. Stinson, “Some BabyStep GiantStep Algorithms for the Low Hamming Weight Discrete Logarithm Prob lem,” Mathematics of Computation, Vol. 71, No. 237, 2002, pp. 379391. [17] M. Chateauneuf, A. Ling and D. R. Stinson, “Slope Packings and Coverings, and Generic Algorithms for the Discrete Logarithm Problem,” Journal of Combinatorial Designs, Vol. 11, No. 1, 2003, pp. 3650. [18] J. Coron, D. Lefranc and G. Poupard, “A New BabyStep GiantStep Algorithm and Some Applications to Crypt analysis,” Lecture Notes in Computer Science, Vol. 3659, 2005, pp. 4760. [19] B. Verkhovsky, “Fast Digital Signature Hybrid Algo rithm Based on Discrete Logarithm, Entanglements of Plaintext Arrays and Factorization,” 7th International Conference Mathematics Modeling in Physics, Technol ogy, SocioEconomic Systems and Processes, Ulyanovsk, Russia, 2009, pp. 1316. [20] B. Verkhovsky, “Information Assurance and Secure Streaming Algorithms Based on Cubic Roots of Inte gers,” In the Fifth International Conference on Informa tion Technology: New Generations (ITNG08), Las Vegas, USA, 2008, pp. 910916. [21] B. Verkhovsky, “Control Protocols Providing Informa tion Assurance in Telecommunication Networks,” Jour nal of Telecommunications Management, Vol. 2, No. 1, 2009, pp. 5968. [22] B. Verkhovsky, “Selection of Entanglements in Informa tion Assurance Protocols and Optimal Retrieval of Origi nal Blocks,” Journal of Telecommunications Manage ment, Vol. 2, No. 2, 2009, pp. 186194. [23] B. Verkhovsky, “Accelerated Cybersecure Communica tion Based on Reduced Encryption/Decryption and In formation Assurance Protocols,” Journal of Telecommu nications Management, Vol. 2, No. 3, 2009, pp. 284293.
