×
Back to all chapters

# Encryption with Number Theory

Results in number theory discovered hundreds of years ago by Fermat and Euler fuel the modern cryptography keeping your texts, emails, and other electronic data safe.

# Public-Key Encryption

What sort of mathematical breakthrough would endanger the security of the RSA encryption algorithm?

In an encoding scheme, each letter is replaced as follows: $A = 1, \ B = 2, \ C = 3,\ \ldots\ , \ Z = 26.$ For example, $$CODE$$ would be encoded as $$31545,$$ since $$C = 3,$$ $$O = 15,$$ $$D = 4,$$ and $$E = 5.$$

What is the main problem with such a system?

To crack a code, Alice and Bob need to find the product of their secret large primes, $$a$$ and $$b,$$ so they each send these primes to each other.

Alice receives $$b$$ and performs $$b \cdot a$$, while Bob receives $$a$$ and performs $$a \cdot b$$.

What's the main issue with this encryption system?

Suppose Alice and Bob want to establish an encryption key. They start by choosing a large prime $$p$$, which is shared in public.

Alice secretly picks a large prime $$a$$, and Bob secretly picks a large prime $$b$$. Then both Alice and Bob multiply their primes by $$p$$, so Alice now has $$a \cdot p$$ and Bob has $$b \cdot p$$.

They send $$a \cdot p$$ and $$b \cdot p$$ to each other. They then multiply what they receive by what their own secret prime. That is, Alice receives $$b \cdot p$$ and performs $$b \cdot p \cdot a$$, and Bob receives $$a \cdot p$$ and performs $$a \cdot p \cdot b$$.

Alice and Bob now have the same number that they can use as their secret key.

Is this encryption system secure?

Suppose a cryptography system included the step where, given $$m ,$$ $$e ,$$ and $$n,$$ it is necessary to calculate $$c$$ in $$m^e \equiv c \pmod{n}.$$ (That is, first $$m^e$$ is found, then the value is divided by $$n$$ with the remainder $$c$$. )

$$e,$$ $$n,$$ and $$c$$ are going to be shared in public, and it is important that $$m$$ remains a secret.

Which of these circumstances would easily compromise $$m?$$

×