5 ms·

What I find interesting about RSA is how it became so popular and important in our daily life, yet it uses basic math from hundred or thousands of years back.

What I find interesting about RSA is how it became so popular and important in our daily life, yet it uses basic math from hundred or thousands of years back. It uses the Fermat's little theorem of prime numbers, which was defined in 1640 then proved by Euler almost 100 years after that. Plus uses the Chinese reminder theorem that was discovered in the 300 CE What is more crazy is that RSA (or something comparable to that) was discovered in parallel also by another mathematician working for a government agency 4 years prior to the RSA algo

eric__cartman 4y ago
I really enjoyed a piece of coursework that I was given on a discrete mathematics course that consisted of implementing RSA using the math theory taught in class. It's a very clever algorithm.
oraetlabora 4y ago
> yet it uses basic math from hundred or thousands of years back as if that was an argument. We use the wheel for a gazillion o "important and f daily life" applications.
- ausudhz 4y ago
  Great, you totally missed the point. While the wheel has been used from the next day of its invention till today, the Fermat's little theorem had no application outside of pure math for roughly 400 years.
  - trompetenaccoun 4y ago
    To be fair there was no obvious point, so how could it be missed? You simply wrote it's interesting without explaining what you find interesting about it.
    - ausudhz 4y ago
      [flagged]
      - Dylan16807 4y ago
        Knowing when Fermat's little theorem gets used outside math is not basic knowledge!
        ausudhz 4y ago
        [flagged]
        Dylan16807 4y ago
        Those classes might mention this use. They're unlikely to teach students that it wasn't used elsewhere (outside math) until then, which is a crucial part of the point you were making. Seriously, that specific aspect is trivia, not basic knowledge, even in the realm of cryptography.
        ausudhz 4y ago
        Though there could've been different ways to ask rather than saying, arrogantly, "wheel is used everyday too"
        deleted 4y ago
        [deleted]
        deleted 4y ago
        [deleted]
        imwillofficial 4y ago
        I’ve taken many a crypto class and never picked up that nugget. You made a social misstep. Accept the correction with grace, try to be better, and move on.
kybernetikos 4y ago
> What is more crazy is that RSA (or something comparable to that) was discovered in parallel also by another mathematician working for a government agency 4 years prior to the RSA algo That story is great - he was a new grad and given it as an exercise by his mentor. He wasn't allowed to write anything down at home so he worked it out entirely in his head that evening.
timthorn 4y ago
> What is more crazy is that RSA (or something comparable to that) was discovered in parallel also by another mathematician working for a government agency 4 years prior to the RSA algo Cocks, Ellis and Williamson at GCHQ: https://www.nsa.gov/History/Cryptologic-History/Historical-Figures/Historical-Figures-View/Article/3006218/clifford-cocks-james-ellis-and-malcolm-williamson/ https://www.nsa.gov/History/Cryptologic-History/Historical-F... An interview with Cocks and Ralph Benjamin: https://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/ https://www.zdnet.com/article/gchq-pioneers-on-birth-of-publ...
anothernewdude 4y ago
They also all use addition, which was invented so long ago, we don't know when it was.
newpavlov 4y ago
Try to run a non-toy RSA by hand using pen and paper, it will be quite painful and impractical. Practicality of RSA largely depends on existence of computers. Even in the presence of all required theoretical knowledge, an application may not be practical, thus it does not get "invented" until the practicality issue gets resolved. I would say it's more interesting that one-time pad encryption was not invented and used much earlier than 19th century. It has obvious military and intelligence uses and is simple enough to be executed by hand.
- ausudhz 4y ago
  For centuries people have been encrypting things "by hand" and "inconveniently" (Cesar's cipher is an example, I can make many more). RSA doesn't largely depends on the existence of computer, it could've been used "by hand" using the math behind it. The reason why was not is because, prior to computer, there was not a problem of "sharing" the key (and btw Nazi knew that a single key was weak, that's why they'd change it everyday to encrypt the communication with enigma) > I would say it's more interesting that one-time pad encryption was not invented and used much earlier than 19th century That's not true, as I mentioned Cesar's cipher is an example of that, though of course uses a simple key. Radio communications (and of course internet later) is the reason why encryption started to boom on the early 19th century onwards.
  - Hendrikto 4y ago
    Ceasar’s cipher is neither complex nor an OTP. What are you talking about?
    - ausudhz 4y ago
      What are you talking about. That was the first cipher. RSA is OTP?
      - nvrspyx 4y ago
        The point originally made was that RSA couldn't practically be used because of how complex the math is to do by hand. So, the parent is pointing out that the Caesar cipher isn't a counterargument. In other words, the "inconvenience" of doing a Caesar cipher by hand is nowhere near comparable as doing an RSA cipher by hand.
nickjj 4y ago
RSA SSH keys are starting to become phased out. Ubuntu 22.04 for example won't let you SSH into another server using an RSA key unless you configure your OpenSSH client to continue supporting RSA. I noticed this even with an RSA SHA-256 key[0]. GitHub and other git hosting providers are also pushing Ed25519 over RSA for generating new keys. I would say it's had a good run, and will likely still be in use for decades because there's always going to be systems that can't updated for whatever reasons. [0]: https://nickjanetakis.com/blog/switching-from-an-rsa-ssh-key-to-ed25519-on-ubuntu-2204 https://nickjanetakis.com/blog/switching-from-an-rsa-ssh-key...
- ryukafalz 4y ago
  This is not correct. The ssh-rsa signature algorithm is being phased out, but that's not the same thing as RSA keypairs for authentication. This page has a good explanation of what's going on: https://levelup.gitconnected.com/demystifying-ssh-rsa-in-openssh-deprecation-notice-22feb1b52acd https://levelup.gitconnected.com/demystifying-ssh-rsa-in-ope... It's unfortunate that there's a signature algorithm and a key format with the same name, because that definitely leads to confusion in cases like this. But RSA keypairs are fine for now.
  - nickjj 4y ago
    > It's unfortunate that there's a signature algorithm and a key format with the same name, because that definitely leads to confusion in cases like this. Thanks for the clarification, but from the end user's perspective it's all the same in the end? It translates to "I have an SSH keypair that was generated using RSA as the algorithm and I was able to SSH into my servers when using OpenSSH vX.X.X and now after updating OpenSSH to a newer version I can no longer SSH into the same servers.". In the end it used to work and now it doesn't and the solution is to pick a different algorithm such as Ed25519 or re-configure your OpenSSH client to continue allowing RSA even though the creators of OpenSSH have deprecated it by default.
    - ryukafalz 4y ago
      It's not quite the same in the end from the end user's perspective, no. If you were logging into servers running a recent-ish version of OpenSSH (i.e. newer than 2016), you would continue to be able to log in with your RSA keypairs with no changes, because the client and server would still be able to negotiate a signature algorithm that both support. It just so happens that very old versions of OpenSSH don't support any of the signature algorithms used with RSA keys that new clients prefer to use. In other words: > or re-configure your OpenSSH client to continue allowing RSA even though the creators of OpenSSH have deprecated it by default ^ this is not correct. RSA is not deprecated by default. A specific signature algorithm used with RSA keys is deprecated. But yes, if your server is running a very old version of OpenSSH, that may be the only signature algorithm it supports. I'm not sure there are any distro releases running versions of OpenSSH this old that aren't EOL though, so really you should probably update your servers, which would also take care of this. (I suppose if you're running CentOS 7 or RHEL 7 you still get security updates for the next 1.5 years at least, but it's no longer actively supported.)
contravariant 4y ago
You'll want Euler's theorem (one of the many) for RSA, it won't be much use to have a prime number as a key since it's not exactly hard to guess its factorisation. That moves your date by a hundred years, into the later half of the 18th century. So not exactly thousands of years back.
- ausudhz 4y ago
  Chinese reminder theorem is from 300 CE. 1700 years ago. That's actively used in some libraries to validate the key (as stated in the link) Euler just proved what Fermat theorized.
  - contravariant 4y ago
    Euler was also the one to generalise the result to non-prime integers. He could have used the Chinese remainder theorem to do so but the first know use of it by western mathematicians was due to Gauss in 1801. To be fair mathematics was really close for a really long time, but before that generalisation not all of the ingredients were there at the same place at the same time. It might well have been possible for the Chinese or Hindu-Arabic mathematicians to discover Fermat's theorem or perhaps even Lagrange's theorem (which is how I'd prove it from scratch if necessary), but as far as I can tell they did not.
aflag 4y ago
To be fair, most of popular and important algorithms and tools in our daily lives are likely even older than that. Arithmetic takes you a very long way. RSA is quite mathematically sophisticated (and recent) next to most of the algorithms we use. Also, look around your kitchen and you'll see a lot of tools that haven't changed much in millenia.
deleted 4y ago
[deleted]

eric__cartman 4y ago

I really enjoyed a piece of coursework that I was given on a discrete mathematics course that consisted of implementing RSA using the math theory taught in class. It's a very clever algorithm.

oraetlabora 4y ago

> yet it uses basic math from hundred or thousands of years back as if that was an argument. We use the wheel for a gazillion o "important and f daily life" applications.

ausudhz 4y ago
Great, you totally missed the point. While the wheel has been used from the next day of its invention till today, the Fermat's little theorem had no application outside of pure math for roughly 400 years.
- trompetenaccoun 4y ago
  To be fair there was no obvious point, so how could it be missed? You simply wrote it's interesting without explaining what you find interesting about it.
  - ausudhz 4y ago
    [flagged]
    - Dylan16807 4y ago
      Knowing when Fermat's little theorem gets used outside math is not basic knowledge!
      - ausudhz 4y ago
        [flagged]
        Dylan16807 4y ago
        Those classes might mention this use. They're unlikely to teach students that it wasn't used elsewhere (outside math) until then, which is a crucial part of the point you were making. Seriously, that specific aspect is trivia, not basic knowledge, even in the realm of cryptography.
        ausudhz 4y ago
        Though there could've been different ways to ask rather than saying, arrogantly, "wheel is used everyday too"
        deleted 4y ago
        [deleted]
        deleted 4y ago
        [deleted]
        imwillofficial 4y ago
        I’ve taken many a crypto class and never picked up that nugget. You made a social misstep. Accept the correction with grace, try to be better, and move on.

kybernetikos 4y ago

> What is more crazy is that RSA (or something comparable to that) was discovered in parallel also by another mathematician working for a government agency 4 years prior to the RSA algo That story is great - he was a new grad and given it as an exercise by his mentor. He wasn't allowed to write anything down at home so he worked it out entirely in his head that evening.

timthorn 4y ago

> What is more crazy is that RSA (or something comparable to that) was discovered in parallel also by another mathematician working for a government agency 4 years prior to the RSA algo Cocks, Ellis and Williamson at GCHQ: https://www.nsa.gov/History/Cryptologic-History/Historical-Figures/Historical-Figures-View/Article/3006218/clifford-cocks-james-ellis-and-malcolm-williamson/ https://www.nsa.gov/History/Cryptologic-History/Historical-F... An interview with Cocks and Ralph Benjamin: https://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/ https://www.zdnet.com/article/gchq-pioneers-on-birth-of-publ...

anothernewdude 4y ago

They also all use addition, which was invented so long ago, we don't know when it was.

newpavlov 4y ago

Try to run a non-toy RSA by hand using pen and paper, it will be quite painful and impractical. Practicality of RSA largely depends on existence of computers. Even in the presence of all required theoretical knowledge, an application may not be practical, thus it does not get "invented" until the practicality issue gets resolved. I would say it's more interesting that one-time pad encryption was not invented and used much earlier than 19th century. It has obvious military and intelligence uses and is simple enough to be executed by hand.

ausudhz 4y ago
For centuries people have been encrypting things "by hand" and "inconveniently" (Cesar's cipher is an example, I can make many more). RSA doesn't largely depends on the existence of computer, it could've been used "by hand" using the math behind it. The reason why was not is because, prior to computer, there was not a problem of "sharing" the key (and btw Nazi knew that a single key was weak, that's why they'd change it everyday to encrypt the communication with enigma) > I would say it's more interesting that one-time pad encryption was not invented and used much earlier than 19th century That's not true, as I mentioned Cesar's cipher is an example of that, though of course uses a simple key. Radio communications (and of course internet later) is the reason why encryption started to boom on the early 19th century onwards.
- Hendrikto 4y ago
  Ceasar’s cipher is neither complex nor an OTP. What are you talking about?
  - ausudhz 4y ago
    What are you talking about. That was the first cipher. RSA is OTP?
    - nvrspyx 4y ago
      The point originally made was that RSA couldn't practically be used because of how complex the math is to do by hand. So, the parent is pointing out that the Caesar cipher isn't a counterargument. In other words, the "inconvenience" of doing a Caesar cipher by hand is nowhere near comparable as doing an RSA cipher by hand.

nickjj 4y ago

RSA SSH keys are starting to become phased out. Ubuntu 22.04 for example won't let you SSH into another server using an RSA key unless you configure your OpenSSH client to continue supporting RSA. I noticed this even with an RSA SHA-256 key[0]. GitHub and other git hosting providers are also pushing Ed25519 over RSA for generating new keys. I would say it's had a good run, and will likely still be in use for decades because there's always going to be systems that can't updated for whatever reasons. [0]: https://nickjanetakis.com/blog/switching-from-an-rsa-ssh-key-to-ed25519-on-ubuntu-2204 https://nickjanetakis.com/blog/switching-from-an-rsa-ssh-key...

ryukafalz 4y ago
This is not correct. The ssh-rsa signature algorithm is being phased out, but that's not the same thing as RSA keypairs for authentication. This page has a good explanation of what's going on: https://levelup.gitconnected.com/demystifying-ssh-rsa-in-openssh-deprecation-notice-22feb1b52acd https://levelup.gitconnected.com/demystifying-ssh-rsa-in-ope... It's unfortunate that there's a signature algorithm and a key format with the same name, because that definitely leads to confusion in cases like this. But RSA keypairs are fine for now.
- nickjj 4y ago
  > It's unfortunate that there's a signature algorithm and a key format with the same name, because that definitely leads to confusion in cases like this. Thanks for the clarification, but from the end user's perspective it's all the same in the end? It translates to "I have an SSH keypair that was generated using RSA as the algorithm and I was able to SSH into my servers when using OpenSSH vX.X.X and now after updating OpenSSH to a newer version I can no longer SSH into the same servers.". In the end it used to work and now it doesn't and the solution is to pick a different algorithm such as Ed25519 or re-configure your OpenSSH client to continue allowing RSA even though the creators of OpenSSH have deprecated it by default.
  - ryukafalz 4y ago
    It's not quite the same in the end from the end user's perspective, no. If you were logging into servers running a recent-ish version of OpenSSH (i.e. newer than 2016), you would continue to be able to log in with your RSA keypairs with no changes, because the client and server would still be able to negotiate a signature algorithm that both support. It just so happens that very old versions of OpenSSH don't support any of the signature algorithms used with RSA keys that new clients prefer to use. In other words: > or re-configure your OpenSSH client to continue allowing RSA even though the creators of OpenSSH have deprecated it by default ^ this is not correct. RSA is not deprecated by default. A specific signature algorithm used with RSA keys is deprecated. But yes, if your server is running a very old version of OpenSSH, that may be the only signature algorithm it supports. I'm not sure there are any distro releases running versions of OpenSSH this old that aren't EOL though, so really you should probably update your servers, which would also take care of this. (I suppose if you're running CentOS 7 or RHEL 7 you still get security updates for the next 1.5 years at least, but it's no longer actively supported.)

contravariant 4y ago

You'll want Euler's theorem (one of the many) for RSA, it won't be much use to have a prime number as a key since it's not exactly hard to guess its factorisation. That moves your date by a hundred years, into the later half of the 18th century. So not exactly thousands of years back.

ausudhz 4y ago
Chinese reminder theorem is from 300 CE. 1700 years ago. That's actively used in some libraries to validate the key (as stated in the link) Euler just proved what Fermat theorized.
- contravariant 4y ago
  Euler was also the one to generalise the result to non-prime integers. He could have used the Chinese remainder theorem to do so but the first know use of it by western mathematicians was due to Gauss in 1801. To be fair mathematics was really close for a really long time, but before that generalisation not all of the ingredients were there at the same place at the same time. It might well have been possible for the Chinese or Hindu-Arabic mathematicians to discover Fermat's theorem or perhaps even Lagrange's theorem (which is how I'd prove it from scratch if necessary), but as far as I can tell they did not.

aflag 4y ago

To be fair, most of popular and important algorithms and tools in our daily lives are likely even older than that. Arithmetic takes you a very long way. RSA is quite mathematically sophisticated (and recent) next to most of the algorithms we use. Also, look around your kitchen and you'll see a lot of tools that haven't changed much in millenia.

deleted 4y ago

[deleted]