mersenneforum.org Potential Coppersmith attack on RSA
 Register FAQ Search Today's Posts Mark Forums Read

2019-08-21, 13:15   #1
Alberico Lepore

May 2017
ITALY

23·32·7 Posts
Potential Coppersmith attack on RSA

The sum S of consecutive odd cubes from 1 to n = 2 * h + 1 is
[(h+1)^2]*(2*h^2+4*h+1)=2*h^4+8*h^3+11*h^2+6*h+1
[see attachment]

That said
One approach to RSA factorization could be this
If a multiple K * N of the number to be factored N is sum of cubes
then
2*h^4+8*h^3+11*h^2+6*h+1=N*K
then using Coppersmith
is found h in polynomial times
once found h
GCD((h+1),N)=p

it can be done?
Attached Files
 Piccolo teorema di Lepore.pdf (28.3 KB, 113 views)

2019-08-21, 14:28   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×1,811 Posts

Quote:
 Originally Posted by Alberico Lepore If a multiple K * N of the number to be factored N is sum of cubes then ... it can be done?
I give you RSA-1024 = 1^3 + 1^3 + 1^3 + .... + 1^3.

Off you go.

2019-08-21, 17:17   #3
Alberico Lepore

May 2017
ITALY

1F816 Posts

Quote:
 Originally Posted by xilman I give you RSA-1024 = 1^3 + 1^3 + 1^3 + .... + 1^3. Off you go.
sum of consecutive odd cubes from 1 to n=2*h+1

K*[RSA-1024]=1^3+3^3+5^3+.........+(2*h+1)^3=2*h^4+8*h^3+11*h^2+6*h+1

is possible use Coppersmith?

2019-08-21, 17:58   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2A7216 Posts

Quote:
 Originally Posted by Alberico Lepore sum of consecutive odd cubes from 1 to n=2*h+1 K*[RSA-1024]=1^3+3^3+5^3+.........+(2*h+1)^3=2*h^4+8*h^3+11*h^2+6*h+1
In which case, why did you not say so?

2019-08-21, 18:12   #5
Alberico Lepore

May 2017
ITALY

1111110002 Posts

Quote:
 Originally Posted by xilman In which case, why did you not say so?
yes, I was wrong (omitted) this fact.
In this case is it possible to use Coppersmith?

2019-08-21, 20:40   #6
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2·2,477 Posts

Quote:
 Originally Posted by Alberico Lepore yes, I was wrong (omitted) this fact. In this case is it possible to use Coppersmith?
What stops you from trying yourself to use it?

2019-08-22, 07:14   #7
Alberico Lepore

May 2017
ITALY

23×32×7 Posts

Quote:
 Originally Posted by VBCurtis What stops you from trying yourself to use it?
according to me it cannot be applied without modifications since | h0 |> N ^ (1/4)

 2019-08-22, 11:53 #8 Alberico Lepore     May 2017 ITALY 1F816 Posts Then the two new questions are: Would any of you know how to transform 2*h^4+8*h^3+11*h^2+6*h+1=N*K into a polynomial that satisfies the conditions of Coppersmith? Do you know other methods to find h?
2019-08-22, 15:18   #9
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32·1,061 Posts

Quote:
 Originally Posted by Alberico Lepore ...then 2*h^4+8*h^3+11*h^2+6*h+1=N*K then using Coppersmith ...
2*h^4+8*h^3+11*h^2+6*h+1 = (h + 1)^2 * (2*h^2 + 4*h + 1)

And then wtf for does one need "Coppersmith"??? It is already factored!

2019-08-23, 02:57   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

141708 Posts

Quote:
 Originally Posted by Alberico Lepore The sum S of consecutive odd cubes from 1 to n = 2 * h + 1 is [(h+1)^2]*(2*h^2+4*h+1)=2*h^4+8*h^3+11*h^2+6*h+1 [see attachment] That said One approach to RSA factorization could be this If a multiple K * N of the number to be factored N is sum of cubes then 2*h^4+8*h^3+11*h^2+6*h+1=N*K then using Coppersmith is found h in polynomial times once found h GCD((h+1),N)=p it can be done?
Start with a smaller number. If it works then try a larger number. Keep repeating until you eventually reach numbers like RSA1024. Or at least see how far you get before you discover the roadblocks that need to be solved.

 2019-08-24, 13:37 #11 Alberico Lepore     May 2017 ITALY 23×32×7 Posts I managed to bring any number into the polynomial 81 * X = -a1 * n ^ 3 + a2 * n ^ 2 - a3 * n + a4 Coppersmith can be used by multiplying the whole polynomial by a prime number P so that n0 <(81 * P) ^ 1/3? or (81 * P) * X = - (a1 * P) * n ^ 3 + (a2 * P) * n ^ 2 - (a3 * P) * n + (a4 * P) would you kindly tell me if in this case you can use Coppersmith?

 Similar Threads Thread Thread Starter Forum Replies Last Post siegert81 FermatSearch 37 2018-07-22 22:09 Explorer09 Software 2 2017-03-09 08:17 cheesehead Software 14 2013-05-16 00:45 cheesehead Lounge 20 2009-06-05 20:24 Fusion_power Miscellaneous Math 13 2005-10-24 17:58

All times are UTC. The time now is 14:11.

Tue Sep 28 14:11:47 UTC 2021 up 67 days, 8:40, 3 users, load averages: 2.05, 1.73, 1.51