4 ms·

RSA and Python

26 points by ibobev 7mo ago

ashwinnair99 7mo ago
RSA is one of those algorithms where understanding it once actually sticks.
gmiller123456 7mo ago
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.
- MattPalmer1086 7mo ago
  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.
  - SkiFire13 7mo ago
    Repeated squares is a way to implement exponentiation, not multiplication.
    - MattPalmer1086 7mo ago
      Oops, yes, I meant exponentiation. Which you need (mod n) in RSA.
dfboyd 7mo ago
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.
- pfortuny 7mo ago
  And pad! Padding for RSA is like CDM (?) for AES.
- NewsaHackO 7mo ago
  I thought it was a padding scheme, where you use a moving mask to obscure the plaintext, then encrypt that. Since it's being XOR'ed, adjacent characters will not have the same encryption values anymore. Sort of like using CBC instead of ECB for block ciphers. However, because this article is about the maths with RSA itself, he probably correctly thought it was not relevant to what he was writing about and would just unnecessarily complicate things.
- hannob 7mo ago
  > 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.
nayuki 7mo ago
I have a different take on the same topic: https://www.nayuki.io/page/java-biginteger-was-made-for-rsa-cryptography 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 https://docs.python.org/3/library/functions.html#pow
- vivzkestrel 7mo ago
  could you add a step by step tutorial like the OP here?
chkas 7mo ago
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. https://easylang.online/apps/tut_publk.html https://easylang.online/apps/tut_publk.html
mcint 7mo ago
> 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 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 https://eprint.iacr.org/2010/006.pdf

26 points by ibobev 7mo ago

RSA is one of those algorithms where understanding it once actually sticks.

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.

MattPalmer1086 7mo ago
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.
- SkiFire13 7mo ago
  Repeated squares is a way to implement exponentiation, not multiplication.
  - MattPalmer1086 7mo ago
    Oops, yes, I meant exponentiation. Which you need (mod n) in RSA.

dfboyd 7mo ago

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.

pfortuny 7mo ago
And pad! Padding for RSA is like CDM (?) for AES.
NewsaHackO 7mo ago
I thought it was a padding scheme, where you use a moving mask to obscure the plaintext, then encrypt that. Since it's being XOR'ed, adjacent characters will not have the same encryption values anymore. Sort of like using CBC instead of ECB for block ciphers. However, because this article is about the maths with RSA itself, he probably correctly thought it was not relevant to what he was writing about and would just unnecessarily complicate things.
hannob 7mo ago
> 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.

nayuki 7mo ago

I have a different take on the same topic: https://www.nayuki.io/page/java-biginteger-was-made-for-rsa-cryptography 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 https://docs.python.org/3/library/functions.html#pow

vivzkestrel 7mo ago
could you add a step by step tutorial like the OP here?

chkas 7mo ago

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. https://easylang.online/apps/tut_publk.html https://easylang.online/apps/tut_publk.html

mcint 7mo ago

> 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 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 https://eprint.iacr.org/2010/006.pdf