Cracking N bits of RSA bits modulo
This is related to my previous post where my only option was to have an RSA algorithm that seemed relatively weak. Suppose I want to encode a 35 bit number (0 to 34359738367) with a 36 bit modulo (between 34359738368 and 68719476735).
Referring to http://en.wikipedia.org/wiki/RSA , I see that my n is between 34359738368 and 68719476735 by a random totalm (p-1 * Q-1 forms). I choose random d and e. I am coding a number and showing that in the UI.
For the purposes of the argument, assume that the user can see up to 1000 of these outputs. Could he use some algorithms like Polla or something similar to crack my d, e or n and thus start predicting new numbers? If so, how hard is it? (Just knowing that 1000 sets of I / O)
As an example (consider 6 outputs as a sample in I / O format),
- 10001621865,31116156015
- 10001621866,33031668326
- 10001621867,37351399313
- 10001621868,06071714212
- 10001621869,01188523761
- 10001621870,18341011998
Can someone tell me what my n, d, e are? (N between 34359738368 and 68719476735)
I just want to know how hacky it is, so if you could give me any information on how long, how fast, how many outputs need to be seen, what algorithms can be used, etc. It will be great.
PS: User does not see "e" as standard RSA algorithm. He can only see sets of outputs.
ADDED DETAILS I am trying to present the user-id from db to the user. Since it is sequential, I don't want the user to guess a different user ID while doing multiple registrations. To avoid this, I have to scramble it to a number <= 12 digits. There were many limitations around this which have been explained in this question .
Also the meaning of n, d and e is unknown to the user. Maximum user can see multiple I / O samples (by re-registering)
Accepting the answer posted by Accipitridae because the Jacobi algorithm can be used to crack in a matter of seconds. Without knowing n, e or p.
a source to share
An attacker can guess the coefficient p from n and e mod (p-1). Each guess can be tested by accepting message m, calculating m ^ e mod p, and then comparing with c mod p, where c is the corresponding ciphertext. Since p and e mod (p-1) can be 20 bits each, this means that the security of the circuit does not exceed 40 bits.
But 40 bits is a very rough upper bound. An attacker can do much better. For example, he can guess the factor p. It then calculates the Jacobi characters of messages and ciphertexts. If message m is a quadratic residue mod p, then the ciphertext must be a quadratic residue mod p and vice versa. Hence, if this relationship is not satisfied for the message / ciphertext pair, it may reject the assumption for p. Or an attacker could compute discrete logarithms between the message and the ciphertext. This gives a much faster candidate for e mod (p-1).
This should provide a security level of 20-30 bits, so it takes a few seconds to break. If you increase the number of samples to 20 I can try some tests.
Update: . Since you didn't give me 20 samples to run the experiment, I had to generate them myself. With the following samples
m = 10001621865 c = 31116156015
m = 10001621866 c = 33031668326
m = 10001621867 c = 37351399313
m = 10001621868 c = 6071714212
m = 10001621869 c = 1188523761
m = 10001621870 c = 18341011998
m = 10001621871 c = 7620400191
m = 10001621872 c = 36106912203
m = 10001621873 c = 37615263725
m = 10001621874 c = 7795237418
m = 10001621875 c = 34774459868
m = 10001621876 c = 4555747045
m = 10001621877 c = 33123599635
m = 10001621878 c = 34836418207
m = 10001621879 c = 33962453633
m = 10001621880 c = 6258371439
m = 10001621881 c = 7500991556
m = 10001621882 c = 5071836635
m = 10001621883 c = 911495880
m = 10001621884 c = 39558568485
the algorithm described above detects factors 201821 and 206153 in 20ms. As described, it is not necessary to know e, although your choice of e = 65537 is easy to guess and can be used as well.
The strength of RSA is that it relies on the complexity of factoring large integers. This is where you remove that difficulty, and everything else is all the weaknesses (i.e., Mathematical Relations) of RSA. Building an RSA-based block cipher is a terrible idea. I really don't understand why you don't want to use the Luby-Rackoff construct as I suggested earlier.
a source to share
RSA is vulnerable to Chosen-Ciphertext attack. That is, let's say we want to break the ciphertext y, we can use one of the ciphertext-plaintext pairs to break it.
How to break it:
select x0 and y0 where x0 and y0 is the plaintext-ciphertext pair that was provided.
y1 = y0 * y mod n y1 is another of 1000 ciphertexts presented to the user who meets these criteria. x1 is the decryption of y1, which is also given, this means:
x1 = y1 ^ d mod n (this is given to us, we already know x1)
x1 = (y0 * y) ^ d mod n x1 = y0 ^ d * y ^ d mod n Ξ x0 * x
x1 * x0 ^ -1 = x
x stands for y.
This, of course, depends on whether y0 * y mod n produces another ciphertext that we already have, and since we only have 1000 such pairs, this is unlikely, but not impossible. You just need to choose your pairs carefully.
I would also like to add that the size n you are working with allows the factoring heuristic to find the primary factorization of n quite quickly. In addition, RSA is vulnerable to temporary attacks, but this can easily be thwarted.
Added information: Without knowing n, d, or e, absolutely no information is provided at all, which means guessing combinations of n, d, or e is as good as guessing the plaintext itself. To find n and e, there are at least 43 359 738 367 combinations of n to guess, and all combinations of e could be. It is not easy for someone, even with 1000 ciphertext and plaintext pairs, to be able to crack n and e.
a source to share
Is this a terrible idea, 36 bit RSA ?? Why not just go with a block or stream cipher? This way you get 1: 1 mapping and in a much safer way.
An alternative solution that I would recommend would be to use the SHA hash as the UID and store the sequential number for each user in the database as a separate column.
a source to share