alt Hacker NewsRSA and Python
Comments
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.
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
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.
I made a similar tutorial for RSA and DH in Easylang—a learning and teaching programming language I developed myself. What makes things a bit difficult is that Easylang doesn't support big numbers.
RSA is one of those algorithms where understanding it once actually sticks.
> Should you use RSA in production always make sure to use numbers which are at least 512 Bit / 64 Byte long.
512-bit RSA has been breakable, by academics, since before this millennium.
> RSA number | Decimal digits | Binary digits | Cash prize offered | Factored on | Factored by
> RSA155 | 155 | 512 | US$9,383[8] | August 22, 1999 | Herman te Riele et al.
https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
Further, according to authors of the paper factoring RSA-768 (bit), in 2009/10
> it would be prudent to phase out usage of 1024-bit RSA within the next three to four years. (p1, 2010)
https://eprint.iacr.org/2010/006.pdf