Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen
Читать онлайн книгу.Key Cryptography and RSA on a Calculator
We now turn to some examples of asymmetric or public key cryptography. First, let us explain RSA, the main public key algorithm. As before, A wants to send a secret message to B. For convenience, let us think of
as being the number 6, say, as in our previous example. We make the encryption more complicated. So instead of saying “add 7,” we say “multiply 6 by itself 7 times” i.e. calculate
. As an extra complication, let us take some number
and declare the encryption algorithm to be “multiply 6 by itself 7 times and take the remainder of this number when divided by
to be the cipher text
.” As a small working example, let
. So our cipher text is the remainder of
upon division by 55. This remainder is easily calculated, using any calculator, as follows:
We want to find the (unique) remainder that is left over when we divide 279 936 by 55. So we have
where is one of
. We are not really interested in the value of
: we just need
. Dividing across by 55 in Eq. (3.5), we get
(3.6)
Pushing the divide button on the calculator, we get
(3.7)
This indicates that is
so
. This is not what we were hoping for:
is supposed to be a whole number, namely the remainder when 279936 is divided by 55! However, the calculator has made rounding errors, and we suspect that
is 41 (and
is 5089). This is easily checked. We can verify that Eq. (3.5) checks out with
,
since
.
Principle 1 To calculate the remainder of 279936 when divided by 55, perform the division on a calculator and multiply the decimal part by 55. Verify your answer by checking that Eq. (3.5) is satisfied. This also works to get the remainder whenever we divide a positive integer (= positive whole number) by another positive integer
.
Question
How do we know that is unique? Maybe there are two possible values?
Go back to Eq. (3.5), and suppose we have two solutions with being positive and
and
both lying between 0 and 54. So we have
(3.8)
(3.9)
Then . Now, if
it follows that
. So assume that
. Call the larger one
, so
.
We now have . Since
is at least 1 bigger than
, we get that the left side is at least 55. Since
and
are between 0 and 54, we see that the right side is at most 54. Since
, we conclude that the assumption
leads