My Math Forum Mathematical Attack on RSA

 Number Theory Number Theory Math Forum

 January 3rd, 2018, 07:10 PM #1 Newbie   Joined: Jan 2018 From: Cyberaid Posts: 3 Thanks: 0 Math Focus: geomerty and number theory Mathematical Attack on RSA Hello, I am trying to find an equation that will find p and q in the N = p * q problem of RSA cryptography. What I have posted here is my latest attempts. I am having trouble finding the error when a square root is calculated by a computer. Yes, I know this is an impossible problem. But hear me out. I have a long polynomial equation that seems more complicated than basic factoring by division. But as I show here the equation is more processing intensive, but tells whether a given x value is higher or lower, because the calculated PNP can be subtracted from the given PNP. So, we know N and plug in a p to find how far the plugged-in p creates an N that is a calculated distance from the given N. It sounds much more complicated than it actually is, but I just wanted to give the background of this problem I created. Please post your comments and/or questions. Code: PNP = 85 x = 85 F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/ PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))] If [PNP - F > 0, x = x + Sqrt[PNP - F + x]] If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ] 85 85 161 Sqrt[4123/2] 1/2 (85 - 7^(3/4) Sqrt[23] (589/2)^(1/4)) N[1/2 (85 - 7^(3/4) Sqrt[23] (589/2)^(1/4))] -0.249277 PNP = 85 x = 5 F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/ PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))] If [PNP - F > 0, x = x + Sqrt[PNP - F + x ]] If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ] 85 5 Sqrt[4179323/2]/17 1/2 (5 - Sqrt[-80 + Sqrt[4179323/2]/17]) N[1/2 (5 - Sqrt[-80 + Sqrt[4179323/2]/17])] 1.37825 PNP = 85 x = 7 F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/ PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))] If [PNP - F > 0, x = x + Sqrt[PNP - F + x ]] If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ] 85 7 (11 Sqrt[45773587/2])/595 1/2 (7 - Sqrt[-78 + (11 Sqrt[45773587/2])/595]) N[1/2 (7 - Sqrt[-78 + (11 Sqrt[45773587/2])/595])] 1.88414 PNP = 85 x = 3 F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/ PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))] If [PNP - F > 0, x = x + Sqrt[PNP - F + x ]] If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ] 85 3 Sqrt[847772947/2]/255 3 + Sqrt[88 - Sqrt[847772947/2]/255] N[3 + Sqrt[88 - Sqrt[847772947/2]/255]] 5.69458 PNP = 85 x = 1 F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/ PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))] If [PNP - F > 0, x = x + Sqrt[PNP - F + x ]] If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ] 85 1 (7 Sqrt[13123/2])/85 1 + Sqrt[86 - (7 Sqrt[13123/2])/85] N[1 + Sqrt[86 - (7 Sqrt[13123/2])/85]] 9.90669
 January 9th, 2018, 04:32 AM #2 Math Team   Joined: Jan 2015 From: Alabama Posts: 3,261 Thanks: 894 I have no idea what you are trying to say here. In particular, if you are trying to find primes p and q such that pq= N, for given N, where does "PNP= 85" and "x= 85" come from? What is special about "85"? Are you saying that you are specifically setting N= 85 and trying to find p and q such that pq= 85? That's kind of trivial isn't it? 85= 5(17). How would this work for other "N"?
 January 9th, 2018, 07:05 AM #3 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,355 Thanks: 2469 Math Focus: Mainly analysis and algebra The whole point about RSA is that factorising a large semiprime is mathematically difficult. This means that it is possible but the best known algorithms take too long to solve the problem to be practicable. I'm not sure what speed the best algorithms are, but I'd guess at polynomial time or $n\log n$ which means that as soon as it becomes possible to factorise an $N$, we just need to pick bigger semiprimes to put factorisation safely out of reach. What I'm trying to say is that your first port of call should be to study modern factorisation techniques and research to understand the current state of knowledge on the subject.
January 9th, 2018, 09:26 AM   #4
Senior Member

Joined: May 2016
From: USA

Posts: 1,119
Thanks: 464

Quote:
 Originally Posted by Trurl Hello, I am trying to find an equation that will find p and q in the N = p * q problem of RSA cryptography. What I have posted here is my latest attempts. I am having trouble finding the error when a square root is calculated by a computer. Yes, I know this is an impossible problem. But hear me out. I have a long polynomial equation that seems more complicated than basic factoring by division. But as I show here the equation is more processing intensive, but tells whether a given x value is higher or lower, because the calculated PNP can be subtracted from the given PNP. So, we know N and plug in a p to find how far the plugged-in p creates an N that is a calculated distance from the given N. It sounds much more complicated than it actually is, but I just wanted to give the background of this problem I created. Please post your comments and/or questions.
What is PNP? No clue in what you have written. You did define a p and an N. Do they have anything to do with PNP?

What is x? No clue in what you have written. It appears to be an iterated guess.

Where does F come from? No clue in what you have written.

Lastly, you do realize that iterative methods for factoring numbers have been known for literally millennia, don't you? Finding a new one is significant only if you can show that, for some material class of cases, the new method is significantly faster than existing methods.

January 9th, 2018, 09:32 AM   #5
Math Team

Joined: Oct 2011

Posts: 13,103
Thanks: 907

Quote:
 Originally Posted by Trurl If [PNP - F > 0, x = x + Sqrt[PNP - F + x]] If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ]
If [PNP - F = 0 ??........]

February 15th, 2018, 09:55 AM   #6
Newbie

Joined: Jan 2018
From: Cyberaid

Posts: 3
Thanks: 0

Math Focus: geomerty and number theory
Quote:
 Originally Posted by Country Boy I have no idea what you are trying to say here. In particular, if you are trying to find primes p and q such that pq= N, for given N, where does "PNP= 85" and "x= 85" come from? What is special about "85"? Are you saying that you are specifically setting N= 85 and trying to find p and q such that pq= 85? That's kind of trivial isn't it? 85= 5(17). How would this work for other "N"?
Well, the equation tests a test value of “x” which in the equation N = p*q which in this equation

PNP = N
x = p (the smaller product)
q = y (the larger product)

PNP = x * y = N = p * q

Quote:
 Originally Posted by v8archie The whole point about RSA is that factorising a large semiprime is mathematically difficult. This means that it is possible but the best known algorithms take too long to solve the problem to be practicable. I'm not sure what speed the best algorithms are, but I'd guess at polynomial time or nlogn which means that as soon as it becomes possible to factorise an N, we just need to pick bigger semiprimes to put factorisation safely out of reach. What I'm trying to say is that your first port of call should be to study modern factorisation techniques and research to understand the current state of knowledge on the subject.
Well, I chose this factorization because it is my own invention. I argue it would be significantly faster if it remained accurate with Prime quotients of hundreds of digits long. I have been told it would be easier to rely on factorization because my equation is too complex. However, my equation tells whether the test value for “x” is higher or lower than the correct value of PNP. So, there is some usefulness. It all depends on the accuracy of the square root of the equation.

Quote:
 Originally Posted by Denis If [PNP - F = 0 ??........]
Well, if there is no error, PNP solved in the equation minus the known PNP would equal zero. So as the test value x gets closer to the given PNP the result approaches zero.

Quote:
 Originally Posted by JeffM1 What is PNP? No clue in what you have written. You did define a p and an N. Do they have anything to do with PNP? What is x? No clue in what you have written. It appears to be an iterated guess. Where does F come from? No clue in what you have written. Lastly, you do realize that iterative methods for factoring numbers have been known for literally millennia, don't you? Finding a new one is significant only if you can show that, for some material class of cases, the new method is significantly faster than existing methods.
Yes, I am aware there are other factoring methods. But mine does more than just test factors by division. It may or may not be significant. But definitely not tried before.

PNP = N
x = p
y = q
F is just a variable I used in Mathematica to hold the value of my if-then-statements. You can ignore those if statements because when PNP gets close to the given PNP the result equals zero.

So I am just placing PNP = 85 and x = 5. Small test values. But I am having trouble with large values do to accuracy.

I hope this explains everything. If it still doesn’t make sense just ask me and I will try to explain why I set up the equation the way I did.

New Work Below

PNP = 85
x = 5

F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/
PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))]

85

5

Sqrt[4179323/2]/17

N[F]

85.0333

Ok, the important thing about the above equations is equation F is the Cumulative Distribution Function of the factors of PNP!

The values below are to show that with the proper x, F will equal (within small error) PNP. This is just to show that it works for Semi-Primes that are a little harder to do on a calculator.

If someone knows how to program large numbers: millions of digits, then they could find larger Prime numbers or break encryption that use factorization as a one way function; RSA for example.

But wait. If you put F into the following programming logic you have created a Normal Distribution Function!

If [PNP - F > 0, x = x + Sqrt[PNP - F + x]]
If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ]

These logic statements create a normal distribution when graphed. Of course it is centered at zero and can be used to correct the error of equation F. But we must note it is mirrored in the x-axis. But know we know where the distribution of the smaller factor that is multiplied to equal PNP. We have a Bell Curve; almost. I am only calling it that because that is what is usually though of with normal distribution. But I think as you read this it may add more credibility to my work.

PNP = 2999* 6883
x = 2999

F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/
PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))]

20642117

2999

Sqrt[40378385476407827918859/2]/6883

N[F]

2.06434*10^7

New Work Below

PNP = 85
x = 5

F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/
PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))]

85

5

Sqrt[4179323/2]/17

N[F]

85.0333

Ok, the important thing about the above equations is equation F is the Cumulative Distribution Function of the factors of PNP!

The values below are to show that with the proper x, F will equal (within small error) PNP. This is just to show that it works for Semi-Primes that are a little harder to do on a calculator.

If someone knows how to program large numbers: millions of digits, then they could find larger Prime numbers or break encryption that use factorization as a one way function; RSA for example.

But wait. If you put F into the following programming logic you have created a Normal Distribution Function!

If [PNP - F > 0, x = x + Sqrt[PNP - F + x]]
If [PNP - F < 0, x = ( x - Sqrt[F - PNP + x]) /2 ]

These logic statements create a normal distribution when graphed. Of course it is centered at zero and can be used to correct the error of equation F. But we must note it is mirrored in the x-axis. But know we know where the distribution of the smaller factor that is multiplied to equal PNP. We have a Bell Curve; almost. I am only calling it that because that is what is usually though of with normal distribution. But I think as you read this it may add more credibility to my work.

PNP = 2999* 6883
x = 2999

F = Sqrt[(((((x^2*PNP^4 + 2*PNP^2*x^5) + x^8)/
PNP^4) - ((1 - x^2/(2*PNP))))*((PNP^2/x^2)))]

20642117

2999

Sqrt[40378385476407827918859/2]/6883

N[F]

2.06434*10^7

Last edited by skipjack; February 20th, 2018 at 09:55 PM.

 Tags attack, mathematical, rsa

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post CSteiner Applied Math 4 January 11th, 2015 12:45 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top