Uni?ed Point Addition Formul?and
Side-Channel Attacks
Douglas Stebila1, and Nicolas Th′e riault2
1Institute for Quantum Computing,
University of Waterloo,Waterloo,ON,Canada,
dstebila@iqc.ca
2Department of Combinatorics and Optimization,
University of Waterloo,Waterloo,ON,Canada,
ntheriau@math.uwaterloo.ca
Abstract.The successful application to elliptic curve cryptography of
side-channel attacks,in which information about the secret key can be
recovered from the observation of side channels like power consumption
or timing,has motivated the recent development of uni?ed formul?for
elliptic curve point operations.In this paper,we give a version of a
previously-developed family of uni?ed point addition formul?that uses
projective coordinates for improved e?ciency.We discuss the applica-
bility of a recent attack by Walter on this family of projective formul?
and describe how the?eld arithmetic can be implemented to obtain fully
uni?ed formul?and avoid this type of attack.
Keywords:elliptic-curve cryptography,side-channel attacks,uni?ed
point addition formul?,projective coordinates.
1Introduction
The study of elliptic curves in cryptography[1,2]has been ongoing for a number of years.Elliptic curve cryptography o?ers higher security per key bit compared to other public key cryptosystems and the smaller key size is more suitable for implementation on small devices such as smart cards.More recently,a new class of attacks has been discovered,called side-channel attacks[3],which use infor-mation observed during the execution of the algorithm to help determine the secret key.There are two classes of side-channel attacks:simple side-channel attacks,which analyze the trace of a single execution of a cryptographic proto-col,and di?erential side-channel attacks,which compare the traces of multiple executions of a protocol.
The central operation in an elliptic curve cryptosystem is the point multipli-cation operation,in which a point is multiplied by a scalar.The basic method for This work was performed while the author was a visiting researcher at Sun Microsys-tems Laboratories,with additional support from NSERC,ORDCF,CIAR,CFI,and MITACS.
implementing point multiplication is the double-and-add technique,which uses a binary representation of the scalar and performs a sequence of point additions and point doublings depending on the bits of the scalar.The double-and-add technique is given in Fig.1.
Input:Point P,integer k=P n?1
i=0
k i2i,k n?1=1.
Output:Point Q=kP.
1.Q←P
2.for i=n?2down to0do
2.1.Q←2Q
2.2.if k i=1then Q←P+Q
3.end for
Fig.1.Double-and-add point multiplication algorithm In double-and-add point multiplication,a point doubling is done for every bit of the key k,but a point addition is done only when a bit of the key is1.If,in a side-channel analysis,a point addition is distinguishable from a point doubling, then the bits of the secret key can be determined;this has been demonstrated ex-perimentally using timing and power analysis[3,4].Techniques for counteracting this problem include:performing dummy operations,such as a point addition, each iteration[5];using alternate point multiplication algorithms,such as Mont-gomery point multiplication[6];using alternate curve parameterizations,such as the Jacobi or Hessian forms;and unifying the algorithms for point addition and point doubling so that they use the same sequence of?eld operations and hence are indistinguishable;it is this last technique that we address in this paper.
A uni?ed formula for point addition and point doubling,in which point addi-tion and point doubling use the same sequence of?eld operations,was?rst given by Brier and Joye[7]in a?ne and projective form.Walter[8]demonstrated a theoretical side-channel attack on the formula of Brier and Joye that,instead of exploiting any irregularity in the sequence of?eld operations performed,ex-ploits an irregularity in the implementation of the?eld operations themselves in the context of the uni?ed point addition formula.A subsequent paper of Brier, D′e ch`e ne,and Joye[10]o?ers an in?nite family of uni?ed point addition formul?in a?ne form.
In this paper,we give a projective version of the uni?ed point addition for-mul?of Brier,D′e ch`e ne,and Joye.Whereas Walter’s attack used the occurrence of the conditional subtraction in a Montgomery?eld multiplication,we note that a conditional addition(in any?eld representation)is also an integral step of?eld subtraction.A typical algorithm for computing prime?eld subtraction is given in Fig.2;the conditional addition is step2.3
3Similarly,a?eld addition contains a conditional subtraction,however our techniques of Sec.5do not make use of this conditional subtraction.
2
We?nd that the ability to detect the occurrence of the conditional addition in?eld subtractions in both the a?ne and projective form decreases the amount of work necessary to recover the key.In the projective case in Montgomery representation,the e?ect is substantial when combined with Walter’s original attack,and in some cases the key for a192-bit elliptic curve over a prime?eld can be recovered in about2hours.From this observation we conclude that a secure implementation requires constant-runtime?eld operations,not just uni?ed point arithmetic.
We also provide some performance results for the various uni?ed formul?and discuss the applicability of timing attacks.It appears that even though uni-?ed point addition and uni?ed point doubling algorithms have slightly di?erent runtime,the timing di?erence is not large enough to be exploited.
Input:Integers a,b,q such that0≤a,b≤q?1.
Output:Integer c such that c=a?b mod q and0≤c≤q?1.
1.c←a?b
2.if c<0then c←c+q
Fig.2.Field subtraction algorithm
This paper is organized as follows:Section2provides a short introduction to elliptic curve cryptography.In Sec.3,we describe the uni?ed formula of Brier and Joye and describe an attack by Walter.In Sec.4,we describe the family of uni?ed formul?in a?ne coordinates given by Brier,D′e ch`e ne,and Joye and give our derivation of the formul?for projective coordinates.In Sec.5,we present an extension of Walter’s attack,analyze its e?ect on the formul?and discuss coun-termeasures.Section6contains performance results and discusses the possibility of timing attacks on double-and-add projective uni?ed point multiplication.
Throughout the body of this paper,we derive formul?only for elliptic curves over prime?elds.Formul?and results for elliptic curves over binary?elds are given in the appendix.We have omitted the discussion of curves over binary ?elds from the main text because the attacks of Sec.5do not apply.
2Background
For a?eld I K,the Weierstra?form of an elliptic curve is given by the equation E/I K:y2+a1xy+a3y=x3+a2x2+a4x+a6.(1) For?elds of characteristic other than2or3,the equation of the curve can be simpli?ed to
y2=x3+ax+b.(2)
3
The set of points on the curve,joined with the point at in?nity O ,forms an abelian group,denoted E (I K);the point at in?nity serves as the identity element in the group.Two points P =(x 1,y 1)and Q =(x 2,y 2),P =Q ,can be added to obtain a third point P +Q =(x 3,y 3),where
x 3=λ2?x 1?x 2
(3)y 3=λ(x 1?x 3)?y 1(4)λ= y 2?y 1x 2?x 1,if P =Q 3x 21+a 2y 1,if P =Q .(5)
Because λis de?ned di?erently depending on whether or not P =Q ,the formula for point addition di?ers from the formula for point doubling.
The formula given above uses a?ne coordinates .The formula for λrequires an inversion,which can be computationally expensive in practice.This has mo-tivated the development of formul?using projective coordinates .In this case,a point is represented by three coordinates,P =(X,Y,Z ),with x =X/Z and y =Y/Z .The denominator is carried through all of the point additions and point doublings comprising a point multiplication,and only at the end is the in-version Z ?1computed to return the ?nal result to a?ne coordinates.While this technique may require more ?eld operations such as multiplications or squarings in each point addition or doubling,it may be more e?cient provided the cost of inversion is higher than the cost of the additional ?eld multiplications and squarings.
3Uni?ed Formula of Brier and Joye
The formula for λin (5)when P =±Q cannot be used for point doubling because x 1=x 2in that case and the denominator is 0.Starting with the point addition form of λ,Brier and Joye [7]use a series of algebraic manipulations to obtain a form of λthat is de?ned for both point addition and point doubling:
λ=(x 1+x 2)2?x 1x 2+a y 1+y 2,if y 1+y 2=0.(6)
This formula for λis only de?ned when y 1+y 2=0.Brier and Joye subsequently derive a projective formula for point addition using this uni?ed value of λ,with x i =X i /Z i ,y i =Y i /Z i :
X 3=2F W ,Y 3=R (G ?2W )?L 2,Z 3=2F 3,(7)
where U 1=X 1Z 2,U 2=X 2Z 1,S 1=Y 1Z 2,S 2=Y 2Z 1,Z =Z 1Z 2,T =U 1+U 2,M =S 1+S 2,F =ZM,L =MF,G =T L,R =T 2?U 1U 2+aZ 2,and W =R 2?G .This formula requires 13?eld multiplications and 5?eld squarings.
4
3.1Walter’s Side-Channel Attack
Walter’s side-channel attack[8]is a theoretical attack that assumes the oc-currence of a conditional subtraction in a Montgomery modular multiplication operation can be detected.This attack should be considered successful if a non-negligible proportion of the keys can be computed signi?cantly faster than an attack on the whole keyspace.We will see that in some cases,the attack becomes practical as a(relatively)high proportion of keys can be found with(relatively) few computations.
Montgomery’s modular reduction technique[6]replaces the modular reduc-tion step after each multiplication with a less expensive step,leaving a result that is not completely reduced.This partial results can be used again in further operations,with the expensive modular reduction step being left for the end. Though Montgomery’s technique is not e?cient for a single modular multiplica-tion,it is e?ective when amortized over a long sequence of operations,such as a point multiplication.
Montgomery multiplication is implemented as follows(c.f.[11]).Let q be an odd prime,and let R>q with gcd(R,q)=1;it is often convenient to choose R=2W t,where W is the word size of the computer architecture.For an input z Input:Integers q,R,z,q with q =?q?1mod R,R>q,0≤z Output:Integer c such that c=zR?1mod q,0≤c 1.c←(z+(zq mod R)q)R?1 2.if c≥q then c←c?q Fig.3.Montgomery modular multiplication algorithm Walter considers the e?ect of being able to detect the conditional subtraction in step2of Fig.3in a point multiplication using the uni?ed formula of Brier and Joye.In the projective formula of(7),for a point doubling,the computa-tions of U1and U2are identical,as are the computations of S1and S2.For a point doubling,the occurrence of a conditional subtraction in the Montgomery multiplication for U1must be the same as that for U2.Thus,if a conditional subtraction is observed in the computation of one of U1or U2but not the other, then a point doubling could not have occurred and the operation must be a point addition.(The same argument allows the computations of S1and S2to distinguish a point addition.) We must now determine the probability p dist of distinguishing a point ad-dition from a point doubling.Walter showed[8,(4)]that,in the multiplication multiplication of two independent randomly distributed residues X and Y with uniformly distributed Z,the probability of a conditional subtraction occurring is 5 p sub =14q 2 ?W t ,where q is the prime and 2?W t is chosen as in the description of Montgomery modular multiplication above.In practice,q is often very close to 2W t ,so p sub ≈1/4.For this value,the probability that a conditional subtraction occurs in the computation of one of U 1,U 2but not the other (and similarly for S 1and S 2)is p di?=2p sub (1?p sub )≈38 .(8)Hence,the probability that the occurrence of conditional subtractions in the computations of U 1,U 2,S 1,and S 2can be used to distinguish a point addition from a point doubling is p dist =1?(1?p di?)2≈3964≈0.61.(9) It is possible to improve this value in certain cases.Walter considers the following scenario:If,over a number of samples of point multiplications,the input point is randomly distributed,then in about one out of 512samples there will be a input point of the form P ≈ 116q,116q,1516q .For a point of this special form,the probability that a point addition can be distinguished from a point doubling is p dist ≈188703262144 ≈0.72.(10)In the sequence of operations in a double-and-add point multiplication algo-rithm,the position of a point addition determines the point doublings on either side of it.Let n be the size in bits of the prime ?eld.Given p dist ,the total number of determined operations is:32(n ?1)p dist ?(n ?2) 12 p dist 2.(11)Walter provides a worked example for the NIST 192-bit prime curve [12].For this curve,the prime is of a special form q =2192?264?1and the natural choice for Montgomery multiplication is 2W t =2192so q 2?W t is very close to https://www.doczj.com/doc/b217690521.html,ing p dist in (10),the total number of determined operations given by (11)is approximately 181.6out of an expected total of 3 2(n ?1)=286.5operations, leaving 104.9unknown operations.Of these,approximately 1 2(n ?1)(1?p dist )= 26.8are point additions.Walter concludes that a brute-force search through this space of possible keys requires an expected 104.926.8 ≈286.8point multiplications. Walter’s analysis provides additional means of decreasing the key space to be searched,including substring restrictions on the possible sequence of point additions and point doublings;furthermore,for the point addition operations which were not distinguished,some combinations of conditional subtractions are more likely than others,and this can also reduce the key space.These two techniques allow the size of the e?ective keyspace in the example to be reduced to below 256. The probabilistic analysis given above does not give the best estimate of the number of determined operations.In experiments,Walter [8]found that,with 6 a set of512samples,it is most e?cient to just pick the sample that has the most number of distinguished point additions.This approach,combined with the substring restrictions given above,can give e?ective keyspaces for a192-bit prime curve of size just217.6,which can be easily searched. 4Uni?ed Formul?of Brier,D′e ch`e ne,and Joye 4.1A?ne Coordinates The uni?ed point addition formula of Brier and Joye from the previous section is de?ned when y1+y2=0,which always holds in the case of point doubling, but it is not applicable to all possible point additions.Izu and Tagaki[9]showed that in some settings these special cases of the point addition could be used to reveal the key.This concern lead Brier,D′e ch`e ne,and Joye[10]to develop an in?nite family of uni?ed point addition formul?which are de?ned for all points. Let m=m(x1,y1;x2,y2)be an arbitrary polynomial,and de?ne ?m=?m(x1,y1;x2,y2)=m(x2,y2;x1,y1).Recall that we are only concerned with elliptic curves over prime?elds.Let λm= (x 1 +x2)2?x1x2+a+(y1?y2)m y1+y2+(x1?x2)m ,if y1+y2+(x1?x2)m=0 (x1+x2)2?x1x2+a+(y2?y1)?m y1+y2+(x2?x1)?m ,if y1+y2+(x2?x1)?m=0 .(12) These formul?are de?ned for all points except those which satisfy y1+y2+(x1?x2)m=0=y1+y2+(x2?x1)?m.(13) If x1=x2,then y1=?y2and hence Q=?P,so the addition formula is not needed.If x1=x2,then m+?m=0.Thus,if we require that m satis?es the condition [(m+?m=0)?(x1=x2)],(14) thenλm is well-de?ned.There is an in?nite family of equations satisfying this condition: m k=(x1?x2)2k.(15) For e?ciency purposes,we can choose m=m0=1.In this case,we get the following uni?ed formula forλ: λ=λ1=(x1+x2)2?x1x2+a+(?1)δ(y1?y2) y1+y2+(?1)(x1?x2) ,y1+y2+(?1)δ(x1?x2)=0, (16) whereδ=0when y1+y2+x1?x2=0andδ=1otherwise. Uni?ed point addition usingλ=λ1requires2?eld multiplications,2?eld squarings,and1?eld inversion. 7 4.2Projective Coordinates To mitigate the high cost of?eld inversion compared to the cost of?eld multi-plication,points are expressed in projective coordinates so that?eld inversion need only be done once per point multiplication rather than at each intermediate point addition or point doubling. We now obtain a projective form of the uni?ed point addition formula given byλas de?ned in(16).We begin by noting that since P+Q=Q+P,the value for y in(4)is symmetric and hence2y3=λ(x1+x2?2x3)?(y1+y2). Letting x i=X i/Z,y i=Y i/Z and completing the square in the numerator ofλ, we obtain: X3=2F W,Y3=R(G?2W)?LF M,Z3=2F3,(17) where U1=X1Z2,U2=X2Z1,S1=Y1Z2,S2=Y2Z1,Z=Z1Z2,T=U1+ U2,M=S1+S2,V=(?1)δ(U1?U2),N=(?1)δ(S1?S2),E=M+V,F= ZE,L=F E,G=LT,R=T2?U1U2+Z(aZ+N),and W=R2?G.Note that δ=0when S1+S2+U1?U2=0andδ=1otherwise.This formula requires 16?eld multiplications and3?eld squarings.4 5Extending Walter’s Attack 5.1Conditional Modular Reduction Attack Walter’s original attack in Sec.3.1assumed that the conditional subtraction at the end of Montgomery multiplication could be detected.We extend this idea by assuming that the conditional subtraction(or addition)at the end of a?eld addition(or subtraction)can be detected.For?eld subtraction as given in Fig.2, the conditional addition is step2.5 We will observe later in this section that there are some modular subtractions in the uni?ed point addition algorithms where,in the case of a point doubling, the arguments are equal and hence the result of the subtraction is zero,i.e.when a=b we are computing a?b mod q as a?b=0.In this case,a conditional addition in?eld subtraction is never performed.However,if we observe the occurrence of a conditional addition for the operation a?b,then it must be that b>a and hence the operation in question must be a point addition. 4The multiplication by(?1)δin the computation of V and N can be implemented with conditional branching(if statement). 5In implementation,this is common.For example,the OpenSSL[13]library provides a function BN mod su b quick which performs exactly the operations in Fig.2,and similarly for?eld addition.When reduction is done using the Extended Euclidean Algorithm,as in OpenSSL’s BN mod sub function,and the value to be reduced is strictly between?q and q,the sequence of steps performed is e?ectively the same as Fig.2and includes a conditional addition. 8 5.2E?ect on a?ne formul?of Sec.4.1 The a?ne formul?of Brier,D′e ch`e ne,and Joye in (16)requires the computa-tion of y 1?y 2and x 1?x 2.If all of the coordinates are distributed uniformly at random,then the probability that a conditional addition is necessary in the com-putation of y 1?y 2is 1/2,and similarly for x 1?x 2.In this case,the probability that a point addition can be distinguished is p dist =1?(1?1/2)2=3/4. We ?rst note that even when additions and doublings cannot be distin-guished,a side channel attack will reveal the number of operations performed in the point multiplication.If the key length is known,then knowing the number of operations gives the number of additions (since the number of doublings is ?xed by the key length).To simplify the analysis,we will consider only keys of the most common length.This does not mean that the attack cannot work for other key lengths,but rather that it is more di?cult to bound the work required to determine the key. If q is between 3·2r ?1and 3·2r ,then the most common key length is r and occurs for p l =r ≥1/3of the keys (integers)between 0and q .This probability is maximal if q is close to 2r +1,in which case p l =r ≈1/2of the keys have length r .If there are k additions of which k 1are not identi?ed,then we can consider the key-space to search as the set of sequences of r ?k “zeros”and k 1“ones”.These sequences are combined with the identi?ed additions of the double and add sequence to give a list of possible keys (the substring structure will often remove a number of sequences).The number of possible keys is then bounded by r ?k +k 1k 1 ,which in turn is bounded by r k 1 .If we assume that all keys of length r are possible (which is true if q ≥2r ?1?1),the probaiblity that a key of length r uses k additions is r k 12r .Given a key with k additions,the probability that k 1of them are not identi?ed is k k 1 (p dist ) k ?k 1(1?p dist )k 1.The probability that exactly k 1additions are not identi?ed in a key of length r is therefore p k 1=r k =k 1 r k 12r k k 1 (p dist )k ?k 1(1?p dist )k 1=r k =k 1(1?p dist )k 12 r k 1 r ?k 1k ?k 1 (p dist )k ?k 1=(1?p dist )k 12r r k 1 r ?k 1 i =0 r ?k 1i (p dist )i =(1?p dist )k 12r r k 1 (1+p dist )r ?k 1 = r k 1 1?p dist k 1 1+p dist r ?k 1.(18) Although the average number of unidenti?ed addition is (1?p dist )r/2=r/8,some keys will have fewer additions remaining to be identi?ed. 9 For our 192-bit prime ?eld example curve,we have r =191and we get an average of 23.9additions remaining to be identi?ed,so the search space is still quite large.However,the analysis has been done assuming that the additions in a point multiplication are independent.This may not be strictly true as x 1and y 1(the x and y coordinates of the base point)are the same for all the additions.In one-eighth of point multiplications kP ,the x -coordinate of the base point P will take on a value between 0and 1 8q and will have an average value of 116q . We take the notation that in the double-and-add point multiplication algorithm the ?xed base point P is the ?rst argument to the uni?ed point addition formula.In the computation of x 1?x 2in (16),over the course of a point multiplication x 2will be uniformly distributed and thus it is expected for 15 16of the point addition operations that x 2>x 1and a conditional addition occurs.We do not put any condition on the y -coordinate of P and assume that the size of y 1can be considered independent from the size of x 1.In this case,the probability that a point addition can be distinguished is the probability that a conditional addition occurs in either the computation of x 1?x 2or y 1?y 2: p dist =1? 1?1516 1?12 =3132 (19)Using p dist in (19),the expected number of additions remaining to be identi?ed decreases to 2.99.We can then conclude that a signi?cant proportions of keys of length r will be left with at 3or fewer unidenti?ed additions (using the distribution in (18),we ?nd that 1in ≈24.6of all keys satisfy that condition).The number of possible keys is then bounded (loosely)by 1913 ≈220.1. With point multiplication using the modi?ed Jacobian wNAF algorithm with w =5,the fastest point multiplication technique listed in Table 2,it would take 116.5minutes on an 900MHz UltraSPARC III to search a keyspace of size 220.1.Hankerson,Menezes,and Vanstone [11,§3.7]provide a survey of point multiplication algorithms with even faster performance. 5.3E?ect on projective formul?of Sec.4.2 Just as for a?ne formul?,there are two operations in the projective formul?of (17)where we can take advantage of the ability to detect a conditional addition in a ?eld subtraction.Without loss of generality,suppose δ=0.Consider the calculations V =U 1?U 2and N =S 1?S 2.In the case of a point doubling,U 1=U 2and S 1=S 2,so no conditional addition will occur in the calculation of either V or N .However,in the case of a point addition,U 1and U 2will be uniformly distributed over 0,...,p ?1and so with probability p add =12,U 2 and a conditional addition is needed in the computation of V =U 1?U 2(sim-ilarly for N =S 1?S 2).Moreover,the occurrence of a conditional addition in the computation of V is independent of the occurrence for N .If a conditional addition is observed in at least one of these computations,then the operation is known to be a point addition,revealing the key bit.The probability of distin-guishing a point addition is again 1?(1?p add )2=3/4.It should be noted that 10 taking advantage of base points of a special form is not possible here as U 1,U 2,S 1and S 2all depend on both of the points of the addition,so the probabilities of identifying point additions are independent from each other. If the ?eld is implemented using Montgomery representation,Walter’s orig-inal attack [8]on detecting conditional subtractions in Montgomery reductions still applies to this projective formula.The detection of a conditional subtraction is used to distinguish a point addition from a point doubling in the computation of U 1as compared to U 2,and of S 1as compared to S 2.We can combine the two sources of information (conditional additions in the ?eld subtractions and dif-ferences in conditional subtractions in the Montgomery reductions)to increase the probability of success. We now have four di?erent conditional events which distinguish a point ad-dition from a point doubling: 1. conditional subtraction in computation of one of U 1,U 2but not the other,2. conditional subtraction in computation of one of S 1,S 2but not the other,3. conditional addition in computation of N =U 1?U 2,and 4.conditional addition in computation of V =S 1?S 2. Each of these events occurs independently,so the total probability of distin-guishing a point addition from a point doubling is p dist =1?(1?p add )2(1?p di?)2.(20) If we assume no special knowledge on the base point of the point multipli-cation,i.e.p add =1/2and p di?≈3/8,we get p dist ≈231/256≈0.902.From the distribution obtained in (18),we have an average of ≈0.049r unidenti?ed additions. If we look for base points of a special form as in Walter’s attack for the formul?of Brier and Joye,the increase in the probability of success is relatively small.With a point of the form ～ 116q,116q,1516q ,we get p di?≈0.93and the expected number of unidenti?ed addition decreases to ≈0.035r .This decrease is small considering that we have to restrict ourselves to 1in 512point.In this case,it is much more practical to consider all base points and take advantage of the variability.For example,for a ?eld of 192bits,15.4%of all point multiplications have 6or less unidenti?ed additions,while the special base points (1in 512)have 6.7unidenti?ed additions on average. Table 1gives estimates for the attack at various ?eld sizes.At each ?eld size,we give the average number of additions remaining to be identi?ed.We also evaluate the costs of the attack when we give a bound on the maximum number of additions remaining to be identi?ed (we chose 3and 6as examples)before the key is attacked.In each case,we give the expected number of point multiplications that must be observed before ?nding such a key and a (loose)upper bound on the size of the remaining keyspace.We assume that general points are considered,so p dist ≈0.902,and that all keys have size r .To take other key sizes into account,the expected number of keys required should be multiplied by a factor between 2and 3(depending on the ratio q/2r )if keys of length other than r are assume to give a failure. 11 Table1.Expected number of operations using conditional modular reduction attack, using p dist as in(20). ?eld size in bits(r+1)160192224256384512 average missing additions:7.769.3310.8912.4518.7024.95 at most3unidenti?ed additions: expected number of keys required:21.866.6217746217.1225.2 bound on the keyspace:219.3220.1220.8221.4223.1224.4 at most6unidenti?ed additions: expected number of keys required:2.965.8212.830.9210.9217.8 bound on the keyspace:234.2235.9237.2238.4241.9244.4 Just as in Walter’s analysis[8]it is possible to decrease the key space remain-ing to be searched,for example by using substring restrictions on the possible sequence of point additions and point doublings. 5.4Countermeasures to the Conditional Modular Reduction Attack The success of the Conditional Modular Reduction attack depends on informa-tion leaked on the size of intermediate values which is observed based on the ?eld subtraction having a conditional addition.If the?eld subtraction were to have constant runtime,for example by inserting a dummy addition to o?set the conditional addition,then the attack would not apply.However,inserting dummy operations may increase the susceptibility of the algorithm to di?erential side-channel attacks. Another countermeasure would be to replace an operation a?b mod q with a sequence of instructions that determines which of a and b is larger,subtracts the smaller from the larger,and then?ips the sign of the result.In most software implementations,the sign of a number is stored in a di?erent register than the value of the number,so?ipping the sign of a number is a single machine instruction;the di?culty is now in detecting a single instruction compared to a multi-precision integer addition. A third countermeasure consist in taking the?eld reductions(both Mont-gomery reductions and addition/subtraction of a multiple of q)as independent operations from the multiplications,squarings,additions and subtractions and rewrite the uni?ed formul?in consequence.This means we will accept that some of the values used during the computations may be greater than q.Although this approach removes any danger of an attack based on variations in the?eld arith-metic,it may have a negative impact on the e?ciency,in particular when the ?eld size is close to a multiple of the word size. At this point we should also note that choosingδ=0orδ=1requires the comparison of two?eld elements,so at least these two must be fully reduced. Since repeated operations or even a change from addition to subtraction could 12 potentially lead to an attack,we chooseδto ensure that1 2(x1+x2+y1+y2)= x2?δinstead of y1+y2+(?1)δ(x1?x2)=0(the two conditions are equivalent, but the computations required for the?rst test are more uniform). For simplicity,we will assume the?eld is in Montgomery representation. We distinguish Montgomery reductions(denoted MontRed(·))and q-reduction where multiples of q are added/subtracted(denoted reduce(·)).To avoid all possible extensions of the attack,we prefer to err on the side of caution and implement the?eld operations as follows: –Products(and squares)are not reduced unless stated. –Sums are not reduced unless stated. –Subtractions never contain a conditional addition(a?xed multiple of q is always added to the?rst operand before doing the subtraction). –If an integer is to be q-reduced,then it is at least as large as q. –For the a?ne formula,inversion accepts any integer between1and6q?1 and coprime to q and returns an integer between1and q?1. –Montgomery reductions are allowed to return an output between0and2q?1. They accept inputs between0and6q2for a?ne coordinates(R>6q)and between0and16q2for projective coordinates(R>16q). –The multiples of q used in the formul?are pre-computed. For the a?ne formula,we get the algorithm in Fig.4.For the projective formula,we let the X,Y and Z coordinates be in the range[0,2q?1]and obtain the algorithm in Fig.5.Note that by construction(x1+x2)2≥x1x2,so the pre-reduction result in step8of the a?ne formula is indeed positive(similarly for step14in the projective formula) Input:Points P=(x1,y1)and Q=(x2,y2),P=Q. Output:Point(x3,y3)=P+Q. 1.E←x1+y1+y2+x2 2.if E is odd,then F←E+3q,else F←E+2q 3.G←reduce(F/2) 4.if G=x2,thenδ←0,elseδ←1 5.H←F?2x2?δ 6.I←H?1mod q 7.J←x1+x2 8.K←MontRed(J2?x1·x2) 9.L←reduce(2q+K+a+y1+δ?y2?δ) 10.λ=MontRed(L·I) 11.M←MontRed(λ2) 12.x3←reduce(3q+M?x1?x2) 13.N←MontRed(λ·(q+x1?x3)) 14.y3←2q+N?y1 Fig.4.A?ne coordinates uniform point addition formula 13 Input:Points P=(X1,Y1,Z1)and Q=(X2,Y2,Z2),P=Q. Output:Point(X3,Y3,Z3)=P+Q. 1.?U1←X1·Z2,?U2←X2·Z1,?S1←Y1·Z2,?S2←Y2·Z1 2.?T=?U1+?U2 3.M←MontRed(?S1+?S2+?T) 4.if M is odd,then V←M+3q,else V←M+2q 5.C←reduce(V/2) 6.B←reduce(p+MontRed(?U2)) 7.if C=B,thenδ←0,elseδ←1 8.E←V?MontRed(2?U2?δ) 9.Z←MontRed(Z1·Z2),T←MontRed(?T) 10.F←MontRed(Z·E),U1←MontRed(?U1),U2←MontRed(?U2) 11.L←MontRed(F·E) 12.G←MontRed(L·T) 13.K←2q+MontRed(a·Z+?S1+δ)?MontRed(?S2?δ) 14.R←MontRed(Z·K+T2?U1·U2) 15.H←MontRed(R2) 16.W←reduce(3q+H?G) 17.X3←MontRed((2F)·W) 18.J←MontRed(F2) 19.Z3←MontRed((2F)·J) 20.N←MontRed(F·M) 21.Y3←2q?MontRed(R·(2q+2W?G)+L·N) Fig.5.Projective coordinates uniform point addition formula 6Timing The timings in this section were performed on a900MHz UltraSPARC III using the multi-precision integer and elliptic curve libraries from NSS3.9[14]with no optimized assembly code.To obtain high-resolution timings,we used the Solaris hrtime C library,which has a resolution of100ns.We use the160-bit prime ?eld curve secp160r2[15]. On our test system,the average time of a160-bit prime?eld modular sub-traction a?b mod q when a>b is about320ns.When a Table2gives performance timings for point operations using the uni?ed point addition and doubling formul?given in this paper as well as other schemes. Point multiplications for all fomul?except Jacobian projective and modi?ed Jacobian wNAF use the double-and-add technique.The timings in the table are the average of105operations. Table3gives average timings and standard deviations for point additions and point doublings in the course of a single point multiplication.The results 14 Table2.Average point operation timings for secp160r2curve. Formula Addition Doubling Multiplication BDJ a?ne,m=1126.5μs126.2μs29.03ms BDJ projective58.9μs58.5μs13.99ms BJ projective49.8μs49.5μs11.76ms A?ne115.7μs118.4μs27.89ms Jacobian projective7.95ms Modi?ed Jacobian wNAF,w=5 6.22ms were obtained by recording the time of each addition or doubling in a single point multiplication using the double-and-add algorithm. Table 3.Individual point operation timings from a single point multiplication for secp160r2curve. Formul?Operation Average Standard Deviation uni?ed addition126.528μs 4.094μs≈3.2% BDJ a?ne,m=1uni?ed doubling126.155μs 3.700μs≈2.9% di?erence0.373μs≈0.3% uni?ed addition58.992μs0.474μs≈0.8% BDJ projective uni?ed doubling59.307μs0.448μs≈0.75% di?erence0.315μs≈0.53% In the top half of Table3,timings are given for point addition and doubling using the a?ne formul?of Brier,D′e ch`e ne,and Joye.A uni?ed doubling takes slightly less time than a uni?ed addition on average,but di?erence between the two operations(0.3%)is one-tenth the size of the standard deviation of either operation,so the timings of the two operations cannot be reliably distinguished. In the bottom half of Table3,timings are given for point addition and dou-bling using the projective formul?developed in Sec.4.2.A uni?ed doubling takes slightly more time(0.53%)than a uni?ed addition.The standard deviation of either operation,at0.8%for addition and0.75%for doubling,is less than twice di?erence. For the a?ne formul?,uni?ed addition is slower than uni?ed doubling,but the situation is reversed for the projective formul?.This phenomenon may be particular to the compiler and processor used. For both the a?ne and projective formul?of Brier,D′e ch`e ne,and Joye in Table3,the average di?erence in timing between a point addition and point doubling is too small compared the standard deviation to be of practical use 15 on its own.However,we do not dismiss the fact that this information may be helpful when combined with other side-channel information. Acknowledgments We are grateful to I.D′e ch`e ne for her insight on uni?ed formul?and other helpful comments.We also thank N.Gura of Sun Microsystems Laboratories for his advise on how to perform high-resolution timings on Solaris.D.S.is grateful of the hospitality of S.Chang of Sun Microsystems Laboratories where he was resident during this research. 16 References 1.Koblitz,N.:Elliptic curve cryptosystems.Mathematics of Computation48(1987) 203–209 https://www.doczj.com/doc/b217690521.html,ler,V.:Use of elliptic curves in cryptography.In Williams,H.C.,ed.:Advances in Cryptology–Proc.CRYTPO’85.Volume218of LNCS.,Springer-Verlag(1986) 417–428 3.Kocher,P.:Timing attacks on implementations of Di?e-Hellman,RSA,DSS,and other systems.In Koblitz,N.,ed.:Advances in Cryptology–Proc.CRYPTO’96. Volume1109of LNCS.,Springer-Verlag(1996)104–113 4.Kocher,P.,Ja?e,J.,Jun,B.:Di?erential power analysis.In Wiener,M.,ed.: Advances in Cryptology–Proc.CRYPTO’99.Volume1666of LNCS.,Springer-Verlag(1999)388–397 5.Coron,J.S.:Resistance against di?erential power analysis for elliptic curve cryp- tosystems.In C?etin K.Ko?c,Paar,C.,eds.:Cryptographic Hardware and Embed-ded Systems(CHES)’99.Volume1717of LNCS.,Springer-Verlag(1999)292–302 6.Montgomery,P.L.:Modular multiplication without trial division.Mathematics of Computation44(1985)519–521 7.Brier,′E.,Joye,M.:Weierstra?elliptic curves and side-channel attacks.In Nac- cache,D.,Paillier,P.,eds.:Public Key Cryptography–PKC2002.Volume2274 of LNCS.,Springer-Verlag(2002)335–345 8.Walter,C.D.:Simple power analysis of uni?ed code for ECC double and add.In Joye,M.,Quisquater,J.J.,eds.:Crytpographic Hardware and Embedded Systems (CHES)2004.Volume3156of LNCS.,Springer-Verlag(2004)191–204 9.Izu,T.,Takagi,T.:On the Security of Brier-Joye’s Addition For- mula for Weierstrass-form Elliptic Curves Technical Report,Technis-che Universit¨a t Darmstadt,Available online:https://www.doczj.com/doc/b217690521.html,rmatik.tu-darmstadt.de/TI/Veroe?entlichung/TR/ 10.Brier,′E.,D′e ch`e ne,I.,Joye,M.:Uni?ed point addition formul?for elliptic curve cryptosystems.In Nedjah,N.,de Macedo Mourelle,L.,eds.:Embedded Cryp-tographic Hardware:Methodologies and Architectures.Nova Science Publishers (2004)247–256 11.Hankerson,D.,Menezes,A.,Vanstone,S.:Guide to Elliptic Curve Cryptography. Springer-Verlag(2004) 12.National Institute of Standards and Technology:Recommended el- liptic curves for federal government use(1999)Available online: https://www.doczj.com/doc/b217690521.html,/CryptoToolkit/dss/ecdsa/NISTReCur.pdf. 13.OpenSSL Project:OpenSSL v0.9.8(2005)Available online: https://www.doczj.com/doc/b217690521.html,/. 14.Mozilla Foundation:Netscape Security Services(NSS)v3.9(2005)Available online: https://www.doczj.com/doc/b217690521.html,/projects/security/pki/nss/. 15.Certicom Research:SEC2:Recommended elliptic curve domain parameters(2000) Available online:https://www.doczj.com/doc/b217690521.html,/. 16.Hankerson,D.,Hernandez,J.L.,Menezes,A.:Software implementation of elliptic curve cryptography over binary?elds.In C?etin K.Ko?c,Paar,C.,eds.:Crytpo-graphic Hardware and Embedded Systems(CHES)2000.Volume1965of LNCS., Springer-Verlag(2000)1–24 17 A Elliptic Curves over Binary Fields A.1Background For ?elds of characteristic 2,the equation of an elliptic curve can be simpli?ed to: E /I K :y 2+xy =x 3+ax 2+b .(21) Two points P =(x 1,y 1)and Q =(x 2,y 2)can be added to obtain a third point P +Q =(x 3,y 3),where x 3=λ2+λ+x 1+x 2+a (22)y 3=λ(x 1+x 3)+x 3+y 1(23)λ= y 1+y 2x 1+x 2,if P =Q x 1+y 1x 1 ,if P =Q .(24) A.2Uni?ed Formula of Sec.3The uni?ed form of λfor point addition and doubling for curves over binary ?elds is: λ=(x 1+x 2)2+x 1x 2+a (x 1+x 2)+y 1y 1+y 2+x 2,if y 1+y 2+x 2=0.(25)Point addition or doubling using the a?ne form requires 1inversion,4multi-plications,and 2squarings;using a projective form requires 20multiplications and 3squarings.In practice,a binary ?eld inversion has the same computational cost as about 10?eld multiplications [16],so the a?ne form is faster than the projective form. A.3 Uni?ed Formul?of Sec.4Let λm = (x 1+x 2)2+x 1x 2+y 2+a (x 1+x 2)+(y 1+y 2)m y 1+y 2+x 2+(x 1+x 2)m ,if y 1+y 2+x 2+(x 1+x 2)m =0(x 1+x 2)2+x 1x 2+y 1+a (x 1+x 2)+(y 1+y 2)?m y 1+y 2+x 2+(x 1+x 2)?m ,if y 1+y 2+x 1+(x 1+x 2)?m =0 .(26) These formul?are de?ned for all points except those which satisfy y 1+y 2+x 2+(x 1+x 2)m =0=y 1+y 2+x 1+(x 1+x 2)?m .(27)For e?ciency purposes,we can choose m =m 0=0.In this case,we get the following uni?ed formula for λ: λ=λ0= (x 1+x 2)2+x 1x 2+a (x 1+x 2)+y 2x 1+y 1+y 2,if x 1+y 1+y 2=0(x 1+x 2)2+x 1x 2+a (x 1+x 2)+y 1x 2+y 1+y 2 ,if x 2+y 1+y 2=0.(28)Uni?ed point addition using λ=λ0requires 4?eld multiplications,2?eld squar-ings,and 1?eld inversion. 18 A.4Uni?ed Formul?of Sec.4.2 We now obtain a projective form of the uni?ed point addition formula given by λas de?ned in(28).Letting x i=X i/Z i,y i=Y i/Z i and completing the square in the numerator ofλ,we obtain: X3=F W,Y3=R(LU+W)+X3+HES,Z3=F H,(29) where U1=X1Z2,U2=X2Z1,S1=Y1Z2,S2=Y2Z1,Z=Z1Z2,T=U1+ U2,M=S1+S2,E=M+U1+δ,F=ZE,L=F E,G=LT,H=F2,R= T2+U1U2+Z(aT+S2?δ),K=F R+G+aH,and W=R2+K.Note that δ=0when M=U1andδ=1otherwise.These terms were derived using y3=λ(x1+x3)+x3+y1but by symmetry of point addition could have equally been derived using y3=λ(x2+x3)+x3+y2. This projective formula requires19?eld multiplications and3?eld squarings. In practice,a binary?eld inversion has the same computational cost as about10?eld multiplications[16]so the a?ne form of the uni?ed point addition formul?is faster than the projective form. A.5Application of Attack of Sec.5 For the projective formula for uni?ed point addition for curves over binary?elds as given in(29),Walter’s attack does not apply nor does our extension in Sec.5.1. Walter’s original attack does not apply because?eld multiplication in binary ?elds is not implemented using Montgomery multiplication.Our extension does not apply because no modular reduction operations are necessary in?eld addi-tion. 19 算法模板 网络122 王硕 目录 1.数学 1.1 矩阵 (2) 1.2 一次方程组的解 (3) 1.3 矩阵的逆 (4) 1.4 最大公约数 (6) 1.5 欧几里得扩展 (6) 1.6 素数表 (7) 1.7 判断素数 (8) 1.8 分解质因数 (9) 1.9 欧拉函数 (10) 1.10 欧拉函数表 (11) 1.11 mobius函数 (12) 1.12 数值积分 (12) 1.13 数值积分（精确） (13) 1.14 快速幂求余 (14) 1.15 进制转换 (15) 1.16 格雷码 (16) 1.17 高精度类 (16) 1.18 Fibonacci数列 (22) 1.19 FFT (23) 2.图论 2.1 拓扑排序 (24) 2.2 dijkstra (25) 2.3 floyd-warshall (26) 2.4 kruskal …………………26 3.序列 3.1 快速排序 (28) 3.2 逆序对 (28) 3.3 最长不降子序列长度 (30) 3.4 最长公共子序列长度 (31) 3.5 最长公共上升子序列长度 (31) 3.6 最长公共上升子序列 (32) 4.字符串 4.1 Sunday (34) 4.2 子串清除 (34) 4.3 KMP (37) 5.数据结构 5.1 并查集 (38) 5.2 树状数组 (39) 5.3 左偏树 (40) 5.4 哈希 (41) 5.5 RMQ线段树 (41) 6.其他 6.1 多边形面积 (43) 6.2 幻方构造 (43) 6.3 奇数阶次幻方 (45) 1.1矩阵 #include The way 的用法 Ⅰ常见用法： 1)the way+ that 2)the way + in which（最为正式的用法） 3)the way + 省略（最为自然的用法） 举例：I like the way in which he talks. I like the way that he talks. I like the way he talks. Ⅱ习惯用法： 在当代美国英语中，the way用作为副词的对格，“the way+ 从句”实际上相当于一个状语从句来修饰整个句子。 1)The way =as I am talking to you just the way I’d talk to my own child. He did not do it the way his friends did. Most fruits are naturally sweet and we can eat them just the way they are—all we have to do is to clean and peel them. 2）The way= according to the way/ judging from the way The way you answer the question, you are an excellent student. The way most people look at you, you’d think trash man is a monster. 3）The way =how/ how much No one can imagine the way he missed her. 4）The way =because 湖南商学院《数据结构与算法》课程设计报告 姓名: 朱晰璋 学号: 160920044 专业: 计算机科学与技术 班级: 计科1602 指导教师: 邹文 职称: 计算机与信息工程学院 20 年月 目录 （结构供参考，请按照自己内容生成，标题宋体小二加粗，居中，段前后距各0.5行）1. 课程设计概（黑体四号，段前后距各0.5行） (1) 1.1问题描述（宋体小四，行距1.5倍） (1) 1.2基本要求 (1) 1.3开发环境 (1) 2. 数据结构及算法分析 (1) 2.1数据结构分析 (1) 2.2算法分析及相关算法介绍 (1) 3. 详细设计与实现 (1) 3.1软件结构 (1) 3.2模块设计 (1) 4. 测试与运行 (1) 5. 总结与收获 (1) 参考文献（要求五篇以上，格式请参考知网上论文） (1) 附录 (1) 课程设计评审表 课程设计题目（宋体小二号，加粗，居中，单倍行距，段前后0.5行） 1.课程设计概述（一级标题段前后距各0.5行） 1.1问题描述（目的，内容，题目等）（黑体小四，二级标题段前后距各0.5行） 1.2基本要求（要完成什么功能，有什么性能，） 1.3开发环境 2.数据结构及算法分析 2.1数据结构分析（采用线性表，树，图等等数据结构的原因及具体结构） 2.2算法分析（比如采用分治法，描述分治法的原理以及应用到此处的理由） 3.详细设计与实现 3.1总体结构（整体包括几个模块，每个模块的功能） 3.2模块设计（具体每个模块的设计实现，可以用流程图或伪码描述等，类似教材的算法描述，包括输入输出，算法功能，以及具体算法描述） 4.测试与运行（测试数据，运行结果，要截图） 5.总结与收获（如果采用多种算法或者数据结构解决同一个问题，请 在总结中用一小节比较各种不同算法空间效率，时间效率，如果没有请省略） 参考文献（要求五篇以上，格式如下，不清楚清参考知网上论文）参考文献通常应为近3年的，至少5篇，其中最好有英文文献。其具体写法为： 1. 专著、论文集、毕业论文、报告等 [序号]作者.书名[文献类型标志].出版地：出版者，出版年.起止页码（任选）.（文 The way的用法及其含义（二） 二、the way在句中的语法作用 the way在句中可以作主语、宾语或表语： 1.作主语 The way you are doing it is completely crazy.你这个干法简直发疯。 The way she puts on that accent really irritates me. 她故意操那种口音的样子实在令我恼火。The way she behaved towards him was utterly ruthless. 她对待他真是无情至极。 Words are important, but the way a person stands, folds his or her arms or moves his or her hands can also give us information about his or her feelings. 言语固然重要,但人的站姿,抱臂的方式和手势也回告诉我们他(她)的情感。 2.作宾语 I hate the way she stared at me.我讨厌她盯我看的样子。 We like the way that her hair hangs down.我们喜欢她的头发笔直地垂下来。 You could tell she was foreign by the way she was dressed. 从她的穿著就可以看出她是外国人。 She could not hide her amusement at the way he was dancing. 她见他跳舞的姿势，忍俊不禁。 3.作表语 This is the way the accident happened.这就是事故如何发生的。 Believe it or not, that's the way it is. 信不信由你, 反正事情就是这样。 That's the way I look at it, too. 我也是这么想。 That was the way minority nationalities were treated in old China. 那就是少数民族在旧中 1、模板匹配法： 在机器识别事物的过程中，常常需要把不同传感器或同一传感器在不同时间、不同成像条件下对同一景象获取的两幅或多幅图像在空间上对准，或根据已知模式到另一幅图像中寻找相应的模式，这就叫匹配。在遥感图像处理中需要把不同波段传感器对同一景物的多光谱图像按照像点对应套准，然后根据像点的性质进行分类。如果利用在不同时间对同一地面拍摄的两幅照片，经套准后找到其中特征有了变化的像点，就可以用来分析图中那些部分发生了变化；而利用放在一定间距处的两只传感器对同一物体拍摄得到两幅图片，找出对应点后可计算出物体离开摄像机的距离，即深度信息。 一般的图像匹配技术是利用已知的模板利用某种算法对识别图像进行匹配计算获得图像中是否含有该模板的信息和坐标； 2、基本算法： 我们采用以下的算式来衡量模板T（m,n)与所覆盖的子图Sij（i,j)的关系，已知原始图像S(W,H)，如图所示： 利用以下公式衡量它们的相似性： 上述公式中第一项为子图的能量，第三项为模板的能量，都和模板匹配无关。第二项是模板和子图的互为相关，随（i,j）而改变。当模板和子图匹配时，该项由最大值。在将其归一化后，得到模板匹配的相关系数： 当模板和子图完全一样时，相关系数R(i,j) = 1。在被搜索图S中完成全部搜索后，找出R的最大值Rmax(im,jm)，其对应的子图Simjm即位匹配目标。显然，用这种公式做图像匹配计算量大、速度慢。我们可以使用另外一种算法来衡量T和Sij的误差，其公式为： 计算两个图像的向量误差，可以增加计算速度，根据不同的匹配方向选取一个误差阀值E0，当E(i,j)>E0时就停止该点的计算，继续下一点的计算。 最终的实验证明，被搜索的图像越大，匹配的速度越慢；模板越小，匹配的速度越快；阀值的大小对匹配速度影响大； 3、改进的模板匹配算法 将一次的模板匹配过程更改为两次匹配； 第一次匹配为粗略匹配。取模板的隔行隔列数据，即1/4的模板数据，在被搜索土上进行隔行隔列匹配，即在原图的1/4范围内匹配。由于数据量大幅减少，匹配速度显著提高。同时需要设计一个合理的误差阀值E0： E0 = e0 * (m + 1) / 2 * (n + 1) / 2 式中：e0为各点平均的最大误差，一般取40~50即可； m,n为模板的长宽； 第二次匹配是精确匹配。在第一次误差最小点（imin, jmin)的邻域内，即在对角点为（imin -1, jmin -1), (Imin + 1, jmin + 1)的矩形内，进行搜索匹配，得到最后结果。 定冠词the的用法： 定冠词the与指示代词this ,that同源,有“那(这)个”的意思,但较弱,可以和一个名词连用,来表示某个或某些特定的人或东西. (1)特指双方都明白的人或物 Take the medicine.把药吃了. (2)上文提到过的人或事 He bought a house.他买了幢房子. I've been to the house.我去过那幢房子. (3)指世界上独一无二的事物 the sun ,the sky ,the moon, the earth (4)单数名词连用表示一类事物 the dollar 美元 the fox 狐狸 或与形容词或分词连用,表示一类人 the rich 富人 the living 生者 (5)用在序数词和形容词最高级,及形容词等前面 Where do you live?你住在哪? I live on the second floor.我住在二楼. That's the very thing I've been looking for.那正是我要找的东西. (6)与复数名词连用,指整个群体 They are the teachers of this school.(指全体教师) They are teachers of this school.(指部分教师) (7)表示所有,相当于物主代词,用在表示身体部位的名词前 She caught me by the arm.她抓住了我的手臂. (8)用在某些有普通名词构成的国家名称,机关团体,阶级等专有名词前 the People's Republic of China 中华人民共和国 the United States 美国 (9)用在表示乐器的名词前 She plays the piano.她会弹钢琴. (10)用在姓氏的复数名词之前,表示一家人 the Greens 格林一家人(或格林夫妇) (11)用在惯用语中 in the day, in the morning... the day before yesterday, the next morning... in the sky... in the dark... in the end... on the whole, by the way... get around/round to: do (something that you have intended to do for a long time.) e.g: I was meaning to see that film but I just never got around to it. 我一直想看那部电影，但始终还是没能去看。 just as well/as well: suggesting that something will be a good thing to do/or that it was luckily that something was done or happened. 正好，幸好，不妨 e.g: “Shall I phone to remind him? ” “That would be just as well.” It was just as well you’re not here. You wouldn’t like the noise. get by (Line 3): be good enough but not very good; manage to live or do things e.g: It is a bit hard for the old couple to get by on a small amount of pension. 如果我们坚持到底，我们就能熬过难关。 We’ll get by if we hold on to the end. get across: be understood Did your speech get across to the students? get away with: run away without being punished The teller had been stealing money from the bankand got away with it. 这个出纳一直在偷银行的钱却能侥幸逃脱。 get through (Line 45): come successfully to the end e.g: We’ve stored enough food and fuel to get through the cold winter. 为了度过寒冬，我们已经储备了足够的食物和燃料。 make it (Line 9) : be successful, fulfill the purpose e.g: Having failed for thousands of times, he eventually made it. 她最后成功地成为了一家大公司的总裁。 She finally made it as a CEO of a big corporation. haul (Line 16) v. transport, as with a truck, cart, etc. e.g: These farmers haul fruits and vegetables to the market on a cart in the early morning every day. v. pull or drag sth. with effort or force e.g: A crane has to be used to haul the car out of the stream. long-overdue (Line 20) adj. Being something that should have occurred much earlier. e.g: Changes to the tax system are long overdue .She feels she’s overdue for promotion. supplement (Line 21) v. add to sth. in order to improve it (followed by with) e.g: 1) Forrest does occasional freelance to supplement his income. 2) The doctor suggested supplementing my diet with vitamins E and A. supplementary adj. additional, auxiliary spray (Line 22): v. force out liquid in small drops upon (followed by with) eg: I’ll have to spray the roses w ith insecticide to get rid of the greenfly. freelance (Line 23) adj. doing particular pieces of work for different organizations rather than working all the time for a single 自由职业者的 e.g: Most of the journalists I know are/work freelance. 高精度计算模板 注意：减法、除法要用到compare函数 乘法需要加法的部分，加法需要减法部分 #include string ADD_INT(string str1, string str2) { string MINUS_INT(string str1, string str2); int sign = 1; string str; if(str1[0] == '-') { if(str2[0] == '-') { sign = -1; str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1)); }else { str = MINUS_INT(str2, str1.erase(0, 1)); } }else { if(str2[0] == '-') str = MINUS_INT(str1, str2.erase(0, 1)); else { string::size_type l1, l2; int i; l1 = str1.size(); l2 = str2.size(); if(l1 < l2) { for(i = 1; i <= (int)(l2 - l1); i++) str1 = "0" + str1; }else { for(i = 1; i <= (int)(l1 - l2); i++) str2 = "0" + str2; } int int1 = 0, int2 = 0; for(i = str1.size() - 1; i >= 0; i--) { int1 = (int(str1[i]) - 48 + int(str2[i]) - 48 + int2) %10; int2 = (int(str1[i]) - 48 + int(str2[i]) - 48 +int2) / 10; str = char(int1 + 48) + str; } if(int2 != 0) str = char(int2 + 48) + str; } } //运算后处理符号位 if((sign == -1) && (str[0] !='0')) str = "-" + str; return str; } “tｈｅwａｙ+从句”结构的意义及用法 首先让我们来看下面这个句子: Ｒead the foｌloｗｉnｇpassagｅａnd talkａbout ｉt wi ｔh your classmaｔes．Try tｏｔeｌl whaｔyｏu thiｎk ｏf Tom aｎd ｏｆｔhe ｗay the chiｌｄrenｔrｅated ｈim. 在这个句子中，ｔhe waｙ是先行词,后面是省略了关系副词that或in whｉch的定语从句。 下面我们将叙述“the ｗaｙ+从句”结构的用法。 1.tｈe wａy之后，引导定语从句的关系词是tｈat而不是hoｗ,因此，<<现代英语惯用法词典＞＞中所给出的下面两个句子是错误的：Ｔhｉs is ｔｈeｗayｈowｉtｈａppened. This is the way how he ａlwａｙs treats me. 2．在正式语体中,thaｔ可被in which所代替;在非正式语体中，ｔhat则往往省略。由此我们得到theｗay后接定语从句时的三种模式：1) tｈe ｗaｙ＋ｔhａt-从句２）the way +ｉn whiｃh－从句3) the ｗay +从句 例如：Ｔｈe way(in whiｃh ，thａt) ｔhｅｓｅｃomｒade ｓloｏｋａｔｐrobｌems is wrong．这些同志看问题的方法 不对。 Ｔｈｅｗａy(that ,ｉn ｗhiｃh)yoｕ’ｒe doinｇit is comple ｔeｌy crａzy.你这么个干法,简直发疯。 Wｅａdmiｒｅd him for thｅｗay ｉｎｗhｉch he fａｃeｓdiｆficultieｓ． Waｌlａｃe ａｎd Ｄarwiｎｇreed ｏn the way ｉｎwhi ｃh ｄｉfｆｅrｅnt forms ｏf life had ｂegｕn.华莱士和达尔文对不同类型的生物是如何起源的持相同的观点。 Thｉs is ｔｈe ｗaｙ（tｈａｔ) hｅdｉd it. I lｉkeｄｔhe waｙ(ｔhat) ｓｈeｏｒganized ｔhe ｍeetｉng． 3.theｗay(tｈat)有时可以与hｏw(作“如何”解）通用。例如： That’s tｈe ｗaｙ(tｈaｔ) shｅspoke. = Tｈat’s how shｅspoke. 表示“方式”、“方法”，注意以下用法： 1.表示用某种方法或按某种方式，通常用介词in(此介词有时可省略)。如： Do it (in) your own way. 按你自己的方法做吧。 Please do not talk (in) that way. 请不要那样说。 2.表示做某事的方式或方法，其后可接不定式或of doing sth。 如： It’s the best way of studying [to study] English. 这是学习英语的最好方法。 There are different ways to do [of doing] it. 做这事有不同的办法。 3.其后通常可直接跟一个定语从句(不用任何引导词)，也可跟由that 或in which 引导的定语从句，但是其后的从句不能由how 来引导。如： 我不喜欢他说话的态度。 正：I don’t like the way he spoke. 正：I don’t like the way that he spoke. 正：I don’t like the way in which he spoke. 误：I don’t like the way how he spoke. 4.注意以下各句the way 的用法： That’s the way (=how) he spoke. 那就是他说话的方式。 Nobody else loves you the way(=as) I do. 没有人像我这样爱你。 The way (=According as) you are studying now, you won’tmake much progress. 根据你现在学习情况来看，你不会有多大的进步。 2007年陕西省高考英语中有这样一道单项填空题： ——I think he is taking an active part insocial work. ——I agree with you_____. A、in a way B、on the way C、by the way D、in the way 此题答案选A。要想弄清为什么选A，而不选其他几项，则要弄清选项中含way的四个短语的不同意义和用法，下面我们就对此作一归纳和小结。 一、in a way的用法 表示：在一定程度上，从某方面说。如： In a way he was right.在某种程度上他是对的。注：in a way也可说成in one way。 二、on the way的用法 1、表示：即将来(去)，就要来(去)。如： Spring is on the way.春天快到了。 I'd better be on my way soon.我最好还是快点儿走。 Radio forecasts said a sixth-grade wind was on the way.无线电预报说将有六级大风。 2、表示：在路上，在行进中。如： He stopped for breakfast on the way.他中途停下吃早点。 We had some good laughs on the way.我们在路上好好笑了一阵子。 3、表示：(婴儿)尚未出生。如： She has two children with another one on the way.她有两个孩子，现在还怀着一个。 She's got five children，and another one is on the way.她已经有5个孩子了，另一个又快生了。 三、by the way的用法 第26卷第6期2010年6月信号处理SIGNAL PROCESSING Vol.26.No.6Jun.2010 收稿日期：2009年4月23日；修回日期：2009年11月24日 雷达高分辨距离像模板自动生成算法 彭 勃 魏玺章 黎 湘 （国防科技大学电子科学与工程学院 长沙410073） 摘 要：模板的完备性直接决定了基于高分辨距离像的雷达目标识别系统的分类性能；在外场试验中限于目标姿态、 环境等因素难以获得准确标定的目标立体角范围内全姿态模板数据。针对一维距离像识别的工程实用化需求，本文基于数据驱动思想，提出了新的一维距离像聚类模板自动生成算法。与传统方法相比，本文方法在提高工程可行性的同时提高了识别性能。为满足实验需要，本文提出了新的基于MSTAR 图像的高分辨距离像反演算法，得到更精确的反演数据。基于该数据的实验结果表明算法解决了模板生成姿态角依赖性问题，提高了识别性能。 关键词：高分辨距离像；模板；聚类；反演 中图分类号：TN957.51 文献标识码：A 文章编号：1003－0530（2010）06－0819－05 Automatic Generation of High Range Resolution Profiles Models for Radar Recognition PENG Bo WEI Xi-zhang LI Xiang （School of Electronic Science and Engineering ，NUDT ，Changsha 410073） Abstract ： The completeness of template directly determines the classification performance of automatic radar target recognition system based on high resolution range profiles （HRRP ）.It ’ s difficult to get HRRP training data labeled accurately covering the entire target-aspect angle because of a lot of practical factors in the field experiments ，such as target attitude ，environment and so on.Accord-ing to the demand of engineering practical development ， the dissertation proposes an algorithm of automatic generation of HRRP template based on data driving means.The proposed approach can be realized much easier with better recognition performance ，comparing with the traditional approach.The dissertation puts forward a new HRRP inversion method based on MSTAR image to get more precise HRRP using in cyber-emulation.At last ， the result of the experiments proves the algorithm.Key words ： High Range Resolution Profiles ；template ；clustering ；HRRP inversion 1引言 自从雷达自动目标识别研究兴起以来，基于高分 辨距离像的雷达目标识别系统因具有识别速率高、适应性广的优点受到广泛的关注。其中，高分辨距离像模板自动生成是该类自动目标识别系统的基础，直接关系到匹配识别的质量和效率。 高分辨距离像（HRRP ）有着平移敏感性、幅度敏感性和目标姿态敏感性。识别系统通常采用预处理的方法克服HRRP 的平移敏感性和幅度敏感性，包括利用最小二乘准则实现距离对准、能量归一化以及去直流 漂移 ［1，2］ 。三种敏感性中尤为不容易克服的是目标特征信号姿态敏感性问题。高分辨雷达工作在光学区， 可以利用散射点模型较好描述［3］ 。根据该模型，高分辨距离像随姿态角的变化主要来源于越距离单元游动 导致的散射点模型改变，即同一距离单元的散射点位 置随着雷达视角及目标姿态所发生的变化。 针对该问题，通常的解决办法可分为两类，一是基于HRRP 模板来进行匹配识别，二是提取目标姿态不 变性质的特征。1993年，文献［4］阐述了直接将一维距离像作为特征矢量的可行性，提出了基于匹配度的距离像匹配识别方法。文献［5］利用多幅飞机目标的一维距离像构造相关滤波器，减少了识别过程中所需 的运算量。文献［6］在每一个姿态角域内构造识别所 需的合成模板，文献［1］提出了基于姿态角的平均模板生成算法，文献［7］根据数据间的相近程度和样本数量 动态调节各帧模板训练数据的角度边界，优化了基于 姿态角的平均模板生成算法。文献［8，9］中采用混合 Gamma 模型来描述目标HRRP 的统计特性，将多分量的后验概率应用于距离像识别，充分利用目标HRRP The way的用法及其含义（一） 有这样一个句子：In 1770 the room was completed the way she wanted. 1770年，这间琥珀屋按照她的要求完成了。 the way在句中的语法作用是什么？其意义如何？在阅读时，学生经常会碰到一些含有the way 的句子，如：No one knows the way he invented the machine. He did not do the experiment the way his teacher told him.等等。他们对the way 的用法和含义比较模糊。在这几个句子中，the way之后的部分都是定语从句。第一句的意思是，“没人知道他是怎样发明这台机器的。”the way的意思相当于how；第二句的意思是，“他没有按照老师说的那样做实验。”the way 的意思相当于as。在In 1770 the room was completed the way she wanted.这句话中，the way也是as的含义。随着现代英语的发展，the way的用法已越来越普遍了。下面，我们从the way的语法作用和意义等方面做一考查和分析： 一、the way作先行词，后接定语从句 以下3种表达都是正确的。例如：“我喜欢她笑的样子。” 1. the way+ in which +从句 I like the way in which she smiles. 2. the way+ that +从句 I like the way that she smiles. 3. the way + 从句(省略了in which或that) I like the way she smiles. 又如：“火灾如何发生的，有好几种说法。” 1. There were several theories about the way in which the fire started. 2. There were several theories about the way that the fire started. 模板匹配算法实现 在机器视觉识别的过程中,常常需要把不同的待测图像和标准图像进行比较,一种最常用的图像识别技术就 是模板匹配.下面是具体实现的过程: /************************************************************************* * * 函数名称： * TemplateMatchDIB() * * 参数: * LPSTR lpDIBBits - 指向源DIB图像指针 * LPSTR lpDIBBitsBK - 指向背景DIB图像指针 * LONG lWidth - 源图像宽度（象素数） * LONG lHeight - 源图像高度（象素数） * LONG lTemplateWidth - 模板图像宽度（象素数） * LONG lTemplateHeight - 模板图像高度（象素数） * * 返回值: * BOOL - 运算成功返回TRUE，否则返回FALSE。 * * 说明: * 该函数用于对图像进行模板匹配运算。 * * 要求目标图像为255个灰度值的灰度图像。 ************************************************************************/ BOOL WINAPI TemplateMatchDIB (LPSTR lpDIBBits, LPSTR lpTemplateDIBBits, LONG lWidth, LONG lHeight, LONG lTemplateWidth,LONG l T emplateHeight) { // 指向源图像的指针 LPSTR lpSrc,lpTemplateSrc; // 指向缓存图像的指针 LPSTR lpDst; // 指向缓存DIB图像的指针 LPSTR lpNewDIBBits; HLOCAL hNewDIBBits; //循环变量 long i; long j; way 的用法 【语境展示】 1. Now I’ll show you how to do the experiment in a different way. 下面我来演示如何用一种不同的方法做这个实验。 2. The teacher had a strange way to make his classes lively and interesting. 这位老师有种奇怪的办法让他的课生动有趣。 3. Can you tell me the best way of working out this problem? 你能告诉我算出这道题的最好方法吗？ 4. I don’t know the way (that / in which) he helped her out. 我不知道他用什么方法帮助她摆脱困境的。 5. The way (that / which) he talked about to solve the problem was difficult to understand. 他所谈到的解决这个问题的方法难以理解。 6. I don’t like the way that / which is being widely used for saving water. 我不喜欢这种正在被广泛使用的节水方法。 7. They did not do it the way we do now. 他们以前的做法和我们现在不一样。 【归纳总结】 ●way作“方法，方式”讲时，如表示“以……方式”，前面常加介词in。如例1； ●way作“方法，方式”讲时，其后可接不定式to do sth.，也可接of doing sth. 作定语，表示做某事的方法。如例2，例3； t h e-w a y-的用法 The way 的用法 "the way+从句"结构在英语教科书中出现的频率较高, the way 是先行词, 其后是定语从句.它有三种表达形式:1) the way+that 2)the way+ in which 3)the way + 从句(省略了that或in which),在通常情况下, 用in which 引导的定语从句最为正式,用that的次之,而省略了关系代词that 或 in which 的, 反而显得更自然,最为常用.如下面三句话所示,其意义相同. I like the way in which he talks. I like the way that he talks. I like the way he talks. 一.在当代美国英语中,the way用作为副词的对格,"the way+从句"实际上相当于一个状语从句来修饰全句. the way=as 1)I'm talking to you just the way I'd talk to a boy of my own. 我和你说话就象和自己孩子说话一样. 2)He did not do it the way his friend did. 他没有象他朋友那样去做此事. 3)Most fruits are naturally sweet and we can eat them just the way they are ----all we have to do is clean or peel them . 大部分水果天然甜润,可以直接食用,我们只需要把他们清洗一下或去皮. way的用法总结大全 way的用法你知道多少，今天给大家带来way的用法，希望能够帮助到大家，下面就和大家分享，来欣赏一下吧。 way的用法总结大全 way的意思 n. 道路,方法,方向,某方面 adv. 远远地，大大地 way用法 way可以用作名词 way的基本意思是“路,道,街,径”,一般用来指具体的“路,道路”,也可指通向某地的“方向”“路线”或做某事所采用的手段,即“方式,方法”。way还可指“习俗,作风”“距离”“附近,周围”“某方面”等。 way作“方法,方式,手段”解时,前面常加介词in。如果way前有this, that等限定词,介词可省略,但如果放在句首,介词则不可省略。 way作“方式,方法”解时,其后可接of v -ing或to- v 作定语,也可接定语从句,引导从句的关系代词或关系副词常可省略。 way用作名词的用法例句 I am on my way to the grocery store.我正在去杂货店的路上。 We lost the way in the dark.我们在黑夜中迷路了。 He asked me the way to London.他问我去伦敦的路。 way可以用作副词 way用作副词时意思是“远远地,大大地”,通常指在程度或距离上有一定的差距。 way back表示“很久以前”。 way用作副词的用法例句 It seems like Im always way too busy with work.我工作总是太忙了。 His ideas were way ahead of his time.他的思想远远超越了他那个时代。 She finished the race way ahead of the other runners.她第一个跑到终点,远远领先于其他选手。 way用法例句算法模板【最后更新2014-05】
The way常见用法
数据结构与算法课程设计模板2018
The way的用法及其含义(二)
模板匹配算法
(完整版)the的用法
英语languagepoint(完整版)
高精度模板(算法必备)
“the way+从句”结构的意义及用法
way 用法
雷达高分辨距离像模板自动生成算法
The way的用法及其含义(一)
模板匹配算法实现
way 的用法
the-way-的用法讲解学习
way的用法总结大全
相关主题
文本预览