Crypto package additions?
Andrew Budker
My name is Andrew Budker and I'm a fourth year undergraduate
Mathematics of Computation student at UCLA. This quarter (and over the
summer) I'll be taking an independent studies course with Nathan Ryan,
and hope to be able to contribute to the SAGE project. I've taken two
courses in cryptology, one applied and one theoretical. Ultimately, I
would like to add several hashes, modes of operation, and several
modern cryptosystem implementations to the Sage crypto package. I just
wanted to introduce myself, and find out if anyone was currently
working on similar additions to the crypto package.
-Andrew Budker
William Stein
David Kohel has written a lot of code for SAGE that does classical
crypto. It could use more documentation and examples; it
would be good if you could write that. This code is in the
SAGE_ROOT/devel/sage/sage/crypto/
directory. SAGE also includes PyCrypto
http://www.amk.ca/python/code/crypto
which is an implementation of a huge range of symmetric and
public key crypto protocols. It could likely be made easier to use
from SAGE, but looks fairly complete as a package.
One thing you could do to start would be to implement *optimized*
code for RSA/Diffie-Hellman/elliptic curve based cryptosystems, since
SAGE includes GMP and PyCrypto doesn't use GMP, hence in SAGE one
could implement those cryptosystems more quickly than in pure Python
or C (without GMP). E.g., integer arithmetic with 1000 digits numbers
with SAGE Integers (=GMP) is orders of magnitude faster than with
Python ints. SAGE also includes the SEA point counting algorithm
for elliptic curves, and recently David Harvey added a highly optimized
implementation of Kedlaya's hyperelliptic curve point counting. Thus
one could also write code for SAGE for elliptic/hyperelliptic curve selection.
You should also look through the Magma documentation to see what
they do related to cryptography, and see if any of that functionality
isn't in SAGE via what's there now or in PyCrypto.
Also, the next release of SAGE will switch from including openssl to
gnutls and its dependencies along with python-gnutls; that has optimized
implementations of some crypto protocols as well.
SUMMARY: There is a huge amount of crypto-related functionality in
SAGE already, but it is "all over", and there are some exciting and unique
cryptographic algorithms that could be implemented in SAGE that
aren't implemented now.
-- William
Martin Albrecht
implementations is the ability to scale down below secure thresholds, i.e.,
to use toy cipher variants. As we are not interested in productivity crypto
but in research that would be very valuable. So reduced round/blocksize
variants would be really, really cool.
Also, as the hash competition is coming up implementing many currently
discussed 'provable secure' hash functions could be a good idea.
Anyway, +1 for attempting to improve SAGE with respect to crypto.
Martin
PS: I am working on some block cipher implementations too, but mainly to
generate polynomial systems for them. But these should be integrated with the
general crypto package stuff, I guess.
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
Nick Alexander
> SUMMARY: There is a huge amount of crypto-related functionality in
> SAGE already, but it is "all over", and there are some exciting and unique
> cryptographic algorithms that could be implemented in SAGE that
> aren't implemented now.
In addition, SAGE could really use arithmetic in Jacobians of
hyperelliptic curves. If you are interested in computational
algebraic geometry and cryptography, this would be a valuable
contribution.
Nick
David Harvey
I second this. Would be great to have a fast implementation. In
particular there are supposed to be very fast algorithms for genus 2,
and perhaps 3 too.
david
David Kohel
The main crypto functionality that I implemented concerns classical
cryptography,
for the purposes of teaching:
http://echidna.maths.usyd.edu.au/~kohel/tch/Crypto/
Hence most of the systems are breakable (using suitable classical
cryptanalytic
attacks). The cryptosystem class can be extended by adding subclasses
for
more serious RSA, ElGamal, and symmetric key systems.
Modes of operation (for block ciphers) are yet to be implemented, but
intended.
Classes of hash functions would also be natural additions -- I'm happy
to discuss
the higher level structure for classes of ciphers and hashes. Many of
the latter
algorithms, and fast algorithms for RSA, ElGamal, and ECC have
implementations
in standard libraries, but as noted, scaled down "weak" versions would
be useful
for testing or demonstrating attacks.
--David
Andrew Budker
I guess I should have been a little more specific about exactly what
i'm trying to do.
As a crypto student, I would have found it useful to see not only to
see reduced round versions of some of the more of the advanced crypto
systems, but virtually every real implementation avoids actually doing
the mathematical operations in the clear (for optimization reasons).
For example in AES, all of the finite field multiplication is
accomplished using some bit-shifting trickery or a table look up.
Since all of this mathematical backbone is built into SAGE, I can
clearly write these crypto systems. I also plan to allow for reduced
round, and step by step options to aid in teaching / demonstrating
attacks.
-Andrew