Square root of a value modulo of a prime (\(p\)) and where \(p=3 \pmod 4\)
[Primes Home][Home]
Within public key encryption, one of the intractable problems is related to computing square roots in \( \mathbb{Z}_n\). For this we have \(x^2=a \pmod p\), and where \(a\) is the square root of \(x\) modulo p. If \(p\) is a prime number, the roots are computed with \(r=a^{(p+1/4)} \pmod p \), and where \(p = 3 \pmod 4\). In this case, we will create a prime number which has a given number of bits. This is the quadratic residue.
|
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^2 = a \pmod N\)
a is then the square root of a modulo N. For example, if N=32, we can have:
\(18^2 = 4 \pmod {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^2=a \pmod 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 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 \( \mathbb{Z}_n\). For this we have \(x^2=a \pmod p\), and where \(a\) is the square root of \(x\) modulo p. If \(p\) is a prime number, the roots are computed with:
\(r=a^{(p+1/4)} \pmod p \)
and where \(p = 3 \pmod 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 } } fmt.Printf("Random Prime (p=3 mod 4)= %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 } 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) checking:=new(big.Int).Mul(r,r) checking=new(big.Int).Mod(checking,p1) fmt.Printf("\nChecking: %s %s",checking, new(big.Int).Sub(p1,checking)) }
A sample run:
Random Prime (p=3 mod 4)= 1990633327 a=61 Roots are 274916533 and -274916533 274916533^2 = 61 (mod 1990633327) Checking: 61 1990633266
[1] Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (2018). Handbook of applied cryptography. CRC press.