Re: Some naive musings about RSA

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).

Conventional notation is n=pq. So this is a rather confusing way to put
it.

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

In more conventional notation:

   2^[(p-1)(q-1)] - 1 = kn

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).

There’s only one k, and it’s k = (2^[(p-1)(q-1)] - 1) / n.

For RSA-2048 that would give us log_2(k) =~ 2^2048. Even if you
converted the entire solar system into a computer, it’d be much too big
to represent.

--
https://www.greenend.org.uk/rjk/