8 ms·
Implementing RSA in Python from Scratch
- Svetlitski 5y agoI feel like this article is missing a disclaimer that you should never, ever roll your own crypto and that this is purely an educational exercise.
- deleted 5y ago[deleted]
- sverhagen 5y agoI 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!
- dnautics 5y agoOn 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".
- tptacek 5y agoPart 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.
- criticaltinker 5y agoRelevant excerpt from stackexchange answer [1]: 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. [1] https://crypto.stackexchange.com/a/1449 https://crypto.stackexchange.com/a/1449
- olliej 5y agoI 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)!
- dagenix 5y agoMissing 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.
- laluser 5y agoI’m really curious about this as others have said similar things. What else is missing?
- DarkmSparks 5y agoThats a secret. Pretty sure the point is you should only use NSA approved implementations.
- criticaltinker 5y agoThings 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. [1] https://eprint.iacr.org/2021/1121.pdf https://eprint.iacr.org/2021/1121.pdf
- DarkmSparks 5y agothe article links to side channel attacks and making it constant time. so hardly a valid accusation that it missed them.
- lazide 5y agoFor 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.
- tzs 5y agoQuite a bit of that code can be eliminated if you use the 3 argument form of Python’s pow() function. pow(a, b, n) efficiently computes (a ** b) % n and pow(a, -1, n) finds b such that (a * b) % n == 1
- nxpnsv 5y agoI had no idea, that's awesome!
- bvrmn 5y agoA minor note: pow is able to calculate modulo inverse (pow(a, -1, n)) starting from python3.8.
- tzs 5y agoA 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.
- deleted 5y ago[deleted]
- vmilner 5y agoYes, I deleted it because I was being an idiot :) 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).
- deleted 5y ago[deleted]
- 5y ago
- DeepYogurt 5y agoGood article, but please don't roll your own crypto.
- ackbar03 5y agoI too am compelled to repeat the mantra, plz don't roll your own crypto
- formerly_proven 5y agootpyrc nwo ruoy llor t'nod
- ZanyProgrammer 5y agoIf you took that literally it would be impossible to learn cryptography.
- cpach 5y agoHere’s a good way to learn more about cryptography: https://cryptopals.com/ https://cryptopals.com/ https://research.nccgroup.com/2021/12/10/announcing-ncc-groups-cryptopals-guided-tour/ https://research.nccgroup.com/2021/12/10/announcing-ncc-grou...
- opheliate 5y agoAlso: https://cryptohack.org/ https://cryptohack.org/, which covers some more modern cryptography.
- deleted 5y ago[deleted]
- chlorion 5y agoPlease 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.
- throwaway81523 5y agoArticle 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.
- upofadown 5y agoSpeaking of curves, they have their weird gotchas as well which tend to get glossed over in simplified examples. A recent discussion: * https://research.nccgroup.com/2021/11/18/an-illustrated-guide-to-elliptic-curve-cryptography-validation/ https://research.nccgroup.com/2021/11/18/an-illustrated-guid...
- throwaway81523 5y agoThanks, 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.
- thrdbndndn 5y agoIs 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? I find it quite hard to grasp.
- _hl_ 5y agoFermat's little theorem. I'm not aware of an intuitive explanation unfortunately.
- thrdbndndn 5y agoAfter 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)".)
- enedil 5y agoλ(n) isn't the totient. As it was told, it's the Carmichael function.
- cryvate1284 5y agoCarmichael's Function is the name. https://en.m.wikipedia.org/wiki/Carmichael_function https://en.m.wikipedia.org/wiki/Carmichael_function
- ale42 5y agoI guess it is a purely didactic project to learn about RSA and related maths in Python?
- littlestymaar 5y agoMandatory 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] [1]: https://link.springer.com/chapter/10.1007%2F3-540-44448-3_3 https://link.springer.com/chapter/10.1007%2F3-540-44448-3_3
- zgs 5y agoDo *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.
- forgotmypw17 5y agoImplementing it yourself is a good way to understand how it works and is often part of required CS courses. I don't think the article said anything about using it in production.
- michaelcampbell 5y agoWe did exactly this in a Cybersecurity program at Georgia Tech.
- fps_doug 5y agoYou are right. 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 https://github.com/wqweto/VbAsyncSocket [2] https://docs.microsoft.com/en-us/previous-versions/visualstudio/visual-basic-6/visual-basic-6-support-policy https://docs.microsoft.com/en-us/previous-versions/visualstu...
- Faelian2 5y agoRelevant "Fuck RSA", or why you don't want to use this in the real world. https://youtu.be/lElHzac8DDI 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).
- upofadown 5y agoWhile 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. [1] https://en.wikipedia.org/wiki/PKCS_1 https://en.wikipedia.org/wiki/PKCS_1 [2] https://datatracker.ietf.org/doc/html/rfc8017 https://datatracker.ietf.org/doc/html/rfc8017
- tialaramex 5y agoThe 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.
- edmcnulty101 5y agojust Googled the three line equals sign and apparently that means identical to instead of simply equals to. 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)
- grenoire 5y agoArticle notes: 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.
- hexane360 5y agoSometimes 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".
- entropie 5y agoYears 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. Nice posts.
- SudoSH 5y agoI 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.
- fexelein 5y agojust make sure nobody ever uses it ;)
- fexelein 5y agoThis came to mind. Somebody used excel to implement RSA as an educational tool. https://m.youtube.com/watch?v=zxMNNwvhj94 https://m.youtube.com/watch?v=zxMNNwvhj94