Is there any probabilistic version of RSA? I have now studying the RSA, but I think that is it possible to have some

probabilistic version like a random bit string "r" XORed with the key?

Is there any probabilistic version of RSA?

Thak you so much
Using randomization on the RSA key before encryption doesn't work as easy as a simple XOR: the key (or actually, key pair) has some complicated mathematical structure, and the public part of it (the modulus and the public exponent) need to be known by the encrypting party. 

What might be possible would be to randomly chose the encryption exponent, and transmit it with the ciphertext. The receiver, knowing the factorization of the modulus, can then calculate a fitting decryption exponent and do the decryption.


Alice chooses randomly big primes $p$ and $q$ , calculates $n = p · q$, and publishes $n$ (but not $p$ nor $q$). (Alice might also calculate and store $\varphi(n) = (p-1)·(q-1)$.)
Bob gets to know $n$, and has a message $m$.
Bob chooses a random $e$, and calculates $c = m^e \bmod n$.
Bob sends $e$ and $c$ to Alice.
Alice calculates $d$ from $e$ and $\varphi(n)$ with $d · e \equiv 1 \pmod n$, e.g. using the extended euclidean algorithm.
Alice calculates $m = c^d \bmod n$.


I'm not sure if this would work quite reliably: with normal RSA a condition on $e$ is $\gcd(e, \varphi(n)) = 1$, which is easy to ensure knowing $\varphi(n)$, but less easy if it is not known. (But at least we know we need to choose an odd $e$, as $\varphi(n)$ is even.) I guess if we restrict $p$ and $q$ to safe primes ($p = 2x+1$, $q = 2y+1$ with $x$, $y$ also prime), $\varphi(n) = 2·2·x·y$, and other than multiples of $x$ and $y$ all odd numbers work for $e$.

The actual public key would then be just the modulus $n$, and the private key would be the factorization $n = p · q$.

This RSA-like cryptosystem (I wouldn't name it RSA) would likely be quite a bit slower on encryption (as you can't use a usual "small" exponent like 3 or 65537), as well as on decryption (since you first need to derive your decryption exponent, instead of using the same as always), without really offering much advantages.



The common way to make RSA encryption non-deterministic (which is needed for some formal security properties) is to use a random padding for the plaintext before encrypting it.

So the actual encryption is
$$ c = \textsf{pad}(m)^e \bmod n,$$
and the encryption is
$$ m = \textsf{unpad}(c^d \bmod n),$$
with a probabilistic padding function $\textsf{pad}$, and its (deterministic) inverse $\textsf{unpad}$.

This padding function can be something simple as prefixing the plaintext with some random bytes, or doing this followed by some (reversible) shuffling function, so all plaintext bits are affected.



In practice RSA is usually not used to encrypt a plaintext directly, but encrypts a randomly generated key for a symmetric cipher, which is then used to encrypt the actual plaintext.

In that case, you don't really need a randomization, as the plaintext is already random by itself.