Remix.run Logo
kangalioo 2 days ago

But what's wrong with sending the number as a string? `"65537"` instead of `"AQAB"`

comex 2 days ago | parent | next [-]

The question is how best to send the modulus, which is a much larger integer. For the reasons below, I'd argue that base64 is better. And if you're sending the modulus in base64, you may as well use the same approach for the exponent sent along with it.

For RSA-4096, the modulus is 4096 bits = 512 bytes in binary, which (for my test key) is 684 characters in base64 or 1233 characters in decimal. So the base64 version is much smaller.

Base64 is also more efficient to deal with. An RSA implementation will typically work with the numbers in binary form, so for the base64 encoding you just need to convert the bytes, which is a simple O(n) transformation. Converting the number between binary and decimal, on the other hand, is O(n^2) if done naively, or O(some complicated expression bigger than n log n) if done optimally.

Besides computational complexity, there's also implementation complexity. Base conversion is an algorithm that you normally don't have to implement as part of an RSA implementation. You might argue that it's not hard to find some library to do base conversion for you. Some programming languages even have built-in bigint types. But you typically want to avoid using general-purpose bigint implementations for cryptography. You want to stick to cryptographic libraries, which typically aim to make all operations constant-time to avoid timing side channels. Indeed, the apparent ease-of-use of decimal would arguably be a bad thing since it would encourage implementors to just use a standard bigint type to carry the values around.

You could argue that the same concern applies to base64, but it should be relatively safe to use a naive implementation of base64, since it's going to be a straightforward linear scan over the bytes with less room for timing side channels (though not none).

nssnsjsjsjs a day ago | parent [-]

Ah OK so: readable, efficient, consistent; pick 2.

shiandow a day ago | parent | prev | next [-]

Converting large integers to decimal is nontrivial, especially when you don't trust languages to handle large numbers.

Why you wouldn't just use the hexadecimal that everyone else seems to use I don't know. There seems to be a rather arbitrary cutoff where people prefer base64 to hexadecimal.

red_admiral a day ago | parent | prev | next [-]

This sounds like an XY problem to me. There is already an alternative that is at least as secure and only requires a single base-64 string: Ed25519.

deepsun a day ago | parent | prev | next [-]

PHP (at least old versions I worked with) treats "65537" and 65537 similarly.

red_admiral a day ago | parent [-]

That sounds horrible if you want to transmit a base64 string where the length is a multiple of 3 and for some cursed reason there's no letters or special characters involved. If "7777777777777777" is your encoded string because you're sending a string of periods encoded in BCD, you're going to have a fun time. Perhaps that's karma for doing something braindead in the first place though.

foobiekr 2 days ago | parent | prev | next [-]

Cost.

ayende 2 days ago | parent | prev [-]

Too likely that this would not work because silent conversion to number along the way

iforgotpassword 2 days ago | parent [-]

Then just prefixing it with an underscore or any random letter would've been fine but of course base64 encoding the binary representation in base 64 makes you look so much smarter.