From Cryptohack.org
- course 2 ( MODULAR ARITHMETIC ) -
이번에는 본격적으로 Quadratic residue, Legendre symbol 에 대해서 알아보도록 하자.
< 6 >
Quadratic residue, 즉 2차 잉여는 간단히 말해서 mod 에서 제곱수로 나타낼 수 있는 모든 수를 말한다. 예를 들어서 mod 11 을 살펴보자면, 5 라는 수를 제곱하면 mod 11 에서 3 이 된다. 따라서 3 은 mod 11 에서 Quadratic residue 가 되는 것이다.
다른 말로는, 2차 잉여는 항상 mod p 에 대해서 제곱근을 가진다고도 말할 수 있겠다.
이번 문제에서는 p 가 29 라는 전제로, 다음 ints 중에서 quadratic residue 를 찾는 것이다. P 가 그렇게 크지 않으니, brute force 방법으로 전수조사를 하는 것이 좋겠다.
코드를 작성해보자.
p = 29
ints = [14, 6, 11]
for i in ints:
for j in range(p):
if pow(j,2,p) == i:
print(f"{i} is a quadratic residue !!")
실행해보면
6 is a quadratic residue !!
6 is a quadratic residue !!
라는 결과가 나온다.
그런데, 왜 print 가 2번이나 될까?? 그 이유는 mod 의 성질에 기인한다. mod p 에서 -a 와 a 는 제곱했을 때 같은 a^2 의 값을 가지기에 항상 quadratic residue 는 2개씩 제곱근을 가진다.
( 이 성질 때문에 quadratic residue 와 non-quadratic residue 는 개수가 같다. )
< 7 >
"르장드르 기호", 말만 들어도 웅장해지는 이름이다. 하지만 르장드르 기호는 Quadratic residue 를 나타내기 위한 기호일 뿐이다.
n 이 mod p 에 대해서 quadratic residue 라면, (n/p) = 1 이고, 아니라면 -1 의 값을 가진다. 이런 르장드르 기호에서는 당연하게도 서로 곱하는 것이 가능하다. (a/p) * (b/p) = (a*b/p) 가 되어 결국 위의 사진에서 말한 공식이 성립하게 된다.
이해가 잘 가지 않는다면 직접 mod 합동식에서 계산해보면 이해가 슂게 될 것이다.
그런데 이 르장드르 기호를 표현하기만 한다면 무슨 의미가 있겠는가.. 여기서 오일러 판정법이라는 것이 등장한다.
오일러 판정법은 n이 mod p 에 대해서 이차 잉여인지를 판단하는 공식이다. 여기서 오일러 정리가 쓰이기 때문에 오일러 판정법이라고 불린다.
어떻게 적용시킬 수 있을까? p-1 은 항상 짝수이기 때문에 제곱근을 구할 수 있다. 따라서 판별하고자 하는 정수 n 을 (p-1)/2 제곱 시킨다면, 만약에 n 이 quadratic residue 였다면, n 은 b ^ 2 꼴로 표현시킬 수 있을 것이고, 결국 이는 b 의 p-1 제곱이 되어 1의 값을 가지겠다.
설명이 조금 난잡한데, 이해를 돕기 위해 사진을 첨부하겠다.
이에 따라서 (p-1)/2 제곱을 시켜보면, Quadratic residue인지 판별할 수 있다.
이번 문제에서는 주어진 output.txt 파일에서 ints 중 QR을 찾는 것이다.
코드를 작성해보도록 하자.
p = 101524035174539890485408575671085261788758965189060164484385690801466167356667036677932998889725476582421738788500738738503134356158197247473850273565349249573867251280253564698939768700489401960767007716413932851838937641880157263936985954881657889497583485535527613578457628399173971810541670838543309159139
ints = [25081841204695904475894082974192007718642931811040324543182130088804239047149283334700530600468528298920930150221871666297194395061462592781551275161695411167049544771049769000895119729307495913024360169904315078028798025169985966732789207320203861858234048872508633514498384390497048416012928086480326832803, 45471765180330439060504647480621449634904192839383897212809808339619841633826534856109999027962620381874878086991125854247108359699799913776917227058286090426484548349388138935504299609200377899052716663351188664096302672712078508601311725863678223874157861163196340391008634419348573975841578359355931590555, 17364140182001694956465593533200623738590196990236340894554145562517924989208719245429557645254953527658049246737589538280332010533027062477684237933221198639948938784244510469138826808187365678322547992099715229218615475923754896960363138890331502811292427146595752813297603265829581292183917027983351121325, 14388109104985808487337749876058284426747816961971581447380608277949200244660381570568531129775053684256071819837294436069133592772543582735985855506250660938574234958754211349215293281645205354069970790155237033436065434572020652955666855773232074749487007626050323967496732359278657193580493324467258802863, 4379499308310772821004090447650785095356643590411706358119239166662089428685562719233435615196994728767593223519226235062647670077854687031681041462632566890129595506430188602238753450337691441293042716909901692570971955078924699306873191983953501093343423248482960643055943413031768521782634679536276233318, 85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771, 50576597458517451578431293746926099486388286246142012476814190030935689430726042810458344828563913001012415702876199708216875020997112089693759638454900092580746638631062117961876611545851157613835724635005253792316142379239047654392970415343694657580353333217547079551304961116837545648785312490665576832987, 96868738830341112368094632337476840272563704408573054404213766500407517251810212494515862176356916912627172280446141202661640191237336568731069327906100896178776245311689857997012187599140875912026589672629935267844696976980890380730867520071059572350667913710344648377601017758188404474812654737363275994871, 4881261656846638800623549662943393234361061827128610120046315649707078244180313661063004390750821317096754282796876479695558644108492317407662131441224257537276274962372021273583478509416358764706098471849536036184924640593888902859441388472856822541452041181244337124767666161645827145408781917658423571721, 18237936726367556664171427575475596460727369368246286138804284742124256700367133250078608537129877968287885457417957868580553371999414227484737603688992620953200143688061024092623556471053006464123205133894607923801371986027458274343737860395496260538663183193877539815179246700525865152165600985105257601565]
for i in ints:
if pow(i,(p-1)//2,p) == 1:
print(f'{i} is a QR!!')
실행시켜보면,
85256449776780591202928235662805033201684571648990042997557084658000067050672130152734911919581661523957075992761662315262685030115255938352540032297113615687815976039390537716707854569980516690246592112936796917504034711418465442893323439490171095447109457355598873230115172636184525449905022174536414781771 is a QR!!
이라는 결과가 나온다.
< 8 >
이번 문제는 드디어 Tonelli Shanks 알고리즘이다. Tonelli Shanks 알고리즘은 임의의 QR n 에 대해서, n 의 제곱근을 구할 수 있게 해주는 알고리즘이다.
우리는 어떻게 제곱근을 구할 수 있을까?
이는 p 가 mod 4 에 대해서 1인지, 3인지에 따라서 확연히 달라진다.
먼저 mod 4 에서 3인 경우부터 살펴보자.
먼저, n 이 mod p 에서 a ^ 2 으로 나타낼 수 있다고 가정하자.
우리는 모두 "페르마 소정리" 를 통해서 a ^ (p-1) 의 값이 1 이 됨을 알 수 있고, 이를 이용해서 a ^ (p+1) 은 다시 a ^ 2 의 값으로 되돌아간다는 사실을 알 수 있다.
그러면 우리는 a ^ (p+1)//2 의 값은 a 의 값과 똑같다는 사실을 유추해낼 수 있다. 그렇다면 a ^ 2의 값을 아는 상황에서는 , a^ 2 의 값을 (p+1)//4 제곱만 해주게 되면, 결국 QR 의 제곱근을 구할 수 있다는 소리가 된다!!!
따라서 p 가 mod 4 에 대해서 3인 경우에는 이렇게 쉽게 제곱근을 구할 수 있다.
하지만, mod 4 에 대해서 1이라면 어떻게 풀어야 할까? 여기서는 새로운 알고리즘인 Tonelli-Shanks 알고리즘을 사용해야 한다.
( 이 포스팅에서 전부 이해하긴 어려울 듯 하다. 링크를 보고 오도록 하자 )
이를 코드로 작성해보면 다음과 같다.
def tonelli_shanks(n,p):
def isQR(x,p):
return pow(x,(p-1)//2,p)==1
if not isQR(n,p):
return -1
Q,S=p-1,0
while Q%2==0:
S+=1
Q//=2
z=None
for x in range(2,p):
if not isQR(x,p):
z=x
break
M,c,t,R=S,pow(z,Q,p),pow(n,Q,p),pow(n,(Q+1)//2,p)
while True:
if t==0:
return 0
elif t==1:
return R
k=t*t%p
ii=None
for i in range(1,M):
if k==1:
ii=i
break
k*=k
k%=p
b=pow(c,2**(M-i-1),p)%p
M=ii%p
c=b*b%p
t=t*c%p
R=R*b%pㅎㅎ.. 여기서 바로 코드를 작성해보도록 하자.
a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
print(tonelli_shanks(a,p))
실행해보면 2362339307683048638327773298580489298932137505520500388338271052053734747862351779647314176817953359071871560041125289919247146074907151612762640868199621186559522068338032600991311882224016021222672243139362180461232646732465848840425458257930887856583379600967761738596782877851318489355679822813155123045705285112099448146426755110160002515592418850432103641815811071548456284263507805589445073657565381850521367969675699760755310784623577076440037747681760302434924932113640061738777601194622244192758024180853916244427254065441962557282572849162772740798989647948645207349737457445440405057156897508368531939120
이 나온다.
< 9 >
이번 문제는 CRT, 중국인의 나머지 정리에 관한 문제이다. CRT는 하나의 x 가 여러 합동식에서 해를 가질 때, 이를 하나로 통합하는 정리이다.
예를 들어서, x 가 mod 5 에서 1, mod 7 에서 4라면, x 는 mod 35 에서 11 이라는 값을 얻어낼 수 있다.
물론 이도 최적화한 알고리즘이 있지만, 솔직히 말해서 느낌있게 노가다하는 것이 제일 편하고 빠른 방법인듯 하다. ㅎㅎ ( 사실 python 모듈도 존재한다. )
코드를 작성해보자.
x = 5
while True:
if x % 11 == 3:
if x % 5 == 2:
print(f"The answer is {x}")
break
else:
x += 17 * 11
x += 17
사실 숫자가 더 컸다면 더 시간을 줄이는 방법도 존재하지만, 이는 나중에 숫자가 클 때 ㅎㅎ 적용해보도록 하자.
실행해보면 The answer is 872 라는 결과가 나온다.
< 10 >
마지막 문제는 별다른 설명이 없다. 아마 지금까지 배운 것을 토대로 문제를 풀어야 하는 듯 하다.
바로 source.py 파일을 살펴보자.
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))
문자열을 비트화시킨 후에, 1이면 a ^ 2 그대로, 0이면 -a^2 를 출력한다. 여기서 관건은 a ^ 2 와 - (a ^ 2)를 구분하는 문제가 되겠다.
어떻게 문제를 풀 수 있을까??
