Waste less time on Facebook — follow Brilliant.
Number Theory

Encryption with Number Theory

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


Problem Loading...

Note Loading...

Set Loading...