Greatest common divisor and its applications in security: Case study

Abstract

In this paper, we explain the importance and applications of the Greatest Common Divisor(GCD) in the field of security. GCD of two numbers is the greatest divisor that ultimately divides these two numbers. The paper initially discusses four standard algorithms used in calculating GCD: Euclidean Algorithm, Binary GCD algorithm, Dijkstra's algorithm, and Lehmer's algorithm. We then analyze the various GCD applications in computer security. Some applications like generating modular multiplicative inverse are used in various cryptographic algorithms, reducing public keys' disclosure within closed groups, the importance of GCD in cryptographic algorithms, key refreshment message authentication, and peer validation. In the end, we cover the effects arising due to not proper use of GCD according to the algorithms stated in this paper, and how a poor choice of prime numbers that we use to compute the GCD and miscalculation of GCD can affect the computer security. © 2020 IEEE.