whitenoise Posted December 11, 2015 Share Posted December 11, 2015 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! Quote Link to comment Share on other sites More sharing options...

cooper Posted December 11, 2015 Share Posted December 11, 2015 Look at GMP bindings for Python. Something like this. Quote Link to comment Share on other sites More sharing options...

whitenoise Posted December 12, 2015 Author Share Posted December 12, 2015 @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. Quote Link to comment Share on other sites More sharing options...

## Recommended Posts

## Join the conversation

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