
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 pluggedin 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: 2,967 Thanks: 807 
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,234 Thanks: 2412 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: 922 Thanks: 368  Quote:
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 From: Ottawa Ontario, Canada Posts: 11,849 Thanks: 766  
February 15th, 2018, 09:55 AM  #6  
Newbie Joined: Jan 2018 From: Cyberaid Posts: 3 Thanks: 0 Math Focus: geomerty and number theory  Quote:
PNP = N x = p (the smaller product) q = y (the larger product) PNP = x * y = N = p * q Quote:
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:
PNP = N x = p y = q F is just a variable I used in Mathematica to hold the value of my ifthenstatements. 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 SemiPrimes 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 xaxis. 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 SemiPrimes 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 xaxis. 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  

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