4
$\begingroup$

Given public standard RSA exponent e = 65537, is there any (d, n) pairs so that RSA decryption becomes a trivial operation?

The modulus n must be no less than 2048-bit. The goal is to get a real certificate for some internal server that must send same data both via http and https. Certificate authorities will check modulus length. But some of them can possibly accept other e values so it can be a viable option too.

Note: security is not a factor at all, only simplicity\speed matters (trivial complexity will be an ideal).

$\endgroup$
  • 6
    $\begingroup$ Why do you want to use a 2048-bit modulus if security doesn't matter and why bother using RSA at all? Note that most fast choices of $d$ will enable any attacker to factor $n$. $\endgroup$ – SEJPM Aug 28 '15 at 17:04
  • 10
    $\begingroup$ @Eug: The 'https' protocol has the advantage over 'http' that it authenticates the data as coming from the server. Even if the same data is accessible via 'http', this does not imply that the 'https' protocol is useless and that you shouldn't care about the security. IMO, if you implement an unsafe https protocol, then you are cheating on the clients that connect. $\endgroup$ – Chris Aug 28 '15 at 18:09
  • 1
    $\begingroup$ @Chris Is this a philosophy community? Other than this is a deep offtopic and https alone does not guarantee to you something, I can say that if cracking costs are much greater than potential profit - that risk can be ignored. That is the golden rule of the cryptography, I guess. So better write your morality thoughts to Mozilla, as they are just dropping 1024-bit RSA certificates, just because they can do that (who cares that there are zillions of cases when 2048 is overkill?). $\endgroup$ – Eug Aug 28 '15 at 20:25
  • 10
    $\begingroup$ @Eug, this question isn't just about you, but will remain as a reference for future visitors. Chris' comment raises an important point that they may care about even if you don't. $\endgroup$ – otus Aug 28 '15 at 20:39
  • 4
    $\begingroup$ @Eug: Sorry Eug, I did not want to offend you! When I write something here, my intention is to help people increase their crypto skills. In a previous comment you argued like "its just a formal thing, the same data that is available over http has also to be available over https, so we really don't have to care about security". Therefore I thought it could be useful to remark that there is also the authentication aspect to it. I also added my impression about 'unsecure' https; but (as I tried to indicate) it is a personal opinion and obviously not everybody has to agree with it. $\endgroup$ – Chris Aug 28 '15 at 22:44
20
$\begingroup$

Actually, if you're willing to consider a somewhat larger $e$, I found a solution that makes the decryption part real cheap.

This solution has $e = 446185741$ and $n = 3*5*7*11*13*23*29*31*43*47*53*61*67*71*79*103*131*139*157*191*211*229*239*277*331*419*421*443*461*463*547*571*599*647*661*691*859*911*967*1013*1021*1093*1123*1327*1381*1429*1483*1597*1871*1933*2003*2311*2347*2381*2531*2731*2861*2927*3037*3221*3571*3877*3911*4421*4523*4621*4831*5237*5981*6007*6271*6917*7411*7591*8581*8741*8779*8971*9283*9661*10627*10949*11731*12541*13567*14821*17291*19381*20021*20333*20749*21319*25117*28843*29173*29717*30941*35531*36709*38039*43891*46411*51613*51871*58787*62791*72931*78541*91771*92821*102103*106261*106591*111827*113621*134597*135661*138139*145861*163021*197341*213181*251941*258061*276277*304981*336491*355811*426973*445741*461891*520031*554269*602141*624037*749893*782783*903211*1118261*1193011*1381381*1492261*1749749*1806421*1939939*2134861*2348347*2624623*2704157*2771341*2897311*3233231*3354781*3749461*8112469*13123111*17160991*40562341$

Unless I miscalculated something (a real possibility), the corresponding decryption exponent is $d=1$; I believe that satisfies your requirement as to a "trivial" operation.

$\endgroup$
  • 4
    $\begingroup$ I'm not sure if this helps the OP as he explicitely fixed $e$ to be $65537$. But anyway, really nice finding, may I ask how you found it? $\endgroup$ – SEJPM Aug 28 '15 at 20:36
  • 1
    $\begingroup$ I confirm the calculations. $\lambda(n)+1=e$ $\endgroup$ – fgrieu Aug 28 '15 at 20:49
  • 8
    $\begingroup$ @SEJPM: $d=1$ if for every prime factor $p$ of $n$, we have $e \equiv 1 \bmod p-1$. So, I picked an $e$ where $e−1$ is divisible by a lot of numbers, and then tested all those divisors to find which ones were one less than a prime, and then made sure that the product of all those primes was $>2^{2048}$ $\endgroup$ – poncho Aug 28 '15 at 21:14
  • $\begingroup$ Of course, once you've got your certificate approved, you can just configure your server to use $e=1$, too! $\endgroup$ – Ilmari Karonen Aug 29 '15 at 15:16
9
$\begingroup$

An option strictly matching the question's statement (which requires $e=65537$) is to choose the public modulus $n$ as the product of many small primes $p_i$, perhaps $k=64$ primes of $32$ bits. That's multiprime RSA pushed to the max. The potential speedup is considerable. For small $k$, and standard arithmetic (quadratic multiplication and modular reduction) the speedup compared to normal RSA with CRT is in the order of $k^2/4$; that won't quite scale up to $k=64$, but we can get a speedup by a factor like $300$ or more (justified below).

We can also restricting to primes $p_i$ such that $d_i=e^{-1}\bmod(p_i-1)$ makes raising to the power $d_i$ less costly than for random choice of $p_i$ (if we use the basic exponentiation method: minimizing the sum of the number of bits in $d_i$ plus its Hamming weight). For a simple example, we restrict to the highest 32-bit primes $p_i$ of the form $p=(65537(4m+1)+1)/2$, get $p_0=4294148083, \dots, p_{63}=4203051653$, and $n$ is the (barely) 2048-bit 0x83658dd3af65c3aa48d7741adc0b9043f22501ef022d4b6c4e4ce93aea15b3410f94b1fd57ded3aa2abdcf90c4d05e564158261a28ce620655dc3d6cf2bbfb2ad57a3e9fd1b3c1c6c93e36f1f8fca29c8f0ba1f52458d7912f70d96e4ca447f0adc1de6e8692fc83201987fc7879f28fe8cc3a135ee38f31c240055d0c250ac55301b6229f698ab3d2fc909f28caff4f6f55bb674a003c83daac7964a285ce6d5485e5137e74c202cec0ff0a64b8c1d613ba70af875a6a49c6e36b13b57b4821a74bc65d03bcf5632e979996d5ad61f4844d1217413b4ab5aa804b1d8d04764fab01ade454b358db4710ba0ec82ae385423f9cf51ea11a6bdd1f1fcba1b1383b; each of the $d_i=(2p_i-1)/65537$ is 17-bit (a significant gain compared to about 31-bit with arbitrary choice of $p_i$). The execution time for a simple implementation computing $x^d\bmod n$ for $n$ of $b=2048$-bit is dominated by three steps:

  1. modular reductions of $x$ modulo each of the prime $p_i$, for a total $64\cdot63=4032$ modular reductions of 64-bit modulo a 32-bit $p_i$;
  2. 64 modular exponentiations, for a total of $1693$ (if I counted right) 32-bit multiplications giving 64-bit result followed by modular reduction to 32-bit;
  3. reconstruction of the result using the CRT, which should require (using a binary tree with width of results doubling each time we move closer to the root) about twice as many elementary operations as in regular RSA with CRT, where it can be done with about $3200$ 32-bit multiplications and accumulation of the 64-bit result.

Compare to about 6 million 32-bit multiplications and accumulation of the 64-bit result (for the equivalent of step 2) in regular RSA with CRT.

[If we can amortize computations over significant use, we can further optimize step 2, thus gain a little, by choosing even smaller $p_i$ (thus even more of them), and precomputing $x^{e^{-1}\bmod(p_i-1)}$ for every $x\in\{0,\dots,p_i-1\}$. For $k=128$, 20 MB of RAM are enough. Other costs are only marginally raised.]

As long as the certification authority is not more zealous than stated in standard Certificate Practice Statements (by trying to factor your $n$ even so slightly), it should deliver a certificate for such key; and things will be perfectly compatible with anything around not manipulating the private key and not trying to factor $n$. But there is a high risk to be exposed as using such trick. In fact any trick giving you a sizable speedup that I can imagine will expose you to that risk.


The above gives no security: anyone caring can factor $n$ (then act as the key owner, including in many cases revoking the key). Factoring is not even necessary in Poncho's system. However that comment suggests that keeping some level of security suitable for short term use might be what the question is about. In the following, I consider how far we can raise $k$ without becoming ridiculously weak.

When we use $k$ primes of about equal size, they will be about $2048/k$ bits. The best known factoring algorithm able to take advantage of small factors in $n$ is ECM. The largest factor ever found by ECM is 273-bit, and only two are above 256-bit. It is thus reasonable to believe that $k=8$ still leaves some security, while it does give a speedup of about $15$ compared to standard RSA with CRT.

$\endgroup$
  • $\begingroup$ Looks like multi-power RSA can be a little bit faster, found a comparison here: cseweb.ucsd.edu/~hovav/dist/survey.pdf But probably there can be something even more clever, given the full freedom of security limitations. $\endgroup$ – Eug Aug 28 '15 at 18:45
  • 2
    $\begingroup$ Well if there would be any good speed up tricks for decryption which wouldn't significantly weaken the encryption people would actually use them, so chances are, all affect security or (if you found one) you can publish a paper about it. $\endgroup$ – SEJPM Aug 28 '15 at 18:47
  • 2
    $\begingroup$ @Eug, that link only considers three primes. With the 33/65 fgrieu suggests you are going to see much more of an effect on both security and performance. $\endgroup$ – otus Aug 28 '15 at 20:36

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.