RSA 704 Question

[R.D. Silverman]

Originally Posted by dgatlin

Thanks for the replies. Any idea why they are believed to be of equal length? The numbers I came up with for upper/lower bound are different than yours. Could you elaborate on how you came up with those numbers?

They have equal bit length. It is not a question of "belief", but
one of "fact".

[jtavares]

How about RSA-129: http://en.wikipedia.org/wiki/RSA-129

Correct me if I am wrong but the factors seems to have different bit lengths.

[jasonp]

Originally Posted by jtavares

How about RSA-129: http://en.wikipedia.org/wiki/RSA-129

Correct me if I am wrong but the factors seems to have different bit lengths.

They have different bit lengths, but RSA Data Security did not generate them and RSA-129 was not part of RSA's contest.

[R.D. Silverman]

Originally Posted by jtavares

How about RSA-129: http://en.wikipedia.org/wiki/RSA-129

Correct me if I am wrong but the factors seems to have different bit lengths.

So what? If you know anything about RSA-129 then you know that it was
generated even before RSA Data Security existed....

[dgatlin]

Originally Posted by R.D. Silverman

They have equal bit length. It is not a question of "belief", but
one of "fact".

Well, I *believed* they were of equal length before I started this thread. I really wanted to know *why*, not just a statement that it was fact. So far, I have seen some good reasoning (but not from you) that they are of equal length. Untill I see proof, I won't be able to confidently call it a fact.

And let me also join in on criticizing jtavares, what would ever give him the idea that it was RSA that generated "RSA-129", next he'll be telling us is that they also generated RSA-768 and RSA-2048.

[philmoore]

Perhaps you did not read the threads that Akruppa recommended. If you had, you would have found out that Mr. Silverman did indeed generate all of the larger RSA challenge numbers while he was an employee at RSA. His statement that both factors are the same bit length is based on the fact that that was the intended outcome of his program. However, because noone has actually examined the factors, and the disks containing the factors were destroyed, this "fact" is unverifiable until the factorizations are eventually completed. As Paul Leyland pointed out, this "fact" is actually based on the belief that the program worked correctly. Because it has been corroborated by all of the factorizations completed so far, I don't believe that anyone has any reasonable grounds to doubt it.

[R.D. Silverman]

Originally Posted by philmoore

Perhaps you did not read the threads that Akruppa recommended. If you had, you would have found out that Mr. Silverman did indeed generate all of the larger RSA challenge numbers while he was an employee at RSA. His statement that both factors are the same bit length is based on the fact that that was the intended outcome of his program. However, because noone has actually examined the factors, and the disks containing the factors were destroyed, this "fact" is unverifiable until the factorizations are eventually completed. As Paul Leyland pointed out, this "fact" is actually based on the belief that the program worked correctly. Because it has been corroborated by all of the factorizations completed so far, I don't believe that anyone has any reasonable grounds to doubt it.

(1) You write "disks containing the factors were destroyed". The factors
were never written to disk. They were generated in dynamic memory as
part of a BSAFE data structure. They were multiplied together and their
*product* was output. But the primes themselves never left dynamic
memory. They were never output in any way. The code was generated
and compiled, and then the executable was transferred to a brand new
laptop with only the OS present. No compilers, no Internet software etc.
The laptop was not attached to the Internet at all. I took the laptop
into my *car* (a close approximation of a Fraday cage), and ran the code.
The composites were written to a floppy. The primes were never revealed.

(2) The code was jointly checked by John Brainard and myself. We did
check that it worked correctly before it was used in production mode.

As for whether my claim constitutes a fact because of the uncertainty
whether the code ran correctly, I could also ask how you know that
the factorizations done so far have primes of equal bit length? Perhaps
one of the prime factors is actually composite and there was a bug in
the code that tested the factors for primality??????

This is a philosophical issue. When a computer (or even independent
computers) perform a computation, there is always a minute probability of
a bug. Independent computers reduce this probability, but it is still
non-zero. This applies to *any* code and computation, and raises the
question: When can an answer given by a computer ever be taken as
"fact"????

My testimony (along with that of John Brainard) would constitute "fact"
in any court.

[retina]

Originally Posted by R.D. Silverman

... *car* (a close approximation of a Fraday cage)...

Thanks for the explanation. But I think a car is not a very good approximation for a Faraday cage, my cell phone works quite fine inside a car. Unless of course you have modified your car in some way to make it a better Faraday cage?

[philmoore]

Originally Posted by R.D. Silverman

The "someone" would be me and John Brainard (still at RSA). We used a
hardware RNG with calls to BSAFE to generate the primes and multiply
them. The code did not send the primes to any external channel (e.g.
print them) so were never revealed. We did this on a laptop disconnected
from all networks and destroyed the code/disk afterward.

Noone (including me) knows the factors. I will confirm that each RSA key
is the product of nearly equal primes. (but don't waste your time with
Fermat's method or related techniques (e.h. Lehman's; they are not that close)

Thanks for the additional details This quote from 05-May-05 was why I had falsely assumed that disks containing the factors had been destroyed.

As for your point about whether we know that the factors of equal bit length found so far really are prime, they are small enough that they could be easily verified to be such, not that I have actually done so. I think that verification through other software would be taken by most reasonable people as evidence of fact. At present, it is impossible to verify in this case, as no one knows the factors!

[R.D. Silverman]

Originally Posted by philmoore

Thanks for the additional details This quote from 05-May-05 was why I had falsely assumed that disks containing the factors had been destroyed.

As for your point about whether we know that the factors of equal bit length found so far really are prime, they are small enough that they could be easily verified to be such

What disk "containing the factors"? Where did I EVER write that the
*factors* were written to disk? I did say that the **code** and its disk
were destroyed. The code was transferred to the laptop that did the
computation via floppy.

Please explain how the factors can be easily *verified* as prime?

There is always a small probability of an error in any computer and computer
code that tests them. Multiple independent computers reduce the
probability, but it still isn't 0.

So I therefore ask: when does the result of a computer computation
constitute "fact"? (It was not I who raised this issue)

Someone else was unwilling to accept my claimed fact that the factors
of RSA704 have equal bit length....

[retina]

Originally Posted by retina

I hope he is also friendly and patient ...

I think I got my answer.