Waste less time on Facebook — follow Brilliant.
×

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.

Warmup

         

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? \)

×

Problem Loading...

Note Loading...

Set Loading...