Let $N$ be a large number; and $(e, d, N)$ be a secret-key; where $e$ is a one-time random factor, and large enough (say the more or less the same number of bits as $N$), where $e < N$ and $e * d \equiv 1\pmod N$

Encryption of a plaintext $m$, where $m < N$, is as follows:

$ c = m * e \bmod N$

Decryption of a ciphertext $c$ is as follows:

$m = c * d \bmod N$

How can we prove, if the above defined cipher is secure (or not) under the following conditions?

  1. Message $m$ is randomly padded to $m_p$ before encrypting, where $m_p < N$, matching the bitlength of $N$
  2. $N$ can be re-used
  3. The secret (and random) factors $(e, d)$ are used only once (once per encryption, session, message etc...)

Note: I'm asking this because, optimizations on this cipher can have a direct use on the protocol defined in the question: Random Masking of Padded RSA Ciphertext through homomorphism

Additional question: Does the choice of $e$ and $N$ affect the security of this cipher?

  • 1
    $\begingroup$ How do you send the padder? $\endgroup$ – kelalaka Oct 4 '18 at 5:46
  • $\begingroup$ @kelalaka I assume the padding is similar/identical to an RSA padding. $\endgroup$ – zetaprime Oct 4 '18 at 7:07

The question uses the term "cipher" in a non-standard way: in cryptography, a cipher's key is usable for multiple messages, and that's explicitly not the case here. We'll extend the term cipher to something with the restriction that components of the key (here, $e$ and $d$) are used for a single message. We'll assume a supply of distinct random secret one-time key components $e$ and $d$ known to encrypting and decrypting parties.

It is asked if the "cipher is secure (or not)". The most standard modern definition of security of a cipher is indistinguishability under Chosen Plaintext Attack. That defines an experiment where an adversary chooses two plaintexts, gets them encrypted, and tries to match ciphertext and message (we'll ignore that this experiment normally uses ciphertexts obtained under the same key).

In this section, we assume there is no random padding (that is, $m_p$ is defined as $m$).

The cipher as stated is not secure per the modified CPA definition: an adversary can submit $m=0$ and $m'=1$, and can recognize the ciphertext $c$ for $m$ from the ciphertext $c'$ for $m'$, because $c=0$ and $c'\ne0$.

The additional restriction $0<m<N$ is not enough for security: if the adversary knows a divisor $d$ of $N$ with $1<d<N$, then the adversary can submit $m=d$ and $m'=1$ and can recognize the ciphertext $c$ for $m$ from the ciphertext $c'$ for $m'$, because $c\bmod d=0$ and $c'\bmod d\ne0$.

However, if the condition $\gcd(m,N)=1$ is imposed to adversaries, and if $e$ is chosen uniformly at random among the subset $\Bbb Z_N^*$ of integers in $[0,N)$ such that $\gcd(e,N)=1$ (this later condition is equivalent to existence of $d$), then demonstrably the cipher leaks no information about $m$ and is CPA-secure. Proof sketch: for fixed $m$, the function $e\mapsto c$ is reversible onto the finite set $\Bbb Z_N^*$, hence is a bijection, hence $e$ uniformly random implies $c$ uniformly random, hence $c$ leaks nothing about $m$.

Methods to impose the condition $\gcd(m,N)=1$ to adversaries include requiring $0<m<N$ and making $N$ either a hard-to-factor RSA modulus of factorization unknown to adversaries, or a prime. However neither is possible in the context (note: where $r$ and $r^{-1}$ are the $e$ and $d$ of the present question), since an adversary is the holder of an RSA private key for $N$, which allows to efficiently obtain the factorization of $N$ and implies $N$ is not prime.

Now we introduce padding. The question's encryption and decryption equations become $$\begin{align} c&=m_p*e\bmod N\\ m_p&=c*s\bmod N \end{align}$$ All random paddings used in RSA (including OAEP) make $\gcd(m_p,N)=1$ overwhelmingly likely, including for adversaries knowing the factorization of $N$ and able to chose $m$ before padding. Therefore, with $N$ an RSA modulus, and a secure RSA random padding tailored for this modulus and using a random number generator not under control of adversaries, the cipher is CPA-secure (per our modified definitions of cipher and CPA-secure).

The choice of $N$ has no influence on security, and its factorization needs not be kept secret for the security of the cipher in the question.

If we leave the padding unspecified, security can depend on $e$ being uniformly random in $\Bbb Z_N^*$ (which can be obtained by taking $e$ uniformly random in $[0,N)$ until $\gcd(e,N)=1$, with this later condition overwhelmingly likely when $N$ is an RSA modulus). However, with OAEP padding, it is enough that $e$ is chosen in $\Bbb Z_N^*$ using a method yielding large entropy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.