[cryptohack.org] MODULAR ARITHMETIC

cryptohack을 공부하면서 얻은 지식들을 정리하려고 한다.

Greatest Common DIvisor

GCD 즉 최대공약수에 대한 내용이다. 유클리드 호제법을 이용해서 두 정수의 최대공약수를 구하라고 한다. 이전에 유클리드 호제법을 다루었던 적이 있다.

2024.07.18 - [BOJ/이론] - 유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기

유클리드 호제법과 최대공약수, 최소공배수 python으로 구현하기

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
print(gcd(66528,52920))

1512

Extended GCD

확장된 유클리드 알고리즘은 두 양의 정수 $a$,$b$가 있을때 베주 항등식이라 불리는 아래의 식에서 $u$,$v$의 값을 찾아내는 효율적인 방법이다.

$$ \displaystyle{\displaylines{a·u + b ·v = gcd(a,b)}} $$

자세한 내용은 이전에 다루었던 글을 참고하자.

2024.09.23 - [BOJ/이론] - Extended Euclidean Algorithm (확장된 유클리드 호제법)

Extended Euclidean Algorithm (확장된 유클리드 호제법)

def eea(a, b):
    x,y, u,v = 0,1, 1,0
    while b != 0:
        q, r = a//b, a%b
        m, n = x-u*q, y-v*q
        a,b, x,y, u,v = b,r, u,v, m,n
    gcd = a
    return gcd, x, y
    
print(eea(32321,26513))

-8404

Modular Arithmetic 1

모듈러 연산에 대해 설명해준다. $m$이 $a$로 나누어 떨어질때, $a|m$라고 표기하거나 $a\equiv 0\; mod\; m$이라고 표기할 수 있다. 아래의 식에서 $x,y$ 중에 더 작은 값을 넣어주면 된다. 

$$ 11\equiv x\; mod\; 6 $$

$$ 8146798528947\equiv y\; mod\; 17$$

4

Modular Arithmetic 2

이번엔 여러 용어들에 대해 설명해준다. $p$가 소수일때, 유한체 $\mathbb{F}_p$를 정의할 수 있는데, 이 유한체 $\mathbb{F}_p$는 $\{0, 1, 2, \ldots, p-1\} $의 원소들로 구성되어 있다. 또한 유한체의 모든 원소 $a$는 $a + b_+ = 0 \; ,\; a \cdot b_* = 1 $ 인 덧셈의 역원$(b_+)$과 곱셈의 역원$(b_*)$을 가진다.

---

$ 3^{17}\mod 17 $과 $ 5^{17}\mod 17$을 계산해보라고 한다. 이를 계산할때 페르마의 소정리를 이용할 수 있다.

페르마의 소정리는 아래과 같다.

$$ p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^p\equiv a\left({\rm mod}\ p\right) \text{이다.}$$

이는 동치인 아래의 정리로 바꿀 수 있다.

$$ p\text{가 소수이면, 모든 정수 }a\text{에 대해 } a^{p-1}\equiv 1\left({\rm mod}\ p\right) \text{이다.}$$

위 정리들을 이용해 문제에서 요구하는 $ 273246787654^{65536} \mod 65537 $을 계산해보자. 위의 두번째 정리와 같은 형태이고, 문제에서 $p$는 소수라고 주어졌기 때문에 계산이 필요 없이 답이 1인것을 구할 수 있다.

1

Modular Inverting

유한체 $\mathbb{F}_p$의 원소 중 하나인 $g$에 대해, $g \cdot d \equiv 1 \mod p$ 를 만족하는 유한체 내의 유일한 정수 $d$가 존재한다고 한다.

$ d=3^{-1}$의 역원, 즉  $3 \cdot d \equiv 1 \mod 13$을 만족하는 정수를 찾아보자.
위의 페르마의 소정리를 다음과 같이 변형할 수 있다. $ a \cdot a^{p-2}\equiv 1\left({\rm mod}\ p\right) $이므로, $ 3 \cdot 3^{13-2}\equiv 1\left({\rm mod}\ 13\right) $이라고 할 수 있다.

pow(3, 13-2, 13)

아래와 같이 간단하게 구할 수도 있다.

from Crypto.Util.number import inverse
inverse(3, 13)

9

Quadratic Residues

이번에는 모듈러 연산에서 제곱근에 대해 설명해준다. $p=29, a=11$일때, $a^2=5\mod 29$이므로 우리는 11을 5의 제곱근이라고 부를 수 있다. 이번에는 $a^2=18$일때를 알아보자. a=1부터 a=p-1까지 모두 생각해봐도,  $a^2=18$의 제곱근을 찾을 수 없다. 즉,  $F_p^{*} $의 모든 원소들이 제곱근을 가지는 것은 아니라는 것을 알 수 있다. 대략적으로, 유한체의 원소들 중 절반 정도가 제곱근을 가지지 않는다고 한다.

$a^2=x\mod p$인 $a$가 존재할 때, 우리는 $x$를 2차 잉여(Quadratic Residue)라고 한다. 반대로, $a^2=x\mod p$인 $a$가 존재하지 않을때, 그 정수를 2차 비잉여(Quadratic Non-Residue)라고 한다.

p=29, ints=[14,6,11]일때, ints 리스트 중에서 quadratic residue를 구하고 그것의 제곱근을 구하라고 한다. 제곱근이 여러개가 가능한 경우에는, 더 작은 것을 출력해야 한다.

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

qr = [a for a in range(p) if pow(a,2,p) in ints]
print(f"flag {min(qr)}")

8

Legendre Symbol

위처럼 p=29같이 숫자가 작을때는 하나하나 찾아봐도 괜찮지만, 숫자가 커지면 제곱근을 찾는데 시간이 굉장히 오래 걸릴 것이다. 다행히도, 단순한 계산으로 정수가 quadratic residue인지 확인할 수 있는 방법인 르장드르 기호(Legendre Symbol)가 있다.
르장드르 기호에 대해 알아보기 전에, quadratic residue에 관한 특이한 성질을 알아보자.

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

quadratic residue가 마치 +1과 -1의 연산처럼 작동한다!!

 

르장드르 기호는$\left( \frac{a}{p} \right) \equiv a^{\frac{p-1}{2}} \mod p$와 같이 나타내고, 다음과 같은 성질을 따른다.

1. a가 quadratic residue이고 $a \not\equiv 0 \mod p$이면 $\left( \frac{a}{p} \right) = 1$이다.
2. a가 quadratic non-residue이고 $a \not\equiv 0 \mod p$이면 $\left( \frac{a}{p} \right) = -1$이다.
3. $a \equiv 0 \mod p$이면 $\left( \frac{a}{p} \right) = 0$이다

이말은, $ a^{\frac{p-1}{2}} \mod p$를 계산하면 a가 quadratic residue인지 바로 판단할 수 있다는 것이다.

---

문제의 output.txt에서는 1024비트짜리 소수와 10개의 정수를 준다. 여기서 quadratic residue를 찾고 그것의 제곱근을 찾으면 된다.

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

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

quadratic resiude를 찾으면 $ a^{\frac{p-1}{2}} \equiv 1\mod p$일테니, 다음과 같이 변형해준다. 

$$ \left( \frac{a}{p} \right) = 1 \\
\left( \frac{a}{p} \right) \cdot a = a \\
a^{\frac{p - 1}{2}} \cdot a = a \\
a^{\frac{p + 1}{2}} \equiv a \mod p \\
\sqrt{a} \equiv a^{\frac{p + 1}{4}} \mod p $$

$ a^{\frac{p+1}{4}} \mod p$를 계산하면 a의 제곱근을 찾을 수 있다는 말이다!! 주의할 것은 $p\equiv 3 \mod 4$ 형태의 소수에만 가능하다는 것이다.

p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139

ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
roots = list()
for a in ints:
    if pow(a,(p-1)//2,p)==1:
        roots.append(pow(a,(p+1)//4,p))

print(max(roots))

93291799125366706806545638475797430512104976066103610269938025709952247020061090804870186195285998727680200979853848718589126765742550855954805290253592144209552123062161458584575060939481368210688629862036958857604707468372384278049741369153506182660264876115428251983455344219194133033177700490981696141526

Modular Square Root

이산 제곱근을 구하는 구하는 효율적인 또다른 방법은 Tonelli-shanks라고 불린다.

2를 제외한 모든 소수들은 $p\equiv 1 \mod 4$나 $p\equiv 3 \mod 4$의 형태로 나타난다. $p\equiv 3 \mod 4$ 형태의 소수는 이전 문제에서 봤듯이 페르마의 소정리로 간단하게 구할 수 있다. 하지만 $p\equiv 1 \mod 4$ 형태의 소수들은 구할 수 없기 때문에, 보다 일반적인 방법이 필요하다.

Tonelli-shanks는, $r^2 \equiv a \mod p$의 형태에서 r을 구할 수 있다. 주의할 것은, Tonelli-shanks는 합성수 모듈러에서는 작동하지 않는다는 것이다.

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161

Tonelli-shanks 알고리즘은 다음과 같이 사용할 수 이다. 직접 구현하려면 꽤나 복잡하다..

from sympy import *
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
print(sqrt_mod(a, p))

2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120

Chinese Remainder Theorem

중국인의 나머지 정리는, 다음과 같이 주어진 합등식에 대해 유일한 해를 구하게 해주는 방법이다.

$$\begin{align*}
x & \equiv a_1 \mod n_1 \\
x & \equiv a_2 \mod n_2 \\
& \vdots \\
x & \equiv a_n \mod n_n
\end{align*}$$

중국인의 나머지정리는 위의 합등식을 만족하는 유일한 해인 $x$가 있다는것을 증명해준다. $ x \equiv a \mod N \quad \text{where} \quad N = n_1 \cdot n_2 \cdots n_n$ 자세한 내용은 이전에 다루었던글을 참고하자.

2024.09.29 - [BOJ/이론] - 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)

중국인의 나머지 정리(Chinese Remainder Theorem, CRT)

def chinese_remainder_theorem(n, a):
    n.sort()
    max = n[-1]
    a3 = a[-1]
    for i in range(len(n)-2, -1, -1):
        for j in range(n[i]):
            if (max * j + a3) % n[i] == a[i]:
                a3 = max*j + a3
                max = n[i]*max
                break

    return a3,max
n = [5,11,17]
a = [2,3,5]
print(chinese_remainder_theorem(n,a))

872

Adrien's Signs

Adrien이 빼기 기호와 기호(르장드르 기호 말하는듯)을 사용해 그의 메세지를 암호화했다고 한다. sourse.py와 output.txt가 주어진다.

# output.txt : [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]


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

FLAG에서 한글자씩 2진수로 바꾸고 8자리로 채워서 plaintext에 저장한다. 1~p중에 무작위 정수를 뽑은 후, $a^e\mod p$ 의 결과를 n에 저장한다. plaintext(2진수)를 한자리씩 읽으면서 1이면  $a^e\mod p$ 그대로 append하고, 0이면  $-a^e\mod p$를 append한다.

문제를 풀때 뭐부터 해야할지 모르고 있다가 일단 문제에서 르장드르 기호를 쓰라고 힌트를 줬으니 a가 p의 이차 잉여인지 확인해봤다. $p\equiv 3\mod 4$이므로, 르장드르 기호를 적용할 수 있고, $ a^{\frac{p-1}{2}} \equiv 1\mod p$이었다. 여기서 중요한것은, 이차 잉여랑 이차 잉여랑 곱한 결과도 이차 잉여라는 것이다. 즉 $ a^{\frac{p-1}{2}}  \mod p$가 이차 잉여니까 $a^e\mod p$ 또한 이차 잉여이기 때문에 값이 1이 된다.   $-a^e\mod p$는 -1이 되므로 $= (-1)^{\frac{p - 1}{2}}$를 해보면 -1이 나온다.

결국, b가 1일때는 이차 잉여를, 0일때는 이차 비잉여를 append한 것이다. 르장드르 기호를 사용해서 output.txt에 있는 숫자들의 이차 잉여 여부를 판단해서 원래의 binary를 복구할 수 있을 것이다.

from Crypto.Util.number import *

en = [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]

a = 288260533169915
p = 1007621497415251

def is_re(a,p):
    return pow(a,(p-1)//2, p)

d = ''
for i in en:
    if is_re(i,p)==1:
        d += '1'
    else:
        d += '0'

print(long_to_bytes(int(d,2)))

crypto{p4tterns_1n_re5idu3s}

Modular Binomals

소수 $p,q$를 구하기 위해 다음 방정식을 사용하라고 한다.

$$ N = p \cdot q \\
c_1 = (2 \cdot p + 3 \cdot q)^{e_1} \mod N \\
c_2 = (5 \cdot p + 7 \cdot q)^{e_2} \mod N $$

어떻게 할지 모르겠어서 구글링을 해보다가, 재미있는 공식을 발견했다. 1학년의 꿈(Freshman's Dream)이라고 하는 등식인데, 

$$ (x+y)^n = x^n + y^n$$

위와 같은 등식이 특정 조건에서 성립하는데, 문제의 상황이 바로 이런 조건이다.

$$ (p+q)^n \mod n = p^n + nC1 \, p^{n-1} q + nC2 \, p^{n-2} q^2 + \cdots + nC(n-1) \, p \, q^{n-1} + q^n $$

이런 식으로 나타나는데, 처음과 마지막의 $ p^n $과$ q^n$을 제외한 중간의 항들은 p,q를 둘다 가지고 있으므로, 법 N에 대해여 0일 수 밖에 없다.

이제 주어진 식을 다음과 같이 변형할 수 있다.

$$ c_1 = (2p)^{e_1}+(3q)^{e_1} \bmod N \\
c_2 = (5p)^{e_2} + (7q)^{e_2} \bmod N $$

미지수가 2개인 연립 방정식을 풀듯이 미지수 하나를 소거해주자.

$$ c_1^{e_2} \equiv (2p)^{e_1e_2} + (3q)^{e_1e_2} \bmod N \\ c_2^{e_1} \equiv (5p)^{e_1e_2} + (7q)^{e_1e_2} \bmod N $$

다음과 같이 정리할 수 있다.

$$ 5^{e_1e_2}c_1^{e_2} -2^{e_1e_2}c_2^{e_1} \equiv (15^{e_1e_2}-14^{e_1e_2})q^{e_1e_2} \bmod N $$

이렇게 구한 $5^{e_1e_2}c_1^{e_2} -2^{e_1e_2}c_2^{e_1} $과 N의 최대공약수를 구한다면, 공통인수가 q 밖에 없을 것이기 때문에 q를 구할 수 있고, q를 구하면 p 또한 구할 수 있다.

import math

N = 14905562257842714057932724129575002825405393502650869767115942606408600343380327866258982402447992564988466588305174271674657844352454543958847568190372446723549627752274442789184236490768272313187410077124234699854724907039770193680822495470532218905083459730998003622926152590597710213127952141056029516116785229504645179830037937222022291571738973603920664929150436463632305664687903244972880062028301085749434688159905768052041207513149370212313943117665914802379158613359049957688563885391972151218676545972118494969247440489763431359679770422939441710783575668679693678435669541781490217731619224470152467768073
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
c1 = 14010729418703228234352465883041270611113735889838753433295478495763409056136734155612156934673988344882629541204985909650433819205298939877837314145082403528055884752079219150739849992921393509593620449489882380176216648401057401569934043087087362272303101549800941212057354903559653373299153430753882035233354304783275982332995766778499425529570008008029401325668301144188970480975565215953953985078281395545902102245755862663621187438677596628109967066418993851632543137353041712721919291521767262678140115188735994447949166616101182806820741928292882642234238450207472914232596747755261325098225968268926580993051
c2 = 14386997138637978860748278986945098648507142864584111124202580365103793165811666987664851210230009375267398957979494066880296418013345006977654742303441030008490816239306394492168516278328851513359596253775965916326353050138738183351643338294802012193721879700283088378587949921991198231956871429805847767716137817313612304833733918657887480468724409753522369325138502059408241232155633806496752350562284794715321835226991147547651155287812485862794935695241612676255374480132722940682140395725089329445356434489384831036205387293760789976615210310436732813848937666608611803196199865435145094486231635966885932646519
q_e1e2 = pow(5,e1*e2,N)*pow(c1,e2,N) - pow(2,e1*e2,N)*pow(c2,e1,N)
q = math.gcd(q_e1e2,N)
print(f'crypto{{{q},{N//q}}}')

crypto{132760587806365301971479157072031448380135765794466787456948786731168095877956875295282661565488242190731593282663694728914945967253173047324353981530949360031535707374701705328450856944598803228299967009004598984671293494375599408764139743217465012770376728876547958852025425539298410751132782632817947101601,112274000169258486390262064441991200608556376127408952701514962644340921899196091557519382763356534106376906489445103255177593594898966250176773605432765983897105047795619470659157057093771407309168345670541418772427807148039207489900810013783673957984006269120652134007689272484517805398390277308001719431273}

---

crypto의 기초가 되는 MODULAR ARITHMETIC 단원이 끝났다. 그동안 중구난방으로 흩어져있던 지식들을 차근차근 정리해 나가는 느낌이라 좋았고, 처음 보는 어려운 내용도 많았다. 하지만 덕분에 새로운 연산, 개념도 알게 되어서 여기저기 써먹을 수 있을 것 같다. 다음 단원인 SYMMETRIC CRYPTOCRAPHY 또한 열심히 공부해 보자.