Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

In RSA algorithm, the modulus $n$ should be chosen based on the below condition

$2^{8(k-1)} \leqslant n < 2^{8k}$

Where $k$ is the byte length of the modulus $n$.

for this condition I want the proof with an example.

An example is required for the condition: $2^{8(k-1)} \leqslant n$

what is the purpose of this condition?

share|improve this question
2  
I don't understand the question. These conditions are a mathematical way to describe the statement "the modulus n is 8k bits long". Try representing the numbers in binary, you'll see the conditions imply something about the binary representation of $n$! (hint: it forces one bit of $n$ to be 1...) –  Thomas Sep 11 '12 at 13:01
1  
By the way, did you mean 8k - 1 instead of 8(k - 1) in your inequality? Because the former requires the modulus to be 8k bits long, whereas the latter allows any bit length between 8k - 7 and 8k. –  Thomas Sep 11 '12 at 13:05
add comment

closed as not a real question by Ninefingers, Thomas, Paŭlo Ebermann Sep 30 '12 at 13:27

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

1 Answer

For RSA, we generally count bits rather than bytes; with RSA, we say a modulus is $k$ bits long if $2^{k-1} \le n < 2^k$

There's no proof involved, because it is not a mathematical statement, instead, it is how we define what a $k$ bit modulus is.

Another way of looking at it is if we take the modulus, and count the bits, from the highest bit that is set, and including all the bits below that; if there are $k$ bits there, we say that is a $k$ bit number.

For example, if we consider the number 187; that has the binary expansion:

... 0 0 0 0 1 0 1 1 1 0 1 1

(where there are a potentially unbounded number of 0's that occur to the left). If we start at the highest 1 bit, and start counting there, we end up with 8 bits; hence we would say that 187 is an 8 bit modulus. This is exactly the same as the first definition, as $2^{8-1} \le 187 < 2^8$

Now, in other contexts, we might use a different definition of the 'number of bits long' something is. For example, on a CPU, we might say that a specific register is '32 bits long'. What that means that the specific register can hold $2^{32}$ distinct settings; we can call the value it holds a 32 bit value (even if the value at the moment happens to be 3). This definition is more about the representation of the integer, rather than the integer itself. We don't use this definition with RSA, because modulii in abstract RSA doesn't have any intrinsic representation.

share|improve this answer
add comment

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