Prev: intolerant HTML parser
Next: how to fix bugs (python)
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 <st...(a)holdenweb.com> 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" <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 parser
Next: how to fix bugs (python)