1
$\begingroup$

Let m be a message of arbitrary size, potentially very large. Is it necessary to use larger parameters in the public-key encryption scheme in order for the receiver to decrypt that message?

My guess is that, in the case of RSA, the size of the message cannot exceed the size of the modulus. I assume this holds for any public-key encryption scheme.

If so, what kind of algorithmic complexity are we talking about: is it linear in the input size (the message), or worse? [I assume it's worse]

EDIT: I don't want to use symmetric-key cryptography.

EDIT 2: You can assume that we possess a secure channel over which we'll send the encrypted message.

Improve this question
$\endgroup$
16
  • $\begingroup$ What you do is, you encrypt a symmetric key and then use that en.wikipedia.org/wiki/Hybrid_cryptosystem $\endgroup$
    – Elias
    Apr 26, 2017 at 8:36
  • $\begingroup$ @Elias: I know about that: this is not what I want. I am solely interested in public-key cryptography in this question. $\endgroup$
    – Symeof
    Apr 26, 2017 at 8:39
  • 1
    $\begingroup$ The complexity is linear (if you would use a block mode) but very very slow. And there are also no good method to get this secure (most methods are sensitive to chosen plaintext, high repetitions (large messages) and so on. I also don't know if there is any approved/researched method because it's so slow that nobody cares) $\endgroup$
    – eckes
    Apr 26, 2017 at 9:46
  • $\begingroup$ For RSA, the main computational load for encryption are the amount of modulo operations in the exponentiation, which can be a small-ish prime (not 3, but 10-20 bits). The major issue thhough, is key generation: Finding a prime with millions of bits would have an impractical runtime. $\endgroup$
    – tylo
    Apr 26, 2017 at 12:32
  • $\begingroup$ How about splitting your message into blocks? $\endgroup$
    – Elias
    Apr 26, 2017 at 13:02

1 Answer 1

Reset to default
3
$\begingroup$

The real problem is not the encryption or even the decryption of an encryption scheme with huge values, it is the generation of the key:

For RSA, ElGamal, Paillier, etc. you need one or more large primes, which make up a modulus for your computations. In practice, you can find large primes by using the Miller-Rabin primality test. It has a run time of $O(t \log^3 n)$, and for large numbers it can be improved to $O(t \log^2 n)$ if using FFT-based multiplication. $t$ notes the number of test runs and you have an error rate of $1/4^k$, where the test says prime for a coposite number. While the runtime with multiplication optimazation has the smaller exponent, the Big-O notation does hide constant factors, and I don't know where the break-even is, but let's just assume the current crypto libraries already use the optimzation.

As a reference in this SO answer generating a $2048$ bit RSA key (which is generating two $1024$ bit primes and a tiny amount of its computation time to find $e$ coprime to $\phi(n)$ and calculating $d$) takes around $1$ sec. So $\approx 0.5s$ for a $1024$ bit prime.

If we want to increase the size by a factor $a$, then the Miller-Rabin test takes $a^2$ times longer. However, we also need to test $a$ times as many numbers on average to find an actual prime number. Example: A random $1000$ bit number is prime roughly with probability $1/ln(2^{1000}) = (\log 2)/ 1000$ and we need on average $1000/(\ln 2)$ tests to find a prime, a random $2000$ bit number is prime with probability $(\log 2)/2000$, and on average we need to test $2000/(\ln 2)$ numbers to find a prime. This means, we expect to run the algorithm on $a$ times as many numbers to find a prime.

For example, for a prime with $1 M$ bits for example and an estimate of $0.5$ sec for a $1024$ bit prime, we have a factor of $~976.5$ in size, so the runtime for Miller-Rabin itself is $0.5 \cdot 976.5^2$, and we need to test $976.5$ as many values, resulting in an overall runtime of $\approx 465 M$ seconds, which is around $14.76$ years.

In case you want to use RSA you need two of these primes, so after 30 years you have a RSA modulus with $2,000,000$ bit, which allows you to encrypt $0.25$ MByte of data in one piece. Of course using a large computing center will speed this up, but the real problem is the size, since I guess you didn't have $0.25$ MB of data in mind when you wrote "potentially very large".

Edit: The encryption and decryption scale much less from the size increase. For RSA, you can still use a small exponent in the encryption, this doesn't have to be much larger than current ones. That means the number of steps in square-and-multiply are roughly the same, just each multiplication and modulo operation takes more time. Decryption then involves a number of length of the modulus, but overall it is still quadratic at worst, and much less than prime generation.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Earlier I tried to find empirically the average time needed to get a prime of size a with Miller-Rabin (for a fixed parameter t of the algorithm) up to a =8K and vaguely remember that (1) the individual values vary enormously, for one could with luck with a few trials hit at a prime, (2) one would need at least 100, if not more, values to obtain a somewhat stable average value, (3) it seems that the average values increase less than a to the 2nd power. (Currently I am doing the analogous task for Maurer's algorithm of provable primes. The result so far obtained seems similar, if I don't err.) $\endgroup$
    – Mok-Kong Shen
    May 2, 2017 at 15:03
  • $\begingroup$ @Mok-KongShen Primes are not evenly spread among the integers, there are arbitrary long intervals in the natural numbers without a single prime. Even the formula $1/ \ln(n)$ is just an approximation for the average density based on the prime number theorem. Regarding the asymptotic runtime of Miller-Rabin, the big-O notation disregards smaller factors, and maybe at that specific length the growth is not quadratic. But when considering arbitrary long numbers, we have to look at the asymptotic behavior. $\endgroup$
    – tylo
    May 2, 2017 at 15:27
  • $\begingroup$ Regarding primes which are constructed instead of randomly-chosen-and-tested: Those might be unsuitable for RSA, because you effectively do not draw from a uniform distribution over all primes of apprpriate length. E.g. using Mersenne primes would be completely insecure, or any publicly available list of large primes for that matter. For DLOG-based cryptosystems they would work - if their totient has at least one large prime factor. $\endgroup$
    – tylo
    May 2, 2017 at 15:33
  • $\begingroup$ Sorry, I am probably highly confused in connection with the big-O notation. But isn't it that, if, say, f(x) is O(n^3), where n is size of x, this says f(x) will ultimately be less than n^3 (and not the other way round) as n becomes very big? (If yes, your time estimate would only be an upper bound and not a lower bound, if I don't err.) $\endgroup$
    – Mok-Kong Shen
    May 22, 2017 at 8:41
  • $\begingroup$ Regarding the first question: Big-O notation $O(n^3)$ means for all $n$ greater than some $n_0$ it is true that $f(n)< c n^3$ for some constant $c$. So yes, it is an upper bound for the asymptotic complexity, and it is not a lower bound. But stating $\Theta(n^3)$ might not be true - unless you can actually prove that there is another constant $c'$, s.t. $f(n)> c' n^3$ (again: for large $n$ greater than some threshold). Often a lower bound for a probabilistic algorithm can not be given or is not meaningful. In this case $O(n^3)$ actually means: "for most cases it has this complexity" $\endgroup$
    – tylo
    May 22, 2017 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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