Implementing cryptographic schemes in `sage.crypto`

[grhkm21]

Problem Description

As it is right now, sage.crypto does not have too many advanced features especially outside symmetric cryptanalysis. It would be great to improve on that.

Proposed Solution

I propose to include implementation of popular and basic cryptography primitives/schemes in that directory. It can serve as a reference implementation, and also help cryptographers prototype new advanced protocols easier.

For basic primitives, there are two directions. One direction is the "structural" side, for example creating classes for encryption schemes, OT, commitment schemes and others. The other direction is the "implementation" side, for example implementing a basic scheme using those classes.

Take encryption schemes as a concrete example. A class for a public key encryption scheme would have methods like .generate_key, .encrypt(msg, pk), .decrypt(msg, sk). An implementation can simply be wrapping around AES.

What do everyone think? Any strong opinion on whether to include this or not?

[vincentmacri]

I don't have an opinion on how this should be implemented in Sage, but as someone who has used Sage to prototype new cryptographic schemes before, I do think something like this would be nice to have.

I think it would be nice if Sage implemented "toy" implementations (i.e. minimal effort put towards things like side-channel resistance, and not intended for real-world encryption use) of well-known cryptographic schemes (RSA, ECDH, and some of the new post-quantum schemes that are being standardized) to provide something to compare against for correctness if someone is trying to implement some well-known scheme with some improved algorithm.