Implementing RSA in Python from Scratch
coderoasis.com
coderoasis.com
With the code presented here and in the last article, you can make a working RSA encryption & decryption application. However, it still lacks protection from side-channel attacks.
These articles are describing something now known as "textbook" or "schoolbook" RSA, which is worth looking up.
A portion of the grade was determined by the speed of your code.
Because this was essentially only a course about number theory you can bet there were issues :)
First: no symmetric crypto, just rsa applied block by block
Second: no counter or chaining of blocks - eg encrypt(m) is the same for any m in the plaintext
Third: because there’s no symmetric cipher modular arithmetic becomes the overwhelming perf cost. My implementation had many many many possible timing attacks.
Fourth: the same key pair was used for encryption and signing. This clearly results in sadness.
Fifth: many of the implementations in the class operated performed an rsa operation for each byte in the input, making the lack of a proper block mode even worse. Mine operated at the maximum size the public key could handle, making it Secure (tm)!
Besides my day job, I'm still kinda-sorta fumbling around doing CS masters courses and ended up doing a similar project last semester.
The project I was doing was actually about power analysis side channel attacks (in a group of CS students, I was the only one who would take a project where you had to touch actual hardware), so the end game was getting my make-shift 128 bit RSA to run on an AVR.
The big-integer-code actually turned out to be the nastiest part of the whole thing. My initial naive implementation took several minutes on my desktop PC. A few long nights later, it ran in 30-ish seconds or so on the AVR, using the internal 1 MHz RC oscillator[1][2].
I initially expected the static power analysis to be a PITA, but finding the square-multiply-loop in the trace and triggering on it turned out to be surprisingly simple[3][4]. It was IMO kinda scary how easy that turned out to be.
So yes, even if you get the obvious cryptographic foot guns right (as opposed to the additional non-obvious foot guns), the possibility for additional side-channel attacks are also plenty.
[1] https://i.imgur.com/zk7IXKd.jpeg
[2] https://i.imgur.com/Ddu2sgo.jpg
I did a full TLS implementation from scratch a few years back - the big integer code was the nastiest part of all of TLS, including X.509 certificate parsing and validation.
Some (Undesirable) Properties of Textbook RSA:
It is malleable. I.e., if you give me a ciphertext 𝑐 which encrypts 𝑚, I can compute 𝑐′≡𝑐⋅2𝑒mod𝑛. When the owner of the private key decrypts 𝑐′, she will get 2𝑚mod𝑛. In other words, I can make predictable changes to ciphertexts.
It is deterministic, and thus not semantically secure. I.e., I can distinguish between the encryptions of 0 and 1 (simply by encrypting both values myself and comparing the ciphertexts).
Differences with Deployed RSA:
Padding
Chinese Remainder Theorem is sometimes used in deployed systems for more efficient decryption.
𝑒 is often statically set to 65537=2^16+1 for encryption speed (since there are only two set bits in that number).
Side-channel attack mitigations can be put in place for deployed systems too.
pow(a, b, n)
(a ** b) % n
pow(a, -1, n)
(a * b) % n == 1[1] if a and n are relatively prime then a^ϕ(n) ≡ 1 mod n.
Edit: someone replied to this wondering how Python implemented (a, -1, n). I looked into this once, remembered that I found it was reasonable, but did not remember how it actually did it. I took another look to answer that comment, but the comment has been deleted.
The answer is that it uses the extended Euclidean algorithm. The function long_invmod in Objects/longobject.c does the deed.
I was momentarily thinking pow(a,-1,n) would need to calculate phi(n) internally (a hard thing to do in general) but the EEA will of course do it very cheaply without needing to know phi(n).
It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
That only has a solution if a is relatively prime to n, and generally the best way to find that solution is to use the extended Euclidean algorithm [1].
Briefly because a and n are relatively prime, there exists integers x and y such that ax + ny = 1 [2]. The extended Euclidean algorithm finds x and y. But ax + ny mod n is just ax mod n, and so we have ax = 1 mod n. The b we seek is x.
[1] https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
Of course, assume a and n are relatively prime.
Then this is equivalent to finding a b such that (a % n + b % n) % n == 1.
We already know that 0 < a % n < n so simply picking b = n + 1 - a % n works. In fact, b = zn + 1 - a % n for any positive integer z works.
Your solution makes sense to me too but I wonder if I'm missing something obvious above?
Also, it is critical you use padding techniques that don’t allow chosen plaintext or similar. Ideally, you also don’t ever encrypt the actual data itself directly with RSA, as 1) it’s slow, and 2) stock RSA is deterministic (same key, same input, same output) and if you encrypt a lot of data that way you’ll end up leaking significant details that make it easier to guess the key or fake future correspondence. OAEP helps immensely here, but what is even better is using RSA + OAEP to exchange a disposable one time use symmetric key of decent strength (Say AES 256 bit) which the content is then encrypted in (say using CTR or GCM mode), which doesn’t have any of these problems.
You also can’t use the same key for signing and encryption.
You have to be sure your primes are actually prime (there have been bugs where ‘primes’ turned out to be composite)
Even if they are prime, some classes of prime are weaker for some reason involving maths I never understood.
I know there are more but my TLS days are mercifully far behind me :)
Treatments like the OP are accessible and can be helpful for beginners to understand RSA and public key crypto at a high level. However, the tradeoff is that critical details like side-channels are often neglected or not mentioned at all.
This tech news/blog of mine is a fun project for my friends and I to do... I just want to offer good tech reads to people about the subjects which we know best.
The support overall here is amazing. I was suggested by a good friend of mine to share it here to see what happens. Wow. Just wow.
RSA is very well understood at this point. Rather than obsessing over the wrong way to do it we should be showing people the right way. There is no reason to present simplified examples without reference to the standard.
* https://research.nccgroup.com/2021/11/18/an-illustrated-guid...
Hankerson, Menezes, and Vanstone's "Guide to Elliptic Curve Cryptography" is very helpful if you are trying to implement ECC for some reason. Most of us are probably better off using an existing implementation.
This is a very dangerous article. The basic RSA algorithm is quite simple to implement, although the most difficult part isn't done in this article -- multi-precision multiplication is the difficult part in my experience.
However, using this implementation cryptographically is very bad. A cryptographically good implementation needs to consider a lot more than just the basic algorithm. Is the implementation constant time? Does it including blinding? How is it padded? These are just the basics, they are plenty more subtleties. Then people want it fast.
RSA should not be used to encrypt plaintext. Simplistically: symmetric cryptographic algorithms are first used and then RSA is used to encrypt the key.
What is a good idea however, is to implement a TLSv1.3 library in Visual Basic 6[1], that doesn't have any external dependencies, by embedding machine code for AES encryption generated with MSVC in the source code, that you patch into memory at runtime, by using all sorts of tricks to do things in VB6 that you aren't supposed to do in VB6. Yes, that VB6, that was released in 1998, superseded by VB.NET in 2002. Because Microsoft has just announced it's supported on Windows 11.[2] So when developing new software, why not use something future-proof? ;)
[1] https://github.com/wqweto/VbAsyncSocket
[2] https://docs.microsoft.com/en-us/previous-versions/visualstu...
I don't think the article said anything about using it in production.
Now, probably there are less people rolling their own crypto than there are people running their own, say... application framework, or ORM. Because crypto has more of a general feeling of "it's hard" about it. But I am still suspicious that there wouldn't be a bunch of folks out there who had to prove to their team that they were smart enough to roll their own crypto too, and are now stuck with it!
I find it quite hard to grasp.
I think the author probably should give the definition of the function first, and then say it fits the equation "x^λ(n) ≡ 1 (mod n) for any x such that gcd(x, n) = 1" due to the theorem, insteads of the other way around (λ(n) is a number that match this equation).
(Also, it probably is more intuitive to say "x^λ(n) - 1 is a multiple of n" than "x^λ(n) ≡ 1 (mod n)".)
[1]: https://link.springer.com/chapter/10.1007%2F3-540-44448-3_3
(That being said, I think it's still interesting to do this to understand RSA, but please don't roll out your own crypto).
I was surely impressed how easy to comprehend that was and respected even more they guys who invented it.
Nice posts.
I can see this in the context of programming objects.
How does this apply in the context of math which is all primitives (in my understanding)
Other times it's used to indicate equivalence or congruence with respect to some equivalency class. In other words, it's a weaker form of equality, the opposite of how's it's used in, say, Javascript. For instance, (1, 2) === (2, 4) over the equivalency class of the rational numbers.
The latter is how it's used in this context. a === b (mod c) means that "a is congruent to b under the mod c equivalency relation".
a ≡ b (mod n) means that there is an integer x such that a + nx = b. A more intuitive explanation is that the reminder of a / n equals the reminder of b / n.
https://research.nccgroup.com/2021/12/10/announcing-ncc-grou...
Instead tell people to roll whatever they want, but not to use it or allow others to use it for anything serious.
There is a big difference between these two things, and having young people and new people learn about how cryptography works is extremely important going forward.