Sage Enhancement Proposal: Improved Public Key Cryptography Functionality

[vincentmacri]

Authors

• Brian Heckel @Brian-Heckel
• Taha Hedayat @TahaHedayat
• Vincent Macri @vincentmacri

Posted on 2025-11-21

Preamble

In recent discussions about Sage governance organized by David Roe and John Palmieri, the idea of bringing back Sage Enhancement Proposals (SEPs) was brought up. SEPs are meant to be similar to Python Enhancement Proposals (PEPs). @vincentmacri suggested using GitHub Discussions for Sage Enhancement Proposals to avoid long technical discussions on sage-devel and instead have those discussions in a place with features like code formatting and $\mathrm{\LaTeX}$ that make long technical discussions easier. The idea is to use GitHub Discussions as a place to get feedback on and hash out the details of a proposal before implementing it, or in the case of major changes, before calling a vote on sage-devel.

This thread is an attempt to try out the idea with a relatively simple topic: improving Sage's public key cryptography facilities. This would otherwise be a series of issues and PRs with discussion spread across all of them. The hope is that by discussing it first here we can have the entire plan written down and discussed in one place for easier future reference, and we can take feedback into account proactively while writing the code the first time so that the code review will be faster/smoother.

We have three goals for this SEP:

1. Get some feedback on the design of some new cryptography features that we are working on adding to Sage.
2. Document the thought process behind the design of the code for future reference.
3. If this goes well, have this SEP serve as an example/template for future SEPs

In order to keep this thread on-topic, we would appreciate if comments on this thread stick to commenting on the proposal itself. We'll be posting a link to this GitHub Discussions thread on sage-devel, and am happy to get feedback on the idea and format of SEPs on the sage-devel thread.

SEP Type

Indicate what kind of SEP this is. Indicating an SEP type that does not require a vote is only to indicate what the author expects the community will want, and does not exempt the proposal from any of our normal processes on calling a vote. Reaching a consensus on GitHub Discussions does not exempt a PR implementing the proposal from the normal code review process, but can be pointed to to explain why certain decisions were made.

• Feedback. Request for feedback on the code design of new math features, or on ideas to improve existing math features. A vote of sage-devel is not expected to be needed.
• Governance. Suggestions to change how the project is run. After the SEP is finalized by the discussion here, a vote on sage-devel is required to move forward with the proposal. For minor changes to the GitHub workflow (such as adding/removing GitHub issue labels) a sage-devel vote is not required, but sage-devel should be notified.
• Major changes. After the SEP is finalized by the discussion here, a vote on sage-devel is required to move forward with the proposal.
• Other. Indicate whether or not you expect a vote will be needed, and if not, why.

Abstract

Sage currently has modules for cryptography, listed here. Sage has base classes and some implementations for symmetric key ciphers. Sage has a pitiful amount of features for public key cryptography. Sage (along with Magma) is commonly used to prototype new cryptographic primitives before writing an optimized low-level (usually C) implementation.

This proposal is to improve Sage's facilities for public key cryptography. This will make prototyping new public key schemes in Sage easier. We will also implement a handful of interesting schemes in Sage for users to experiment with and to demonstrate the utility of Sage's API for public key cryptography. These implementations and APIs should also be useful pedagogically for cryptography students and instructors. By using our TestSuite framework, we will be able to test implementations for correctness (e.g. both parties arrive at the same shared secret) once the necessary methods are implemented (similar to how Sage can test the group axioms on a new group a user implements in Sage once they implement the necessary methods). This will reduce the amount of uninteresting/boilerplate code that users have to write when experimenting with cryptography so that they can focus on the mathematics.

The first step of this will be to implement public key exchange protocols and the necessary APIs for them.

This proposal is not suggesting that Sage be used for real-world cryptographic deployments. This proposal is about using Sage to experiment with cryptography for pedagogical purposes, or as a prototyping tool for researchers. The authors discourage anyone from using Sage's cryptography facilities in any situation where security is desired.

Motivation

Sage is a very useful tool for prototyping cryptography schemes, and by providing a common API and taking care of boilerplate work via abstract base classes Sage can make this prototyping work much easier.

Public key cryptography is a rich area of mathematics. Public key cryptography has received a lot of attention recently as researchers have been working to create and deploy new cryptographic schemes that are resistant to quantum attacks. Many of these post-quantum schemes rely on more advanced mathematics (e.g. elliptic curve isogenies, lattices) than classical public key cryptography (e.g. elliptic curve group law, modular integer arithmetic). Because of this, new cryptographic schemes are sometimes first prototyped in a high-level math programming language like Sage or Magma before writing a more careful implementation in a low-level language like C. The low-level implementations can be highly optimized and difficult to understand, sometimes going as far as including handwritten assembly code. High level implementations do not share a common API, making it difficult to write generic code that works with multiple public key schemes.

For this proposal, we make the following distinction between different types of public key protocols:

• Key exchange: Diffie-Hellman-like protocols to establish a shared secret where either party can initiate the key exchange. Both parties perform the "same" (or at least similar) mathematical operation. Examples: Diffie-Hellman and similar schemes like CSIDH and SIDH.
• Key encapsulation mechanism (KEM): Protocols to establish a shared secret where the two parties perform possibly different mathematical operations. There is a clear distinction between the party that initiates the key agreement and the party that responds. Examples: Kyber, SIKE, and RSA or ElGamal where the message to be encrypted is randomly chosen.
• Public key encryption (PKE): Protocols that can encrypt arbitrary messages to communicate over an insecure channel. Examples: RSA, ElGamal.
• Digital signatures: Protocols to verify the authenticity of a message. Example: ECDSA.

A key exchange protocol can easily be transformed to a KEM by enforcing at the protocol level which party initiates and which responds. A PKE scheme can be transformed to a KEM by encrypting a random message rather than a message chosen by the user. (This is a simplified explanation, in practice there are additional considerations if one wishes to maintain security.)

The initial version of this will only implement key exchange. We are proposing to do key exchange first due to simplicity and the authors' familiarity. The rest of this proposal will focus on key exchange, but the general design principles should apply to KEM, PKE, and signature schemes as well. Sage has some existing code for PKE that we are unsure what to do with, so we suggest implementing PKE only after deciding what to do with the existing PKE code.

Rationale

Sage already has cryptography facilities, this proposal is simply to add new cryptographic functionality. While we could simply provide wrappers around existing cryptography libraries, we do not think that would be a good approach, at least for public key cryptography.

Public key cryptography is based on various mathematical objects that are usually already implemented in Sage. Real-world cryptography implementations are highly optimized and work directly with basic types rather than the mathematical objects that define the scheme mathematically (for example, instead of defining objects for elliptic curves and points, a real cryptography implantation is more likely to consist of a series of formulas on arrays of integers). To give a very rough analogy with Sage terminology, this is like implementing an Element without implementing its Parent. It may be sufficient (and possibly more efficient) if one wants just to do a particular computation, but it makes it more difficult to poke deeper into what's going on mathematically. The cryptography implementations that we propose to add to Sage are mainly for pedagogical purposes so that people can use Sage to explore the mathematics behind various interesting cryptography schemes, and we believe this is best accomplished by working with the higher level mathematical objects and functions already defined in Sage. An additional benefit of this approach is that the unit tests for our cryptography implementations would also serve as a kind of integration test of Sage's implementations of the underlying mathematical objects.

Having the code work with mathematical objects also allows additional pedagogically useful functionality that would not normally be found in other cryptographic tools. For example, we would allow the construction of Diffie-Hellman over a group where discrete log is easy, so students can try to implement attacks on it as an exercise.

Specification

The code for this will live under src/sage/crypto/public_key.

Code for key exchange, which this proposal focuses on, will live in src/sage/crypto/public_key/key_exchange. Eventually code for KEMs will live in src/sage/crypto/public_key/kem and the code for public key encryption will live in src/sage/crypto/public_key/encryption.

Code common to or interacting with different types of public key protocols will live in src/sage/crypto/public_key.

The API will consist of abstract base classes that users can inherit from. The abstract base classes will implement as much functionality as is possible to do generically, so that users can focus on implementing the mathematically interesting parts. For example, the abstract base class for key exchange will implement tests that check that both parties arrive at the same shared secret. The user will only need to implement methods for key generation and shared secret computation, and can test their implementation via our TestSuite framework. An instance of a key exchange class corresponds to a specific parameter set of the key exchange scheme the class implements.

This proposal will be updated with more specifics of the key exchange API once we have a prototype implemented.

What kinds of schemes will be included

There are many cryptography schemes, and it isn't possible, or desirable, to include all of them. We are not going to advocate for strict rules about what should or shouldn't be included, but here are some potential guidelines:

• Schemes of significant pedagogical interest that are frequently discussed in an introductory cryptography course. These schemes may or may not be frequently used in practice.
  • Examples: ElGamal, RSA, Diffie-Hellman
• Schemes of significant interest to cryptographers. Schemes that are being considered for, undergoing, or have undergone standardization and will be or already are widely deployed.
  • Examples: RSA, Diffie-Hellman, KYBER
• Schemes (possibly of historical interest) which are interesting for either mathematical or implementation reasons.
  • Example: SIDH
    • Beyond the authors' interest in SIDH, it has a "almost Diffie-Hellman" structure that makes it an interesting case to test the design of our API. The attack that broke SIDH is also very interesting mathematically.
• Other schemes of active research interest.
  • Example: CSIDH

(Our examples skew towards isogeny-based schemes only because it's what the authors have the most experience with.)

Backwards compatibility, required deprecations, and major refactoring

Currently src/sage/crypto/public_key only contains blum_goldwasser.py. The file blum_goldwasser.py will be left alone for now, but may be refactored/rewritten to fit in with the rest of the public key code in the future if we decide to deprecate PublicKeyCryptosystem (discussed below). This would likely require a deprecation as the API would change significantly.

The code under src/sage/crypto/key_exchange will be refactored and the functionality will be moved into src/sage/crypto/public_key/key_exchange. @vincentmacri, one of the authors of this proposal, marked the entirety of that package as experimental when he created it and so it is exempt from our deprecation policies.

We do already have a framework for public key encryption, PublicKeyCryptosystem in src/sage/crypto/cryptosystem.py. The only user of PublicKeyCryptosystem in the Sage library is blum_goldwasser.py. We doubt there are many users of PublicKeyCryptosystem in the wild. PublicKeyCryptosystem seems to have been written in a way that is targeted towards operating on actual text data, which includes encoding and decoding it into the underlying mathematical structures used. We don't think it's required to work with text data, but it appears that deliberate effort was put into allowing it and this may complicate things in a way that provides little utility. We don't see doing public key cryptography on text data as being a useful feature for Sage as we don't think the "mathematically interesting" cryptography work that someone would want to use Sage for would include encoding and decoding text data, but since we only have one example implemented, perhaps we am not seeing the potential of PublicKeyCryptosystem. We are also interested in hearing what people think about this. Is PublicKeyCryptosystem useful in its current form? Should Sage keep and/or improve it or should Sage deprecate it in favour of something that works only with mathematical objects rather than text data? As we are proposing to implement key exchange first which wouldn't use PublicKeyCryptosystem anyway, we don't think we need an urgent decision on this as work on both public key exchange and KEMs should be able to proceed while we discuss what to do about PublicKeyCryptosystem.

How to Teach This

In addition to the docstrings that all Sage code has, we will write a tutorial of how to use Sage's public key framework and add the tutorial to the documentation as well, likely under Sage Thematic Tutorials.

FAQ

Will be updated in response to feedback.

Ideas for Future Work

Medium-term future work:

• KEMs
• PKE
• Digital signatures
• Additional schemes

Rejected Ideas

Providing bindings to existing cryptography libraries instead of writing our own implementations.

• This would not give us the same pedagogical or prototyping utility that we would get from implementations that work with Sage's mathematical objects. Provides little value over using existing libraries directly.

Points for discussion

Feedback on any part of this proposal is welcome. In particular, I'd appreciate feedback on:

• The proposal overall, especially the plan to focus on the mathematical aspects of cryptography and implement schemes using the underlying mathematical objects that already exist in Sage.
• Other than the examples listed, other schemes people think would be useful or interesting to have included in Sage.
• Thoughts on what Sage should do with PublicKeyCryptosystem.

[dimpase]

I can only say, good idea!

[cxzhong]

Thank you very much. It is much better for my work.

[tobiasdiez]

Very nice write-up! I cannot say much about the cryptography part. One suggestion concerning

By using our TestSuite framework, we will be able to test implementations for correctness (e.g. both parties arrive at the same shared secret) once the necessary methods are implemented (similar to how Sage can test the group axioms on a new group a user implements in Sage once they implement the necessary methods).

I think it would be more convenient to implement this testing functionality actually in pytest instead of sage's TestSuite. For example, it is not possible to just run one single test method of a TestSuite without also running all other methods. Pytest also has a few other nice features such as a watch mode where tests are automatically rerun when you change the implementation etc. In the implementation would actually not be that different, you have a TestBase class that defines the generic tests and then the user can simply inherit from that class to run it against her implementation of the interface (see eg https://stackoverflow.com/a/52044620/873661).

(Disclaimer: For pretty much the same reasons, I'll propose to completely replace sage "TESTS" with pytest, but that will be a different SEP).

[tobiasdiez]

I propose we leave the general discussion about pytest for a separate SEP (I'll try to create one very soon), if that's okay with everyone. One relevant point though is that pytest was made a standard SPKG about a year ago, exactly with the argument to transition to more standard python tooling. So from this perspective it is as 'standard' as Sage's TestSuite.

Can pytest do something similar without the user having to do anything more complicated than TestSuite(custom_key_exchange).run()?

If such a user scenario is a hard requirement, then pytest might indeed not be the right choice. Pytest by design favors a splitting of "tests" from the actual implementation.

Could you describe in more detail how you expect people to develop their own implementations? So do you expect people to really use the sage prompt to develop their algorithms? Or would they normally implement them in a bunch of python modules, or in jupyter notebooks, or...? How would they write their own "tests" to confirm their implementation is correct (beyond the abstract tests that should be derived from sage)?

[vincentmacri]

Could you describe in more detail how you expect people to develop their own implementations? So do you expect people to really use the sage prompt to develop their algorithms? Or would they normally implement them in a bunch of python modules, or in jupyter notebooks, or...?

A user would extend the abstract base class, (let's call it KeyExchangeBase). In practice not at a Sage prompt (I guess they could, but it would be an uncomfortable workflow), but in either a .sage file or in a Jupyter notebook. An implementation of a key exchange scheme should be able to be written entirely in one file.

How would they write their own "tests" to confirm their implementation is correct (beyond the abstract tests that should be derived from sage)?

With TestSuite they can add their own _test_foo methods to their class that TestSuite will pick up.

[vincentmacri]

For an example, here's the in-progress work by @Brian-Heckel for Diffie-Hellman over a finite field: https://github.com/vincentmacri/sage/blob/d68b9da03fe225678b6821d9f65c0dc1bcfc6c70/src/sage/crypto/public_key/key_exchange/finite_field_dh.py. Finite field Diffie-Hellman is probably the simplest key exchange scheme, for most key exchange schemes you'll need more than one line of code to implement each method.

A user should be able to do something similar in a .sage file or in a Jupyter notebook. Extend the base class, implement some methods, and inherit tests that they can then run through TestSuite.

This is all supported already by TestSuite, I used it quite a bit when working on my Master's thesis to implement a group (implementation file and launching TestSuite from Sage code if you want example code).

[vincentmacri]

Minimum example of TestSuite being used in Sage user code:

class MyObject(SageObject):

    def __init__(self, good):
        self.good = good

    def _test_good(self, **options):
        tester = self._tester(**options)
        tester.assertTrue(self.good)

    def __eq__(self, other):
        return self.good == other.good

TestSuite(MyObject(True)).run(verbose=True)

Output:

running ._test_category() . . . pass
running ._test_good() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass

The __eq__ method is (indirectly) tested by _test_pickling, which comes from SageObject. And the new _test_good is picked up by TestSuite as well.

[vincentmacri]

Also:

it is not possible to just run one single test method of a TestSuite without also running all other methods

Calling the _test_foo methods directly is supported per our documentation: https://doc.sagemath.org/html/en/reference/misc/sage/misc/sage_unittest.html#sage.misc.sage_unittest.TestSuite

Of course, without looking at the code a user won't know what _test_ methods are implemented in the base class they are inheriting from, but they can test their own tests directly that way.