4
$\begingroup$

I am doing a paper on textbook RSA (highschool-level). I am explaining and proving the significance of the public key exponent in time and security. So far, I have encrypted a constant message with a constant modulus but using different public exponents. The calculation time has been annotated using Mathematica.

I want to determine a lower and an upper bound for a range of public key exponents. I want to do this from a security perspective and a time perspective.

Here are my three questions:

  1. Can I use the BigOh function? Would they respectively serve as the lower and upper bound? I can use BigOh for time, to show what the absolute worst time for encryption. Is there a time function that is related to the public key exponent?
  2. Is there a general 'upper bound' for time i.e. is there a maximum time value that no calculation should surpass?
  3. How would I determine a range of suitable numbers alternatively and upper bound in terms of security?

Thanks.

$\endgroup$
  • $\begingroup$ I believe that this doc. may help you to understand public and symmetric keys in detail. ietf.org/rfc/rfc3766.txt Furthermore, for estimating the lower and upper bounds, read this doc. eprint.iacr.org/2012/666.pdf. It will be very helpful! $\endgroup$ – user24094 Nov 6 '15 at 14:46
  • $\begingroup$ Thank you, these resources are fantastic! However, my paper focuses on the public key exponent so I am unsure if the latter link can help me.. $\endgroup$ – user9750060 Nov 7 '15 at 23:40
8
$\begingroup$

Yes you can use Big-O notation to express runtime, that's customary. Formally, that does not give an upper bound on runtime for any fixed parameters, much less a lower bound; formally, that gives you an indication of how an upper bound would behave when some parameter grows to infinity, and no practical indication. However, in practice, when dealing with runtime of algorithms, you can use Big-O notation and timing measurements for realistic parameters to extrapolate an evaluation of run time for other realistic parameters. If run time is $\mathcal O(f(s))$ for some function $f(s)=s^2$, and the run time is $t_0=1.2\text{ second}$ for parameter $s_0=1000$, then run time $t_1$ for parameter $s_1=1500$ can be evaluated as $t_1={f(s_1)\over f(s_0)}t_0={1500^2\over 1000^2}1.2=2.7\text{ second}$. This is not mathematically justified by a definition of Big-O notation, and can fail for many practical reasons (including the run time increasing by steps as a function of parameters; cache effects..) but in the context of the question, it will work reasonably well.

With $(N,e)$ an RSA public key, the time to compute $x\to y=x^e\bmod N$ (as performed in RSA encryption, or signature verification), changes as a function of $e$ that is $\mathcal O(\log(e))$, assuming $N$ of unknown factorization; that is, time grows no faster as a function of $e$ than the number of digits in $e$ (Caution: this does not tell how it varies with $N$). More precisely, time to compute $x^e\bmod N$ grows proportionally to the number of bits necessary to write $e$ (within a factor less than 2 in RSA practice), for constant $N$, and arbitrary $x$. That follows from analysis of good modular exponentiation algorithms.

As far as we know, the security of RSA does not change when the public exponent $e$ increases, assuming the message is randomly padded, as it should be. When the message is not randomly padded, RSA encryption can be insecure, regardless of exponent.

To illustrate that later point: for any public key $(N,e)$, assume that one enciphers the name of a person in the class simply by transforming the bits in the computer representation of that name into a number $x$ (using binary convention), computes $y=x^e\bmod N$, and makes $y$ known. An attacker with the name of all persons in the class can do the same computation for each name, and when the result matches the $y$ , the message is effectively deciphered.

Random padding prevents this attack. In its simplest form, it appends secret random bits (as obtained by coin toss) to the name enciphered, up to nearly the bit size of $N$, such that $x$ is unpredictable to attackers. If we add enough random bits, and holders of the private key are careful leaking no information during decryption, $e=3$ is fine. If we use better encryption padding, like OAEP, the potential for goof by private key holders is reduced, and we have constructive mathematical security arguments (although no proof that breaking encryption is as hard as factorization, or that the size of $e$ matters or not to the security).

The size of $N$ has a paramount influence on the computation time: for commonly used algorithms it is about $\mathcal O(\log(N)^2)$ for $x\to y=x^e\bmod N$ as used in encryption and signature verification (justification: this computation reduces to some number, fully determined by $e$, of multiplications and Euclidian divisions on integers of size proportional to the size of $N$; the methods learned in school for these two operations require a number of uses of the multiplication table growing with the square of the number of digits in the arguments). Computation time goes $\mathcal O(\log(N)^3)$ for $y\to x=y^d\bmod N$ as used for decryption and signature computation (the extra factor $O(\log(N))$ is because the exponent is of size growing with the size of $N$). It is possible to do slightly better for large $N$, using sub-quadratic multiplication, but that is seldom used in normal practice.

For proper use of RSA, the best known attack is to factor the public modulus $N$. For properly setup $N$, the best known method for this is GNFS. It is believed that currently, only organizations with resources comparable to government agencies could do this for $N$ of 1024-bit; that 2048-bit is currently safe; and that 4096-bit (or just 3072-bit) is safe for very long term use. See this for an historical perspective, and this for size recommendations.


Illustration: we use code that computes $x^e\bmod N$ using right-to-left binary scanning of the exponent, thus with execution time $\mathcal O(\log(e))$; and performs modular multiplication by multiplying, then reducing, using schoolbook methods, thus with execution time $\mathcal O(\log(N)^2)$. We measure that with $e=257$ and 1024-bit $N$ the encryption computation takes $t_0\approx0.1s$. We want to extrapolate the time taken

  1. if we used $e=65537$;
  2. if we used 2048-bit $N$ and the original $e=257$.

Solution:

  1. When changing $e$ form $257$ to $65537$, given that time is $\mathcal O(\log(e))$, a rough estimate is that the time becomes $t_1={\log(65537)\over\log(257)}t_0\approx2t_0=0.2s$. Note: we can use logarithm in any base, base 2 allows to perform the calculation more easily, since $\log_2(65537)\approx16$, and $\log_2(257)\approx8$.
  2. When changing $N$ from a 1024-bit value $N_0$ to a 2048-bit value $N_2$, given that time is $\mathcal O(\log(N)^2)$, a rough estimate is that the time becomes $t_2={\log(N_2)^2\over\log(N_0)^2}t_0=\left({\log_2(N_2)\over\log_2(N_0)}\right)^2t_0\approx\left({2048\over1024}\right)^2t_0=0.4s$

If we know the exact algorithm used, we might be able to directly determine the effect of some parameter on its runtime, and be more confident with the approximation. For example, for $e=2^k+1$, the simplest modular exponentiation algorithm raises to the $e^\text{th}$ power with $k$ successive modular squaring, followed by one modular multiplication with the starting value; e.g. for $k=2$ we compute $x_1=x^2\bmod N$; $x_2=x_1^2\bmod N=x^4\bmod N$; $y=x\;x_2\bmod N=x^5\bmod N$. If squaring and modular multiplication use the same time, and represent the overwhelming majority of the effort, going from $e=257=2^8+1$ ($k=8$) to $e=65537=2^{16}+1$ ($k=16$) takes ${16+1\over8+1}\approx1.89$ more time.

$\endgroup$
  • $\begingroup$ Thanks, I think your answer is helpful - but I am not sure I understand everything. When you calculate running time t_1= t_0*f(s_1)/f(s_0), the 'parameter' used, is that the amount of bits of the modulus? I understood everything you wrote that is security-related,but would you mind 'dumbing down' the time-part? I am quite new to big-O and expressing running time. Also, how does one plot a big-O function? Can it be done using Mathematica. Haha, so many questions (sorry). Thanks $\endgroup$ – user9750060 Nov 10 '15 at 22:40

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.