Part 2 of this article seems to explain that to encrypt arbitrary plaintexts, those larger than 256 bytes, you should chunk your messages up, pad the last block, and encrypt with RSA-ECB.
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.
I remember a cryptography project at uni where we had to implement RSA - that is everything including the large integer support.
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)!
> I remember a cryptography project at uni where we had to implement RSA - that is everything including the large integer support.
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.
> The big-integer-code actually turned out to be the nastiest part of the whole thing
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.
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.
A minor note to your minor note: if you are on an earlier Python but happen to know ϕ(n), you can use Euler's theorem [1] to replace pow(a, -1, n) with pow(a, ϕ(n)-1, n).
[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).
Python allows for overloading these operators, and has dynamic types, so cannot produce the more efficient byte code on load. Most python interpreters also don't have JIT compilers that could do the optimization on the fly.
Hmm.. when you compile to byte code you could emit a single POW_MOD instruction, and then dispatch to the more efficient code if both methods remain un-redefined, or call the full methods if one or more has been redefined.
I think you are looking to find b such that a + b = 1 mod n. The problem is to find b such that a x b = 1 mod n.
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.
Thanks! Reading my comment again it's clear I had a brain fart during writing the comment but I was indeed trying to solve: find b such that (a + b) % n == 1.
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?
Sry, I had a brain fart again. My solution won't work, it's for a different problem. I can't delete comments from my phone and I think for the addition problem it's a reasonable solution so I'll just leave it.
Missing from the article is a warning about how hard it actually is to make RSA secure. There are a _ton_ of footguns that are easy to miss which can result in a totally broken implementation. So, nifty article and all - but there really should be a disclaimer that an actual implementation is an order of magnitude more complex once you take into account all of those gotchas.
For one, it is critical that you don’t use the same key for signing as you do for encryption.
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.
The article mentions timing, though it’s important to realize that RSA is resistant to constant time - you can mitigate this with some random work making use of ‘X mod N’ is the same as ‘AXA^-1 mod N’
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 :)
To give one potential example: it appears that some primes are likely to be less secure than other primes. I don't really have much background info on this to provide here, so you'll want to Google around, but I'll leave a couple of links to more reading. (There are probably better links I'm not aware of.) I just know enough to know that it's a bad idea to implement asymmetric cryptography without fully understanding the number theory behind it.
Things like constant-time arithmetic are essential for safe and correct cryptography [1].
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.
I was never expecting to wake up to all of this.... nor even expecting to get noticed with all of the amazing content and everything that's already shared.
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.
While there are multiple warnings about textbook RSA here in the comments there are currently no direct references to what you are actually supposed to do. The Wikipedia page for PKCS 1[1] provides some basic references. There is a RFC[2].
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.
The Right Thing in 2021 is to not do RSA encryption. RSA signatures work fine, but RSA encryption has too many footguns and doesn't offer enough benefit to make that acceptable.
Article is somewhat mathematically educational but cryptographically not so great. e=35537 is a weird choice: 65537 is more common since it has low Hamming weight, i.e. you just do some squaring and one multiplication. You should not encrypt the plaintext directly, but rather use an encoding like OAEP (if that has not fallen out of favor by now). See whatever the current PKCS standards are. Finally, RSA itself has fallen out of favor, which elliptic curve methods now preferred.
Thanks, that is a good article. There are a lot of tricks to implementing ECC efficiently (besides correctly), enough that writing a competitive DIY implementation is a lot of work even if you know what you're doing. That's in contrast with RSA, where the work is all in the modular exponentiation operation, which is already carefully optimized in libraries like GMP (so just call GMP and you are done).
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.
Do *not* implement your own cryptography. There are a lot of nuances.
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.
Implement your own cryptography library, just be careful about using it. Why are we telling people to not learn by doing? You can even get some constructive criticism if you post it here. :)
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? ;)
The amount of corporate cognitive dissonance required to refuse to acknowledge that dropping VB was a huge mistake and yet continue to support it - because it’s still widely used because it’s so effective - over 25 years must be staggering.
Those who want to weaken cryptography now or in the future smile every time the advice to not implement your own cryptography is given. (Which is not to say everyone giving the advice wants to weaken cryptography, and yes, there are real reason to be extra careful.)
I totally agree. But meanwhile, I'm wondering if the droves of people that I have met who forego proven libraries and frameworks to roll their own, wouldn't also just do the same for crypto? Because exactly the integration and maintenance and socialization of these projects are underestimated.
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!
On the other hand I once had a CTO get mad at me because I customized a few options in the builtin TLS library for erlang (I made it possible to sign the keys against an IP address instead of only FQDNs, which was fine for our use case) - for "rolling your own crypto".
Is there an "intuitive explanation" for the part "λ(n) is a number such that x^λ(n) ≡ 1 (mod n) for any x such that gcd(x, n) = 1. From this you can conclude that x^a ≡ x^b (mod n) if a ≡ b (mod λ(n))", or a formal name for such "λ(n)" so I can search around?
After reading about it, I assume the λ(n) here is the Euler's totient function.
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)".)
Mandatory reading for anyone wanting to implement RSA by themselves (even if it's for fun): Why Textbook ElGamal and RSA Encryption Are Insecure Bonehn, Joux, Nguyen − 2000 [1]
Years ago I watched a lecture from some CCC dood on a small local event (leipzig) and he pretty much explained RSA on simple mathematical samples with bc.
I was surely impressed how easy to comprehend that was and respected even more they guys who invented it.
Sometimes it's used to mean "defined as". I.e. you're saying "Let <LHS> be the value computed by <RHS>", rather than saying "<LHS>, which is defined elsewhere, is equal in value to <RHS>".
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.
Please don't tell people to not roll their own crypto.
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.
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.