Square root of a value modulo of a prime (\(p\)) and where \(p=5 \pmod 8\)
[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 using \(p = 5 \pmod 8\). 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 \(p\) is a prime number defined by \(p = 5 \pmod 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 \pmod 8\). We can see this when we run Python:
C:\python27\godir>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 \( \mathbb{Z}_n\). For this we have \(x^2=a \pmod p\), and where \(a\) is the square root of \(x\) modulo p.
We can first determine if we have a root of \(x^2=a \pmod p\) by proving:
\( a^{(p-1)/2}==1 \)
Next we compute:
\(d=a^{(p-1)/4} \pmod p\)
If \(d=1\) then \(r=a^{(p+3)/8} \pmod p\)
If \(d=p-1\) then \(r=2a{(4a})^{(p-5)/8} \pmod p\)
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, new(big.Int).Sub(p1,checking)) } }
A sample run gives:
< Random Prime (p=5 mod 8)= 28621 a=61 d=28620 Roots: 18117 and -18117 Checking: 61 28560
and:
Random Prime (p=5 mod 8)= 6573528512571103089839833580092364022797714854838570321851211852434447274380685678021617840450398098062017227741073404001190934680266920353607246246935613 a=61 d=6573528512571103089839833580092364022797714854838570321851211852434447274380685678021617840450398098062017227741073404001190934680266920353607246246935612 Roots: 317287091509758296649502983171072323027950673097237287778664232711406970193773792238233399620977848168945715075751678562088897474206694175337661055815100 and -317287091509758296649502983171072323027950673097237287778664232711406970193773792238233399620977848168945715075751678562088897474206694175337661055815100 Checking: 61
If we do not have a root, we get the condition where \(a^{(p-1)/2}=p-1\):
Random Prime (p=5 mod 8)= 31469 a=61 No root found (a^{(p-1)/2}=31468)
[1] Menezes, A. J., Van Oorschot, P. C., & Vanstone, S. A. (2018). Handbook of applied cryptography. CRC press.