New type public key cryptography , digital signature by higher order equations and symmetric expressions

(Countering the realization of quantum computer)

I have developed a new type of public key cryptosystem that is considered to be able to counter the realization of quantum computers by using symmetric expressions expressed by basic symmetric formulas. Elgama encryption type public key cryptography (Diffie-Hellman key sharing), also supports digital signature. Depending on the difficulty of some kind of discrete logarithm problem, difficulty of solving multi-order multivariable equations is added. The bit number of this encryption key and the time taken for encryption / decryption are somewhat larger than RSA encryption and Elgama encryption, and it is a practical encryption. The realization of the quantum computer was thought to be decades later, but there is a possibility that it will be realized several years later due to rapid technological progress. We think that this cryptosystem is the most appropriate public key cryptography when quantum computer is realized.
Also, in case of this cryptosystem, especially in the case of quadratic expression, it is not prime number, it is not prime number, it can not decompose prime factor of N = pq constructed on the residue type modulo large number of synthesis ⇒ not solve the discrete logarithm problem The following ciphers can be proved. However, although it can not compete with quantum computer, it is "the world's fastest public key cryptography" . Chebyshev2.pdf

Public key cryptography based on higher order equations and symmetric expressions (higher-order symmetric cryptography)

The n th order equation on modulo K

    xⁿ−σ₁x^{n −1}＋σ₂xⁿ⁻²−σ₃xⁿ⁻³＋…＋ (−1)ⁿ⁻¹σ_n−1x＋(−1)ⁿσ_n＝0    …�@
. Let α ₁ , α ₂ , α ₃ , ..., α _n denote the solution of �@ in the extension field of body K according to this equation, then �@
    (x - α ₁ ) (x - α ₂ ) (x - α ₃ ) ··· (x - α _n ) = 0
σ₁ , σ₂ , σ₃ , ..., σ_n are basic symmetric equations of α₁ , α₂ , α₃ , ..., α_n .
Here, when the coefficient of x ⁿ is 1 and an n th degree equation having α ₁ ^p , α ₂ ^p , α ₃ ^p , ..., α _n ^p as a solution
    (x - α ₁ ^p ) (x - α ₂ ^p ) (x - α ₂ ^p ) · · · (x - α _n ^p ) = 0
Let f _p (x) be the expansion expression on the left side of
Since the coefficients of the polynomial f _p (x) are basic symmetric equations of α ₁ ^p , α ₂ ^p , α ₃ ^p , ..., α _n ^p , symmetric equations of α ₁ , α ₂ , α ₃ , ..., α _n Therefore, it can be represented by σ ₁ , σ ₂ , σ ₃ , ..., σ _{n - 1} , σ _n .
Therefore, let p and q be natural numbers different from f ₁ (x)
    f _p (x) and f _q (x)
Are required.
Considering f _pq (x), the coefficient is a basic symmetric expression of α ₁ ^pq , α ₂ ^pq , α ₃ ^pq , ..., α _n ^pq , so α ₁ ^p , α ₂ ^p , α ₃ ^p , ..., α _n ^p , so the coefficients of f _pq (x) can be expressed as coefficients of f _p (x).
Similarly, the coefficient of f _pq (x) can be expressed by the coefficient of f _q (x). That is
You can find  from f _p (x) and q to f _pq (x) , from f _q (x) and p .to f _pq (x)
As a result, the sender and receiver can share the polynomial f _pq (x), and the Elgamal encryption type public key cryptography (Diffie-Hellman key sharing) can be configured.
At the time of implementation, n is a prime number of 3 or more, and the constant term (-1) ⁿ σ _n is -1. At this time, the constant term of f _p (x) is always -1.
Also, take the values ​​of σ ₁ , σ ₂ , σ ₃ , ... σ _n so that �@ does not have a solution on body K. Even in this case, if we consider the extension field, �@ always has solutions α ₁ , α ₂ , α ₃ , ..., α _n .

The problem in implementing the above cryptography is to obtain f _p (x) from f ₁ (x) at high speed, but there was actually a high speed algorithm and it could be implemented.

Let α be one of the solutions of �@
    αⁿ−σ₁αⁿ⁻¹＋σ₂α^{n −2}−σ₃αⁿ⁻³＋…＋(−1)ⁿ⁻¹σ_n−1α ＋(−1)ⁿσ_n＝0
If you deform by multiplying both sides by α ^{k - n}
(- 1) ^{n - 1} σ _{n - 1} α - (- 1) ⁿ σ _n α ^{k - n} (1) where α ^k = σ ₁ α ^{k - 1} - σ ₂ α ^{k -2} + σ ₃ α ^{k - 3} - �A
Is satisfied. If �A is repeatedly used, α ^p is represented by α ⁰ , α ¹ , α ² , ..., α ^n-1 for any natural number p.
That is, for any natural number p, α ^p is
α ^p = t ₁ α ^{n -1} + t ₂ α ^{n - 2} + t ₃ α ^{n - 3} + ... + t _{n - 1} α + t _n ... �B
, And the coefficients t ₁ , t ₂ , t ₃ ,..., T _n-1 , t _n on the right side can be obtained.
Since it is too late to find practically anything if α ^p is sequentially found for α ^{n + 1} , α ^{n + 2} , α ^{n + 3} , ..., α p for a huge natural number p, binary Method is used.
If α ^k is represented by α ⁰ , α ¹ , α ² , ..., α ^{n -1} , α ^{k + 1} = α ^k · α and α ^{2 k} = (α ^k ) ² are also α ⁰ , α ¹ , α ² , ..., α ^{n - 1} , so α ^k can be represented by α ⁰ , α ¹ , α ² , ..., α ^{n - 1} for arbitrary k by the binary method.
Therefore, t ₁ , t ₂ , t ₃ , ..., t _{n - 1} , t _n of �B can be found at high speed.
next,
S _p = α ₁ ^p + α ₂ ^p + ... + α _n ^p
. S _p is a symmetric expression for α ₁ , α ₂ , ..., α _n . I want to find S _p .
In α of �B, α ₁ , α ₂ , α ₃ , ..., α _n Substitute and add
S _p = t ₁ S _{n -1} + t ₂ S _{n -2} + t ₃ S _{n -3} + ... + t _{n -1} S ₁ + t _n S ₀
, The values ​​of S ₀ , S ₁ , S ₂ , S ₃ , ..., S _n-1 and t ₁ , t ₂ , t ₃ , ..., t _{n -1} , t _{n on} the right side of this equation By substituting the value, the value of S _p can be obtained.
Furthermore, if �B is raised to the second power, the third power, ...
α ^p , α 2 ^p , α ^{3 p} , ..., α ^np
Can also be represented by a linear combination of α ⁰ , α ¹ , α ² , ..., α ^n-1 and its coefficients can also be obtained, so S _p , S 2 _p , S _{3 p} , ..., S _np Is required. From the above
σ ₁ , σ ₂ , σ ₃ , ..., σ _{n - 1} , σ _n and S ₀ , S ₁ , S ₂ , S ₃ , ..., S _{n - 1} , The values ​​of S _p , S _2p , S _3p , ..., S _np can be obtained at high speed.....�C

In addition, the following Newton's formula for mutually transforming the basic symmetric expression σ _k (1 ≤ k ≤ n) and the symmetric equation S _k = α ₁ ^k + α ₂ ^k + ... + α _n ^k (1 ≦ k ≦ n) Algorithm) is used.

Algorithm for finding a power sum from a basic symmetric expression
S ₁ = σ ₁
S ₂ = σ ₁ S ₁ - ₂ σ ₂
S ₃ = σ ₁ S ₂ - σ ₂ S ₁ + ₃ σ ₃
..................
S _n = σ ₁ S _{n -1 -} σ ₂ S _{n - 2} + ... + (- 1) ⁿ σ _{n - 1} S ₁ + (- 1) ^{n + 1} nσ _n
Furthermore, when k ≧ n
S _k = σ ₁ S _{k -1} σ ₂ S _{k - 2} + ... + (-1) ⁿ σ _{n - 1} S _{k - n + 1} + (- 1) ^{n + 1} σ _n S _{k - n} ← Sequence {S _k } Can be considered to be defined by this recurrence formula with S ₁ , S ₂ , S ₃ , ..., S _n

An algorithm for finding a basic symmetric expression from a power sum
σ ₁ = S ₁
σ ₂ = - (S ₂ - σ ₁ S ₁ ) · 2 ^-1
σ ₃ = (S ₃ - σ ₁ S ₂ + σ ₂ S ₁ ) · 3 ^-1
..................
σ _n = (- 1) ^{n + 1} {S _n - σ ₁ S _{n - 1} + σ ₂ S _{n - 2} - ... + (- 1) ^{n - 1} σ _{n - 1} S ₁ }

By using this algorithm, the other is obtained from one of σ_k (k = 1, 2, 3, ..., n) and S_k (k = 1, 2, 3, ..., n).
Therefore, the coefficient of x ^nk in the expansion expression on the left side of (x - α ₁ ^p ) (x - α ₂ ^p ) (x - α ₂ ^p ) ··· (x - α _n ^p ) = 0 is σ (p, k), then
    σ₁，σ₂，σ₃，…， σ_n  →　S₁，S₂，S₃，…，S_n 　→　S_p，S_2p，S_3p，…，S_np　→　σ(p，1)，σ(p，2)，σ(p，3)，…，σ(p，n)
Can be obtained.
Therefore, σ (p, 1) , σ (p, 2) , σ (p, 3) Letting σ (p) be the set of σ (p, n) numbers
Let p and q be huge natural numbers,
       From σ (1) σ (p) and σ (q)
σ (pq) is obtained from both σ (p) and σ (q)
It is required at high speed.

As a result, Elgamal cryptography can be constructed as follows. (It will become extremely fast if the magnitude of p and q below is kept at about the same 128 bit as common key encryption.)

(1) Let s = σ (1) and t = σ (p) be the recipient's public key. p is the secret key.

(2) The sender selects a secret random number q for the document M, calculates γ = σ (q) from s and σ (pq) from t.
The document M is encrypted with common key encryption with σ (pq) as a key.
Send the encrypted document and γ = σ (q) to the recipient.

(3) The recipient calculates σ (pq) from γ = σ (q) and secret key p, and decrypts the document with σ (pq) as a key.

Here, t ₁ , t ₂ , t ₃ , ..., t _n  of �B From S _p , S 2 _p , S _{3 p} , ..., S _np Can be easily obtained, S _p , S 2 _p , S _{3 p} , ..., S _np T ₁ , t ₂ , t ₃ , ..., t _n It is difficult to find out.
The usual Elgamal ciphers are t ₁ , t ₂ , t ₃ , ..., t _n (Discrete logarithm problem) that it is difficult to obtain the value of p when given the cryptographic strength as a basis for the strength of this cipher
Difficulty degree for finding t ₁ , t ₂ , t ₃ , ..., t _n from S _p , S _2p , S _3p , ..., S _np is added. S _p , S 2 _p , S _{3 p} , ..., S _np T ₁ , t ₂ , t ₃ , ..., t _n , T ₁ , t ₂ , t ₃ , ..., t _n Linear equation must be solved for this cryptosystem. Therefore, this cryptogram adds a difficult problem of solving a multi-order multivariable equation as the basis of strength. This realizes the quantum computer I think that it is resistant to .

Equatiok.pdf also describes the proof of the Frame method, which is an algorithm for finding the inherent polynomial of a matrix using Newton's official proof and Newton's formula. Please see equatiok.pdf for details.

Digital signature in higher order symmetric cryptography

For an a ₂ , a ₃ , ..., a _n and b ₁ , b ₂ , b ₃ , ..., b _n , an identity of the n ² degree polynomial of x (n is a prime number at the time of implementation, n is an odd number of 3 or more)
        (x−a₁b₁)・ (x− a₁b₂)・ (x−a₁b₃)・…・(x−a₁b_n)・ (x−a₂b₁)・ (x−a₂b₂)・(x−a₂b₃)・…・ (x−a₂b_n)・…・ (x−a_nb_n)
                    ＝x^{n^2}−（a₁＋a₂＋a₃＋… ＋a_n)（b₁＋b₂＋b₃＋…＋b_n)x^{n^2 −1}＋(a₁²b₁b₂＋a₁²b₁b₃＋a₁²b₁b₄＋… ＋a_n²b_n−1b_n)x^{n^2−2}＋… −(a₁a₂a₃…a_nb₁b₂b₃…b_n)ⁿ…�@
think of.
 coefficient is a basic symmetric expression of a₁b₁，a₁b₂，a₁b₃，…， a₁b_n，a₂b₁，a₂b₂，a₂b₃，…， a₂b_n，…，a_nb_n
     T_k＝(a₁b₁)^k＋(a₁b₂)^k＋(a₁b₃)^k＋… ＋(a₁b_n)^k＋(a₂b₁)^k＋(a₂b₂)^k＋(a₂b₃)^k＋… ＋(a₂b_n)^k＋… ＋(a_nb_n)^k
. Deformed
    T _k = (a ₁ ^k + a ₂ ^k + a ₃ ^k + ... + an ^k ) (b ₁ ^k + b ₂ ^k + b ₃ ^k + ... + b _n ^k )
Here, using the Newton's algorithm, all the coefficients of the polynomial �@ are represented by T _k (k = 1, 2, 3, ..., n ² ), T _k is represented by a ₁ , a ₂ , a ₃ , is represented by the basic symmetric expression of a _n and b ₁ , b ₂ , b ₃ , ..., b _n . The computational complexity for obtaining the coefficients of polynomial �@ from a ₁ , a ₂ , a ₃ , ..., a _n and b ₁ , b ₂ , b ₃ , ..., b _{n from} the basic symmetry formula is O (n ⁴ ).
If the coefficient of x ^k in �@ is (-1) ^k A _{n ^ 2 - k} , the right side of �@ is
    x^{n^2}−A₁x^{n^2 −1}＋A₂x^{n^2−2}＋…−A_n^2…�A
. However, A _k are all represented by T _k .
The left side of �@
    (x - a ₁ b ₁ ) · (x - a ₂ b ₂ ) · (x - a ₃ b ₃ ) · · · (x - a_n b _n )
As a factor. Expand this to
    x ⁿ = B ₁ x ^{n - 1} + B ₂ x ^{n - 2} + ... - B _n ... �B
. At this time, �A is divisible by �B.
In particular, if a _k = α _k ^p , b _k = α _k ^q then a _k b _k = α _k ^{p + q} (k = 1, 2, 3,.....,n)
So, �A can also be divisible by �B.

This method is shown.

Digital signature 1 (It is fast for signature 2, signature length is short, added on March 23, 2015)

(1) Let g = σ (1) and t = σ (p) be the sender 's public key. p is the secret key.

(2) The sender obtains the hash value e = h (M) of the document M for the document M and further obtains λ = σ (p + e).
λ is the signature of M. (For safety, pad document M)
At this time, the formula (2) made from σ (p) and σ (e) is λ = σ (p + e).
The sender sends the document M and its signature λ .

(3) The receiver calculates the hash value e = h (M ).
Furthermore, σ (e) is obtained from g and e, Then, Create �A from σ (e) and t .
At this time, if we change equation (2) to λ If the remainder obtained by dividing it by equation (3) becomes 0, it is considered that the signature of document M has been confirmed.

Digital signature 2 ( Elgamal signature or modified digital signature of Schnorr signature ) (Algorithm was revised on June 25, 2011)

(1) Let g = σ (1) and t = σ (p) be the sender 's public key. p is the secret key.

(2) The sender selects a secret random number q for the document M and performs the following calculation.
γ = σ (q)
e = h (M, γ) (Hash value of document combining document M and γ)
δ = q-pe
At this time, since pe + δ = q, The formula (2) made from σ (pe) and σ (δ) is divisible by �B by γ = σ (q).
The sender sends the document M and its signature ( γ , δ) to the recipient.

(3) The receiver obtains the hash value e = h (M, γ ).
Furthermore, σ (δ) is obtained from σ (pe), g and δ from t and e, Create �A from σ (pe) and σ (δ).
At this time, if the remainder obtained by dividing equation (2) by equation (3) by γ becomes 0, it is considered that the signature of document M was confirmed.

Note n is a prime number of 3 or more, and the constant term (-1) ⁿ σ _n is -1.
Equation  x ⁿ - σ ₁ x ^{n -1} + σ ₂ x ^{n - 2} - σ ₃ x ^{n - 3} + ... + (- 1) ^{n - 1} σ _{n - 1} x - 1 = 0
Dividing both sides by xⁿ and placing 1/x = t
    t ⁿ _{- 1} t ^{n -1} + σ _{n - 2} t ^{n - 2} - σ _{n - 3} t ^{n - 3} + ... + (- 1) ^{n - 1} σ ₁ t - 1 = 0
The order of the original equations and coefficients is reversed.
Therefore, in Newton's algorithm, σ ₀ , σ ₁ , σ ₂ , ..., σ _{n -1} , σ _n are replaced with σ _n , σ _{n -1} , σ _{n -2},....., σ ₁ , σ ₀  and  S ₁ , S ₂ , S ₃ , ... are replaced by S _-1 , S _-2 , S _-3 , ... holds. For calculation of σ _{n -1} , σ _{n -2} , ... σ _{(n + 1) / 2} , the calculation amount is about 1/2 in the digital signature and it can be parallelized. Therefore, It can be halved further.

Features of higher-order symmetric cryptography

1. This cipher is a set of the number of prime fields K = σ = (σ ₁ , σ ₂ , σ ₃ , ..., σ _{n - 1} ) and a set of natural numbers p to number (σ _{1, p} , σ _{2, p} , σ _{3 , p} , ..., σ _{n - 1, p} ). At this time f ( σ , p), q) = f ( σ , pq) holds but f ( σ , p + q) can not be found from f ( σ , p) and f ( σ , p) Hmm. Therefore, Elgamal cipher (Diffie - Hellman key sharing) can be configured, but efficient cryptanalysis for ordinary Elgamal cipher is ineffective. Furthermore, it is considered to be resistant to quantum computers.
2. Since postprocessing is added after calculation of exponents similar to Elgamal cryptosystem, encryption becomes slightly slower if it is the same bit length as compared with normal Elgamal cryptosystem.
3. The computational complexity is O (n ³ ) in a simple method in the case of nth order equation. Therefore, the total calculation amount is O (bit number ³ ).
4. In the case of the nth order equation, the number of bits of the key is about n - 1 times the number of bits of the body to be implemented.
5. In order to solve this cipher efficiently, it seems to be necessary to solve a multi-order multivariable equation, so it is considered to be multi-order multivariable public key cryptosystem . However, for safety, it is better to set n to 100 or more.
6. The signature length of the digital signature 1 is the same as the public key length, and the signature length of the digital signature 2 is longer than the public key length. Also, there are O (n ³ ) and O (n ⁴ ) parts in the calculation, but the coefficients of O (n ⁴ ) are small, so if n is around 100 it will be fast enough.
7. We have not applied for patents, so the algorithm is free to use.

Higher order symmetric cryptography and its digital signature were implemented in the case of 13 bit × 103 order equation.

• Explanation of creation of public key cryptography by higher order equations equation.pdf
• Implementation example of encryption in the case of 13 bit × 103 degree equation Equation.c multi.c ← multi.c must be changed to multi.h and be included
• Digital signature 2 implementation example signature.c Please change multi.c ← multi.c to multi.h and include it
• A program "decimal BASIC" that finds prime numbers necessary for this cryption equationprime.bas

Below is the cubic expression up to which we came up with the above cipher. It remains for the sake of reference only.

• Explanation of encryption · digital signature when extending Chebyshev polynomial Chebyshev.pdf
• Example of implementation of encryption when extending Chebyshev polynomial Chebyshev 127.c
• Implementation example of encryption in the case of cubic equation with equation of higher order equation125.c

I think that this cipher can only be solved in exponential time. This is the "world's strongest public-key cryptosystem" which is thought to survive when the quantum computer realizes, RSA cipher, Elgamal cipher, elliptic curve cryptograpy is destroyed.

There is also vulnerability in "CAB method cipher" which claimed that "cryptanalysis was proved mathematically proved" also in "Sarah's cipher" famous for his book "The world's strongest cipher challenged by 16-year-old Sarah". did. Sarah.pdf CAB.pdf
There is a possibility of this vulnerability also in this cipher. Those who have found mistakes or defects in theory or implementation, those who think that it is not the world's strongest public key cryptosystem, those who think that such ciphers can be easily solved should be informed by e-mail.

(E-mail address is an image for anti-spam measures.)

Back to the first page