RSA 704 Question

[dgatlin]

Everyone appears to be saying (not necessarily here, but other places) that RSA-704 is a product of two 106 digit primes. I can't think of a reason that this has to be. Is it stated officially that this is the case?

[retina]

Originally Posted by dgatlin

Is it stated officially that this is the case?

I doubt you will ever get an official statement saying such a thing unless it has been broken. My understanding is that the primes making up RSA704 are, as yet, unknown. The original system used to create RSA704 was destroyed and nobody read the original primes before destruction.

Although there is a good chance that the two primes are both 106 digits numbers, since that would make some methods of factorisation harder than if using a smaller prime and a bigger prime. eg. 2 digit prime + 210 digit prime would be trivial to break but 106+106=non_trivial to break.

[axn]

I don't know whether it is "officially" stated... But it is well known that all the RSA numbers have two factors of equal _bit_ length. So for RSA 704, it would be two 352 bit factors.

After looking at the actual number, it looks like the factors will be between
8070373681869514072734228812145027220094678854297782287717332620153464615011270601823360738857596970569827
and
9173994463960286046443283581208347763186259956673124494950355357547691504353939232280074212440502746218496 (2^352)

[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?

[axn]

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?

The factors must both be 352 bits in length. Largest 352 bit number = 2^352-1, thus yielding the upper bound. Lower bound is simply (RSA 704 / Upper bound).

[jasonp]

Originally Posted by dgatlin

Any idea why they are believed to be of equal length?

Because if they were not it would theoretically be easier to collect RSA prize money, and because all RSA challenge number factored to date have had equal size factors, and because customers expect optimal security from generated keys, which requires the modulus to have equal size factors.

jasonp

[ppo]

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?

How did you computed yours numbers ?

[rdotson]

Originally Posted by retina

I doubt you will ever get an official statement ...

You will get a statement as official as it gets from one of the people who created the RSA challenge numbers that the two factors are always the same bit length (In the case of RSA-704 they each contain 352 significant bits). He posts here and over at the Yahoo Prime numbers forum but I'm embarrassed to say I can't recall his name (Silverman?), and don't have a link handy.

The way I understand it, their program generated the factors and tested them for vulnerabilities and produced the RSA Challenge numbers, but NO ONE has ever seen or otherwise had access to the factors of the unsolved RSA challenge numbers.

-- Ron

[akruppa]

Yes, Robert D. Silverman. He posted a brief description of the key generation process on this board sometime, see http://www.mersenneforum.org/showthr...070&#post59070

Alex

[retina]

Originally Posted by akruppa

Yes, Robert D. Silverman. He posted a brief description of the key generation process ...

Brief is quite an understatement. However, it is nice to know there is someone on this board that has been involved in such things. I hope he is also friendly and patient, because from some posts I have seen there seems to be a large gap between the have's and the have-not's.

[akruppa]

Read a couple of follow-up postings to the one I linked to. There's also a link to another thread where he does mention some details of the key generation process.

Alex