Cryptography Fundamentals 2: Groups operations (Add, Subtract, Multiply, Divide and Exponentiation)

A fundamental element in cryptography is the mapping of one group to another and then being able to map back again. In this, there should be no confusion about the mapping and where it should be deterministic in the mapping — that is, no matter how many times we do it, we will always create the same mapping. Obviously, we can add some randomisation into the process, but with the same randomization, we always get the same mappings. In the previous podcast, I showed how a group of A={1,2,3,4} will map to B={2,4,3,1} using a mapping of b=g^a (mod p). We see that every element of A has a one-to-one mapping from A to B. We then aim to have a mapping back from B to A, and recover the original value. Arithmetic operations And, so, encryption (the mapping of A to B) can become a mathematical operation, and then where the decryption (the mapping of B to A) is basically just the reverse of our encryption process. And, so, remember those puzzles as a child. Think of a number. Now add 10 and double it. Take away 7. Add 5, and half it. The answer is 9. Of course, this is a trick, and where we get: [(2(x+10)-7+5)/2]-x =[(2x+20–7+5)]-x = [(2x+18)/2 ]-x= [x+9]-x = 9 For this, we are basically just reversing back the method we quote in the track. And so, for encryption, we could multiply by 9, and add 14 to get our cipher value. To decrypt, we would reverse the operations so that we subtract by 14 and then divide by 9. But, in cryptography, we have a finite field in our group and thus use the (mod p) operation to constrain our integers. Luckily, all our arithmetic operations still work if we use the modulo of a prime number. Adding and subtracting Let’s try to add, with x=8 and y=12, and use a prime number of p=11. If we do: (x+y) (mod p) is it the same as x (mod p) + y (mod p). And, so: 8 (mod 11) + 5 (mod 11) = 13 (mod 11) = 2 Now we will try: (8+5) (mod 11) = 13 (mod 11) = 2 So can we now subtract b from the result? 2–5 (mod 11) = -3 (mod 11) = 8 Thus if we had an operation to add to values in a group and then reverse them. This goes for modulo multiply and then divide.  Multiplying and divide Now let’s try to multiply and divide. For this, we will multiply our values by four modulo 5. This will get: >>> (1*3)%53>>> (2*3)%51>>> (3*3)%54>>> (4*3)%52 We ignore the zero for the set in A, as we will always get the same result. Thus we map {1,2,3,4} to {3,1,4,2}. Now we need to divide by three modulo 3. For this, we create the inverse mod of the value and then just multiply. This is basically: a/b (mod p) = a* b^{-1} (mod p) Basically, it is the value of x which will make this true: b.x (mod p) = 1 This x is thus the multiplicative modular inverse value of b. So, let’s find the inverse of 3 (mod p): >>> pow(3,-1,5)2 Note that the pow(x,y,p) function is x^y (mod p). Thus to divide by 3 (mod 5), we multiply by 2. Let’s try it: >>> (3*2) % 51>>> (1*2) % 52>>> (4*2) % 53>>> (2*2) % 54 and so we get our original values back. Thus we use an inverse mod to reverse a modulo multiplication. Exponentiation And, so, we can see that adding, subtracting, multiplying and dividing work with the modulo operations. Let’s try exponentiation. For this, we can have: b = a^x (mod p) If we try x=3 and p=5, we get: >>> (1**3) % 51>>> (2**3) % 53>>> (3**3) % 52>>> (4**3) % 54 Thus {1,2,3,4} maps to {1,3,2,4}. But what about the reverse? Well, we need to use an inverse log modulo p function. With this, as in the RSA (Rivest Shamir Adleman) public key method we find a value for a^x (mod p) so that: x*y (mod PHI) = 1 and where PHI is (p-1). Now we compute: >>> pow(3,-1,4)3 So we can go ahead and now reverse and find the inverse log for {1,3,2,4} (mod 5): >>> pow(1,3,5)1>>> pow(3,3,5)2>>> pow(2,3,5)3>>> pow(4,3,5)4 And, so, we have reversed our modulo logarithm. Overall, the magic of PHI is at the core of the RSA method and where we can reverse the exponentiation operation. For this, we have a cipher of: C= M^e (mod N) and then can reverse with a value of d which is computed from: d = e^{-1} mod PHI and where PHI is (p-1)(q-1). We recover the message with: M=C^d (mod N) In this case, we actually have two prime numbers (p and q), and which are multiplied together to give the modulus (N). Conclusions And, so, all we need to constrain our mathematical operations on our groups is the (mod p) operation.