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.

From what I can remember, RSA is something like this:

  • Generate 2 distinct prime numbers $p$ and $q$ that have similar bit length.
  • Compute $n=pq$ and $\phi(n)=(p-1)(q-1)$
  • Compute $e$ such that $1<e<\phi(n)$ and $\gcd(\phi(n),e)=1$. It is optimal for $e$ to be prime
  • Compute $d$ such that $ed\equiv1\pmod{\phi(n)}$
  • To encrypt a message $m$ into cipher $c$, compute $c=m^e\pmod{n}$
  • To decrypt a cipher $c$ into message $m$, compute $m=c^d\pmod{n}$

But for large $m$ values, this does not necesssarily work.

Let me use an example to demonstrate what I mean:

  • Let $p=1999$, $q=2039$, and $e=65537$ (note, all of $p$, $q$ and $e$ are prime)
  • Compute $\displaystyle n=pq=1999\times2039=4075961$
  • Compute $\displaystyle \phi(n)=(p-1)(q-1)=1998\times2038=4071924$
  • Compute $d$ such that $65537d\equiv1\pmod{4071924}$ by solving the Linear Diophantine Equation $\displaystyle 65537x-4071924y=1$

Steps to solve (using a bad implementation of the Extended Euclidean Algorithm)

$\displaystyle 65537\times63-1\times4071924=56907$

$\displaystyle 1\times65537-1\times56907=8630$

$\displaystyle 1\times56907-6\times8630=5127$

$\displaystyle 1\times8630-1\times5127=3503$

$\displaystyle 1\times5127-1\times3503=1624$

$\displaystyle 1\times3503-2\times1624=255$

$\displaystyle 1\times1624-6\times255=94$

$\displaystyle 1\times255-2\times94=67$

$\displaystyle 1\times94-1\times67=27$

$\displaystyle 1\times67-2\times27=13$

$\displaystyle 1\times27-2\times13=1$

Therefore, these things can be substituted:

$\displaystyle 1\times27-2\times(1\times67-2\times27)=5\times27-2\times67=1$

$\displaystyle 5\times(1\times94-1\times67)-2\times67=5\times94-7\times67=1$

$\displaystyle 5\times94-7\times(1\times255-2\times94)=19\times94-7\times255=1$

$\displaystyle 19\times(1\times1624-6\times255)-7\times255=19\times1624-121\times255=1$

$\displaystyle 19\times1624-121\times(1\times3503-2\times1624)=261\times1624-121\times3503=1$

$\displaystyle 261\times(1\times5127-1\times3503)-121\times3503=261\times5127-382\times3503=1$

$\displaystyle 261\times5127-382\times(1\times8630-1\times5127)=643\times5127-382\times8630=1$

$\displaystyle 643\times(1\times56907-6\times8630)-382\times8630=643\times56907-4240\times8630=1$

$\displaystyle 643\times56907-4240\times(1\times65537-1\times56907)=4883\times56907-4240\times65537=1$

$\displaystyle 4883\times(63\times65537-1\times4071924)-4240\times65537=303389\times65537-4883\times4071924=1$

Through calculation, we conclude that $\displaystyle d=303389$ because $\displaystyle 65537\times303389\equiv1\pmod{4071924}$

Example 1

Encryption

Let $m=113$, then, $c\equiv(113^{65537})\pmod{4075961}=3345792$

Decryption

Let $c=3345792$, then, $m\equiv(3345792^{303389})\pmod{4075961}=113$

It works this time! Good!

Example 2:

Encryption

Let $m=33555553$, then, $m\equiv(33555553^{65537})\pmod{4075961}=2621940$

Decryption

Let $c=2621940$, then, $m\equiv(2621940^{303389})\pmod{4075961}=947865$

It does not work this time! What the ----?

Is this message too big to be encrypted? If so, how do we make it smaller?

share|improve this question
    
Yes. $\:$ We encrypt a key. $\;\;\;$ –  Ricky Demer Nov 24 '13 at 5:29
    
In very short: Just imagine $e=d=1$ (not safe, but works functionally). Then encypt:$c= m \mod n$ and then decrypt: $m' = c \mod n$. If your message is larger than the modulus, then $m'$ wont be equal to $m$. In modular arithmetic you can not get a result equal to or greater than the modulus. –  tylo Nov 29 '13 at 10:32

1 Answer 1

up vote 4 down vote accepted

The issue is that we use modular arithmetic. In modular arithmetic, you may view $m \bmod n$ as the remainder of $m$ when divided by $n$. So, for example, $7 \bmod 2 = 1$, also written as $7 \equiv 1 \pmod 2$, because $2(3) + 1 = 7$.

Now consider what you're guaranteed by $m \equiv c^d \pmod n$, the decryption formula for plain RSA. You're guaranteed that $c^d$ is equivalent to the message modulo $n$. You're not guaranteed that it is precisely equal. Now, if the message is smaller than the modulus — if $m < n$ — then by the way we program modular reduction, where we usually give the smallest positive integer modulo $n$ , you're going to get $m$ exactly when you compute $c^d \bmod n$. But if $m>n$, if the message is bigger, you're going to get a smaller integer that is equivalent modulo $n$.

And indeed this is the case with your example. Note that your example message $m = 33555553$ is larger than your example $n = 4075961$. So when you compute $c^d$, you're going to find an equivalent integer modulo $n$, but not exactly the one you wanted.

In this case, you got back $c^d \bmod n = 947865$. But note what happens if you reduce your original message modulo $n$: you get that your original message is equivalent to $c^d \bmod n$.

In summary: if your message is larger than your modulus, you won't get the exact message back when you decrypt. You'll get an equivalent message instead. To avoid this, you can instead encrypt a key used in a symmetric cryptosystem (or any cryptosystem that can handle messages of the length you're wanting). As Ricky Demer linked in his comment, this is sometimes called a hybrid cryptosystem. Once you've done this, you just use the other cryptosystem's key to do all of your encryption for you.

share|improve this answer
    
You are telling me that now this RSA scheme becomes something that encrypts a symmetric key that is less than $n$, and once the cipher is decrypted into the message, that message contains a symmetric key that is used to decrypt the actual thing that you want to keep confidential? –  user2213307 Nov 24 '13 at 6:03
    
@user2213307: Yep, exactly! You use RSA to encrypt a symmetric key, and then the rest of the ciphertext is your actual message encrypted under that symmetric key. –  Reid Nov 24 '13 at 6:09
    
@user2213307: I also should note that a typical symmetric key is somewhere around 128 to 256 bits, whereas a typical RSA key is somewhere around 2048 bits. So that scheme is virtually guaranteed to work. –  Reid Nov 24 '13 at 6:37
    
......"Because $\frac{2^{2048}}{2^{256}}=2^{1792}$ which is a big difference". –  user2213307 Nov 24 '13 at 18:30
    
@user2213307: I'm not sure I understand ... can you elaborate on what you're trying to say? Yes, $2^{2048}$ is huge relative to $2^{256}$. –  Reid Nov 24 '13 at 21:32

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.