20100613, 13:02  #1 
Jun 2010
4_{10} Posts 
It's possible to calculate an unknown RSA modulus?
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_{1} = C_{1}^E MOD N M_{2} = C_{2}^E MOD N M_{3} = C_{3}^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? 
20100613, 13:17  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{4}×3^{2}×73 Posts 
Quote:
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 

20100613, 14:36  #3  
Jun 2010
2^{2} Posts 
Quote:
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 outreading procedure, so I am trying to calculate it from the known data and that's it, what is this thread all about. Last fiddled with by D2MAC on 20100613 at 14:37 

20100613, 14:42  #4  
"Robert Gerbicz"
Oct 2005
Hungary
1,429 Posts 
Quote:


20100613, 16:47  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{4}×3^{2}×73 Posts 
Quote:
We should examine that requirement to see whether it is reasonable. Quote:
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 

20100613, 22:00  #6 
Dec 2008
179 Posts 
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.

20100613, 22:23  #7 
Jul 2003
So Cal
2^{3}×257 Posts 
Enough talking about it, just try it! In Mathematica,
Code:
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 
20100615, 19:29  #8 
Jun 2010
2^{2} Posts 
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.

20101226, 16:32  #9 
1,327 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modulus function on a linear convolution  lukerichards  Number Theory Discussion Group  4  20180406 12:57 
Extracting the Modulus from publickeyblob RSA 512  26B  Homework Help  2  20141130 07:31 
Factorization of a 768bit RSA modulus  akruppa  Factoring  53  20100312 13:50 
Fixed leading bits in RSA modulus, vs NFS  fgrieu  Factoring  7  20090923 11:45 
Factoring with Highly Composite Modulus  mgb  Math  3  20060909 10:35 