Cryptography Fundamentals 7: Quadratic residues Mod N
Remember at school that class where the teacher taught you about how to square something? It was great, and where we loved to take the square of 3 and get 9, and the square of 5 gave us 25. But, in the next lesson, we came back to earth with a bump, as it was time for the nasty little square root. Now, we have to find two numbers which, when multiplied together, give us 121, or 196. Luckily, there was a convenient button on the calculator that gave us our quick answer. In the time before calculators, though, to work out more complex square roots involved tables of logarithms. And, so, in this podcast, I will outline a difficult problem … find a square root in a modulo n world … aka quadratic residues.
A hard problem
In cryptography, we look for hard problems to solve. For this, we can create a backdoor into the problem and solve the problem. With discrete logarithms we use the hard problem of:
Y=g^x (mod p)
and where it is difficult to determine x, even though we know g, Y and p, but as long as the prime number is large enough. Another hard problem is used in the RSA public key method, and this involves the difficulty in factorization at modulus (N), which is made up of two prime numbers.
Another hard problem is quadratic residues modulus n, which uses the form of:
x²=a (mod p)
and where we must find a value of x which results in a value of a (mod p). If a solution exists, the value of a is a quadratic residue (mod n).
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.
For example, if we have a=969 and p=1223, we get:
Solve x²=968 (mod 1223) [Ans: 453] Try!
Another example:
Solve x²=1203 (mod 1223) [Ans: 375] Try!
Thus 968 and 1203 are quadratic residues modulo 1223.
The form of x²=a (mod p) is not always solvable. For example, if we have a=209 and p=1223 , we get:
x²=209 (mod 1223)
and which does not have a solution. Also, if a shares a factor with p it is also not solvable. For example:
x²=39 (mod 13)
will return a zero value for x.
If we take a value of p=53, we get the following values [here]:
0, 1, 4, 6, 7, 9, 10, 11, 13, 15, 16, 17, 24, 25, 28, 29, 36, 37, 38, 40, 42, 43, 44, 46, 47, 49, 52A sample run of the code gives:
Quadradic residue (mod n) solver
a: 47
p: 53We need to solve for:
val^2 = 47 (mod 53 )
-----------------------
Result: 10
( 10 )^2 = 47 (mod 53 )-----------------------
For a prime number of 53 here are the residues up to p (or 100)
1 4 6 7 9 10 11 13 15 16 17 24 25 28 29 36 37 38 40 42 43 44 46 47 49 52In this case we see that 10 is a possible quadratic residue for a p of 53. The solution is thus:
10²=47 (mod 53)
You can see a demonstration here and here are some examples:
- Solve x²=12 (mod 13) [Ans: 8] Try!
- Solve x²=968 (mod 1223) [Ans: 453] Try!
- Solve x²=1203 (mod 1223) [Ans: 375] Try!
- Solve x²=47 (mod 53) [Ans: 10] Try!
- Solve x²=209 (mod 1223) [No solution!] Try!
- Solve x²=888 (mod 1223) [No solution!] Try!
- Solve x²=39 (mod 13) [No solution!] Try!
Legendre (Le-jon-dra) symbol
In science, it is difficult to avoid Adrien-Marie Legendre, as there are so many things named after him: Fourier–Legendre series; Gauss–Legendre algorithm; Legendre chi function; Legendre duplication formula; Legendre–Papoulis filter; Legendre form; Legendre polynomials; Legendre sieve; Legendre symbol; Legendre transformation; Legendre wavelet; Legendre–Clebsch condition; Legendre–Fenchel transformation; Legendre’s constant; Legendrian knot; and Gamma function–Legendre formula.
And, so, where does Legedre help with your online security? Well, you will find his method used in elliptic curve methods, which are used to protect your online identity and the security of the communications that you have with this Web page. So, let’s look at the Legendre Symbol.
For this, we turn to Legendre, who, in 1798, defined the Legendre symbol. In the following, we will try and solve for the value of x, and also generate the Legendre symbol value [link]:
Solve x²=12 (mod 13)
With his method, we can determine that the answer is 8, as 64 (mod 13) is 12. Some sample code is [here]:
import sys
import libnum
def legendre_symbol(a, p):
ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
n=11
if (len(sys.argv)>1):
n=int(sys.argv[1])
print ("Here are the Z*p (quadratic residues modulo n and coprime to n):")
print ("\nJacobi symbol")
for a in range(1, n):
rtn= libnum.jacobi(a,n)
if (rtn==1):
print (a,end=', ')
print ("\nLegendre symbol")
for a in range(1, n):
rtn= legendre_symbol(a,n)
if (rtn==1):
print (a,end=', ')A quadratic residue relates to the solving of the form: y=x² (mod n), and where we need to find values of y for different values of x, and for a given modulus (n). For n=11, we get Z∗p={1, 3, 4, 5, 9}. This is because, 1² (mod11)=1, 2² (mod11)=4, 3² (mod11)=9, 4² (mod11)=5, 5² (mod11)=3, 6² (mod11)=3, 7² (mod11)=5, 8² (mod11)=9, 9² (mod11)=4, and 10² (mod11)=1.
To find the quadratic residues for a given modulus, we can use the Jacobi symbol is:
and is defined as:
The legendre_symbol returns:
- 1. When a is a quadratic residue of p.
- -1. When a is a quadratic nonresidue of p.
- 0. When a shares a factor of p.
The Jacobi symbol was defined by Carl Gustav Jacob Jacobi as a generalized form of the Legendre symbol.
Elliptic Curves
While we have a trivial example here, we can use it for more complex ones, such as finding a point on the elliptic curve [here]. A sample run is:
Elliptic curve is: P-192
Finding elliptic point closest to: 1
Prime number: 6277101735386680763835789423207666416083908700390324961279
a,b -3 2455155546008943817740293915197451784769108058161191238065
(2, 1126956676167578795924565825825899020268914906345645360775L)
(3, 2476168101441297080746512578325117519920374855425678540834L)
(5, 936760824408609109609580731987662341845728162027345586443L)
(6, 61374494507529673497365598443020935064779457192199494327L)
(8, 1539168359597512271047259505090133446672063593980132990812L)
(12, 3464753203279792192409824182683870253677262339932562461307L)
(13, 3288234558942609973454802567986887155175778959720199156770L)
(15, 4548834217212027584647316131131523554591911664904227806291L)
(17, 2148916484007672061843886225501299518817815267521173400039L)
(18, 1600977792967480259538850281480651298625682822208237361467L)
(22, 1682016893107185458056834822961338463540516386180178478778L)The code for this is [here]:
import math
import sys
import libnumdef legendre_symbol(a, p): ls = pow(a, (p - 1) // 2, p)
return -1 if ls == p - 1 else ls
def findit(start,p,a,b):
x=start
count=0
while True:
val=((x*x*x) + a*x+ b) % p
rtn= legendre_symbol(val, p)
if (rtn==1):
if (libnum.has_sqrtmod(val,{p: 1})):
res=next(libnum.sqrtmod(val,{p: 1}))
print(x,int(res))
count=count+1
x=x+1
if (count>20):
return
if (x-start>200):
returnp = 2**256 - 2**224 + 2**192 + 2**96 - 1
a=-3
b=41058363725152142129326129780047268409114441015993725554835256314039467401291
startval=1
type="P-192"if (len(sys.argv)>1):
startval=int(sys.argv[1])if (len(sys.argv)>2):
type=str(sys.argv[2])if (type=="P-192"):
p = 2**192-2**64-1
a=-3
b=2455155546008943817740293915197451784769108058161191238065if (type=="P-224"):
b=18958286285566608000408668544493926415504680968679321075787234672564
p = 2**224 - 2**96 + 1
a=-3if (type=="P-256"):
p = 2**256 - 2**224 + 2**192 + 2**96 - 1
a=-3
b=41058363725152142129326129780047268409114441015993725554835256314039467401291if (type=="P-384"):
a=-3
b=27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575
p = 2**384 - 2**128 - 2**96 + 2**32 - 1 if (type=="Curve25519"):
a=486662
b=1
p = 2**255 - 19 if (type=="secp256k1"):
a=0
b=7
p = 2**256 - 2**32 - 977 if (type=="M-221"):
a=117050
b=1
p = 2**221 - 3 if (type=="BN(2,254)"):
a=0
b=2
p = 16798108731015832284940804142231733909889187121439069848933715426072753864723 if (type=="M-383"):
a=2065150
b=1
p = 2**383 - 187
print("Elliptic curve is:\t\t",type)
print("Finding elliptic point closest to:\t",startval)
print("Prime number:\t\t\t",p)
print("a,b",a,b)
findit(startval,p,a,b)
