Cracking a N bit RSA modulo numbers

Question

This is related to my previous post, where my only option was to have a RSA algorithm which seemed relatively weak. Let us assume that I want to encode a 35 bit number (From 0 upto 34359738367) with a 36 bit modulo (between 34359738368 upto 68719476735).

Referring to http://en.wikipedia.org/wiki/RSA I can see that my n is between 34359738368 upto 68719476735 a random totient (of the form p-1 * q-1). I pick a random d and e. I encode a number and show that on the UI.

For the purpose of argument let us assume that a user can see upto 1,000 such outputs. Can he use some algorithms like Polla's or anything of the like to crack my d,e or n and thereby start predicting new numbers? If so how hard is it going to be ? (By just knowing say 1000 sets of inputs/outputs)

As an example (consider 6 outputs as sample in input/output format),

1. 10001621865,31116156015
2. 10001621866,33031668326
3. 10001621867,37351399313
4. 10001621868,06071714212
5. 10001621869,01188523761
6. 10001621870,18341011998

Can someone tell me what my n, d, e was? (N between 34359738368 upto 68719476735)

I simply want to know how crackable it is, so if you could give me any information on how long, how fast, how many outputs does one has to see, what algorithms can one use etc. It will be great.

PS: User does not see the "e" like the standard RSA algorithm. He can only see the input output sets.

DETAILS ADDED I am trying to present a sequential user-id from db to the user. Because it is sequential I dont want a user to guess another user's id by doing a few registrations. To avoid this I have to scramble it to a <= 12 digit number. There were lot of constraints around this which were explained in this question .

Also the value of n,d and e is not known to the user. The maximum a user can see is a few input ouput samples (by way of registering repeatedly)

Accepting the answer posted by Accipitridae since the "Jacobi" algorithm can be used to crack this in a matter of few seconds. Without knowing n, e or p.

Answer 1

RSA is vulnerable against a Chosen-Ciphertext attack. That is, say we want to break ciphertext y, we can use one of the ciphertext-plaintext pairs to break it.

How to break it:

choose an x0 and y0, where x0 and y0 is a plaintext-ciphertext pair that has been provided.

y1 = y0*y mod n y1 is another one of the 1000 ciphertexts given to the user that satisfies this criteria. x1 is the decryption of y1, which is also given, this means:

x1 = y1^d mod n (this has been 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 is the decryption of y.

This is of course dependent on whether or not y0*y mod n produces another ciphertext that we already have, and since we have only 1000 such pairs to work with, it is unlikely but not unfeasible to break. You just have to choose your pairs extremely carefully.

I'd also like to add that the size of n you're working with allows a factoring heuristic to find the prime factorization of n fairly quickly. Also, RSA is vulnerable to timing attacks, but that can be easily thwarted.

With added info: Without knowing n, d, or e, there is absolutely no information 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 as well as all of the combinations e could be. It's not easy for someone even with 1000 ciphertext-plaintext pairs to be able to crack n and e.

Answer 2

An attacker can guess a factor p of n and e mod (p-1). Each guess can be checked by taking a message m, computing m^e mod p and then comparing with c mod p, where c is the corresponding ciphertext. Since p and e mod (p-1) are maybe 20 bits each, this means that the security of the scheme is not larger than 40 bits.

But 40 bits is only a very crude upper bound. An attacker can do much better. For example he can guess a factor p. Then he computes the Jacobi symbols of the messages and ciphertexts. If a message m is a quadratic residue mod p then the ciphertext must be a quadratic residue mod p and vice versa. Hence if this relation is not satisfied for a message/ciphertext pair he can reject the guess for p. Or the attacker can compute discrete logarithms between message and ciphertext. This gives a much faster candidate for e mod (p-1).

That should give a security level of 20-30 bits, hence require a few seconds to break. If you extend your number of samples to 20 I might try some benchmarks.

Update: Since you didn't give me 20 samples to run an 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

as input, the algorithm described above finds the factors 201821 and 206153 in 20ms. As described this does not need to know e, although your choice of e=65537 is easy to guess and can be exploited as well.

The strength of RSA is that it is based on the difficulty of factoring large integers. Here you remove this difficulty and what remains are all the weaknesses (i.e. mathematical relations) of RSA. Building a block cipher based on RSA is a horrible idea. I really don't see why you don't want to use a Luby-Rackoff construction as I proposed earlier.

Answer 3

This is a horrible idea, 36 bit RSA?? Why not simply go with a block or stream-cipher? That way you get the 1:1 mapping and in a much securer way.

An alternative solution that I would recommend would be to use a SHA hash as UID and store the sequential number for each user in the database as a separate column.