Cryptography Fundamentals 7: Quadratic residues Mod N

Demos These are: Quadratic residues: https://asecuritysite.com/primes/q_res Jacobi symbol: https://asecuritysite.com/primes/jac Jacobi and Legendre symbol: https://asecuritysite.com/primes/jacobi Introduction 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, gave us 121, or 196. Luckily, there was a convenient button on the calculator that give us our quick answer. In the time before calculators, though, working 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 have a 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 if 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, and 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! and: 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) 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, 52 A 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 52 In 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 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 sysimport libnumdef legendre_symbol(a, p): ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else lsn=11if (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-192Finding elliptic point closest to: 1Prime number: 6277101735386680763835789423207666416083908700390324961279a,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 mathimport sysimport libnumdef legendre_symbol(a, p): ls = pow(a, (p - 1) // 2, p) return -1 if ls == p - 1 else lsdef 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=-3b=41058363725152142129326129780047268409114441015993725554835256314039467401291startval=1type="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)