 mersenneforum.org > Math It's possible to calculate an unknown RSA modulus?
 Register FAQ Search Today's Posts Mark Forums Read 2010-06-13, 13:02 #1 D2MAC   Jun 2010 48 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 Mx and Cx 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 Cx and Cy, which fulfils the condition Cx = 2*Cy or similar. But, of course, I can generate such Cx and Cy with "not very large" common factor. M1 = C1^E MOD N M2 = C2^E MOD N M3 = C3^E MOD N . . . Mn = Cn^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?   2010-06-13, 13:17   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

24·13·53 Posts Quote:
 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 Mx and Cx 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 Cx and Cy, which fulfils the condition Cx = 2*Cy or similar. But, of course, I can generate such Cx and Cy with "not very large" common factor. M1 = C1^E MOD N M2 = C2^E MOD N M3 = C3^E MOD N . . . Mn = Cn^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   2010-06-13, 14:36   #3
D2MAC

Jun 2010

22 Posts Quote:
 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.

Last fiddled with by D2MAC on 2010-06-13 at 14:37   2010-06-13, 14:42   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts Quote:
 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 Mx and Cx 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 Cx and Cy, which fulfils the condition Cx = 2*Cy or similar. But, of course, I can generate such Cx and Cy with "not very large" common factor. M1 = C1^E MOD N M2 = C2^E MOD N M3 = C3^E MOD N . . . Mn = Cn^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.   2010-06-13, 16:47   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

24·13·53 Posts Quote:
 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.
Quote:
 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   2010-06-13, 22:00   #6
Random Poster

Dec 2008

179 Posts Quote:
 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.   2010-06-13, 22:23 #7 frmky   Jul 2003 So Cal 32×13×19 Posts Enough talking about it, just try it! In Mathematica, Code: In:= e = 65537 Out= 65537 In:= c = 2^512 - 12873641987236333198276; In:= n = c^e; // Timing Out= {1.607, Null} In:= Log[10, n] // N Out= 1.0101*10^7 So it took all of 1.607 seconds to do the calculation, resulting in a 10.1 million digit number.   2010-06-15, 19:29 #8 D2MAC   Jun 2010 22 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.    2010-12-26, 16:32   #9
Laam

32·11·83 Posts Quote:
 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.

J.L. Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post lukerichards Number Theory Discussion Group 4 2018-04-06 12:57 26B Homework Help 2 2014-11-30 07:31 akruppa Factoring 53 2010-03-12 13:50 fgrieu Factoring 7 2009-09-23 11:45 mgb Math 3 2006-09-09 10:35

All times are UTC. The time now is 21:29.

Sun Nov 28 21:29:59 UTC 2021 up 128 days, 15:58, 0 users, load averages: 1.04, 1.26, 1.29