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.

Am not a mathematician.

Every crypto specification I see uses the modulo operation. For example RSA -

If $e$ is the public key and $m$ is the plaintext with a modulus $n$ - the cipher text is $c = m^{e} \bmod n$

Why is this $\bmod\ n$ there? By definition isn't the modulo operation introduces an uncertainty? I mean $3 \bmod 7 = 10 \bmod 7 = 3$.

Is it the idea to limit the result to a group? Why is there no uncertainty about the result?

share|improve this question

1 Answer 1

Is it the idea to limit the result to a group?

Yes. The advantage to doing so is that we have multiplicative inverses (well, for anything relatively prime to $n$) and can therefore decrypt. It also keeps ciphertexts relatively small.

Why is there no uncertainty about the result?

There would be, except we require require plaintexts to be smaller than the modulous (i.e., part of the group). In your example, we wouldn't allow 10 to be a plaintext, because 10 is greater than 7, the modulous.

So how do you encrypt long messages? Normally, the only thing you encrypt using RSA is a symmetric key, and then encrypt your actual message using the symmetric key. Since symmetric keys are significantly shorter than RSA moduli, this isn't an issue.

We would also like to sign long messages with RSA. Therefore we typically hash the message to a digest that's shorter than the modulous, and then sign the digest. This also improves performance and stops attackers from exploiting the fact that RSA encryption is a homomorphism to forge signatures.

share|improve this answer
    
Thanks! As a follow up - In the wiki page for RSA in the section Attacks against RSA the first point says that a vulnerability exists if the cipher text is smaller than the modulus n. Why is that a vulnerability when we are trying to make everything less than modulus n? –  user220201 May 15 at 6:52
    
@Seth The multiplication modulo $n$ in RSA is in the ring $Z_n$. Messages are not limited to those who have multiplicative inverses and thus are in the multiplicative group $Z_n^*$. –  DrLecter May 15 at 6:52
1  
@user220201 The vulnerability is only a problem if the plaintext is much smaller than the modulus, for example if the plaintext is 128 bits long with a 2048 bits modulus. In practice, padding schèmes are used to ensure that the plaintext is only slightly smaller than the modulus. –  fkraiem May 15 at 8:09
1  
@user220201 This is when, e.g. using $e = 3$, we have $m < n^{1/3}$, in which case $c$ is literally $m^3$ and you can just take the cube root in the integers and decrypt the ciphertext using only public information. If $m > n^{1/3}$, then we only know that $c + kn$ is a perfect cube for some integer $k$, but this $k$ becomes very, very large on average as $m$ increases (with a very complicated distribution), making it impossible to brute force it without knowing the factors of $n$ (or so we believe). –  Thomas May 15 at 11:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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