From: hzhuo1 on 7 Feb 2010 10:08 > > And I really don't see how simple enumeration of range(2^2048) breaks > RSA-2048, since that problem requires you to find two factors which, > when multiplied together, give that specific value. > I can tell you why is that. RSA-2048 has a composite of length less than 2^2048, which is a product of two large primes. So one of its factors cannot exceed 2^2047, and we can treat the multiplication as a computation with constant complexity. So the time complexity of enumerating 2^2048 strings is the same with factoring a composite with length 2^2048 which is the product of two primes. And obviously, whenever we successfully factor the composite, we can calculate the Euler function of it. So that given any public key (n,e), calculating the private key (n,d) is easy. From: Steve Holden on 7 Feb 2010 10:38 hzhuo1(a)gmail.com wrote:>> And I really don't see how simple enumeration of range(2^2048) breaks >> RSA-2048, since that problem requires you to find two factors which, >> when multiplied together, give that specific value. >> > > I can tell you why is that. RSA-2048 has a composite of length less > than 2^2048, which is a product of two large primes. So one of its > factors cannot exceed 2^2047, and we can treat the multiplication as a > computation with constant complexity. So the time complexity of > enumerating 2^2048 strings is the same with factoring a composite with > length 2^2048 which is the product of two primes. > > And obviously, whenever we successfully factor the composite, we can > calculate the Euler function of it. So that given any public key > (n,e), calculating the private key (n,d) is easy. > So all I have to do to break RSA is to count to 2^2048? regards Steve -- Steve Holden +1 571 484 6266 +1 800 494 3119 PyCon is coming! Atlanta, Feb 2010 http://us.pycon.org/ Holden Web LLC http://www.holdenweb.com/ UPCOMING EVENTS: http://holdenweb.eventbrite.com/ From: hzhuo1 on 7 Feb 2010 16:57 That is a method called brute force. According to my computation, 2^2048= 32317006071311007300714876688669951960444102669715484032130345427524655138867890 89319720141152291346368871796092189801949411955915049092109508815238644828312063 08773673009960917501977503896521067960576383840675682767922186426197561618380943 38476170470581645852036305042887575891541065808607552399123930385521914333389668 34242068497478656456949485617603532632205807780565933102619270846031415025859286 41771167259436037184618573575983511523016459044036976132332872312271256847108202 09725157101726931323469678542580656697935045997268352998638215525166389437335543 602135433229604645318478604952148193555853611059596230656L which is a very large number. There are some other algorithms for factoring integers, including Generalized number field sieve. And in quantum computing, there is an algorithm called Shor, which is claimed to be a polynomial algorithm if run under quantum computers. But seems that kind of computers haven't been successfully built, or else RSA and many other security mechanisms based on computation complexity cannot be used any longer. What I need in my application is just to list all expressions that match a particular regex, which I believe will be more efficient to deal with if there is a general function for this purpose. Unfortunately there is not such a function, so I will write my own function to deal with my particular regex, which can be enumerated. Sincerely, Zhuo On Feb 7, 10:38 am, Steve Holden wrote:> hzh...(a)gmail.com wrote: > >> And I really don't see how simple enumeration of range(2^2048) breaks > >> RSA-2048, since that problem requires you to find two factors which, > >> when multiplied together, give that specific value. > > > I can tell you why is that. RSA-2048 has a composite of length less > > than 2^2048, which is a product of two large primes. So one of its > > factors cannot exceed 2^2047, and we can treat the multiplication as a > > computation with constant complexity. So the time complexity of > > enumerating 2^2048 strings is the same with factoring a composite with > > length 2^2048 which is the product of two primes. > > > And obviously, whenever we successfully factor the composite, we can > > calculate the Euler function of it. So that given any public key > > (n,e), calculating the private key (n,d) is easy. > > So all I have to do to break RSA is to count to 2^2048? > > regards >  Steve > -- > Steve Holden           +1 571 484 6266   +1 800 494 3119 > PyCon is coming! Atlanta, Feb 2010  http://us.pycon.org/ > Holden Web LLC                http://www.holdenweb.com/ > UPCOMING EVENTS:        http://holdenweb.eventbrite.com/ From: Steven D'Aprano on 7 Feb 2010 17:07 On Sun, 07 Feb 2010 03:53:49 +0100, Alf P. Steinbach wrote: >> "Given the function hashlib.sha256, enumerate all the possible inputs >> that give the hexadecimal result >> 0a2591aaf3340ad92faecbc5908e74d04b51ee5d2deee78f089f1607570e2e91." > > I tried some "parrot" variants but no dice. :-( Oh, everybody expects parrots! That's not unexpected -- as a clue, I wrote that "the message is predictable for being totally unexpected". The input was "Nobody expects the Spanish Inquisition!", which is another Monty Python catchphrase. -- Steven From: Paul McGuire on 7 Feb 2010 22:11 On Feb 6, 1:36 pm, "hzh...(a)gmail.com" wrote:> Hi, > > I am a fresh man with python. I know there is regular expressions in > Python. What I need is that given a particular regular expression, > output all the matches. For example, given [1|2|3]{2} as the regular > expression, the program should output all 9 matches, i.e., "11 12 13 > 21 22 23 31 32 33". > > Is there any well-written routine in Python or third-party program to > do this? If there isn't, could somebody make some suggestions on how > to write it myself? > > Thanks. > > Zhuo Please check out this example on the pyparsing wiki, invRegex.py: http://pyparsing.wikispaces.com/file/view/invRegex.py. This code implements a generator that returns successive matching strings for the given regex. Running it, I see that you actually have a typo in your example. >>> print list(invert("[1|2|3]{2}")) ['11', '1|', '12', '13', '|1', '||', '|2', '|3', '21', '2|', '22', '23', '31', '3|', '32', '33'] I think you meant either "[123]{2}" or "(1|2|3){2}". >>> print list(invert("[123]{2}")) ['11', '12', '13', '21', '22', '23', '31', '32', '33'] >>> print list(invert("(1|2|3){2}")) ['11', '12', '13', '21', '22', '23', '31', '32', '33'] Of course, as other posters have pointed out, this inverter does not accept regexen with unbounded multiple characters '+' or '*', but '?' and "{min,max}" notation will work. Even '.' is supported, although this can generate a large number of return values. Of course, you'll also have to install pyparsing to get this to work. -- Paul First  |  Prev  |  Next  |  Last Pages: 1 2 3 4 5 Prev: intolerant HTML parserNext: how to fix bugs (python)