# Modular Arithmetic

{% embed url="<https://cryptohack.org/courses/modular/course_details/>" %}

{% embed url="<https://brilliant.org/wiki/modular-arithmetic/>" %}

## 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](https://en.wikipedia.org/wiki/Euclidean_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.

{% embed url="<https://brilliant.org/wiki/greatest-common-divisor/>" %}

### Using Repititive Subtraction

{% embed url="<https://brilliant.org/wiki/greatest-common-divisor/#euclidean-algorithm-and-more>" %}

{% code lineNumbers="true" %}

```python
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))
```

{% endcode %}

### Using Modulo

{% embed url="<https://brilliant.org/wiki/euclidean-algorithm/#computing-the-greatest-common-divisor>" %}

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


print(gcd(66528, 52920))
```

### Using math.gcd()

```python
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.\
\
&#x20;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](https://web.archive.org/web/20230511143526/http://www-math.ucdenver.edu/~wcherowi/courses/m5410/exeucalg.html).

{% embed url="<https://brilliant.org/wiki/modular-arithmetic/#modular-arithmetic-multiplicative-inverses>" %}

{% code lineNumbers="true" %}

```python
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
```

{% endcode %}

***

## Modular Arithmetic 1

Calculate the following integers:

11 ≡ x mod 6&#x20;

8146798528947 ≡ y mod 17

The solution is the smaller of the two integers.

```python
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: <mark style="color:red;">1</mark>

{% hint style="info" %}
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;)$$
{% endhint %}

{% embed url="<https://brilliant.org/wiki/fermats-little-theorem/>" %}

***

## Modular Inverting

### Question

What is the inverse element: `3 * d ≡ 1 mod 13`?

### Using Fermat's Little Theorem

{% hint style="info" %}
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}$$
{% endhint %}

```python
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

```python
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()

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

print(inverse(3, 13))
```

***

## Quadratic Residues

{% embed url="<https://brilliant.org/wiki/quadratic-residues/>" %}

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

p = 29&#x20;

ints = \[14, 6, 11]

{% code lineNumbers="true" %}

```python
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]))
```

{% endcode %}

***

## Properties of Quadratic (Non-) Residues

Quadratic Residue \* Quadratic Residue = Quadratic Residue&#x20;

Quadratic Residue \* Quadratic Non-residue = Quadratic Non-residue&#x20;

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

***

## Legendre Symbol

### Definition

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

where,

(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p&#x20;

(a / p) = -1 if a is a quadratic non-residue mod p&#x20;

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

{% embed url="<https://mathcenter.oxford.emory.edu/site/math125/findingSquareRoots/>" %}

#### Formula for Finding Square Root

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

```python
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

```python
from sympy.ntheory import nthroot_mod

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

print(min(nthroot_mod(a, 2, p, True)))
```

### Tonelli-Shanks Algorithm Implementation

```python
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

<pre class="language-python"><code class="lang-python">from sage.rings.finite_rings.integer_mod import square_root_mod_prime

<strong>a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
</strong>p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161


print(square_root_mod_prime(Mod(a, p), p))
</code></pre>

***

## Chinese Remainder Theorem

{% embed url="<https://brilliant.org/wiki/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.

### 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`

```python
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

```python
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.

```python
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 = p*q*&#x20;

*c1 = (2*p + 3*q)\*\*e1 mod N*&#x20;

*c2 = (5*p + 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

```python
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) + '}')
```

{% hint style="info" %}
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`.
{% endhint %}

{% hint style="info" %}
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`:

1. **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`.
2. **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`.
3. **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`.
4. **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`.
5. **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`.
{% endhint %}
