Intractable Problems in Public Key: SQUARING

Public key encrytion 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 (mod 32)

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 [link]:

Quadratic residue (mod p)

There is also a special case, and where we use Blum integers. A Blum integer is created by multiplying up of two prime numbers (p and q) and where p=3 (mod 4) and q=3 (mod 4): n=p×q. Thus we take the prime numbers (p and q) and divide by four, and if we get an answer of 3, we have the required value. For example 7 is a possible value, as when we divide by four, we get 3. The possible prime numbers are then: 3, 7, 11, 19, and so on. The Blum integers then become: 21, 33, 57, 69, 77, 93, 129, 133, 141, 161, 177, 201, 209, 213, 217, 237, 249, ….

Within public key encryption, one of the intractable problems is related to computing square roots in ℤn. For this we have x²=a (mod p), and where a is the square root of x modulo p. If p is a prime number, the roots are computed with:

and where p=3 (mod 4). 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:=61
 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(4))
  if res.Cmp(big.NewInt(3)) == 0 {
   break
  }
  p.Add(p.Lsh(p, 1), big.NewInt(1))
 }

 fmt.Printf("Random Prime (p=3 mod 4)= %v\n", p1)
 fmt.Printf("a=%s\n\n", a)
 
 p2 := new(big.Int).Add(p1, big.NewInt(1))
 p2 = new(big.Int).Div(p2, big.NewInt(4))
 r := new(big.Int).Exp(a, p2, p1)
 fmt.Printf("Roots are %s and -%s\n\n", r, r)
 fmt.Printf("%s^2 = %s (mod %s)", r, a,p)
}

A sample run [here]:

Random Prime (p=3 mod 4)= 29443
a=61
Roots are 22751 and -22751
22751^2 = 61 (mod 29443)

In this case the roots are 22,751 and -22,751. If we take 227512 (mod 29443) we get 61. And:

Random Prime (p=3 mod 4)= 8857899395777239187
a=61
Roots are 3647187581037169671 and -3647187581037169671
3647187581037169671^2 = 61 (mod 8857899395777239187)

References

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