Modular Arithmetic

CryptoHack – Modular Arithmetic -CryptoHack

Modular Arithmetic | Brilliant Math & Science Wikibrilliantorg

Greatest Common Divisor

Question

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.

Greatest Common Divisor | Brilliant Math & Science Wikibrilliantorg

Using Repititive Subtraction

Greatest Common Divisor | Brilliant Math & Science Wikibrilliantorg

def gcd(a, b):
    if a == b:
        return a
    if a > b:
        return gcd(a - b, b)
    if a < b:
        return gcd(a, b - a)


print(gcd(84, 132))

Using Modulo

Euclidean Algorithm | Brilliant Math & Science Wikibrilliantorg

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)


print(gcd(66528, 52920))

Using math.gcd()

from math import gcd

print(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.

Modular Arithmetic | Brilliant Math & Science Wikibrilliantorg

def extended_gcd(x, y):
    # Initializing Values
    a, b = x, y
    if y > x:
        a, b = y, x
    current_m, previous_m = 0, 1
    current_n, previous_n = 1, 0

    while 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 = a

    return 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 % 6
b = 8146798528947 % 17

print(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

$a^{p-1} \equiv 1 \;\;(\;mod\;\;p\;)$

Fermat's Little Theorem | Brilliant Math & Science Wikibrilliantorg

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:

$a^{p-1} \equiv 1 \mod p\;(\;Fermat's\;Little\;Theorem\;)$

$Multiplicating\;a^{-1}\;on\;both\;sides$

$a^{p-1} \cdot a^{-1} \equiv a^{-1} \mod p$

$Rewriting\;a^{p-1}\;as\;a^{p-2}$

$a^{p-2} \cdot a \cdot a^{-1} \equiv a^{-1} \mod p$

$a^{p-2} \equiv a^{-1} \mod p$

The final implication:

$a^{p-2} \equiv a^{-1} \mod p \iff a^{p-2} \mod p = a^{-1}$

a = 3
p = 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 efficient
print(a**(p - 2) % p)
# or
print(pow(a, p-2, p))

Using Extended Euclidean Algorithm

def multiplicative_inverse(x, y):
    # Using Extended Euclidean Algorithm / Extended GCD
    a, b = x, y
    if y > x:
        a, b = y, x

    t1, t2 = 0, 1

    while b != 0:
        q = a // b
        r = a % b
        t = t1 - t2 * q

        a, b = b, r
        t1, t2 = t2, t

    if y > x:
        return y + t1  # To get a Positive Value
    else:
        return x + t1  # To get a Positive Value


print(multiplicative_inverse(7, 11))

Using Crypto.Util.number.inverse()

# pip install pycryptodome
from Crypto.Util.number import inverse

print(inverse(3, 13))

Quadratic Residues

Quadratic Residues | Brilliant Math & Science Wikibrilliantorg

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

p = 29

ints = [14, 6, 11]

from math import gcd

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

print(min([i for i in range(1, p) if gcd(i, p) == 1 and pow(i, 2, p) in ints]))

Properties of Quadratic (Non-) Residues

Quadratic Residue * Quadratic Residue = Quadratic Residue

Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue

Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue

Legendre Symbol

Definition

where,

(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.

Finding Square Roots

Formula for Finding Square Root

$x \equiv \pm a^{(p+1)/4}\pmod{p}$

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 Residue
        print(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_mod

a = 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.
def is_quadratic_residue(n, p):
    if n % p == 0:
        return True
    return pow(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.
def tonelli_shanks(p, n):
    # Case when p|n, so n=0(mod p). The square root of 0 is 0.
    if n % p == 0:
        return 0

    # 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 not
    if not is_quadratic_residue(n, p):
        print("This value of n is not a quadratic residue.")
        return None
    else:
        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) directly
    if p % 4 == 3:
        return pow(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 = 0
    while Q % 2 == 0:
        S += 1
        Q //= 2

    # Find a quadratic non-residue of p by brute force search
    z = 2
    while is_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 = t
        while 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 root
    return R


print(tonelli_shanks(p, a))

Using Sage

from sage.rings.finite_rings.integer_mod import square_root_mod_prime

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161


print(square_root_mod_prime(Mod(a, p), p))

Chinese Remainder Theorem

Chinese Remainder Theorem | Brilliant Math & Science Wikibrilliantorg

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.

Formula

$X = a\;mod\;N$

where,

$N = n_{1}\;\times\;n_{2}\;\times\;n_{3}\;...\;n_{i}$

$N_{i} = \frac{N}{n_{i}}$

$a = a_{1}N_{1}N_{1}^{-1}\;+\;a_{2}N_{2}N_{2}^{-1}\;+\;a_{3}N_{3}N_{3}^{-1}\;...\;a_{i}N_{i}N_{i}^{-1}$

Question

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 prod


def chinese_remainder_theorem(a_s: list, n_s: list):
    if len(a_s) != len(n_s):
        raise ValueError("There should be equal number of a's and n's")

    a = 0
    n = prod(n_s)

    for i, j in zip(a_s, n_s):
        n_i = n // j
        a += i * n_i * pow(n_i, j - 2, j)  # Modular Inverse Using Fermat's Little Theorem

    return a % n


print(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 randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'


def encrypt_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 ciphertext


print(encrypt_flag(FLAG))

output.txt - Given

[67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]

Solution

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.

a = 288260533169915
p = 1007621497415251

cipher_text = [67594220461269, 501237540280788, 718316769824518, 296304224247167, 48290626940198, 30829701196032, 521453693392074, 840985324383794, 770420008897119, 745131486581197, 729163531979577, 334563813238599, 289746215495432, 538664937794468, 894085795317163, 983410189487558, 863330928724430, 996272871140947, 352175210511707, 306237700811584, 631393408838583, 589243747914057, 538776819034934, 365364592128161, 454970171810424, 986711310037393, 657756453404881, 388329936724352, 90991447679370, 714742162831112, 62293519842555, 653941126489711, 448552658212336, 970169071154259, 339472870407614, 406225588145372, 205721593331090, 926225022409823, 904451547059845, 789074084078342, 886420071481685, 796827329208633, 433047156347276, 21271315846750, 719248860593631, 534059295222748, 879864647580512, 918055794962142, 635545050939893, 319549343320339, 93008646178282, 926080110625306, 385476640825005, 483740420173050, 866208659796189, 883359067574584, 913405110264883, 898864873510337, 208598541987988, 23412800024088, 911541450703474, 57446699305445, 513296484586451, 180356843554043, 756391301483653, 823695939808936, 452898981558365, 383286682802447, 381394258915860, 385482809649632, 357950424436020, 212891024562585, 906036654538589, 706766032862393, 500658491083279, 134746243085697, 240386541491998, 850341345692155, 826490944132718, 329513332018620, 41046816597282, 396581286424992, 488863267297267, 92023040998362, 529684488438507, 925328511390026, 524897846090435, 413156582909097, 840524616502482, 325719016994120, 402494835113608, 145033960690364, 43932113323388, 683561775499473, 434510534220939, 92584300328516, 763767269974656, 289837041593468, 11468527450938, 628247946152943, 8844724571683, 813851806959975, 72001988637120, 875394575395153, 70667866716476, 75304931994100, 226809172374264, 767059176444181, 45462007920789, 472607315695803, 325973946551448, 64200767729194, 534886246409921, 950408390792175, 492288777130394, 226746605380806, 944479111810431, 776057001143579, 658971626589122, 231918349590349, 699710172246548, 122457405264610, 643115611310737, 999072890586878, 203230862786955, 348112034218733, 240143417330886, 927148962961842, 661569511006072, 190334725550806, 763365444730995, 516228913786395, 846501182194443, 741210200995504, 511935604454925, 687689993302203, 631038090127480, 961606522916414, 138550017953034, 932105540686829, 215285284639233, 772628158955819, 496858298527292, 730971468815108, 896733219370353, 967083685727881, 607660822695530, 650953466617730, 133773994258132, 623283311953090, 436380836970128, 237114930094468, 115451711811481, 674593269112948, 140400921371770, 659335660634071, 536749311958781, 854645598266824, 303305169095255, 91430489108219, 573739385205188, 400604977158702, 728593782212529, 807432219147040, 893541884126828, 183964371201281, 422680633277230, 218817645778789, 313025293025224, 657253930848472, 747562211812373, 83456701182914, 470417289614736, 641146659305859, 468130225316006, 46960547227850, 875638267674897, 662661765336441, 186533085001285, 743250648436106, 451414956181714, 527954145201673, 922589993405001, 242119479617901, 865476357142231, 988987578447349, 430198555146088, 477890180119931, 844464003254807, 503374203275928, 775374254241792, 346653210679737, 789242808338116, 48503976498612, 604300186163323, 475930096252359, 860836853339514, 994513691290102, 591343659366796, 944852018048514, 82396968629164, 152776642436549, 916070996204621, 305574094667054, 981194179562189, 126174175810273, 55636640522694, 44670495393401, 74724541586529, 988608465654705, 870533906709633, 374564052429787, 486493568142979, 469485372072295, 221153171135022, 289713227465073, 952450431038075, 107298466441025, 938262809228861, 253919870663003, 835790485199226, 655456538877798, 595464842927075, 191621819564547]

decoded_flag = ['1' if pow(each, (p - 1) // 2, p) == 1 else '0' for each in cipher_text]

print(''.join([chr(int(''.join(decoded_flag[i:i + 8]), 2)) for i in range(0, len(decoded_flag), 8)]))

Modular Binomials

Rearrange the following equations to get the primes p,q

N = pq

c1 = (2p + 3q)**e1 mod N

c2 = (5p + 7*q)**e2 mod N

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

Explanation

$Given,$

$N = p \times q$

$c_1 = ((\;2 \times p\;) + (\;3 \times q\;))^{e_1}\;mod\;N \rightarrow [1]$

$c_2 = ((\;5 \times p\;) + (\;7 \times q\;))^{e_2}\;mod\;N \rightarrow [2]$

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 $1^{e_2}$ and equation [2] by $1^{e_1}$ , which results in the following form,

$c_1^{e_2} = (\;2 \times p^{e_1 . e_2}\;) + (\;3 \times q^{e_1 . e_2}\;)\;mod\;N \rightarrow [3]$

$c_2^{e_1} = (\;5 \times p^{e_1 . e_2}\;) + (\;7 \times q^{e_1 . e_2}\;)\;mod\;N \rightarrow [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 $2^{e_1.e_2}$ .

$5^{e1.e2} \times c_1^{e_2} \equiv (\;10^{e_1 . e_2} \times p^{e_1 . e_2}\;) + (\;15^{e_1 . e_2} \times q^{e_1 . e_2}\;)\;mod\;N \rightarrow [5]$

$2^{e1.e2} \times c_2^{e_1} \equiv (\;10^{e_1 . e_2} \times p^{e_1 . e_2}\;) + (\;14^{e_1 . e_2} \times q^{e_1 . e_2}\;)\;mod\;N \rightarrow [6]$

Multiply eqution [6] with -, which results in the following equation,

$-\;2^{e1.e2} \times c_2^{e_1} \equiv -\;(\;10^{e_1 . e_2} \times p^{e_1 . e_2}\;) - (\;14^{e_1 . e_2} \times q^{e_1 . e_2}\;)\;mod\;N \rightarrow [7]$

Solving equations [5] and [7], we get,

$(\;5^{e1.e2} \times c_1^{e_2}\;)\; - (\;2^{e1.e2} \times c_2^{e_1}\;) \equiv (\;15^{e_1 . e_2} \times q^{e_1 . e_2}\;) - (\;14^{e_1 . e_2} \times q^{e_1 . e_2}\;)\;mod\;N$

$(\;5^{e1.e2} \times c_1^{e_2}\;)\; - (\;2^{e1.e2} \times c_2^{e_1}\;) \equiv q^{e_1 . e_2} \;\times \;(\;15^{e_1 . e_2}\;-\; 14^{e_1 . e_2}\;)\;mod\;N \rightarrow [8]$

From equation [8], we can get q by the following steps:

If a congruence holds modulo a product of two integers, it holds modulo each integer.
The right-hand side of the congruence is a multiple of q, so the expression $c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}$ is also a multiple of q.
N is a multiple of q, meaning q is a divisor of both the expression and N.
The only divisors of N are 1, p, q, and N. Since q divides only N and N, it's highly likely that $\text{gcd}(c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}, N)$ is q, not N.
There's no particular reason for p to divide $c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}$ , making it very unlikely that $\text{gcd}$ would be N.
Therefore, it's highly probable that $\text{gcd}(c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}, N)$ equals q.

After getting q, we can get p by $p = \frac{n}{q}$ , which we derived from the given, .

Solution

from math import gcd

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519

q = gcd((pow(c1, e2, N) * pow(5, e1 * e2, N)) - (pow(c2, e1, N) * pow(2, e1 * e2, N)), N)
p = N // q

print('crypto{' + str(p) + ',' + str(q) + '}')

Why gcd((pow(c1, e2, N) * pow(5, e1 * e2, N)) - (pow(c2, e1, N) * pow(2, e1 * e2, N)), N)?

The equation

\text{gcd}(c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}, N)

is equivalent to the expression

gcd((pow(c1, e2, N) * pow(5, e1 * e2, N)) - (pow(c2, e1, N) * pow(2, e1 * e2, N)), N)

Here's why:

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, $5^{e_1 \cdot e_2}$ means 5 raised to the power of $e_1 \cdot e_2$ , and similarly for the others. In the second expression, pow(c1, e2, N) calculates $c_1^{e_2} \mod N$ , 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 $c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}$ ?

Taking the modulo N of each term in Equation $c_1^{e_2} \times 5^{e_1 \cdot e_2} - c_2^{e_1} \times 2^{e_1 \cdot e_2}$ 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 $c_1^{e_2} \mod N$ . 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 $5^{e_1 \cdot e_2} \mod N$ . Again, this ensures that the result remains within the range of integers modulo N.
pow(c2, e1, N): This computes $c_2^{e_1} \mod N$ . 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 $2^{e_1 \cdot e_2} \mod N$ , 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.

PreviousIntroduction to CryptoHack NextSymmetric Cryptography

Last updated 1 year ago

Was this helpful?