Efficient (HUGE) prime modulus

[Tim Roberts]

blaine <frikker at gmail.com> wrote:
>
>  For my Network Security class we are designing a project that will,
>among other things, implement a Diffie Hellman secret key exchange.
>The rest of the class is doing Java, while myself and a classmate are
>using Python (as proof of concept).  I am having problems though with
>crunching huge numbers required for calculations.  As an alternative I
>can use Java - but I'd rather have a pure python implementation.  The
>problem is that Python takes a very long time (I haven't had it finish
>yet)

And it won't.  Ever.  Well, actually, it will finish when it crashes.

>...
>    G =
>long(2333938645766150615511255943169694097469294538730577330470365230748185729160097289200390738424346682521059501689463393405180773510126708477896062227281603)
>    P =
>long(7897383601534681724700886135766287333879367007236994792380151951185032550914983506148400098806010880449684316518296830583436041101740143835597057941064647)
>
>    a = self.rand_long(1) # 512 bit long integer
>
>    A = (G ** a) % P # G^a mod P
>
>###### END #####
>The above code takes a very long time.

We all know the proper answer (use 3-arg math.pow).  However, Paul Rubin's
suggested to figure out how large (G ** a) prompted me to go do just that.
That expression is not computable on any computer on Earth today.  It is a
number requiring 7 x 10**156 bits.  Consider that a terabyte hard disk
today only includes 9 x 10**12 bits.  Also consider that, by rough
estimate, there are approximately 10**80 atoms in the known universe
today...
-- 
Tim Roberts, timr at probo.com
Providenza & Boekelheide, Inc.