1
$\begingroup$

Consider a public modulus that is supposedly 4096 bits. But since it contains two hex pairs of zeroes, i.e. ...:00:...:00... such that the bit length of the decimal value instead becomes 4093 bits, is it actually a 4096 bit key or not?

I hope my question is vaguely intelligible.

Edit: modulus is here https://pastebin.com/adYe0F7g The reason for my (stupid) question is that I was told it would have the size of 4096 bits, but when I do what I see many do in for example Python to calculate the bit length -> int(hexN, 16).bit_length() it turns out to be 4093.

$\endgroup$
  • $\begingroup$ Are you saying that the 2 most significant bytes are 0, or just there happen to be multiple zero substrings in places other than the most significant place? Also, why are your bringing up the decimal representation of the value? $\endgroup$ – Ken Goss Feb 1 at 3:51
  • 1
    $\begingroup$ What's "the bit length of the decimal value" of an integer? How is 4093 obtained from 4096 and "two hex pairs of zeroes", that is 16 bits? Is "the private modulus" really the public modulus $N$ in an RSA public key $(N,e)$? If so; yes, $N$ may contain zeroes, in binary, hex, and decimal; and it is expected that it does so to some degree. By convention, the RSA key size is the bit size of $N$, that is the integer $k$ such that $2^{k-1}\le N<2^k$. I may turn this into an answer if the question becomes clear. $\endgroup$ – fgrieu Feb 1 at 7:25
1
$\begingroup$

The pastebin contains $512$ two-character hex values, starting with 18: and ending in :4d. That is $512\times8=4096$ bits.

When interpreted as a big-ending integer, that forms a $N$ of $4093$ bits, per the definition of that in cryptography: a positive $N$ has $k$ bits when $2^{k-1}\le N<2^k$. One way to compute this: the first byte 18 in hex is 00011000 in binary, thus is an $8$-bit bitstring starting with $3$ leading zero bits before the first one bit, thus is a $8-3=5$-bit integer; then whatever the value of the next $511$ bytes (including 00), these bytes add $511\times 8=4088$, for $4088+5=4093$.

There are reasons to believe this is how $N$ is intended to be understood, and that $N$ is in fact the public modulus of some RSA key: the resulting integer is composite, but has no small prime factors. That's rare for a random integer that size.

In RSA as standardized, the key size / security level usually is defined as the bit size the public modulus $N$. But it is not uncommon that $N$ is actually a few bits smaller than advertised, as seen here. Not all implementations and standards allow that, thought.

$\endgroup$
3
$\begingroup$

There is no such thing as a "private modulus". There are the secret primes and the secret exponent, and there is the public modulus. Assuming you are talking about the primes or the secret exponent, are these bits in the most significant (leftmost) position, or are they somewhere in the middle or end? If they are in the most significant position, then they do not count towards the size of the integer. After all, any finite integer at all can be thought of as having an infinite number of leading zeros! If the zeros are somewhere within the integer, they serve to change its value. A random integer is expected to have a few null bytes.

Think about it this way: there is no difference between 0123 and 00123 (both are the same number), but there is a big ten-fold difference between 1230 and 12300, despite both adding a single zero. Of course this is base 10 whereas hex is base 16, but the principle is the same and zero means the same thing.

You can easily calculate the size of your key by taking the ceiling of the binary logarithm of the public modulus. That is, you can calculate $\lceil\log_2(N)\rceil$ for an integer representation of the public modulus $N$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.