It's possible to calculate an unknown RSA modulus?

[D2MAC]

Hello.
Maybe I have some interesting problem.
From the equation:
M = C^E MOD N,
I know M, C and E, but unfortunately I don't know the public RSA modulus N and want to calculate it. However, without of computing the term C^E, because C is in 512bit size and E is 10001 hex.
I also can generate many different pairs M_x and C_x for the same N, I want to calculate, but I have only limited control of what will be generated.
Meaning, I can't for example generate such C_x and C_y, which fulfils the condition C_x = 2*C_y or similar. But, of course, I can generate such C_x and C_y with "not very large" common factor.

M₁ = C₁^E MOD N
M₂ = C₂^E MOD N
M₃ = C₃^E MOD N
.
.
.
M_n = C_n^E MOD N

What I know about the unknown public RSA modulus is, that it is in 512bit size (128 hex letters) and I also know the MSB of it.

What is the best and quickest way to calculate the public modulus?
Any ideas?

[xilman]

Originally Posted by D2MAC

Hello.
Maybe I have some interesting problem.
From the equation:
M = C^E MOD N,
I know M, C and E, but unfortunately I don't know the public RSA modulus N and want to calculate it. However, without of computing the term C^E, because C is in 512bit size and E is 10001 hex.
I also can generate many different pairs M_x and C_x for the same N, I want to calculate, but I have only limited control of what will be generated.
Meaning, I can't for example generate such C_x and C_y, which fulfils the condition C_x = 2*C_y or similar. But, of course, I can generate such C_x and C_y with "not very large" common factor.

M₁ = C₁^E MOD N
M₂ = C₂^E MOD N
M₃ = C₃^E MOD N
.
.
.
M_n = C_n^E MOD N

What I know about the unknown public RSA modulus is, that it is in 512bit size (128 hex letters) and I also know the MSB of it.

What is the best and quickest way to calculate the public modulus?
Any ideas?

Black-box attack on a RSA-cryptosystem, eh?

Let's do a deal. You tell us which particular implementation you are attacking and, in return, we'll give you guidance on how to approach your problem.

Paul

[D2MAC]

Originally Posted by xilman

Black-box attack on a RSA-cryptosystem, eh?

Let's do a deal. You tell us which particular implementation you are attacking and, in return, we'll give you guidance on how to approach your problem.

Paul

More or less, yes.
I was trying to read out this key from one of the blocked directories of old unsafe version of cryptoworks smartcards, which has been withdrawn from the market few years ago. It is no longer active and even if I get and publish this key, nothing will happen, because this key is unique for each card and the card isn't active, as I have said before. Today's cryptoworks cards have completely different system of data protection and reading out of any keys is no longer possible.
The worth of this key for me is in the possibility of testing some new instructions for the old card and learn something more about this system of data protection, which will not be possible without the unique key. However, I was not successful with the out-reading procedure, so I am trying to calculate it from the known data and that's it, what is this thread all about.

[R. Gerbicz]

Originally Posted by D2MAC

Hello.
Maybe I have some interesting problem.
From the equation:
M = C^E MOD N,
I know M, C and E, but unfortunately I don't know the public RSA modulus N and want to calculate it. However, without of computing the term C^E, because C is in 512bit size and E is 10001 hex.
I also can generate many different pairs M_x and C_x for the same N, I want to calculate, but I have only limited control of what will be generated.
Meaning, I can't for example generate such C_x and C_y, which fulfils the condition C_x = 2*C_y or similar. But, of course, I can generate such C_x and C_y with "not very large" common factor.

M₁ = C₁^E MOD N
M₂ = C₂^E MOD N
M₃ = C₃^E MOD N
.
.
.
M_n = C_n^E MOD N

What I know about the unknown public RSA modulus is, that it is in 512bit size (128 hex letters) and I also know the MSB of it.

What is the best and quickest way to calculate the public modulus?
Any ideas?

N divides M-C^E. So let G=gcd(M_1-C_1^E_1,...) then N divides G.

[xilman]

Originally Posted by R. Gerbicz

N divides M-C^E. So let G=gcd(M_1-C_1^E_1,...) then N divides G.

Unfortunately, he doesn't want to calculate C^E to full precision.

We should examine that requirement to see whether it is reasonable.

However, without of computing the term C^E, because C is in 512bit size and E is 10001 hex.

Assume the worst case, where C=2^512. E=10001 hex. According to bc(1) 0x10001 * log_2 (2^512) = 0x2000200. Such a number takes 0xAAAB56 bytes to represent.

Converting back to decimal because that's what most of us find comfortable, the maximum size of C^E is 11184982 bytes, or something over 11M bytes. By the standards of GMP that is a medium sized number and easily computable in a short time.

Suggestion: drop the prohibition on calculating C^E and go for the straightforward approach.

Paul

[Random Poster]

Originally Posted by xilman

Assume the worst case, where C=2^512. E=10001 hex. According to bc(1) 0x10001 * log_2 (2^512) = 0x2000200. Such a number takes 0xAAAB56 bytes to represent.

It takes that many bytes if converted to a string of decimal digits, but that would be completely pointless, since the only purpose of this number is to take its GCD with another number of the same form, and you can do that in the same program which you use to compute the number in the first place. In its binary format, the number takes just 0x400040 bytes, a fraction over 4 MB.

[frmky]

Enough talking about it, just try it! In Mathematica,

In[1]:= e = 65537
Out[1]= 65537
In[2]:= c = 2^512 - 12873641987236333198276;
In[3]:= n = c^e; // Timing
Out[3]= {1.607, Null}
In[4]:= Log[10, n] // N
Out[4]= 1.0101*10^7

So it took all of 1.607 seconds to do the calculation, resulting in a 10.1 million digit number.

[D2MAC]

Thank You very much for good advices. I was little worried about the huge size of the expression C^E, but as you have predicted, my worries were pointless. Using Mathematica, it finally worked. The exponentiation procedure took little over one second and the final GCD step took about one minute, resulting in a multiple of the searched key. After partial factorization I finally got to the unique modulus.

Originally Posted by D2MAC

More or less, yes.

For MOSCing CW cards and reading keys from EMM which are crypted in C8 nano for particular provider , which is using nano C8 ...

Good Deal in Europe.


/these words are a better describing your interest about RSA/

J.L.