Patent Publication Number: US-2020304306-A1

Title: Cryptographic System and Method

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present invention relates generally to cryptographic systems and methods. More particularly, the present invention relates to public key cryptographic systems and methods that can be used, for example, to build highly secure systems for data storage, access, encryption, decryption, digital signing, and digital signing verification. 
     FIELD OF THE INVENTION 
     The present invention relates generally to cryptographic systems and methods. More particularly, the present invention relates to public key cryptographic systems and methods that can be used, for example, to build highly secure systems for data storage, access, encryption, decryption, digital signing, and digital signing verification. 
     BACKGROUND OF THE INVENTION 
     Security over the Internet is crucial as everyday life is becoming ever more reliant on the Internet, e.g. remote access, social media, banking, money transfer, stock trading, shopping, researching, medical records transfer, voting, tax filing, identification, etc. There are many aspects of security over the Internet, one of which is safe guarding accessibility of data by blocking unauthorized access to hardware components such as servers. Another aspect is to prevent comprehension of data after unauthorized access has occurred. This second aspect is critical in addressing the ever-evolving illegitimate and malicious means of gaining access to data. Many technologies have been developed to make the Internet safe against such illegitimate and malicious activities. 
     A common type of malicious activity is inserting spyware into an end-user computer to surreptitiously copy Internet activity such as User Name and Password transmission for various sensitive accounts. Anti-virus programs are one tool used to combat this type of attack. Another common malicious activity is spoofing a web site, such as a banks&#39; online login page, to look the same as the original. When a user enters login credentials, this forged site captures the sensitive login credentials. Digital Certificates are a tool used to secure the Internet against this type of attack. Digital Certificates help to guarantee that the site you are visiting is really the site operated by the original intended organization instead of a “look-a-like” spoofed site operated by a malicious party. Digital Certificates also allow software publishers to digitally sign executable files to prove legitimacy. 
     Even though there are many ways to block malicious activities, there is an ever-present risk of becoming a victim of a cyber attack. For example, malicious attackers are constantly working on ways to bypass anti-virus software. Malicious parties may also be able to gain access to the database of a public server, such as a bank or a social media site, by-passing the login process. Malicious parties may also be able to tap into a communication session between an end user and a website they are accessing and collect data as a “man in the middle”. It is important, therefore, to implement lower level security, such as encryption, to ensure that no one can understand the content of the communication session even if security has been breached. 
     There are many different encryption techniques. Symmetrical encryption methods, such as AES and DES, use the same key to encrypt and decrypt. Another form of encryption is the asymmetrical encryption method using a pair of private and public keys. Examples of this type of encryptions include RSA and El Gamal. This type of encryption uses one of the keys to encrypt data so that only the entity having the other key can decrypt it. Banks use this type of encryption in their communication sessions and typically employ an SSL Digital Certificate with a pair of private and public keys. The public key is built into the Certificate and distributed publicly to whoever wants to establish a communication session with the bank&#39;s server. When the user is communicating with the bank&#39;s server, such as when transmitting the user name and password, the contents will be encrypted and the corresponding session keys of the symmetric encryption will be encrypted using the public key. Only the bank&#39;s server, having the private key, will be able to decrypt the data. 
     In general, a public and private key pair is generated by multiplying two very large randomly selected prime numbers as well as performing some other complex mathematical processes such as hashing. Security of asymmetrical encryption lies in the difficulty of factoring a semi-prime number that is the product of two very large prime numbers, an essential step to reverse engineer a private key from its public key twin. As a result, the time required to factor a semi-prime number into the original prime numbers in order to decrypt the message (“Brute Force Time”) is exponentially related to the size of the public key. 
     An RSA key size of 4096 bits is believed to be unbreakable in human acceptable time as of the date of this application using brute force factoring. However, this assumption only applies to computer technologies generally available as of the date of this application. A new breed of computer has been in development since early 1980s referred to as quantum computers. Quantum computers employ quantum-mechanical phenomena, such as superposition and entanglement, so that computation can be carried out simultaneously as contrasted with classical computing which is based on just on/off states, i.e., bits, and in which computation is performed sequentially. 
     A quantum computer is able to factor large numbers in polynomial time and could be used to break the public/private key mechanism. Shor&#39;s Algorithm, which is designed to run on a Quantum computer, is the process of period-finding which is done using Quantum Fourier Transform (QFT). The QFT can be used to determine the period of a function f(x). QFT processing can be done efficiently on a quantum computer because all of the experiments can be run at once in superposition, with bad experiments deteriorating from destructive interference effects and the good experiments dominating from constructive interference effects. Once the period-finding mechanism of the QFT becomes available, it can be exploited to find patterns in the mathematical structure of the number being factored. While not yet a commodity item, quantum computers will be at least available via the cloud in the foreseeable future. 
     Another trend is Distributed Ledger Technology (“DLT”) which involves distributing a database over multiple computers as opposed to being contained in a single central database. This technology is also frequently referred to as “Blockchain” technology. DLT increases security by requiring each new block of data to be digitally signed by the authorized node who posted it, and to also include a hash value for the previous block. Thus, a list is formed that contains the hash values of all of the blocks in this chain going back to the first block. By requiring the hash values of all previous blocks to be included, the history of transactions is greatly secured against editing. 
     DLT further requires the chain of data blocks be replicated among numerous computers with a self-correcting mechanism. This way, not only is a natural redundancy built-in but, importantly, a consensus is also required to legitimize a new block. In other words, malicious activities must simultaneously attack a large number of nodes for the fake transaction to “appear as legitimate.” Otherwise, the “minority fake transaction” will be over-written by the self-correcting mechanism of DLT. 
     DLT is considered to be a highly secure platform for cyber-security that is also practically feasible. Notwithstanding the advantages provided by DLT and asymmetric encryption, both technologies rely on the difficulty of prime number factorization as their main defense. Quantum computers, which have the ability to factor large prime numbers, will therefore present a challenge to security using these technologies. 
     A number of methods have been proposed that are theoretically capable of making the Brute Force Time exponentially related to the key size when quantum computers are used to do such computational processing. Examples of such methods are code-based encryption, lattice-based encryption, hash-based encryption, systems based on multivariate polynomial equations, and systems based on supersingular isogenies of elliptic curves. Exemplary code-based encryption functions include the McEliece cryptosystem and the Niederreiter cryptosystem which have been mathematically proven to have an exponential relation between key size and the Brute Force Time in the Post-Quantum world. 
     There are 2 main components of the secret key for the McEliece and Niederreiter schemes, i.e., a Goppa polynomial, G(x), and L, i.e., the set of numerators of the codeword positions, also referred to as the locators or support set. From coding theory it is well-known that it is G(x) and L that uniquely define the Goppa code, i.e., (L,G) code. G(x) and L uniquely determine the parity check and generator matrices and they are also necessary to realize a constructive decoding algorithm of the (L, G) code. In all known schemes based on Goppa codes, the secret is a polynomial G(x) where set L is a set of all elements of the Galois field GF(2 m ), where 2 m =n is an element of a public key. 
     With respect to the first component of the secret key, the known McEliece and Niederreiter encryption schemes are based on binary irreducible Goppa codes with the following 4 definitions:
         Definition #1: Goppa code is called irreducible if G(x) is an irreducible polynomial.   Definition #2: A binary vector α=(a 1 a 2  . . . a n ) is a codeword of (L, G) code if, and only if, the following equality is satisfied:       

     
       
         
           
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   n 
                 
                  
                 
                   
                     a 
                     i 
                   
                   
                     x 
                     - 
                     
                       α 
                       i 
                     
                   
                 
               
               = 
               
                 0 
                  
                 
                     
                 
                  
                 mod 
                  
                 
                     
                 
                  
                 
                   G 
                    
                   
                     ( 
                     x 
                     ) 
                   
                 
               
             
             , 
           
         
       
     
     where α i ∈L and L={α 1 ,α 2 , . . . , a n }⊆GF(2 m ),G(α i )≠0, ∀α i ∈L.
         Definition #3: Goppa code is called separable if the polynomial G(x) does not have multiple roots.   Definition #4: Goppa code is called wild if the polynomial G(x) has the following form: G(x)=g(x) τ  where g(x) is a separable polynomial.       

     With respect to the second component, the second part of the private key of McEliece and Niederreiter schemes is the support set L⊆GF(2 m ). In a classical McEliece scheme there are two matrices used: S, a random non-singular k×k matrix, and P, a random n×n permutation matrix. In the McEliece scheme, by using the two matrices and a generator matrix G, obtained from L and G(x), a public key matrix G*=S×G×P is calculated. 
     The McEliece cryptosystem (MECS) is defined as follows:
         Private key: (Decoding algorithm, L, G(x), S, P)   Public key: G*=S×G×P   Encryption: Let m be a k-bit message, and let e be a random n-bit vector with Hamming weight W H (e)≤t. Then c=m×G*⊕e is a ciphertext.   Decryption: Decryption is given by the following algorithm:   1) c*=c×P −1 =m×S×G⊕e×P −1 =m*×G⊕e×P −1      2) Obtaining m*=m×S by using decoding algorithm (error correcting) with knowledge L and G(x).   3) m=m*×S −1          

     Although a more secure form of encryption, the McEliece and Niederreiter schemes use a large key size, requiring more storage resources. There is a need for a cyber security mechanism that addresses the challenges to cyber-security that quantum computers will present. This mechanism must not only be secure against the computing power of quantum computers but it must also be deployable in connection with classical computing devices, smartphones, Internet-of-Things (IoT) devices, miniature devices like credit card chips, etc. This mechanism must also maintain high efficiency in the encryption/decryption process. 
     SUMMARY OF THE INVENTION 
     In accordance with one aspect of the present invention, a cryptographic system and cryptographic method is provided in which an input device receives data to be encrypted. The cryptographic system and method also includes a processor for receiving the data to be encrypted and encrypting that data using instructions from a cryptographic engine. In the cryptographic system and method, the instructions when executed encrypt the data using a code-based encryption scheme based on binary irreducible Goppa code in which the support set consists of the rational functions with a degree of the denominator not greater than the degree of the Goppa polynomial. 
     In accordance with another aspect of the invention, the instructions when executed also use the Goppa codes in a weighted Hamming metric. 
     In yet another aspect of the invention, the polynomials have degree not greater than r, where r is the maximum degree of the denominator of a rational function over F 2     m   [x] in the set of L, where L is a set of rational functions of degree not greater than r where r is greater than 1, and with coefficients from a finite field GF(2 m ). 
     In yet another aspect, a system and method is provided for creating a public key cryptographic platform that has increased security against cyber attacks using quantum computers. In this embodiment there are in general 3 different ways of implementation: 1) Signature-only; 2) Encryption-only; 3) Signature+Encryption. Signature-only implementation is utilized, for example, when authenticity of the message needs to be verifiable but the message can be transmitted and stored without encryption. An example of this is public Blockchain that is storing publicly-accessible data. 
     Encryption-only implementation is utilized, for example, when messages cannot be altered, corrupted, or replaced. An example is when the media is protected from tampering, but secrecy is required. This implementation is also suitable for cases such as, but not limited to, Tor, I2P, etc. when a sender remains anonymous so that the identity is unknown and therefore signature is not required. Another typical usage is hard drive encryption, folders/files encryption, database encryption, etc. 
     Signature+Encryption implementation is utilized, for example, when messages are first signed with the sender&#39;s private key, then encrypted with the receiver&#39;s public key before being transmitted to the receiver and finally decrypted by the receiver using the private key at the receiver. This kind of implementation can be found in most of the modern cryptographic frameworks and protocols such as, but not limited to, SSL, SSH, NPM, PGP/GPG, etc. 
     In accordance with yet another aspect of the present invention, a method of encrypting a message with the cryptographic engine of the present invention is provided in which data is encrypted with a first encryption engine and sent to a receiving system. The receiving system retrieves an available symmetric key of the sending system and creates a public/private key pair for encrypting and decrypting data. The receiving system encrypts the symmetric key using the public key of the public/private key pair. 
     In accordance with yet another aspect of the present invention, a method of encrypting a message with the cryptographic engine of the present invention is provided in which data is encrypted with a first encryption engine and sent to a receiving system. The receiving system retrieves an available symmetric key of the sending system and creates a public/private key pair for encrypting and decrypting data. The receiving system decrypts the data using the retrieved symmetric key and re-encrypts it using a new symmetric key followed by encrypting the new symmetric key using the public key of the public/private key pair. 
     In accordance with another aspect of the present invention, a Trusted Platform Module (TPM) is provided for creating a public key cryptographic platform that has increased security against cyber attacks using quantum computers. 
     In accordance with another aspect of the present invention, an USB secure key is provided for creating a public key cryptographic platform that has increased security against cyber attacks using quantum computers. 
     In accordance with yet another aspect of the present invention, a Post-Quantum Blockchain (“PQBC”) can be built to create a DLT that is safe in the post-quantum world of computing. This ensures sensitive data like financial transactions, privacy data, etc. can be trusted even in the post-quantum world of computing. 
     Aspects of the present invention can be applied to virtually any industry to increase security. Application to DLT is only one example of the applications. Optionally, encrypting data blocks in PQBC can further raise security. 
     There has thus been outlined, rather broadly, certain embodiments of an example of the invention in order that the detailed description thereof herein may be better understood, and in order that the present contribution to the art may be better appreciated. There are, of course, additional embodiments of an example of the invention that will be described below and which will form the subject matter of the claims appended hereto. 
     In this respect, before explaining at least one embodiment of an example of the invention in detail, it is to be understood that an example of the invention is not limited in its application to the details of construction and to the arrangements of the components set forth in the following description or illustrated in the drawings. The invention is capable of embodiments in addition to those described and of being practiced and carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein, as well as the abstract, are for the purpose of description and should not be regarded as limiting. 
     As such, those skilled in the art will appreciate that the conception upon which this disclosure is based may readily be utilized as a basis for the designing of other structures, methods and systems for carrying out the several purposes of the present invention. It is important, therefore, that the claims be regarded as including such equivalent constructions insofar as they do not depart from the spirit and scope of the present invention. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a system for carrying out a cryptographic method in accordance with one embodiment of the present invention whereby the system is used for encryption, decryption, generating digital signatures, verifying digital signatures, etc. 
         FIG. 2  is a block diagram of a system for carrying out a cryptographic method in accordance with an additional embodiment of the present invention whereby the system provides further security through use of a trusted platform module (TPM) or a universal serial bus (USB) interface. 
         FIG. 3  is a block diagram of a system for carrying out a cryptographic method in accordance with another embodiment of the invention whereby the system generates a public key and a private key based on a set of input parameters. 
         FIG. 4  is a block diagram of a system for carrying out a cryptographic method in accordance with another embodiment of the invention whereby a Post-Quantum Blockchain (PQBC) is created so that data security of the PQBC is strengthened against cyber attacks from quantum computers and classical computers. 
         FIG. 5  is a flowchart illustrating a process of generating a private key and a corresponding public key in a public key cryptographic device in accordance with an embodiment of the present invention. 
         FIG. 6  is a flowchart illustrating the process of encrypting data using a public key in the public key cryptographic device in accordance with an embodiment of the present invention. 
         FIG. 7  is a flowchart illustrating the process of decrypting an encrypted data using a corresponding private key in a public key cryptographic device in accordance with an embodiment of the present invention. 
         FIG. 8  is a flowchart illustrating the process of digital signing data using a private key in a public key cryptographic device in accordance with an embodiment of the present invention. 
         FIG. 9  is a flowchart illustrating the process of verifying a digital signature using a corresponding public key in a public key cryptographic device in accordance with an embodiment of the present invention. 
         FIG. 10  is a block diagram of a system for carrying out a process of sending encrypted contents to a recipient using the cryptographic method in accordance with one embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The invention will now be described with reference to the drawing figures in which like reference numerals refer to like parts throughout. In  FIG. 1 , a public key cryptographic device  100  in accordance with an exemplary embodiment of the invention is depicted. The cryptographic device  100  to receives an encryption key from memory  102 , which can be a public key or private key. The cryptographic device also receives from an input device  104 , data that is to be encrypted. The data can include, but is not limited to, a message vector to be securely transmitted from a sender to a receiver, or data from a network interface, a data storage device such as a hard drive, a key board, and the like. As described below, the data to be encrypted can also be the hash value of data to be digitally signed. 
     The encryption key and encrypted data may be received from inside a computing device, such as a personal computer, from one or more devices within a network or from third party devices outside the network. As described in more detail below, it will be readily understood that the public key cryptographic device can be any device capable of performing the processes described herein whether integrated into a single semiconductor package or distributed amongst several semiconductor devices contained within a single computer or server or distributed over multiple devices within one or more networks. 
     The cryptographic device  100  includes an input/output device  106 , which can, for example, be a network communication interface, for receiving the plain data from the input device  104  and receiving the encryption key. The plain data and encryption key are then forwarded to an Input/Output Bridge  108  and a Memory Bridge  110  for storage in system memory  112 . In exemplary embodiments the System Memory  112  may contain operating instructions such as, but not limited to, the Operating System  114 . In addition to the operating system as well as other operating instructions  114  that are stored in system memory  112 , the system memory includes the processing instructions of a cryptographic engine  116 . The cryptographic engine  116  provides the operational instructions for the cryptographic functions such as encryption, decryption, digital signature, verification of digital signature, etc. 
     The cryptographic processing of the encrypted data is performed in the CPU  118  that is linked to system memory  112  via a Memory Bus. The CPU  118  can be implemented as a parallel co-processor, a field programmable gate array (FPGA), microprocessor, or the like, as is well understood. 
     Where all components of the system are contained within a single device, as depicted in  FIG. 1 , the cryptographic device  100  can be implemented as a single purpose computing device, e.g., a special device performing one or more special cryptography function like a secure key device, a credit card chip, passport chip, etc.) Alternatively, the components and functioning depicted in  FIG. 1  can be can be distributed within a multiple purpose computing device, e.g., a general computer or server, or distributed over multiple devices within a network. For example, the functioning can be implemented on a cluster of server computers in a manner that is well-known. 
     The embodiment of  FIG. 1  can be implemented on a computer network such as the Internet that is strengthened against cyber attack from both classical computers and quantum computers and has a manageable key size and improved computational efficiency using a variant of the McEliece and Niederreiter schemes. In the classical McEliece and Niederreiter algorithms, the scheme parameters are determined by two key elements m and t and the error correcting code is considered in the classical, i.e., un-weighted, Hamming metric. In one embodiment of the scheme of the present application there is significant flexibility in choosing the parameter of the code length n based on a third key parameter r and the use of Goppa codes in a weighted Hamming metric. In this embodiment, a special type of locator set, L*, is used that is a set of rational functions of degree not greater than r where r is greater than 1, and with coefficients from a finite field GF(2 m ). This is contrasted with the classical scheme, in which the elements of the field GF(2 m ) are used as the locator set. This change in the locator set significantly increases the length of the code, while the calculations remain in the field GF(2 m ). 
     In this embodiment, a special representation of the parity check matrix H, and the generator matrix G of the code, a special selection of the error vector, and/or a special selection of the codeword presentation by the additional field(s) inclusion are utilized. In an embodiment a parity check matrix H is generated for an n, k, d binary generalized (L, G) code wherein n, k, and d, are positive integers, n is a code length, k is a number of information symbols and d is a minimal distance n≤Σ i=1   r l 2     m   (i), k≥n−tm. Where l 2     m   (i) is a number of irreducible polynomials of degree i with coefficients from GF(2 m ). It is also possible to present transformation A×H×P=H* (or S×G×P=G*) as a special permutation of the support set L. Therefore, matrix G* or H* can be obtained directly, without matrix S or A and P, from L* and G(x), where L* is a special secret permutation of support set L. In such case we can interpret L* as a second part of a secret key. This embodiment of the invention can be applied to make changes in the main components of, including, but not limited to, the encryption and signature schemes. 
     In this embodiment, by using the L* support set directly instead of L with matrix S and P, we can obtain the following variant of McEliece scheme:
         Private key: (Decoding algorithm, L*, G(x))   Public key: G*   Encryption: Let m be a k-bit message, and let e be a random n-bit vector with Hamming weight W H (e)≤t. Then c=m×G*⊕e is a ciphertext.   Decryption: Obtaining m by using decoding algorithm (error correcting) with knowledge L* and G.       

     In the Niederreiter scheme, by using the two matrices and parity check matrix H, obtained from L and G(x), a public key matrix H*=A×H×P is calculated. As with the McEliece scheme, by using the L* support set directly instead of L with matrix A and P, we can obtain the following variant of Niederreiter scheme:
         Private key: (Decoding algorithm, L*, G(x))   Public key: H*   Encryption: Let m be a message, with Hamming weight W H (e)≤t. Then c=m×H* T  is a ciphertext.   Decryption: Obtaining m by using decoding algorithm (error correcting) with knowledge L* and G(x).       

     This implementation allows for: 1) the expansion of the selection of a support set, thereby expanding the available private keys; 2) use of rational functions of degree greater than one to keep the calculation in a finite field with a comparable code length. For example, for rational functions of degree 2 with coefficients from the field GF(2 m ), the code length is n=2 2m−1 +2 m−1 . The practical benefits of using rational functions with different degree are: 1) reducing the amount of CPU cycles needed in the encryption, decryption, and key generation processes; and 2) increasing the security for codes with the same parameters (n, k, d), as in classical Goppa codes. 
     The generalized (L, G) code of an embodiment of the present invention is characterized by a set L where the proper rational functions of F 2     m   [x] are chosen whose denominators are various irreducible polynomials from F 2     m   [x] with degree less than or equal r (r&gt;1), and whose numerators are formal derivatives of the denominators. 
     In an embodiment of the invention, a special support set L is used as a second part of the private secret key in the McEliece and Niederreiter method. In this embodiment, we have the following additional definitions: 
     Definition #5: Support set L is defined as follows: 
     
       
         
           
             
               L 
               = 
               
                 { 
                 
                   
                     
                       
                         f 
                         1 
                         ′ 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     
                       
                         f 
                         1 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                   , 
                   
                     
                       
                         f 
                         2 
                         ′ 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     
                       
                         f 
                         2 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     
                       
                         f 
                         n 
                         ′ 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     
                       
                         f 
                         n 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                 
                 } 
               
             
             , 
           
         
       
     
     where ƒ′ i (x) is a formal derivative of ƒ i (x) in GF(2 m ) and ƒ i (x)=x l     i   +c l     i     −1,i x l     i     −1 +. . . c 1,i x+c 0,i ,c j,i ϵGF(2 m ), gcd(f i (x), f j (x))=1, gcd(f i (x), G(x))=1, ∀i, j, i≠j, deg G(x)=t. 
     Definition #6: Binary vector a=(a 1 , a 2 , . . . , a n ) is a codeword of generalized (L, G) code if and only if the following equality is satisfied: 
     
       
         
           
             
               
                 ∑ 
                 
                   i 
                   = 
                   1 
                 
                 n 
               
                
               
                 
                   a 
                   i 
                 
                  
                 
                   
                     
                       f 
                       i 
                       ′ 
                     
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   
                     
                       f 
                       i 
                     
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                 
               
             
             = 
             
               0 
                
               mod 
                
               
                   
               
                
               
                 G 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
           
         
       
     
     For such codes the design bound for the minimum distance: 
     
       
         
           
             
               
                 d 
                 G 
               
               ≥ 
               
                 
                   
                     2 
                      
                     t 
                   
                   + 
                   1 
                 
                 l 
               
             
             , 
             
               l 
               = 
               
                 max 
                  
                 
                   l 
                   i 
                 
               
             
           
         
       
     
     and the decoding algorithm corresponding to it is determined. To construct a parity check matrix for such generalized (L, G) code the following presentation for rational functions 
     
       
         
           
             
               
                 f 
                 i 
                 ′ 
               
                
               
                 ( 
                 x 
                 ) 
               
             
             
               
                 f 
                 i 
               
                
               
                 ( 
                 x 
                 ) 
               
             
           
         
       
     
     by modulo G(x) is used: 
     
       
         
           
             
               
                 
                   
                     f 
                     i 
                     ′ 
                   
                    
                   
                     ( 
                     x 
                     ) 
                   
                 
                 
                   
                     f 
                     i 
                   
                    
                   
                     ( 
                     x 
                     ) 
                   
                 
               
               = 
               
                 
                   
                     s 
                     i 
                   
                    
                   
                     ( 
                     x 
                     ) 
                   
                 
                 = 
                 
                   
                     
                       b 
                       
                         i 
                         , 
                         
                           t 
                           - 
                           1 
                         
                       
                     
                      
                     
                       x 
                       
                         t 
                         - 
                         1 
                       
                     
                   
                   + 
                   
                     
                       b 
                       
                         i 
                         , 
                         
                           t 
                           - 
                           2 
                         
                       
                     
                      
                     
                       x 
                       
                         t 
                         - 
                         2 
                       
                     
                   
                   + 
                   
                     
                       … 
                       · 
                       
                         + 
                         
                           b 
                           
                             i 
                             , 
                             1 
                           
                         
                       
                     
                      
                     
                       x 
                       1 
                     
                   
                   + 
                   
                     
                       b 
                       
                         i 
                         , 
                         0 
                       
                     
                      
                     
                       
                         mod 
                          
                         G 
                       
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                   
                 
               
             
             , 
             
               
 
             
              
             
               
                 b 
                 
                   i 
                   , 
                   j 
                 
               
               ∈ 
               
                 G 
                  
                 
                   F 
                    
                   
                     ( 
                     
                       2 
                       m 
                     
                     ) 
                   
                 
               
             
           
         
       
     
     The equation for the generalized Goppa code can then be rewritten as: 
     
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                       
                         a 
                         i 
                       
                        
                       
                         
                           
                             f 
                             i 
                             ′ 
                           
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                         
                           
                             f 
                             i 
                           
                            
                           
                             ( 
                             x 
                             ) 
                           
                         
                       
                     
                   
                   = 
                     
                    
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       n 
                     
                      
                     
                       
                         a 
                         i 
                       
                        
                       
                         
                           s 
                           i 
                         
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 
                   = 
                     
                    
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           b 
                           
                             i 
                             , 
                             
                               t 
                               - 
                               1 
                             
                           
                         
                          
                         
                           x 
                           
                             t 
                             - 
                             1 
                           
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           b 
                           
                             i 
                             , 
                             
                               t 
                               - 
                               2 
                             
                           
                         
                          
                         
                           x 
                           
                             t 
                             - 
                             2 
                           
                         
                       
                     
                     + 
                     
                       … 
                       · 
                       + 
                     
                   
                 
               
             
             
               
                 
                     
                    
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           b 
                           
                             i 
                             , 
                             1 
                           
                         
                          
                         
                           x 
                           1 
                         
                       
                     
                     + 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         n 
                       
                        
                       
                         
                           a 
                           i 
                         
                          
                         
                           b 
                           
                             i 
                             , 
                             0 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 
                   
                     = 
                       
                      
                     
                       0 
                        
                       mod 
                        
                       
                           
                       
                        
                       
                         G 
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                     
                   
                   , 
                 
               
             
           
         
       
     
     From this equation a parity check matrix H is obtained: 
     
       
         
           
             H 
             = 
             
               [ 
               
                 
                   
                     
                       b 
                       
                         1 
                         , 
                         
                           t 
                           - 
                           1 
                         
                       
                     
                   
                   
                     
                       b 
                       
                         2 
                         , 
                         
                           t 
                           - 
                           1 
                         
                       
                     
                   
                   
                     … 
                   
                   
                     
                       b 
                       
                         n 
                         , 
                         
                           t 
                           - 
                           1 
                         
                       
                     
                   
                 
                 
                   
                     ⋮ 
                   
                   
                     ⋮ 
                   
                   
                     ⋱ 
                   
                   
                     ⋮ 
                   
                 
                 
                   
                     
                       b 
                       
                         1 
                         , 
                         0 
                       
                     
                   
                   
                     
                       b 
                       
                         2 
                         , 
                         0 
                       
                     
                   
                   
                     … 
                   
                   
                     
                       b 
                       
                         n 
                         , 
                         0 
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
     From this parity check matrix we can obtain a generator matrix G for the generalized (L, G) code and by using matrix S and P to calculate the public key matrix G*=S×G×P. 
     In another embodiment we can also use the fractions 
     
       
         
           
             
               
                 f 
                 i 
                 ′ 
               
                
               
                 ( 
                 x 
                 ) 
               
             
             
               
                 f 
                 i 
               
                
               
                 ( 
                 x 
                 ) 
               
             
           
         
       
     
     with different degrees of ƒ i (x) for support set L. By using irreducible polynomials ƒ(x) with degree not greater than r for support set we can obtain a generalized Goppa code with codeword length n≤Σ i=1   r l 2     m   (i), where l 2     m   (i) is a number of irreducible polynomials of degree i with coefficients from GF(2 m ). 
     The following two examples are provided for illustration purposes: 
     Example 1 
     In this example m=6 and r=2. 
     
       
         
           
             
               
                 Since 
                  
                 
                     
                 
                  
                 
                   
                     I 
                     
                       2 
                       6 
                     
                   
                    
                   
                     ( 
                     1 
                     ) 
                   
                 
               
               = 
               64 
             
             , 
             
               
                 
                   I 
                   
                     2 
                     6 
                   
                 
                  
                 
                   ( 
                   2 
                   ) 
                 
               
               = 
               
                 
                   
                     2 
                     
                       1 
                        
                       2 
                     
                   
                   - 
                   
                     2 
                     6 
                   
                 
                 2 
               
             
           
         
       
     
     we obtain n=2048+32=2080. Let d=61, t=30 then we have k≥2080−60·6=1720. 
     Example 2 
     For l=2 and ƒ i (x)=(x−β i )(x−β i   2     m   ), β i ∈GF(2 2m )\GF(2 m ), G(x) which is an irreducible polynomial from the polynomial ring F 2     m   [x]. The parity check matrix for this example is: 
     
       
         
           
             
               1 
               
                 x 
                 - 
                 β 
               
             
             = 
             
               
                 
                   
                     G 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   - 
                   
                     G 
                      
                     
                       ( 
                       β 
                       ) 
                     
                   
                 
                 
                   x 
                   - 
                   β 
                 
               
                
               
                 
                   G 
                    
                   
                     ( 
                     β 
                     ) 
                   
                 
                 
                   - 
                   1 
                 
               
                
               mod 
                
               
                   
               
                
               
                 G 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
           
         
       
       
         
           and 
         
       
       
         
           
             
               
                 β 
                 + 
                 
                   β 
                   
                     2 
                     m 
                   
                 
               
               
                 
                   ( 
                   
                     x 
                     - 
                     β 
                   
                   ) 
                 
                  
                 
                   ( 
                   
                     x 
                     - 
                     
                       β 
                       
                         2 
                         m 
                       
                     
                   
                   ) 
                 
               
             
             = 
             
               
                 
                   
                     
                       G 
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     - 
                     
                       G 
                        
                       
                         ( 
                         β 
                         ) 
                       
                     
                   
                   
                     x 
                     - 
                     β 
                   
                 
                  
                 
                   
                     G 
                      
                     
                       ( 
                       β 
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
               
               + 
               
                 
                   
                     
                       G 
                        
                       
                         ( 
                         x 
                         ) 
                       
                     
                     - 
                     
                       G 
                        
                       
                         ( 
                         
                           β 
                           
                             2 
                             m 
                           
                         
                         ) 
                       
                     
                   
                   
                     x 
                     - 
                     
                       β 
                       
                         2 
                         m 
                       
                     
                   
                 
                  
                 
                   
                     G 
                      
                     
                       ( 
                       
                         β 
                         
                           2 
                           m 
                         
                       
                       ) 
                     
                   
                   
                     - 
                     1 
                   
                 
                  
                 mod 
                  
                 
                     
                 
                  
                 
                   G 
                    
                   
                     ( 
                     x 
                     ) 
                   
                 
               
             
           
         
       
       
         
           
             
               
                 
                   
                     G 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   - 
                   
                     G 
                      
                     
                       ( 
                       β 
                       ) 
                     
                   
                 
                 
                   x 
                   - 
                   β 
                 
               
               = 
               
                 
                   
                     g 
                     t 
                   
                    
                   
                     ( 
                     
                       
                         x 
                         
                           t 
                           - 
                           1 
                         
                       
                       + 
                       
                         
                           x 
                           
                             t 
                             - 
                             2 
                           
                         
                          
                         β 
                       
                       + 
                       … 
                       + 
                       
                         β 
                         
                           t 
                           - 
                           1 
                         
                       
                     
                     ) 
                   
                 
                 + 
                 
                   
                     g 
                     
                       t 
                       - 
                       1 
                     
                   
                    
                   
                     ( 
                     
                       
                         x 
                         
                           t 
                           - 
                           2 
                         
                       
                       + 
                       
                         
                           x 
                           
                             t 
                             - 
                             3 
                           
                         
                          
                         β 
                       
                       + 
                       … 
                       + 
                       
                         β 
                         
                           t 
                           - 
                           2 
                         
                       
                     
                     ) 
                   
                 
                 + 
                 
                   … 
                    
                   
                       
                   
                    
                   
                     
                       g 
                       2 
                     
                      
                     
                       ( 
                       
                         x 
                         + 
                         β 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   g 
                   1 
                 
               
             
             , 
             
               
 
             
              
             
               
                 where 
                  
                 
                     
                 
                  
                 
                   G 
                    
                   
                     ( 
                     x 
                     ) 
                   
                 
               
               = 
               
                 
                   ∑ 
                   
                     i 
                     = 
                     0 
                   
                   t 
                 
                  
                 
                   
                     g 
                     i 
                   
                    
                   
                     x 
                     i 
                   
                 
               
             
             , 
             
               
                 g 
                 i 
               
               ∈ 
               
                 G 
                  
                 
                   F 
                    
                   
                     ( 
                     
                       2 
                       m 
                     
                     ) 
                   
                 
               
             
             , 
             
               
                 g 
                 t 
               
               ≠ 
               0 
             
             , 
             
               
                 
                   g 
                   0 
                 
                 ≠ 
                 
                   0 
                    
                   
                     
 
                   
                    
                   and 
                    
                   
                     
 
                   
                    
                   
                     
                       
                         G 
                          
                         
                           ( 
                           x 
                           ) 
                         
                       
                       - 
                       
                         G 
                          
                         
                           ( 
                           
                             β 
                             
                               2 
                               m 
                             
                           
                           ) 
                         
                       
                     
                     
                       x 
                       - 
                       
                         β 
                         
                           2 
                           m 
                         
                       
                     
                   
                 
               
               = 
               
                 
                   
                     g 
                     t 
                   
                    
                   
                     ( 
                     
                       
                         x 
                         
                           t 
                           - 
                           1 
                         
                       
                       + 
                       
                         
                           x 
                           
                             t 
                             - 
                             2 
                           
                         
                          
                         
                           β 
                           
                             2 
                             m 
                           
                         
                       
                       + 
                       … 
                       + 
                       
                         β 
                         
                           
                             2 
                             m 
                           
                            
                           
                             ( 
                             
                               t 
                               - 
                               1 
                             
                             ) 
                           
                         
                       
                     
                     ) 
                   
                 
                 + 
                 
                   
                     g 
                     
                       t 
                       - 
                       1 
                     
                   
                    
                   
                     ( 
                     
                       
                         x 
                         
                           t 
                           - 
                           2 
                         
                       
                       + 
                       
                         
                           x 
                           
                             t 
                             - 
                             3 
                           
                         
                          
                         
                           β 
                           
                             2 
                             m 
                           
                         
                       
                       + 
                       … 
                       + 
                       
                         β 
                         
                           
                             2 
                             m 
                           
                            
                           
                             ( 
                             
                               t 
                               - 
                               2 
                             
                             ) 
                           
                         
                       
                     
                     ) 
                   
                 
                 + 
                 
                   … 
                    
                   
                       
                   
                    
                   
                     
                       g 
                       2 
                     
                      
                     
                       ( 
                       
                         x 
                         + 
                         
                           β 
                           
                             2 
                             m 
                           
                         
                       
                       ) 
                     
                   
                 
                 + 
                 
                   g 
                   1 
                 
               
             
             , 
           
         
       
     
     The coefficients at x t−2 ,x t−2 , . . . ,x,1 in the sum 
     
       
         
           
             
               
                 
                   
                     G 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   - 
                   
                     G 
                      
                     
                       ( 
                       β 
                       ) 
                     
                   
                 
                 
                   x 
                   - 
                   β 
                 
               
                
               
                 
                   G 
                    
                   
                     ( 
                     β 
                     ) 
                   
                 
                 
                   - 
                   1 
                 
               
             
             + 
             
               
                 
                   
                     G 
                      
                     
                       ( 
                       x 
                       ) 
                     
                   
                   - 
                   
                     G 
                      
                     
                       ( 
                       
                         β 
                         
                           2 
                           m 
                         
                       
                       ) 
                     
                   
                 
                 
                   x 
                   - 
                   
                     β 
                     
                       2 
                       m 
                     
                   
                 
               
                
               
                 
                   G 
                    
                   
                     ( 
                     
                       β 
                       
                         2 
                         m 
                       
                     
                     ) 
                   
                 
                 
                   - 
                   1 
                 
               
             
           
         
       
       
         
           
             
               
                 x 
                 
                   t 
                   - 
                   1 
                 
               
                
               
                 : 
               
                
               
                 ( 
                 
                   
                     
                       G 
                        
                       
                         ( 
                         β 
                         ) 
                       
                     
                     
                       - 
                       1 
                     
                   
                   + 
                   
                     
                       G 
                        
                       
                         ( 
                         
                           β 
                           
                             2 
                             m 
                           
                         
                         ) 
                       
                     
                     
                       - 
                       1 
                     
                   
                 
                 ) 
               
                
               
                 g 
                 t 
               
             
             , 
             
               
 
             
              
             
               
                 
                   x 
                   
                     t 
                     - 
                     2 
                   
                 
                  
                 
                   : 
                 
                  
                 
                   ( 
                   
                     
                       
                         G 
                          
                         
                           ( 
                           β 
                           ) 
                         
                       
                       
                         - 
                         1 
                       
                     
                     + 
                     
                       
                         G 
                          
                         
                           ( 
                           
                             β 
                             
                               2 
                               m 
                             
                           
                           ) 
                         
                       
                       
                         - 
                         1 
                       
                     
                   
                   ) 
                 
                  
                 
                   g 
                   
                     t 
                     - 
                     1 
                   
                 
               
               + 
               
                 
                   ( 
                   
                     
                       β 
                        
                       
                         
                           G 
                            
                           
                             ( 
                             β 
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         β 
                         
                           2 
                           m 
                         
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   
                     g 
                     t 
                   
                   . 
                   
                     
 
                   
                    
                   
                     x 
                     
                       t 
                       - 
                       3 
                     
                   
                 
                  
                 
                   : 
                 
                  
                 
                   ( 
                   
                     
                       
                         G 
                          
                         
                           ( 
                           β 
                           ) 
                         
                       
                       
                         - 
                         1 
                       
                     
                     + 
                     
                       
                         G 
                          
                         
                           ( 
                           
                             β 
                             
                               2 
                               m 
                             
                           
                           ) 
                         
                       
                       
                         - 
                         1 
                       
                     
                   
                   ) 
                 
                  
                 
                   g 
                   
                     t 
                     - 
                     2 
                   
                 
               
               + 
               
                 
                   ( 
                   
                     
                       β 
                        
                       
                         
                           G 
                            
                           
                             ( 
                             β 
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         β 
                         
                           2 
                           m 
                         
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   g 
                   
                     t 
                     - 
                     1 
                   
                 
               
               + 
               
                 
                   ( 
                   
                     
                       
                         β 
                         2 
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             β 
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         β 
                         
                           2 
                           · 
                           
                             2 
                             m 
                           
                         
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   g 
                   t 
                 
               
             
             , 
             
               
 
             
              
             
               
                 
                   x 
                   0 
                 
                  
                 
                   : 
                 
                  
                 
                   ( 
                   
                     
                       
                         G 
                          
                         
                           ( 
                           β 
                           ) 
                         
                       
                       
                         - 
                         1 
                       
                     
                     + 
                     
                       
                         G 
                          
                         
                           ( 
                           
                             β 
                             
                               2 
                               m 
                             
                           
                           ) 
                         
                       
                       
                         - 
                         1 
                       
                     
                   
                   ) 
                 
                  
                 
                   g 
                   1 
                 
               
               + 
               
                 
                   ( 
                   
                     
                       β 
                        
                       
                         
                           G 
                            
                           
                             ( 
                             β 
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         β 
                         
                           2 
                           m 
                         
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   g 
                   2 
                 
               
               + 
               … 
               + 
               
                 
                   ( 
                   
                     
                       
                         β 
                         
                           t 
                           - 
                           1 
                         
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             β 
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     
                       
                         β 
                         
                           
                             ( 
                             
                               t 
                               - 
                               1 
                             
                             ) 
                           
                           · 
                           
                             2 
                             m 
                           
                         
                       
                        
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   ) 
                 
                  
                 
                   
                     g 
                     t 
                   
                   . 
                 
               
             
           
         
       
     
     A parity check matrix H is defined by: 
     
       
         
           
             H 
             = 
             
               [ 
               
                 
                   
                     
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               1 
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                       + 
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               1 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   
                     
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               2 
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                       + 
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               1 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                   
                     … 
                   
                   
                     
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               n 
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                       + 
                       
                         
                           G 
                            
                           
                             ( 
                             
                               β 
                               1 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           β 
                           1 
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 1 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           β 
                           1 
                           
                             2 
                             m 
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 1 
                                 
                                   2 
                                   m 
                                 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           β 
                           2 
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 2 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           β 
                           2 
                           
                             2 
                             m 
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 2 
                                 
                                   2 
                                   m 
                                 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                     
                   
                   
                     … 
                   
                   
                     
                       
                         
                           β 
                           n 
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 n 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           
                             β 
                             n 
                             
                               2 
                               m 
                             
                           
                            
                           
                             ( 
                             
                               β 
                               n 
                               
                                 2 
                                 m 
                               
                             
                             ) 
                           
                         
                         
                           - 
                           1 
                         
                       
                     
                   
                 
                 
                   
                     
                         
                     
                   
                   
                     ⋮ 
                   
                   
                     
                         
                     
                   
                   
                     
                         
                     
                   
                 
                 
                   
                     
                       
                         
                           β 
                           1 
                           
                             t 
                             - 
                             1 
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 1 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           β 
                           1 
                           
                             
                               ( 
                               
                                 t 
                                 - 
                                 1 
                               
                               ) 
                             
                              
                             
                               2 
                               m 
                             
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 1 
                                 
                                   2 
                                   m 
                                 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           β 
                           2 
                           
                             t 
                             - 
                             1 
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 2 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           β 
                           2 
                           
                             
                               ( 
                               
                                 t 
                                 - 
                                 1 
                               
                               ) 
                             
                              
                             
                               2 
                               m 
                             
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 2 
                                 
                                   2 
                                   m 
                                 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                     
                   
                   
                     … 
                   
                   
                     
                       
                         
                           β 
                           n 
                           
                             t 
                             - 
                             1 
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 n 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                       + 
                       
                         
                           β 
                           n 
                           
                             
                               ( 
                               
                                 t 
                                 - 
                                 1 
                               
                               ) 
                             
                              
                             
                               2 
                               m 
                             
                           
                         
                          
                         
                           
                             G 
                              
                             
                               ( 
                               
                                 β 
                                 n 
                                 
                                   2 
                                   m 
                                 
                               
                               ) 
                             
                           
                           
                             - 
                             1 
                           
                         
                       
                     
                   
                 
               
               ] 
             
           
         
       
     
     By way of the foregoing, a special generalization of Goppa codes is constructed with a support set L as a set of rational functions 
     
       
         
           
             
               
                 
                   f 
                   i 
                   ′ 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               
                 
                   f 
                   i 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
             . 
           
         
       
     
     The special generalization of Goppa codes is neither a Reed Solomon (RS) code nor an alternant code. 
     For decoding these generalized Goppa codes, the Goppa polynomial G(x) and support set L must be known. A classical decoding algorithm (Euclidean, Berlekamp-Massey, Patterson, etc.) can then be used. 
     Using a set of position numerators of degree greater than 1, the degree of Galois field extension m for obtaining a support set L is reduced, thereby reducing the complexity of the calculations in the decoding process. The degree m of the field extension is reduced by r times, where r is the degree of the position numerators. 
     By way of example, a scheme (2060, 1720, t=30) can be constructed close in parameters to the classical McEliece and Niederreiter (2048, 1718, t=30) scheme by using elements from the Galois field GF(2 6 ) instead of the field GF(2 11 ) used in the original scheme. Therefore in the scheme of this example, all calculations in the decoding procedure can be done in the Galois field GF(2 6 ) with only 2 6  elements instead of the Galois field GF(2 11 ) with 2 11  elements required. 
     In the embodiment depicted in  FIG. 1 , after the cryptographic operations are performed, the result  120  of this computation is returned to the input/output device  106  and output from the cryptographic device  100 . An embodiment in accordance with one aspect of the present invention provides a public key cryptographic system and method that can be used to build a highly secure system for data storage, access, encryption, decryption, digital signing, digital signature verification, etc. 
       FIG. 2  depicts an alternative embodiment of a system in which the foregoing encryption method can be employed. In the system of  FIG. 2 , the cryptographic engine  116  is implemented on a Chip  130 , such as field programmable gate array (FPGA), operating as an independent processing module  132  such as, but not limited to, a TPM-Trusted Platform Module (TPM) or a Universal Serial Bus (USB) Module, rather than being stored in system memory. An advantage of implementing the cryptographic engine  116  on an independent processing module  132  is that the private key  124  is stored on the chip  130  and therefore separated from the operating system contained in the System Memory  114 . This provides an added layer of security as the Private Key  124  is not directly exposed to the file system of the operating system which can be compromised as can the system memory  114 . 
     In the alternative embodiment of  FIG. 3 , the public key cryptographic device  100  generates a private key  124  and its corresponding public key  126  using an input list of parameters  122 . As previously described, the public key  126  ( FIG. 3 ) can be used in encryption and decryption operations. In one embodiment, the public key cryptographic device  100  of  FIG. 3  can be implemented as described in connection with  FIG. 1  except for the instructions being implemented by the cryptographic engine  116 . 
     An application of the foregoing systems is depicted in  FIG. 4 , in which the cryptographic engine can be applied to create a Post-Quantum Blockchain (PQBC)  140 . In the exemplary embodiment of  FIG. 4 , the last data block  152  in the PQBC  140  is created by participant node  146  preceded by the data block  150  created by participant node  144  and further preceded by the data block  148  created by participant node  142 . All participant nodes use a public key cryptographic device  100  for cryptographic functions. For example, when node  146  creates the last data block  152 , node  146  digitally signs the block and records the hash value of the previous data block  150  in the PQBC using a digital signature function in the public key cryptographic device  100 . Similarly the other participant nodes  142  and  144  perform the same steps when creating a new data block. Transaction data inside each of the data blocks can optionally be encrypted using the encryption function in the public key cryptographic device  100 . End point security can be further enhanced by employing the system of  FIG. 3  in which the private key  124  is maintained separate from the operating system. 
     Alternative instructions that can be implemented by the device of  FIG. 3  are depicted in connection with  FIG. 5  in which a method of generating a private and public key pair is shown. The private key  124  and its corresponding public key  126  are used for different functions in the public key cryptographic device  100  such as, but not limited to, encryption, decryption, digital signing, and digital signature verification. The code parameter selection engine  132  chooses m, r, t, n with the property that code length n≤Σ i=1   r l 2     m   (i), t&gt;r and wherein: m is the degree of the field expansion GF(2 m ) in which the operations will be performed during decoding and signature calculations, and which will thereby determine the complexity of the circuit calculations; r is the maximum degree of the denominator of a rational function over F 2     m   [x] in the set of L; and t is the number of errors in the weighted Hamming metric that can be corrected by the code. There is no limit on how m, r, and t are selected. 
     For illustration purposes, m determines the Galois field GF(2 m ) used in the calculations while r and m determine the size of support set L. Since code length n, r, and t determine a minimal distance of the code, therefore these parameters also determine the number of errors that could be corrected by such error correcting code. The private support set L generator  160  chooses or generates n elements (rational functions 
     
       
         
           
             
               
                 
                   f 
                   i 
                   ′ 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               
                 
                   f 
                   i 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
             ) 
           
         
       
     
     to support set L. For the sake of clarity, f i (x) should be an irreducible polynomial of degree r. There are well-known methods to generate such polynomial, which are outside the scope of this invention. The Private Goppa Polynomial G(x) processor  162  chooses and/or generates primitive polynomial degree t from F 2     m   [x]. For the sake of clarity, G(x) is an irreducible (separable) polynomial of degree t with coefficients from GF(2 m ). There are well-known methods to generate such polynomial, any of which can be used. The two elements G and L of Goppa code are defined unequally. Therefore, by using the (f i (x)) −1  mod G(x) generator  164  and obtaining r i (x) using the i-th column r i (x) of parity check matrix H generator  166 , it is now possible to use the i-th binary column of parity check matrix H generator  168  to obtain a number of binary elements equal to the multiplication of t and m (tm), and collect all necessary n columns and tm binary rows n i1 , r i2 , . . . , r imt  of parity check matrix H from the i-th column r i (x)∈GF(2 m ), deg r i (x)=t−1 during n cycles of the process of steps  160 ,  164 , and  166 . For the sake of clarity, r i (x)=ƒ′ i (x)(ƒ i (x)) −1  mod G(x), where ƒ′ i (x) is formal derivative of ƒi(x). The binary parity check matrix H  170  is represented as a tm×n binary matrix. Together with a randomly selected mt×mt non-singular matrix S  172  and another randomly selected n×n permutation matrix P  174  the public key  126  can be obtained by performing a matrix multiplication of H*=S×H×P. On the other hand, the private key  124  can be obtained as K={S, P, L, G(x)}. 
     A method of encrypting a message in accordance with an embodiment of the present invention is depicted in  FIG. 6  in which the Message  176  is presented as a binary vector e of length n and Hamming weight no more than t/r. The Encrypted Message  178  is obtained as an encrypted vector w of length mt by using matrix multiplication of the public key  126  and the message  176  whereby w=e×(H*) T . 
     A method of decrypting an encrypted message in accordance with a preferred embodiment of the invention is depicted in  FIG. 7  in which the encrypted message  180  of length mt is decoded by decoder  182  using a Berlekamp-Massey algorithm or an extended Euclidean algorithm or Patterson algorithm. The private key  124  and the elements of field GF(2 m )  186  are provided to the decoder  182  for the decoding process. For the sake of clarification, in the private key  124  G(x) is an irreducible polynomial of degree t with coefficients from the field GF(2 m ) with support set L as a set of rational functions 
     
       
         
           
             
               
                 
                   f 
                   i 
                   ′ 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               
                 
                   f 
                   i 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
             . 
           
         
       
     
     The decoded message  184  is an information vector e of the length n and weight in the weighted Hamming metric less than or equal to t. 
     A method of obtaining a digital signature for input data, using the cryptographic device  100 , is depicted in  FIG. 8 . This method uses the secret Goppa code elements of a Goppa polynomial G(x) with support set L in a well-known digital signature generation process such as, but not limited to, the Courtois-Finiasz-Sendrier (CFS) signature scheme. Data  190  to be digitally signed is provided to a first hash process  192 . The resulting hash value h is used by a second hash process  194  to generate hash value H using h and i (H=hash(h∥i) where the length of H is mt bits) where i is a looping incremental value starting at 1. The second hash value H is then used by the decoder  196  in a decoding process based on elements of a Galois field GF(2 m )  198  and a private key  124  using an Berlekamp-Massey or Extended Euclidean algorithm. For the sake of clarification, in the private key  124 , G(x) is an irreducible polynomial of degree t with coefficients from the field GF(2 m ) with support set L as a set of rational functions 
     
       
         
           
             
               
                 
                   f 
                   i 
                   ′ 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
               
                 
                   f 
                   i 
                 
                  
                 
                   ( 
                   x 
                   ) 
                 
               
             
             . 
           
         
       
     
     The second hash process  194  and the decoder  196  are repeated with an incrementing i value until a successful decoding is reached. The resulting digital signature  120 , represented as {s,i}, consists of two elements: 1) a vector s of the length n and weight in the weighted Hamming metric of less than or equal to t; and 2) a parameter i equal to the number of the successful steps. 
     A method of verifying a digital signature for given data, in the cryptographic device  100 , is depicted in  FIG. 9 . In this embodiment, the digital signature  202  to be verified is represented as s*,i . The data  204 , which is signed by the digital signature  202 , is provided to a hash process  206  as w. Hash process  206  is operated so that the resulting hash value h*=Hash(h∥i), where Hash(w)=h and i is the parameter in the digital signature  202 . From the digital signature  202  we can obtain the signature vector s* of length n and weight less than or equal to t in the weighted Hamming metric. A binary vector h** of the length tm, h**=s*×(H*) T , can be obtained by using matrix multiplication of the public key  126  and the binary vector of the signature s from digital signature  202 . The determination between valid signature  208  and an invalid signature  210  can be obtained by comparing the value h** and h*. 
     A system and method of sending encrypted contents to a recipient system, whereby a recipient in not initially registered with a trusted third-party server that administers registration to use the public/private key infrastructure generated in accordance with the above described systems and methods. As a result, the sender cryptographic engine does not initially have access to the public key of the recipient&#39;s cryptographic engine, is depicted in  FIG. 10 . The system and method of  FIG. 10  can be implemented on any data transmission and communication system but will be described in an exemplary embodiment herein as implement in an email system. In accordance with this system and method, if a sender desires to send an encrypted email, the email client on the sender system will encrypt the email with a first encryption engine  300 . Examples of suitable first encryption engines include the AES symmetric encryption engine, although it will be understood that other encryption engines can also be used to achieve the purposes described herein. 
     In the exemplary embodiment described herein, the symmetric key is then stored in a location accessible by the recipient cryptographic engine  302 . In a preferred embodiment, the symmetric key is forwarded and stored at a trusted server which is accessible by the recipient system over the Internet. The encrypted data is then sent by the sender system email client to the email client on the recipient system  304  along with an invitation message with instructions on registering the recipient onto the system used by the sender. Upon registering onto the system used by the sender, the recipient system will query for the symmetric key. As will be understood, the trusted server can be a server associated with the sender system or can be an independent third-party server. Moreover, the invitation message can be included as part of the encrypted email message from the sender or can be provided separately by the sender or a third-party server that is administering the Public/Private encryption key system. In one embodiment, the sender may send the symmetric key to the trusted third party and, upon receipt of the symmetric key from the sender system, the trusted third-party server will communicated a registration request to the recipient system in order to access the symmetric key. 
     The recipient system will create a public/private key pair utilizing the cryptographic systems and engines described herein  306 . The recipient system will then encrypt the symmetric key provided by the sender system with the public key of the recipient. The recipient can then decrypt the symmetric key and use that to decrypt the email message 
     The recipient system can also provide the public key directly to the sender system for encryption of future emails or that public key can be stored at the trusted third-party for use by the sender system, as well as other systems utilizing the same cryptographic systems and engines, to encrypt data for the recipient system. As will be readily understood, alternative ways of creating the public/private key pair and making the public key of the recipient system available can also be utilized in accordance with the present system. 
     When the recipient system receives the symmetric key, it will encrypt it using the previously created public key  308  and store the encrypted symmetric key. The recipient system can now decrypt the data  310  by using the private key created in step  306  to access the symmetric key. As will be readily understood, in order to further increase security, the method of  FIG. 10  may be implemented such that the recipient system can decrypt the data using the symmetric key followed by the recipient system encrypting the data with a new symmetric key and then encrypting that new symmetric key with the public key in step  308 . It should be readily understood that the registration request system and method of  FIG. 10  allows the encryption systems described herein to be used for communications to recipients not yet registered to use these systems and thereby can be utilized to invite and add users to a network of systems equipped to encrypt communications with the cryptographic systems and engines described herein. 
     In order to further increase security, the sender may store the first symmetric key on its own computer in step  302 . When the recipient wishes to retrieve the first symmetric key in step  308 , it makes an outbound connection with the server and the server bridges an end-to-end communication session between the sender and the recipient to transfer the symmetric key from the sender computer to the recipient computer. 
     Although described as an ordered series of steps, it will be readily understood that various steps of the method depicted in  FIG. 10 , including, but not limited to, steps  302  and  304  and steps  306 , can be performed simultaneously or in reverse order. In addition, different ones of the steps may be combined with other steps, or a single step may be subdivided into two or more sub-steps, without departing from the spirit and scope of the invention. 
     Although specific embodiments of the invention have been set forth herein, it is not intended that those be limiting. It should be understood that alternate embodiments, including variations and modifications thereto as well as various other features or functions, can be added to the present invention without departing from the scope of the present invention.