Quadratic Roots for a Modulo of a Prime of 5 (mod 8)

Public key encryption has a range of number theoretic problems, of which there is no actual proof of security [1]:

These are intractable at the current time with the right parameters. For example, RSA depends on FACTORING and RSAP. With this, if we have C= M^e (mod N), then it is difficult to determine M, even if we know C, e and N (RSAP). Also, since the modulus (N) is made up of two prime numbers (N=p.q), we also have FACTORING.

One of the number theoretic problems is SQROOT, we have the form of:

x²=a (mod N)

a is then the square root of a modulo N. For example, if N=32, we can have:

18²=4 (mod32)

Thus the square root of 18 modulo 32 is 4 — and which is known as the quadratic residue.

Overall, it is a hard problem to compute if N is a composite number, but can be computed efficiently if it is a prime number.

Square root modulo with a prime number

If we have the form of x²=a (mod p), we must find a value of x which results in a value of a (mod p). It is actually a difficult problem to solve. If a solution exists, the value of a is a quadratic residue (mod p). In modular arithmetic, this operation is equivalent to a square root of a number (and where x is the modular square root of a modulo p). In the following, we will try and solve for the value of x and also generate the Legendre symbol value [here].

There is also a special case, and where p is a prime number defined by p=5 (mod 8). This means that when we divide the prime number by eight, we get a remainder of 5. For example, if we divide 101 by 8 we get 12 remainder 5, and so 101 is a prime that gives 5 (mod 8). We can see this when we run Python:

Python 3.8.5 (tags/v3.8.5:580fbb0, Jul 20 2020, 15:43:08) [MSC v.1926 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> 101%8
5
>>> 397%8
5

Within public key encryption, one of the intractable problems is related to computing square roots in ℤn. For this we have x²=a(modp), and where a is the square root of x modulo p.

We can first determine if we have a root of x²=a(modp) by proving:

Next we compute:

If d=1 then

If d=p−1 then

The roots are then (r,−r).

The coding is [here]:

package main

import (
 "crypto/rand"
 "fmt"

 "math/big"
 "os"
 "strconv"
)

func main() {

 bits := 16
 aval:=60

 argCount := len(os.Args[1:])

 if argCount > 0 {
  bits, _ = strconv.Atoi(os.Args[1])
 }
 if argCount > 1 {
  aval, _ = strconv.Atoi(os.Args[2])
 }

 if bits < 3 {
  fmt.Printf("We need at least three bits")
 }

 a := big.NewInt(int64(aval))

 var p *big.Int
 p1 := new(big.Int)

 for {

  p, _ = rand.Prime(rand.Reader, int(bits)-1)
  p1.Set(p)
  res := new(big.Int).Mod(p1, big.NewInt(8))
  if res.Cmp(big.NewInt(5)) == 0 {

   break
  }

 }
 fmt.Printf("Random Prime (p=5 mod 8)= %v\n", p1)
 fmt.Printf("a=%s\n\n", a)

 // Determine if there is a root if a^{(p-1)/2==1 we have a root, 
 // else if equal to p-1 there is not one
 num:=new(big.Int).Sub(p1,big.NewInt(1))
 num=new(big.Int).Div(num,big.NewInt(2) )
 val:=new(big.Int).Exp(a,num,p1)

 if val.Cmp(new(big.Int).Sub(p1, big.NewInt(1))) ==0  {
  fmt.Printf("No root found (a^{(p-1)/2}=%s)",val)
  fmt.Printf("\nPlease try again with another prime number")
  return
 }


 d := new(big.Int).Sub(p1, big.NewInt(1))
 d = new(big.Int).Div(d, big.NewInt(4))
 d = new(big.Int).Exp(a,d,p1)

 fmt.Printf("d=%s", d)


 if d.Cmp(big.NewInt(1)) == 0 { 

  pow := new(big.Int).Add(p1,big.NewInt(3) )
  pow = new(big.Int). Div(pow,big.NewInt(8))

  r := new(big.Int).Exp(a,pow,p1)


  fmt.Printf("\nRoots: %s and -%s", r,r)


  checking:=new(big.Int).Mul(r,r)
  checking=new(big.Int).Mod(checking,p1)

  fmt.Printf("\n\nChecking: %s %s",checking, new(big.Int).Sub(p1,checking))


 } else if d.Cmp(new(big.Int).Sub(p1, big.NewInt(1))) == 0 {


  val_4a := new(big.Int).Mul(a, big.NewInt(4))

  val_2a := new(big.Int).Mul(a, big.NewInt(2))

  pow := new(big.Int).Sub(p1,big.NewInt(5) )
  pow = new(big.Int).Div(pow,big.NewInt(8) )

  r := new(big.Int).Exp(val_4a,pow,p1)

  r = new(big.Int).Mul(r, val_2a)

  r = new(big.Int).Mod(r,p1)

  fmt.Printf("\nRoots: %s and -%s", r,r)



  checking:=new(big.Int).Mul(r,r)
  checking=new(big.Int).Mod(checking,p1)

  fmt.Printf("\n\nChecking: %s %s",checking)

 } 

}

A sample run gives [here]:

Random Prime (p=5 mod 8)= 28621
a=61
d=28620
Roots: 18117 and -18117
Checking: 61 28560

If we do not have a root, we get the condition where a(p−1)/2=p−1 [here]:

Random Prime (p=5 mod 8)= 31469
a=61
No root found (a^{(p-1)/2}=31468)

Here is an example where we have a Blum integer, and where we use a prime number which is equal to 3 (mod 4):

Intractable Problems in Public Key: SQUARING

References

[1] Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (2018). Handbook of applied cryptography. CRC press.