Associated Topics || Dr. Math Home || Search Dr. Math

### Public Key Encryption

```
Date: 03/29/99 at 11:32:27
From: Jonathan Crowell
Subject: Public Key Encryption

I have been given a mathematics assignment in my computer science
course. The assignment is to write a public key encryption program. I
have been doing some research into public key encryption, but most of
what I have found is very technical and difficult to understand.

My basic question is this: if someone encrypts a message to me using
my public key, why is it not possible for someone else, who also knows
what my public key is, to decrypt the message by simply running my
public key encryption algorithm in reverse?

Also, could you please explain exactly how the "mod" function works?
but I do not yet have a clear understanding.

Thanks.
```

```
Date: 03/29/99 at 12:27:43
From: Doctor Rob
Subject: Re: Public Key Encryption

The "mod" function can be defined as follows: To compute x (mod n),
divide x by n, throw away the quotient, and the remainder is the
answer. If you do the division correctly, the remainder should be in
the range from 0 to n - 1.

The trick with public key encryption is to make it virtually
impossible for someone who knows the encryption algorithm to figure
out a decryption algorithm. There are various ways to do that, based
on the idea that it may be easy to do some operation, but hard to undo
it.

One such operation is multiplying together two large prime numbers.
This is easy. Now, given the product, to find those prime factors is
hard. You cannot just "run in reverse" the multiplication! If you think
you can, try finding the two prime factors of 247925393283219413785644419.

Another such operation is raising a public number to a private power
mod(a public number): g^x = y (mod n), where g, n, and y are known,
but x is not. If you think this is easy, find x in the equation

2^x = 2094218297454 (mod 2103532971451).

Another such operation is raising a private number to a public power
mod(a public number): x^e = y (mod n), where e, y, and n are known, but
x is not. Here, if you can factor n into its prime factors, you can find x,
but otherwise not.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/30/99 at 14:24:23
From: Jonathan Crowell
Subject: Re: Public Key Encryption

In your answer, you pointed out that it is easy to multiply two large
prime numbers together, but it is difficult to factor out the two
prime numbers given just their product. I understand that.

But a person who encrypts a message to me using my public key
obviously does not have access to the two large prime numbers that my
particular algorithm is based on. No part of the process of encrypting
a message using a public key involves multiplying together two large
prime numbers - that is done beforehand.

The person who wants to encrypt a message to me using my public key
has access to three numbers: M (the plaintext), E (a number relatively
prime to (P-1)(Q-1)), and PQ. P and Q are the two large prime numbers,
of course. Now, the encrypter performs some mathematical operations on M
using E and PQ to get C (the ciphertext). Anyone else with access to my
public key, which is assumed to be everyone in the world, will know what
E and PQ are, and will be given C. They will also know that C is M^E (mod PQ),
(I think I am right about that, but I am not sure. In any case, having
access to the public key entails being able to encrypt messages, so they
will know the particular mathematical operations involved in encrypting
a message.)

But it seems incredible to me that a person can be given C and know E
and PQ ahead of time, and know that C = M^E (mod PQ) -- and yet not be
able to figure out what M is. Obviously, this is not the case. Can you
explain why or where I have made an error?

Before I go, I want to solve the second mathematical problem you gave

Find x in the equation  2^x = 2094218297454 (mod 2103532971451)

You defined mod as follows: "To compute x (mod n), divide x by n, throw
away the quotient, and the remainder is the answer." Now, 2,103,532,971,451
is bigger than 2,094,218,297,454. The quotient would be 0 and the remainder
would be 2,094,218,297,454. So now, the problem is reduced to finding x
in the equation 2^x = 2,094,218,297,454. I do not have much background in
mathematics, but I think this equation can be solved using a base 2 logarithm.
Unfortunately, the calculator on my computer only performs natural logarithms
and base 10 logarithms, so I am going to have to work it out through trial
and error with the x^y function. Okay, I have figured out that x is
44.251477067515 give or take 0.000000000004. It took me about ten minutes.
I was not able to narrow down the last little bit because the calculator on
my computer does not accept numbers longer than 13 digits in length, but I
know the answer is between ...6751 and ....6752. If I had the time to run
down to the computer lab, though, I am pretty sure I could write a program
that would allow one of the Sun Sparcs down there to solve the problem in
a matter of milliseconds. Am I wrong?

```

```
Date: 03/30/99 at 16:02:16
From: Doctor Rob
Subject: Re: Public Key Encryption

Multiplying together is an example of an operation that is easy one way and
hard the other. In and of itself, it is *not* an example of an encryption
method.

The RSA Public Key Cryptosystem, which is the one you are discussing
in your followup above, depends for its security on the difficulty of

Given E, C, and PQ, find a number M such that

M^E = C (mod PQ)

It may strain your credulity, but it really is difficult! It is conjectured
to be about as difficult as factoring PQ. In fact, if you could factor PQ
and discover P and Q, then you could compute the decryption exponent D such
that D*E = 1 (mod[P-1][Q-1]), and find C^D = M (mod PQ), thereby decrypting
the message. If you cannot find P and Q, you cannot find D. Furthermore,
the ability to decrypt messages without finding P and Q first probably would
allow you to factor PQ using that capability.

As an example, suppose E = 3, and PQ = 183487271509, and C = 128879322311.
Find M. This is not easy! Finding a perfect cube M^3 which, when divided by
PQ leaves remainder C, is not a simple matter. There is only one such M
smaller than PQ.

Try a smaller example. Without factoring PQ, let E = 3, PQ = 47083,
C = 46440. Finding M is hard. It turns out that the only M smaller
than PQ which works is M = 11111. Then 11111^3 = 1371700960631. When
divided by 47083, the quotient is 29133677, and the remainder is
46440.

In the problem I gave you,

Find x in the equation  2^x = 2094218297454 (mod 2103532971451)

x has to be an integer. Perhaps I should have written it in the form

Find integer x such that  2094218297454 = 2^x (mod 2103532971451)

where 2^x will be a VERY large number, which, when divided by
2103532971451, will give a VERY large quotient (irrelevant) and the
remainder 2094218297454.

As an example, 2^3854 is a number with 1161 decimal digits. When you
divide it by 2103532971451, the quotient has 1148 decimal digits, and
the remainder is 375356427471. And 3854, a four-digit exponent, is really
a very small exponent to use; it could have had twelve digits!

The function x |--> 2^x (mod 2103532971451) is a very complicated one.
It is pretty easy to compute that, but hard to compute its inverse.
The same is true of the map M |--> M^E (mod PQ) used in the RSA Public Key
Cryptosystem.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search