[Python] Handeling big numbers

Recommended Posts

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!

Share on other sites

@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.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.