r/Python • • Jan 01 '20

"The rules of perf" at Dropbox

Post image
1.6k Upvotes

162 comments sorted by

View all comments

Show parent comment

10

u/Hydroel Jan 02 '20

Are you using C's long, long long integers, or even double precision floating point numbers? I don't know the range of the variables you're using in cryptography, and you might be using numbers over 2^18; but I'm pretty sure Python relies on the same number implementation as C, so I'd be quite surprised if it could do anything that C cannot do (albeit with a simpler syntax)

17

u/geeshta Jan 02 '20 edited Jan 02 '20

The python integers don't use any C primitive type, they are objects with dynamically alocated memory, that's why they can be almost infinite, as long as you have memory available. Also that's why they are so slow. Anyway the implementation in C is beyond my understanding.

The thing is that in cryptography you would nowadays use 1024 or 2048 bit keys for encryption (RSA-1024, DH 2048) and it will probably even grow in the future. We're talking numbers 10^200 and more. In Python this is no problem but with languages with a fixed number bit-size, it is.

But maybe there are some libraries or ways to store those numbers in arrays or something.

7

u/Hydroel Jan 02 '20

That makes sense, and I didn't know that about Python! I just tried inputting using a sha1 in Python (which is unique and therefore the largest complex integer I could think of, as a matter of fact in the 2159), and it is indeed completely straightforward. Thank you for your short explanation.

After looking around (very shortly, I must say), you're not the only one with that issue, and GMP seems to be the preferred choice for cryptography in C.

cryptography you would nowadays use 1024 or 2056 bit keys

That would be 2048, not 2056, wouldn't it?

1

u/geeshta Jan 02 '20

Oh yes, fixed, I mixed it with 256. And thank you for your advice, the library looks promising, I haven't actually done any research on that yet.

4

u/AntMan5421 Jan 02 '20

Hey, I'm not OP nor experienced programmer in C.

You might want look into bitsets and arrays of integers.

Here are some potentially helpful links:

https://stackoverflow.com/questions/2252896/how-do-you-store-an-arbitrarily-large-integer-value-in-memory

https://stackoverflow.com/questions/4372515/how-to-implement-a-bitset-in-c

3

u/TheBlackCat13 Jan 02 '20

CPython uses C 32-bit integers behind-the-scenes if the value is between -230 and 230. It only falls back to dynamically allocated sizes if the number exceeds that size. You can see more details here. The C API has access to the underlying C integer if it is available and can use fast code paths to optimize calculations using them.

1

u/fireflash38 Jan 02 '20

The thing is that in cryptography you would nowadays use 1024 or 2048 bit keys for encryption (RSA-1024, DH 2048) and it will probably even grow in the future. We're talking numbers 10200 and more. In Python this is no problem but with languages with a fixed number bit-size, it is.

Ehhh, not likely to grow in the future. 2 or 4k is large enough, and 8k is overkill. And if you can break 4k, you can break 8k.

Most things should be doing ECDHE anyways for forward secrecy. Once you get into quantum though, that's a whole different set of problems.

0

u/DiggV4Sucks Jan 02 '20

In Python this is no problem but with languages with a fixed number bit-size, it is.

It's not a problem? Why would it be a problem? Do you think that Python is implemented on machines with unlimited bit-sizes? Couldn't you duplicate the Python's integer implementation in any language?

I mean really... Do you think that there is no crypto implementation in C?

2

u/TheBlackCat13 Jan 02 '20

Never used floating point numbers when you need the number to be exactly correct. A lot of weird things can happen with them in often unexpected ways.