 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?   Thread Tools Show Printable Version Email this Page 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