7
$\begingroup$

In this question, we restrict to RSA public keys $(n,e)$ such that

  1. $n$ and $e$ are odd, $3\le e<e_\max$, $e<n$

    Note: For some old Windows API, $e_\max=2^{32}$. In FIPS 186-4, $e_\max=2^{256}$. Other requirements are from PKCS#1.

  2. For all $m\in[0,n)$, it holds $m^e\bmod n=m$. That is, textbook RSA encryption is the identity function. Such unusual requirement is for debugging/analysis purposes.

    Note: That requirement is equivalent to $n$ square-free with $e\equiv1\pmod{\lambda(n)}$, where $\lambda$ is the Carmichael function.

How does the largest possible $n$ evolve as a function of $e_\max$ ?

What's an efficient algorithm to find a $(n,e)$ with large (not necessarily quite maximal) $n$ ?

What are examples (with $n$ as large as possible) for $e_\max=2^{32}$ ?

Do things change if we only require $m^e\bmod n=m$ for most $m\in[0,n)$, that is or remove the requirement that $n$ is square-free?


Motivation: an old comment stated "$n$ is truly tiny" for $e_\max=2^{32}$.

$\endgroup$
3
  • 1
    $\begingroup$ Does $n$ have to be the product of exactly two prime numbers? $\endgroup$
    – Daniel S
    Jan 12, 2023 at 15:32
  • 1
    $\begingroup$ Heh, I got confused by the title as I thought identity as in identity-management. Fortunately reading the actual question and seeing the author cleared that one up, it's just the identity function $f(x) = x$ or $E(m) = m$ in this case :P $\endgroup$
    – Maarten Bodewes
    Jan 12, 2023 at 16:11
  • $\begingroup$ @Daniel S: no, $n$ is only constrained as in 1. It's not necessary either that it's hard to factor, since the public key is not secure anyway. $\endgroup$
    – fgrieu
    Jan 12, 2023 at 16:46

1 Answer 1

5
$\begingroup$

Many thanks for asking this interesting question, and multiple editorial improvements.

For square-free numbers, condition 2 is equivalent to saying that $\lambda(p)$ divides $e-1$ for every prime $p$ that divides $n$, which in turn says that $(p-1)|(e-1)$ for all primes $p$ that divide $n$ is a necessary and sufficient condition. Given such a condition, a natural approach is to choose $e-1$ with many factors and hope that adding one to each factor is a prime. Given $e$, there will be $d(e-1)$ candidates for prime divisors of $n$ and because factors of $e-1$ occur in pairs, the product of all the $p-1$ values can be at most $(e-1)^{\frac{d(e-1)}2}$. This is an upper bound of sorts on how well we can do, but unlikely to be a very tight one as most of our candidates will not be prime. Heuristically then we might expect a product of $p-1$ around size $(e-1)^{\frac{d(e-1)}{2\log e}}$ and so $n$ of similar size*.

All of this motivates choosing $e$ so that $d(e-1)$ is as large as possible and so we could choose $e-1$ to be a highly composite number. Being a little sneakier we might note that odd divisors are of no use to us as they will not be of the form $p-1$. Instead we want to have $e-1$ with a large number of even divisors and so letting $e-1$ be twice a highly composite number is probably slightly better. Being greedy let us choose $(e-1)/2$ to be the largest highly composite number less than $e_{\mathrm max}/2$. In the case of $e_{\mathrm max}=2^{32}$ we can directly look this up in Ramanujan's classic paper and see that the choice $(e-1)/2=2095133040=2^4\cdot3^4\cdot5\cdot7\cdot 11\cdot13\cdot17\cdot19$, which is equivalent to the choice $e=4190266081<2^{32}$. Here's some sage

eminus1 = 2^5*3^4*5*7*11*13*17*19
pp = []
for d in eminus1.divisors():
    if is_prime(d+1):
        pp+=[d+1]
n = prod(pp)

which gives us the 8012-bit $n$ :

709646208014585150890871550433345056103596951823588673062275614500185549073757388141231464088281182469964275713741823081119376553744553888460013731836818457690645159749444897904379484735678885208632475222542089843255457586557157192693077597549612572185484270372933578241322991701582270631442897237888777784427046809586941066881187275863715679017344867341317817037488231592067648304962483440201315626634676614628738924360238679010692824875091147023509250598084747598601331851467628158366840414176527562338651574323363308401031464146837204005297508483200802331440182024566132593026280792754339338888418114289205539708802892126128394425942636073747287685556784279959306681795124263894971083243513820403794650572000621494793075790805601475858616359077542210912301801626897849297833516161049824423111801676806714364289101745801280380322417390095474316750444400897514816405976218003382663217392350599466928327002452844913876925180238187923399920000961136382624827296252793015195688029552243938787885559528344199179843462541001024593576810163221575784629820459768138273537191466234350621908012387013092994493323540013809484775566269677490011102097358733314489863307418531090903542906349933666960108764219612093131106865438382095096760945733775450856039034111294965246059070415990133443545231060410567678149466186356755403229078154827586116908234349501396471831302801918478570370845164066724331087136341060318573490792676263276046757692350939135375146554886120263972014539543483319092583452771807359942947767791704652160989733062655300947505983468036469534172433073554329454940958963980366227319614082760795466458602840272493610908746784140775814921226720472012779991619902772009511513876311572756720315505723978897545450318192817346866775711797473562023110590029486954872112538519305855400760952824509365115209842732952503164489403037745409932750773229406460278448112545535678381916473526884142741710615488487242704823690394318376019030450198962361342367514952519293804227906712790708430460369321461239831745682083801098886352914417543364259874119977843065586553402123831629649634020580672862276382210738132451160697129225063413839022967175257339497779135945413194267153918862698526387450871624555589515220480538545102341594782123777187023279295807514420540155994517703363855436579918814137167679702342119373527577732329172386300608769293445615932445746413773715895259229096188705209848008477180405483862978079696493510

As fgrieu points out, this is even, as our sage code included the divisor 1, so we should divide out by the factor of 2. However, if we drop our square-free assumption, we note that 3, 5, 7, 11, 13, 17 and 19 all divide $n$. If we allow for exceptions in the cases where $p|m$ but $p^r$ does not divide $m$ (here $r$ is the largest power of $p$ that divides $n$), we can increase the power of each of these primes and still have a number whose Carmichael function evaluates to $e-1$. Specifically, we can multiply $n$ by $3^4\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19/2$ to form the a 8037-bit modulus which will fail on a proportion $$1-\frac{163}{243}\frac{21}{25}\frac{43}{49}\frac{111}{121}\frac{157}{169}\frac{273}{289}\frac{343}{361}$$ of messages.

In the comments below @fgrieu suggests that it would be of interest to find divisors of this $n$ with bit length exactly 2048 or 3072. This can be done straightforwardly enough; we run through our list of primes (I will do this in reverse to reduce the chances of small factors being spotted e.g. because the modulus ends in 5), multiplying in a prime unless it would form a product of too large a bit length. Here's some more sage

pp.reverse()
n2048 = 1
lg2048 = 2048.0
for p in pp:
    if N(log(p,2.0)) <= lg2048:
        n2048 *=p
        lg2048 -= log(p,2.0)

which gives the following 2048-bit modulus for the same value of $e$ :

25221518893438748889850305777274652645546562003164475182563355199272942456123642025485356087317855439495470736885864906996264229739957876791659643881508498160047738594439635347685131735361416229325271419313881003841185062233877601616251730435123363625037350695419443692395285844362991144820635808694811600641716706712052066522648145932621369340864581630105199301967963217981369210997982734834265708376111780248393932908864959674389034700872109764453034480103626184828403012997872045576535956627817680079571492181167547222968907316303637488523263623449915880540034149147125803970946660919904134707121646808677077340113

In terms of behaviour of the size of $n$ achievable as a function of $e_{\mathbf max}$, Ramanujan proved (see equation 163 of his paper) that the gap between highly composite numbers near $x$ is $$O\left(\frac{x(\log\log\log x)^{3/2}}{\sqrt{\log\log x}}\right)$$ so that we will be able to find an $e$ with $(e-1)/2$ highly composite and $(1-\epsilon)e_{\mathrm max}<e<e_{\mathrm max}$. For such an $e$, $(e-1)$ will have $$2^{\frac{\log e}{\log\log e}+O\left(\frac{\log e}{(\log\log e)^2}\right)}$$ even divisors (see section II.5 of Ramanujan). The expected penalty for only allowing divisors which are one less than a prime can be absorbed into the error term and we see that $$\log\log n\sim\log\log e^{d((e-1)/2)}\sim\frac{\log e}{(\log 2)(\log\log e)},$$ so that the size of the largest $n$ is growing almost exponentially in some sense.

Ramanujan's calculated list of highly composite numbers does not extend as far as $2^{256}$, but he did provide a good algorithmic description of how to construct large "superior highly composite" numbers that could furnish candidate $e$ value around that size. Alternatively even straightforward choices such as taking $e$ to be a large factorial/primorial plus one should generate large $n$. If the $e_{\mathrm max}=2^{256}$ is of especial interest, I can probably throw together some sage, but I hope that the above answers the question in a somewhat complete manner.


(*) - In fact for our choice of $e$ our candidates have a noticeably better chance of being prime than $1/\log e$.

$\endgroup$
2
  • 3
    $\begingroup$ Nitpick: that 8012-bit $n$ is even, contrary to requirement 1. But $n'=n/2$ (8011-bit) is not, and together with $e=4190266081$ matches all the conditions. Congratulations, AFAIK this is the high score to date. Addition: by trimming this, it would be easy to make a 2048-bit or 3072-bit $n$ that would probably pass the tests of standard CAs and be accepted by most browsers, with possibly unexpected and perhaps useful results. $\endgroup$
    – fgrieu
    Jan 12, 2023 at 18:03
  • $\begingroup$ Kudos for the 2048-bit $n$, which would pass muster for many CAs and most browsers. Update: with this, we no longer need to consider $e_\max=2^{256}$. $\endgroup$
    – fgrieu
    Jan 13, 2023 at 12:04

Your Answer

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

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