mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > Alberico Lepore

Reply
 
Thread Tools
Old 2019-08-21, 13:15   #1
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

23·32·7 Posts
Default 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
File Type: pdf Piccolo teorema di Lepore.pdf (28.3 KB, 113 views)
Alberico Lepore is offline   Reply With Quote
Old 2019-08-21, 14:28   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,811 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
xilman is online now   Reply With Quote
Old 2019-08-21, 17:17   #3
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1F816 Posts
Default

Quote:
Originally Posted by xilman View Post
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?
Alberico Lepore is offline   Reply With Quote
Old 2019-08-21, 17:58   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2A7216 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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?
xilman is online now   Reply With Quote
Old 2019-08-21, 18:12   #5
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1111110002 Posts
Default

Quote:
Originally Posted by xilman View Post
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?
Alberico Lepore is offline   Reply With Quote
Old 2019-08-21, 20:40   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·2,477 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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?
VBCurtis is offline   Reply With Quote
Old 2019-08-22, 07:14   #7
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

23×32×7 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
What stops you from trying yourself to use it?
according to me it cannot be applied without modifications since | h0 |> N ^ (1/4)
Alberico Lepore is offline   Reply With Quote
Old 2019-08-22, 11:53   #8
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

1F816 Posts
Default

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?
Alberico Lepore is offline   Reply With Quote
Old 2019-08-22, 15:18   #9
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32·1,061 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
...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!
Batalov is offline   Reply With Quote
Old 2019-08-23, 02:57   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

141708 Posts
Default

Quote:
Originally Posted by Alberico Lepore View Post
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.
retina is offline   Reply With Quote
Old 2019-08-24, 13:37   #11
Alberico Lepore
 
Alberico Lepore's Avatar
 
May 2017
ITALY

23×32×7 Posts
Default

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?
Alberico Lepore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Potential primality of F33, F34, and F35 siegert81 FermatSearch 37 2018-07-22 22:09
Prime95 potential race on WORKER_THREADS_ACTIVE and WORKER_THREADS_STOPPING Explorer09 Software 2 2017-03-09 08:17
A potential cause of Windows low-memory messages cheesehead Software 14 2013-05-16 00:45
Low-Stress Job with High Potential? Mathematician cheesehead Lounge 20 2009-06-05 20:24
Formula to calculate number of potential factors? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.