Many "Zeros" in Public Key, factorization easy ?
 

Hey all,

our Professor gave us a riddle concerning RSA, prime factorization. It roughly sounds like this:

When creating my public key, I was careless, the public key looks like this:

[CODE]
n = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004943449893861185811563806587897209039394765349228600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004438724091153735385330145100740518448292725876750765167357855909678843140444732487940078664422013
[/CODE]

I am quite sure that the factorization is fairly easy on this one. But why ? Just cannot figure this one out :-( Would be great if someone could give me a tip on this one, does it have to do something with the factorial primes ?

Thank you very much,

Greetings

What are n's particular traits? What particular characteristics of RSA public keys do you know, in general?

n = (10^m+a)*(10^m+b) = pq
a*b = 4438724091153735385330145100740518448292725876750765167357855909678843140444732487940078664422013
a+b = 49434498938611858115638065878972090393947653492286
(should have the actual answer for you shortly...)
J

? A={big number}
? T=round(sqrt(A))
? issquare(T^2-A)
1
? A%round(T-sqrt(T^2-A))
0

I'm actually having problems with this...
msieve gives the factorization of (a*b) as:
p1 factor: 3
p1 factor: 3
p2 factor: 31
p6 factor: 140551
p7 factor: 1691101
prp41 factor: 53192383744805292572364285928936275866737
prp43 factor: 1258348708567569132243547867193996784363281
Now, since a*b is 97 digits and a+b is 50 digits, then a and b must each be 49 digits (?).
Also, since a*b ends in 3, and a+b ends in 6, then a ends in 7, and b in 9 (?).
So far, so good - but I can't seem to arrange the factors above to give desired a,b....
Can anyone else help?
J

[quote=Unregistered;198487]n = (10^m+a)*(10^m+b) = pq
a*b = 4438724091153735385330145100740518448292725876750765167357855909678843140444732487940078664422013
a+b = 49434498938611858115638065878972090393947653492286
[/quote]Check your assumptions.

[QUOTE=cheesehead;198495]Check your assumptions.[/QUOTE]

You tell me! :)
J

prp43=p43
J

[CODE]
Last login: Fri Dec 11 14:45:57 on ttys000
Desmond:~ james$ cd math
Desmond:math james$ cd gmp-ecpp
Desmond:gmp-ecpp james$ ./atkin49.gmp*
total = 3183
max = 111763

PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458701
******************
E = 2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193200305992181741359662904357290033429526059563073813232862794349076323382988075319525101901157383418793070215408914993488416750924476146066808226480016847741185374234544243710753907774499206955170227
******************
NATLOGONEPOINTNINE = 0.64185388617239472924480336140742337708875986273577482323572661701981349350622067937977027835051711557447795163484234193531054347593783899429423869404453535514142240725738237814424208303296382145925585774588652778113072312704658578565729252450789704376486755030303476770273209650026296904001464121404548576383
******************
number to be tested or 0 to quit:
1258348708567569132243547867193996784363281
D = -11, dP = 1, P = 1 32768
D = -187, dP = 2, P = 1 4545336381788160000 -3845689020776448000000
j = 1258348708567569132243545594525805890283281
D = -595, dP = 4, P = 1 1908606683491595666107623383040000 8752111455147508300981595950899265536000 483054636550112292687021684688517332992000000 -91399742601830803813322386656934773129216000000
j = 1086925400330382964073177132346989006773405
N[0] = 1258348708567569132243547867193996784363281
a = 1216279372824046067721180339712273625754870
b = 107146466473004570453700290919309043673442
m = 1258348708567569132245765614111687379850544
q = 191857102865472574188504061
P = (141383339, 440369271776032351132821693841488407256480)
P1 = (0, 1)
P2 = (614744102939792574837803939756010891496586, 933339603822832156049176023097197804436211)
N[1] = 191857102865472574188504061
a = 191857102865472572969391004
b = 0
m = 191857102865499431629845250
q = 767428411461997726519381
P = (1782381373, 35592862107491066287643185)
P1 = (0, 1)
P2 = (136132592456267607750070095, 155732348874876656926637504)
N[2] = 767428411461997726519381
a = 767427579541704257876772
b = 0
m = 767428411463744976175172
q = 110783901770629
P = (2066487189, 618541189099874314852572)
P1 = (0, 1)
P2 = (629813497343601678871866, 202173885394664278429567)
N[3] = 110783901770629
a = 110783713479579
b = 0
m = 110783886744834
q = 6154660374713
P = (1504947915, 79263792555867)
P1 = (0, 1)
P2 = (85383958304154, 80332212198595)
N[4] = 6154660374713
a = 6154660374712
b = 0
m = 6154665336208
q = 14915917
P = (2006943890, 1428084754618)
P1 = (0, 1)
P2 = (5298792201095, 2642777147295)
proven prime
number to be tested or 0 to quit:
[/CODE]

[QUOTE=cheesehead;198495]Check your assumptions.[/QUOTE]

I guess I/we should check there _is_ a unique 'm' - but I can't bring myself to count all those zeros!!! (yet) [Is this what you mean, cheesehead?] [and anyway, _unless_ I'm missing something obvious(?) it's a stupid/difficult(!) question w/o a unique 'm'...]
J

[QUOTE=cheesehead;198495]Check your assumptions.[/QUOTE]

I don't _think_ the 10^m can be split, can it?? [so as to give: pq = (2^m'*5^m''+a)*(5^m'*2^m''+b)]
J

Hey again,

thanks a lot for so many replies, did not expect them so quickly :-) Will now look into the problem again. I talked to my prof today and he told me that another student has already sent a solution in.

I also got to know that it cannot be easily brute forced, the key is to think about how these kind of numbers 100000234234000000002342342 can be created.

Thanks again,

Greetings, Chris