CN1245695C - Type II public pin and code system based on level function - Google Patents

Abstract

The present invention relates to a public key code system designed by a lever function and a super increasing sequence, which belongs to the fields of a cryptography and a computer science. The public key code system comprises a key generation module, a coding module and a decoding module. A user obtains two code keys from the third party authority mechanism, one key is only private, the other is public, and a public key can not push out a private key; the public key is used for converting plain text into coding text, and the private key is used for reducing the coding text back to the plain text; the system can resist minimal point attack of Shamir and L<3> reduced basis attack of LOB effectively, and the present invention is used for coding and decoding any files and data in a computer network and a communication network.

Description

A kind of key encrypt method based on lever function and super increasing sequence

(1) technical field

Public key encryption method (abbreviation key encrypt method) belongs to cryptography and computer science and technology field.The public key encryption method comprises two keys, and one is public-key cryptography, is called for short PKI, and one is private cipher key, is called for short private key.

(2) background technology

1976, American scholar Whitfield Diffie and Martin Hellman proposed the thought of " public key cryptosystem " first.Based on this thought, more existing at present concrete realization technology mainly comprise: (1) MH knapsack public key cryptosyst; (2) RSA public key cryptosyst; (3) Pohlig-Hellman public key cryptosyst; (4) Rabin public key cryptosyst; (5) ElGamal public key cryptosyst, the ECC public key cryptosyst also is in its realization on elliptic curve; (6) McEliece public key cryptosyst; (7) LUC public key cryptosyst; (8) finte-state machine common key cryptosystem (said system can be referring to " applied cryptography ", and U.S. BruceSchneier is outstanding, and Wu Shizhong, Zhu Shixiong etc. translates, China Machine Press, in January, 2000).

In the said system, first kind to the 7th kind is that the foreigner invents, most of patent applied for, and wherein, the ElGamal system on RSA system and the elliptic curve is widely used.At last a kind of is that Chinese scholar professor Tao Renji proposes.

(3) summary of the invention

The present invention can be used for the encryption and decryption of various files such as character, literal, figure, pictures and sounds and data in computer network and the communication network, to guarantee the privacy of file and data storage and transmission.Wish that our country can have the core technology of oneself in the public key cryptography field, with information security and the economic security of guaranteeing China.

3.1 two key concepts

3.1.1 super increasing sequence

If A ₁, A ₂..., A _nBe n mutually different positive integer, and satisfy

A _i＞∑A _j(i＝2，3，…，n；j＝1，2，…，i-1)

Claim that then such positive integer sequence is a super increasing sequence, be designated as { A ₁, A ₂..., A _n) or { A _i).

Super increasing sequence has following character: (1≤m≤n) is from super increasing sequence { A for positive integer m arbitrarily _i) in optional m, this m add up and (be subclass with) then: $E_S=A_{i_1}+A_{i_2}+\&CenterDot;\&CenterDot;\&CenterDot;+A_{i_m}$ Be well-determined.

3.1.2 lever function

If f (i) is by the injective function of integer to integer, i ∈ 1,2 ..., n}.

Its functional value f (1), f (2) ..., f (n) is n different positive integer.In this encryption method, when from PKI derivation private key or ciphertext, need to consider f (i) full number of permutations n! But when private key is untied ciphertext, only need consider f (i) add up and.Therefore, as if being fulcrum with the ciphertext, then f (i) is that an end calculated amount is big, and other end calculated amount is little.The f (i) that we claim to satisfy this character is a lever function.

3.2 technical scheme

The present invention is a kind of public key encryption method based on lever function and super increasing sequence, be called for short the REESSE2 key encrypt method, the password product of producing according to it can be the deciphering chip that pure DLC (digital logic circuit) is made, perhaps add the deciphering chip that the curing program is made, perhaps cipher machine of forming by computer hardware and software etc. by DLC (digital logic circuit).Therefore, the present invention is a kind of exploitation cryptographic system or product mandatory ultimate principle of institute and technical scheme, rather than physical product itself.

This key encrypt method is made up of three parts such as key generation, encryption and decryption.

3.2.1 encrypt and decrypt pattern of the present invention

Suppose that user V desire sends a file or data by network to user U, and carry out in the mode of maintaining secrecy.Encrypting file before or data, encrypt file afterwards or data herein, ciphertext expressly.User V and user U desire realize so secret communication process, and its pattern is as follows:

Key generates: at first, user U should go to the 3rd side authoritative institution (ca authentication center or digital certificate center) to get a pair of private key (Private Key) and PKI (Public Key) that is generated parts output by key, private key must must not be divulged a secret by user U oneself keeping; PKI then allows openly to provide to the external world with the form of public key certificate, so that use.

Cryptographic operation: user V obtains the public key certificate of user U from the ca authentication center, the plaintext that on the machine of operation encryption unit desire is sent is encrypted, and obtains ciphertext, and by network ciphertext is sent to user U.

Decryption oprerations: after user U receives the ciphertext that user V sends, on the machine of operation deciphering parts, ciphertext is decrypted, recovers plaintext with own private key.

In key encrypt method, in order to improve the efficient of encryption, adopt the mixed cipher technology usually, promptly come encrypting plaintext with DSE arithmetic, come encrypted session key with public-key cryptosystem again.Employed encryption key of DSE arithmetic and decruption key are same key in essence, are called as session key.

3.2.2 key generating portion

The key generating portion is used for the ca authentication center, is used for producing a pair of private key and PKI.Its implementation is:

(1) produces the super increasing sequence { A that item number is n at random ₁, A ₂..., A _n}

(2) find a positive prime number M, it satisfies $M>\left({\mathrm{\&Sigma;}}_{i=1}^n{A}_1\right),$ And (n/log ₂M)＞0.645

(3) produce at random different in twos functional value f (1), f (2) ..., f (n), 5≤f (i)≤(n+4), i=1,2 ..., n

(4) choose suitable positive integer W, Z, it satisfies W＜M and Z＜M

(5) calculate non-super increasing sequence C _i=((A _i+ Z*f (i)) mod M * W), i=1,2 ..., n

(6) from (Z+ (Z)) mod M=0 obtains-Z, from (W*W ^-1) mod M=1 obtains W ^-1

At last, with ({ A _iW ^-1,-Z, M) as private key, with ({ C _i, M) as PKI.

Attention: in this article, " * " in the expression formula represents multiplication.{ C ₁Representative { C ₁, C ₂..., C _n.

3.2.3 encryption section

Encryption section uses for transmit leg, is used for to expressly encrypting.Transmit leg is take over party's PKI for obtaining encryption key, must obtain take over party's public key certificate from the ca authentication center.

In encryption section and decryption portion, symbol " Hash " is represented one-way hash function.

If ({ C _i, M) be PKI, EF is expressly, packet count h≤32.Then the implementation method of encryption section is:

(1) produces the grouping b of h n bit long at random ₁₁b ₁₂B _1n, b ₂₁b ₂₂B _2n..., b _H1b _H2B _Hn

(2) with Hash (b ₁₁b ₁₂B _1nb ₂₁b ₂₂B _2nB _H1b _H2B _Hn) n bit output as session key K

(3) with session key K plaintext EF is carried out symmetric cryptography, obtain ciphertext CF

(4) make i=1

(5) make E ₁=0, j=1

(6) if b _Ij=1, E then _i=(E _i+ C _j) mod M

(7) put j=j+1, if j≤n then goes to (6)

(8) put i=i+1, if i≤h then goes to (5), otherwise, finish

At last, obtain ciphertext CF and the subclass and the sequence { E that can send safely ₁, E ₂..., E _h.

3.2.4 decryption portion

Decryption portion is used for the take over party, is used for ciphertext is decrypted.The take over party with oneself private key as decruption key.

If ({ A _i, W ^-1,-Z, M) be private key, CF is a ciphertext, { E ₁, E ₂..., E _hBe subclass and sequence.Then the implementation method of decryption portion is:

(1) makes i=1

(2) calculate E _i=(E _i* W ^-1) mod M

(3) calculate E _i=(E _i+ (Z)) mod M

(4) make b _I1b _I2B _InEverybody is all 0, E _s=E _i, j=n

(5) if E _s〉=A _j, b then _Ij=1 and E _s=E _s-A _j

(6) put j=j-1, if j 〉=1 and E _s≠ 0, then go to (5)

(7) if E _s≠ 0, then go to (3)

(8) put i=i+1, if i≤h then goes to (2)

(9) with Hash (b ₁₁b ₁₂B _1nb ₂₁b ₂₂B _2nB _H1b _H2B _Hn) n bit output as session key K

(10) with session key K ciphertext CF is carried out the symmetry deciphering, obtain expressly EF

At last, the take over party to recover the plaintext of transmit leg be source document EF.

3.3 advantage and good effect

3.3.1 security meets the demands

Owing to fully utilized lever function and one-way hash function, so this encryption method can effectively be resisted the minimal point attack of Shamir and the L of Lagarias-Odlyzko-Brickell ³The reduction base is attacked.

3.3.2 fast operation

In this encryption method, encrypt, decryption oprerations only uses addition and subtraction basically, and maximum integer (being modulus) can be controlled within 192 bit range, so, with popular RSA, ECC algorithm by comparison, encrypt, deciphering speed will go up manyfold soon.

3.3.3 technology can disclose

Realization technology of the present invention can disclose fully, and PKI (Public Key) also can be provided to the external world fully.As long as private key (Private Key) is not divulged a secret, just can guarantee the safety of ciphertext fully.

3.3.4 the information security to country is favourable

At present, positive develop actively E-Government of China and ecommerce, information security is related to national security and economic security.But the information security of a vast big country can not be based upon on the encryption technology basis of foreign country fully, and does not have autonomous core technology, so, the public key cryptography of studying us seem imperative be significant.

(4) embodiment

Key encrypt method based on lever function and super increasing sequence can allow each user obtain two keys (obtaining from the ca authentication center), a key can disclose, a key can only the individual have, and like this, has not divulged a secret in granting and communication process with regard to not worrying key.When transmitting information on the net, the sender uses recipient's PKI to expressly encrypting, and the recipient uses the private key of oneself that ciphertext is decrypted.

When this key encrypt method is used for development, can adds the curing program or add software with DLC (digital logic circuit) or by DLC (digital logic circuit) and wait and realize by computer hardware.The present invention is a kind of production password product mandatory ultimate principle of institute and technical scheme, rather than physical product itself.

Below, illustrate key encrypt method based on lever function and super increasing sequence:

If sequence item number n=6, packet count h=6 (in the practical application, n should be 96 at least, and h should be 16 at least).

If one-way hash function, promptly the Hash function is as follows:

H ₀=101100 (" 101100 " are binary number, down together)

H _i=(H _I-1 T _i) ²Mod 1000000 (" 1000000 " are binary number, down together)

Wherein, represents binary XOR, T _iExpression length is the binary block of n.

If symmetric encryption scheme (that is decrypt scheme) is:

Y _i＝～(X _iK)

Wherein ,～represent binary inverse, X _iBe the integrated data of n bit, K is the session key of n bit.

Notice that in the practical application, Hash function and symmetric encryption scheme want complicated more than top hypothesis.

(1) generation of key

Implementation method according to 3.2.2 key generating portion:

If produce a super increasing sequence { A at random _iBe 3,5,9,20,39,79}.

Find $M=163>{\mathrm{\&Sigma;}}_{i=1}^6{A}_1=(3+5+9+20+39+79)=155,$ Can verify that 163 is prime number, and (n/log ₂M)=6/log ₂163＞0.645.

Produce lever function value f (1)=4 at random, f (2)=5, f (3)=2, f (4)=6, f (5)=7, f (6)=3.

Choose W=101, Z=158, obviously, W＜M, Z＜M.

Be C _i=((A _i+ Z*f (i)) mod M * W), then

C ₁＝((3+158*4)*101)mod?163＝76 C ₂＝((5+158*5)*101)mod?163＝99

C ₃＝((9+158*2)*101)mod?163＝62 C ₄＝((20+158*6)*101)mod?163＝131

C ₅＝((39+158*7)*101)mod?163＝78 C ₆＝((79+158*3)*101)mod?163＝107

Therefore, obtain non-super increasing sequence { C _i}={ 76,99,62,131,78,107}.

From (Z+ (Z)) mod M=0 obtains (Z)=5, from (W*W ^-1) mod M=1 and according to the expansion Euclidean algorithm obtain W ^-1=92.

With (76,99,62,131,78,107}, 163) as PKI, with (3,5,9,20,39,79}, 92,5,163) as private key.

(2) encrypt

Known take over party's PKI is ({ 76,99,62,131,78,107}, 163).

If expressly EF is a text, its content is " Peking " (not containing quotation marks, totally 6 characters), and then its ASCII character binary mode is: 01,010,000 01,100,101 01,101,011 01,101,001 01,101,110 01100111.

Implementation method according to the 3.2.3 encryption section:

Produce the grouping b of 66 bit long at random ₁₁b ₁₂B ₁₆, b ₂₁b ₂₂B ₂₆..., b ₆₁b ₆₂B ₆₆For:

011010、100101、001100、111110、010011、100111。

Being output as of Hash (011010100101001100111110010011100111) then:

H ₁＝(H ₀T ₁) ²mod?1000000＝(101100011010) ²mod?1000000＝100100

H ₂＝(H ₁T ₂) ²mod?1000000＝(100100100101) ²mod?1000000＝000001

H ₃＝(H ₂T ₃) ²mod?1000000＝(000001001100) ²mod?1000000＝101001

H ₄＝(H ₃T ₄) ²mod?1000000＝(101001111110) ²mod?1000000＝010001

H ₅＝(H ₄T ₅) ²mod?1000000＝(010001010011) ²mod?1000000＝000100

H ₆＝(H ₅T ₆) ²mod?1000000＝(000100100111) ²mod?1000000＝001001

So, obtain session key K=H ₆=001001.

Below, plaintext EF is carried out symmetric cryptography, divide into groups by 6 bits, with " Peking " promptly 010,100 000,110,010,101 101,011 011,010 010,110 111,001 100111 as the input, its ciphering process is as follows:

Y ₁＝～(X ₁K)＝～(010100001001)＝100010；Y ₂＝～(X ₂K)＝～(000110001001)＝110000

Y ₃＝～(X ₃K)＝～(010101001001)＝100011；Y ₄＝～(X ₄K)＝～(101011001001)＝011101

Y ₅＝～(X ₅K)＝～(011010001001)＝101100；Y ₆＝～(X ₆K)＝～(010110001001)＝100000

Y ₇＝～(X ₇K)＝～(111001001001)＝001111：Y ₈＝～(X ₈K)＝～(100111001001)＝010001

To export Y ₁, Y ₂, Y ₃, Y ₄, Y ₅, Y ₆, Y ₇, Y ₈Connect, obtain ciphertext CF, its binary content is 100010110000100011011101101100100000001111010001.

Root pick 3.2.3 encryption method obtains subclass and sequence is from 6 groupings 011,010 100,101 001,100 111,110 010,011 100111:

E ₁＝(b ₁₁C ₁+b ₁₂C ₂+b ₁₃C ₃+b ₁₄C ₄+b ₁₅C ₅+b ₁₆C ₆)mod?M＝(99+62+78)mod?163＝76

E ₂＝(b ₂₁C ₁+b ₂₂C ₂+b ₂₃C ₃+b ₂₄C ₄+b ₂₅C ₅+b ₂₆C ₆)mod?M＝(76+131+107)mod?163＝151

E ₃＝(b ₃₁C ₁+b ₃₂C ₂+b ₃₃C ₃+b ₃₄C ₄+b ₃₅C ₅+b ₃₆C ₆)mod?M＝(62+131)mod?163＝30

E ₄＝(b ₄₁C ₁+b ₄₂C ₂+b ₄₃C ₃+b ₄₄C ₄+b ₄₅C ₅+b ₄₆C ₆)mod?M＝(76+99+62+131+78)mod?163＝120

E ₅＝(b ₅₁C ₁+b ₅₂C ₂+b ₅₃C ₃+b ₅₄C ₄+b ₅₅C ₅+b ₅₆C ₆)mod?M＝(99+78+107)mod?163＝121

E ₆＝(b ₆₁C ₁+b ₆₂C ₂+b ₆₃C ₃+b ₆₄C ₄+b ₆₅C ₅+b ₆₆C ₆)mod?M＝(76+131+78+107)mod?163＝66

At last, transmit leg is with ciphertext CF and subclass and sequence E ₁, E ₂, E ₃, E ₄, E ₅, E ₆Give the take over party by Network Transmission.

(3) deciphering

From the 3.2.4 decryption method as can be seen, the deciphering subclass and process be to verify that while search for every number of times of taking turns search can not surpass ${\mathrm{\&Sigma;}}_{i=1}^{6}f\left(i\right)=27,$ Relevant with item number n polynomial time complexity, be feasible so find the solution.Notice that decrypting process is not used lever function f (i).

The known private key of take over party is ({ 3,5,9,20,39,79}, 92,5,163);

The binary content of ciphertext CF is 100010110000100011011101101100100000001111010001;

Subclass and sequence E ₁, E ₂..., E _mBe 76,151,30,120,121,66.

The implementation method of root pick 3.2.4 decryption portion:

E ₁＝(E ₁*W ^-1)mod?M＝76*92?mod?163＝146

And by E ₁=(E ₁+ (Z)) mod M cyclic search is to E _S=E ₁=53, get b after the checking ₁₁b ₁₂B ₁₆=011010

E ₂＝(E ₂*W ^-1)mod?M＝151*92?mod?163＝37

And by E ₂=(E ₂+ (Z)) mod M cyclic search is to E _s=E ₂=102, get b after the checking ₂₁b ₂₂B ₂₆=100101

E ₃＝(E ₃*W ^-1)mod?M＝30*92mod?163＝152

And by E ₃=(E ₃+ (Z)) mod M cyclic search is to E _s=E ₃=29, get b after the checking ₃₁b ₃₂B ₃₆=001100

E ₄＝(E ₄*W ^-1)mod?M＝120*92mod?163＝119

And by E ₄=(E ₄+ (Z)) mod M cyclic search is to E _s=E ₄=76, get b after the checking ₄₁b ₄₂B ₄₆=111110

E ₅＝(E ₅*W ^-1)mod?M＝121*92?mod?163＝48

And by E ₅=(E ₅+ (Z)) mod M cyclic search is to E _s=E ₅=123, get b after the checking ₅₁b ₅₂B ₅₆=010011

E ₆＝(E ₆*W ^-1)mod?M＝66*92?mod?163＝41

And by E ₆=(E ₆+ (Z)) mod M cyclic search is to E _s=E ₆=141, get b after the checking ₆₁b ₆₂B ₆₆=100111

Like this, we obtain the grouping 011010,100101,001100,111110,010011,100111 of 66 bit long.

Being output as of Hash (011,010 100,101 001,100 111,110 010,011 100111) then:

H ₁＝(H ₀T ₁) ²mod?1000000＝(101100011010) ²mod?1000000＝100100

……

H ₆＝(H ₅T ₆) ²mod?1000000＝(000100100111) ²mod?1000000＝001001

So, obtain session key K=H ₆=001001.Note, ask the K process identical with encryption section.

Below, ciphertext CF is carried out symmetry deciphering, divide into groups by 6 bits, as importing, its decrypting process is as follows with the binary content 100010110000100011011101101100100000001111010001 of ciphertext CF:

Y ₁＝～(X ₁K)＝～(100010001001)＝010100；Y ₂＝～(X ₂K)＝～(110000001001)＝000110

Y ₃＝～(X ₃K)＝～(100011001001)＝010101；Y ₄＝～(X ₄K)＝～(011101001001)＝101011

Y ₅＝～(X ₅K)＝～(101100001001)＝011010；Y ₆＝～(X ₆K)＝～(100000001001)＝010110

Y ₇＝～(X ₇K)＝～(001111001001)＝111001；Y ₈＝～(X ₈K)＝～(010001001001)＝100111

To export Y ₁, Y ₂, Y ₃, Y ₄, Y ₅, Y ₆, Y ₇, Y ₈Connect, obtain expressly EF, its binary content is 010100000110010101101011011010010110111001100111, and textual form is " Peking ".

Obviously, the plaintext that the take over party has recovered transmit leg is source document EF, and knows that its content is " Peking ".

Finish for example.

Claims (1)

1, a kind of key encrypt method based on lever function and super increasing sequence, form by key generation, three parts of encryption and decryption, the key generating portion produces user's a pair of private key and PKI for the 3rd side authoritative institution, encryption section utilizes take over party's PKI expressly being converted to ciphertext for transmit leg, decryption portion utilizes the private key of oneself that ciphertext is reduced into expressly for the take over party, it is characterized in that

● the key generating portion has adopted the following step:

(1) produces the super increasing sequence { A that item number is n at random ₁, A ₂, A _n}

(2) find a positive prime number M, it satisfies $M>\left({\mathrm{\&Sigma;}}_{l=1}^n{A}_i\right),$ And (n/log ₂M)＞0.645

(3) produce at random different in twos functional value f (1), f (2) ..., f (n), 5≤f (i)≤(n+4), i=1,2 ..., n

(4) choose suitable positive integer W, Z, it satisfies W＜M and Z＜M

(5) calculate non-super increasing sequence Ci=((Ai+Z*f (i)) * W) mod M, i=1,2 ..., n

(6) from (Z+ (Z)) mod M=0 obtains-Z, from (W*W ^-1) mod M=1 obtains W ^-1

At last, with ({ A _i, W ^-1,-Z, M) as private key, with ({ C _i, M) as PKI, wherein, private key can only be had privately by the ciphertext take over party;

● encryption section has adopted the following step:

The PKI of supposing the take over party is ({ C _i, M), be EF expressly, packet count h≤32, transmit leg carries out

(1) produces the grouping b of h n bit long at random ₁₁b ₁₂B _1n, b ₂₁b ₂₂B _2n..., b _H1b _H2B _Hn

(2) with Hash (b ₁₁b ₁₂B _1nb ₂₁b ₂₂B _2nB _H1b _H2B _Hn) n bit output as session key K

(3) with session key K plaintext EF is carried out symmetric cryptography, obtain ciphertext CF

(4) make i=1

(5) make E _i=0, j=1

(6) if b _Ij=1, E then ₁=(E1+C _j) mod M

(7) put j=j+1, if j≤n then goes to (6)

(8) put i=i+1, if i≤h then goes to (5), otherwise, finish

At last, obtain ciphertext CF and subclass and sequence { E ₁, E ₂..., E _h, they will be sent to the take over party;

● decryption portion has adopted the following step:

The take over party utilizes the private key ((A of oneself _i, W ^-1,-Z, M), to subclass and sequence { E ₁, E ₂..., E _hCarry out with ciphertext CF

(1) makes i=1

(2) calculate E _i=(E _i* W ^-1) mod M

(3) calculate E ₁=(E ₁+ (Z)) mod M

(4) make b _I1b _I2B _InEverybody is all 0, E _S=E _i, j=n

(5) if E _S〉=A _j, b then _Ij=1 and E _S=E _S-A _j

(6) put j=j-1, if j 〉=1 and E _S≠ 0, then go to (5)

(7) if E _S≠ 0, then go to (3)

(8) put i=i+1, if i≤h then goes to (2)

(9) with Hash (b ₁₁b ₁₂B _1nb ₂₁b ₂₂B _2nB _H1b _H2B _Hn) n bit output as session key K

(10) with session key K ciphertext CF is carried out the symmetry deciphering, obtain expressly EF

At last, the take over party to recover the plaintext of transmit leg be source document EF.