# How can a system be non-deterministic?

Newbie here, so forgive me if this is a stupid question. In math class we learned about RSA encryption (as a practical application of what we learned about the Euler phi function and Fermats little theorem), and I wondered that since the same input always yields the same output, if eve had a couple of guesses for what the message is (for instance a yes or a no), she could try encoding them herself and compare that to the ciphertext. I googled how to get around this, and I gathered that a process can be non-deterministic, meaning it yields different results if done repeatedly. However, when I looked into how this was possible, I never really understood the explanations, they got really complicated really fast.

So what I'm asking is, can anyone explain fairly simply (high-school level math) how a ciphertext can be generated with an element of randomness, but still be decipherable. Surely the receiver can't easily undo those random changes, if the same message could come in in many different forms?

• Your non deterministic (random) part is like rolling a dice, your deterministic part is like following a set of instructions that the sender, receiver and evesdropper has. In RSA the dice rolling is for picking your P and Q. – daniel Jul 20 '17 at 19:06
• @daniel: 'In RSA the dice rolling is for picking your P and Q'; no, it is not; that's generating the random key. What Justin is asking is 'given that you have selected a key, how do nondetermanistic encryption work?' – poncho Jul 20 '17 at 19:10
• @poncho you can read the code here, its a pretty expensive implementation in terms of how many dice you have to roll, as primes are not really common en.wikipedia.org/wiki/RSA_(cryptosystem)#Code – daniel Jul 20 '17 at 19:19
• You're still not understanding the OP's question, which is how RSA encryption (given a fixed P and Q) can be randomized. Randomly-generated Ps and Qs will still yield a deterministic encryption scheme if the encryption algorithm itself is not randomized. – pg1989 Jul 21 '17 at 0:46
• @daniel A cryptosystems consists of multiple algorithms, usually called KeyGen, Encrypt and Decrypt. The question was about nondeterminism in the encrypt algorithm. And that's not given in textbook-RSA. Of course a deterministic KeyGen algorithm would not make any sense at all. – tylo Jul 21 '17 at 10:38

As a high level concept, nondetermistic encryption is where the encryption function takes three inputs, the key $k$, the plaintext $P$ and a random value $R$, generating a ciphertext $C = E_k(P, R)$; the idea is that a) two different random values $R$ gives completely different ciphertexts $C$, even if the plaintexts where the same (or related), and b) no matter what value $R$ we picked, decryption still works, that is, $P = D_k( C )$ (where, in an assymetric system, $k$ may be the private key).

All this should have been covered in your math class; your question is "how does this work in practice?" Since you mentioned RSA, I'll give you a simple version of it:

RSA has a relatively large plaintext size; for example, 2048 bits. So, to encrypt a 256 bit plaintext $P_{256}$, what we do is select 1784 random bits $R_{1784}$, and generate an RSA block:

$$01 || R_{1784} || P_{256}$$

The initial byte is a fixed 01 value (so that the resulting plaintext will always be less than the modulus size); the resulting block is precisely 2048 bits long. We can then give it to RSA, which converts it into a ciphertext.

$$(01 || R_{1784} || P_{256})^e \bmod N$$

We can see that:

• Depending on what values we select for $R_{1784}$, the resulting ciphertext will look completely different

• The decryptor can easily recover the original plaintext (by decrypting the ciphertext, and just looking at the last 256 bits).

Now, it turns out simple RSA padding schemes like this tend to have issues with chosen ciphertext attacks, and so in practice, we generally use more sophisticated ways of padding the message (that is, don't use the simple scheme I mentioned directly). However, it should clarify how deterministic encryption can work in general.

• How is using R1784 different to any varied IV or a simple randomly concatenated plain text part of chained block encryption like AES-CBC (without an explicit IV)? Is there a subtle distinction? – Paul Uszak Jul 20 '17 at 20:47
• @PaulUszak: no, there is no fundamental difference. I used this example as Justin mentioned RSA, so I wanted to give an example in that context. – poncho Jul 20 '17 at 20:53
• Thanks for the super simple explanation, I can see how you can generate a decryptable yet randomized ciphertext now. I was trying to think of a mathematical function that introduced randomness, I didn't think to pad the plaintext. – Justin Sanders Jul 20 '17 at 23:05
• There is no mathematical function that "introduces" randomness. Math is deterministic. There are however physical processes that can generate randomness (at least that's how we perceive them). After that we can use various deterministic functions to extract the and expand the data containing the randomness. That randomness might as well be used to pad the plaintext, it certainly doesn't make sense to use the randomness for a irreversible function on the plaintext message. – Maarten Bodewes Jul 20 '17 at 23:11
• @JustinSanders An alternative to randomly padding the plain text, and introducing a form of randomness is a random IV /nonce. upload.wikimedia.org/wikipedia/commons/thumb/2/2a/… is an old chestnut but perfectly shows the random IV's role. – Paul Uszak Jul 21 '17 at 0:17

The other answers might be skipping a useful step for beginners, non-deterministic encryption is named Probabilistic encryption, which is opposed to deterministic encryption which always produces the same ciphertext for a given plaintext and key.

So your deterministic part of a system always does the same thing, and will always give the same output for a certain input, all computer programs are deterministic. To get random values we need to go outside of a computer program and sample some random event(rolling dice, listen to static), for this we use a hardware random number generator. I hold by my comments that creating P and Q is a non-deterministic part of a system (but so is ethernet), but an example of non-deterministic encryption is OAEP.

I'll assume that you have already picked your private key $d$ along with your public key $d,n$ and that you know the basics of RSA.
My answer now consists of two parts: The first part describes a very elegant randomized encryption that is as strong as the RSA problem, but requires certain cryptographic helper functions. The second part out-lines a standard variant of RSA that is secure against the chosen-plaintext attacks you found, but not against stronger types of attacks.
Before I leave my introduction, what you have found is the IND-CPA security notion for cryptosystems, the link contains a nice description of this game-based security notion.

The first scheme is commonly referred to as RSA-KEM, which stands for RSA Key Encapsulation Method. It goes as follows for encryption:

• Pick a random integer $r$ smaller than your modulus.
• Encrypt this integer using RSA and call the result $c_1:=r^e\bmod n$.
• Run $r$ through a hash function $H$ (ie a function that takes an arbitrary length input and outputs a fixed-length result)1 and call the result $k:=H(r)$.
• Take your message $m$ and $k$ and apply a standard, symmetric encryption method to $m$ using $k$ as the key, call the result $c_2$.
• Return the pair $(c_1,c_2)$

Decryption is now straight-forward: You recover $r$ from $c_1$ using RSA decryption, you derive $k$ again and you apply the decryption function on $c_2$ using $k$.

Now for the (in-)famous RSA-PKCS1v1.5 randomized encryption method (which is the standardized version of the scheme poncho described in his answer). Let your message be $m$ of length $l_m$ bytes and your modulus $n$ be of length $l_n$ bytes. Encryption now goes as follows:

Take your message. On the left, that is on the side of the bytes with more significance, add a zero-byte, a byte with value 2, as many random non-zero bytes as fit ($l_n-l_m-3$) and another zero-byte right before your message starts. Encrypt the result with standard RSA.

Upon decryption, you run the input through your decryption function, check that the second most-significant byte is indeed 2 and search for the zero-byte the next zero byte to the right. You simply output everything to the right of this zero-byte.

1: Additionally with that, we also demand that the input cannot be recovered faster than by trial-and-error from the output and that we cannot easily find two inputs that map to the same output.