CN1610291A - Data Encryption and Decryption Methods - Google Patents

Abstract

The data enciphering and deciphering method includes pseudo-enciphering data to be transmitted in pseudo-enciphering method in the transmitting side and deciphering the received data in the method corresponding to the pseudo-enciphering method in the receiving side. The present invention, unlike traditional elliptic curve cipher system, adopts pseudo-enciphering method to obtain new plain text embedding method and one enciphering system with semanteme safety under the adaptive selective cipher text attack. The present invention provides one very clear plain text embedding mode and can verify the legality of cipher text to provide even high data safety.

Description

Data Encryption and Decryption Methods

technical field

The invention relates to a data encryption and decryption method, in particular to a semantically secure encryption and corresponding decryption method under an adaptive selected ciphertext attack on an elliptic curve group with a new plaintext embedding method, belonging to computers and communications field of security technology.

Background technique

Since Diffie and Hellman proposed the idea of public key encryption system in 1976, cryptographers and mathematicians have been researching for the concrete realization of this idea for nearly thirty years, but so far, the security Effective public-key encryption systems are still very limited. According to the problems they are based on, they can be roughly divided into three categories: encryption systems based on the decomposition of large numbers, encryption systems based on finite field discrete logarithm problems, and ellipse-based encryption systems. Encryption schemes for the curved discrete logarithm problem. Among them, since no sub(sub)exponential time algorithm has been found to solve the discrete logarithm problem of elliptic curves, the encryption system based on the discrete logarithm problem of elliptic curves has the incomparable advantages of the former two types of encryption systems, for example: in the same security In terms of strength, the size of system parameters and keys is relatively short (for example, 160bits of Elliptic Curve Cryptography (ECC) and 1024bits of RSA have considerable security strength), and there are more choices.

Elliptic curve public key cryptography was independently proposed by V.Miller and N.Koblitz in 1985, and the subsequent elliptic curve cryptosystems almost all translated the existing cryptosystems based on the discrete logarithm problem on finite fields to elliptic obtained from the curve group. The Elliptic Curve Encryption Scheme ECES (Elliptic Curve Encryption Scheme) mentioned in the standard IEEE P1363 of the American Institute of Electrical and Electronics Engineers is derived from the ElGamal system. Because its encryption algorithm is scalable, it is not indistinguishable under adaptive chosen ciphertext attacks. (Indistinguishability under adaptive chosen-ciphertext attack, IND-CCA2), but indistinguishable under plaintext attack (Indistinguishability under chosen-plaintext attack, IND-CPA); in 2000, M.Abdalla et al. proposed a secure The encryption system DHIES (encryption system based on the Diffie-Hellman problem), because its efficiency is equivalent to ElGamal, and the security level is high, it is adopted by some standards, such as ANSI X9.63 (ANSI is the American National Standardization Organization American The abbreviation of National Standards Institute) and SECG (The Standards for Efficient Cryptography Group, elliptic cipher group standard). Apply DHIES to the elliptic curve group to obtain the elliptic curve integrated encryption system ECIES (Elliptic Curve Integrated Encryption System), which is the organization NESSIE (New European schemes for Signatures, New European schemes for Signatures, Integrity and Encryption) the elliptic curve hybrid encryption system, the current security conclusion is that in the general group model, if the symmetric encryption system is semantically secure under the chosen plaintext attack, and the Hash function is ideal, then the ECIES system is IND -CCA2 is safe, but since the elliptic curve group has a special property, which is ignored by the general group oracle, this can only be regarded as a theoretical conclusion. NTT (Nippon Telegraph and Telephone Public Corporation) laboratory constructed a series of provably secure elliptic curve encryption systems: PSEC-1 (Variation 1 of PSEC, PSEC is a provably secure elliptic curve encryption system, is Shorthand for Provably Secure EllipticCurve encryption scheme), PSEC-2 (PSEC variant 2) and PSEC-3 (PSEC variant 3), if the elliptic curve determines the Diffie-Hellman problem ECDDHP (Elliptic Curve Decision Diffie-Hellman Problem) is difficult to solve, then PSEC-1 is IND-CCA2 safe; if the elliptic curve calculation Diffie-Hellman problem (ECCDHP) is difficult to solve, then PSEC-2 with filling is IND-CCA2 safe ; if ECCDHP is intractable and the symmetric encryption system is secure under passive attack, then PSEC-2 with symmetric encryption system is IND-CCA2 secure; if the elliptic curve Gap Diffie-Hellman problem (ECGDHP) is difficult Solution, then PSEC-3 is IND-CCA2 safe. They were all submitted to NESSIE, but because NTT subsequently proposed a key encapsulation mechanism based on PSEC - PSEC-KEM (PSEC Key Encapsulation Mechanism), PSEC-1 and PSEC-2 were withdrawn.

The above-mentioned ECIES system, PSEC-2 and PSEC-3 are all mixed encryption systems, that is, the system includes a symmetric encryption system, and its ciphertext size is three times, three times and four times the plaintext size respectively (assuming the symmetric encryption system The size of the plaintext is equivalent to the size of the ciphertext, and the output size of the hash function (Hash function) is equivalent to the security parameters, and the compression technology of elliptic curve points is used); although PSEC-1 does not require a symmetric encryption system, its security is based on the ECDDHP difficulty To solve this premise, if ECCDHP is solvable, then ECDDHP must be solvable, so this premise is not stronger than ECCDHP, and the security based on ECDDHP is not higher than that based on ECCDHP.

Contents of the invention

An object of the present invention is to provide a data encryption method, which has a new plaintext embedding method based on a pseudo-add operation, and adaptively selects a semantically secure elliptic curve under ciphertext.

Another object of the present invention is to provide a data decryption method, specifically to decrypt the encrypted data obtained by the above encryption method to obtain the original data before encryption.

When the sender sends data to the receiver, the data to be sent is encrypted according to the pseudo-encryption method:

First, randomly select an integer k, and the integer k satisfies: 1<k<n;

Then, calculate F(k), F(k)P, F(k)Q _A ; where: F(k) is the Hash function value of k, and F(k)P is F(k) times of the elliptic curve point P point, F(k) Q _A point F(k) times of elliptic curve point Q _A ; F(k) is a positive integer less than n, F(k)P and F(k)Q _A are both on the elliptic curve point;

Then further process the encrypted data according to the following formula:

m'=m||0 ^λ' , where m is the encrypted data, m' is the intermediate data formed during the encryption process, and λ' is the number of zeros to be added; λ' can be obtained in various ways, for example : Take one-third of the security parameter, etc.; the security parameter here refers to the quantitative description of the degree of security of the cryptographic algorithm itself, for example: 192 bits is a security parameter that is more secure than 1024-bit RSA;

Calculate G(k) again; if x(F(k)Q _A )=m'G(k), then re-select the integer k, repeat the above steps; otherwise start the step of calculating the ciphertext; wherein: G(k ) is the Hash function value of k; x(F(k)Q _A ) is the x coordinate value of the elliptic curve point F(k)Q _A ;

Finally, the ciphertext C is calculated according to the following formula:

C=(C ₁ , C ₂ )=(F(k)P, F(k)Q _A +(m'G(k), H(m'G(k))k));

Among them, the ciphertext C has two elements C ₁ and C ₂ ; C ₁ =F(k)P; C ₂ =F(k)Q _A +F(k)Q _A +(m′G(k), H(m'G(k))k);H(m'G(k)) is the Hash function value of m'G(k);

If the x-coordinate of C ₂ belongs to the set {m′G(k), x(F(k)Q _A )}, reselect the integer k and repeat the above steps; otherwise, output the ciphertext C.

In order to enable the party receiving the encrypted data to restore the encrypted data after receiving the data encrypted by the above encryption method, the present invention also provides a corresponding decryption method. For the ciphertext C, the specific decryption steps are as follows :

First, calculate Q'=d _A C ₁ , if x(Q')=x(C ₂ ), refuse to receive the ciphertext data; where, Q' is the elliptic curve point, d _A is the private key data of the decryption party, x(Q′), x(C ₂ ) are the x coordinates of Q′ and C ₂ respectively;

Then calculate (M, r)=C ₂ -Q′, if M=x(C ₂ ) or x(Q′), then refuse to receive the ciphertext data; where, M and r are respectively the values of a point on the affine plane x-coordinate and y-coordinate;

Further calculate f=H(M)r; wherein, H(M) is the Hash function value of M; if F(f)P=C ₁ , and the value of M's back λ' bit is 0, then the received plaintext m is the first λ-λ'bit of M; otherwise, it refuses to receive; among them, F(f)P is the F(f) times point of the elliptic curve point P; λ' is the number of 0s added in the encryption process; λ is the security parameter, which can basically be regarded as the length of the above M.

The present invention makes full use of the feature of pseudo-encryption, obtains a new plaintext embedding method, and obtains a semantically safe encryption system under adaptive chosen ciphertext attack, which is also the biggest difference between it and the traditional elliptic curve cryptosystem. The invention provides a very concise plaintext embedding method, and can verify the legitimacy of the ciphertext during decryption, thereby providing a higher level of data security. Compared with the existing encryption and decryption processing based on the elliptic curve, the encryption and decryption of data in the present invention has more secure semantics under the attack of adaptively chosen ciphertext.

Detailed ways

Below in conjunction with specific embodiment the present invention is described in further detail:

Before giving the specific encryption scheme, first give a description of the pseudo-add operation: on the affine plane F _P ² , two points with different x coordinates can uniquely determine the Weierstrass equation Y on the plane ² =X ³ +a ₄ X+a ₆ , where X and Y are variables, a ₄ and a ₆ are elements in the field F _p , and p is a large prime number. If the cubic curves they determine are elliptic curves, the coordinates of their addition points are completely determined by themselves.

The present invention utilizes this property to define a new operation: pseudo-addition.

Suppose P ₁ =(x ₁ , y ₁ ), P ₂ =(x ₂ , y ₂ ) are two points on the affine plane F _P ² , and x ₁ ≠x ₂ , the pseudo-add operation is defined as follows:

1. P ₁ +P ₂ =P ₃ =(x ₃ , y ₃ ) where x ₃ and y ₃ satisfy the following formula:

${\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}{{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 3</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}$

2. -P ₁ = (x ₁ , -y ₁ )

3. P ₁ -P ₂ =P ₁ +(-P ₂ )

Suppose P and Q are two points on the affine plane F _P ² , and the x coordinates are different, then P and Q uniquely determine an affine curve E(P, Q): Y ² =X ³ +aX+b, Let P, Q be the points on the affine curve, where a, b are elements of the field F _p , which are uniquely determined by points P and Q with different x coordinates, F _P is a finite field of p elements, and p is a prime number , and P is a point whose two coordinates are elements in F _P . Here, for all non-singular points on the curve E(P, Q), the point-multiplication operation is supplemented and defined, and the operation formula is exactly the same as the point-multiplication formula of the elliptic curve:

Suppose the curve E(P, Q): Y ² =X ³ +aX+b, P ₁ =(x ₁ ,y ₁ ) is a non-singular point on the curve, then 2P=(x ₃ ,y ₃ ), where :

x ₃ =λ ² -2x ₁

y ₃ =λ(x ₁ -x ₃ )-y ₁

$\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; =</span>\frac{{\mathrm{<span\; class="notranslate">\; 3</span>}\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; a</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}{\mathrm{<span\; class="notranslate">\; the\; y</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}}$

If 4a ³ +27b ² ≠0modp, then the curve is an elliptic curve. The pseudo addition operation "+" defined above is the addition of points on the elliptic curve. All rational points on the elliptic curve are under the "+" operation and point doubling operation form a group, the infinite point 0 is its zero point, and "-" is the inverse operation of "+"; if 4a ³ +27b ² =0modp, then the curve is singular, and there is only one singular point, all non- The singular point also forms a group under the "+" operation and the doubling operation, and the infinite point 0 is its zero point, and "-" is the inverse operation of "+".

From the nature of the operation, it can be seen that if and only if P and Q are all non-singular points on E(P, Q), and R(=P+Q), the x-coordinates of P and Q are different in pairs, it can be obtained without knowing P, in the case of the specific equation of the curve E (PQ) determined by Q, obtain Q (=R-P) by R (=P+Q) and P. Note that R, P, and the x coordinates of Q are different in pairs. P and Q are all non-singular points, so the probability that P and Q are all non-singular points is at least 1-6/(p-1), where p is a large prime number. That is to say: two x coordinates are not the same Point P, Q, note R=P+Q, can calculate another point by any two points wherein under 1-6/(p-1) probability.The present invention has fully utilized this characteristic, has obtained a new plaintext Embedding method, and obtain a semantically secure encryption system under adaptive chosen ciphertext attack, this feature is also the biggest difference between it and the traditional elliptic curve cryptosystem.

Suppose E: Y ² =X ³ +aX+b is an elliptic curve on a finite field F _p , E(F _p ) refers to the group composed of all rational points of F _p of E and 0. For any point P in E(F _p ), there exists the smallest integer n such that nP=0, n is called the order of point P, then point P can generate a cyclic group of order n. Most of the elliptic curve public-key cryptosystems are built on the cyclic group generated by the point whose order is a large prime number, which is called the base point. Unless otherwise specified below, uppercase letters are used to represent points on the curve, lowercase letters represent elements on a finite field, x(P), y(P) represent the x-coordinates and y-coordinates of point P, and between different points The addition of is the above-mentioned pseudo addition, and the doubling operation is the doubling operation defined on the elliptic curve.

Let the system parameters be (p, a, b, P, n), where p is a large prime number, which is determined by the required security strength, that is, the security parameter λ; a, b are the elements in the finite field F _p , where Determine an elliptic curve E: Y ² =X ³ +aX+b. P is an F _p- rational point of E with order n, where n is a large prime and is of the same size as p. Each user A has its own user parameters (SK _a , PK _a )=(d _a , Q _a ), where Q _a =d _a P, where d _a is a positive integer smaller than n, and d _a and Q _a are called User A's private key and public key. The public key is public and can be known by anyone, while the private key is private and only known by user A. H(.), F(.), G(.) are all Hash functions of {0, 1} ^λ → {0, 1} ^λ , λ' is any integer satisfying 1/2 ^λ' is a negligible function of λ , let λ'=λ/4 here. In the implementation of the system, in order to reduce the possibility of data out of bounds, the highest 8 bits of each Hash function value are forced to be 0.

If user B wants to send a message m ∈ {0, 1} ^λ-λ' to user A, then user B performs the following encryption operations:

First, randomly select an integer k, 1<k<n; then calculate the Hash function value F(k) of k, and record the F(k) times point F(k)P of the elliptic curve point P as C ₁ F(k) times point F(k)Q _a of Q _a ; then add λ′ 0s after m to get m′, that is, m′=m||0 ^λ′ ; then calculate the Hash function value G(k of k ), if the x-coordinate value of F(k)Q _a is x(F(k)Q _a )=m′G(k), return to reselect the integer k; finally, calculate the ciphertext C=(C ₁ , C ₂ )=(C ₁ , F(k)Q _a + (m′G(k), H(m′G(k))k), if the x coordinate of the affine plane point C ₂ belongs to the set{ m′G(k), x(F(k)Q _a )}, then return the reselected integer k; otherwise, output the ciphertext C.

After user A receives the ciphertext C sent by user B, the following decryption operation is performed to recover the plaintext m:

1. First, calculate the d _a times point d _a C ₁ of the elliptic curve point C ₁ and record it as Q', if x(Q')=x(C ₂ ), refuse to accept;

2. Then calculate the point C ₂ -Q′ on the affine plane and write it as (M, r), M, r are elements in the finite field F _p , if M=x(C ₂ ) or x(Q′) , refuse to accept;

3. Further calculate H(M)r and record it as f;

4. If the F(f) times point F(f)P of the elliptic curve point P is the elliptic curve point C ₁ and the last λ' bit of MG(f) is 0, then the received plaintext m is MG(f ) of the first λ-λ'bits; otherwise reject reception.

The following is a mathematical proof for obtaining high security by encrypting data using the present invention:

Assuming that the order of the elliptic curve group is approximately p, and half of m makes m ³ +am+b a quadratic residue modulo p, the following conclusions show that the probability of returning 1 in the encryption process is very small.

Lemma 1. For randomly chosen k and m, the probability of x(kQ _a )=m is at most 2/p.

Lemma 2. Note R=kP+(m, Hash(m)k), where, x(kP)≠m, then the probability of x(R)∈{m, x(kP)} is negligible.

Proof Assuming kP=(c,d), then d ² =c ³ +ac+b, c,d are completely determined by k. Hash(.) will be abbreviated as h(.) below. If x(R)=m, it can be obtained by the pseudo-addition formula:

$\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; =</span>{<span\; class="notranslate">\; (</span>\frac{\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&CirclePlus;</span>\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; d</span>}}{\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; c</span>}}<span\; class="notranslate">\; )</span>}^{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; c</span>}$

The d in the above formula can be replaced by using the relationship d ² =c ³ +ac+b to obtain the following formula:

(h(m)k) ⁴ +(h(m)k) ² (6m ² c-4m ³ +2ac+2b)-4(h(m)k)(c ³ +ac+b)

+4m ⁶ -12m ⁵ c-9m ² c ² -4m ³ (ac+b)+6m ² (ac+b)+a ² c ² +b ² +2abc＝0

If for a given k, the probability of the above formula is not negligible, it means that the Hash function h(.) satisfies the above formula with a non-negligible probability. Under the condition of k being fixed, for the Hash function value satisfying the above formula e, taking m as an unknown, the original image of e can be obtained by solving the sixth-order equation, that is, if the probability of the above formula is not negligible for a given k, then the Hash function h(.) does not satisfy the one-way property Therefore, for any k, the probability of the above formula being established is negligible, and the probability of x(R)=m is negligible. If x(R)=c, similarly we can get:

(h(m)k) ² +c ³ +ac+bm ³ -2m ² c+3mc ² ) ² ＝4(h(m)k) ² (c ³ +ac+b)

Because the Hash function h(.) is one-way, the probability of the above formula is also negligible. It is known from the above that the probability of x(R)∈{m, x(kP)} is negligible.

Above-mentioned lemma explanation: the probability that encryption process returns 1 is negligible, and encryption, decryption all only need the multiplication of two elliptic curve points and a false addition, so can think: the encryption method that this present invention adopts is effective , its rationality is obvious. Refer to the IEEE P1363 standard, if the point compression technique is used, the ciphertext generated by this system has three times the plaintext expansion, that is, the ciphertext size is three times the plaintext size.

Based on the fact that the pseudo-addition of two different points does not depend on the curve itself, the above method changes the plaintext embedding method in the ElGamal encryption system, that is, embedding m into the point (m′G(k), H(m′G (k))k)), instead of embedding it into a point on the elliptic curve determined by the system parameters. This makes plaintext embedding very natural and simple. In addition, the system also has the following characteristics: it can verify the legality of the ciphertext through the fourth step in the decryption process, which makes it very difficult to forge legal ciphertext (unless by choosing plaintext); it Different groups of elliptic curves are used to perform the operations. That is to say, in addition to the elliptic curve determined by the system parameters, there is also a curve determined by F(k)Q _a and (m′G(k), H(m′G(k)k), which is As m and k vary, unless user A's private key is known, it is impossible to know the elliptic curve group where the current operation is located.

The encryption time complexity of the above encryption system is 2 scalar multiplications, which is equivalent to the efficiency of the ElGamal system; the time complexity of decryption with verification is 2 scalar multiplications, which is one more scalar multiplication than the ElGamal system. Without validation, the efficiency is equivalent. If the point compression technique is used, it has 3 times the plaintext expansion. For the convenience of description, only the system under which the base domain characteristic is a large prime number is given here. When the characteristic is 2, the description of the pseudo-addition and the system is very similar.

The encryption system is a variant of the ElGamal system, and its security is based on the Elliptic Curve Computational Diffie-Hellman Problem (ECCDHP). It provides a very concise plaintext embedding method and can verify the validity of the ciphertext, thus providing a higher level of security. Under the random oracle model, it is proved that the encryption scheme is semantically secure under adaptively chosen ciphertext (IND-CCA2).

Under the random oracle model (random oracle model), it is proved that if the elliptic curve computing Diffie-Hellman problem (ECCDHP) is difficult to solve, then the encryption system is semantically secure under adaptive chosen ciphertext attack (IND-CCA2 ), since the proof is based on ECCDHP, its security may be higher than that of PSEC-1. It is not a hybrid encryption system, and its operations only include multiplication of elliptic curve points, pseudo-addition and hash functions, and do not need to apply a symmetric encryption system. The encryption system uses a new pseudo-add operation to embed the plaintext into the x-coordinate of the midpoint of the affine plane, which provides a very simple plaintext embedding method and can verify the legitimacy of the ciphertext.

In the implementation of this cryptographic system, the first thing to face is the selection of system parameters (p, a, b, P, n). From a security point of view, in order to resist some known attack algorithms, special restrictions can be placed on system parameters:

1.n>2 ¹⁶⁰ and $\mathrm{no}>4\sqrt{p};$

2. The elliptic curve is non-supersingular, that is, p does not divide p+1-#E(F _p );

3. The order n of the base point P is not divisible by p ^k -1 (1≤k≤C), and C=20 is usually taken in practice;

4. The elliptic curve is non-anomalous, that is, #E(F _p )≠p.

In this embodiment, the base field _Fp is the finite field suggested by the standard IEEEP1363, the Hash functions G(.), F(.) and H(.) are all SHA1 and the highest 8 bits of the Hash function value are forced to be 0, which is large The number of bits of the prime number p is λ. Randomly select the parameters a and b of the elliptic curve, use the SEA algorithm to calculate its order, and then use the elliptic curve that meets the above requirements as the system parameter. In the specific implementation of the present invention, elliptic curve point addition algorithm, pseudo-addition algorithm, elliptic curve point multiplication algorithm and scalar multiplication of elliptic curve points are required, and each algorithm is given below one by one.

Since the pseudo-addition algorithm is the same as the point-addition algorithm for two points with different x-coordinates on the elliptic curve, it is not listed separately.

In a specific embodiment of the present invention, the key generation process is as follows:

1. Randomly select an integer d _A , 1<d _A <n, and use NAF coding and scalar multiplication algorithm to calculate Q _A =d _A P;

2. Use d _A as the private key and Q _A as the public key.

The specific encryption steps are: divide the message data m into groups m ₁ m ₂ ...m _d according to 3λ/4, and encrypt one group at a time, for example: encrypt a grouped message m before transmitting.

2.1 Find the public key Q _A ;

2.2 Choose a random number k, 1<k<n;

2.3 Calculate f=SHA1(k);

2.4 Use NAF coding and scalar multiplication algorithm to calculate fP and mark it as C ₁ ;

2.5 Transform m into the element m'=m||0 ^λ/4 in the field;

2.6 Use NAF coding and scalar multiplication algorithm to calculate fQ _A and record it as Q', if x(Q') is equal to m'f, then execute 2.2;

2.7 Use point addition algorithm to calculate Q'+(m'f, SHA1(m'f)k) as C ₂ , if x(C ₂ ), x(Q') and m'f are different in pairs , then send encrypted data (C ₁ , C ₂ ), otherwise, return 2.2.

Decryption process: After receiving encrypted data (C ₁ , C ₂ ), implement the following decryption process:

3.1 Use NAF coding and scalar multiplication algorithm to calculate point Q'=d _A C ₁ , if x(Q') is equal to x(C ₂ ), refuse to accept;

3.2 Use point addition algorithm to calculate (M, r) = C ₂ -Q', if M is equal to x(C ₂ ) or x(Q'), refuse to accept;

3.3 Calculate k=SHA1(M)r;

3.4 Calculate f=SHA1(k);

3.5 Calculate m'=Mf

3.6 NAF coding and scalar multiplication algorithm are used for calculation. If fP is equal to C ₁ and the last λ/4 bits of m' are 0, the received plaintext m is the first 3/4 bits of m'; otherwise, it is rejected.

The above point addition algorithm is as follows:

When encrypting a piece of data, for the input elliptic curve y ² =x ³ +ax+b, and the point P ₀ =(x ₀ ,y ₀ ) and the point P ₁ =(x ₁ ,y ₁ );

A1. If P ₀ =0, the output point P ₂ is P ₁

A2. If P ₁ = 0, the output point P ₂ is P ₀

A3. If x ₀ ≠ x ₁

A3.1 Calculate λ←(y ₀ -y ₁ )/(x ₀ -x ₁ )mod p; it means assigning (y0-y1)/(x0-x1)mod p to λ;

A3.2 Execute step A7

A4. If y ₀ ≠y ₁ , output P ₂ ←O

A5. If y ₀ =0, output P ₂ ←O

A6. Calculate λ←(3x ² +a)/(2y ₁ ) mod p

A7. Calculate x ₂ ←λ ² -x ₀ -x ₁ mod p

A8. Calculate y ₂ ←(x ₁ -x ₂ )λ-y ₁ mod p

A9. Output P ₂ ←(x ₂ , y ₂ )

Note: To subtract point P=(x, y), just add point -P=(x, -y).

The algorithm for doubling points on the elliptic curve above is as follows:

Input: elliptic curve E, point P(X ₁ , Y ₁ , Z ₁ ) on E, P≠O

Output: (X ₃ , Y ₃ , Z ₃ )=2P

B1. Calculate λ ₁ ←3X ₁ ² +aZ ₁ ⁴ ;

B2. Calculate Z ₃ ← 2Y ₁ Z ₁

B3. Calculate λ ₂ , ←4X ₁ Y ₁ ² ;

B4. Calculate X ₃ ←λ ₁ ² -2λ ₂ ;

B5. Calculate λ ₃ ←8Y ₁ ⁴ ;

B6. Calculate Y ₃ ←λ ₁ (λ ₂ -X ₃ )-λ ₃ ;

B7. Output (X ₃ , Y ₃ , Z ₃ )

The above NAF encoding algorithm is as follows:

input: integer $k={\mathrm{\&Sigma;}}_{j=0}^{l-1}{k}_j{2}^j,k_j\&Element;\left\{\mathrm{0,1}\right\}.$

Output: NAF $k={\mathrm{\&Sigma;}}_{i=0}^l{\mathrm{the\; s}}_i{2}^i,{\mathrm{the\; s}}_i\&Element;\{-\mathrm{1,0,1}\}$

C1, c ₀ ←0, k _l ←0, k _l+1 ←0;

C2, j←0

C3. If j≠l+1

C3.1 Calculation

C3.2 Calculate s _j ←k _j +c _j -2c _j+1

C3.3 Calculate j=j+1

C3.4 Go to Step 3

C4, output (s _l s _l-1 , ..., s ₁ , s ₀ ) ₂

The above NAF scalar multiplication algorithm is as follows:

Input: a point P on the elliptic curve, NAF(s _l s _l-1 ,..., s ₁ , s ₀ ) ₂ of integer k, s _l =1;

Output: Q=kP;

D1, Q←O;

D2, j←l;

D3. If j≠-1

D3.1 Calculate Q←2Q

D3.2 If s _j = 1, calculate Q←Q+P

D3.3 If s _j = -1, calculate Q←Q+P

D3.4 Calculate j=j-1

D3.5 Go to step 3

D4, output Q.

The above algorithms provide the specific implementation of the elliptic curve encryption system described in the present invention, and a set of experimental data obtained by running in this mode is given below, wherein each data is expressed in hexadecimal notation.

System parameters:

Lambda: 192

p: ffffffffffffffffffffffffffffffffffffffffffffffff

a: ffffffffffffffffffffffffffffffffffffffffffffffc

b: 02d5134233c1f7f4f50706f02882d85e767294c7230612c2

P.x: df00000129200001db000001ffbe800169ea40011de3ec01

P.y: 46b19ab9a84501afc6c94ce6fb9ae8f21a93fedb9ec6881f

n: fffffffffffffffffffffffe75432f994b9b16ef54c39393

d _A : 83cedad356f4f6cf573ff873b789add938df2ec7d5d2753b

Q _A.x : 1f18bcacb74087835ae629a87968f0d57adb39110ec1fd70

Q _A .Y: 53b96505a207de2442510c7f01c80c4cffcdaf40099fa0a1 when encrypted:

m: 000000000000000000313233343536373839

m': 00000000000000000313233343536373839000000000000

k: 9296decb12fc6d896ffd58ade5b03a3f1e235d0556e3f57d

f: 09cf3ae17aad817332dd1e4fe8d41c50d8b7ee7152ac5b6

_C1.x : 362b32f9f9b3c21c1df13631ea7155f23d04d4853ce048db

_C1.y : f7cbaa643bccce14f252660b0104542f86a8a5f89f7c1c5

fQ _A.x : fa529d8354bbb6bd3289b906f1b3337914628f6cf75a354c

fQ _A.y : 91f142b803c9ba20ece5012f02bc9511cb4412b881bbbd7a

m’f: 09cf3ae17aad817331ce3d7cab877f235b27ee7152ac5b6

SHA1(m'f)k:

92d183184e2365cc9b2673ddc3f49bf2a3c57cb6b5c3ea36

C _2.x : 6edaa4c686f938464514b379720f10dd4ba8a353e1a9e6de

C _2.y : 2f47f3be8875cc0417fbfacf87993ea4893595ddf610b43 after decryption:

Q′.x: fa529d8354bbb6bd3289b906f1b3337914628f6cf75a354c

Q′.y: 91f142b803c9ba20ece5012f02bc9511cb4412b881bbbd7a

M: 09cf3ae17aad817331ce3d7cab877f235b27ee7152ac5b6

r: 92d183184e2365cc9b2673ddc3f49bf2a3c57cb6b5c3ea36

SHA1(M): 0475dd35cdf0845f4db2b702644a1cdbde621b3e3201f4b

k: 9296decb12fc6d896ffd58ade5b03a3f1e235d0556e3f57d

f=SHA1(k):09cf3ae17aad817332dd1e4fe8d41c50d8b7ee7152ac5b6

m’f: 0000000000000000000313233343536373839000000000000

fP.x: 362b32f9f9b3c21c1df13631ea7155f23d04d4853ce048db

fP.y: f7cbaa643bccce14f252660b0104542f86a8a5f89f7c1c5

m: 000000000000000000313233343536373839;

Use INTEL company PentiumIV 1.7G microprocessor, the computer of 256M memory, and under the environment of WINDOWS98 operating system, realize the system on the finite field that is p and characteristic is 2 with ANSIC programming language, wherein p=2 ¹⁹² -2 ⁶⁴ +1, F _2m , m=193, generating polynomial f(x)=x ¹⁹³ +x ¹⁵ +1; the realization efficiency is shown in the following table: content *F _p F _p *F _2m F _2m key generation 1.21 5.43 0.67 2.48 encryption 6.70 10.95 3.29 5.43 ECES encryption 6.76 10.53 3.20 5.26 decrypt 6.50 11.57 3.12 5.42 Decrypt (without verification) 5.26 5.95 2.59 2.45 ECES decryption 5.51 5.48 2.62 2.53 multiply 1.20 5.32 0.65 2.39

The indicators in the table are executed at the speed of 1000 times, and the unit is second; the indicators under the * column are the allowable preprocessing speeds.

If the operation on F _p is written in assembly language, the multiplication speed of 192-bit points is 1.81 seconds (1000 times), and the following table lists the speed of executing 1000 times under p= ²²⁵⁶ , and the unit is second: content ANSI C compilation key generation 2.25 0.93 encryption 18.93 6.35 decrypt 18.64 6.35 Decrypt (without verification) 16.2 5.43

The encryption/decryption efficiency realized by MCS51 single-chip microcomputer is shown in the following table. The main memory configuration of MCS51: 256B internal RAM, 64KB external RAM, 64KB program area ROM. Clock frequency: 1M clock cycle/second (crystal oscillator Frequency: 12MHZ). Taking F _p , p=2 ¹⁹² -2 ⁶⁴ -1 and F _2m , m=193, the generator polynomial is x ¹⁹³ +x ¹⁵ +1. Function F _p (sec/time) F _2m (sec/time) key generation 4.89 4.34 encryption 25.32 20.84 ECES encryption 25.19 20.74 Decrypt (without verification) 20.43 16.21 ECES decryption 20.42 16.21 Decryption (with storage) 25.33 20.10 Multiplication (with pre-stored) 4.77 4.32 Multiplication (without pre-store) 19.96 16.4

Note: F _p ’s external RAM occupies 1.5K, ROM occupies 9K programs, 6K pre-stored values; F _2m ’s external RAM occupies: 2K (with pre-stored)/1.2K (without pre-stored), ROM occupies: 7K programs, 6K pre-stored values.

In the following, a detailed proof that the encryption scheme is semantically secure under adaptively chosen ciphertexts is given.

1. Definition of security

Assuming that U is a probability algorithm, then A(x ₁ , x ₂ ,...;r) represents the output of algorithm A when the input is x ₁ , x ₂ ,..., and the random number is r; y←A(x ₁ , x ₂ ,...) means to choose r randomly, let y be equal to A(x ₁ , x ₂ ,...; r); if r exists so that A(x ₁ , x ₂ ,...; r) =y, then y is said to be the output of A(x ₁ , x ₂ ,...); if S is a finite set, then x←S means that x is randomly selected from the set S according to a uniform distribution; if a is neither A set is not an algorithm, then x←a means to assign the value of a to x.

Definition 1. The public key encryption system is a triplet composed of algorithms: PE=(KG, Enc, Dec), where

KG: key generation algorithm, which is a probabilistic algorithm, the input is a security parameter 1 ^λ (λ∈N), and the output is a pair of public and private keys (pk, sk);

Enc: Encryption algorithm, which is a probabilistic algorithm, the input is the public key pk and the plaintext x∈{0, 1} ^* , and the output is the ciphertext y;

Dec: decryption algorithm, which is a deterministic algorithm. The input is the private key sk and the ciphertext y, and the output is the plaintext x∈{0, 1} ^* or the special character , which indicates that the input ciphertext is not a valid ciphertext, that is There is no x ∈ {0, 1} ^* such that its ciphertext is y.

For any public-private key pair (pk, sk) obtained by the key generation algorithm and any plaintext x∈{0, 1} ^* , if y is the output of Enc _pk (x), there must be Dec _sk (y) =x. Because the public key encryption system needs to ensure the security of the information transmitted in reality, the above three algorithms (KG, Enc, Dec) are all polynomial time algorithms based on security parameters.

The definition of the security of the public key encryption system can first consider the attacker's possible attack goals (goals) and possible attack model (attack model), and then give the definition of various levels of security by combining the attack model and attack goals .

According to different attack targets, the security analysis of the system mainly considers one-way (OW, oneway), semantic security (SS, semantic security), indistinguishability of ciphertext (IND, indistinguishability of encryptions) and non-extensibility (non-extensibility). -malleability, NM). Simply put, one-way means that it is very difficult to obtain the corresponding plaintext x=Dec _sk (y) from the target ciphertext y; semantic security means that any information about the corresponding plaintext x obtained from the target ciphertext y is uncomputable Yes; the indistinguishability of ciphertext means that two plaintexts and a ciphertext corresponding to a certain plaintext are known, and it is impossible to determine which plaintext corresponds to the ciphertext. It can be considered that both the indistinguishability of ciphertext and semantic security are the promotion of the concept of one-way, and they are all covered in the traditional confidentiality requirements. One-way is the minimum requirement for encryption system security. If the system is indistinguishable from ciphertext or semantically secure, the system must be unidirectional, so this paper does not discuss any unidirectional properties. Non-extensibility refers to obtaining another different ciphertext y' from the target ciphertext y, so that there is a "meaningful connection" between the corresponding ciphertext x and x' (such as x'=x+1), it It improves the idea of anti-tampering of ciphertext in reality.

The attack model describes the capabilities of the attacker, which can be divided into chosen-plaintext attack (CPA), non-adaptive chosen-ciphertext attack (CCA1) and adaptive chosen-ciphertext attack ( adaptive chosen-ciphertext attack, CCA2). CPA gives the attacker the right to freely choose the plaintext and obtain the corresponding ciphertext. For the public key encryption system, the attacker has the ability to choose the plaintext attack if he knows the public key; the formal definition of CCA1 was developed by two scholars Naor and Yung Given, where the attacker has access to the decryption oracle (the external device is the decryption algorithm) in addition to knowing the public key, but the attacker only has the right to access the decryption oracle before getting the target ciphertext (non-adaptive is Refers to the access to the decryption oracle does not depend on the target ciphertext), according to its characteristics, non-adaptive chosen ciphertext attack is also called midnight attack (midnight attack) or lunch attack (lunchtime attack, Lunch-break attack); CCA2 is developed by Proposed by two scholars, Rackoff and Simon, in which the attacker knows both the public key and can access the decryption oracle, and his access to the decryption oracle is unlimited, even after obtaining the target ciphertext, the attacker can still access the decryption oracle but he cannot use the target ciphertext itself as input to the decryption oracle (adaptive means that access to the decryption oracle depends on the target ciphertext).

Combining the above-mentioned attack targets and attack models, various definitions of security can be obtained, and only the formal definition of indistinguishability is given below, which includes the highest level of security-semantic security under adaptively chosen ciphertext IND-CCA2.

According to the fact that the attacker U has different inputs at different stages, it can be regarded as two probabilistic algorithms (U ₁ , U ₂ ), where the roles of U ₁ and U ₂ depend on the goals of the attacker. In the definition of indistinguishability of ciphertext, the input of algorithm U ₁ is pk, the output is (x ₀ , x ₂ , s), the first two terms are two plaintexts of the same length, s is what the attacker wants to keep Information; Randomly select a ciphertext from x ₀ , x ₁ marked as x _b , challenge ciphertext y is x _b , the input of algorithm U ₂ is (x ₀ , x ₁ , s) and challenge ciphertext y It tries to Output the correct b.

Definition 2 (IND-CPA, IND-CCA1, IND-CCA2). Suppose PE=(KG, Enc, Dec) is a public key encryption system, A=(A ₁ , A ₂ ) is an attacker, H(. ) is a random oracle, for any atk∈{cpa, cca1, cca2} and any λ∈N, let

${\mathrm{<span\; class="notranslate">\; Adv</span>}}_{\mathrm{<span\; class="notranslate">\; PE</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; A</span>}}^{\mathrm{<span\; class="notranslate">\; ind</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; atk</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Ex</span>}{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; PE</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; A</span>}}^{\mathrm{<span\; class="notranslate">\; ind</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; atk</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; E.</span>}{\mathrm{<span\; class="notranslate">\; xp</span>}}_{\mathrm{<span\; class="notranslate">\; PE</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; A</span>}}^{\mathrm{<span\; class="notranslate">\; ind</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; atk</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; ]</span>$

Where b∈{0, 1} is taken, and the experiment Exp _{PE is defined, A} ^ind-atk-d (λ) is

$<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; pk</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; sk</span>}<span\; class="notranslate">\; )</span>\stackrel{\mathrm{<span\; class="notranslate">\; R</span>}}{<span\; class="notranslate">\; \&LeftArrow;</span>}\mathrm{<span\; class="notranslate">\; KG</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; \&lambda;</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ;</span>$

$<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&LeftArrow;</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}^{{\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; pk</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ;</span>$

y←Enc _pk (x _b );

$\mathrm{<span\; class="notranslate">\; d</span>}<span\; class="notranslate">\; \&LeftArrow;</span>{\mathrm{<span\; class="notranslate">\; A</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}^{{\mathrm{<span\; class="notranslate">\; o</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; )</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; (</span><span\; class="notranslate">\; \&CenterDot;</span><span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; s</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; the\; y</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; ;</span>$

Return d.

If atk=cpa, then O ₁ (.)=, O ₂ (.)=; if atk=cca1, then O ₁ (.)=Dec _sk (.), O ₂ (.)=; if atk =cca2, then O ₁ (.)=De _sk (.), O ₂ (.)=Dec _sk (.); also requires |x ₀ |=|x ₁ |, algorithm A ₂ cannot use decryption oracle to obtain y plaintext. If there is Exp _{PE for any attacker A in polynomial time, and A} ^ind-atk (·) is a negligible function, then the public key encryption system PE is said to be secure in the sense of IND-ATK.

2. Safety Analysis

From the point of view of the system itself, because the operation of the present invention is based on different elliptic curve groups, and "+" hardly has associative law (for example: three points P=(1,2) on the affine plane R ² , Q=(2, 3), R=(3,1), get (P+Q)+R=(-2,1)+(3,1)=(-1,-1) by the false addition formula, and P+(Q+ R)=(1,2)+(-1,-9)=(121/4,-1303/8).), so it is very difficult to obtain the ciphertext of R(m) from the ciphertext of m, where R is a non-trivial relation, that is, intuitively, the system has a non-expandable property, which is the most obvious difference from the ElGamal system, and it is also a reason for the improved security. The use of the Hash function further strengthens the security of the system. This section will prove that the scheme is IND-CCA2 secure. For convenience, the encryption system is abbreviated as ∏ below.

Theorem 1. Under the condition of ECCDHP intractability, Π is IND-CCA2 safe.

Proof Assuming that ∏ exists in the sense of IND-CCA2, the attacker A=(A ₁ , A ₂ ), the corresponding records obtained by A accessing the random oracle G(.), H(.) and F(.) are respectively called G - table, H-table and F-table, recorded as τ _G ={(g _i , G _i )}, τ _H ={(h _i , H _i )}, τ _F ={(f _i , F _i ) } Its length (the number of visits) is represented by q _G , q _H , and q _F respectively. Then the solution algorithm B of ECCDHP can be constructed as follows. Suppose the input of B is P, Q=aP, Y=bP, and its purpose is to calculate R=abP.

B uses P and Q as the input of A ₁ to call A ₁ , since A ₁ can access the random oracle and the decryption oracle, B needs to simulate the random oracle and the decryption oracle. Let A ₁ query g from the random oracle G(.), if g is in the query record, then use the corresponding output value in the record as the answer to A; otherwise, randomly select the number in its value range as the answer to A ₁ Answer, and add k and the random number as a pair of input and output to the record at the same time. B simulates random oracles H(.) and F(.) in the same way as it simulates G(.). Let A ₁ access y=(C ₁ , C ₂ ) to the decryption oracle, if (g _i , G _i ), (f ₁ , F ₁ ), ( h _j , H _j ), satisfy f ₁ = g _i , F ₁ P = C ₁ , C ₂ = F ₁ Q+(h _j , H _j f ₁ ), calculate M=h _j G _i , if M If the low λ' bit is 0, the high λ-λ' bit of M is output as plain text, and in other cases, an empty string  is output. When A ₁ is suspended, it is advisable to set the output of A ₁ as (m ₀ , m ₁ , s).

B randomly selects C ₂ ^* ∈ {0, 1} ^2λ , let y ^* = (C ₁ ^* = Y, C ₂ ^* ), B takes (m ₀ , m ₁ , s, y ^* ) as the input of A ₂ , Call A ₂ , the process of simulating the decryption oracle and the random oracle is the same as above.

After A terminates, B randomly selects (h, H) from the H-table, if there is t such that R=C ₂ ^* -(h, t)∈E, then output R; otherwise, select from the H-table again (h, H); if the above relation does not exist in the H-table, then randomly output the point of E as R.

F*=log _P Y, (s*, t*)=C ₂ ^* -F*Q, h*=s*, k*=t*H(h*) are written below. Using the equation of E and the pseudo-additive formula, it can be known that C ₂ ^* -(h, t)∈E is a sextic equation about t, which has at most six solutions, let AskH represent an event: A visits h to H(.) *, then the probability that B outputs the correct ECDH solution ${\mathrm{\&epsiv;}}^{\&prime;}\&Greater\; Equal;\frac{\mathrm{PR}\left[\mathrm{Ask\; H}\right]}{{6q}_h}.$

In order to ensure the correct invocation of A, firstly, B must correctly simulate the decryption oracle, and secondly, B must ensure that the target ciphertext y ^* is legal. Bad indicates that the response to the decryption oracle is wrong or y ^* is not a valid ciphertext. Suppose the probability of A's success is (1+ε)/2, if B calls A correctly, because y ^* has nothing to do with m ₀ and m ₁ , so the probability of A outputting the correct result is 1/2, then

(1+ε)/2≤1/2(1-Pr[Bad])+Pr[Bad],

It can be obtained that Pr[Bad]≥ε. obviously

Pr[AskH]≥Pr[AskH∧Bad]＝Pr[Bad]-Pr[Bad∧﹃AskH]≥ε-Pr[Bad|﹃AskH]

On the premise of not accessing h* to H(.), only when A visits k* (denoted as AskK) to G(.) or F(.) or the answer of the decryption oracle is wrong (denoted as DBad) , Bad may occur, namely

Pr[Bad|‘AskH]≤Pr[AskK|‘AskH]+Pr[DBad|‘AskH∧AskK]

If h* is not visited, then H(h*) is completely random, so k*=t*H(h*) is completely random, so the probability of k* being visited is not greater than (q _G +q _F )/2 ^λ ,Right now

$\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Ask\; K</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&Not;</span>\mathrm{<span\; class="notranslate">\; Ask\; H</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; G</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}}{{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}}<span\; class="notranslate">\; .</span>$

The following discussion is based on the precondition that k* and h* are not visited.

Assuming that the input of A to the decryption oracle is y(C ₁ , C ₁ ), record F=logPC ₁ , (s, t)=C ₂ -FQ, k=H(s)t, h=s, Pr' [.]=Pr[·|“AskH∧“AskK].

If both h and k are queried, the output result must be correct; if h is queried but k is not queried from G(.) or F(.), the output result is an empty string. If the result is not true, then y must be legal The ciphertext is discussed in the following cases: because h is queried, k is determined, and k* is random, so the probability of k=k* is not greater than 2 ^-λ , and the probability of y being a legal ciphertext under the condition of k=k* It is at most 1, then when k=k*, the error probability of the simulated answer is not greater than 2 ^-λ ; if k≠k* and k does not visit G(.), y is legal ciphertext means sG(k) The low λ' bit of y is 0, because k≠k* and k has no access to G(.), so the probability that y is a legal ciphertext is not greater than 2 ^-λ' ; if k≠k* and k has no access to F(. ) access, y is legal ciphertext means F(k)=log _p C ₁ , because k≠k* and k has no access to F(.), so the probability of y being legal ciphertext is not greater than 2 ^-λ ; if h has not been queried, the output result is an empty string, if the result is not true, then y must be a legal ciphertext, that is, F(k)=log _P C ₁ and the low λ' bit of sG(k) is 0, If h=h*, because h* has not been queried, so H(h) is completely random; if k≠k*, because h has not been queried, so H(h) is completely random; so there is no condition for h to be queried , H(h) is completely random, then k=tH(h) is completely random, so the probability of F(k)=log _P C ₁ is not greater than 2 ^-2 , sG(k) If the probability that the low λ' bit is 0 is not greater than 2 ^-λ' , then under the condition that h is not accessed, the probability of an error in the simulated response is not greater than 2 ^-λ .

Based on the above analysis, we can know that Pr[DBad|﹃AskK∧﹠AskH]≤3q _D /2 ^λ +q _D /2 ^λ , then

$\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Bad</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&Not;</span>\mathrm{<span\; class="notranslate">\; Ask\; H</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&le;</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; G</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 3</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; 2</span>}}^{{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}}$

$\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Ask\; H</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Bad</span>}<span\; class="notranslate">\; |</span><span\; class="notranslate">\; \&Not;</span>\mathrm{<span\; class="notranslate">\; Ask\; H</span>}<span\; class="notranslate">\; ]</span><span\; class="notranslate">\; \&Greater\; Equal;</span>\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; G</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 3</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}}<span\; class="notranslate">\; +</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; 2</span>}}^{{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}}<span\; class="notranslate">\; )</span>$

Therefore, the probability that B outputs the correct ECDH solution

${\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}<span\; class="notranslate">\; \&Greater\; Equal;</span>\frac{\mathrm{<span\; class="notranslate">\; PR</span>}<span\; class="notranslate">\; [</span>\mathrm{<span\; class="notranslate">\; Ask\; H</span>}<span\; class="notranslate">\; ]</span>}{{\mathrm{<span\; class="notranslate">\; 6</span>}\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}}<span\; class="notranslate">\; \&Greater\; Equal;</span>\frac{\mathrm{<span\; class="notranslate">\; \&epsiv;</span>}}{{\mathrm{<span\; class="notranslate">\; 6</span>}\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; G</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 3</span>}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; 6</span>}\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}^{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}}<span\; class="notranslate">\; -</span>\frac{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; D.</span>}}}{{\mathrm{<span\; class="notranslate">\; 6</span>}\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; h</span>}}{\mathrm{<span\; class="notranslate">\; 2</span>}}^{{\mathrm{<span\; class="notranslate">\; \&lambda;</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}}$

From the above formula, if ε is non-negligible, then ε′ must be non-negligible, and if the running time of A is t, then the running time of B is t′=t+q _H t _f , where t _f is expressed in F The time required to solve the sextic equation on _p , obviously if A is polynomial time, then B must also be polynomial time. From the above, if Π is not IND-CCA2 safe, then ECCDHP can be solved, which is contradictory, so Under the ECCDHP-hard condition, Π is IND-CCA2 safe.

Finally, it should be noted that: the above embodiments are only used to illustrate the present invention rather than limit the technical solutions described in the present invention; Those of ordinary skill in the art should understand that the present invention can still be modified or equivalently replaced; and all technical solutions and improvements that do not depart from the spirit and scope of the present invention should be covered by the claims of the present invention.

Claims (2)

1. A method of data encryption, characterized by: when a sender sends data to a receiver, encrypting the data to be sent according to a pseudo-encryption method; the encryption processing steps are as follows:

step 10: randomly selecting an integer k, wherein the integer k satisfies the following conditions: k is more than 1 and less than n; wherein n is the order of the base point of the elliptic curve;

step 11: calculating F (k), F (k) Q_A(ii) a Wherein:

f (k) is the Hash function value of k, F (k) P is the F (k) times point of the elliptic curve point P, F (k) Q_AIs an elliptic curve point Q_AF (k) times the point of (a);

f (k) is a positive integer less than n, F (k) P and F (k) Q_AAll points are points on an elliptic curve;

step 12: the encrypted data is processed according to the following formula:

m’＝m||0^λ’wherein

m is the encrypted data, m ' is the data in the encryption process, λ ' is the number of 0's to be added;

step 13: calculating G (k); if x (F (k) Q_A) M'  g (k), go to step 10; otherwise, executing step 14;

wherein: g (k) is the Hash function value of k;

x(F(k)Q_A) Is an elliptic curve point F (k) Q_AX coordinate value of (a);

step 14: ciphertext C is calculated according to the following formula:

C＝(C₁，C₂)＝(F(k)P，F(k)Q_A+(m′G(k)，H(m′G(k))k))；

wherein C is a ciphertext data set, C₁And C₂Two elements which are C; and,

C₁＝F(k)P；

C₂＝F(k)Q_A+F(k)Q_A+(m′G(k)，H(m′G(k))k)；

h (m ' G (k)) is the Hash function value of m'  G (k);

step 15: if C is present₂Belongs to the set { m'  G (k) }, x (F (k) Q_A) Executing step 10; otherwise, the ciphertext C is output.

2. A method of decrypting data encrypted according to the method of claim 1, characterized by: when the receiving party receives the encrypted ciphertext data of the sending party, the receiving party decrypts the ciphertext data according to the following method and restores the encrypted data into data; the decryption steps are as follows:

step 20: calculating Q' ═ d_AC₁If x (Q') isequal to x (C)₂) Refusing to receive the ciphertext data; wherein,

q' is an elliptic curve point, d_AIs the private key data of the decryptor, x (Q'), x (C)₂) Are respectively Q' and C₂X coordinate of (a);

step 21: calculating (M, r) ═ C₂-Q', if M ═ x (C)₂) Or x (Q'), refusing to receive the ciphertext data; wherein M, r are the x-coordinate and the y-coordinate of a point on the affine plane, respectively;

step 22: calculating f ═ h (m)  r; wherein H (M) is the Hash function value of M;

step 23: if F (f) P ═ C₁And the rear lambda 'bit value of M is 0, the received plaintext M is the front lambda-lambda' bit of M; otherwise, refusing to receive;

wherein F (f) P is F (f) times the elliptic curve point P;

λ 'is the number of 0's added in the encryption process;

λ is a safety parameter.