YobiWiki - User contributions [en]

SAGE & cryptology

2008-07-13T11:12:58Z

VentziNikov: /* Cryptanalysis tools */

===Discussions===
* [http://groups.google.com/group/sage-devel/browse_thread/thread/9557f299b1ec2fab?hl=en this thread in the ML]
* [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl this blog] and especially [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl/2008/03/21#sage-crypto-todo this post]
* [http://modular.math.washington.edu/sage/jsage/ JSAGE]
* [http://modular.math.washington.edu/sage/dev.html notes for developers]
===Docs===
* http://www.cryptlib.com/standards-compliance.htm

===Available===
* sage.crypto
* Sage ships [http://www.amk.ca/python/code/crypto PyCrypto] which implements many standard cryptographic algorithms. It is not really meant for research/education/playing around but for production code but maybe something could be done to have easier access to it from within Sage. The docstring level documentation is horrible:
sage: import Crypto.Cipher.IDEA
sage: Crypto.Cipher.IDEA?
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
* [http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/index.html book written on Cryptography by David Kohel], using SAGE
* ? openssl & pyopenssl optional packages

===Wishes===
* [http://www.sagemath.org:9002/sage_trac/report/1?sort=ticket&asc=0 General trac]
* sage.crypto: block ciphers
* Someone needs to replace FiniteField_ext_pari with the two NTL implementations (they are much faster).
* elliptic and hyperelliptic curves over finite fields support is rather poor
* algebraic aspects received some attention for the cryptanalysis of symmetric cryptographic algorithms, i.e. the cryptanalyst expresses the cipher as a large set of multivariate polynomials and attempts to solve the system. The most common case over GF(2) is handled by PolyBoRi. This library is the backbone of BooleanPolynomialRing and friends. This class needs testing, documentation, extension and bugfixes. Basically someone should sit down and add all the methods of MPolynomial[Ring]_libsingular to BooleanPolynomial[Ring] which make sense, add a ton of doctests and test the hell out of the library to make sure no SIGSEGVs surprise the user.
* the module sage.crypto.mq is also relevant for the above.
* Univariate polynomials over GF(2) are still implemented via NTL's ZZ_pX class rather than GF2X. This should be changed. Also [http://trac.sagemath.org/sage_trac/ticket/2114 this ticket] has a link to gf2x a very small drop in replacement C library which claimed to be 5x faster than NTL. Though, a formal vote is needed to get it into Sage.
* At the end of the day everything boils down to linear algebra. So if you improve that, everybody wins. Sparse linear algebra mod p is still too slow (Ralf-Phillip Weinmann did some work here wrapping code from eclib), there isn o special implementation for sparse linear algebra over GF(2) (both blackbox and e.g. reduced echelon forms), dense LA over GF(2) needs Strassen multiplication/reduction, dense LA over GF(2^n) should probably get implemented.
==The ideal toolbox==
This is a lengthy list but it's our Xmas list ;-)
We aim to have a toolbox for research/education/playing not production optimizations required.
So easy access, reconfigurability and clearness are more important!
===Block ciphers===
====Block cipher algorithms====
Make sure the internals are accessible and reconfigurable, particularly the S-BOXes.
 Try to make generic constructors such as Feistel cipher, etc
* Serpent
* Twofish
* Idea
* DES, 3DES 112, 168
* AES 128, 196, 256
* Present
====Modes of operation====
Make sure we can select independently the block cipher encryption/decryption mode and the chaining "encryption/decryption" mode
* Authentication modes
** CMAC
** XCBC
** CBC-MAC
* Authentication+encryption modes
** CCM
** GCM
* Encryption modes
** ECB
** CBC
** CTR
* Disk encryption modes
** LRW
** XTS
Non-keyed hashes
* MDC-2 (ISO 10118-2)
====Paddings====
* Bit padding (can be done at bit level, others are at byte level)
DD DD DD 80 00 00 00 00
* zeros
DD DD DD 00 00 00 00 00
* PKCS7
DD DD DD 05 05 05 05 05
* ISO 10126
DD DD DD 42 DB 8A 98 05
* ANSI X.923
DD DD DD 00 00 00 00 05
===Stream ciphers===
Same thing, get the internals accessible and patchable
* RC4
* A5/1 A5/2
* SNOW2 SNOW3G
* SW candidates of eSTREAM:
** HC-128
** RABBIT
** Salsa 20/12
** SOSEMANUK
* HW candidates of eSTREAM:
** F-FCSR
** Grain
** MICKEY
** Trivium
* LFSR
* Shrinking generator
* Self-shrinking generator

===One-way functions===
* MD5
* SHA family
* Whirlpool
* RipeMD
* MDC-2
* RadioGatún
Ways to transform a block cipher into a hash
* Davies-Meyer
* Matyas-Meyer-Oseas
* Miyaguchi-Preneel
MACs based on hash functions
* HMAC
* NMAC
Key derivation functions
* KDF family
* PBKDF2

===Public-key cryptography===
====ECC====
* all coordinate systems
* cf http://www.hyperelliptic.org/EFD/
====Others====
* RSA (encryption, signature, PKCS#1 v1.5 and v2.1, with and without CTR)
* DSA
* ElGamal
* DH
* XTR
* Paillier
* NTRUE

===Pseudo-random generators===
* cf NIST
* Mersenne Twister
===Cryptanalysis tools===
* boolean functions & S-Box
** algebraic degree
** algebraic immunity
** algebraic normal form (ANF)
** non linearity
** resiliency
** Walsh transforms
** cross-correlation
* ECC point counting
** complex multiplication?
* factorisation solver
* discrete log solver
* statistical tests (diehard, FIPS...)
* Field operations: addition, multiplication, inverses (normal and polynomial basis)

SAGE & cryptology

2008-07-13T11:11:00Z

VentziNikov: /* Others */

===Discussions===
* [http://groups.google.com/group/sage-devel/browse_thread/thread/9557f299b1ec2fab?hl=en this thread in the ML]
* [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl this blog] and especially [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl/2008/03/21#sage-crypto-todo this post]
* [http://modular.math.washington.edu/sage/jsage/ JSAGE]
* [http://modular.math.washington.edu/sage/dev.html notes for developers]
===Docs===
* http://www.cryptlib.com/standards-compliance.htm

===Available===
* sage.crypto
* Sage ships [http://www.amk.ca/python/code/crypto PyCrypto] which implements many standard cryptographic algorithms. It is not really meant for research/education/playing around but for production code but maybe something could be done to have easier access to it from within Sage. The docstring level documentation is horrible:
sage: import Crypto.Cipher.IDEA
sage: Crypto.Cipher.IDEA?
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
* [http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/index.html book written on Cryptography by David Kohel], using SAGE
* ? openssl & pyopenssl optional packages

===Wishes===
* [http://www.sagemath.org:9002/sage_trac/report/1?sort=ticket&asc=0 General trac]
* sage.crypto: block ciphers
* Someone needs to replace FiniteField_ext_pari with the two NTL implementations (they are much faster).
* elliptic and hyperelliptic curves over finite fields support is rather poor
* algebraic aspects received some attention for the cryptanalysis of symmetric cryptographic algorithms, i.e. the cryptanalyst expresses the cipher as a large set of multivariate polynomials and attempts to solve the system. The most common case over GF(2) is handled by PolyBoRi. This library is the backbone of BooleanPolynomialRing and friends. This class needs testing, documentation, extension and bugfixes. Basically someone should sit down and add all the methods of MPolynomial[Ring]_libsingular to BooleanPolynomial[Ring] which make sense, add a ton of doctests and test the hell out of the library to make sure no SIGSEGVs surprise the user.
* the module sage.crypto.mq is also relevant for the above.
* Univariate polynomials over GF(2) are still implemented via NTL's ZZ_pX class rather than GF2X. This should be changed. Also [http://trac.sagemath.org/sage_trac/ticket/2114 this ticket] has a link to gf2x a very small drop in replacement C library which claimed to be 5x faster than NTL. Though, a formal vote is needed to get it into Sage.
* At the end of the day everything boils down to linear algebra. So if you improve that, everybody wins. Sparse linear algebra mod p is still too slow (Ralf-Phillip Weinmann did some work here wrapping code from eclib), there isn o special implementation for sparse linear algebra over GF(2) (both blackbox and e.g. reduced echelon forms), dense LA over GF(2) needs Strassen multiplication/reduction, dense LA over GF(2^n) should probably get implemented.
==The ideal toolbox==
This is a lengthy list but it's our Xmas list ;-)
We aim to have a toolbox for research/education/playing not production optimizations required.
So easy access, reconfigurability and clearness are more important!
===Block ciphers===
====Block cipher algorithms====
Make sure the internals are accessible and reconfigurable, particularly the S-BOXes.
 Try to make generic constructors such as Feistel cipher, etc
* Serpent
* Twofish
* Idea
* DES, 3DES 112, 168
* AES 128, 196, 256
* Present
====Modes of operation====
Make sure we can select independently the block cipher encryption/decryption mode and the chaining "encryption/decryption" mode
* Authentication modes
** CMAC
** XCBC
** CBC-MAC
* Authentication+encryption modes
** CCM
** GCM
* Encryption modes
** ECB
** CBC
** CTR
* Disk encryption modes
** LRW
** XTS
Non-keyed hashes
* MDC-2 (ISO 10118-2)
====Paddings====
* Bit padding (can be done at bit level, others are at byte level)
DD DD DD 80 00 00 00 00
* zeros
DD DD DD 00 00 00 00 00
* PKCS7
DD DD DD 05 05 05 05 05
* ISO 10126
DD DD DD 42 DB 8A 98 05
* ANSI X.923
DD DD DD 00 00 00 00 05
===Stream ciphers===
Same thing, get the internals accessible and patchable
* RC4
* A5/1 A5/2
* SNOW2 SNOW3G
* SW candidates of eSTREAM:
** HC-128
** RABBIT
** Salsa 20/12
** SOSEMANUK
* HW candidates of eSTREAM:
** F-FCSR
** Grain
** MICKEY
** Trivium
* LFSR
* Shrinking generator
* Self-shrinking generator

===One-way functions===
* MD5
* SHA family
* Whirlpool
* RipeMD
* MDC-2
* RadioGatún
Ways to transform a block cipher into a hash
* Davies-Meyer
* Matyas-Meyer-Oseas
* Miyaguchi-Preneel
MACs based on hash functions
* HMAC
* NMAC
Key derivation functions
* KDF family
* PBKDF2

===Public-key cryptography===
====ECC====
* all coordinate systems
* cf http://www.hyperelliptic.org/EFD/
====Others====
* RSA (encryption, signature, PKCS#1 v1.5 and v2.1, with and without CTR)
* DSA
* ElGamal
* DH
* XTR
* Paillier
* NTRUE

===Pseudo-random generators===
* cf NIST
* Mersenne Twister
===Cryptanalysis tools===
* boolean functions & S-Box
* algebraic degree
* algebraic immunity
* algebraic normal form (ANF)
* non linearity
* resiliency
* Walsh transforms
* cross-correlation
* ECC point counting
* complex multiplication?
* factorisation solver
* discrete log solver
* statistical tests (diehard, FIPS...)

SAGE & cryptology

2008-07-13T11:09:07Z

VentziNikov: /* One-way functions */

===Discussions===
* [http://groups.google.com/group/sage-devel/browse_thread/thread/9557f299b1ec2fab?hl=en this thread in the ML]
* [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl this blog] and especially [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl/2008/03/21#sage-crypto-todo this post]
* [http://modular.math.washington.edu/sage/jsage/ JSAGE]
* [http://modular.math.washington.edu/sage/dev.html notes for developers]
===Docs===
* http://www.cryptlib.com/standards-compliance.htm

===Available===
* sage.crypto
* Sage ships [http://www.amk.ca/python/code/crypto PyCrypto] which implements many standard cryptographic algorithms. It is not really meant for research/education/playing around but for production code but maybe something could be done to have easier access to it from within Sage. The docstring level documentation is horrible:
sage: import Crypto.Cipher.IDEA
sage: Crypto.Cipher.IDEA?
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
* [http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/index.html book written on Cryptography by David Kohel], using SAGE
* ? openssl & pyopenssl optional packages

===Wishes===
* [http://www.sagemath.org:9002/sage_trac/report/1?sort=ticket&asc=0 General trac]
* sage.crypto: block ciphers
* Someone needs to replace FiniteField_ext_pari with the two NTL implementations (they are much faster).
* elliptic and hyperelliptic curves over finite fields support is rather poor
* algebraic aspects received some attention for the cryptanalysis of symmetric cryptographic algorithms, i.e. the cryptanalyst expresses the cipher as a large set of multivariate polynomials and attempts to solve the system. The most common case over GF(2) is handled by PolyBoRi. This library is the backbone of BooleanPolynomialRing and friends. This class needs testing, documentation, extension and bugfixes. Basically someone should sit down and add all the methods of MPolynomial[Ring]_libsingular to BooleanPolynomial[Ring] which make sense, add a ton of doctests and test the hell out of the library to make sure no SIGSEGVs surprise the user.
* the module sage.crypto.mq is also relevant for the above.
* Univariate polynomials over GF(2) are still implemented via NTL's ZZ_pX class rather than GF2X. This should be changed. Also [http://trac.sagemath.org/sage_trac/ticket/2114 this ticket] has a link to gf2x a very small drop in replacement C library which claimed to be 5x faster than NTL. Though, a formal vote is needed to get it into Sage.
* At the end of the day everything boils down to linear algebra. So if you improve that, everybody wins. Sparse linear algebra mod p is still too slow (Ralf-Phillip Weinmann did some work here wrapping code from eclib), there isn o special implementation for sparse linear algebra over GF(2) (both blackbox and e.g. reduced echelon forms), dense LA over GF(2) needs Strassen multiplication/reduction, dense LA over GF(2^n) should probably get implemented.
==The ideal toolbox==
This is a lengthy list but it's our Xmas list ;-)
We aim to have a toolbox for research/education/playing not production optimizations required.
So easy access, reconfigurability and clearness are more important!
===Block ciphers===
====Block cipher algorithms====
Make sure the internals are accessible and reconfigurable, particularly the S-BOXes.
 Try to make generic constructors such as Feistel cipher, etc
* Serpent
* Twofish
* Idea
* DES, 3DES 112, 168
* AES 128, 196, 256
* Present
====Modes of operation====
Make sure we can select independently the block cipher encryption/decryption mode and the chaining "encryption/decryption" mode
* Authentication modes
** CMAC
** XCBC
** CBC-MAC
* Authentication+encryption modes
** CCM
** GCM
* Encryption modes
** ECB
** CBC
** CTR
* Disk encryption modes
** LRW
** XTS
Non-keyed hashes
* MDC-2 (ISO 10118-2)
====Paddings====
* Bit padding (can be done at bit level, others are at byte level)
DD DD DD 80 00 00 00 00
* zeros
DD DD DD 00 00 00 00 00
* PKCS7
DD DD DD 05 05 05 05 05
* ISO 10126
DD DD DD 42 DB 8A 98 05
* ANSI X.923
DD DD DD 00 00 00 00 05
===Stream ciphers===
Same thing, get the internals accessible and patchable
* RC4
* A5/1 A5/2
* SNOW2 SNOW3G
* SW candidates of eSTREAM:
** HC-128
** RABBIT
** Salsa 20/12
** SOSEMANUK
* HW candidates of eSTREAM:
** F-FCSR
** Grain
** MICKEY
** Trivium
* LFSR
* Shrinking generator
* Self-shrinking generator

===One-way functions===
* MD5
* SHA family
* Whirlpool
* RipeMD
* MDC-2
* RadioGatún
Ways to transform a block cipher into a hash
* Davies-Meyer
* Matyas-Meyer-Oseas
* Miyaguchi-Preneel
MACs based on hash functions
* HMAC
* NMAC
Key derivation functions
* KDF family
* PBKDF2

===Public-key cryptography===
====ECC====
* all coordinate systems
* cf http://www.hyperelliptic.org/EFD/
====Others====
* RSA
* DSS
* ElGamal
* DH
* Signature paddings
* PKCS#1
* XTR
* Paillier
* NTRUE
===Pseudo-random generators===
* cf NIST
* Mersenne Twister
===Cryptanalysis tools===
* boolean functions & S-Box
* algebraic degree
* algebraic immunity
* algebraic normal form (ANF)
* non linearity
* resiliency
* Walsh transforms
* cross-correlation
* ECC point counting
* complex multiplication?
* factorisation solver
* discrete log solver
* statistical tests (diehard, FIPS...)

SAGE & cryptology

2008-07-13T11:07:51Z

VentziNikov: /* Stream ciphers */

===Discussions===
* [http://groups.google.com/group/sage-devel/browse_thread/thread/9557f299b1ec2fab?hl=en this thread in the ML]
* [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl this blog] and especially [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl/2008/03/21#sage-crypto-todo this post]
* [http://modular.math.washington.edu/sage/jsage/ JSAGE]
* [http://modular.math.washington.edu/sage/dev.html notes for developers]
===Docs===
* http://www.cryptlib.com/standards-compliance.htm

===Available===
* sage.crypto
* Sage ships [http://www.amk.ca/python/code/crypto PyCrypto] which implements many standard cryptographic algorithms. It is not really meant for research/education/playing around but for production code but maybe something could be done to have easier access to it from within Sage. The docstring level documentation is horrible:
sage: import Crypto.Cipher.IDEA
sage: Crypto.Cipher.IDEA?
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
* [http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/index.html book written on Cryptography by David Kohel], using SAGE
* ? openssl & pyopenssl optional packages

===Wishes===
* [http://www.sagemath.org:9002/sage_trac/report/1?sort=ticket&asc=0 General trac]
* sage.crypto: block ciphers
* Someone needs to replace FiniteField_ext_pari with the two NTL implementations (they are much faster).
* elliptic and hyperelliptic curves over finite fields support is rather poor
* algebraic aspects received some attention for the cryptanalysis of symmetric cryptographic algorithms, i.e. the cryptanalyst expresses the cipher as a large set of multivariate polynomials and attempts to solve the system. The most common case over GF(2) is handled by PolyBoRi. This library is the backbone of BooleanPolynomialRing and friends. This class needs testing, documentation, extension and bugfixes. Basically someone should sit down and add all the methods of MPolynomial[Ring]_libsingular to BooleanPolynomial[Ring] which make sense, add a ton of doctests and test the hell out of the library to make sure no SIGSEGVs surprise the user.
* the module sage.crypto.mq is also relevant for the above.
* Univariate polynomials over GF(2) are still implemented via NTL's ZZ_pX class rather than GF2X. This should be changed. Also [http://trac.sagemath.org/sage_trac/ticket/2114 this ticket] has a link to gf2x a very small drop in replacement C library which claimed to be 5x faster than NTL. Though, a formal vote is needed to get it into Sage.
* At the end of the day everything boils down to linear algebra. So if you improve that, everybody wins. Sparse linear algebra mod p is still too slow (Ralf-Phillip Weinmann did some work here wrapping code from eclib), there isn o special implementation for sparse linear algebra over GF(2) (both blackbox and e.g. reduced echelon forms), dense LA over GF(2) needs Strassen multiplication/reduction, dense LA over GF(2^n) should probably get implemented.
==The ideal toolbox==
This is a lengthy list but it's our Xmas list ;-)
We aim to have a toolbox for research/education/playing not production optimizations required.
So easy access, reconfigurability and clearness are more important!
===Block ciphers===
====Block cipher algorithms====
Make sure the internals are accessible and reconfigurable, particularly the S-BOXes.
 Try to make generic constructors such as Feistel cipher, etc
* Serpent
* Twofish
* Idea
* DES, 3DES 112, 168
* AES 128, 196, 256
* Present
====Modes of operation====
Make sure we can select independently the block cipher encryption/decryption mode and the chaining "encryption/decryption" mode
* Authentication modes
** CMAC
** XCBC
** CBC-MAC
* Authentication+encryption modes
** CCM
** GCM
* Encryption modes
** ECB
** CBC
** CTR
* Disk encryption modes
** LRW
** XTS
Non-keyed hashes
* MDC-2 (ISO 10118-2)
====Paddings====
* Bit padding (can be done at bit level, others are at byte level)
DD DD DD 80 00 00 00 00
* zeros
DD DD DD 00 00 00 00 00
* PKCS7
DD DD DD 05 05 05 05 05
* ISO 10126
DD DD DD 42 DB 8A 98 05
* ANSI X.923
DD DD DD 00 00 00 00 05
===Stream ciphers===
Same thing, get the internals accessible and patchable
* RC4
* A5/1 A5/2
* SNOW2 SNOW3G
* SW candidates of eSTREAM:
** HC-128
** RABBIT
** Salsa 20/12
** SOSEMANUK
* HW candidates of eSTREAM:
** F-FCSR
** Grain
** MICKEY
** Trivium
* LFSR
* Shrinking generator
* Self-shrinking generator

===One-way functions===
* MD5
* SHA family
* Whirlpool
* RipeMD
* MDC-2
* RadioGatún
Ways to transform a block cipher into a hash
* Davies-Meyer
* Matyas-Meyer-Oseas
* Miyaguchi-Preneel
MACs based on hash functions
* HMAC
Key derivation functions
* KDF family
* PBKDF2
===Public-key cryptography===
====ECC====
* all coordinate systems
* cf http://www.hyperelliptic.org/EFD/
====Others====
* RSA
* DSS
* ElGamal
* DH
* Signature paddings
* PKCS#1
* XTR
* Paillier
* NTRUE
===Pseudo-random generators===
* cf NIST
* Mersenne Twister
===Cryptanalysis tools===
* boolean functions & S-Box
* algebraic degree
* algebraic immunity
* algebraic normal form (ANF)
* non linearity
* resiliency
* Walsh transforms
* cross-correlation
* ECC point counting
* complex multiplication?
* factorisation solver
* discrete log solver
* statistical tests (diehard, FIPS...)

SAGE & cryptology

2008-07-13T11:05:37Z

VentziNikov: /* The ideal toolbox */

===Discussions===
* [http://groups.google.com/group/sage-devel/browse_thread/thread/9557f299b1ec2fab?hl=en this thread in the ML]
* [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl this blog] and especially [http://www.informatik.uni-bremen.de/cgi-bin/cgiwrap/malb/blosxom.pl/2008/03/21#sage-crypto-todo this post]
* [http://modular.math.washington.edu/sage/jsage/ JSAGE]
* [http://modular.math.washington.edu/sage/dev.html notes for developers]
===Docs===
* http://www.cryptlib.com/standards-compliance.htm

===Available===
* sage.crypto
* Sage ships [http://www.amk.ca/python/code/crypto PyCrypto] which implements many standard cryptographic algorithms. It is not really meant for research/education/playing around but for production code but maybe something could be done to have easier access to it from within Sage. The docstring level documentation is horrible:
sage: import Crypto.Cipher.IDEA
sage: Crypto.Cipher.IDEA?
x.__init__(...) initializes x; see x.__class__.__doc__ for signature
* [http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/index.html book written on Cryptography by David Kohel], using SAGE
* ? openssl & pyopenssl optional packages

===Wishes===
* [http://www.sagemath.org:9002/sage_trac/report/1?sort=ticket&asc=0 General trac]
* sage.crypto: block ciphers
* Someone needs to replace FiniteField_ext_pari with the two NTL implementations (they are much faster).
* elliptic and hyperelliptic curves over finite fields support is rather poor
* algebraic aspects received some attention for the cryptanalysis of symmetric cryptographic algorithms, i.e. the cryptanalyst expresses the cipher as a large set of multivariate polynomials and attempts to solve the system. The most common case over GF(2) is handled by PolyBoRi. This library is the backbone of BooleanPolynomialRing and friends. This class needs testing, documentation, extension and bugfixes. Basically someone should sit down and add all the methods of MPolynomial[Ring]_libsingular to BooleanPolynomial[Ring] which make sense, add a ton of doctests and test the hell out of the library to make sure no SIGSEGVs surprise the user.
* the module sage.crypto.mq is also relevant for the above.
* Univariate polynomials over GF(2) are still implemented via NTL's ZZ_pX class rather than GF2X. This should be changed. Also [http://trac.sagemath.org/sage_trac/ticket/2114 this ticket] has a link to gf2x a very small drop in replacement C library which claimed to be 5x faster than NTL. Though, a formal vote is needed to get it into Sage.
* At the end of the day everything boils down to linear algebra. So if you improve that, everybody wins. Sparse linear algebra mod p is still too slow (Ralf-Phillip Weinmann did some work here wrapping code from eclib), there isn o special implementation for sparse linear algebra over GF(2) (both blackbox and e.g. reduced echelon forms), dense LA over GF(2) needs Strassen multiplication/reduction, dense LA over GF(2^n) should probably get implemented.
==The ideal toolbox==
This is a lengthy list but it's our Xmas list ;-)
We aim to have a toolbox for research/education/playing not production optimizations required.
So easy access, reconfigurability and clearness are more important!
===Block ciphers===
====Block cipher algorithms====
Make sure the internals are accessible and reconfigurable, particularly the S-BOXes.
 Try to make generic constructors such as Feistel cipher, etc
* Serpent
* Twofish
* Idea
* DES, 3DES 112, 168
* AES 128, 196, 256
* Present
====Modes of operation====
Make sure we can select independently the block cipher encryption/decryption mode and the chaining "encryption/decryption" mode
* Authentication modes
** CMAC
** XCBC
** CBC-MAC
* Authentication+encryption modes
** CCM
** GCM
* Encryption modes
** ECB
** CBC
** CTR
* Disk encryption modes
** LRW
** XTS
Non-keyed hashes
* MDC-2 (ISO 10118-2)
====Paddings====
* Bit padding (can be done at bit level, others are at byte level)
DD DD DD 80 00 00 00 00
* zeros
DD DD DD 00 00 00 00 00
* PKCS7
DD DD DD 05 05 05 05 05
* ISO 10126
DD DD DD 42 DB 8A 98 05
* ANSI X.923
DD DD DD 00 00 00 00 05
===Stream ciphers===
Same thing, get the internals accessible and patchable
* RC4
* A5/1 A5/2
* SNOW2 SNOW3G
* SW candidates of eSTREAM:
** HC-128
** RABBIT
** Salsa 20/12
** SOSEMANUK
* HW candidates of eSTREAM:
** F-FCSR
** Grain
** MICKEY
** Trivium
===One-way functions===
* MD5
* SHA family
* Whirlpool
* RipeMD
* MDC-2
* RadioGatún
Ways to transform a block cipher into a hash
* Davies-Meyer
* Matyas-Meyer-Oseas
* Miyaguchi-Preneel
MACs based on hash functions
* HMAC
Key derivation functions
* KDF family
* PBKDF2
===Public-key cryptography===
====ECC====
* all coordinate systems
* cf http://www.hyperelliptic.org/EFD/
====Others====
* RSA
* DSS
* ElGamal
* DH
* Signature paddings
* PKCS#1
* XTR
* Paillier
* NTRUE
===Pseudo-random generators===
* cf NIST
* Mersenne Twister
===Cryptanalysis tools===
* boolean functions & S-Box
* algebraic degree
* algebraic immunity
* algebraic normal form (ANF)
* non linearity
* resiliency
* Walsh transforms
* cross-correlation
* ECC point counting
* complex multiplication?
* factorisation solver
* discrete log solver
* statistical tests (diehard, FIPS...)