# Decryption of a file encrypted by pseudo-random number generator (The Linear Congruence rand()

How to decrypt this file:

Given that the only information available about it are:

1. It has been created ‎on 21/3/‎2018, ‏‎9:05:15 AM
2. The plaintext of the file is probably starting with "\documentclass[12pt]{article}", and it's a latex file
3. The code used for encryption is in C, and used a pseudo-random number generator (The Linear Congruence rand()):
/* The ISO/IEC 9899:1990 edition of the C standard */
#define RAND_MAX 32767
static unsigned long int next = 1;
int rand(void) // RAND_MAX assumed to be 32767
{
next = next * 1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
void srand(unsigned int seed)
{
next = seed;
}

#include <stdio.h>
#include <time.h>

//Return a byte at a time of the rand() keystream
char randchar() {
static int key;
static int i = 0;

i = i % 4;
if (i == 0) key = rand();
return ((char *)(&key))[i++];
}

int main(int argc, const char* argv[]) {
static char randstate[64];

srand(time(NULL));
FILE *input, *output;
input = fopen("Homework1b.tex", "r");
output = fopen("Homework1b.tex.enc", "w");

int c,rc;
while ((c = fgetc(input)) != EOF) {
rc=randchar();
printf("c=%d (%c) and rc=%d\n",c,c,rc);
fputc(c^rc,output);
}
fclose(input);
fclose(output);
}


I read about the weakness of C random and I know that knowing a part of the plaintext should help, but couldn't figure it out.

• If you know the exact time the fie was encrypted, you know the seed and can reconstruct the keystream. Mar 25 '18 at 0:27
• I have a time range actually and narrowed the possibilities down based on the known plaintext I have. However, I couldn’t do the “reconstruct” part, due to the lake of my knowledge in the reverse engineering and long time of no coding. If some could give me general idea of the concept that would be great. Mar 25 '18 at 18:59

Short answer: Just replace the srand(time(NULL)); with srand(<epoch seconds when encrypted>); and then "encrypt" the encrypted file again to decrypt.

Long answer: The unserlying priciple of this programm is a stream cipher, as you already mentioned in your tags, which means the plaintext $P$ is xored with a random keystream $K$. To undo this operation, you simply need to xor the ciphertext $C$ with the same keystream again, which is proven by $C \oplus K = (P \oplus K) \oplus K = P \oplus 0 = P$.

So to reconstruct the plaintext, we need to reconstruct the keystreams to which can be achieved in two ways:

1. Using the time of encrytion: As you can see in the second line of the main method, the seed of the rand-function is set to the current time in secconds. Since all the following outputs of the rand-function depend on that seed only, one can reconstruct the keystream by setting the seed to the seconds since the unix epoch.
2. Using a known plaintext: Let's take a look at how the keystream is generated: $K_{i+1}=(1103515245 \cdot K_i + 12345)\ /\ 65536\ (mod\ 32768)$ This may look complicated at first, but there is one simple property which can easily be exploited: The next state only relies on the previous state. This allows us to compute all the following states using only one state. To get this, we simply xor the ciphertext with the plaintext since $K_0 = C_0 \oplus P_0$ and use it as seed for $K_1$. You can then go on and use the rand-function to get the keystream.

Finally, you need to know the endianness of the encrypting source, so that your decrypting program can match and correctly decrypt.

• Thank you that was helpful, could you further explain the second part? I understand the concept but couldn’t put it in code. Mar 24 '18 at 21:02
• You have to load the first 4 bytes from the file and xor them with the known plaintext to recieve $K_0$ which is the "next"-state after the first call of the rand-function. You can then call the srand-function with $K_0$ and then go on and decrypt the rest of the data. Mar 24 '18 at 21:26
• What does “endianness” mean? Still when I use the xor of the 8 byte plaintext/ciphertext combination as a seed I get wrong output. Mar 31 '18 at 23:08