Quantum safe cryptography and advanced encryption and key exchange (AEKE) method for symmetric key encryption/exchange

Abstract

An advanced encryption and key exchange (AEKE) algorithm for quantum safe cryptography is disclosed. The AEKE algorithm does not use hard mathematical problems that are easily solvable on a quantum computer with Shor's algorithm. Instead, new encryption algorithm uses simple linear algebra, rank deficient matrix and bilinear equation, which will be easy to understand, fast, efficient and practical but virtually impossible to crack.

Claims

1. A quantum safe cryptography and advanced encryption and key exchange (AEKE) method for symmetric key encryption/exchange comprising: generating a sender private key ‘a’; generating a recipient private key ‘c’; generating a public key ‘B’ by the sender, said private keys ‘a’, ‘c’ and public key ‘B’ generated via an unpredictable random number generator, wherein public key ‘B’ is made a rank deficient linearly dependent matrix; generating and distributing a shared key k by an equation k=a.sup.tBc for a product of a transpose of an n×1 vector ‘a.sup.t’ of the sender private key ‘a’, an n×n matrix ‘B’ of the public key, and an n×1 vector ‘c’ of a recipient private key ‘c’; transmitting the public key ‘B’ to the recipient; encrypting the sender private key by ‘e.sub.s.sup.t=a.sup.tB’; encrypting the recipient private key by ‘e.sub.r=Bc’; exchanging the encrypted private keys ‘e.sub.s’ and ‘e.sub.r’ between the sender and the recipient; generating a shared private key ‘k’ by ‘a.sup.te.sub.r’ by the sender; generating the shared private key ‘k’ by ‘e.sub.s.sup.tc’ by the recipient; converting a 1×1 vector of the shared private key ‘k’ into a p×n matrix K by splitting the shared private key into each cell of a K matrix by the sender; converting a 1×1 vector of shared private key ‘k’ into p×n matrix K by splitting the shared private key into each cell of the K matrix by the recipient; a sending user encrypting a textual message by the sender converting the textual message into numbers and splitting the numbers to each cell of a message matrix ‘M’ using a character code; the sender generates an m×n error matrix ‘D’ with an unpredictable random number generator using the shared private key ‘k’ as a seed; the sender generates a cipher text ‘E’ with the error matrix ‘D’, the message matrix ‘M’ and the shared private key ‘K’ using an encryption equation E=MK+D; the sender adds characters to the cipher text ‘E’; the sender shuffles cell elements in the cipher text ‘E’; the sender sends the cipher text ‘E’ to the recipient; the recipient unshuffles the cipher text ‘E’; the recipient subtracts added characters from the unshuffled cipher text ‘E’; the recipient generates the m×n error matrix ‘D’ with the unpredictable random number generator using the shared private key ‘k’ as the seed; the recipient decrypts, unshuffles and subtracts cipher text ‘E’ to recover the numbers in the message ‘M’ using the error matrix ‘D’ and the shared private key ‘K’ from the equation M=(E−D)K.sup.t(KK.sup.t).sup.−1, and converts the recovered numbers in the message matrix ‘M’ into the textual message for a readable text message to the recipient.

2. The method according to claim 1, further includes shuffling the cipher text ‘E’ using the shared private key ‘k’ as the seed.

3. The method according to claim 1, further includes adding numbers or characters to make a uniform distribution of the cipher text ‘E’.

4. The method according to claim 1, wherein the shared private key K is used a different key for each cell to increase an encryption security.

5. The method according to claim 1, wherein said character code is preassigned numbers for each character.

6. The method according to claim 1, wherein said symmetric key is a variable length.

7. The method according to claim 1, wherein a matrix is used the sender private key.

8. The method according to claim 1, wherein a matrix is used the recipient private key.

9. The method according to claim 1, further includes extending a length of the sender private key.

10. The method according to claim 1, further includes extending a length of the recipient private key.

11. The method according to claim 1, wherein said shared private key generation for the sender private key, the recipient private key and the public key is with real numbers.

12. The method according to claim 11, wherein said shared private key is a shared symmetric key.

13. The method according to claim 1, wherein said n×n matrix ‘B’ is at least a 2×2 matrix.

14. The method according to claim 1, further includes a rank deficient matrix of the public key ‘B’ for a key exchange.

15. The method according to claim 14, wherein said rank deficient matrix of the public key ‘B’ for said key exchange is by making a linearly dependent matrix.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S)

(1) FIG. 1 shows a shared symmetric key generation and exchange method.

(2) FIG. 2 shows an encryption and decryption method using a shared symmetric key.

DETAILED DESCRIPTION OF THE INVENTION

(3) It will be readily understood that the components of the present invention, as generally described and illustrated in the drawings herein, could be arranged and designed in a wide variety of different configurations. Thus, the following more detailed description of the embodiments of the system and method of the present invention, as represented in the drawings, is not intended to limit the scope of the invention but is merely representative of various embodiments of the invention. The illustrated embodiments of the invention will be best understood by reference to the drawings, wherein like parts are designated by like numerals throughout.

(4) TABLE-US-00001 Item Numbers and Description 20 sender 21 recipient 30 sender private key 31 encrypted sender private key 32 public key 33 recipient private key 34 encrypted recipient private key 40 send to a.sup.tB 41 Send to Bc 50 encrypted sender private key 51 recipient private key 52 shared secret key 53 encrypted recipient private key 54 sender private key 61 message 62 encryption 63 decryption 64 message 65 send to

(5) The quantum safe cryptography and AEKE method for symmetric key encryption/exchange of the present disclosure may be comprised of the following elements. This list of possible constituent elements is intended to be exemplary only and it is not intended that this list be used to limit the quantum safe cryptography and AEKE method of the present application to just these elements.

(6) FIG. 1 shows a shared symmetric key generation and exchange method.

(7) Shared Private Key Exchange

(8) 1. Shared key generation and distribution uses an equation of k=a.sup.tBc, where k is 1×1 vector of shared private key for sender and recipient, a.sup.t is a transpose of n×1 vector a of sender private key, B is n×n matrix of public key, and c is n×1 vector of recipient private key.

(9) 2. From FIG. 1, both sender and recipient of the message generate their own private keys, as a sender private key 30 a and a recipient private key 33 c. The sender private key 30 a and the recipient private key 33 c are created with secure random number generator(s) or any other method that is unpredictable.

(10) 3. The sender generates a public key 32 B with secure random number generator or any other method that is unpredictable and makes the public key 32 B rank deficient matrix (by making the public key 32 B linearly dependent.)

(11) 4. The sender transmits the public key B to the recipient.

(12) 5. Both the sender and recipient encrypt the sender private key 30 a and the recipient private key 33 c with the same public key 32 B (31 e.sub.s.sup.t=a.sup.tB for sender and 34 e.sub.r=Bc for recipient).

(13) 6. The sender 20 sends encrypted sender private key 31 e.sub.s.sup.t to the recipient 21 (40) and the recipient 21 sends encrypted recipient private key 34 e.sub.r to the sender 20 (41).

(14) 7. Sender generates the shared private key 52 k with encrypted recipient private key 53 e.sub.r and sender private key 54 a by a.sup.te.sub.r and converts it into p×n matrix K by splitting the key into each cell of matrix K.

(15) 8. Recipient generates the same-shared private key 52 k with encrypted sender private key 50 e.sub.s.sup.t and recipient private key 51 c by e.sub.s.sup.tc and converts it into p×n matrix K by splitting the key into each cell of matrix K.

(16) 9. If only one user encrypts and decrypts the information, the user generates the private key 52 K with a, B, c, and secure random number generator or any other method that is unpredictable.

(17) The Above Steps 1-8 is how to Generate the Shared Key and Exchange the Shared Key Between Sender and Recipient—This is the Novel Key Exchange Feature.

(18) FIG. 2 shows an encryption and decryption method using a shared symmetric key.

(19) Encryption and Decryption of the Message

(20) 10. AEKE symmetric key encryption uses E=MK+D as the encryption algorithm, which is a bilinear equation, where E is m×n cipher text, M is m×p message, K is p×n private key, and D=m×n error matrix. (THIS IS THE ENCRYPTION FEATURE).

(21) 11. The sender converts the message into numbers and splits it into each cell of the message matrix 61 M using ASCII character code or equivalent table.

(22) 12. The sender generates m×n error matrix D with a secure random number generator or any other method that is unpredictable using the shared private key k as a seed.

(23) 13. The sender generates the cipher text E with message 61 M, error matrix D and shared secret key 52 K using E=MK+D. If more security is needed, the encryption can use different key for each cell of K.

(24) 14. The sender 20 can add characters to make uniform distribution of the cipher text E and shuffle it if more security is needed for the cipher text E.

(25) 15. The sender 20 sends the cipher text E to the recipient 21.

(26) 16. The recipient 21 unshuffle and subtract added characters from the cipher text E if adding characters and shuffling are used.

(27) 17. In the decryption, the recipient 21 generates m×n error matrix D with a secure random number generator or any other method that is unpredictable using the shared private key k as a seed and decrypts 63 the cipher text E to recover the numbers in the message 64 M using error matrix D and the shared private key 52 K from M=(E−D)K.sup.t(KK.sup.t).sup.−1.

(28) 18. The recipient converts the recovered number in message M into the readable message 64.

(29) The various elements of the quantum safe cryptography and AEKE method for symmetric key encryption/exchange of the present disclosure may be related in the following exemplary fashion. It is not intended to limit the scope or nature of the relationships between the various elements and the following examples are presented as illustrative examples only. Steps 2 and 3 are the private and public key generation steps needed to generate the shared key in steps 7 and 8. In step 5, private keys for the sender and the recipient generated from step 2 are encrypted with a public key generated from step 3. Then the shared same private key for the sender and the recipient is generated in steps 7 and 8. If a single user uses AEKE system, shared key generation is not needed; therefore, the user would skip steps 4 through 8 and step 15. Instead, the single user could just generate a private key in step 9 with a, B and c. Message is encrypted into a cipher text in steps 11 through 14. Then the cipher text is decrypted and converted into the original message in steps 16 through 18.

(30) The quantum safe cryptography and AEKE method of the present disclosure generally works by following the above-listed steps. In this way, a sending user (the sender) can encrypt a message to a cipher text using a shared private key. Then the recipient can decrypt the cipher text to a readable plain text using the same-shared private key. Shared symmetric key generation and its key exchange method can be applied to the secure one-time pad generation.

(31) To make the quantum safe cryptography and AEKE method of the present disclosure, one may implement the steps of the method into a practical application, such as a program that implements the above-listed steps so that users can easily use the quantum safe cryptography and AEKE scheme to successfully provide secure messaging. Also, it is possible to make the quantum safe cryptography and AEKE method more secure by extending the length of both the sender and the recipient private keys in each cell of a vector, or just be using a matrix instead of a vector, or both extending the length of the keys and using a matrix. This will increase the complexity of the shared private key. The encryption can also use different key for each cell of K to increase the security. In addition, using real numbers instead of integers in all cells of a vector and a matrix will increase the security of the encryption system. To further increase the security of the encryption, characters can be added to the cipher text to make it uniform distribution and shuffle the cipher text using private key k as a seed as well.

(32) To use the quantum safe cryptography and AEKE method of the present disclosure, a user would typically follow the steps listed above in the order shown. By following the above-listed steps, in the order listed, the secret key can be securely shared between the sender and the recipient. Then the recipient can securely decrypt the cipher text sent by the sender without using the public encryption of the secret key. However, the order of the steps for using the quantum safe cryptography and AEKE method is not a required order. In other embodiments of the quantum safe cryptography and AEKE method the order of the steps can vary from the order shown above. For instance, in some embodiments, step 3 can occur before step 2 and the quantum safe cryptography and AEKE method will provide identical results. In addition, steps 7 and 8 can be shuffled.

(33) For a better understanding of the shared key exchange and symmetric key encryption method, this document provides an example using a message “Hello World!” illustrated in step-by-step for the case of m=n=p=3 and the message “Hello World!”.

(34) 1. Shared Symmetric Key Generation

(35) Step 1. Sender generates its own sender private key 30 with a secure random number generator or any other method that is unpredictable. In this example the sender private key is identified as a.sup.t=[227 148 339] and linearly dependent rank deficient public key 32 B.

(36) There are many ways to create a rank deficient matrix. In this illustration, public key B is made a rank one matrix, i.e. the second and third columns and rows are multiples of the first column and row, respectively.

(37) $B=\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 6\\ 3& 6& 9\end{array}\right]$

(38) Then sender encrypts its own sender private key 30 a with the public key 32 B.

(39) $e_s^t=a^{t}B=\left[\begin{array}{ccc}227& 148& 339\end{array}\right]\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 6\\ 3& 6& 9\end{array}\right]=\left[\begin{array}{ccc}1540& 3080& 4620\end{array}\right]$

(40) Step 2. The sender 20 transmits both encrypted private key e.sub.s and the public key 32 B to the recipient 21.

(41) Step 3. The recipient generates its own recipient private key 33 c with a secure random number generator or any other method that is unpredictable. In this example the recipient private key is c.sup.t=[389 268 428] and the recipient encrypts its own private key 34 with the public key 32 B.

(42) $e_r=\mathrm{Bc}=\left[\begin{array}{ccc}1& 2& 3\\ 2& 4& 6\\ 3& 6& 9\end{array}\right]\left[\begin{array}{c}389\\ 268\\ 428\end{array}\right]=\left[\begin{array}{c}2209\\ 4418\\ 6627\end{array}\right]$

(43) Then recipient 21 sends e.sub.r the sender 20.

(44) Step 4. Sender generates the shared private key 52 k with the own sender private key 54 a and the encrypted recipient private key 53 e.sub.r.

(45) $k=a^t{e}_r=\left[\begin{array}{ccc}227& 148& 339\end{array}\right]\left[\begin{array}{c}2209\\ 4418\\ 6627\end{array}\right]=3401860$

(46) Step 5. The recipient 21 generates the same-shared secret key 52 k with recipient private key 51 c and the Encrypted Sender Private Key 50 e.sub.s.

(47) $k=e_{s}c=\left[\begin{array}{ccc}1540& 3080& 4620\end{array}\right]\left[\begin{array}{c}389\\ 268\\ 428\end{array}\right]=3401860$

(48) 2. Encryption and Decryption

(49) Step 6. Both sender and recipient convert 1×1 vector k into 3×3 matrix K by splitting the key into each cell of 3×3 matrix.

(50) $K=\left[\begin{array}{ccc}0& 0& 3\\ 4& 0& 1\\ 8& 6& 0\end{array}\right]$

(51) Step 7. Sender transforms the message “Hello World!” into numbers with a two-digit number for each character according to preassigned numbers. In this example the letters are converted using an ASCII conversion where each letter is converted to a numerical value.

(52) In this illustration, preassigned numbers for each character are H=44, e=15, 1=22, o=25, blank=95, W=59, r=28, d=14, and !=63. Each number is serially appended together. This transforms the message into m=441522222595592528221463. Then in is split into each cell of 3×3 matrix M.

(53) $M=\left[\begin{array}{ccc}44& 222& 528\\ 15& 595& 221\\ 22& 592& 463\end{array}\right]$

(54) Step 8. Sender generates 3×3 error matrix D with a secure random number generator or any other method that is unpredictable using the shared private key 52 k (3401860) as a seed.

(55) $D=\left[\begin{array}{ccc}62421& 13997& 52136\\ 53778& 55426& 49760\\ 19811& 72572& 27115\end{array}\right]$

(56) Step 9. The sender generates the cipher text E with D and the shared private key K generated in step 6. Then transmits E to the recipient.

(57) $E=\mathrm{MK}+D=\left[\begin{array}{ccc}44& 222& 528\\ 15& 595& 221\\ 22& 592& 463\end{array}\right]\left[\begin{array}{ccc}0& 0& 3\\ 4& 0& 1\\ 8& 6& 0\end{array}\right]+\left[\begin{array}{ccc}62421& 13997& 52136\\ 53778& 55426& 49760\\ 19811& 72572& 27115\end{array}\right]$$\mathrm{Combining}E=\left[\begin{array}{ccc}5112& 3168& 354\\ 4148& 1326& 640\\ 6072& 2778& 658\end{array}\right]+\left[\begin{array}{ccc}62421& 13997& 52136\\ 53778& 55426& 49760\\ 19811& 72572& 27115\end{array}\right]=[\begin{array}{ccc}67533& 17165& 52490\\ 57926& 56752& 50400\\ 25883& 75350& 27773\end{array}]$

(58) Step 10. Recipient generates 3×3 error matrix D with a secure random number generator or any other method that is unpredictable, using the shared private key 52 k as a seed.

(59) 0$D=\left[\begin{array}{ccc}62421& 13997& 52136\\ 53778& 55426& 49760\\ 19811& 72572& 27115\end{array}\right]$

(60) Then subtract D from E and recover the message M.

(61) $E-D=[\begin{array}{ccc}67533& 17165& 52490\\ 57926& 56752& 50400\\ 25883& 75350& 27773\end{array}]-\left[\begin{array}{ccc}62421& 13997& 52136\\ 53778& 55426& 49760\\ 19811& 72572& 27115\end{array}\right]=\left[\begin{array}{ccc}5112& 3168& 354\\ 4148& 1326& 640\\ 6072& 2778& 658\end{array}\right]$$\begin{array}{c}M=\left(E-D\right){K^t\left({\mathrm{KK}}^t\right)}^{-1}\\ =\left[\begin{array}{ccc}5112& 3168& 354\\ 4148& 1326& 640\\ 6072& 2778& 658\end{array}\right]\left[\begin{array}{ccc}0& 4& 8\\ 0& 0& 6\\ 3& 1& 0\end{array}\right]{\left(\left[\begin{array}{ccc}0& 0& 3\\ 4& 0& 1\\ 8& 6& 0\end{array}\right]\left[\begin{array}{ccc}0& 4& 8\\ 0& 0& 6\\ 3& 1& 0\end{array}\right]\right)}^{-1}\\ =\left[\begin{array}{ccc}44& 222& 528\\ 15& 595& 221\\ 22& 592& 463\end{array}\right]\end{array}$

(62) Numbers in each cell of 3×3 matrix M are put together to form, m=441522222595592528221463. Then recipient converts in into characters by reversing two-digit numbers in in using the preassigned numbers and recovers the original message, “Hello World!”

(63) Google defines “The rank of a matrix is defined as (a) the maximum number of linearly independent column vectors in the matrix or (b) the maximum number of linearly independent row vectors in the matrix. Both definitions are equivalent. For an r×c matrix, if r is less than c, then the maximum rank of the matrix is r.” A matrix is said to have full rank if its rank is either equal to its number of columns or to its number of rows (or to both). A matrix that does not have full rank is said to be rank deficient.

(64) Thus, specific embodiments of a quantum safe cryptography and advanced encryption and key exchange method for symmetric key encryption/exchange have been disclosed. The above-described embodiments of the invention are presented for purposes of illustration and not of limitation. While these embodiments of the invention have been described with reference to numerous specific details, one of ordinary skill in the art will recognize that the invention can be embodied in other specific forms without departing from the spirit of the invention. It should be apparent, however, to those skilled in the art that many more modifications besides those described are possible without departing from the inventive concepts herein. The inventive subject matter, therefore, is not to be restricted except in the spirit of the appended claims.