Path: nntp.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Ethan Carter <ec1828@somewhere.edu>
Newsgroups: comp.misc
Subject: Re: Some naive musings about RSA
Date: Mon, 07 Jul 2025 20:45:10 -0300
Organization: A noiseless patient Spider
Lines: 54
Message-ID: <87h5znlg55.fsf@somewhere.edu>
References: <mc6qpdF6bjvU1@mid.individual.net>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Tue, 08 Jul 2025 01:45:15 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="57f5be52a2f183cf009d830c038fe3e0";
	logging-data="3331041"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/uEwbch2NqgU7EMyrvCcd3K1gE3sdGI88="
Cancel-Lock: sha1:prxr2hchLojb4P/dPCtx2Ofwg+8=
	sha1:7NfndTUhNwwQ9G3ZW3Od6iwmLNY=

Sylvia Else <sylvia@email.invalid> writes:

> Sometimes in an idle moment, I find myself wondering about possible
> ways to attack RSA. Spoiler alert, I haven't found one.
>
> But in passing, I found myself thinking about this:
>
> For the uninitiated, RSA is based on the fact that if p and q are
> large primes, then the product p*q is a large number that is
> computationally infeasible to factorise - which is to say, no one's
> found a way, though quantum computers offer a possibility.
>
> Let m be p * q, and n be (p-1)(q-1). Then RSA further depends on the
> fact that for any integer a, co-prime with m, a^n modulo m is 1. Since
> 2 will be co-prime with m, that means that 2^n modulo m is also 1. We
> can write that equivalently as
>
> 	2^n - 1 = k * m
>
> where k is an unknown integer. Actually, there are an infinity of
> possible k, but we're interested in the lowest (ignoring the trivial
> case of k = 0).

I suggest you should not use the word ``unknown'' here because the
equation is true for all integers k, as you observe on the following
sentence.  The equation is saying that 2^n - 1 is a multiple of m.
Mathematical lingo is such that ``an unknown integer'' means a /fixed/
number k (that we don't which it is), but your k here is not fixed.
(You can say ``an arbitrary integer'' instead.)

> If we knew k, then that would give us n, or a factor of n (n is never
> prime, it is at least divisible by 4).

Something isn't quite right here.  We trivially know the smallest
positive k that satisfy the equation---that's k = 1.  For example, take
p = 3, q = 5 so that m = 15 and n = 8.  Then the equation

  2^8 - 1 = k * 15

is trivially satisfied by taking k = 1, which is the smallest /positive/
integer you're looking for.  

So I did not really understand the rest of your post.  You seemed to be
looking for a factor of n.  You're then looking for a factor of

  p - 1 or q - 1.

If these numbers would have /small/ factors, you could find them by
trial division, say.  That would indeed be a weakness.  RSA is not safe
if we pick p, q such that p - 1 or q - 1 have small factors.  (A keyword
here would be ``Pollard's p - 1 method''.)  However, Ronald Rivest and
Robert Silverman have argued that by just selecting large random primes,
we're unlikely to run into trouble.  (In other words, we don't need
``strong primes'', meaning the security gain is negligible.)