https://www.johndcook.com/blog/2025/10/06/a-quiet-change-to-rsa/

John D. Cook
Skip to content

  * MATH
      + PROBABILITY
      + SIGNAL PROCESSING
      + NUMERICAL COMPUTING
      + SEE ALL ...
  * STATS
      + EXPERT TESTIMONY
      + WEB ANALYTICS
      + FORECASTING
      + RNG TESTING
      + SEE ALL ...
  * PRIVACY
      + HIPAA
      + SAFE HARBOR
      + CRYPTOGRAPHY
      + DIFFERENTIAL PRIVACY
      + PRIVACY FAQ
  * WRITING
      + BLOG
      + RSS FEED
      + TWITTER
      + SUBSTACK
      + ARTICLES
      + TECH NOTES
  * ABOUT
      + CLIENTS
      + ENDORSEMENTS
      + TEAM
      + SERVICES

(832) 422-8646
Contact

A quiet change to RSA

Posted on 6 October 2025 by John

An RSA public key is a pair of numbers (e, n) where e is an exponent
and n = pq where p and q are large prime numbers. The original RSA
paper said choose a private key d and compute e. In practice now we
choose e and compute d. Furthermore, e is now almost always 65537 for
reasons given here. So the public key is essentially just n.

Euler's totient function

The relationship between the exponent and the private decryption key
in the original RSA paper was

ed = 1 mod ph(n).

It is easy to compute e given d, or d given e, when you know Euler's
totient function of n,

ph(n) = (p - 1)(q - 1).

The security of RSA encryption rests on the assumption that it is
impractical to compute ph(n) unless you know p and q.

Carmichael's totient function

Gradually over the course of several years, the private key d changed
from being the solution to

ed = 1 mod ph(n)

to being the solution to

ed = 1 mod l(n)

where Euler's totient function ph(n) was replaced with Carmichael's
totient function l(n).

The heart of the original RSA paper was Euler's generalization of
Fermat's little theorem which says if a is relatively prime to m,
then

a^ph(n) = 1 (mod n)

Carmichael's l(n) is defined to be the smallest number that can
replace ph(n) in the equation above. It follows that l(n) divides ph(n
).

Why the change?

Using Carmichael's totient rather than Euler's totient results in
smaller private keys and thus faster decryption. When n = pq for odd
primes p and q,

l(n) = lcm( (p - 1), (q - 1) ) = (p - 1)(q - 1) / gcd( (p - 1), (q -
1) )

so l(n) is smaller than ph(n) by a factor of gcd( (p - 1), (q - 1) ).
At a minimum, this factor is at least 2 since p - 1 and q - 1 are
even numbers.

However, an experiment suggests this was a trivial savings. When I
generated ten RSA public keys the gcd was never more than 8.

from sympy import randprime, gcd

for _ in range(10):
    p = randprime(2**1023, 2**1024)
    q = randprime(2**1023, 2**1024)
    print(gcd(p-1, q-1))

I repeated the experiment with 100 samples. The median of the gcd's
was 2, the mean was 35.44, and the maximum was 2370. So the while gcd
might be moderately large, but it is usually just 2 or 4.

Better efficiency

The efficiency gained from using Carmichael's totient is minimal.
More efficiency can be gained by using Garner's algorithm.

Categories : Math
Tags : Cryptography
Bookmark the permalink

Post navigation

Previous PostFermat primes and tangent numbers
Next PostTrue growth rate accounting for inflation

Leave a Reply

Your email address will not be published. Required fields are marked 
*

          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
Comment * [                                             ]

Name * [                              ]

Email * [                              ]

Website [                              ]

[Post Comment] 

 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
D[                                             ] 

Search for: [                    ] [Search]
John D. Cook

John D. Cook, PhD

My colleagues and I have decades of consulting experience helping
companies solve complex problems involving data privacy, applied math
, and statistics.

Let's talk. We look forward to exploring the opportunity to help your
company too.

John D. Cook

(c) All rights reserved.

Search for: [                    ] [Search]
(832) 422-8646

EMAIL