🔐 CryptoHack - Modular Arithmetic

Greatest Common Divisor#

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b).

For a=12,b=8 we can calculate the divisors of {1,2,3,4,6,12} and the divisors of {1,2,4,8}. Comparing these two, we see that gcd(a,b)=4.

Now imagine we take a=11,b=17. Both a and b are prime numbers. As a prime number has only itself and 1 as divisors, gcd(a,b)=1.

We say that for any two integers a,b, if gcd(a,b)=1 then a and b are coprime integers.

If a and b are prime, they are also coprime. If a is prime and b<a then a and b are coprime.

There are many tools to calculate the GCD of two integers, but for this task we recommend looking up Euclid’s Algorithm.

Try coding it up; it’s only a couple of lines. Use a=12,b=8 to test it.

Now calculate gcd(a,b) for a=66528,b=52920 and enter it below.

GCD

Solution :

1
# Function to return gcd of a and b
2
def gcd(a, b):
3
  if a == 0 :
4
      return b
5

6
  return gcd(b%a, a) # This will loop until a == 0
7

8
a = 66528
9
b = 52920
10
print("gcd(", a , "," , b, ") = ", gcd(a, b))

Extended GCD#

Let a and b be positive integers. The extended Euclidean algorithm is an efficient way to find integers u,v such that

1
a⋅u+b⋅v=gcd(a,b)

Using the two primes p=26513,q=32321, find the integers u,v such that

1
p⋅u+q⋅v=gcd(p,q)

Enter whichever of u and v is the lower number as the flag.

NOTE

Knowing that p,q are prime, what would you expect gcd(p,q) to be For more details on the extended Euclidean algorithm, check out this page

EGCD

Solution :

1
# Extended Euclidean Algorithm to find gcd and coefficients (u, v) such that:
2
# a*u + b*v = gcd(a, b)
3
def extended_gcd(a, b):
4
  # Base case: if a is 0, gcd is b, and the coefficients are (0, 1)
5
  if a == 0:
6
      return (b, 0, 1)
7
  else:
8
       # Recursively apply the extended Euclidean algorithm
9
      g, x, y = extended_gcd(b % a, a)
10
      return (g, y - (b // a) * x, x)
11

12
p = 26513
13
q = 32321
14

15
gcd, u, v = extended_gcd(p, q)
16
print("gcd:", gcd)
17
print("u:", u)
18
print("v:", v)

Modular Arithmetic 1#

Imagine you lean over and look at a cryptographer’s notebook. You see some notes in the margin:

At first you might think they’ve gone mad. Maybe this is why there are so many data leaks nowadays you’d think, but this is nothing more than modular arithmetic modulo 12 (albeit with some sloppy notation).

You may not have been calling it modular arithmetic, but you’ve been doing these kinds of calculations since you learnt to tell the time (look again at those equations and think about adding hours).

Formally, “calculating time” is described by the theory of congruences. We say that two integers are congruent modulo m if a ≡ b mod m. Another way of saying this, is that when we divide the integer a by m, the remainder is b. This tells you that if m divides a (this can be written as m∣a) then a ≡ 0 mod m.

Calculate the following integers:

1
11 ≡ x mod 6
2
8146798528947 ≡ y mod 17

The solution is the smaller of the two integers, (x,y), you obtained after reducing by the modulus.

MA1

Solution :

1
# First congruence
2
x = 11 % 6
3

4
# Second congruence
5
y = 8146798528947 % 17
6

7
# Output results
8
print("x =", x)
9
print("y =", y)
10
print("Smaller of the two =", min(x, y))

Modular Arithmetic 2#

We’ll pick up from the last challenge and imagine we’ve picked a modulus p, and we will restrict ourselves to the case when p is prime.

A finite field Fₚ is the set of integers 0, 1, ..., p − 1, and under both addition and multiplication, there are inverse elements b₊ and bₓfor every element a in the set, such that: a + b₊ = 0 and a · bₓ = 1

Let’s say we pick p = 17. Calculate 3¹⁷ mod 17. Now do the same but with 5¹⁷ mod 17.

What would you expect to get for 7¹⁶ mod 17 Try calculating that.

This interesting fact is known as Fermat's Little Theorem. We’ll be needing this (and its generalizations) when we look at RSA cryptography.

Now take the prime p = 65537. Calculate 27324678765⁴⁶⁵⁵³⁶ mod 65537.

Did you need a calculator

MA2

Solution :

1
# Fermat's Little Theorem demonstrations
2
p1 = 17
3

4
# 3^17 mod 17
5
res1 = pow(3, 17, p1)
6
print("3^17 mod 17 =", res1)
7

8
# 5^17 mod 17
9
res2 = pow(5, 17, p1)
10
print("5^17 mod 17 =", res2)
11

12
# 7^16 mod 17
13
res3 = pow(7, 16, p1)
14
print("7^16 mod 17 =", res3)
15

16
# Now using the large prime p = 65537
17
p2 = 65537
18
base = pow(27324678765, 4, p2)
19
res4 = pow(base, 65536, p2)
20
print("27324678765^4^65536 mod 65537 =", res4)
21

22
# This script shows that for a prime p and integer a not divisible by p:
23
# a^(p-1) ≡ 1 (mod p)
24
# Hence answer is 1

Modular Inverting#

Solution :

1
# Find d such that (3 * d) % 13 == 1
2

3
g = 3
4
p = 13
5

6
# Try each number from 1 to 12 to see which one gives (3 * d) % 13 = 1
7
for d in range(1, p):
8
  if (g * d) % p == 1:
9
      print(f"The modular inverse of {g} mod {p} is: {d}")
10
      break

Quadratic Residues#

Find the quadratic residue and then calculate its square root. Of the two possible roots, submit the smaller one as the flag.

1
p = 29 ints=[14, 6, 11]

Solution :

1
p = 29
2
numbers = [14, 6, 11]
3

4
# Loop through each number in the list
5
for x in numbers:
6
   # Try every number a from 1 to p-1
7
  for a in range(1, p):
8
      if (a * a) % p == x:
9
          # If found, x is a quadratic residue
10
          print(f"{x} is a square (quadratic residue) mod {p}")
11
          print(f"Square roots: {a} and {p - a}")
12
          print(f"Smaller root to submit as flag: {min(a, p - a)}")
13
          break
14
  else:
15
      print(f"{x} is NOT a square mod {p}")

Legendre Symbol#

Before looking at Legendre’s symbol, let’s take a brief detour to see an interesting property of quadratic (non-)residues:

1
Quadratic Residue * Quadratic Residue = Quadratic Residue
2
Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
3
Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue
4

5
Want an easy way to remember this Replace "Quadratic Residue" with +1 and "Quadratic Non-residue" with −1, all three results are the same!

1
Given an integer a and an odd prime p, the Legendre symbol (a/p) tells you:
2

3
(a/p) = 1 if a is a quadratic residue modulo p (i.e., there exists some x such that x² ≡ a mod p)
4

5
(a/p) = -1 if a is not a quadratic residue modulo p
6

7
(a/p) = 0 if a ≡ 0 mod p

Challenge file: Output.txt

Solution :

1
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
2

3
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
4

5
for a in ints:
6
    # Compute Legendre symbol
7
    legendre = pow(a, (p-1)//2, p)
8
    if legendre == 1:
9
        print(f"Found quadratic residue: {a}")
10

11
        sqrt_a = pow(a, (p+1)//4, p)
12

13
        # Pick the larger of the two roots
14
        root = max(sqrt_a, p - sqrt_a)
15

16
        print(f"Flag is: {root}")
17
        break

Modular Square Root#

MSR

1
def tonelli_shanks(a, p):
2
    """
3
    Find a square root of a mod p using the Tonelli-Shanks algorithm.
4
    p must be an odd prime.
5
    """
6

7
    # Step 1: Find Q and S such that p-1 = Q * 2^S
8
    S = 0  # Initialize S to 0
9
    Q = p - 1  # Start with Q = p-1
10
    while Q % 2 == 0:
11
        Q //= 2  # Keep dividing Q by 2 while it's even
12
        S += 1  # Count how many times 2 divides p-1
13

14
    # Step 2: Find a quadratic non-residue z
15
    # A quadratic non-residue z is a number such that z^(p-1)/2 ≡ -1 (mod p)
16
    z = 2  # Start from z = 2 and check if it's a quadratic non-residue
17
    while pow(z, (p - 1) // 2, p) != p - 1:  # z^(p-1)/2 mod p should be -1 (p-1 mod p)
18
        z += 1  # Increment z until a non-residue is found
19

20
    # Step 3: Initialize variables for the Tonelli-Shanks algorithm
21
    M = S  # Set M to S, which is the exponent of 2 in the factorization of p-1
22
    c = pow(z, Q, p)  # Compute c = z^Q mod p
23
    t = pow(a, Q, p)  # Compute t = a^Q mod p (this is used to track progress)
24
    R = pow(a, (Q + 1) // 2, p)  # Compute R = a^((Q+1)//2) mod p as the initial guess for the root
25

26
    # Step 4: Loop until t == 1, which means we have found a square root
27
    while t != 1:
28
        # Find the smallest i such that t^(2^i) ≡ 1 mod p
29
        i = 0  # Start the exponent count
30
        temp = t  # Use a temporary variable to check powers of t
31
        while temp != 1:
32
            temp = pow(temp, 2, p)  # Compute t^(2^i) mod p by squaring t
33
            i += 1  # Increment i (the exponent of 2)
34
            if i == M:  # If we have tried all possible exponents, no root exists
35
                return None  # No square root exists, so return None
36

37
        # Step 5: Update variables to improve the guess for the root
38
        b = pow(c, 2 ** (M - i - 1), p)  # Compute b = c^(2^(M-i-1)) mod p
39
        M = i  # Update M to the current value of i
40
        c = pow(b, 2, p)  # Update c = b^2 mod p (this helps in the next iteration)
41
        t = (t * c) % p  # Update t = t * c mod p (this moves us closer to 1)
42
        R = (R * b) % p  # Update R to the new value, refining the root approximation
43

44
    # When t becomes 1, R is the square root of a mod p
45
    return R  # Return the square root
46

47
# Given values for a and p
48
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
49
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
50

51
# Solve for the square root
52
sqrt_a = tonelli_shanks(a, p)
53

54
# Output the result
55
if sqrt_a is not None:
56
    # If a square root exists, print the smaller root (between sqrt_a and p - sqrt_a)
57
    smaller_root = min(sqrt_a, p - sqrt_a)
58
    print(f"Square root found! The smaller root is:\n{smaller_root}")
59
else:
60
    # If no square root exists, print a message
61
    print("No square root exists.")