mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-06-13, 13:02   #1
D2MAC
 
Jun 2010

48 Posts
Question 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?
D2MAC is offline   Reply With Quote
Old 2010-06-13, 13:17   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24·13·53 Posts
Default

Quote:
Originally Posted by D2MAC View Post
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
xilman is offline   Reply With Quote
Old 2010-06-13, 14:36   #3
D2MAC
 
Jun 2010

22 Posts
Default

Quote:
Originally Posted by xilman View Post
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
D2MAC is offline   Reply With Quote
Old 2010-06-13, 14:42   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×11×23 Posts
Default

Quote:
Originally Posted by D2MAC View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2010-06-13, 16:47   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

24·13·53 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
xilman is offline   Reply With Quote
Old 2010-06-13, 22:00   #6
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-06-13, 22:23   #7
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

32×13×19 Posts
Default

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
So it took all of 1.607 seconds to do the calculation, resulting in a 10.1 million digit number.
frmky is offline   Reply With Quote
Old 2010-06-15, 19:29   #8
D2MAC
 
Jun 2010

22 Posts
Default

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.
D2MAC is offline   Reply With Quote
Old 2010-12-26, 16:32   #9
Laam
 

32·11·83 Posts
Default

Quote:
Originally Posted by D2MAC View Post
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.
  Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modulus function on a linear convolution lukerichards Number Theory Discussion Group 4 2018-04-06 12:57
Extracting the Modulus from publickeyblob RSA 512 26B Homework Help 2 2014-11-30 07:31
Factorization of a 768-bit RSA modulus akruppa Factoring 53 2010-03-12 13:50
Fixed leading bits in RSA modulus, vs NFS fgrieu Factoring 7 2009-09-23 11:45
Factoring with Highly Composite Modulus 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.