H4CKING GAME - Cryptography, Season1 : IsThisRSA?

Season1 : IsThisRSA?

 

parameter.txt

0.00MB

 

 

p = 19658233588384543584622422773066019672489254398483015934476452553849995704298358120740877755608542182334997267943829377464450026302593617446862837354950969314579923780089201656308163287003294456275000554652343465427543808477672452215200736502512188571245151127289141060304796191397863697287887282204127454708930277439425204130235515834590386608380129637051671376529607894071415705844956658677179594382647311466792979086465387828027784217317657927203627879898246745853399227774969308883597843454989170675701829826382988716737621415565450716579861526421813180402295307362320383599181383156383685564511101599793011162633
e = 64
ct = 16750884000935236034491752511249723971891896042980444832954004971203960558410090031312324645325324943394354034068119912663106496139027086054349018249761628360613480732615377968377982243375212849642556023236130442536216540819455104415588101364683685173407023853114514074023653334435674812056862657158683279265580316314999461613971859181504990738065610381025805161703619997873222980686597541631888966726504136367537482282282062290334231739794009595009570495415787866361186110113305472254242787678627107053957991763343542757340120960015364678693578837312511178507536955257672100134133188148766806646087943553847582936282

 

 

p, e, ct 값이 나온다. 문제 제목처럼 과연 rsa 문제일까? 

e=64 를 보고 일반적인 rsa 문제가 아니라는 것을 알 수 있다. 

 

보통 rsa에서 e 값은 65537과 같은 홀수를 많이 쓰는데 여기에서는 64 라는 짝수를 썼다. 

정상적인 RSA라면 φ(n)도 보통 짝수이므로 gcd(64,φ(n)) =/= 1 가 돼서 개인키 d가 존재하지 않는다.

 

 

그렇다면 rsa의 기본이 되는 모듈러 연산식을 봐보자. 

 

ct = m^e mod p

ct = m^64 mod p

ct = (m^32)^2 mod p

 

우리가 지금 ct, p를 알고 있으니 해당 연산을 통해 m^32 값을 구할 수 있다. 

 

다행인 건 아래의 파이썬 함수가 대신 연산해줌 

from sympy.ntheory.residue_ntheory import sqrt_mod
sqrt_mod(x, p, all_roots=True)

 

그럼 m^32 에 대한 값이 2개가 나오는데, 각각에 대한 sqrt_mod 연산을 다시 해주면 또 2개씩 값이 나온다.

 

이런식으로

          ct
         /  \
        ?    ?

 

        ct
       /  \
      ?    ?
     / \  /  \

 

우리는 계산을 6번 해야 하니 결국 답은 여러 개(최대 64개)의 후보 중 하나가 된다.

 

또한 최종으로 나온 숫자를 다시 아스키코드 변환을 해주어야 한다. 

 

1번째: 2개
2번째: 4개
3번째: 8개
4번째: 8개
5번째: 8개
6번째: 8개
b'V\xda\x18\xd3\x18\xebm\xdb|\t\x8b\xfd\xc2@`Zo^h2\x1c\xc4^\xadl\xe9!\x1e\x1b\xd9u\x9f\x91\xd0\xb1\xe6e\xd4s\x9d$s{\x067\x9a*\xd9I\x9a\xb1\xb9\xc4\xb3x&\xb8\x049m\x1b\x94\x1eq\xa7\xd0\xabo\x8c\xa1&Y\xe8\x7f0H\xedZ\xa2\xd7k7\x9e\x08<\xb8\tl\xcaWr\xa2\xebu]\xba\xbe\xd4\x89G\xf7u\xb8\x0b\xb9f\x7f\xcf\x89RPc\xaf^\x16\x8b\xd4t\x8fh\x7f0e\xac\x98\x87(\xb4C;\xdb\xc7\x0b\xf6\xa9\xd4\x0c\xde&)\x9e:\x12\x90\xe2\x00\x95H\xba\x04\x0fk\xd95\x9b\x854v\x1c\x8f\xfa\xba\xbd;\xea\x18\x9b\x92\xd2I4\xd6I-\xa3Qa\x10c\ti\x8dF\x1b\xfaU\x9b\xcc\x10\xae\xbbL\xde\x0f\x03\x9eS\xd8\xb2\x10J\xa5\x97\xae\x92\xd2\x98\xb52e\x83Q;\xaa\xbe\x94\xca\xc5,\x1a\x12\xc6\xff\xc7{\x0cS>\xce0\xa4\xfd\x93\xe0\xd8e\xf3R\x94#\xa9\x1f\x94\x89NZ\xc9na\xceaX\x19\x04\t$'
b's\x1a=\xa7\xe8\x12\xee\x1fB,o37aC\x8b\xd6\x1f\xc7\xe2\x1f\x91\x1b\xd0\xe2\xcfz1\xab\xd4@\x1c\x07\xca\x11\x16\x03\x17\x9d\xb2\xd5\t\xbe\x95\xed.\xe1\x1fl\xdc#\xdb\x16\xd9\xbf\xe2\x82^\x14\xc7\rS\xe4\xd5\xc9u\xfbL{\x17\x14\xfc\xe8\xc28\xd5\xf8\xdf\xd2\xf43\xe2\x8e\x0b\xf4^\'\x08\xeb\x8c\xdd\xba\xef\xa7e)\xd81\xeb\r?\x83}5\x8c\x1e\x05\x10\xa6\xf1\xc2Eh7\xd4\xc5\xa8\x99\x9a\xa5\x9cU0k\xe9\x9c\x82\xb2\xac\xa5\x91\x16H,\xe3o\xd3\x17<\x8a\\i$_\x97g_\xaf\xf8\x88\x0e\x91uU8l-\xc8\x05\x99\xcbCl)\xe0\x9d\xe1dw\xa6-U\x0b\xd0\x85"%f\x0f\xf3^\xb6\x81a\xb9xJd\x1f\xa1,j\xad\x1b\xc3\xcf\x96EV\\_4\xa5\xe4\xbb~\xf4mk\r\x03+\xd64G^\xaf\x00\x1ck\xee\x9e\x9c\xa1\xdf\x19\x06\xb2\xee\xa8t\xd2\xcc(c\xec(\xa0\xac1\xf9\xab\xf5\xff.\xc6T\xf8\x9c`\xc6\xe5\xb0\xc6\xcb<'
b'\x9b\xb9$\t\xce\xe2\xb2\x8b\xad+r\xc4\x14\xac\xcbg@\xe9\xa3*\x99\xa1+\xac2,\x9f\x0fC\xa4\x8bH%@%q \x9c:$)\x8d\xdd\x1c\x14p\x8a\x17\xec\xd8c\x80K\xdbx\x94a+@]\x9f\x98\x1c3\xaf2\x95\xce*\x08E\x7fa\x1f\xfbX~\xc1t\xe6\x1b\x12h?k-s\xed\x08\xa2k\xe9\xb6*\x94]\xd1\t\xf6~\x18\xa7ak\xde\xd9\xec\xaazv\x17S.M\x08\x99\xb8E\x7f\x91\xee]\xaa2\xf1\xd8?Q\x10i?\x04\xa8\xc5\xc7\xd8o\x85B_\xb0\x9f\x92\xd76Ct\xcbch\xaa\xb7#\x90s5\xc2\xde\xaa\xdd\xb7R W\xa0\x06)j\xcfY\x170\x0f\xad\xe3:\xdb\x9d\\\xf2z\x8b\x08\x1a\xb2\xc8P\xf5IQ\xc2P\xe5\xf5\xcf\xac\x99X\xbd\\s\x9b\xcf\x9c\x0fW!P\x126+k\xab\xa4"z\x85\xe7aqJ\xfb\x03\t4\x82\xa4\x1d\xe7\xcf9\x0b\x03\xc1\x84e\xa4\xe7\xcb%\xdd(\x88\xae]\xb8M\xed\xdbgq\x1fPX\x90\x8c'
b'H4CGM{shanks_dont_have_one_???}'
b"(\x9e\xe6a\xe6\xcf\xc4lj\xff\x03\x90\xddK\x87\xdbj\xc9\xdbHz\x10\x0f\xdbO]$\xdd\x97\xd0K,\x1dv\x14[\x1d\x84\x9cqT\x84\x1e\x86'A\xa8\xf8\x7f\xfc?\xa55\x01\xb8\xb1\xde\xcd+\x96\x92D7]\xe5\xbc\x9a\x81\xae\xf10\x82x]\xc2\x82\x85\xe1\xa1\xf1\xe7/\xda3v\xcfL\xe4\x1d\x15\x8e.\xc6\x83/3\xf8\xd8\x0bp\xd9#\xe46R\xbb\xe7\x99\xd3\x84U\r\xc6\x153\xd4\x0f\xab\xe4\xecR\x08y\xc7\x08;\xbc\x9ec\xc3\xad\xee`\x98\xe4h\x9cn\x05\xd5T6nw\x9e\xdc\x15\x1bj\xe0\x9c%\xae;:\xc9\x95\x16\xa5C\xec\x0e\xb4-\xbfhH\x06W\xb2\xe9\xdb\x03\xdd^\x18\xb67L\xff\x1b\xd4\x86\xb8\xf9P\x06\x91)\xb0\x95\xe68\xda\x0b\xdd\x03\x13g\x00\x14g)\xb7S\xd8,\xe2\xa7)(?\xd5o\xdb\x1b\xd6\xe7E\x05\\\\fgU\xb1\xd1\xae@t?\xab\x9f\xfa\x8e\xe4\xef\xa6\x83cQ\xf0\xf2\x17\x90h^T\xaeu\x0f\x99\x01\x042\xcd"
b'D\xdf\x0b6\xb5\xf7D\xb01!\xe6\xc6Rlk\x0c\xd1\x8b:\xf8|\xdc\xcc\xfe\xc5C}\xf1\'\xcb\x15\xa8\x93os\x8a\xba\xc7\xc6\x87\x05\x1ab\x15\xdc\xd6_>\xa3=\xb1\xc6\x87(\x00m\xa9\'\x06\xf0\x84\x03\xfd\xc2\x07a\xea^\x9dg\x1f%x\xa0\xcb\x0f\x91f\xd2\x0e\xaf\xda\xca7.uj\x80>J\xf9F\xca\xb56\xa3\x125m6!1\xa9`%sl\xda\xf1#\xc6\xef~\xee\xf2\r\xe3\xd0\xf0)o-D\x86YQ\x16\x9c\xcd-c=\x9c\xcf\x1e\x04b\xa7\x1c6\x12e\x80FTB\xdf\x82\xa9d\x9bKJZ\xd7\xb0\x8eh\x8eM\xbc\x97c\x1b\xb5\xed\x8d\xd7\xfd\x0f\xe2Y\xc6\x80?\xe9z\x8c\xf9\xe9\x10\xfd\xc1\xfe\xb8r\xb5)8\xa3\x07\x04\x07\xe6\xcc\x0eE\x80\x0bL(\xf67\xed|\x84\x88\x9a\xdf\xd0\xa8\x1ao\xf9c\xe5\xbb"5W84\x03A\xb9\xbe\x85"`\xec\x0f\x80\xd8B\x1ak$\xf4\x9bq\xa2}S\x8dp\xd3\xe9\xde\xe9\x07u&\x98\xc6\xf4\xe5'
b"Ql\xaa\xc5\xf1'C\x06\x1c\x81\xdb\xd2\xd1\xec|\x99\xf9V\x90\x93J\x8drz\x9a\xd8\x8b@\xee[\x9aT\x02\x18\xd1\xa5\x05\x8fb\x18!k0\n  \x80w\xaaj\x8e\x9bU\xd6(\xa3\xf6o;\x8d`q\xef)wLpTY21\xf1\x13f\xa5\xc5l\xb3\xb6\xa3\xa0h\xd4\xae`K/\x89y\xdf\xa5\x8b\xb5\xe9\xcaO\xf6\xd1OX\x10\xcc\xcb}#\xe5\xfa\xe5\xf9\x17\xe0E\x9a\xa8\xdc\x99\xeb\xb6\x94bcv\x04\xd0\x13\xb0\xa0\x9f\xd3,S&\x90\x90b|\r83K\x81\x8f\x16\xc2\x98\xda{\xd3\n*\xda\xe9\x94/0Ib\x16\xdd\xd2\\;w\xd7\xccq\xc1\xd8\xd9\xa3Jf\xb4\x88\xaa\xca\xc3\x1d\x8f6{\xc7{\x8b\xea\x1e\xd9h\x19Mq\xb1\xe2x\xed\x82\xc1\xff$G5|hX\xcc\x9c\xb5\xb0%j\x90@I3\xd3Vjc\xaa\x8f==\x96\xe1\xf2C\xe5W1x\x86\xed\xb4\x01_\x19\xce\x01\x9d\x98\xdf\xc9\x0b\xd7\xb7\xaeD\x88\xf1Z{\xb5\x7f\x13\x99\x94"
b'JLyC\xdd\xbbo\x85\x90\xa9\x96\xf1B\xc0N\xcdG\x93\x12\x97O\x13\xb91\x97T\x13\xceUH\xf0\xf4#\'S\xcc\x1b\x0c\xd8\x0c\x08"\xad\x11\xf4P\t\xa0Bm\xd4\xe4\xf6\x05O\xf0j\xbc\x04\xd0?&-\n7\xe6%y\xd0\xd6\x13\x8eM\xb9U\x93\x12\r\xbeBz\xa9\x93\x91\n\xe2Dc\x8e\xc2\xc6^\x00@\xca\r\xda8\xa7&\x07\xda\x95\xee\xba\xf3\xf1\xc4\x81^7\r\x93\xa4+\xff\xcc\x8e\xeb/\x8a\xe7\xa5b\xde\'\x9e\xb1=<\xeb\xde\x185e\\bM\x0f\x14/\x10|\x14\x9dh\xf8\xf8Y=\xcf\xcd\x8faB\xec`\xc7\xcd\x0b[\x16\xa8\x7f\xd3\x94g\x91\xf5\xb5\xcc\xc9[%8p\x18\x7f\xcd\xbb\xfe\xc3\x8c\x8e\xc8\xa9w\x8d0\x04P\x9f\x03|\xe2)\xd7Y\x99\x15>\x1fgCB\xbak\x9f\xec\xcb\x9b+bpO$\x1b\x83\xb6\xe2\r\xbdl\'B\x86\xf3\t\xfd\xa4-\x90\xb8!\x93\xb7JE\x91\xfck\xd3\xdc?\x07\x80n\xc4Y{Z\xc92\xb7du'

 

이렇게 최종 후보는 8개가 나왔고 그중 하나는 flag 로 보인다. 

 

??? 값은 여러분들이 직접 찾아보세요 공부하세요!!!