Discussion
RSA and Python
gmiller123456: One of the bigger hurdles in implementing RSA is having an algorithm which can multiply the large numbers in real time. If you try a niave multiplication algorithm, you might find you'll never get an answer. A lot of hardware now comes with special instructions which implement efficient algorithms for doing this.
ashwinnair99: RSA is one of those algorithms where understanding it once actually sticks.
MattPalmer1086: Sure, you can't use built in multiplication, but it isn't a very big hurdle. Just use repeated squares, it's fairly trivial to implement. I've worked on software that did this on very low power mobile payment devices.
dfboyd: The way the article uses RSA is no better than a simple substitution cipher. Both the "l"s in "hello" are enciphered to 2575. It's a newspaper cryptogram.You're supposed to concatenate all the input numbers, to create a message that has hundreds or thousands of digits; then RSA-encrypt that number.
nayuki: I have a different take on the same topic: https://www.nayuki.io/page/java-biginteger-was-made-for-rsa-...My article isn't written as a step-by-step tutorial and doesn't come with example numbers. But mine fills in certain things that xnacly doesn't cover: random prime generation, efficiently calculating the decryption exponent d from (n, e) by using a modular inverse, using modular exponentiation instead of power-then-modulo.By the way for Python, modular exponentiation is pow(x, y, m) (since 3.0), and modular inverse is pow(x, -1, m) (since 3.8, Oct 2019). https://docs.python.org/3/library/functions.html#pow
SkiFire13: Repeated squares is a way to implement exponentiation, not multiplication.
pfortuny: And pad! Padding for RSA is like CDM (?) for AES.
hannob: > You're supposed to concatenate all the input numbers, to create a message that has hundreds or thousands of digits; then RSA-encrypt that number.That's not how it works...In modern protocols, you don't encrypt at all with RSA. You use a key exchange, and if you use RSA, you only use it as a signature algorithm to initiate the key exchange.If you happen to want to encrypt with RSA, which you usually shouldn't, you first use a padding algorithm (the modern variant of that is called RSA-OAEP) with which you prepare and then encrypt a random key. That key you then use for symmetric encryption.
MattPalmer1086: Oops, yes, I meant exponentiation. Which you need (mod n) in RSA.
