Since we’re all thoroughly stumped, let’s have a discussion about public-key cryptography.
Lately, we have been obsessed with symmetric encryption methods, primarily DES, Rijndael, AES and the like. This is fine. However, Storm mentioned during the interview posted online that he was worried about gents from Cambridge being involved, and he therefore upped the ante in terms of the difficulty of the ARG. With that in mind, I think it’s safe to assume that we may be looking at a problem that involves some intricate sleuthing.
Although the Hex Code could very well be the result of a symmetric cipher, I think it’s reasonable to assume that the key itself may actually be encrypted via asymmetric encryption (public-key cryptography). Referring back to the BENALOHPAILLIER hint, both of these encryption methods utilize asymmetrical algorithms—therefore, this could indicate that one (or both) of these methods is used directly, but it may also simply be a hint that public-key cryptography is used in determination of the private key utilized in a symmetric cipher. In other words, the Hex Code may be encrypted with a symmetric method, but the key itself is derived from an asymmetrical method.
Before getting further into the asymmetric key theory, I also want to note that the high entropy of the Hex Code could indicate a number of things and it’s wise to have a more thorough understanding of which of these is most likely.
First and foremost, a random number generator could have been utilized in the creation of the key, although I find that extremely unlikely—considering it would make the problem practically impossible to solve. A second consideration is that random data was added to the plaintext to supplement entropy, although this seems a bit too gimmicky for someone with Storm’s prowess. A third option, and the one I find most likely, is that an initialization vector was utilized, most likely through cipher-block chaining (CBC). In essence, this means that a value of equal size to that of the first block is used to XOR the first block of plaintext, at which point it is encrypted. The resulting ciphertext of that block is then used as the IV of the next block, so on and so forth. This, in turn, creates high entropy—in practical use, this could also be implemented instead of a random number generator to help prevent the occurrence of low randomness in the generated numbers.
Now, usually the IV is a random or pseudorandom number, but I think it’s safe to assume that, if an IV is used here, we likely have it hidden within one of our messages. If this is the case, we actually need 3 parts: 1.) the ciphertext; 2.) the Initialization vector; and 3.) the key utilized to encrypt.
With that in mind, let’s explore further the theory that the key is encrypted utilizing an asymmetrical method:
(For a list of steps, see this page under the “A worked example” heading.)
Our key could not be a word at all, but a number or encrypted alphabetical plaintext key—and one that is created using an asymmetrical method. I’ll do my best to explain this, but no promises are made.
We start with two prime numbers, p and q. These numbers can be very small, or they can be very large. Let’s go with a large example I’m borrowing from a book on cryptography (written by Rudolf Kippenhahn) as, if Storm were attempting to obfuscate the key, it’s possible he would use larger numbers—however, this would make it extremely difficult to crack. Furthermore, we have one such number, 10010851, which is the first half of the Code A-D password implemented on his website.
Let’s assume p = 48,611 and q = 1,009. Next we determine N by multiplying these two prime numbers together: N = 49,048,499.
The next step is to calculate z, which is calculated utilizing the following formula: z = (p – 1)(q – 1). Or, in layman’s terms, we subtract one from both p and q and multiply those results together. In our example, we would multiply 48,610 by 1,008 = 48,998,880. Therefore, we set z equal to 48,998,880. Now that we have z, we can determine our two key numbers E and D.
Now, we have some things to consider when choosing what E will be. In essence, E cannot share a factor with z. The simplest way of ensuring this rule is met is to choose a prime number smaller than z and check if it is contained within z by dividing it into it. In our example, we know that z is even, so 2 will not work for E. We then continue to try prime numbers that are not divisible into z; in this example, our E = 61 as 61 is prime and is also not a factor of 48,998,880.
Now we have N and E, but we still need our private number, D. In terms of public and private, E would be the key we could share with those who want to encrypt messages, but we would reserve D as a private number that only those with decryption access would know.
D is determined by following these parameters: when multiplied by E, it must, when divided by z, leave the remainder of 1. To break this down, we first divide z by E, which results in 48,998,880/61 = 803,260.328. We multiply the whole portion of the number (803,260) by E (61) to get: 48,998,860. When subtracted from z, this leaves us with 20. Now, we take that 20 and divide E by this number (instead of z): 61/20 = 3 with a remainder of 1.
The next step is even trickier, but it makes sense—in essence, we work backwards and rearrange the formula to get an equation by which to solve for D. First, let’s formulate that last step: E = (3 x 20) + 1. Spelled out, that equation simply means that E is equal to 3 times 20 plus the remainder of 1—the 3 and the 20 are the results of the two calculations. Then, we set this equation equal to 1: 1 = E – (3 x 20). Next, we can replace the 20 with (z – 803,260E)—we do this because, in our first equation, we found that the remainder of 20 was a result of subtracting the product of E and 803,260 from z. This leaves us with the equation as follows: 1 = E – (3 (z- 803,260E)). Simplify to: 1 = E – (3z – 2,409,780E), then distribute the negative:1 = E – 3z + 2,409,780E. Lastly, simplify the E’s within the equation:1 = -3z + 2,409,781E.
The magic number before the E is our D. Therefore, D = 2,409,781.
For our needs, it’s possible that our key is either encrypted with the aforementioned method and needs to be decrypted, or we are required to encrypt a provided key (BENALOHPAILLIER, perhaps) and use the result as the actual key in the symmetrical cipher—either in number or plaintext form.
Unfortunately, if such large numbers are actually used, we would require the aid of a computer—or someone with a will of stone and time to spare. Thankfully, these calculators exist online, and we could probably even create a program that takes the combined inputs of p and q, determines N, then encrypts or decrypts utilizing the resulting N. We might also already be provided with the private and public keys (and could therefore also derive N from them), but I see this as being less likely.
Aside from asymmetrical encryption of the key itself, we could also be looking at encryption of the entire Hex Code. If this is the case, we would likely convert the hexadecimal to decimal, then create groups of 4 or 5 numbers—these groups would then be utilized to solve for the numerical plaintext (which would then be converted to letters). To do this, we would take the groupings of numbers and raise each group to the power of the private key. Dividing by N and only keeping the remainder would provide us with the plaintext in numerical form (mod N). Our example likely wouldn’t work very well, as the numbers are simply too big.
However, to borrow again from the book. If we want to encode “its all greek to me” utilizing the following parameters, p = 47, q = 59, N = 2,773, E = 17 and D = 157:
I t s _ a l l _ g r e e k _ t o _ m e _
0920 1900 0112 1200 0718 0505 1100 2015 0013 0500
To encrypt, we raise each block of four numbers by the power of E, then divide by N after each multiplication and keep only the remainder. To do this simply, put it in a calculator as: 0920 ^ 17 (mod 2,773). The result is 0948. Therefore, the first block of ciphertext is 0948.
Conversely, to decrypt we raise each block of ciphertext to the power of D. Therefore, 0948 ^ 157 (mod 2,773) = 0920. We have thus arrived at our plaintext (in numerical form) which we can then convert to letters: IT.
To use this practically in the ARG, our N and corresponding E and D values would need to be pretty small. 10010851 would technically work as our E (or D, if you prefer to set D to the public key value), but the calculators I used for the first example were fried by the exponential calculation of 27,289,139 ^ 2,409,781. Again, it’s not impossible, but it is impractical.
If you didn’t understand any of that, the simple gist is that our Hex Code could use an encryption method based on asymmetric (public-key) cryptography, such as Benaloh or Paillier, or might utilize asymmetric encryption for one of the steps. To be frank, it all simply depends on how deep down the rabbit hole Storm wanted to go.
