The Day I “Got” Public Encryption Encryption … Here’s The Mod Root

The Day I “Got” Public Key Encryption … Here’s The Mod Root

The day that I really got public key cryptography was when I realised why we used prime numbers and the modulus operation. Basically, we could perform any maths operation we wanted, and could then reverse it. So we could add:

c = a + b (mod p)

and which has the same result as:

c = a (mod p) + b (mod p) (mod p)

We could then multiply and reverse it with a divide (which is known as an inverse mod). Basically, we have a ring caused by the prime number (p), and where the values go between 0 and p-1. The laws that we then create are the Identity, Associated and Commutative laws:

Identity Law
a + 0= 5
0 + a= 5

Associate Law
a+(b+c)= 15
(a+b)+c= 15

Commutative Law
a+b= 27
b+a= 27

Identity Law
a * 1= 6
1 * a= 6

Associate Law
a*(b*c)= 13
(a*b)*c= 13

Commutative Law
a*b= 24
b*a= 24

These laws are normal in our maths, and where a*b is the same as b*a. You can learn more here:

https://asecuritysite.com/principles_pub/rings

If you don’t know it, the (mod) operation is the remainder from an integer division, and in cryptography, we are typically only interested in the remainder.

So, what about the root of a value (mod p)?

In maths, you should know that:

and that the 3rd root of 8 is then 2:

But, in discrete methods, we need to solve the kth root of n modulo p and find the result:

For this, we need to find the value of k so that:

A few examples of these are [here]:

2nd root of 5 (mod 11) = 4
3rd root of 5 (mod 11) = 3
4th root of 5 (mod 11) = 2
5th root of 5 (mod 11) = None
6th root of 5 (mod 11) = 5
7th root of 5 (mod 11) = 4
8th root of 5 (mod 11) = 3
9th root of 5 (mod 11) = 9
10th root of 5 (mod 11) = None

Thus 4² (mod 11) is 16 (mod 11) and gives you 5. 3³ (mod 11) gives you 5, and 2⁴ (mod 11) you get 5. Notice, there are a few that do not give any roots, as there is no basic solution for that root.

Some simple code to search for the root is [here]:

import sys
def findnroot(x,n,p):
    for k in range(1,p):
        if (pow(k,n,p)==x):
            return(k)

p=17

n=2

if (len(sys.argv)>1):
    n=int(sys.argv[1])
if (len(sys.argv)>2):
    p=int(sys.argv[2])

for root in range(2,p):
    if (root>50): break
    v=findnroot(n,root,p)
    if (root==2): print(f"{root}nd root of {n} (mod {p}) = {v}")
    elif (root==3): print(f"{root}rd root of {n} (mod {p}) = {v}")
    else: print(f"{root}th root of {n} (mod {p}) = {v}")

And, so here is the code:

https://asecuritysite.com/principles_pub/kroot

Conclusions

So, I will leave you with this: