Int. J. Communications, Network and System Sciences, 2010, 3, 579-584
doi:10.4236/ijcns.2010.37077 Published Online July 2010 (http://www.SciRP.org/journal/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
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 (entanglement-encryption-
decryption-disentanglement). 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: Crypto-Immunity, Cybersecurity, Digital Authentication, Array Entanglements, Multi-Layer
Cryptographic Protection, Hybrid Cryptocol
1. Introduction and Basic Definitions
In this paper a hybrid digital signature cyber-secure 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 (entanglement-encryption-decry-
ption-disentanglement). Since there is no one-to-one
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 non-singular matrix E with rr
||0E 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 trade-off between crypto-immunity 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 non-linear 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 580
2
2
is a private key of the k-th 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 non-deterministic 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 Diffie-Hellman 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
B
n;
G2. Bob computes :modBAB
x
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
:modB;
B
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
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 i-th 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)
elliptic-curve cryptography [7-10] 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
:
A
d
kk
f
a with her private key, then encrypts
it with Bob’s public key
mod A n
:modB
e
kk B
cf n; (16)
and transmits the ciphertext to Bob over an open
communication channel. Bob decrypts
k
c
:mod
B
d
B
x
cn
and then verifies the signature:
:mod
A
e
A;
y
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 pair-wise 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. Non-Linear Transformations
In the more general case, the entanglements can be
non-linear, 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 non-singular 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 non-linear 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)

B. S. VERKHOVSKY 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
2ii 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. Trade-off Analysis
Every block in (16)-(17) requires four exponentiations
for encryption and decryption. In contrast, in the protocol
A.2-L.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 speed-up of A.2-L.2 is. If r =
100, then A.2-L.2 is four hundred times faster than the
RSA algorithm.
Furtermore, if
B
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 non-linear trans-
formations) is a tool that is proposed to accelerate the
encryption-decryption 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 trade-off 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 [7-9] 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
,,..,
N
hh h
1
h
using (18) and encrypt only one of them, say,
. For instance, if the sender transmits information re-
garding highly-sensitive issues of long-term national
policy or the details of a major corporate policy, the in-
truder will invest all available resources to break the en-
crypted entanglement [12-18]. 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
public-key cryptographic protocols is that they are noto-
riously slow and therefore cannot be used in the real-time
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. Elliptic-curve cryptography
and its hyper-elliptic 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 A4-H4 describe a system design stage and the
steps I4-L4 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


, (13-15);
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 {,,}
A
AA
pqn
{, ,}
is a triad of Alice’s private keys
and
B
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 ugmodp1601
1p 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) :modb
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
A
B
w of their secret key
A
B
w:1
A
B
w = 1281 [11];
G4. {Alice requests Bob to send his private key
B
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
d1009
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
x
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
k-th 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 by-product 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-
bic-root 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 non-linear 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. 90-93.
[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. 263-269.
[3] W. Diffie and M. E. Hellman, “New Directions in Cryp-
tography,” IEEE Transactions on Information Theory, Vol.
IT-22, No. 6, 1976, pp. 644-654.
[4] R. Rivest, A. Shamir and L. Adleman, “A Method of
Obtaining Digital Signature and Public-Key Cryptosys-
tems,” Communication of ACM, Vol. 21, No. 2, 1978, pp.
120-126.
[5] B. Verkhovsky, “Deterministic Algorithm for Generators
of Strong Primes,” CS-06 Research Report, NJIT, 2006.

B. S. VERKHOVSKY 584
[6] M. O. Rabin, “Digitized Signatures and Public Key Func-
tions as Intractable as Factorization,” MIT/LCS Technical
Report, TR-212, Cambridge, 1979.
[7] V. S. Miller, “Use of Elliptic Curves in Cryptography,”
Lecture Notes in Computer Science, Vol. 218, No. 85,
1985, pp. 417-426.
[8] N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics
of Computation, Vol. 48, No. 177, 1987, pp. 203-209.
[9] N. Koblitz, A. Menezes and S. Vanstone, “The State of
Elliptic Curve Cryptography,” Designs, Codes and Cryp-
tography, Vol. 19, No. 2-3, 2000, pp. 173-193.
[10] N. Koblitz, “Hyperelliptic Cryptosystems,” Journal of
Cryptology, Vol. 1, No. 3, 1989, pp. 139-150.
[11] B. Verkhovsky, “Overpass-Crossing Scheme for Digital
Signature,” International Conference on Systems Re-
search, Informatics and Cybernetics, Baden-Baden, Ger-
many, July 29-31, 2001.
[12] J. M. Pollard, “Monte Carlo Methods for Index Computa-
tion Mod P,” Mathematics of Computation, Vol. 32, No.
143, 1978, pp. 918-924.
[13] V. I. Nechaev, “Complexity of a Deterministic Algorithm
for the Discrete Logarithm,” Mathematical Notes, Vol. 55,
No. 2, 1994, pp. 165-172.
[14] A. M. Odlyzko, “Discrete Logarithms: The Past and the
Future,” Designs, Codes and Cryptography, Vol. 19, No.
2-3, 2000, pp. 129-145.
[15] J. M. Pollard, “Kangaroos, Monopoly and Discrete Loga-
rithms,” Journal of Cryptology, Vol. 13, No. 4, 2000, pp.
437-447.
[16] D. R. Stinson, “Some Baby-Step Giant-Step Algorithms
for the Low Hamming Weight Discrete Logarithm Prob-
lem,” Mathematics of Computation, Vol. 71, No. 237,
2002, pp. 379-391.
[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. 36-50.
[18] J. Coron, D. Lefranc and G. Poupard, “A New Baby-Step
Giant-Step Algorithm and Some Applications to Crypt-
analysis,” Lecture Notes in Computer Science, Vol. 3659,
2005, pp. 47-60.
[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, Socio-Economic Systems and Processes, Ulyanovsk,
Russia, 2009, pp. 13-16.
[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 (ITNG-08), Las Vegas,
USA, 2008, pp. 910-916.
[21] B. Verkhovsky, “Control Protocols Providing Informa-
tion Assurance in Telecommunication Networks,” Jour-
nal of Telecommunications Management, Vol. 2, No. 1,
2009, pp. 59-68.
[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. 186-194.
[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. 284-293.