Jump to content

[Python] Handeling big numbers


whitenoise
 Share

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!

Link to comment
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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

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

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...