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.
Using Repititive Subtraction
defgcd(a,b):if a == b:return aif a > b:returngcd(a - b, b)if a < b:returngcd(a, b - a)print(gcd(84, 132))
Using Modulo
defgcd(a,b):return b if a % b ==0elsegcd(b, a % b)print(gcd(66528, 52920))
Using math.gcd()
from math import gcdprint(gcd(66528, 52920))
Extended GCD
Using the two primes p = 26513, q = 32321, find the integers u,v such that
p * u + q * v = gcd(p,q)
Enter whichever of u and v is the lower number as the flag.
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.
defextended_gcd(x,y):# Initializing Values a, b = x, yif y > x: a, b = y, x current_m, previous_m =0,1 current_n, previous_n =1,0while b !=0: q = a // b r = a % b m = current_m - previous_m * q n = current_n - previous_n * q a, b = b, r current_m, previous_m = previous_m, m current_n, previous_n = previous_n, n gcd = areturn gcd, current_m, current_n
Modular Arithmetic 1
Calculate the following integers:
11 ≡ x mod 6
8146798528947 ≡ y mod 17
The solution is the smaller of the two integers.
a =11%6b =8146798528947%17print(a if a < b else b)
Modular Arithmetic 2
Now take the prime p = 65537. Calculate 273246787654 ^ 65536 mod 65537.
Did you need a calculator?
Answer: 1
According to Fermat's Little Theorem,
If 'p' is a prime number and 'a' is a positive integer and not divisible by 'p', then
ap−1≡1(modp)
Modular Inverting
Question
What is the inverse element: 3 * d ≡ 1 mod 13?
Using Fermat's Little Theorem
We can derive an equation from the Fermat's Little Theorem, that gives the multiplicative inverse of 3 * d ≡ 1 mod 13. The derivation is given below:
ap−1≡1modp(Fermat′sLittleTheorem)
Multiplicatinga−1onbothsides
ap−1⋅a−1≡a−1modp
Rewritingap−1asap−2
ap−2⋅a⋅a−1≡a−1modp
ap−2≡a−1modp
The final implication:
ap−2≡a−1modp⟺ap−2modp=a−1
a =3p =13# You can use any method ** or pow to find the power.# Both is going to give the same result.# But using pow is more efficientprint(a**(p -2) % p)# orprint(pow(a, p-2, p))
Using Extended Euclidean Algorithm
defmultiplicative_inverse(x,y):# Using Extended Euclidean Algorithm / Extended GCD a, b = x, yif y > x: a, b = y, x t1, t2 =0,1while b !=0: q = a // b r = a % b t = t1 - t2 * q a, b = b, r t1, t2 = t2, tif y > x:return y + t1 # To get a Positive Valueelse:return x + t1 # To get a Positive Valueprint(multiplicative_inverse(7, 11))
(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a / p) = -1 if a is a quadratic non-residue mod p
(a / p) = 0 if a ≡ 0 mod p
Which means given any integer a, calculating pow(a, (p-1) // 2,p) is enough to determine if a is a quadratic residue.
Question
Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.
Formula for Finding Square Root
x≡±a(p+1)/4(modp)
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [ 25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803,
45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555,
17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325,
14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863,
4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318,
85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771,
50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987,
96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871,
4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721,
18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565
]for a in ints: legendre_symbol =pow(a, (p -1) //2, p)if legendre_symbol ==1:# Checking if Valid Residueprint(pow(a, (p +1) //4, p))# Finding the Positive Square Root
Modular Square Root
Find the square root of a modulo the 2048-bit prime p. Give the smaller of the two roots as your answer.
Using Sympy
from sympy.ntheory import nthroot_moda = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
print(min(nthroot_mod(a, 2, p, True)))
Tonelli-Shanks Algorithm Implementation
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
# Implementation of the Tonelli-Shanks algoritm as described at:# https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm# Determines if n is a quadratic residue of an# odd prime p by using Euler's criterion.defis_quadratic_residue(n,p):if n % p ==0:returnTruereturnpow(n, (p -1) //2, p)==1# Given an odd prime p and an integer n# This is an algorithm to find a mod-p square root of n when possible# Can delete all the print statements once its working.deftonelli_shanks(p,n):# Case when p|n, so n=0(mod p). The square root of 0 is 0.if n % p ==0:return0# So we can assume n is coprime to p, i.e. p does not divide n.# Use Euler's criteria to see if a solution exists or notifnotis_quadratic_residue(n, p):print("This value of n is not a quadratic residue.")returnNoneelse:print("This value of n is a quadratic residue.")# If p=3(mod 4) and we know n is a quadratic residue then# we can solve x^2=n(mod p) directlyif p %4==3:returnpow(n, (p +1) //4, p)# So now p=1(mod 4), (although this is not needed in the algorithm).# Write p - 1 = (2^S)(Q) where Q is odd Q = p -1 S =0while Q %2==0: S +=1 Q //=2# Find a quadratic non-residue of p by brute force search z =2whileis_quadratic_residue(z, p): z +=1# Initialize variables M = S c =pow(z, Q, p) t =pow(n, Q, p) R =pow(n, (Q +1) //2, p)while t !=1:# Calculate i i =0 temp = twhile temp !=1: i +=1 temp = (temp * temp) % p# Calculate b, M, c, t, R pow2 =2** (M - i -1) b =pow(c, pow2, p) M = i c = (b * b) % p t = (t * b * b) % p R = (R * b) % p# We have found a square rootreturn Rprint(tonelli_shanks(p, a))
Using Sage
from sage.rings.finite_rings.integer_mod import square_root_mod_primea = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
print(square_root_mod_prime(Mod(a, p), p))
Chinese Remainder Theorem
In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.
Given the following set of linear congruences:
x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17
Find the integer a such that x ≡ a mod 935
from math import proddefchinese_remainder_theorem(a_s:list,n_s:list):iflen(a_s)!=len(n_s):raiseValueError("There should be equal number of a's and n's") a =0 n =prod(n_s)for i, j inzip(a_s, n_s): n_i = n // j a += i * n_i *pow(n_i, j -2, j)# Modular Inverse Using Fermat's Little Theoremreturn a % nprint(chinese_remainder_theorem([2, 3, 5], [5, 11, 17]))
Adrien's Signs
Adrien's been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?
source.py - Given
from random import randinta =288260533169915p =1007621497415251FLAG =b'crypto{????????????????????}'defencrypt_flag(flag): ciphertext = [] plaintext =''.join([bin(i)[2:].zfill(8) for i in flag])for b in plaintext: e =randint(1, p) n =pow(a, e, p)if b =='1': ciphertext.append(n)else: n =-n % p ciphertext.append(n)return ciphertextprint(encrypt_flag(FLAG))
While the provided source.py script exponentiates the n value with random numbers, it's important to note that since a is a quadratic residue, its powers will also be quadratic residues. However, the script negates the sign of n when b is not equal to 1 (i.e., when b is 0). This implies that we can decode the 8-bit binary code by determining whether n is a quadratic residue. If it is, the function returns 1; otherwise, it returns 0. By doing this we can generate the binary string and then decode it to flag.
To get the values of p and q, we have to solve the given equations. First we have to make the equations exponentially same. To do that multiply equation [1] by 1e2 and equation [2] by 1e1, which results in the following form,
c1e2=(2×pe1.e2)+(3×qe1.e2)modN→[3]
c2e1=(5×pe1.e2)+(7×qe1.e2)modN→[4]
Now to get the value of q, we have to eliminate p from equations [3] and [4]. To do that multiply equation [3] by and equation [4] by 2e1.e2.
Modular Property: Both expressions represent congruences modulo N, the modulus. So, we're ensuring that the arithmetic operations stay within the range of integers modulo N.
Exponential Terms: Each term involving 5, c_1, 2, and c_2 is raised to an exponent. In the first expression, 5e1⋅e2 means 5 raised to the power of e1⋅e2, and similarly for the others. In the second expression, pow(c1, e2, N) calculates c1e2modN, and so forth. These are equivalent computations modulo N.
Subtraction of Terms: In both expressions, there's a subtraction operation between two terms.
GCD Calculation: The gcd function calculates the greatest common divisor of the difference between the two terms and N. This operation ensures that we're finding the greatest common divisor within the modular arithmetic context.
In summary, both expressions represent the same mathematical operation: finding the greatest common divisor of a certain expression and N, where the expression involves exponentiation modulo N.
Why are we taking the mod n on each term in the equation c1e2×5e1⋅e2−c2e1×2e1⋅e2?
Taking the modulo N of each term in Equation c1e2×5e1⋅e2−c2e1×2e1⋅e2 is essential because it ensures that the arithmetic operations stay within the range of integers modulo N. This practice is common in cryptographic operations, particularly in modular arithmetic used in RSA encryption and related algorithms.
Here's why each term is taken modulo N:
pow(c1, e2, N): This computes c1e2modN. Taking the exponentiation modulo N ensures that the result stays within the range of 0 to N-1.
pow(5, e1 * e2, N): This computes 5e1⋅e2modN. Again, this ensures that the result remains within the range of integers modulo N.
pow(c2, e1, N): This computes c2e1modN. Similar to the previous terms, taking the exponentiation modulo N ensures that the result is within the range of integers modulo N.
pow(2, e1 * e2, N): This computes 2e1⋅e2modN, ensuring the result remains within the range of integers modulo N.
gcd(..., N): Finally, the gcd function is applied to the difference of the two terms, followed by taking modulo N. This ensures that the final result, the greatest common divisor, is also within the range of integers modulo N.
Taking each term modulo N is crucial for maintaining the correctness and security of cryptographic operations, preventing arithmetic overflow, and ensuring that the computations are performed within the finite field defined by N.