Question

how would you crack an RSA cryptosystem by solving the factorization problelm, when not told the modulus. this is for number theory class

Answer 1

RSA can be defined as the standard cryptographic algorithm which is known publicly but is very tough to crack.
In the method of encryption two keys are used one is a public key which is open and is used by the client to encrypt the random session key and in order to intercept the encrypted key, we must use the second key which is the private key. If the session key gets decrypted then only the server can use it to decrypt or encrypt any further messages with the help of a faster algorithm.

This algorithm is based on a very simple idea of Prime Factorization which is simply the multiplying of two prime numbers but it is very hard to factorize its results

Look at this example
Factors for the number 507,906,452,803 is 566,557 x 896,479

So based on the asymmetry in the complexity we can distribute the public key based on the product of two prime numbers but without the knowledge of prime factors, we can't decrypt the message and the prime factorization complexity grows exponentially with every increase in the key length but there are ways available that can reduce the complexity and can break the encryption and one such the algorithm is the Shors Algorithm but in the question, we must not include the modulus also so it eliminates many algorithms as GCD and modulus is very important

So let's see some other options
We know the security of RSA is based on the multiplication of the two prime numbers which will give the modulus value and if by any way we can get the modulus value then we can crack the decryption key.

Let me give you some of the methods which can factorize the modulus

-Difference of Squares
This can be referred as the simplest methods in which we can factorize a value by taking a value and then add it with a squared value and if the result comes out to be a square then we can use the difference of the squares to find the factors

I am explaining here all the process that goes here because it will be very lengthy and is totally different from what you have asked so if you want to learn the method you can search

First, we need to start with:
x²−y²=(x−y)(x+y)

N=y²−x²

The factors of N:
(x+y) and (x−y)

rearranging N=x²−y² we get:
N+y²=x²
and then we need to carry further steps and coding

One more way is
-Elliptic curve factorization
This factorization method is also known as the Lenstra elliptic curve factorization and is one of the fastest integer factorization methods. This method is suitable only for the numbers which are below 60 digits and helpful in finding small factors

One more method is
-Pollards ρ method
In order to find the factor, we need to iterate until the gcd()(greatest common denominator) value is not unity and the value that gets returned from the nonunity gcd() value is the first factor.