Skip to main content

Can AI Break RSA Encryption?

We’re told that it will take powerful quantum computers to break RSA encryption, so for now the world is safe. But I wondered, in an era of increasingly sophisticated models, might AI pose a threat? These systems excel at finding patterns in data that humans miss, and if there were any subtle weaknesses in key generation, I would think AI could detect them.

Yes, theory says it’s all but impossible to break RSA because it relies on the computational hardness of factoring large prime numbers. But theory and practice don’t always align, and sometimes the most interesting discoveries come from testing our assumptions. So I set up an experiment to test whether a transformer model could learn to reverse-engineer SSH private keys from their corresponding public keys.

Experiment and Results

I trained a T5-small transformer model (60 million parameters) on a dataset of 50,000 SSH key pairs, split into 70% training, 15% validation, and 15% test. Given a public key as input, the model was asked to output the corresponding private key.

For hardware reasons, I decided to work with a smaller model (I could provision more resources and try a larger model if the results indicated something interesting). As it was, the experiment ran “comfortably” on my Mac M1, with 1 epoch taking about 15 hours.

In the first 25% of training, the model quickly learned. Loss dropped from 7.66 to 4.58. I suspected it was learning superficial structure, such as base64 encoding patterns and the standard SSH private key file header and footer. But the loss soon plateaued, stabalizing around 4.56-4.54, with only tiny improvements during the remainder of training. The validation loss showed similar behavior, decreasing from 4.52 to 4.49 over the final 50% of training. this suggests the model had hit a barrier.

For RSA-2048, the probability of randomly guessing a private key is approximately 2-2048, which is essentially zero. So, this sort of stagnation is exactly what we’d hope to see. The model had reached the the point where it had exhausted all learnable patterns except the actual mathematical relationship.

When I tested the trained model on unseen public keys, the results were reassuring. The model generated outputs that were structurally correct but cryptographically invalid. The first ~80 characters were identical, but this is the OpenSSH private key header. Where the actual cryptographic material begins, the outputs diverged.

Conclusion

I’d like to think this experiment provides empirical validation of RSA’s security against pattern-based attacks. A 60-million parameter transformer, trained on 50,000 unique examples, could not find any exploitable patterns in SSH key generation. And the plateau suggests further attempts with a larger model or more training would continue to be unsuccessful. The model did indeed learn formatting, but failed at the cryptographic content.

So much for any interesting discoveries. At least the world is indeed safe … at least for now.

Code for this experiment is available on GitHub.

Labels:

Comments

Post a Comment

Popular posts from this blog

Writing a Minimal PSR-0 Autoloader

An excellent overview of autoloading in PHP and the PSR-0 standard was written by Hari K T over at PHPMaster.com , and it's definitely worth the read. But maybe you don't like some of the bloated, heavier autoloader offerings provided by various PHP frameworks, or maybe you just like to roll your own solutions. Is it possible to roll your own minimal loader and still be compliant? First, let's look at what PSR-0 mandates, taken directly from the standards document on GitHub : A fully-qualified namespace and class must have the following structure \<Vendor Name>\(<Namespace>\)*<Class Name> Each namespace must have a top-level namespace ("Vendor Name"). Each namespace can have as many sub-namespaces as it wishes. Each namespace separator is converted to a DIRECTORY_SEPARATOR when loading from the file system. Each "_" character in the CLASS NAME is converted to a DIRECTORY_SEPARATOR . The "_" character has no special ...
6 comments
Read more

Safely Identify Dependencies for Chrooting

The most difficult part of setting up a chroot environment is identifying dependencies for the programs you want to copy to the jail. For example, to make cp available, not only do you need to copy its binary from /bin and any shared libraries it depends on, but the dependencies can have their own dependencies too that need to be copied. The internet suggests using ldd to list a binary’s dependencies, but that has its own problems. The man page for ldd warns not to use the script for untrusted programs because it works by setting a special environment variable and then executes the program. What’s a security-conscious systems administrator to do? The ldd man page recommends objdump as a safe alternative. objdump outputs information about an object file, including what shared libraries it links against. It doesn’t identify the dependencies’ dependencies, but it’s still a good start because it doesn’t try to execute the target file. We can overcome the dependencies of depende...
Post a Comment
Read more

A Unicode fgetc() in PHP

In preparation for a presentation I’m giving at this month’s Syracuse PHP Users Group meeting, I found the need to read in Unicode characters in PHP one at a time. Unicode is still second-class in PHP; PHP6 failed and we have to fallback to extensions like the mbstring extension and/or libraries like Portable UTF-8 . And even with those, I didn’t see a unicode-capable fgetc() so I wrote my own. Years ago, I wrote a post describing how to read Unicode characters in C , so the logic was already familiar. As a refresher, UTF-8 is a multi-byte encoding scheme capable of representing over 2 million characters using 4 bytes or less. The first 128 characters are encoded the same as 7-bit ASCII with 0 as the most-significant bit. The other characters are encoded using multiple bytes, each byte with 1 as the most-significant bit. The bit pattern in the first byte of a multi-byte sequence tells us how many bytes are needed to represent the character. Here’s what the function looks like: f...
1 comment
Read more