Original Article ShodhKosh: Journal of Visual and Performing Arts

ISSN (Online): 2582-7472 July-December 2023 4(2), 3635–3639

APPLICATIONS OF NUMBER THEORY IN CRYPTOGRAPHY

Dr. Gavirangaiah K 1

1 Associate Professor of Mathematics, Government First Grade College, Tumkur

ABSTRACT
Number theory is a branch of mathematics that plays a critical role in the field of
cryptography, providing the theoretical foundations for many cryptographic algorithms
and protocols. It involves the study of integers and their properties, including prime
numbers, divisibility, modular arithmetic, and Diophantine equations. Cryptographic
DOI systems leverage these number-theoretic concepts to secure communication, protect
10.29121/shodhkosh.v4.i2.2023.402 data, and ensure privacy in digital transactions. One of the most significant applications
1 of number theory in cryptography is in public-key cryptography, which relies on the
mathematical difficulty of certain number-theoretic problems. For example, the RSA
Funding: This research received no
specific grant from any funding agency in
algorithm, one of the most widely used public-key cryptosystems, depends on the
the public, commercial, or not-for-profit difficulty of factoring large numbers, a problem that is grounded in number theory.
sectors. Modular arithmetic and prime number theory form the core of RSA key generation,
encryption, and decryption processes. Similarly, Elliptic Curve Cryptography (ECC) uses
Copyright: © 2023 The Author(s). the algebraic structure of elliptic curves over finite fields and relies on the difficulty of
This work is licensed under a Creative
solving the Elliptic Curve Discrete Logarithm Problem (ECDLP). Other number-theoretic
Commons Attribution 4.0
International License.
methods, such as modular exponentiation and the Euclidean algorithm for finding
greatest common divisors, are central to the security of protocols like Diffie-Hellman key
With the license CC-BY, authors retain exchange, which allows two parties to securely share a secret key over an insecure
the copyright, allowing anyone to channel. Digital signatures, which authenticate and verify the integrity of messages, also
download, reuse, re-print, modify, use number-theoretic operations, often involving modular arithmetic and hash functions.
distribute, and/or copy their
In conclusion, number theory is indispensable to modern cryptography. It underpins the
contribution. The work must be
properly attributed to its author. security of a wide range of cryptographic protocols and systems, ensuring the
confidentiality, integrity, and authenticity of digital communications and transactions in
an increasingly interconnected world.

Keywords: Applications, Number Theory, Cryptography

1. INTRODUCTION
Cryptography is the practice and study of securing communication and information through the use of mathematical
techniques. It involves transforming readable data (plaintext) into an unreadable format (ciphertext) and vice versa,
ensuring that only authorized parties can access the original information. The primary objectives of cryptography are
confidentiality, integrity, authentication, and non-repudiation. These objectives are essential for securing sensitive data
and communications in an increasingly digital world, where cyber threats are prevalent. Cryptography is an integral
part of modern computing systems, supporting secure communication in areas such as banking, e-commerce, military,
government, and personal data protection. Cryptographic methods are used to protect passwords, credit card numbers,
digital currencies, emails, and much more. The two main branches of cryptography are symmetric-key cryptography,
where the same key is used for both encryption and decryption, and asymmetric-key cryptography, where two different
keys (public and private) are used. Public-key cryptography, developed in the 1970s, revolutionized security by allowing
secure communication without the need for a shared secret key. The strength of cryptographic systems is based on the
complexity of certain mathematical problems, such as factoring large numbers, solving discrete logarithms, and
computing elliptic curve discrete logarithms. As technology advances and computing power increases, cryptographic

How to cite this article (APA): K, G. (2023). Applications of Number Theory in Cryptography. ShodhKosh: Journal of Visual and 3635
Performing Arts, 4(2), 3635–3639. doi: 10.29121/shodhkosh.v4.i2.2023.4021
 Applications of Number Theory in Cryptography

techniques must evolve to stay ahead of potential security threats. Cryptography remains a cornerstone of digital
security, providing the foundation for privacy, secure transactions, and trust in digital systems.

1.1. OBJECTIVE OF THE STUDY

This study explores the Applications of Number Theory in Cryptography.

2. RESEARCH METHODOLOG
This study is based on secondary sources of data such as articles, books, journals, research papers, websites and
other sources.

3. APPLICATIONS OF NUMBER THEORY IN CRYPTOGRAPHY

Cryptography is the art and science of securing communication to protect sensitive information from unauthorized
access or tampering. It has become a critical component in various areas, such as secure communications, digital
transactions, and online privacy. The role of cryptography is to ensure the confidentiality, integrity, and authenticity of
data as it is transmitted over potentially insecure networks like the internet. Number theory, a branch of mathematics,
is essential to cryptography because it provides the mathematical foundations for secure encryption algorithms and
protocols. It deals with the study of integers and the relationships between them, focusing on the properties of prime
numbers, modular arithmetic, greatest common divisors, and Diophantine equations. Cryptography utilizes these
principles to create systems that can secure information effectively. By leveraging the difficulty of certain number-
theoretic problems (like factoring large numbers or solving discrete logarithms), cryptographic systems can ensure that
only authorized parties can access sensitive data. The interplay between cryptography and number theory allows for
the creation of robust security protocols, such as public-key cryptography (which uses asymmetric encryption) and
digital signatures. These cryptographic systems rely on the inherent difficulty of solving number-theoretic problems,
providing a mathematical guarantee of security.

3.1. KEY CONCEPTS IN NUMBER THEORY RELEVANT TO CRYPTOGRAPHY

Number theory offers several key concepts that are fundamental to cryptography, including prime numbers,
modular arithmetic, the greatest common divisor (GCD), and Euler’s Totient Function.
1) Prime Numbers
Prime numbers are the building blocks of number theory and cryptography. A prime number is a natural number
greater than one that has no positive divisors other than one and itself. Prime numbers are crucial for constructing
cryptographic keys, particularly in algorithms like RSA. The security of RSA, for example, hinges on the difficulty of
factoring large composite numbers, which are products of two prime numbers. The larger the prime numbers used, the
more secure the encryption becomes, because factoring large composite numbers is computationally infeasible. In RSA,
the private key is linked to two prime numbers, making their secrecy vital for maintaining the security of the system.
2) Modular Arithmetic
Modular arithmetic is the process of performing calculations "modulo" some number, meaning the remainder after
division. For example, in modular arithmetic, 9 mod 4=1, because when you divide 9 by 4, the remainder is 1. This
concept underpins many cryptographic algorithms, such as RSA and Diffie-Hellman. In these systems, numbers are raised
to large powers, and the results are reduced modulo a number to keep the results manageable. The modular
exponentiation operation forms the basis of key operations like encryption and decryption.
3) Greatest Common Divisor (GCD) and Euclidean Algorithm
The greatest common divisor (GCD) of two integers is the largest integer that divides both of them without leaving
a remainder. The Euclidean algorithm is an efficient method for computing the GCD of two numbers. In cryptographic
systems, the GCD is used to determine the coprimeness of numbers. For example, in RSA, the public and private keys
must be coprime with Euler's Totient function of a number (i.e., their GCD must be 1). The Euclidean algorithm also helps
in calculating the modular inverse, which is essential in RSA for key generation.

ShodhKosh: Journal of Visual and Performing Arts 3636

 Dr. Gavirangaiah K

4) Euler’s Totient Function

Euler's Totient function, denoted ϕ(n), counts how many integers from 1 to n are coprime with n (i.e., have no
common divisors with n other than 1). This function is crucial in RSA for computing the private key. It is used to calculate
the number of integers less than n that can be used in the encryption process. The Totient function is also important for
understanding the structure of modular arithmetic and plays a vital role in the difficulty of breaking many cryptographic
systems.

3.2. RSA ALGORITHM AND ITS BASIS IN NUMBER THEORY

The RSA algorithm is one of the most widely used public-key cryptographic algorithms, and it is based heavily on
number theory, particularly the concepts of prime numbers, modular arithmetic, and Euler’s Totient function.
1) Key Generation
RSA starts by selecting two large prime numbers, p and q, and multiplying them to produce n = p×q. The number n
is used as part of both the public and private keys. The next step is to compute Euler's Totient function for n, denoted
ϕ(n)=(p−1)(q−1). This is necessary because it represents the number of integers less than n that are coprime to n, which
is crucial for generating the keys. A public exponent e is then chosen, which must be coprime with ϕ(n). This ensures
that there exists a modular inverse d for e modulo ϕ(n). The modular inverse d is calculated using the Extended Euclidean
Algorithm. The public key is composed of the pair (n,e), and the private key is composed of the pair (n,d).
2) Encryption
Once the keys are generated, the sender can encrypt a message using the recipient's public key. The encryption
process in RSA involves raising the message mmm to the power of eee modulo n, producing the ciphertext c:
c= me mod n
This transformation ensures that only someone with the correct private key can decrypt the message.
3) Decryption
To decrypt the message, the recipient uses their private key (n,d). The decryption process involves raising the
ciphertext c to the power of d modulo n:
m= cd mod n
This process recovers the original message because (me)d ≡ m, due to the mathematical properties of modular
arithmetic. The security of RSA relies on the fact that while it is easy to multiply large prime numbers together to
compute n, it is computationally difficult to factor n back into its prime factors p and q. Without knowledge of these
factors, it is almost impossible to compute the private key d from the public key.

3.3. ELLIPTIC CURVE CRYPTOGRAPHY (ECC)

Elliptic Curve Cryptography (ECC) is an asymmetric cryptographic method that uses elliptic curves over finite fields.
ECC is based on the difficulty of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP), which is considered
computationally difficult even for relatively small numbers. An elliptic curve is defined by the equation:
y2=x3+ax+b
where a and b are constants, and the curve is defined over a finite field. The points on the curve can be added
together using an elliptic curve addition operation, which forms the basis for key generation and encryption in ECC.
In ECC, a private key is a randomly selected integer, and the corresponding public key is obtained by multiplying a
fixed generator point on the curve by the private key. The security of ECC relies on the difficulty of the ECDLP, which is
the problem of determining the private key given the public key. This problem is much harder than factoring large
numbers or solving traditional discrete logarithm problems, making ECC more efficient in terms of key size and
computational power compared to RSA. For example, ECC can offer the same level of security as RSA but with much
smaller key sizes. This makes it especially useful in resource-constrained environments such as mobile devices and IoT
(Internet of Things) systems, where computational efficiency is crucial.

ShodhKosh: Journal of Visual and Performing Arts 3637

 Applications of Number Theory in Cryptography

3.4. DIFFIE-HELLMAN KEY EXCHANGE AND MODULAR EXPONENTIATION

The Diffie-Hellman Key Exchange algorithm allows two parties to securely establish a shared secret over an insecure
channel. The security of Diffie-Hellman relies on the difficulty of computing discrete logarithms in a finite field, a problem
that is considered hard for large numbers.
1) Key Exchange Process
1) Both parties agree on a large prime number p and a base g, both of which are public.
2) Each party selects a private key, say a for Alice and b for Bob. They then compute their corresponding public
keys as A= ga mod p and B=gb mod p, and exchange them over the insecure channel.
3) Once each party has received the other party’s public key, they compute the shared secret. Alice computes
S=Ba mod p, and Bob computes S= Ab mod p. Both parties end up with the same shared secret because
(ga)b= (gb)a mod p.
The security of Diffie-Hellman arises from the fact that, while it is easy to compute A and B, it is computationally
infeasible to determine the shared secret SSS without knowledge of the private keys a or b, due to the difficulty
of solving the discrete logarithm problem.

4. DIGITAL SIGNATURES AND HASH FUNCTIONS

Digital signatures are used to verify the authenticity and integrity of messages or documents. A digital signature is
created by applying a cryptographic hash function to the message and then encrypting the hash with the sender's private
key. In RSA, the signature of a message mmm is created by computing:
Signature = H (m)d mod n
where H(m) is the hash of the message and d is the sender's private key. The recipient can verify the signature
by decrypting it with the sender's public key and checking that the decrypted value matches the hash of the original
message. Hash functions, such as SHA-256, are used in digital signatures to reduce the size of the data that needs to be
signed. These hash functions are designed to produce fixed-length outputs and are resistant to collisions, ensuring that
each unique input maps to a unique hash value.

4.1. APPLICATIONS OF NUMBER THEORY IN CRYPTOGRAPHY

The applications of number theory in cryptography are vast and critical for modern secure communication systems.
Public Key Infrastructure (PKI) systems, digital currency systems like Bitcoin, and secure communication protocols like
HTTPS and SSH all rely on the principles of number theory. These systems ensure secure transactions, protect privacy,
and authenticate users by utilizing number-theoretic problems that are computationally difficult to solve. The robustness
of these cryptographic techniques relies on the difficulty of problems like integer factorization, solving discrete
logarithms, and the elliptic curve discrete logarithm problem.

5. CONCLUSION
Number theory is a cornerstone of modern cryptography, providing the mathematical foundation for securing
digital communication and protecting sensitive data. Concepts such as prime numbers, modular arithmetic, Euler’s
Totient function, and discrete logarithms are integral to the design and functioning of many cryptographic algorithms.
Public-key cryptography, including well-known algorithms like RSA and elliptic curve cryptography (ECC), heavily relies
on the computational difficulty of number-theoretic problems to ensure data security. These systems offer a robust
framework for encryption, digital signatures, and secure key exchange, which are essential in today's digital world. The
security of numerous applications, ranging from online banking and e-commerce to secure communications and digital
currencies, is directly tied to the strength of number-theoretic techniques. As computational power continues to grow,
number theory remains crucial in developing more efficient and secure cryptographic methods to counter emerging
threats. Additionally, the rise of quantum computing challenges traditional cryptographic systems, urging researchers to
explore quantum-resistant number-theoretic algorithms. Number theory not only enables the security of modern

ShodhKosh: Journal of Visual and Performing Arts 3638

 Dr. Gavirangaiah K

communication systems but also evolves with technological advancements to safeguard privacy, integrity, and trust in
digital environments, ensuring the continued reliability of cryptographic techniques in an interconnected world.

CONFLICT OF INTERESTS
None.

ACKNOWLEDGMENTS
None.

REFERENCES
Barker, E., & Barker, W. (2012). Recommendation for pairwise key establishment schemes using discrete logarithm
cryptography (NIST Special Publication 800-56A Rev. 3). National Institute of Standards and Technology.
Katz, J., & Lindell, Y. (2014). Introduction to modern cryptography (2nd ed.). CRC Press.
Schneier, B. (2015). Cryptography engineering: Design principles and practical applications (2nd ed.). Wiley.
Stinson, D. R. (2005). Cryptography: Theory and practice (3rd ed.). CRC Press.
Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (1997). Handbook of applied cryptography. CRC Press.

ShodhKosh: Journal of Visual and Performing Arts 3639