Understanding Cryptographic Functions and RSA Security

What is a One-Way Function?

A one-way function is a function that is easy to compute in one direction but difficult to compute in the reverse. For example, given an input, a hash is easy to compute. However, given the output, it is extremely difficult (time-consuming) to determine the input.

What is a Trapdoor Function?

A trapdoor function is like a one-way function; however, a trapdoor function can reverse the one-way function if the trapdoor is known. For example, finding the two prime divisors of 6,895,601 is difficult. However, if you know that 1,931 is one of the numbers, it will be easy to divide 6,895,601 by 1,931 to determine the answer. In this case, 1,931 is the trapdoor.

What Makes RSA Difficult to Break?

The large number factorization problem makes RSA difficult to break. The modulus used in RSA is usually 1024 bits long, which is a number that has more than 300 digits. Computing the divisors is infeasible.

Euler’s Phi (Totient) Function and its RSA Use

Euler’s Phi Function is used to calculate the count of numbers in the set Z_n^*. If n is a prime, the count of numbers in the set Z_n^* is n-1, i.e., φ( n) = n-1. Euler’s totient function is distributive; i.e., if n = p ∗ q, then φ( n) = φ( p) ∗ φ( q). Calculating φ( n) is difficult (due to the large number factorization problem), but because p and q are known and chosen during the RSA process, it is easy to calculate φ( n). From the set of numbers in φ( n), a value e (the encryption key) is selected such that e is coprime to φ( n). A value d (decryption key) is also selected such that d is the inverse of e modulo φ( n).

Asymmetric Encryption Beyond Message Encryption

Asymmetric encryption can also be used for digital signatures and key exchange.

RSA Alternatives: Elliptic Curve Cryptography

Elliptic Curve Cryptography is an alternative to RSA.