[Python] Handeling big numbers

[whitenoise]

Hey,

I'm trying to code some crypto stuff. I don't just want to simulate an algorithm but want to use numbers that are used in practice.

During the calculations of a Diffie Hellman key exchange some large numbers have to be processed. There is a prime number with >2048 bits and a base with an exponent, where the exponent should have a size of around 160-256 bits.

At the moment I'm having problems with finding the right data types for this big numbers. If I just try to calculate something like (p is not a prime here):

p=123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789

b=2

x=987654321987654321987654321

A=b**x mod p

Here for testing:

#!/usr/bin/env python
#-*- coding: utf-8 -*-

p=123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789

b=2

x=987654321987654321987654321

A=b**x % p

print A

I run into a memory problem (MemoryError). Converting the int's to long does not help, using Decimal() does not help either.

I was trying to use the datatypes of numpy (see here) but I get

OverflowError: Python int too large to convert to C long

Has anyone experience in handling such big numbers and doing arithmetics with them in python? I mean .. DH key exchange is something my browser does a hundreds time a day and it never told me it is out of memory so I guess there has to be a trick ;)

Cheers!

[cooper]

Look at GMP bindings for Python. Something like this.

[whitenoise]

@cooper: I just found another solution ;)

Dealing with such big numbers in the method above takes too much memory. However, the problem can be solved with a for-loop by what is called Modular Exponentiation.

Python has a built-in function called pow(), which does modular exponentiation and can take up to three arguments (base, exponent and optional a modulo parameter).

If you substitute:

A=b**x % p

by

A=pow(b,x,p)

A=67106303645408219781140727427280612111960487935201208302504831122113989347565507978724914118463849388439348417955712740781306188779036136994829742272005372145131781890427605537882

That's the way Diffie Hellman is calculated.