Cryptography Reference
In-Depth Information
We proceed in reverse order for decryption:
1. We divide the ciphertext into
N
-bit blocks.
2. For each ciphertext block with numerical value
c
, we calculate the
remainder,
c
d
, from division by
n
. This produces a plaintext block with
a length of
N
−
1 bits (we delete the first bit — it has to be 0; otherwise,
there is an error).
We can easily see that RSA is slow: multiplications and calculating remainders
take time with 1000-bit numbers.
How to Create a Key
One question that has remained unanswered so far is very important for the
method's security and speed: how do we find such huge prime numbers? You
probably know Eratosthenes' sieve, the simplest method to compute prime
numbers.
We write down all numbers, e.g., up to 1000, beginning with 2:
23456789101112131415...
We delete all multiples of the first number (which is 2), except that number
itself:
2
3
5
7
9
11
13
15
The smallest number greater than 2 is 3; that's the next prime number. We
delete all multiples of 3, except 3 itself:
2
3
5
7
11
13
Now we look for the smallest number greater than 3 that's still left, and so
on. The method works like a sieve: only prime numbers are caught. This is
very effective, for example, if you want to calculate
all
prime numbers up to
