Number Theory in Cryptography
Bonjour👋 I’m Ankita Sinha, an MTech CSE student doing a specialization in Information Security. You can connect with me on LinkedIn, and Github. Contributors of the Article: Megala & AnkitaInsecurity applications like authentication, cryptography, etc number theory play a vital role. Cryptography is nowadays needed everywhere like for transferring emails, and messages, online transactions, the internet, etc. Cryptography is the practice and study of secure communication and protection of information from threats and attacks. It is also known as cryptology. It is an art of secretly transmitting information and is practiced for a long time. There is a sort of cryptography symmetric and asymmetric cryptography. In symmetric cryptography, a single key is used to encrypt and decrypt the text. Whereas in asymmetric cryptography two keys i.e. public and private keys used to encrypt and decrypt the text. The encoded text is called ciphertext.
Cryptography uses encryption algorithms like RSA, Diffie-Hellman (DH), or Digital Signature Algorithm (DSA) modulo a prime p, Elliptic Curve Diffie-Hellman (ECDH) or Elliptic Curve Digital Signature Algorithm (ECDSA). Symmetric cryptography uses Diffie-Hellman (DH) to generate this key based on number theory and asymmetric cryptography uses the RSA algorithm to generate the keys. Generally, private key cryptography is based on a hash function, block cipher, etc. But for public-key cryptography number theory is used. Theorems like Euclid's theorem, Fermat’s theorem, Factorization, etc. Fermat’s theorem is used in the RSA algorithm for public-key cryptography and primality testing.
In symmetric cryptography, the length of the key ranges from 46 bits to 256 bits. Hence, most of them are used for long messages. For n station in a network, the number of keys required is,
i.e. key, k is divisible by 2. Advanced encryption standards (AES) and data encryption standards (DES) are used in symmetric cryptography. Here the keys are not shared keys, its generated using the DH algorithm by using the following formula, where x and y are prime numbers, private numbers, G and N are prime numbers, publicly available known by sender and receiver.
Once the keys R1 and R2 are generated they are exchanged between the sender and receiver. Then secret keys are generated, and both the keys have equal values.
In asymmetric cryptography, the length of the keys ranges from 256 bits to 2048 bits. Hence, most of them are used for long messages. For n station in a network, the number of keys required is,
i.e. key, k is multiple of 2. RSA algorithm is used in asymmetric cryptography. RSA algorithm is a public key encryption algorithm and is one of the most secure ways of encryption. In RSA, there are two sets of keys private and public keys used by the sender and receiver. Two large prime numbers p and q are selected, then RSA modulus is calculated, i.e. N = p* q, N is the large number. Then Euler’s totient function is calculated, i.e.
A derived number is the public key and is selected by satisfying the following conditions,
And the private key, d is calculated using the formula,
where k=0,1,2, 3…., n. Therefore, the public key is a pair of (N, e), and the private key is a pair of (N, d), then
Here, C denoted ciphertext, and P denotes plain text. Using the above keys encryption and decryption are performed.
As shown in the above algorithms its shows that the algorithms are based on number theory. Similarly, in the elliptic curve DH algorithm and elliptic curve digital signature algorithm number theory theorems and methods like Modular arithmetic, and the greatest common divisor are used for cryptography. The above algorithm uses Euclid’s algorithm and congruence.
In Fermat’s Theorem, let p be a prime number and GCD ( a, p ) = 1.
In Fermat’s Theorem, let p be a prime number and GCD ( a, p ) = 1.
This can be used for public-key cryptography and primality testing.
Similarly, in the Chinese Remainder Theorem, let p and q be coprime then, the system equations are
has an unique solution, for x modulo pq. The reverse direction is trivial given that
where the x modulo p and x modulo q are reduced to obtain two equations of the above-shown form. So, the theorem is divided into two parts where in the first part there should exist x and the second part states the solutions formed by the same remainder when divided by p and q. Chinese Remainder Theorem speeds up modulo computation. And there are several equations in modular arithmetic a prime power that with the Chinese remainder theorem generalizes any result.
Algorithms like Fermat’s and Euler’s theorems, Primality testing, Chinese Remainder Theorem, and Primitive Roots and Discrete Logarithms are used with cryptography to ensure the integrity of the message and network security like ElGamal cryptosystem, or Discrete log problem. Many number theory tools like primes, divisors, congruence, remainders, and Euler’s function are plays a vital role in cryptography for security purposes. Congruencies are used in Caesar's cipher keys and in RSA keys.
References:
[1] P. Singh, A. Singh, and S. Jhamb, “Importance of Number Theory in Cryptography,” 6th Int. Conf. onRecent Trends Eng. Sci. Manag., pp. 591–595, 2017, [Online]. Available: http://data.conferenceworld.in/SGTB/P591-595.pdf.
[2] K. A. Draziotis, V. Martidis, and S. Tiganourias, “Product Subset Problem : Applications to number theory and cryptography,” pp. 1–17, 2020, [Online]. Available: http://arxiv.org/abs/2002.07095.
[3] K. Lauter, “The Advantages of Elliptic Curve Cryptography for Wireless Security,” IEEE Wirel. Commun., vol. 11, no. 1, pp. 62–67, 2004, doi: 10.1109/MWC.2004.1269719.
