From Newsgroup: comp.misc

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

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). The method I came up with is to
start with a variable v initialised to m. Then repeatedly look for the
lowest zero bit in v, say bit i, and add m * 2^i to v. That will set
that bit, but not disturb any bits lower than i. So, just do this
repeatedly, until v is a continuous sequence of 1s.

But remember the spoiler alert. Outside of some very improbable cases,
for realistic values of m used in RSA, this will take longer than the
time remaining in the Universe to terminate.

I think it's reasonably obvious that if the algorithm terminates, it
will yield a value that is not greater than n. So here's the question:
Leaving aside concerns about the longevity of the Universe, can one be
sure that it will ever terminate?

Sylvia.











--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.misc

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/
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.misc

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.)
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.misc

Ethan Carter <ec1828@somewhere.edu> writes:

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

Noting again for reference that conventional notation here is n=pq.

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

I covered this in another post. For a given RSA key there’s only one k
and it’s straightforward to write down an expression for it, just not practical to compute the value of that expression. I don’t know why
Sylvia thought there might be more than one, or for that matter why k=0
would work since it’s obviously not possible for any RSA key.

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.

p-1 and q-1 are always divisible by 2, as small a factor as you can
possibly get.
--
https://www.greenend.org.uk/rjk/
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: comp.misc

Richard Kettlewell <invalid@invalid.invalid> writes:

Ethan Carter <ec1828@somewhere.edu> writes:

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

Noting again for reference that conventional notation here is n=pq.

Noted. (I wanted to keep most of the choices of the OP.)

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

I covered this in another post. For a given RSA key there’s only one k
and it’s straightforward to write down an expression for it, just not practical to compute the value of that expression. I don’t know why
Sylvia thought there might be more than one, or for that matter why k=0
would work since it’s obviously not possible for any RSA key.

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.

What was I thinking? I somehow thought 2^8 = 16.

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.

p-1 and q-1 are always divisible by 2, as small a factor as you can
possibly get.

You're right. I'm totally mistaken. Scratch it all. Thanks!
--- Synchronet 3.21a-Linux NewsLink 1.2