pow pow! (20pt)

Prob

---

CATEGORY : Crypto

I signed my flag, thats pretty much the same as encryption, right?

I signed my flag, thats pretty much the same as encryption, right?

pub_e: 65537
pub_n: 27130058966678375728118690628915085193505679921867847648180394177280300520851322209827953313677610995977175396855400115719997248093217978788791475794191309606741245965521564249520758557425707716276357612383008262150259072257782913410617175802499340022388447047629022386881255413171331856263374853843961598744215379945538726953506454859112787839466674350352298690863753069032704210896554984332177790093120515590458961735089368466550753534317073220559703261053361251093853868715391272704827131460657841223647599202717920842362378900859386228898179814271143542598798022604629591665790726585192070387959726079579927264339
flag: 4172204809297405811985500677636732349089473540889855289757337736512303070584208009356148963914969296139250262532036044670829787749340381486502259003934029518250084291211843615602473277568939725661998743287881104315586743909166094376545879628924755210696938802618107247235991939968132055218667508994013042802832653274036857030938271120371493508056689333496510130233288415153533743215499505779621204995381781585793891494891361783339201260743345041742788508748141553059420124837675803038062487182700364305742864198416705040747639989644160240694540025745969599421913149372250571544665491768421384384768919101583170066211

 

Solve

---

RSA 전자서명에 사용된 공개지수(공개키) e 와 서명 값 s 가 공개되었기 때문에 쉽게 복구할 수 있다. Dreamhack을 풀이하면서 sagemath 사용 환경을 구축하였는데, 이를 이용해보기로 했다. 

먼저 간단하게 RSA 전자서명에 대해 언급하자면, 서명자는 비밀키  d 를 사용하여 메시지 m 에 서명하여 서명 값 s를 생성한다.

이 서명을 검증하는 사람은 공개키 e 를 사용하여 서명 값을 검증한다.

여기서 m' = m 이 성립할 경우 서명이 유효하다는 것을 의미한다.

sagemath를 사용하여 아래와 같이 m' 값을 구할 수 있다.

sage: (417220480929740581198550067763673234908947354088985528975733773651230307058420800935614896391496929613925026253203604467082
....: 9787749340381486502259003934029518250084291211843615602473277568939725661998743287881104315586743909166094376545879628924755
....: 2106969388026181072472359919399681320552186675089940130428028326532740368570309382711203714935080566893334965101302332884151
....: 5353374321549950577962120499538178158579389149489136178333920126074334504174278850874814155305942012483767580303806248718270
....: 0364305742864198416705040747639989644160240694540025745969599421913149372250571544665491768421384384768919101583170066211 ^
....: 65537) % 2713005896667837572811869062891508519350567992186784764818039417728030052085132220982795331367761099597717539685540
....: 0115719997248093217978788791475794191309606741245965521564249520758557425707716276357612383008262150259072257782913410617175
....: 8024993400223884470476290223868812554131713318562633748538439615987442153799455387269535064548591127878394666743503522986908
....: 6375306903270421089655498433217779009312051559045896173508936846655075353431707322055970326105336125109385386871539127270482
....: 7131460657841223647599202717920842362378900859386228898179814271143542598798022604629591665790726585192070387959726079579927
....: 264339
679187977328367916642288683373970245379557496941171228479756467373482365
sage:

이 값을 hex 값으로 바꾼 뒤, string으로 치환하면 플래그를 얻을 수 있다.

def hex_to_string(hex_num):
	if hex_num[:2] == '0x':
		hex_num = hex_num[2:]
	string_value = bytes.fromhex(hex_num).decode('utf-8')
	return string_value

res = 679187977328367916642288683373970245379557496941171228479756467373482365
flag = hex_to_string(hex(res))
print (flag)

Flag : bh{signing_is_not_encryption!}