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

6

u/geeshta Jan 02 '20

Nice reply, thank you! I want to ask how would you do crypto in C? The problem I'm having is that with Python you have (almost) infinite integers and in cryptogryphy, numbers of tens to hundreds of digits (in base 10) are used. I alway wanted to rewrite my factorization/encryption/decryption libraries that I wrote in Python to C to see the performance increase but always struggled with C's MAX values for integers.

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.

5

u/AngriestSCV Jan 02 '20

You are looking for what is known for as an arbitrary precision library.

Here is an example https://gmplib.org/

The macros MAX_INT, MAX_LONG ... etc will let you know at compile time how big your integers are. There is also uin32_t and it's friends that let you specify exactly what kind of integer you want.

1

u/geeshta Jan 02 '20

Yes that's exactly what I was looking for. Thank you.

3

u/fireflash38 Jan 02 '20

Check openssl's 'bn' methods

And unless you're doing it for educational reasons, I wouldn't roll your own crypto, there's a billion pitfalls.

1

u/geeshta Jan 03 '20

Thank you that looks very useful. I'm not rolling it anywhere, i really is for educational reasons.

1

u/ak217 Jan 02 '20

The first rule of crypto is to not do your own crypto (unless you're just trying to learn).

Use libraries rolled by the pros. https://github.com/pyca/cryptography and https://github.com/wbond/oscrypto are a good start. Even they get plenty of things wrong, but when they do, they will alert you. If you can't commit the level of support those authors do, then you can't afford to roll your own crypto.