Cryptography Fundamentals 5: GCD, Extended GCD and Group Generators

Cryptography Fundamentals 5: GCD, Extended GCD and Group Generators

This podcast will outline a few building blocks of cryptography: GCD (Greatest common divisor), extended GCD and group generators. These you will find in many related cryptography papers, and any weaknesses in these can cause significant problems to the overall security of a method.

Greatest common divisor— GCD

A fairly simple concept that is used within public key encryption is the greatest common divisor (GCD). With this, we take two integer values and determine the largest factor that they are. Overall, every non-prime number is made up of the multiplication of prime numbers. For example:

32,128 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 251

36,281 = 7 x 71 x 73

So, the GCD of 56 and 42 is 14, as both of the values can be factorized into 4 x 14 and 3x14, respectively. https://asecuritysite.com/principles_pub/gcd

Normally we use this function to find values which do not share a factor, as we will see when selecting the public exponent (e) in the RSA method. The method to determine the GCD is fairly simple, and where we take two values (a and b) and use the modulus operation to find the GCD:

def gcd(a, b):
 while( b != 0 ):
 Remainder = a % b;
 a = b;
 b = Remainder;
 return a;
g = gcd(679,99)
print g

A sample run shows that 679 and 99 do not share any factors:

a:679, b:99, Remainder:85
a:99, b:85, Remainder:14
a:85, b:14, Remainder:1
a:14, b:1, Remainder:0
Return value:1

Web: https://asecuritysite.com/encryption/gcd

Extended GCD

GCD is the greatest common divisor. For two integers (x and y), the extended GCD method solves ax+by=v for a and b, and where v=gcd(x,y). One example of using the Extended GCD method is to determine the modulo inverse of a value (the inverse value of n (mod p) so that:

n⋅n^{−1}=1 (mod p) ).

30a+20b=gcd(30,20). Soln: a=1, b=−1. Try!

35a+15b=gcd(35,15) . Soln: a=1, b=−2. Try!

https://asecuritysite.com/principles_pub/xgcd

Group generator

In reading about cryptography, have you ever come across the term of a cyclic group G of order p and with a generator g? With a discrete log mapping, we map x to Y with

Y=g^x (mod p)

where we have a generator value (g) and a prime number p. The challenge is that even though we know Y, g and p, it is extremely difficult to determine the x value if we use a large prime number.

But can we use any value of g, and should it be as large as possible? The answer to both of these questions is no. If select a prime number of 11, and then select g values of 2, 3, 4 …10, and then calculate the results we get [spreadsheet]:

Now look at g=2 and p=11, for 2¹ (mod 11) we get 2, 2² (mod 11) we get 4, 2³ (mod 11) we get 8, and so on. As we see {1,2,3,4,5,6,7,8,9,10} gives {2,4,8,5,10,9,7,3,6,1}, and where all the input values give a 1-to-1 mapping to another value in the group. But if we try g=3 and p=11, we get x=1 gives 3, and for x=6 also gives 3. The mapping is now {1,2,3,4,5,6,7,8,9,10} to {3,9,5,4,1,3,9,5,4,1}, and so we are not using the full range, and where there would be a confusing for mapping back to our original value.

But, in order to demonstrate the principle, I have done this in a long-handed way, so how do I find out all the possible values of G for a given prime number (p)? Well, here’s a nice simple method in Python that I created to test up to p):

import sys
def issafe(g,p):
        exp=1
        rand=g
        next = rand % p
        while (next != 1 ):
                next = (next*rand) % p
                exp = exp+1
        if (exp==p-1):
                return True
        else: return False
p=11
g=4
if (len(sys.argv)>1):
 p=int(sys.argv[1])
if (len(sys.argv)>2):
 g=int(sys.argv[2])
print ("Is g={0} safe for p={1}? {2}".format(g,p,issafe(g,p)))
print ("x\tg^x\tg^x (mod p)")
for x in range(0,10):
 print ("{0}\t{1}\t{2}".format(x,pow(g,x),pow(g,x,p)))

A sample run with an unsafe value is:

Is g=3 safe for p=13? False
x	g^x	g^x (mod p)
0	1	1
1	3	3
2	9	9
3	27	1
4	81	3
5	243	9
6	729	1
7	2187	3
8	6561	9
9	19683	1

and where the only output value is 1, 3 and 9. For a safe value, we get:

Is g=3 safe for p=17? True
x	g^x	g^x (mod p)
0	1	  1
1	3	  3
2	9	  9
3	27	  10
4	81	  13
5	243	   5
6	729	  15
7	2187      11
8	6561      16
9	19683     14

So, how does this work in practice? Well, rather than picking the prime number and then finding a g value which will work, we typically we pick the g value we want, such as for g=2, g=3 or g=5, and then find a prime number of a given size to work with that value. This will slow down the process, as we might have to pick a few prime numbers before we find one that will work. An example command in OpenSSL to generate the Diffie-Hellman parameters for g=3 and a 512-bit prime number is:

openssl dhparam -text -3 512
DH Parameters: (512 bit)
 P: 
 00:ff:1a:a6:fd:94:1b:55:8c:03:e0:ba:91:d5:e3:
 23:40:6a:8e:49:a1:d4:d9:dd:68:3f:10:3d:ff:a7:
 a6:8e:2f:9f:f9:3f:4d:dc:3d:54:71:e0:aa:65:dc:
 24:03:42:73:39:db:d6:02:a6:dc:bd:ac:49:12:a8:
 dc:d0:57:d9:bf
 G: 3 (0x3)

https://asecuritysite.com/openssl/dh