Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm a newbie to encryption. If I create a number 'n' as a product of two prime numbers 'p' and 'q' with the following specifications:
'p' is a fully random prime with 300 decimal digits in length. 'q' is a fully random prime with 400 decimal digits in length.
My question is: If I make 'n' public, will anyone be able to get 'p' and 'q' within a month? Tanks in advance!
No an attacker will not be able to factor your $n$ (e.g. break it).
Your $n$ is of size 700 decimal digits which is $\frac{700}{\log_{10}(2)}\approx2325$ bits. Now 2048-bit moduli is the most widespread size used on the internet and hasn't seen a failure yet (without exploiting bad random number generators), so you are secure with that modulus size.
As for the largest known-broken modulus size, this would be a 768-bit modulus and it is conjectured that nation-state attackers are able to factor 1024-bit moduli using their ressources.
You have chosen 400 digits and 300 digits. While this is safe in this instance, this is unusual to do, because too much unbalancedness can help the attacker as he can apply attacks that find small factors first (by trial division or ECM). The standard way of approaching this is to generate two equally large primes (in terms of digits) and ensuring that $|p-q|>2^{k/3}$ (where k is your modulus bitlength), which will hold anyways with overwhelming probability if you choose both primes independently at random.
Addressing kapserd's comment:
Likely using more than the two primes we use today would not help immensely, and likely (again) would reduce the difficulty. This is, of course, subject to the point I shall end with (below).
The reason is that there is one pair of lengths completing your right triangle for every pair combination of prime factors used. So use {3,5,7} and your combinations are {3,35}, {5,21}, and {7,15} giving you hypotenuse and other side lengths of {19,16}, {13,8}, and {11,4} respectively. (The third side is their product, 105, in all three triangles.) So now the codebreaker would have three targets instead of a single target. And adding primes makes those combinations take off.
The other point addresses the idea of using similar size primes. There is a human element to all things in human life and this is no exception. If one "must" shoot for two 350 decimal digit primes or "be sub-par at his encoding" then codebreakers will start with 350 decimal digit primes and work away from the center, so to speak. Those happen to be the most numerous of the possible numbers to examine (as SEJPM says, one doesn't have to attack the LARGER prime, just the smaller prime). If one uses a 300 and a 400 decimal digit prime, the path to them would be MUCH MUCH longer than the path from 1 decimal digit up to 300. So expecting you to do the cleverest thing mathematically would hurt very badly if you do the cleverest thing "humanly."
(That point applies to kasperd's smaller primes but more of them in the sense that it is, sort of, and obtusely, a way of ending up with primes to find that are a long way from the "balanced" primes SEJPM talks about. So it maybe would get an advantage.)
