Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  10 May 2011 
Place of Publication  Eindhoven 
Publisher  
Print ISBNs  9789038624761 
DOIs  
Publication status  Published  2011 
Fingerprint
Cite this
}
Curves, codes, and cryptography. / Peters, C.P.
Eindhoven : Technische Universiteit Eindhoven, 2011. 198 p.Research output: Thesis › Phd Thesis 1 (Research TU/e / Graduation TU/e)
TY  THES
T1  Curves, codes, and cryptography
AU  Peters, C.P.
PY  2011
Y1  2011
N2  This thesis deals with two topics: ellipticcurve cryptography and codebased cryptography. In 2007 ellipticcurve cryptography received a boost from the introduction of a new way of representing elliptic curves. Edwards, generalizing an example from Euler and Gauss, presented an addition law for the curves x2 + y2 = c2(1 + x2y2) over nonbinary fields. Edwards showed that every elliptic curve can be expressed in this form as long as the underlying field is algebraically closed. Bernstein and Lange found fast explicit formulas for addition and doubling in coordinates (X : Y : Z) representing (x, y) = (X/Z, Y/Z) on these curves, and showed that these explicit formulas save time in ellipticcurve cryptography. It is easy to see that all of these curves are isomorphic to curves x2 + y2 = 1 + dx2y2 which now are called "Edwards curves" and whose shape covers considerably more elliptic curves over a finite field than x2 + y2 = c2(1 + x2y2). In this thesis the Edwards addition law is generalized to cover all curves ax2 +y2 = 1+dx2y2 which now are called "twisted Edwards curves." The fast explicit formulas for addition and doubling presented here are almost as fast in the general case as they are for the special case a = 1. This generalization brings the speed of the Edwards addition law to every Montgomery curve. Tripling formulas for Edwards curves can be used for doublebase scalar multiplication where a multiple of a point is computed using a series of additions, doublings, and triplings. The use of doublebase chains for ellipticcurve scalar multiplication for elliptic curves in various shapes is investigated in this thesis. It turns out that not only are Edwards curves among the fastest curve shapes, but also that the speed of doublings on Edwards curves renders double bases obsolete for this curve shape. Elliptic curves in Edwards form and twisted Edwards form can be used to speed up the EllipticCurve Method for integer factorization (ECM). We show how to construct elliptic curves in Edwards form and twisted Edwards form with large torsion groups which are used by the EECMMPFQ implementation of ECM. Codebased cryptography was invented by McEliece in 1978. The McEliece publickey cryptosystem uses as public key a hidden Goppa code over a finite field. Encryption in McEliece’s system is remarkably fast (a matrixvector multiplication). This system is rarely used in implementations. The main complaint is that the public key is too large. The McEliece cryptosystem recently regained attention with the advent of postquantum cryptography, a new field in cryptography which deals with publickey systems without (known) vulnerabilities to attacks by quantum computers. The McEliece cryptosystem is one of them. In this thesis we underline the strength of the McEliece cryptosystem by improving attacks against it and by coming up with smallerkey variants. McEliece proposed to use binary Goppa codes. For these codes the most effective attacks rely on informationset decoding. In this thesis we present an attack developed together with Daniel J. Bernstein and Tanja Lange which uses and improves Stern’s idea of collision decoding. This attack is faster by a factor of more than 150 than previous attacks, bringing it within reach of a moderate computer cluster. We were able to extract a plaintext from a ciphertext by decoding 50 errors in a [1024, 524] binary code. The attack should not be interpreted as destroying the McEliece cryptosystem. However, the attack demonstrates that the original parameters were chosen too small. Building on this work the collisiondecoding algorithm is generalized in two directions. First, we generalize the improved collisiondecoding algorithm for codes over arbitrary fields and give a precise analysis of the running time. We use the analysis to propose parameters for the McEliece cryptosystem with Goppa codes over fields such as F31. Second, collision decoding is generalized to ballcollision decoding in the case of binary linear codes. Ballcollision decoding is asymptotically faster than any previous attack against the McEliece cryptosystem. Another way to strengthen the system is to use codes with a larger errorcorrection capability. This thesis presents "wild Goppa codes" which contain the classical binary Goppa codes as a special case. We explain how to encrypt and decrypt messages in the McEliece cryptosystem when using wild Goppa codes. The size of the public key can be reduced by using wild Goppa codes over moderate fields which is explained by evaluating the security of the "Wild McEliece" cryptosystem against our generalized collision attack for codes over finite fields. Codebased cryptography not only deals with publickey cryptography: a codebased hash function "FSB"was submitted to NIST’s SHA3 competition, a competition to establish a new standard for cryptographic hashing. Wagner’s generalized birthday attack is a generic attack which can be used to find collisions in the compression function of FSB. However, applying Wagner’s algorithm is a challenge in storagerestricted environments. The FSBday project showed how to successfully mount the generalized birthday attack on 8 nodes of the Coding and Cryptography Computer Cluster (CCCC) at Technische Universiteit Eindhoven to find collisions in the toy version FSB48 which is contained in the submission to NIST.
AB  This thesis deals with two topics: ellipticcurve cryptography and codebased cryptography. In 2007 ellipticcurve cryptography received a boost from the introduction of a new way of representing elliptic curves. Edwards, generalizing an example from Euler and Gauss, presented an addition law for the curves x2 + y2 = c2(1 + x2y2) over nonbinary fields. Edwards showed that every elliptic curve can be expressed in this form as long as the underlying field is algebraically closed. Bernstein and Lange found fast explicit formulas for addition and doubling in coordinates (X : Y : Z) representing (x, y) = (X/Z, Y/Z) on these curves, and showed that these explicit formulas save time in ellipticcurve cryptography. It is easy to see that all of these curves are isomorphic to curves x2 + y2 = 1 + dx2y2 which now are called "Edwards curves" and whose shape covers considerably more elliptic curves over a finite field than x2 + y2 = c2(1 + x2y2). In this thesis the Edwards addition law is generalized to cover all curves ax2 +y2 = 1+dx2y2 which now are called "twisted Edwards curves." The fast explicit formulas for addition and doubling presented here are almost as fast in the general case as they are for the special case a = 1. This generalization brings the speed of the Edwards addition law to every Montgomery curve. Tripling formulas for Edwards curves can be used for doublebase scalar multiplication where a multiple of a point is computed using a series of additions, doublings, and triplings. The use of doublebase chains for ellipticcurve scalar multiplication for elliptic curves in various shapes is investigated in this thesis. It turns out that not only are Edwards curves among the fastest curve shapes, but also that the speed of doublings on Edwards curves renders double bases obsolete for this curve shape. Elliptic curves in Edwards form and twisted Edwards form can be used to speed up the EllipticCurve Method for integer factorization (ECM). We show how to construct elliptic curves in Edwards form and twisted Edwards form with large torsion groups which are used by the EECMMPFQ implementation of ECM. Codebased cryptography was invented by McEliece in 1978. The McEliece publickey cryptosystem uses as public key a hidden Goppa code over a finite field. Encryption in McEliece’s system is remarkably fast (a matrixvector multiplication). This system is rarely used in implementations. The main complaint is that the public key is too large. The McEliece cryptosystem recently regained attention with the advent of postquantum cryptography, a new field in cryptography which deals with publickey systems without (known) vulnerabilities to attacks by quantum computers. The McEliece cryptosystem is one of them. In this thesis we underline the strength of the McEliece cryptosystem by improving attacks against it and by coming up with smallerkey variants. McEliece proposed to use binary Goppa codes. For these codes the most effective attacks rely on informationset decoding. In this thesis we present an attack developed together with Daniel J. Bernstein and Tanja Lange which uses and improves Stern’s idea of collision decoding. This attack is faster by a factor of more than 150 than previous attacks, bringing it within reach of a moderate computer cluster. We were able to extract a plaintext from a ciphertext by decoding 50 errors in a [1024, 524] binary code. The attack should not be interpreted as destroying the McEliece cryptosystem. However, the attack demonstrates that the original parameters were chosen too small. Building on this work the collisiondecoding algorithm is generalized in two directions. First, we generalize the improved collisiondecoding algorithm for codes over arbitrary fields and give a precise analysis of the running time. We use the analysis to propose parameters for the McEliece cryptosystem with Goppa codes over fields such as F31. Second, collision decoding is generalized to ballcollision decoding in the case of binary linear codes. Ballcollision decoding is asymptotically faster than any previous attack against the McEliece cryptosystem. Another way to strengthen the system is to use codes with a larger errorcorrection capability. This thesis presents "wild Goppa codes" which contain the classical binary Goppa codes as a special case. We explain how to encrypt and decrypt messages in the McEliece cryptosystem when using wild Goppa codes. The size of the public key can be reduced by using wild Goppa codes over moderate fields which is explained by evaluating the security of the "Wild McEliece" cryptosystem against our generalized collision attack for codes over finite fields. Codebased cryptography not only deals with publickey cryptography: a codebased hash function "FSB"was submitted to NIST’s SHA3 competition, a competition to establish a new standard for cryptographic hashing. Wagner’s generalized birthday attack is a generic attack which can be used to find collisions in the compression function of FSB. However, applying Wagner’s algorithm is a challenge in storagerestricted environments. The FSBday project showed how to successfully mount the generalized birthday attack on 8 nodes of the Coding and Cryptography Computer Cluster (CCCC) at Technische Universiteit Eindhoven to find collisions in the toy version FSB48 which is contained in the submission to NIST.
U2  10.6100/IR711052
DO  10.6100/IR711052
M3  Phd Thesis 1 (Research TU/e / Graduation TU/e)
SN  9789038624761
PB  Technische Universiteit Eindhoven
CY  Eindhoven
ER 