Hacker News Reader

Comment by ausudhz | Hacker News Reader

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

View on HN

> 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-F...

An interview with Cocks and Ralph Benjamin: https://www.zdnet.com/article/gchq-pioneers-on-birth-of-publ...

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.

RSA on pen and paper isn’t that bad compared to some other calculations people used to do by hand. By comparison in 1800 multiple people had already calculated the first 100 digits of pie. https://en.wikipedia.org/wiki/Chronology_of_computation_of_π

People can get shockingly good at that kind of thing with enough practice.

Well book ciphers go some ways back and they are almost OTP (in the sense of how they are performed, not in the sense of security properties). It may have been prohibitively expensive to print a custom pad used for encryption.

A one-time pad seems totally feasible to me without a computer, and sufficient motivation. RSA does not. They're different algorithms of course! OTP is a very simple one, as you point out.

Expensive but spy agencies did it.

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.

> The reason why was not is because, prior to computer, there was not a problem of "sharing" the key

Lol. There is a new dude sitting in a castle one sea over. You want to communicate with them. Let’s say you want to agree to attack a third neighbour at the same time. If your message gets intercepted you will be in trouble.

How do you share your secret keys with them? Mind you, you don’t really trust any of your man, and the sea route is treacherous so you don’t fancy risking going in person.

Sharing keys is a problem old as time.

That's the point. Still though is very old is not a 19th century problem. Yet RSA was used 400 years after the theory behind

Why didn't people came up with a manual "RSA" before. Since the math is 400 years old.

I recommend you try to do it -- it's a fun exercise, and will very quickly answer any remaining doubt why it can't be done manually.

We actually did that in university; the public key we used was something like 91 (not hard to factor). Wikipedia has an example with 3233, and that's already very cumbersome: https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Example

I tried generating an Ethereum address by hand starting by creating a random private key. It quickly got away from me.

I wish there was some way to simplify the math to allow doing it by hand. It would be a nice way to check for correctness while computing it offline, and while ensuring dependencies hadn't been compromised to produce a fake public address.

I feel like making your own circuits that could do this would be a more feasible approach. Or at least a circuit that uses small purpose build ICs that are easy to verify.

I did that in university before you born

It can be done manually easily

Ceasar’s cipher is neither complex nor an OTP. What are you talking about?

What are you talking about. That was the first cipher.

RSA is OTP?

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.

Is not complex at all, if you can't multiply two prime number and do subtraction probably you should reconsider your skills.

If people were able to do that in 15th century by hand I don't see how who really needs it couldn't.

Is just the needs were different, but is not complicated

Otp

> 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.

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.

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.

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.

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.

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.

> 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.

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.

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.

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...

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-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.

> 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.

> Thanks for the clarification, but from the end user's perspective it's all the same in the end?

The vast majority of users will not experience this unless their client is old. I literally dealt with this issue yesterday with one of our lead Developers.

He was using JSch in an older version of dbeaver, couldn't SSH into the new test environments we're validating on Ubuntu 22.04. Turns out to be this exact issue. The solution was to update dbeaver and switch to the new default SSHJ client within it.

Same private key, new client. Problem solved.

I will be using this as leverage to force a company standard change from RSA4096 keys to ed25519. So I am not going to clarify the difference to the Security teams.

RSA keys aren’t deprecated (apart from those with shorter key lengths, e.g. 1024 bits). What’s deprecated is the use of SHA-1, and in consequence the signature algorithms that combine SHA-1 with RSA. Instead you have to use signature algorithms that combine other hash algorithms (like SHA-2) with RSA. RSA itself, and RSA keys, remain unaffected.

Another thing that may get deprecated in the coming years is RSA 1.5 padding, requiring to use PSS padding instead. Again, that doesn’t impact RSA keys, but only the algorithm parameters used with RSA.

In the context of TLS/SSH, it just means that client and server have to negotiate the RSA-based algorithm variant they both support and both deem to be safe, using the existing RSA keys.

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.)

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

Reply on news.ycombinator.com