# Fast Parallel Molecular Algorithms for  DNA-Based Computation: Solving the Elliptic Curve  Discrete Logarithm Problem overGF(2n)

Authors: Kenli Li; Shuting Zou; Jin  Xv
Journal: Journal of Biomedicine and Biotechnology
 (2008)

---

## Abstract

Elliptic curve cryptographic algorithms convert input
data to unrecognizable encryption and the unrecognizable data back
again into its original decrypted form. The security of this form of
encryption hinges on the enormous difficulty that is required to
solve the elliptic curve discrete logarithm problem (ECDLP),
especially overGF(2n),  n∈Z+. This paper
describes an effective method to find solutions to the ECDLP by
means of a molecular computer. We propose that this research
accomplishment would represent a breakthrough for applied biological
computation and this paper demonstrates that in principle this is
possible. Three DNA-based algorithms: a parallel adder, a parallel
multiplier, and a parallel inverse over GF(2n) are described.
The biological operation time of all of these algorithms is
polynomial with respect to n. Considering this analysis,
cryptography using a public key might be less secure. In this
respect, a principal contribution of this paper is to provide
enhanced evidence of the potential of molecular computing to tackle
such ambitious computations.


---

## Body

## 1. Introduction

This paper proposes theoretical work that introduces
powerful algorithms of molecular computation that could potentially compromise
the security that is afforded by certain cryptography algorithms. Molecular
computation [1] involves
biochemistry and DNA rather than silicon chips to tackle formidable
computations. Theoretical aspects of this interdisciplinary field are important
to develop the potential and interest in this form of computation [2].Elliptic curve cryptography (ECC) is a mathematical
approach to public key cryptography using elliptic curves that are typically
defined over finite fields [3]. Elliptic curves [4, 5] constitute a major area of current research that is
particularly important to number theory, for example, elliptic curves had a
role in the recent proof of Fermats last theorem.
As applied to cryptography, not only has ECC become applied in
Diffie-Hellman key exchange but also in the digital signature algorithm (DSA),
a US federal government standard for digital signatures. It is known as the
elliptic curve DSA (ECDSA) or that variant of the DSA operating on elliptic
curve groups.The security of these cryptosystems relies on the
difficulty of solving the elliptic curve discrete logarithm problem [6, 7]. If P is a point with
order m on an elliptic
curve, and Q is some other
point on the same curve, then the elliptic curve discrete logarithm problem is
to determine an l such that Q=lP, where l is an integer
and 0≤l≤m−1. If this problem can be solved efficiently, then
elliptic curve-based cryptosystems can be broken efficiently.In order to tackle such a problem, Feynman proposed
molecular computation in 1961 [8]. However, his idea was not implemented experimentally
for some decades. In 1994, Adleman succeeded in solving an instance of the
Hamiltonian path problem in a test tube, simply by the manipulation of DNA
strands [1]. Following
this, Lipton demonstrated that the Adleman techniques offered a solution to the
satisfiability problem (the first considered NP-complete problem) [9].Recent advances in molecular
biology [10, 11] have made it possible to
produce roughly 1018 DNA strands in
a test tube. Those 1018 DNA strands can
be made to represent 1018 bits of
information. In a distant future, if biological operations may be run error
free using a test tube with 1018 DNA strands,
then it would be possible to process 1018 bits of
information simultaneously. More details about test tube distributed systems
are given in [2]. The
objective for biological computing technology is to provide this enormous
amount of parallelism for dealing with computationally intensive real world
problems [12–14].Advancement in DNA computing has already been made in
many areas. In the field of cryptology, Boneh et al. have cracked DES using identical principles to those of
Adleman's solution of the travelling salesman problem. Also, Chang et al. have developed a way to factor integers. They proposed three DNA-based
algorithms: parallel subtractor; parallel comparator; and parallel modular
arithmetic unit [15, 16].In this paper, we take a step further with respect to
Chang's work [16] in
order to solve the elliptic curve discrete logarithm problem. We develop
DNA-based algorithms for a parallel adder; a parallel multiplier; a parallel
divider over GF(2n) (i.e., a
Galois field of characteristic 2); and a
parallel adder for adding points on elliptic curves. We accomplish all of these
by means of basic biological operations. We also showed that cryptosystems
based on elliptic curves can be broken. Our work presents clear evidence of
molecular computing abilities to accomplish complex mathematical operations.The paper is organized as follows. Section2 gives a
brief background on DNA computing. Section 3 introduces the DNA computing that
solves the elliptic curve discrete logarithm problem, for solution spaces of
DNA strands. Conclusions are drawn in the final section.


## 2. Background

DNA (DeoxyriboNucleic Acid) is the molecule that plays the main role in DNA-based computing. DNA is a polymer, which is
strung together from monomers called deoxyriboNucleotides. Distinct
nucleotides are detected only with their bases, which come in two sorts: purines and pyrimidines. Purines include adenine and guanine,
abbreviated A and G. Pyrimidines contain cytosine and thymine,
abbreviated C and T. A DNA strand is essentially a sequence
(polymer) of four types of nucleotides detected by one of four bases they
contain. Two strands of DNA can form (under appropriate conditions) a double
strand, if the respective bases are the Watson-Crick complements of each other—A matches T and C matches G. Hybridization is a
special technology term for the pairing of two single DNA strands to make a
double helix and also takes advantages of the specificity of DNA base pairing
for the detection of specific DNA strands (for more discussions of the relevant
biological background, refer to [10, 11]).In the past decade, there have been revolutionary
advances in the field of biomedical engineering, particularly in recombinant
DNA and RNA manipulating. Due to the industrialization of the biotechnology
field, laboratory techniques for recombinant DNA and RNA manipulation are
becoming highly standardized. Basic principles about recombinant DNA can be
found in [17–20]. In the following, we describe five biological
operations that are useful for solving the elliptic curve discrete logarithm
problem.A (test) tube is a set of molecules of DNA (a multiset
of finite strings over the alphabet{A,C,G,T}).
Given a tube, one can perform the following operations.(1)
Extract.
Given a tube P and a short
single strand of DNA, S, the operation produces two tubes +(P,S) and −(P,S), where +(P,S) is all of the
molecules of DNA in P which contain S as a substrand
and −(P,S) is all of the molecules
of DNA in P which do not
contain S.(2)
Merge.
Given tubes P1 and P2, yield ∪(P1,P2), where ∪(P1,P2)=P1∪P2. This operation is to pour two tubes into one,
without any change in the individual strands.(3)
Amplify.
Given a tube P, the operation Amplify (P,P1,P2), will produce
two new tubes P1 and P2 so that P1 and P2 are totally a
copy of P (P1 and P2 are now
identical) and P becomes an
empty tube.(4)
Append.
Given a tube P containing a
short strand of DNA Z, the operation will append Z onto the end of
every strand in P.(5)
Append-head.
Given a tube P containing a
short strand of DNA, Z, the operation will append Z onto the head
of every strand in P.


## 3. Finding the Discrete Logarithm on Elliptic Curve overGF(2n)

### 3.1. Elliptic Curve Public Key Cryptosystem overGF(2n)

An elliptic curve is defined to be the set of
solutions(x,y)∈GF(2n)×GF(2n) to the
equation(1)y2+xy=x3+ax2+b,where a,b∈GF(2n) and b≠0, together with the point on the curve at infinity O, (with homogeneous coordinates (0,0)).The points on an elliptic curve form an Abelian group
under a well-defined group operation. The identity of the group operation is
the pointO. For P=(x1,y1) a point on the
curve, we define −P to be (x1,y1+x1), so P+(−P)=(−P)+P=O. Now suppose P and Q are not O, and P≠−Q. Let P be as above and Q=(x2,y2), then P+Q=(x3,y3), where(2)x3=μ2+μ+x1+x2+a,y3=μ(x1+x3)+x3+y1,μ={y2+y1x2+x1ifP≠Q,x12+yx1ifP=Q,
(refer to [21]).In this paper, for convenience, usebn−1bn−2⋯b1b0 to denote the
value of bn−1ωn−1+bn−2ωn−2+⋯+b1ω+b0 over GF(2n).LetE be an elliptic
curve defined over GF(2n), and let G∈E be a fixed and
publicly known point. The receiver B chooses a randomly and
publishes the key aG, while keeping a itself secret.
To transmit a message m to B, user A chooses a
random integer k and sends the
pair of points (kG,Pm+k(aG)). To read the message, B multiplies the
first point in the pair by his secret a, and then subtracts the result from the second point
in the pair. So, if a breaker can compute a from public key G and aG, he can decrypt any encryption sent to B (refer to
[3]).


### 3.2. The Construction of a Parallel Adder overGF(2n)

OverGF(2n), the additive operation on two numbers is just doing XOR on each bit, respectively, without any carry. For instance, (1101)+(1001)=(0100). For every bit xj, two distinct 15 base value sequences are designed.
One represents the value zero for xj and the other
represents the value one for xj. For convenience, we assume that xj1 denotes the
value of xj to be one and xj0 denotes the
value of xj to be zero. The
following algorithm is used for parallel adding two n bits binary
number in a strand with one starts from the pth bit and the
other one starts from the qth bit and
appending the result from rth bit (see Algorithm 1).Algorithm 1:Procedure ParallelAdder (T0,n,p,q,r).
(1) Forj=0 to n−1(1a)T1=+(T0,xp+j1) and T2=−(T0,xp+j1)(1b)T3=+(T1,xq+j1) and T4=−(T1,xq+j1)(1c)T5=+(T2,xq+j1) and T6=−(T2,xq+j1)(1d)T7=∪(T4,T5) and T8=∪(T3,T6)(1e) Append(T7,xr+j1) and Append (T8,xr+j0)(1f)T0=∪(T7,T8)EndForEndProcedureConsider thatn=3, p=1, q=4, and r=7. That is, two binary numbers to be added in parallel
are both 3 bits, while one from the 1st bit and the other one from the 4th bit
in a strand, and “append” operation starts from the 7th bit. We then
suppose, tube T0={110001,010101,001111,100011} which is
regarded as an input tube for the algorithm ParallelAdder (T0,n,p,q,r). Because the value of n is 3, step (1a)
to step (1f) will be run 3 times. After the first execution of step (1a) is
finished, T1={110001,100011} and T2={010101,001111}. Next, after the first execution of step (1b) and
step (1c) is performed, T3=Φ, T4={110001,100011}, T5={010101,001111}, and T6=Φ, while T0=T1=T2=Φ. After first execution of step (1d) is run, tube T7={110001,010101,001111,100011} and T8=Φ. After first execution of step (1e) and step (1f) is
run, T0={1100011,0101011,0011111,1000111}. Then, after the rest operations are performed, the
result of tube T0 is shown in
Table 1.Table 1
Result of tubeT0.
TubeThe result is generated by ParallelAdderT0110001111, 010101111, 001111110, 100011111Lemma 1.
The
algorithm ParallelAdder(T0,n,p,q,r) is applied to
finish the function of a parallel adder.Proof.
The
algorithm ParallelAdder(T0,n,p,q,r) is implemented
by means of the extract, merge, and append operations. Each execution of step
(1a) is used to produce two tubes T1 and T2, where all of the molecules of DNA in T1 contain xp+j1 and all of the
molecules of DNA in T2 contain xp+j0. Each execution of step (1b) and step (1c) is used to
produce four tubes T3, T4, T5, T6, where all DNA strands in T3 contain xp+j1 and xq+j1, all DNA strands in T4 contain xp+j1 and xq+j0, all DNA strands in T5 contain xp+j0 and xq+j1, and all DNA strands in T6 contain xp+j0 and xq+j0. According to the additive theorem over GF(2n), the jth bit of the
sum in T4 and T5 is 1 and the jth bit of the
sum in T3 and T6 is 0.
From ParallelAdder(T0,n,p,q,r), it takes 3n extract
operations, 3n merge
operations, 2n append
operations, and 9 test tubes to finish parallel addition. A value sequence for
every bit contains 15 bases. Therefore, the algorithm will add 15n bases to all
DNA strands in tube T0.


### 3.3. The Construction of a Parallel Multiplier overGF(2n)

OverGF(2n), the multiplicative operation runs as follows:(3)(bn−1ωn−1+⋯+b1ω+b0)(bn−1'ωn−1+⋯+b1'ω+b0')=bn−1ωn−1(bn−1'ωn−1+⋯+b1'ω+b0')+⋯+b0(bn−1'ωn−1+⋯+b1'ω+b0')=h2n−2ω2n−2+h2n−3ω2n−3+⋯+h2ω2+h1ω+h0,h2n−2=bn−1bn−1',h2n−3=bn−1bn−2'+bn−2bn−1',…,hn−1⁢=bn−1b0'+bn−2b1'+⋯+b0bn−1',…,h1=b1b0'+b0b1',h0=b0b0'.The algorithm ParallelMultiplier(T0,n,p,q) is used to
multiply two nbit binary
numbers on every strand in parallel with one starts from the pth bit and the
other one starts from the qth bit. It runs
as follows: at first, employ extract operation to form two tubes: T1 and T2. The first tube T1 includes all of
the strands on which xp=1 and the second
tube T2 includes all of
the strands on which xp=0. Then, we copy the bits from qth to
(q+n−1) th
to the end of every strand in tube T1 and append n bits 0 to the
end of every strand in tube T2. After these operations, the (q+n)th bit to (q+n+n−1)th bit show the
coefficients of ω2n−2 to ωn−1. Using the same principle, we get the coefficients of ω2n−3 to ωn−2, ω2n−4 to ωn−3,…,ωn−1 to ω0. At last, call algorithm ParallelAdder (T0,n,p,q,r) to compute the
sum of coefficients of ω2n−2, the sum of coefficient of ω2n−3,…, and so on. As a result, the length of every
strand will increase n×n+2n−1 bits.From ParallelMultiplier(T0,n,p,q), it takes O(n2) extract
operations, O(n2) merge
operations, O(n2) append
operations, and O(1) test tubes to
finish the function of a parallel multiplier.


### 3.4. The Construction of a Parallel Shifter for Multiplicative Result

Because overGF(2n), the exponent of ω cannot be
beyond n−1, the result of parallel multiplying should be shifted
by a certain irreducible polynomial, called primitive polynomial:
ωn+bn−1ωn−1+⋯+b1ω+b0=0⇔ωn=bn−1ωn−1+⋯+b1ω+b0. The algorithm
ParallelShifter (T0,n,p), p representing
that the multiplicative result starts from the pth bit, is used
to parallel shift the multiplicative result b2n−2ω2n−2+b2n−3ω2n−3+⋯+b1ω+b0 to legal form bn−1ωn−1+bn−2ωn−2+⋯+b1ω+b0 over GF(2n) which can be
designed as follows: appends the primitive polynomial's coefficients from ωn−1 to ω0 to the end of
every strand at first. Employ the extract operation to form two test tubes T1 and T2. Tube T1 includes all of
the strands on which xp=1 and tube T2 includes all of
the strands on which xp=0. Then, we add the coefficients, from item ω2n−3 to item ωn−2, to the coefficients of irreducible polynomial in
parallel in tube T1. This forms the new coefficients from ω2n−3 to ωn−2 and has deleted
the ω2n−2 item. The
coefficients from ωn−3 to ω0 are without any
change. For the T2 includes all of
the strands that have xp=0, so just copy the coefficients from ω2n−3 to ω0 without any
change. After all the executions before are run, the highest exponent of ω is reduced to 2n−3. Then, merge T1 and T2 and begin new
reduction. The principle of rest reducing turn is all like this above. When
this algorithm is run out, the highest exponent of ω is reduced to n−1. This algorithm will totally append n×n+(n−1)(n−2)/2 bits more to
every strand.From ParallelShifter(T0,n,p), it takes O(n2) extract
operations, O(n2) merge operations, O(n2) append
operations, and O(1) test tubes to
finish the function of a parallel shifter.


### 3.5. The Mathematical Principle of Division onGF(2n)

OverGF(2n), to do a division operation for a dividend and a
divisor, one should get the divisor's inverse first and then multiply the
dividend. For the primitive polynomial ωn+bn−1ωn−1+⋯+b1ω+b0 is irreducible,
there exists a polynomial g(ω) and a
polynomial f(ω) that fit the
equation (according to Euclid algorithm):(4)g(ω)×divisor+f(ω)×(ωn+bn−1ωn−1+⋯+b1ω+b0)=1.Becauseωn+bn−1ωn−1+⋯+b1ω+b0=0, g(ω)×divisor=1, which is to say g(ω) is the inverse
of the divisor. To find g(ω) and f(ω), one can do as follows, which is called Euclid
algorithm, also called division algorithm; first, ωn+bn−1ωn−1+⋯+b1ω+b0 is divided by
the divisor. If the value of the remainder is 1, that is to say, (ωn+bn−1ωn−1+⋯+b1ω+b0)+g(ω)×divisor=1 with g(ω) is the division
result and the inverse of divisor has found which is g(ω); else let remainder be r(ω), let the divisor be the dividend and r(ω) be the divisor
and do division operation again. Repeat the process until the remainder is 1.
Because the highest exponent of ω of remainder
reduces by 1 in each repeat, it is at most repeating n−1 times. So in
the first time division, the dividend is n+1 bits and the
divisor is n bits and the
remainder is at most n−1 bits, and in
the second time division the dividend is n bits and the
divisor is n−1 bits and the
remainder is at most n−2 bits,…, and
in last time division the dividend is 3 bits and the divisor is 2 bits and the
remainder is 1 bit. Then, trace back to get the g(ω).


### 3.6. The Construction of a Parallel Comparator

Prior to each
step of long division, comparison should be done first. Suppose the divisor isn bits at that
time. At first compare the first two bits of dividend with divisor to determine
that addition operation between first two bits of dividend and divisor should
be done or not, then compare the first three bits of result with divisor,…, compare
the first n bits of result
with divisor, the last time (finally), compare the last n bits of result
with divisor for this time the first bit of result is 0. The following
algorithm is used to compare the divisor which is from pth bit to qth bit with the
bits from jth bit to kth bit in
parallel, and forms tube T1 and T2. T2 contains all
strands on which add execution will be done and T1 contains all
strands on which add execution will not be done (see Algorithm 2).Algorithm 2:Procedure ParallelComparator (T0,p,q,j,k,T1,T2).
(1) If(q−p>k−j) then(1a) Form=1 to q−p−(k−j)(1a1)T3=+(T0,xp+m−11)(1a2)T1=∪(T1,T3)EndForEndIf(2) Form=q−(k−j)−p to q−p(2a)T3=+(T0,xp+m1)(2b)T4=−(T3,xj+m−(q−p−k+j)1)(2c)T5=−(T0,xp+m1)(2d)T6=+(T5,xj+m−(q−p−k+j)1)(2e)T1=∪(T1,T4) and T2=∪(T2,T3,T6) andT0=∪(T0,T5)EndForEndProcedureLemma 2.
The
algorithm Parallel Comparator(T0,p,q,j,k,T1,T2) is applied to
finish the function of parallel comparator.Proof.
Ifq−p>k−j, that means the bits of divisor is more than the bits
of the result which are intended to compare this time. Step (1) considers the
excessive bits of divisor and if any one bit is 1, which means the divisor is
“bigger" than the bits of the result which are intended to compare this
time and pour the strands to T1. Step (2) considers the rest of the bits of divisor
and the bits of result which are intended to compare this time. T3 contains all
strands on which certain bit of divisor is 1 and corresponding bit of the
result is 1; T4 contains all
strands on which certain bit of divisor is 1 and corresponding bit of the
result is 0; T5 contains all
strands on which certain bit of divisor is 0 and corresponding bit of the
result is 0; T6 contains all
strands on which certain bit of divisor is 0 and corresponding bit of the
result is 1. So add execution can be done over strands in T3 and T6, which can not be done over strands in T4, and strands in T5 need more
consideration.
From ParallelComparator(T0,p,q,j,k,T1,T2), it takes O(n) extract
operations, O(n) merge
operations, and O(1) test tubes to
finish the function of a parallel comparator.


### 3.7. The Construction of a Parallel Long Division

Suppose the divisor isn bits and is
from pth bit and the
dividend is n+1 bits and is
from the qth bit in each
strand. To do the long division, first compare the divisor with first two bits
of dividend using ParallelComparator to get the first bit of the result of
division and note down the result of first time addition result. Then, compare
the divisor with the first three bits of the addition result last time to get
the second bit of the result of the long division, and note down the addition
result. Finally, compare the divisor with the last n bits of
addition result last time to get the last bit of division result and the
remainder (see Algorithm 3).Algorithm 3:Procedure SimilarDiv (T0,n,p,q).
(1) Forj=1 to n−1(1a) ParallelComparator(T0,p,p+n−1,q+(j−1)(n+2),q+(j−1)(n+2)+j,T1,T2)(1b) Append(T1,xq+n+1+(j−1)(n+2)0) and Append (T2,xq+n+1+(j−1)(n+2)1)(1c) Fork=0 to n(1c1)T3=+(T1,xq+(n+2)(j−1)+k1) and T4=−(T1,xq+(n+2)(j−1)+k1)(1c2) Append(T3,xq+j(n+2)+k1) and Append (T4,xq+j(n+2)+k0)(1c3)T1=∪(T3,T4)EndFor(1d) ParallelAdder(T2,j+1,q+(j−1)(n+2),p+n−j−1,q+(n+2)j)(1e) Fork=n−j down to 1(1e1)T3=+(T2,xq+(n+2)j−k−11) and T4=−(T2,xq+(n+2)j−k−11)(1e2) Append(T3,xq+(j+1)(n+2)−k−11) and Append (T4,xq+(j+1)(n+2)−k−10)(1e3)T2=∪(T3,T4)EndFor(1f)T0=∪(T1,T2)EndFor(2) ParallelComparator(T0,p,p+n−1,q+(n+2)(n−1)+1,q+(n+2)(n−1)+n,T1,T2)(3) Append(T1,xq+(n+2)n−10) and Append (T2,xq+(n+2)n−11)(4) Fork=0 to n(4a)T3=+(T1,xq+(n+2)(n−1)+k1) and T4=−(T1,xq+(n+2)(n−1)+k1)(4b) Append(T3,xq+(n+2)n+k1) and Append (T4,xq+(n+2)n+k0)(4c)T1=∪(T3,T4)EndFor(5) Append(T2,xq+(n+2)n0)(6) ParallelAdder(T2,n,q+(n+2)(n−1)+1,p,q+(n+2)n+1)(7)T0=∪(T1,T2)EndProcedureLemma 3.
The
algorithm SimilarDiv(T0,n,p,q) is applied to
finish the function of parallel long division.Proof.
Each
execution of step (1) is to get each bit of the long division result. The rest
part is to get the last bit of the long division result. Consider the first
cycle of step (1), step (1a) compares the divisor with the first two bits of
the dividend, and form two tubesT1 and T2 that T2 contains all strands
on which add execution can be done, contrarily the T1. Step (1b) appends 0 to all strands in T1 and appends 1
to all strands in T2. This bit is the first bit of the division result.
Step (1c) just finishes to append the dividend in tube T1. Step (1d) adds the divisor and the first two bits of
the dividend in T2. Step (1e) copies the rest of the bits of the dividend
in T2. Step (1f) pours T1 and T2 together and
finishes the first execution of step (1) to get the first bit of the division
result and the first time addition result. The second execution of step (1) is
to compare the divisor with the first three bits of the addition result last
time and get the second bit of the division result. The principle of other
cycles and the rest of the steps are similar to the principle above. The length
of each strand will reach to q+n+(n+2)n bits when this
algorithm is run out.
From SimilarDiv(T0,n,p,q), it takes O(n2) extract
operations, O(n2) append
operations, O(n2) merge operations,
and O(1) test tubes to
finish the function of a parallel long division.


### 3.8. The Construction of Parallel Traceback

Suppose the irreducible polynomialA(ω)=ωn+bn−1ωn−1+⋯+b1ω+b0 and suppose g(ω) and f(ω) satisfy that g(ω)×divisor+f(ω)A(ω)=1, for the purpose of finding the divisor's inverse, g(ω), we need to do sometimes long division introduced in
Section 3.7; let A(ω) be the dividend
and divisor mentioned above be the divisor in first time and suppose the result
is g1(ω), and if the remainder is 1, then the division result g1(ω) is g(ω). Else, let the divisor last time be the dividend and
let the remainder last time be the divisor and do the long division. Suppose
the result is p(ω) and g2(ω)=p(ω)×g1(ω)+1, if the remainder is 1, the g2(ω) is g(ω). Else, let the divisor last time be the dividend and
let the remainder last time be the divisor and do the long division. Suppose
the result is p(ω) and g3(ω)=p(ω)×g2(ω)+g1(ω), if the remainder is 1, the g3(ω) is g(ω). Generally speaking, we need to trace back after
long division each time: first time, the tracing result is the division's
result; the second time, the tracing's result is the sum of 1 and the product
of the division's result and the tracing's result last time; from the third
time, the tracing's result is the sum of the tracing's result last second time
and the product of the division's result and the tracing's result last time.
The following algorithm is used to do tracing operation from the third time in
which t, d, and p mean that the
tracing's result last second time is from the tth bit and the
last tracing's result is from the dth bit and the
division result is from the pth bit (see Algorithm 4).Algorithm 4:Procedure Traceback (T0,t,d,p,n).
(1) ParallelMultiplier(T0,n,d,p)(2) ParallelShifter(T0,n,p+n+n2)(3) ParallelAdder(T0,n,t,p+M,p+n+M)EndProcedureLemma 4.
The
algorithm TraceBack(T0,t,d,p,n) is used to
trace back after long division from the third time in order to get the
divisor's inverse.Proof.
In
this and following procedures,M=n2+2n−1+n2+(n−1)(n−2)/2, which represent the total number of increased bits
when ParallelMultiplier (T0,n,p,q) and
ParallelShifter (T0,n,p) are called.
Step (1) is used to multiply the last tracing's result from dth bit to the
long division result from pth bit in
parallel. The result will be from the (p+n+n×n)th bit to (p+n+n×n+2n−1)th bit. Step
(2) is to shift the result of multiplication to legal form which will append ((n−1)(n−2)/2+n2) bits to every
strand. And its result is from (p+M)th bit to (p+n+M−1)th bit. Step
(3) is used to add the result to the last second time's tracing's result in
parallel.
From TraceBack(T0,t,d,p,n), it takes O(n2) extract
operations, O(n2) append
operations, O(n2) merge
operations, and O(1) test tubes to
finish the function of tracing back.


### 3.9. The Construction of a Parallel inverse

From the algorithms introduced above, we can find
divisors' inverses in parallel as follows: first pick out the strands on which
divisor equals to 1. Then, let the primitive polynomial be the dividend and the
divisor be the divisor and do long division. Trace back to get the tracing's
result first time and pick up the strands on which the remainder equals to 1
and store them in tubeT1. Then, let the divisor last time be the dividend and
the remainder last time be the divisor and do long division. Collect the
quotient and trace back. Pick up the strands on which the remainder equals to 1
and store them in tube T2,…, these executions, including long division,
collecting every bit of the quotient and tracing back, are run n−1 times at most.
In the following algorithm, the parameters n and p mean that the
divisor is n bits and it
starts from pth bit in every
strand. The last parameter r is used to
represent that each strand in tube is r−1 bit long and we
begin append operation from rth bit of every
strand.Among the algorithm, the
procedure Picking(T0,n,p,Ts) is used to pick
out the strands on which the pth bit to the (p+n−2)th bit are all
0 and the (p+n−1)th bit is 1
and store them in Ts. It is easy to program, so just omitted here (see Algorithm 5).Algorithm 5:Procedure ParallelInverse (T0,n,p,r).
(1) Picking(T0,n,p,Tz)(2) AppendA(x) to the end of
all strands in T0(3) SimilarDiv(T0,n,p,r)(4) Forj=0 to n−1(4a)Tm=+(T0,xr+n+1+(n+2)j1) and Ts=−(T0,xr+n+1+(n+2)j1)(4b) Append(Tm,xr+n+1+(n+2)n+j1) and Append (Ts,xr+n+1+(n+2)n+j0)(4c)T0=∪(Tm,Ts)EndFor(5) Picking(T0,n−1,r+n+1+(n+2)(n−1)+3,T1)(6) Forj=0 to n−1(6a)Tm=+(T0,xp+j1) and Ts=−(T0,xp+j1)(6b) Append(Tm,xr+s1+j1) and Append (Ts,xr+s1+j0)(6c)T0=∪(Tm,Ts)EndFor(7) SimilarDiv(T0,n−1,r+n+1+(n+2)(n−1)+3,r+s1)(8) Append(T0,xr+s1+n+(n+1)(n−1)0)(9) Forj=0 to n−2(9a)Tm=+(T0,xr+s1+n+(n+1)j1) and Ts=−(T0,xr+s1+n+(n+1)j1)(9b) Append(Tm,xr+s1+n+(n+1)(n−1)+1+j1) and Append (Ts,xr+s1+n+(n+1)(n−1)+1+j0)(9c)T0=∪(Tm,Ts)EndFor(10) ParallelMultiplier(T0,n,r+n+1+(n+2)n,r+s1+n+(n+1)(n−1))(11) ParallelShifter(T0,n,r+s1+n+(n+1)(n−1)+n+n2)(12) Add 1 to the product above which will result inn bits more to
each strand(13) Picking(T0,n−2,r+s1+n+(n+1)(n−2)+3,T2)(14) Forj=2 to n−2(14a) Copy dividend (divisor last time) to the end(14b) SimilarDiv(T0,n−j,r+s1+⋯+sj−1+n+2−j+(n+3−j)(n−j)+3,r+s1+⋯+sj)(14c) Appendj bits 0 to the
end(14d) Collectn−j bits quotient
of this division to the end(14e) Traceback(T0,r+s1+⋯+sj−1−n,r+s1+⋯+sj−n,r+s1+⋯+sj+(n+1−j)+(n+2−j)(n−j),n)(14f) Picking(T0,n−1−j,r+s1+⋯+sj+n+1−j+(n+2−j)(n−1−j)+3,Tj+1)EndFor(15) Forj=1 to n−1(15a) Fork=0 to sj+1+⋯+sn−1−1(15a1) Append(Tj,xr+s1+⋯+sj+k0)EndFor(15b) Fork=0 to n−1(15b1)Tm=+(Tj,xr+s1+⋯+sj−n+k1) and Ts=−(Tj,xr+s1+⋯+sj−n+k1)(15b2) Append(Tm,xr+s1+⋯+sn−1+k1) and Append (Ts,xr+s1+⋯+sn−1+k0)(15b3)Tj=∪(Tm,Ts)EndForEndFor(16) Forj=0 to s1+⋯+sn−1+n−2Append(Tz,xr+j0)EndFor(17) Append(Tz,xr+s1+⋯+sn−1+n−11)(18)T0=∪(Tz,T1,T2,…,Tn−1)EndProcedureLemma 5.
The
algorithm ParallelInverse(T0,n,p,r) is applied to
find inverses over GF(2n) in parallel.Proof.
Step
(2) is used to appendn+1 bits
irreducible polynomial, which is the dividend in first long division, to every
strand. The execution of step (3) calls the algorithm SimilarDiv (T0,n,p,r) to finish long
division. Now the length of strands is added up to r+n+(n+2)n bits. Step (4)
finishes the function of collecting every bit of quotient and will add n bits to every
strand. This is the first time tracing result. Step (5) calls the procedure
Picking (T0,n,p,Ts) to pick out the
strands on which the remainder is 1 and store them in tube T1. Step (6) finishes the operation of appending the
dividend, which is divisor last time, to the strands. Note that s1=n+1+(n+2)n+n. Step (7) calls the algorithm SimilarDiv (T0,n,p,q) to accomplish
the second time long division. Step (8) employs the append operation to append
a bit 0 in order to make the quotient to be n bits. Step (9)
finishes the function of collecting every bit of quotient and will add n−1 bits to every
strand. Steps (10) and (11) call the algorithm ParallelMultiplier (T0,n,p,q) and
ParallelShifter (T0,n,p). Step (12) is used to add 1 to the product. These
three steps accomplish the function of tracing back of the second time. Now the
length of every strand is r+s1+n+(n+1)(n−1)+n+M+n−1. Step (13) calls the algorithm Picking (T0,n,p,Ts) to pick out the
strands on which the remainder is 1 and store them in tube T2. One execution of step (14) finishes the function of
long division and tracing back and picking out the strands on which the
remainder is 1. The step will be looped n−3 times, because
the long division should be done n−1 times to make
sure that the remainder of each strand equals to 1 and long division has been
done twice before. Note that while j≥2, sj=n+2−j+(n+3−j)(n+1−j)+n+M+n. Step (15a) is used to append certain bits 0 to each
tube Tj to make sure
that strands in T1 to Tn−1 are all r+s1+⋯+sn−1−1 bits long. Step
(15b) is used to append the inverse gotten before to the last of every strand
in T1 to Tn−1. Step (18) pours strands in all tubes together to one
tube T0. From all above, getting inverse one time needs
increasing s1+s2+⋯+sn−1+n bits to every
strand.
From ParallelInverse(T0,n,p,r), it takes O(n3) extract
operations, O(n3) append
operations, O(n3) merge
operations, and O(n) test tubes to
finish the function of finding inverse in parallel.


### 3.10. The Construction of a Parallel Divider

To do a division operation onGF(2n), first one should calculate divisor's inverse using
above mentioned algorithm then multiply the dividend. The following algorithm
is used to finish the function of parallel division over GF(2n), where the
dividend begins with the qth bit and the
divisor begins with the pth bit, and
current bit is the rth bit (see Algorithm 6).Algorithm 6:Procedure ParallelDivision (T0,n,p,q,r).
(1) ParallelInverse(T0,n,p,r)(2) ParallelMultiplier(T0,n,q,r+s1+⋯+sn−1)(3) ParallelShifter(T0,n,r+s1+⋯+sn−1+n+n×n)EndProcedureLemma 6.
The
algorithm ParallelDivision(T0,n,p,q,r) is used to
finish the function of parallel division over GF(2n).Proof.
Step
(1) calls the algorithm ParallelInverse(T0,n,p,r) to get the
divisor's inverse of every strand. The length of every strand is r+s1+⋯+sn−1+n−1 bits now with
the inverse from (r+s1+⋯+sn−1)th bit to (r+s1+⋯+sn−1+n−1)th bit. Step
(2) calls ParallelMultiplier (T0,n,p,q) to finish the
function of the inverse being multiplied by the dividend every strand with the
dividend starting from the qth bit. Now the
length of each strand adds up to r+s1+⋯+sn−1+n+n×n+2n−1−1 bits. Step (3)
shifts the product by calling ParallelShifter (T0,n,p) and will add (n−1)(n−2)/2+n×n bits to every
strand. Generally speaking, doing parallel division one time need increasing the
strands D=s1+⋯+sn−1+n+M bits.
From ParallelDivision(T0,n,p,q,r), it takes O(n3) extract
operations, O(n3) append
operations, O(n3) merge
operations, and O(n) test tubes to
finish the function of parallel division.


### 3.11. The Construction of a Parallel Adder of Two Points on Elliptic Curve

By far the addition, subtraction (the same to
addition), multiplication, and division operations overGF(2n) have been
solved. Now consider how to execute addition of two points on an elliptic curve y2+xy=x3+ax2+b in biological
ways. We should consider five different cases: case 1, the first point is O and the point
of sum equals to the second point; case 2, the second point is O and the point
of sum equals to the first point; case 3, one point is the inverse of the other
one, and the point of sum is O; case 4, one point equals to the other one, and
computes the sum as the formula in part 3.1; case 5, computes the sum using the
formula in part 3.1.The algorithm AddTwoNode(T0,n,x1,y1,x2,y2,r) is used to add
two points. The first one's position x starts from the (x1)th bit and position y starts from the (y1)th bit, and
the second one's position x starts from the (x2)th bit and y starts from the (y2)th bit. The
parameter r represents the
current bit. In the procedure, it calls Picking01 (T0,n,x1,y1,x2,y2,T11) to pick out the
strands on which the first point is O and store them
in T11, Picking02 (T0,n,x1,y1,x2,y2,T12) to pick out the
strands on which the second point is O and store them
in T12, PickingInverse (T0,n,x1,y1,x2,y2,r,T2) to pick out the
strands on which one point is the inverse of the other one and store them in
tube T2, and PickingEqual (T0,n,x1,y1,x2,y2,T3) to pick out the
strands on which one point equals to the other one and store them in tube T3. These four algorithms are easy to design, so omitted
here. Note that PickingInverse (T0,n,x1,y1,x2,y2,r,T2) will increase n bits to every
strand in T0 (see Algorithm 7).Algorithm 7:Procedure AddTwoNode (T0,n,x1,y1,x2,y2,r).
(1) Picking01(T0,n,x1,y1,x2,y2,T11)(2) Picking02(T0,n,x1,y1,x2,y2,T12)(3) PickingInverse(T0,n,x1,y1,x2,y2,r,T2)(4) PickingEqual(T0,n,x1,y1,x2,y2,T3)(5) Forj=0 to M−1(5a) Append(T0,xr+n+j0)EndFor(6) ParallelAdder(T0,n,y1,y2,r+n+M)(7) ParallelAdder(T0,n,x1,x2,r+n+M+n)(8) ParallelDivision(T0,n,r+n+M+n,r+n+M,r+n+M+2n)(9) Forj=0 to n−1(9a)Tm=+(T3,xx1+j1) and Ts=−(T3,xx1+j1)(9b) Append(Tm,xr+n+j1) and Append (Ts,xr+n+j0)(9c)T3=∪(Tm,Ts)EndFor(10) ParallelMultiplier(T3,n,r+n,r+n)(11) ParallelShifter(T3,n,r+n+n+n×n)(12) ParallelAdder(T3,n,y1,r+n+n+M−n,r+n+n+M)(13) ParallelDivision(T3,n,x1,r+n+n+M,r+n+n+M+n)(14)T0=∪(T0,T3)SUPPOSEU=n+M+n+D(15) ParallelMultiplier(T0,n,r+n+U−n,r+n+U−n)(16) ParallelShifter(T0,n,r+n+U+n×n)(17) ParallelAdder(T0,n,r+n+U−n,r+n+U+M−n,r+n+U+M)(18) ParallelAdder(T0,n,r+n+U+M,x1,r+n+U+M+n)(19) ParallelAdder(T0,n,r+n+U+M+n,x2,r+n+U+M+n+n)(20) Forj=0 to n−1(20a) Append(T0,xa,r+n+U+M+3n+j)EndFor(21) ParallelAdder(T0,n,r+n+U+M+2n,r+n+U+M+3n,r+n+U+M+4n)SUPPOSEX=U+M+5n(22) ParallelAdder(T0,n,x1,r+n+X−n,r+n+X)(23) ParallelMultiplier(T0,n,r+n+U−n,r+n+X)(24) ParallelShifter(T0,n,r+n+X+n+n×n)(25) ParallelAdder(T0,n,r+n+X+n+M−n,r+n+X−n,r+n+X+n+M)(26) ParallelAdder(T0,n,r+n+X+n+M,y1,r+n+X+n+M+n)SUPPOSEY=n+M+n+n(27) Forj=0 to n−1(27a)Tm=+(T0,xr+X+j1) and Ts=−(T0,xr+X+j1)(27b) Append(Tm,xr+n+X+Y+j1) and Append (Ts,xr+n+X+Y+j0)(27c)T0=∪(Tm,Ts)EndFor(28) Forj=0 to n−1(28a)Tm=+(T0,xr+n+X+Y−n+j1) and Ts=−(T0,xr+n+X+Y−n+j1)(28b) Append(Tm,xr+n+X+Y+n+j1) and Append (Ts,xr+n+X+Y+n+j0)(28c)T0=∪(Tm,Ts)EndFor(29) Appendn+X+Y bits 0 to each
strand in T11 and T12. Then, append values of x2 and y2 of each strand
tothe end inT11, and append values of x1 and y1 of each strand
to the end in T12(30) AppendX+Y+2n bits 0 to every
strand in T2(31)T0=∪(T11,T12,T2,T0)EndProcedureLemma 7.
The
algorithm AddTwoNode(T0,n,x1,y1,x2,y2,r) can compute the
sum of two points on elliptic curve.Proof.
Step
(5) employs append operation to appendM bits 0 to all
strands in tube T0. Step (6) to step (8) are operations on tube T0 to get μ of strands in T0. Step (9) to step (13) are operations on tube T3 to get μ of strands in T3. Step (14) pours T0 and T3 to T0 and the length
of every strand in T0 now is r+n+n+M+n+D−1 bits. Step (15)
to step (21) accomplish to compute the position x of point of sum
and the result is from (r+X)th bit. The
execution of steps (22) to (26) is used to get the position y of the sum
which equals to μ(x1+x3)+x3+y1. And now, the position y of the sum is
from (r+X+Y)th bit and the
length is r+n+X+Y−1 bits.
Steps (27) and (28) are applied to append the value
of positionsx and y of the sum of
two points to the last of every strand. Now, the length of every strand in T0 is r+n+X+Y+2n−1 bits with the
value x from the (r+n+X+Y)th bit and y from the (r+n+X+Y+n)th bit.
From AddTwoNode(T0,n,x1,y1,x2,y2,r), it takes O(n3) extract
operations, O(n3) append
operations, O(n3) merge
operations, and O(n) test tubes to
finish the function of a parallel adder for points on elliptic curve.


### 3.12. Breaking the Elliptic Curve Cryptosystem

We have constructed the algorithm above for parallel
computing the point of the sum of two points. Then, we can solve elliptic curve
discrete logarithm problem as follows: consider pointP and Q are given, and l is what we want
to get which matches Q=lP. First, we amplify P into two tubes
and add P in one tube.
Check if 2P equals to Q; if not, note down the value of 2P and pour two
tubes together. Then, amplify the tube into two tubes and add 2P in one tube.
Check if any point equals to Q; if not, note down the value of 4P and pour two
tubes together, or we get the value of l. Then, amplify the tube into two tubes and add 4P in one tube,…, while this loop executes n times, the
value from 1 to 2n for l will have been
checked, and the elliptic curve cryptosystem has been broken by
the solved elliptic curve discrete logarithm
problem.


## 3.1. Elliptic Curve Public Key Cryptosystem overGF(2n)

An elliptic curve is defined to be the set of
solutions(x,y)∈GF(2n)×GF(2n) to the
equation(1)y2+xy=x3+ax2+b,where a,b∈GF(2n) and b≠0, together with the point on the curve at infinity O, (with homogeneous coordinates (0,0)).The points on an elliptic curve form an Abelian group
under a well-defined group operation. The identity of the group operation is
the pointO. For P=(x1,y1) a point on the
curve, we define −P to be (x1,y1+x1), so P+(−P)=(−P)+P=O. Now suppose P and Q are not O, and P≠−Q. Let P be as above and Q=(x2,y2), then P+Q=(x3,y3), where(2)x3=μ2+μ+x1+x2+a,y3=μ(x1+x3)+x3+y1,μ={y2+y1x2+x1ifP≠Q,x12+yx1ifP=Q,
(refer to [21]).In this paper, for convenience, usebn−1bn−2⋯b1b0 to denote the
value of bn−1ωn−1+bn−2ωn−2+⋯+b1ω+b0 over GF(2n).LetE be an elliptic
curve defined over GF(2n), and let G∈E be a fixed and
publicly known point. The receiver B chooses a randomly and
publishes the key aG, while keeping a itself secret.
To transmit a message m to B, user A chooses a
random integer k and sends the
pair of points (kG,Pm+k(aG)). To read the message, B multiplies the
first point in the pair by his secret a, and then subtracts the result from the second point
in the pair. So, if a breaker can compute a from public key G and aG, he can decrypt any encryption sent to B (refer to
[3]).


## 3.2. The Construction of a Parallel Adder overGF(2n)

OverGF(2n), the additive operation on two numbers is just doing XOR on each bit, respectively, without any carry. For instance, (1101)+(1001)=(0100). For every bit xj, two distinct 15 base value sequences are designed.
One represents the value zero for xj and the other
represents the value one for xj. For convenience, we assume that xj1 denotes the
value of xj to be one and xj0 denotes the
value of xj to be zero. The
following algorithm is used for parallel adding two n bits binary
number in a strand with one starts from the pth bit and the
other one starts from the qth bit and
appending the result from rth bit (see Algorithm 1).Algorithm 1:Procedure ParallelAdder (T0,n,p,q,r).
(1) Forj=0 to n−1(1a)T1=+(T0,xp+j1) and T2=−(T0,xp+j1)(1b)T3=+(T1,xq+j1) and T4=−(T1,xq+j1)(1c)T5=+(T2,xq+j1) and T6=−(T2,xq+j1)(1d)T7=∪(T4,T5) and T8=∪(T3,T6)(1e) Append(T7,xr+j1) and Append (T8,xr+j0)(1f)T0=∪(T7,T8)EndForEndProcedureConsider thatn=3, p=1, q=4, and r=7. That is, two binary numbers to be added in parallel
are both 3 bits, while one from the 1st bit and the other one from the 4th bit
in a strand, and “append” operation starts from the 7th bit. We then
suppose, tube T0={110001,010101,001111,100011} which is
regarded as an input tube for the algorithm ParallelAdder (T0,n,p,q,r). Because the value of n is 3, step (1a)
to step (1f) will be run 3 times. After the first execution of step (1a) is
finished, T1={110001,100011} and T2={010101,001111}. Next, after the first execution of step (1b) and
step (1c) is performed, T3=Φ, T4={110001,100011}, T5={010101,001111}, and T6=Φ, while T0=T1=T2=Φ. After first execution of step (1d) is run, tube T7={110001,010101,001111,100011} and T8=Φ. After first execution of step (1e) and step (1f) is
run, T0={1100011,0101011,0011111,1000111}. Then, after the rest operations are performed, the
result of tube T0 is shown in
Table 1.Table 1
Result of tubeT0.
TubeThe result is generated by ParallelAdderT0110001111, 010101111, 001111110, 100011111Lemma 1.
The
algorithm ParallelAdder(T0,n,p,q,r) is applied to
finish the function of a parallel adder.Proof.
The
algorithm ParallelAdder(T0,n,p,q,r) is implemented
by means of the extract, merge, and append operations. Each execution of step
(1a) is used to produce two tubes T1 and T2, where all of the molecules of DNA in T1 contain xp+j1 and all of the
molecules of DNA in T2 contain xp+j0. Each execution of step (1b) and step (1c) is used to
produce four tubes T3, T4, T5, T6, where all DNA strands in T3 contain xp+j1 and xq+j1, all DNA strands in T4 contain xp+j1 and xq+j0, all DNA strands in T5 contain xp+j0 and xq+j1, and all DNA strands in T6 contain xp+j0 and xq+j0. According to the additive theorem over GF(2n), the jth bit of the
sum in T4 and T5 is 1 and the jth bit of the
sum in T3 and T6 is 0.
From ParallelAdder(T0,n,p,q,r), it takes 3n extract
operations, 3n merge
operations, 2n append
operations, and 9 test tubes to finish parallel addition. A value sequence for
every bit contains 15 bases. Therefore, the algorithm will add 15n bases to all
DNA strands in tube T0.


## 3.3. The Construction of a Parallel Multiplier overGF(2n)

OverGF(2n), the multiplicative operation runs as follows:(3)(bn−1ωn−1+⋯+b1ω+b0)(bn−1'ωn−1+⋯+b1'ω+b0')=bn−1ωn−1(bn−1'ωn−1+⋯+b1'ω+b0')+⋯+b0(bn−1'ωn−1+⋯+b1'ω+b0')=h2n−2ω2n−2+h2n−3ω2n−3+⋯+h2ω2+h1ω+h0,h2n−2=bn−1bn−1',h2n−3=bn−1bn−2'+bn−2bn−1',…,hn−1⁢=bn−1b0'+bn−2b1'+⋯+b0bn−1',…,h1=b1b0'+b0b1',h0=b0b0'.The algorithm ParallelMultiplier(T0,n,p,q) is used to
multiply two nbit binary
numbers on every strand in parallel with one starts from the pth bit and the
other one starts from the qth bit. It runs
as follows: at first, employ extract operation to form two tubes: T1 and T2. The first tube T1 includes all of
the strands on which xp=1 and the second
tube T2 includes all of
the strands on which xp=0. Then, we copy the bits from qth to
(q+n−1) th
to the end of every strand in tube T1 and append n bits 0 to the
end of every strand in tube T2. After these operations, the (q+n)th bit to (q+n+n−1)th bit show the
coefficients of ω2n−2 to ωn−1. Using the same principle, we get the coefficients of ω2n−3 to ωn−2, ω2n−4 to ωn−3,…,ωn−1 to ω0. At last, call algorithm ParallelAdder (T0,n,p,q,r) to compute the
sum of coefficients of ω2n−2, the sum of coefficient of ω2n−3,…, and so on. As a result, the length of every
strand will increase n×n+2n−1 bits.From ParallelMultiplier(T0,n,p,q), it takes O(n2) extract
operations, O(n2) merge
operations, O(n2) append
operations, and O(1) test tubes to
finish the function of a parallel multiplier.


## 3.4. The Construction of a Parallel Shifter for Multiplicative Result

Because overGF(2n), the exponent of ω cannot be
beyond n−1, the result of parallel multiplying should be shifted
by a certain irreducible polynomial, called primitive polynomial:
ωn+bn−1ωn−1+⋯+b1ω+b0=0⇔ωn=bn−1ωn−1+⋯+b1ω+b0. The algorithm
ParallelShifter (T0,n,p), p representing
that the multiplicative result starts from the pth bit, is used
to parallel shift the multiplicative result b2n−2ω2n−2+b2n−3ω2n−3+⋯+b1ω+b0 to legal form bn−1ωn−1+bn−2ωn−2+⋯+b1ω+b0 over GF(2n) which can be
designed as follows: appends the primitive polynomial's coefficients from ωn−1 to ω0 to the end of
every strand at first. Employ the extract operation to form two test tubes T1 and T2. Tube T1 includes all of
the strands on which xp=1 and tube T2 includes all of
the strands on which xp=0. Then, we add the coefficients, from item ω2n−3 to item ωn−2, to the coefficients of irreducible polynomial in
parallel in tube T1. This forms the new coefficients from ω2n−3 to ωn−2 and has deleted
the ω2n−2 item. The
coefficients from ωn−3 to ω0 are without any
change. For the T2 includes all of
the strands that have xp=0, so just copy the coefficients from ω2n−3 to ω0 without any
change. After all the executions before are run, the highest exponent of ω is reduced to 2n−3. Then, merge T1 and T2 and begin new
reduction. The principle of rest reducing turn is all like this above. When
this algorithm is run out, the highest exponent of ω is reduced to n−1. This algorithm will totally append n×n+(n−1)(n−2)/2 bits more to
every strand.From ParallelShifter(T0,n,p), it takes O(n2) extract
operations, O(n2) merge operations, O(n2) append
operations, and O(1) test tubes to
finish the function of a parallel shifter.


## 3.5. The Mathematical Principle of Division onGF(2n)

OverGF(2n), to do a division operation for a dividend and a
divisor, one should get the divisor's inverse first and then multiply the
dividend. For the primitive polynomial ωn+bn−1ωn−1+⋯+b1ω+b0 is irreducible,
there exists a polynomial g(ω) and a
polynomial f(ω) that fit the
equation (according to Euclid algorithm):(4)g(ω)×divisor+f(ω)×(ωn+bn−1ωn−1+⋯+b1ω+b0)=1.Becauseωn+bn−1ωn−1+⋯+b1ω+b0=0, g(ω)×divisor=1, which is to say g(ω) is the inverse
of the divisor. To find g(ω) and f(ω), one can do as follows, which is called Euclid
algorithm, also called division algorithm; first, ωn+bn−1ωn−1+⋯+b1ω+b0 is divided by
the divisor. If the value of the remainder is 1, that is to say, (ωn+bn−1ωn−1+⋯+b1ω+b0)+g(ω)×divisor=1 with g(ω) is the division
result and the inverse of divisor has found which is g(ω); else let remainder be r(ω), let the divisor be the dividend and r(ω) be the divisor
and do division operation again. Repeat the process until the remainder is 1.
Because the highest exponent of ω of remainder
reduces by 1 in each repeat, it is at most repeating n−1 times. So in
the first time division, the dividend is n+1 bits and the
divisor is n bits and the
remainder is at most n−1 bits, and in
the second time division the dividend is n bits and the
divisor is n−1 bits and the
remainder is at most n−2 bits,…, and
in last time division the dividend is 3 bits and the divisor is 2 bits and the
remainder is 1 bit. Then, trace back to get the g(ω).


## 3.6. The Construction of a Parallel Comparator

Prior to each
step of long division, comparison should be done first. Suppose the divisor isn bits at that
time. At first compare the first two bits of dividend with divisor to determine
that addition operation between first two bits of dividend and divisor should
be done or not, then compare the first three bits of result with divisor,…, compare
the first n bits of result
with divisor, the last time (finally), compare the last n bits of result
with divisor for this time the first bit of result is 0. The following
algorithm is used to compare the divisor which is from pth bit to qth bit with the
bits from jth bit to kth bit in
parallel, and forms tube T1 and T2. T2 contains all
strands on which add execution will be done and T1 contains all
strands on which add execution will not be done (see Algorithm 2).Algorithm 2:Procedure ParallelComparator (T0,p,q,j,k,T1,T2).
(1) If(q−p>k−j) then(1a) Form=1 to q−p−(k−j)(1a1)T3=+(T0,xp+m−11)(1a2)T1=∪(T1,T3)EndForEndIf(2) Form=q−(k−j)−p to q−p(2a)T3=+(T0,xp+m1)(2b)T4=−(T3,xj+m−(q−p−k+j)1)(2c)T5=−(T0,xp+m1)(2d)T6=+(T5,xj+m−(q−p−k+j)1)(2e)T1=∪(T1,T4) and T2=∪(T2,T3,T6) andT0=∪(T0,T5)EndForEndProcedureLemma 2.
The
algorithm Parallel Comparator(T0,p,q,j,k,T1,T2) is applied to
finish the function of parallel comparator.Proof.
Ifq−p>k−j, that means the bits of divisor is more than the bits
of the result which are intended to compare this time. Step (1) considers the
excessive bits of divisor and if any one bit is 1, which means the divisor is
“bigger" than the bits of the result which are intended to compare this
time and pour the strands to T1. Step (2) considers the rest of the bits of divisor
and the bits of result which are intended to compare this time. T3 contains all
strands on which certain bit of divisor is 1 and corresponding bit of the
result is 1; T4 contains all
strands on which certain bit of divisor is 1 and corresponding bit of the
result is 0; T5 contains all
strands on which certain bit of divisor is 0 and corresponding bit of the
result is 0; T6 contains all
strands on which certain bit of divisor is 0 and corresponding bit of the
result is 1. So add execution can be done over strands in T3 and T6, which can not be done over strands in T4, and strands in T5 need more
consideration.
From ParallelComparator(T0,p,q,j,k,T1,T2), it takes O(n) extract
operations, O(n) merge
operations, and O(1) test tubes to
finish the function of a parallel comparator.


## 3.7. The Construction of a Parallel Long Division

Suppose the divisor isn bits and is
from pth bit and the
dividend is n+1 bits and is
from the qth bit in each
strand. To do the long division, first compare the divisor with first two bits
of dividend using ParallelComparator to get the first bit of the result of
division and note down the result of first time addition result. Then, compare
the divisor with the first three bits of the addition result last time to get
the second bit of the result of the long division, and note down the addition
result. Finally, compare the divisor with the last n bits of
addition result last time to get the last bit of division result and the
remainder (see Algorithm 3).Algorithm 3:Procedure SimilarDiv (T0,n,p,q).
(1) Forj=1 to n−1(1a) ParallelComparator(T0,p,p+n−1,q+(j−1)(n+2),q+(j−1)(n+2)+j,T1,T2)(1b) Append(T1,xq+n+1+(j−1)(n+2)0) and Append (T2,xq+n+1+(j−1)(n+2)1)(1c) Fork=0 to n(1c1)T3=+(T1,xq+(n+2)(j−1)+k1) and T4=−(T1,xq+(n+2)(j−1)+k1)(1c2) Append(T3,xq+j(n+2)+k1) and Append (T4,xq+j(n+2)+k0)(1c3)T1=∪(T3,T4)EndFor(1d) ParallelAdder(T2,j+1,q+(j−1)(n+2),p+n−j−1,q+(n+2)j)(1e) Fork=n−j down to 1(1e1)T3=+(T2,xq+(n+2)j−k−11) and T4=−(T2,xq+(n+2)j−k−11)(1e2) Append(T3,xq+(j+1)(n+2)−k−11) and Append (T4,xq+(j+1)(n+2)−k−10)(1e3)T2=∪(T3,T4)EndFor(1f)T0=∪(T1,T2)EndFor(2) ParallelComparator(T0,p,p+n−1,q+(n+2)(n−1)+1,q+(n+2)(n−1)+n,T1,T2)(3) Append(T1,xq+(n+2)n−10) and Append (T2,xq+(n+2)n−11)(4) Fork=0 to n(4a)T3=+(T1,xq+(n+2)(n−1)+k1) and T4=−(T1,xq+(n+2)(n−1)+k1)(4b) Append(T3,xq+(n+2)n+k1) and Append (T4,xq+(n+2)n+k0)(4c)T1=∪(T3,T4)EndFor(5) Append(T2,xq+(n+2)n0)(6) ParallelAdder(T2,n,q+(n+2)(n−1)+1,p,q+(n+2)n+1)(7)T0=∪(T1,T2)EndProcedureLemma 3.
The
algorithm SimilarDiv(T0,n,p,q) is applied to
finish the function of parallel long division.Proof.
Each
execution of step (1) is to get each bit of the long division result. The rest
part is to get the last bit of the long division result. Consider the first
cycle of step (1), step (1a) compares the divisor with the first two bits of
the dividend, and form two tubesT1 and T2 that T2 contains all strands
on which add execution can be done, contrarily the T1. Step (1b) appends 0 to all strands in T1 and appends 1
to all strands in T2. This bit is the first bit of the division result.
Step (1c) just finishes to append the dividend in tube T1. Step (1d) adds the divisor and the first two bits of
the dividend in T2. Step (1e) copies the rest of the bits of the dividend
in T2. Step (1f) pours T1 and T2 together and
finishes the first execution of step (1) to get the first bit of the division
result and the first time addition result. The second execution of step (1) is
to compare the divisor with the first three bits of the addition result last
time and get the second bit of the division result. The principle of other
cycles and the rest of the steps are similar to the principle above. The length
of each strand will reach to q+n+(n+2)n bits when this
algorithm is run out.
From SimilarDiv(T0,n,p,q), it takes O(n2) extract
operations, O(n2) append
operations, O(n2) merge operations,
and O(1) test tubes to
finish the function of a parallel long division.


## 3.8. The Construction of Parallel Traceback

Suppose the irreducible polynomialA(ω)=ωn+bn−1ωn−1+⋯+b1ω+b0 and suppose g(ω) and f(ω) satisfy that g(ω)×divisor+f(ω)A(ω)=1, for the purpose of finding the divisor's inverse, g(ω), we need to do sometimes long division introduced in
Section 3.7; let A(ω) be the dividend
and divisor mentioned above be the divisor in first time and suppose the result
is g1(ω), and if the remainder is 1, then the division result g1(ω) is g(ω). Else, let the divisor last time be the dividend and
let the remainder last time be the divisor and do the long division. Suppose
the result is p(ω) and g2(ω)=p(ω)×g1(ω)+1, if the remainder is 1, the g2(ω) is g(ω). Else, let the divisor last time be the dividend and
let the remainder last time be the divisor and do the long division. Suppose
the result is p(ω) and g3(ω)=p(ω)×g2(ω)+g1(ω), if the remainder is 1, the g3(ω) is g(ω). Generally speaking, we need to trace back after
long division each time: first time, the tracing result is the division's
result; the second time, the tracing's result is the sum of 1 and the product
of the division's result and the tracing's result last time; from the third
time, the tracing's result is the sum of the tracing's result last second time
and the product of the division's result and the tracing's result last time.
The following algorithm is used to do tracing operation from the third time in
which t, d, and p mean that the
tracing's result last second time is from the tth bit and the
last tracing's result is from the dth bit and the
division result is from the pth bit (see Algorithm 4).Algorithm 4:Procedure Traceback (T0,t,d,p,n).
(1) ParallelMultiplier(T0,n,d,p)(2) ParallelShifter(T0,n,p+n+n2)(3) ParallelAdder(T0,n,t,p+M,p+n+M)EndProcedureLemma 4.
The
algorithm TraceBack(T0,t,d,p,n) is used to
trace back after long division from the third time in order to get the
divisor's inverse.Proof.
In
this and following procedures,M=n2+2n−1+n2+(n−1)(n−2)/2, which represent the total number of increased bits
when ParallelMultiplier (T0,n,p,q) and
ParallelShifter (T0,n,p) are called.
Step (1) is used to multiply the last tracing's result from dth bit to the
long division result from pth bit in
parallel. The result will be from the (p+n+n×n)th bit to (p+n+n×n+2n−1)th bit. Step
(2) is to shift the result of multiplication to legal form which will append ((n−1)(n−2)/2+n2) bits to every
strand. And its result is from (p+M)th bit to (p+n+M−1)th bit. Step
(3) is used to add the result to the last second time's tracing's result in
parallel.
From TraceBack(T0,t,d,p,n), it takes O(n2) extract
operations, O(n2) append
operations, O(n2) merge
operations, and O(1) test tubes to
finish the function of tracing back.


## 3.9. The Construction of a Parallel inverse

From the algorithms introduced above, we can find
divisors' inverses in parallel as follows: first pick out the strands on which
divisor equals to 1. Then, let the primitive polynomial be the dividend and the
divisor be the divisor and do long division. Trace back to get the tracing's
result first time and pick up the strands on which the remainder equals to 1
and store them in tubeT1. Then, let the divisor last time be the dividend and
the remainder last time be the divisor and do long division. Collect the
quotient and trace back. Pick up the strands on which the remainder equals to 1
and store them in tube T2,…, these executions, including long division,
collecting every bit of the quotient and tracing back, are run n−1 times at most.
In the following algorithm, the parameters n and p mean that the
divisor is n bits and it
starts from pth bit in every
strand. The last parameter r is used to
represent that each strand in tube is r−1 bit long and we
begin append operation from rth bit of every
strand.Among the algorithm, the
procedure Picking(T0,n,p,Ts) is used to pick
out the strands on which the pth bit to the (p+n−2)th bit are all
0 and the (p+n−1)th bit is 1
and store them in Ts. It is easy to program, so just omitted here (see Algorithm 5).Algorithm 5:Procedure ParallelInverse (T0,n,p,r).
(1) Picking(T0,n,p,Tz)(2) AppendA(x) to the end of
all strands in T0(3) SimilarDiv(T0,n,p,r)(4) Forj=0 to n−1(4a)Tm=+(T0,xr+n+1+(n+2)j1) and Ts=−(T0,xr+n+1+(n+2)j1)(4b) Append(Tm,xr+n+1+(n+2)n+j1) and Append (Ts,xr+n+1+(n+2)n+j0)(4c)T0=∪(Tm,Ts)EndFor(5) Picking(T0,n−1,r+n+1+(n+2)(n−1)+3,T1)(6) Forj=0 to n−1(6a)Tm=+(T0,xp+j1) and Ts=−(T0,xp+j1)(6b) Append(Tm,xr+s1+j1) and Append (Ts,xr+s1+j0)(6c)T0=∪(Tm,Ts)EndFor(7) SimilarDiv(T0,n−1,r+n+1+(n+2)(n−1)+3,r+s1)(8) Append(T0,xr+s1+n+(n+1)(n−1)0)(9) Forj=0 to n−2(9a)Tm=+(T0,xr+s1+n+(n+1)j1) and Ts=−(T0,xr+s1+n+(n+1)j1)(9b) Append(Tm,xr+s1+n+(n+1)(n−1)+1+j1) and Append (Ts,xr+s1+n+(n+1)(n−1)+1+j0)(9c)T0=∪(Tm,Ts)EndFor(10) ParallelMultiplier(T0,n,r+n+1+(n+2)n,r+s1+n+(n+1)(n−1))(11) ParallelShifter(T0,n,r+s1+n+(n+1)(n−1)+n+n2)(12) Add 1 to the product above which will result inn bits more to
each strand(13) Picking(T0,n−2,r+s1+n+(n+1)(n−2)+3,T2)(14) Forj=2 to n−2(14a) Copy dividend (divisor last time) to the end(14b) SimilarDiv(T0,n−j,r+s1+⋯+sj−1+n+2−j+(n+3−j)(n−j)+3,r+s1+⋯+sj)(14c) Appendj bits 0 to the
end(14d) Collectn−j bits quotient
of this division to the end(14e) Traceback(T0,r+s1+⋯+sj−1−n,r+s1+⋯+sj−n,r+s1+⋯+sj+(n+1−j)+(n+2−j)(n−j),n)(14f) Picking(T0,n−1−j,r+s1+⋯+sj+n+1−j+(n+2−j)(n−1−j)+3,Tj+1)EndFor(15) Forj=1 to n−1(15a) Fork=0 to sj+1+⋯+sn−1−1(15a1) Append(Tj,xr+s1+⋯+sj+k0)EndFor(15b) Fork=0 to n−1(15b1)Tm=+(Tj,xr+s1+⋯+sj−n+k1) and Ts=−(Tj,xr+s1+⋯+sj−n+k1)(15b2) Append(Tm,xr+s1+⋯+sn−1+k1) and Append (Ts,xr+s1+⋯+sn−1+k0)(15b3)Tj=∪(Tm,Ts)EndForEndFor(16) Forj=0 to s1+⋯+sn−1+n−2Append(Tz,xr+j0)EndFor(17) Append(Tz,xr+s1+⋯+sn−1+n−11)(18)T0=∪(Tz,T1,T2,…,Tn−1)EndProcedureLemma 5.
The
algorithm ParallelInverse(T0,n,p,r) is applied to
find inverses over GF(2n) in parallel.Proof.
Step
(2) is used to appendn+1 bits
irreducible polynomial, which is the dividend in first long division, to every
strand. The execution of step (3) calls the algorithm SimilarDiv (T0,n,p,r) to finish long
division. Now the length of strands is added up to r+n+(n+2)n bits. Step (4)
finishes the function of collecting every bit of quotient and will add n bits to every
strand. This is the first time tracing result. Step (5) calls the procedure
Picking (T0,n,p,Ts) to pick out the
strands on which the remainder is 1 and store them in tube T1. Step (6) finishes the operation of appending the
dividend, which is divisor last time, to the strands. Note that s1=n+1+(n+2)n+n. Step (7) calls the algorithm SimilarDiv (T0,n,p,q) to accomplish
the second time long division. Step (8) employs the append operation to append
a bit 0 in order to make the quotient to be n bits. Step (9)
finishes the function of collecting every bit of quotient and will add n−1 bits to every
strand. Steps (10) and (11) call the algorithm ParallelMultiplier (T0,n,p,q) and
ParallelShifter (T0,n,p). Step (12) is used to add 1 to the product. These
three steps accomplish the function of tracing back of the second time. Now the
length of every strand is r+s1+n+(n+1)(n−1)+n+M+n−1. Step (13) calls the algorithm Picking (T0,n,p,Ts) to pick out the
strands on which the remainder is 1 and store them in tube T2. One execution of step (14) finishes the function of
long division and tracing back and picking out the strands on which the
remainder is 1. The step will be looped n−3 times, because
the long division should be done n−1 times to make
sure that the remainder of each strand equals to 1 and long division has been
done twice before. Note that while j≥2, sj=n+2−j+(n+3−j)(n+1−j)+n+M+n. Step (15a) is used to append certain bits 0 to each
tube Tj to make sure
that strands in T1 to Tn−1 are all r+s1+⋯+sn−1−1 bits long. Step
(15b) is used to append the inverse gotten before to the last of every strand
in T1 to Tn−1. Step (18) pours strands in all tubes together to one
tube T0. From all above, getting inverse one time needs
increasing s1+s2+⋯+sn−1+n bits to every
strand.
From ParallelInverse(T0,n,p,r), it takes O(n3) extract
operations, O(n3) append
operations, O(n3) merge
operations, and O(n) test tubes to
finish the function of finding inverse in parallel.


## 3.10. The Construction of a Parallel Divider

To do a division operation onGF(2n), first one should calculate divisor's inverse using
above mentioned algorithm then multiply the dividend. The following algorithm
is used to finish the function of parallel division over GF(2n), where the
dividend begins with the qth bit and the
divisor begins with the pth bit, and
current bit is the rth bit (see Algorithm 6).Algorithm 6:Procedure ParallelDivision (T0,n,p,q,r).
(1) ParallelInverse(T0,n,p,r)(2) ParallelMultiplier(T0,n,q,r+s1+⋯+sn−1)(3) ParallelShifter(T0,n,r+s1+⋯+sn−1+n+n×n)EndProcedureLemma 6.
The
algorithm ParallelDivision(T0,n,p,q,r) is used to
finish the function of parallel division over GF(2n).Proof.
Step
(1) calls the algorithm ParallelInverse(T0,n,p,r) to get the
divisor's inverse of every strand. The length of every strand is r+s1+⋯+sn−1+n−1 bits now with
the inverse from (r+s1+⋯+sn−1)th bit to (r+s1+⋯+sn−1+n−1)th bit. Step
(2) calls ParallelMultiplier (T0,n,p,q) to finish the
function of the inverse being multiplied by the dividend every strand with the
dividend starting from the qth bit. Now the
length of each strand adds up to r+s1+⋯+sn−1+n+n×n+2n−1−1 bits. Step (3)
shifts the product by calling ParallelShifter (T0,n,p) and will add (n−1)(n−2)/2+n×n bits to every
strand. Generally speaking, doing parallel division one time need increasing the
strands D=s1+⋯+sn−1+n+M bits.
From ParallelDivision(T0,n,p,q,r), it takes O(n3) extract
operations, O(n3) append
operations, O(n3) merge
operations, and O(n) test tubes to
finish the function of parallel division.


## 3.11. The Construction of a Parallel Adder of Two Points on Elliptic Curve

By far the addition, subtraction (the same to
addition), multiplication, and division operations overGF(2n) have been
solved. Now consider how to execute addition of two points on an elliptic curve y2+xy=x3+ax2+b in biological
ways. We should consider five different cases: case 1, the first point is O and the point
of sum equals to the second point; case 2, the second point is O and the point
of sum equals to the first point; case 3, one point is the inverse of the other
one, and the point of sum is O; case 4, one point equals to the other one, and
computes the sum as the formula in part 3.1; case 5, computes the sum using the
formula in part 3.1.The algorithm AddTwoNode(T0,n,x1,y1,x2,y2,r) is used to add
two points. The first one's position x starts from the (x1)th bit and position y starts from the (y1)th bit, and
the second one's position x starts from the (x2)th bit and y starts from the (y2)th bit. The
parameter r represents the
current bit. In the procedure, it calls Picking01 (T0,n,x1,y1,x2,y2,T11) to pick out the
strands on which the first point is O and store them
in T11, Picking02 (T0,n,x1,y1,x2,y2,T12) to pick out the
strands on which the second point is O and store them
in T12, PickingInverse (T0,n,x1,y1,x2,y2,r,T2) to pick out the
strands on which one point is the inverse of the other one and store them in
tube T2, and PickingEqual (T0,n,x1,y1,x2,y2,T3) to pick out the
strands on which one point equals to the other one and store them in tube T3. These four algorithms are easy to design, so omitted
here. Note that PickingInverse (T0,n,x1,y1,x2,y2,r,T2) will increase n bits to every
strand in T0 (see Algorithm 7).Algorithm 7:Procedure AddTwoNode (T0,n,x1,y1,x2,y2,r).
(1) Picking01(T0,n,x1,y1,x2,y2,T11)(2) Picking02(T0,n,x1,y1,x2,y2,T12)(3) PickingInverse(T0,n,x1,y1,x2,y2,r,T2)(4) PickingEqual(T0,n,x1,y1,x2,y2,T3)(5) Forj=0 to M−1(5a) Append(T0,xr+n+j0)EndFor(6) ParallelAdder(T0,n,y1,y2,r+n+M)(7) ParallelAdder(T0,n,x1,x2,r+n+M+n)(8) ParallelDivision(T0,n,r+n+M+n,r+n+M,r+n+M+2n)(9) Forj=0 to n−1(9a)Tm=+(T3,xx1+j1) and Ts=−(T3,xx1+j1)(9b) Append(Tm,xr+n+j1) and Append (Ts,xr+n+j0)(9c)T3=∪(Tm,Ts)EndFor(10) ParallelMultiplier(T3,n,r+n,r+n)(11) ParallelShifter(T3,n,r+n+n+n×n)(12) ParallelAdder(T3,n,y1,r+n+n+M−n,r+n+n+M)(13) ParallelDivision(T3,n,x1,r+n+n+M,r+n+n+M+n)(14)T0=∪(T0,T3)SUPPOSEU=n+M+n+D(15) ParallelMultiplier(T0,n,r+n+U−n,r+n+U−n)(16) ParallelShifter(T0,n,r+n+U+n×n)(17) ParallelAdder(T0,n,r+n+U−n,r+n+U+M−n,r+n+U+M)(18) ParallelAdder(T0,n,r+n+U+M,x1,r+n+U+M+n)(19) ParallelAdder(T0,n,r+n+U+M+n,x2,r+n+U+M+n+n)(20) Forj=0 to n−1(20a) Append(T0,xa,r+n+U+M+3n+j)EndFor(21) ParallelAdder(T0,n,r+n+U+M+2n,r+n+U+M+3n,r+n+U+M+4n)SUPPOSEX=U+M+5n(22) ParallelAdder(T0,n,x1,r+n+X−n,r+n+X)(23) ParallelMultiplier(T0,n,r+n+U−n,r+n+X)(24) ParallelShifter(T0,n,r+n+X+n+n×n)(25) ParallelAdder(T0,n,r+n+X+n+M−n,r+n+X−n,r+n+X+n+M)(26) ParallelAdder(T0,n,r+n+X+n+M,y1,r+n+X+n+M+n)SUPPOSEY=n+M+n+n(27) Forj=0 to n−1(27a)Tm=+(T0,xr+X+j1) and Ts=−(T0,xr+X+j1)(27b) Append(Tm,xr+n+X+Y+j1) and Append (Ts,xr+n+X+Y+j0)(27c)T0=∪(Tm,Ts)EndFor(28) Forj=0 to n−1(28a)Tm=+(T0,xr+n+X+Y−n+j1) and Ts=−(T0,xr+n+X+Y−n+j1)(28b) Append(Tm,xr+n+X+Y+n+j1) and Append (Ts,xr+n+X+Y+n+j0)(28c)T0=∪(Tm,Ts)EndFor(29) Appendn+X+Y bits 0 to each
strand in T11 and T12. Then, append values of x2 and y2 of each strand
tothe end inT11, and append values of x1 and y1 of each strand
to the end in T12(30) AppendX+Y+2n bits 0 to every
strand in T2(31)T0=∪(T11,T12,T2,T0)EndProcedureLemma 7.
The
algorithm AddTwoNode(T0,n,x1,y1,x2,y2,r) can compute the
sum of two points on elliptic curve.Proof.
Step
(5) employs append operation to appendM bits 0 to all
strands in tube T0. Step (6) to step (8) are operations on tube T0 to get μ of strands in T0. Step (9) to step (13) are operations on tube T3 to get μ of strands in T3. Step (14) pours T0 and T3 to T0 and the length
of every strand in T0 now is r+n+n+M+n+D−1 bits. Step (15)
to step (21) accomplish to compute the position x of point of sum
and the result is from (r+X)th bit. The
execution of steps (22) to (26) is used to get the position y of the sum
which equals to μ(x1+x3)+x3+y1. And now, the position y of the sum is
from (r+X+Y)th bit and the
length is r+n+X+Y−1 bits.
Steps (27) and (28) are applied to append the value
of positionsx and y of the sum of
two points to the last of every strand. Now, the length of every strand in T0 is r+n+X+Y+2n−1 bits with the
value x from the (r+n+X+Y)th bit and y from the (r+n+X+Y+n)th bit.
From AddTwoNode(T0,n,x1,y1,x2,y2,r), it takes O(n3) extract
operations, O(n3) append
operations, O(n3) merge
operations, and O(n) test tubes to
finish the function of a parallel adder for points on elliptic curve.


## 3.12. Breaking the Elliptic Curve Cryptosystem

We have constructed the algorithm above for parallel
computing the point of the sum of two points. Then, we can solve elliptic curve
discrete logarithm problem as follows: consider pointP and Q are given, and l is what we want
to get which matches Q=lP. First, we amplify P into two tubes
and add P in one tube.
Check if 2P equals to Q; if not, note down the value of 2P and pour two
tubes together. Then, amplify the tube into two tubes and add 2P in one tube.
Check if any point equals to Q; if not, note down the value of 4P and pour two
tubes together, or we get the value of l. Then, amplify the tube into two tubes and add 4P in one tube,…, while this loop executes n times, the
value from 1 to 2n for l will have been
checked, and the elliptic curve cryptosystem has been broken by
the solved elliptic curve discrete logarithm
problem.


## 4. Conclusion

This paper is the first effort in literature that
demonstrates that the difficult problem for elliptic curve discrete logarithm
can be solved on a DNA-based computer. While Chang's work makes great progress
in application of DNA computing in cryptoanalysis [16], which is breaking RSA by
factoring integer, this paper proposes application of DNA computing in another
popular cryptosystem, ECC, which is more complex and has more challenge in
cryptoanalysis. Though the algorithm is somewhat complex, it takes a series of
steps that is polynomial in the input size, so it is feasible in theory and
inspirits the development of DNA computing. Simultaneously, the paper also
shows that humans' complex mathematical operations can directly be performed
with basic biological operations. The property for the difficulty of elliptic
curve discrete logarithm is the basis of elliptic curve cryptosystems. However,
this property seems to be incorrect on a molecular computer. This indicates
that the elliptic curve cryptosystems are perhaps insecure if the technique of
DNA computing is skillful enough to run the algorithms efficiently as discussed
in this paper.



---

*Source: 518093-2008-04-07.xml*