Jump to content

# [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

Look at GMP bindings for Python. Something like this.

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

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
• ### Recently Browsing   0 members

• No registered users viewing this page.
×

• #### Activity

• Leaderboard
×
• Create New...