I know we've all seen plenty of cryptography used in cache puzzles, but it struck me that it's only ever classical cryptosystems. It doesn't even scratch the surface of what modern cryptography has to offer! So now I'm offering you some more complex cryptosystems, many of which are still in use in computing today (and some of which are still just theoretical potential others!). By the way, I’d recommend taking notes on what you do to solve these; it might help for the final.
The classical cryptosystems that we are used to seeing are known as "symmetric cryptosystems"; that means that if you can encrypt something, you must also be able to decrypt it. Instead I'll be going through some "asymmetric cryptosystems," which means even if you can encrypt something, you don't necessarily know how to decrypt it. This is done by providing a "public key," which anyone can see, and which is used to encrypt messages. However, to decrypt, the message recipient must use a "private key," which is related mathematically to the public key but which only the recipient knows.
The usual analogy that people give is like a mailbox, as in the big blue ones in public places. Anyone has access to the mail slot (the "public key") so anyone can put a letter into the box ("encrypting the message"). However, only one person—in this case the postal workers—has the physical key (the "private key") that opens the mailbox, so only they have access to the letters inside ("decrypting the message").
The public key and private key are connected through some sort of mathematical relation that is considered "very hard to solve," as in the private key cannot be derived from the public key in a reasonable amount of time. For example, finding the prime factors of a number is considered a "very hard problem," in that if the numbers are sufficiently large, then no computer has the computing power to be able to calculate it within, say, thousands of years. A common way of creating the keys is based on this—two extremely large prime numbers are taken as the private key, and their product is the public key. Multiplication is a trivial matter, so forming the public key is extremely easy, but figuring out the private key from the public key is near impossible since factorization takes so long. Keys formed in this way are therefore considered very secure and are still in use in several encryption systems used today. Discrete logaritms and elliptic curves are also used in creating keys, among other things.
Of course, since I'm going to have you break some of these cryptosystems, we will not be using numbers so large that a computer cannot perform the calculations. They will still be very large, and I would very much advise against doing calculations by hand, but there are definitely tools that can do these calculations very quickly. In fact, I was able to find tools exclusively online which could do all of these! (hint hint: find the alternative name for element #74 and use that for most of the calculations. They had good tools for everything but the CRT stuff, but there were other websites that could handle that well.) To solve the puzzle, you will need to figure out which cryptosystem I am using (and I'll give a good hint for it), then figure out how to get the private key from the public key (probably with a computer calculation), then read up in detail on the cryptosystem to figure out how to decode it, and then use a computer to perform all the computations that will decode it. I imagine this taking a LOT of research and working through things very slowly to understand the concepts needed to solve. It's probably much harder than a 4, but I'm leaving it at that since it will get harder later in the series. But I'm happy to provide any help along the way or to offer a detailed explanation of the mathematical concepts behind it—just send me a message if you need it! Also, since these numbers can be tedious to work with, I'm happy to check computations at any time (including before FTF).
By the way, because of the way many asymmetric cryptosystems are set up, decryption might result in several possible plaintexts. To get around this, a message sender may pad the beginning with a certain sequence of characters, and share this sequence with the recipient so that it is clear which one is the true message. In our case, this will not be necessary because which one you will need will be very obvious.
Also, I've included a short message at the end of the plaintext; I will tell you right now that if you want to read it, just separate that portion into blocks of three numbers and convert from decimal to ASCII. It's not necessary, though, and it doesn't provide any new information.
So without further ado, here's the actual puzzle portion!
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Public Key: 1829009020402873293586532135011620390583697
Ciphertext: 30443687459657418239674449728124595692513
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Notes on the difficulty rating: the overall puzzle will probably be between a 4.5 and a 5 depending on your experience. Compared to future puzzles in this series, it is probably around a 3 or 4 (but keep in mind every puzzle will be hard based on the background needed). The hide itself is probably somewhere between a 3 and a 3.5. When you find it, be sure to lift UP. And please don’t remove it from what it’s held onto; it may be hard to just remove the lid but I don’t want to risk it going missing. $1 for FTF.
Check Certitude for a hide hint.
You can validate your puzzle solution with certitude.
Congrats to KK2005 on the FTF!!!!!
Puzzles in this series:
Asymmetric #1
Asymmetric #2
Asymmetric #3
Asymmetric #4