My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
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 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
Trurl is offline  
 
January 9th, 2018, 04:32 AM   #2
Math Team
 
Joined: Jan 2015
From: Alabama

Posts: 3,189
Thanks: 871

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"?
Country Boy is offline  
January 9th, 2018, 07:05 AM   #3
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,313
Thanks: 2447

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.
v8archie is offline  
January 9th, 2018, 09:26 AM   #4
Senior Member
 
Joined: May 2016
From: USA

Posts: 1,038
Thanks: 423

Quote:
Originally Posted by Trurl View Post
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.
JeffM1 is offline  
January 9th, 2018, 09:32 AM   #5
Math Team
 
Joined: Oct 2011
From: Ottawa Ontario, Canada

Posts: 12,599
Thanks: 843

Quote:
Originally Posted by Trurl View Post
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 ??........]
Denis is offline  
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 View Post
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 View Post
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 View Post
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 View Post
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.
Trurl is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2018 My Math Forum. All rights reserved.