What will become of Elliptic Curve Cryptography (ECC), a backbone of modern secure communications? Contrary to apocalyptic predictions, the story isn’t about an end but an evolution if you ask me! I’ve read a lot recently about being prepared for Quantum Computing, so I thought I’d do some of my own research. This has meant exploring things like Falcon(for key gen and digital signatures), Kyber(for key exchange) and SIBC(super singular isogeny-based cryptograph, also for key exchange) and will be continuing my research and practical testing.
I’m going to talk about SIBC first in the following article though. I should also mention, this is new to me, and I’m no expert. This will be more of a high level overview, with examples of how to generate (believed to be) Quantum Resistant keys, via the SIBC Python library.
ECC, a foundation tech for encrypting web traffic, banking systems, and secure messaging, hinges on the hardness of the Elliptic Curve Discrete Logarithm Problem (ECDLP). In simple terms, while it’s easy to perform calculations in one direction on an elliptic curve, reversing these operations is incredibly difficult — making ECC robust against classical computational attacks.
But what about when we face sufficiently powerful Quantum Computers? These advanced machines, armed with algorithms like Shor’s, threaten to make what was once a difficult problem, easy, effectively breaking ECC. The quantum algorithm can solve ECDLP efficiently and so then, the hardness of the Elliptic Curve isn’t sufficient anymore.
All is not lost, though. The cryptographic community, ever resilient, is actively developing quantum-resistant algorithms. One of the most promising areas is super singular isogeny-based cryptography (SIBC). Unlike ECC, which relies on points on a curve, SIBC involves isogenies between elliptic curves — functions that preserve their structure while being computationally hard to reverse, even for quantum computers. I’m not going to go into detail about isogenies here, in all honesty this is new to me, and I’m still getting my head around it!
To illustrate, let’s explore sibc, a tool focusing on SIBC(from a user perspective, as things like the curves used etc, are abstracted away). It offers a glimpse into the practical implementation of quantum-resistant algorithms(rather than actually showing the complexity of them). For instance, generating a key pair in sibc involves commands like csidh-genkey and csidh-pubkey. These keys are encoded strings, not too different in appearance from ECC keys, but under the hood, they leverage the quantum-resistant properties of SIBC( which in real world use cases, could be for key exchange).
Python library:
GitHub — JJChiDguez/sibc: Supersingular Isogeny-Based Cryptography constructions (python-code library)
- Purpose:
sibcis designed for isogeny-based cryptographic primitives, providing a user-friendly interface for dealing with such schemes. - Integrated Schemes: Includes SIDH (Super singular Isogeny Diffie-Hellman), CSIDH (Commutative Super singular Isogeny Diffie-Hellman), and B-SIDH schemes.
- Formulae and Curve Types: Utilizes traditional and velusqrt formulae on Montgomery curve x-only projective coordinates.
- Prime and Quadratic Field Classes: Allows operating field elements as integers.
- Constant-Time Implementation: The cryptographic primitives are implemented to run in constant time relative to the number of field operations.
- Vulnerabilities: The library acknowledges a devastating attack against SIDH and SIKE by Castryck & Decru, which also extends to B-SIDH and B-SIKE. However, CSIDH is not affected by this attack.
Python Scripting with sibc
import os
import subprocessdef generate_csidh_keypair():
# existing keys in pwd?
if not os.path.exists('csidh_private_key.txt') or not os.path.exists('csidh_public_key.txt'):
# Generate the secret key
secret_key_command = "sibc csidh-genkey"
secret_key_output = subprocess.check_output(secret_key_command, shell=True)
# Save the secret
with open('csidh_private_key.txt', 'wb') as file:
file.write(secret_key_output)
# Derive the public key file, from the secret
public_key_command = "sibc csidh-pubkey csidh_private_key.txt"
public_key_output = subprocess.check_output(public_key_command, shell=True)
# Save the public key
with open('csidh_public_key.txt', 'wb') as file:
file.write(public_key_output)
def main():
generate_csidh_keypair()
if __name__ == "__main__":
main()
Example keys:
admin@host:~/sibc$ cat csidh_private_key.txt 9fIACfP4BADwDP4J9gbz9xP5/RP78f0RCvgQA/b+Df77BwP9+QkB/AL6Av/4/AAEAPkG/Pz8A/sB/fsDAQH9BQAEBAT8/AQA/AE=
admin@host:~/sibc$ cat csidh_public_key.txt tR8ULLece4AQBPHW2K8ZOILNrpp0BmxixcIEnHJBKfdLTQiqgO8CUGj3UuVoSuSYh3D1XZ5+XnG0hfOaaA+JGg==
- The private key is 592 bits long.
- The public key is 512 bits long.
These(key lengths)seem slightly odd, however much of the underlying intricacies are hidden when using the SIBC library. I’ll need to verify these! But as per the general rule of Post-QC, they are larger than typical keys we use today.
So, is the advent of Quantum computing a death sentence for ECC? The answer isn’t straightforward. While ECC, in its current form, could become vulnerable( and most of the experts say it will), the principles underlying elliptic curves are not being discarded but rather reimagined in quantum-resistant cryptography.
While quantum computing presents a significant challenge, it also pushes us towards more advanced cryptographic algorithms and mathematical concepts. Elliptic curve cryptography is evolving, not ending if you ask me! I for one will be happy to see the Elliptic Curve still being used in some form, well into the future.
Thanks for reading. I hope this was useful to someone out there!
