Prime Numbers and Cryptography

By: Nazren Nazrinaz bin Nazri (MT2824)

Prime Numbers
Prime numbers are natural numbers, greater than 1, that are divisible only by 1 and itself. All of the
prime numbers are odd, except for 2. The opposite of prime numbers, composite numbers, are positive
integer that has more than two factors (Prime Numbers (Definition, Chart, List from 1 to 1000), n.d.).
The prime numbers within the range of 1 to 50 are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
These numbers are fundamental in number theory and have unique properties that make them essential
in various fields, including cryptography.

The Relationship between Prime Numbers and Cryptography

Cryptography is the process of hiding information so that the intended person can read it (Fortinet,
2023). It is derived from the Greek word “kryptos”, meaning hidden. So, cryptography is basically
means “hidden message” (IBM, 2023). Prime numbers are used in cryptography due to the nature of
the prime numbers itself, which is difficult to factorize. This implies that without first knowing the
factors, it is challenging to determine the prime factors of a composite number. This makes it more
difficult for someone without the right key to intercept a message and read it (Peshin, 2018).

The RSA Cipher

The RSA Cipher was named after its inventors, Ron Rivest, Adi Shamir, and Len Adlemen, who were
researchers at MIT, credited for being the first to publicize the RSA cipher. The RSA crytosystem is
based on Fermat’s Little Theorem and Euler’s Theorem (Klima & Sigmon, 2012). Fermat’s Little
Theorem stated that, if p is prime and a ∈ ℤ with p∤a, then a(p−1) ≡1 (mod p). In other words, if you
raise a to the power of p – 1, then divided by p, the remainder is 1.
For example:
Let a = 3 and p = 7, from Fermat Little’s Theorem,
37−1 = 36 = 729
7
7 7 2 9
− 7 2 8
1 Remainder

1
Thus,
36 ≡ 1 (mod 7)

Euler’s Theorem stated that if a and n are coprime positive integers, then a𝜑(n) ≡ 1 (mod n), where
φ(n) is the Euler’s Phi Function. Euler’s Phi Function is defined as the number of positive integers ≤ n
which are relatively prime to n. For example:
If φ(9), then, φ(9) = 6. This is due to the fact that the number of positive integers ≤ 9 that are relatively
prime to 9 are 1, 2, 4, 5, 7 and 8. As for the Euler’s Theorem, let n = 4 and a = 15. Here, φ(n) = φ(4) =
2, since there are only two positive integers, that are ≤ 4, which are relatively prime to 4, in this case,
1 and 2. Observe:
a𝜑(n) = 152 = 225.
Thus, 225 ≡ 1 (mod 4) ⇒ 224 ≡ (mod 4) ⇒ 4|224 ⇒ 224 = (56)4.
From the definition of Euler’s Phi Theorem, we have two lemmas, that are:
• If n is prime, then φ(n) = n – 1.
• If p and q are prime, then φ(pq) = φ(p)φ(q).

RSA Process
The RSA process begins with the recipient sending the originator two integers. The process of choosing
integers are as follows:
1 Decide on two prime integers, p and q.
2 Calculates n = pq, and φ(n) = φ(pq) = φ(p)φ(q) = (p – 1)(q – 1).
3 Choose an integer e such that 1 < e < φ(n) with gcd(e, φ(n)) = 1.
The recipient then send the values of e and n to the originator while keeping the values of p and q to
themselves.
When the originator receives the two values of n and e, they can now begin to encrypt the
message with the function y ≡ xe (mod n), where y is the value correspond to the ciphertext. The, the
recipient will then receives the crypted message and now starting the process to decrypt it. To decrypt
the message, they will have to find the private decryption key, d for which d ≡ e−1 (mod n), by using
extended Euclidean Algorithm. The decryption function is given by x ≡ yd (mod n).

2
For the following example, we’re going to refer to the table below:
Alphabets A B C D E F G H I J K L M
Ciphertext 1 2 3 4 5 6 7 8 9 10 11 12 13
Alphabets N O P Q R S T U V W X Y Z
Ciphertext 14 15 16 17 18 19 20 21 22 23 24 25 26

Izzaidie wants to send a message to Tristian. Tristian needs to send the value of n and e to Izzaidie as
the lock, the lock is public, meaning everyone can see the lock. Tristian chooses two prime integers, p
= 3 and q = 11. Tristian then calculates n = pq = (3)(11) = 33 and φ(n) = (3 – 1)(11 – 1) = 20. He
chooses e = 7 since gcd(7, 20) = 1. Tristian sends 7 and 33 to Izzaidie. Once Izzaidie receives the key,
he then starts to decrypt “HI” to Tristian. So, using the table provided above:
y ≡ 87 ≡ 2 (mod 33)
y ≡ 97 ≡ 15 (mod 33)
Izzaidie now sends the encrypted ciphertext, 2 and 15, to Tristian. Tristian will decrypt the message by
finding d such that 7d ≡ 1 (mod 20). By using the Extended Euclidean Algorithm, the value of d = 3,
since 21 ≡ 1 (mod 20). Tristian decrypt the message by using the decryption function is given by x ≡
yd (mod n).
x ≡ 23 (mod 33) ≡ 8 (mod 33)
x ≡ 153 (mod 33) ≡ 9 (mod 33)
Now, Tristian can decrypt the message using the table provided, that is “HI”.

Why Prime Numbers are Important in Cryptography?

Prime numbers are crucial in cryptography because they make it easy to multiply two large primes
together, but extremely difficult to reverse the process and factor the resulting product back into the
original primes. This one-way function is the foundation of many encryption systems, such as RSA.

In RSA encryption, two large prime numbers are multiplied to create a public key. While anyone can
use this public key to encrypt data, only someone with knowledge of the original prime numbers can
efficiently decrypt it. The security of this system relies on the fact that, although multiplying primes is
straightforward, factoring their product is computationally infeasible for sufficiently large numbers.

In summary, prime numbers are essential in cryptography because they enable the creation of secure
encryption methods that protect digital information.

3
References

Fortinet. (2023). What Is Cryptography? Definition, Importance, Types. Fortinet.

https://www.fortinet.com/resources/cyberglossary/what-is-cryptography

IBM. (2023, November 14). Cryptography. Ibm.com. https://www.ibm.com/think/topics/cryptography

Klima, R. E. & Sigmon, N. P. (2018). Cryptology. CRC Press.

Klima, R. E., & Sigmon, N. P. (2012). Cryptology: Classical and Modern With Maplets: Vol. Chapter
8 (First Edition, pp. 275–327) [Review of Cryptology: Classical and Modern With Maplets].
CRC Press. (Original work published 2012)

Maxy, M. (2012). A Modern Day Application of Euler’s Theorem: The RSA Cryptosystem.
https://www.gcsu.edu/sites/files/page-assets/node-808/attachments/maxey.pdf

Peshin, A. (2018, May 7). How Are Prime Numbers Used In Cryptography? Science ABC.
https://www.scienceabc.com/innovation/how-are-prime-numbers-used-in-cryptography.html

Prime Numbers (Definition, Chart, List from 1 to 1000). (n.d.). BYJUS.

https://byjus.com/maths/prime-numbers/