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.
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.
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.
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? ;)
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!
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?
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.
[+] [-] tptacek|4 years ago|reply
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.
[+] [-] tzs|4 years ago|reply
[+] [-] bvrmn|4 years ago|reply
[+] [-] unknown|4 years ago|reply
[deleted]
[+] [-] nxpnsv|4 years ago|reply
[+] [-] chrisseaton|4 years ago|reply
[+] [-] omegalulw|4 years ago|reply
It's (a % n + b % n) == 1. So pick b = a + 1 - a % n and you are done?
[+] [-] dagenix|4 years ago|reply
[+] [-] laluser|4 years ago|reply
[+] [-] SudoSH|4 years ago|reply
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.
[+] [-] upofadown|4 years ago|reply
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.
[1] https://en.wikipedia.org/wiki/PKCS_1
[2] https://datatracker.ietf.org/doc/html/rfc8017
[+] [-] tialaramex|4 years ago|reply
[+] [-] throwaway81523|4 years ago|reply
[+] [-] zgs|4 years ago|reply
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.
[+] [-] johnisgood|4 years ago|reply
[+] [-] fps_doug|4 years ago|reply
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...
[+] [-] forgotmypw17|4 years ago|reply
I don't think the article said anything about using it in production.
[+] [-] Buttons840|4 years ago|reply
[+] [-] Svetlitski|4 years ago|reply
[+] [-] sverhagen|4 years ago|reply
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!
[+] [-] unknown|4 years ago|reply
[deleted]
[+] [-] thrdbndndn|4 years ago|reply
I find it quite hard to grasp.
[+] [-] littlestymaar|4 years ago|reply
[1]: https://link.springer.com/chapter/10.1007%2F3-540-44448-3_3
[+] [-] Faelian2|4 years ago|reply
https://youtu.be/lElHzac8DDI
(That being said, I think it's still interesting to do this to understand RSA, but please don't roll out your own crypto).
[+] [-] entropie|4 years ago|reply
I was surely impressed how easy to comprehend that was and respected even more they guys who invented it.
Nice posts.
[+] [-] ale42|4 years ago|reply
[+] [-] fexelein|4 years ago|reply
https://m.youtube.com/watch?v=zxMNNwvhj94
[+] [-] edmcnulty101|4 years ago|reply
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)
[+] [-] hexane360|4 years ago|reply
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".
[+] [-] grenoire|4 years ago|reply
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.
[+] [-] fexelein|4 years ago|reply
[+] [-] DeepYogurt|4 years ago|reply
[+] [-] ZanyProgrammer|4 years ago|reply
[+] [-] chlorion|4 years ago|reply
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.
[+] [-] ackbar03|4 years ago|reply
[+] [-] formerly_proven|4 years ago|reply