picoctf2018_rsa-madlibs.py

import sys
import socket
import time
 
def egcd(a, b):
	x,y, u,v = 0,1, 1,0
	while(a!=0):
		q, r = b//a, b%a
		m, n = x-u*q, y-v*q
		b,a, x,y, u,v = a,r, u,v, m,n
		gcd = b
	return gcd, x, y
 
hostname = "2018shell3.picoctf.com"
port = 36859
 
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((hostname, port))
print("Connected")
 
while True:
	res = ""
	res = sock.recv(2048)
	print(res)
	time.sleep(3)

	if "q : 93187" in res and "p : 94603" in res and "n" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		q = 93187
		p = 94603
		sock.sendall('y\n')
		print("y\n")
		res = sock.recv(1024)
		print(res)
		n = p*q
		sock.sendall(str(n))
		sock.sendall('\n')
		print(str(n),'\n')

	if "p : 81203" in res and "n : 6315400919" in res and "q" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		p = 81203
		n = 6315400919
		sock.sendall('y\n')
		print("y\n")
		res = sock.recv(1024)
		print(res)
		q = n/p
		sock.sendall(str(q))
		sock.sendall('\n')
		print(str(q),'\n')

	if "e : 3" in res and "n : 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913" in res and "p" in res and "q" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		e = 3
		n = 12738162802910546503821920886905393316386362759567480839428456525224226445173031635306683726182522494910808518920409019414034814409330094245825749680913204566832337704700165993198897029795786969124232138869784626202501366135975223827287812326250577148625360887698930625504334325804587329905617936581116392784684334664204309771430814449606147221349888320403451637882447709796221706470239625292297988766493746209684880843111138170600039888112404411310974758532603998608057008811836384597579147244737606088756299939654265086899096359070667266167754944587948695842171915048619846282873769413489072243477764350071787327913
		sock.sendall('n\n')
		print("n\n")

	if "p : 79999" in res and "q : 78203" in res and "totient(n)" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		p = 79999
		q = 78203
		sock.sendall('y\n')
		print("y\n")
		res = sock.recv(1024)
		print(res)
		PHi = (p-1)*(q-1)
		sock.sendall(str(PHi))
		sock.sendall('\n')
		print(str(PHi),'\n')

	if "plaintext : 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748" in res and "e : 3" in res and "ciphertext" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		plaintext = 1815907181716474805136452061793917684000871911998851410864797078911161933431337632774829806207517001958179617856720738101327521552576351369691667910371502971480153619360010341709624631317220940851114914911751279825748
		e = 3
		n = 29129463609326322559521123136222078780585451208149138547799121083622333250646678767769126248182207478527881025116332742616201890576280859777513414460842754045651093593251726785499360828237897586278068419875517543013545369871704159718105354690802726645710699029936754265654381929650494383622583174075805797766685192325859982797796060391271817578087472948205626257717479858369754502615173773514087437504532994142632207906501079835037052797306690891600559321673928943158514646572885986881016569647357891598545880304236145548059520898133142087545369179876065657214225826997676844000054327141666320553082128424707948750331
		sock.sendall('y\n')
		print("y\n")
		res = sock.recv(1024)
		print(res)
		C = (plaintext**e) % n
		sock.sendall(str(C))
		sock.sendall('\n')
		print(str(C),'\n')

	if "ciphertext : 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323" in res and "e : 3" in res and "plaintext" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		ciphertext = 107524013451079348539944510756143604203925717262185033799328445011792760545528944993719783392542163428637172323512252624567111110666168664743115203791510985709942366609626436995887781674651272233566303814979677507101168587739375699009734588985482369702634499544891509228440194615376339573685285125730286623323
		e = 3
		n = 27566996291508213932419371385141522859343226560050921196294761870500846140132385080994630946107675330189606021165260590147068785820203600882092467797813519434652632126061353583124063944373336654246386074125394368479677295167494332556053947231141336142392086767742035970752738056297057898704112912616565299451359791548536846025854378347423520104947907334451056339439706623069503088916316369813499705073573777577169392401411708920615574908593784282546154486446779246790294398198854547069593987224578333683144886242572837465834139561122101527973799583927411936200068176539747586449939559180772690007261562703222558103359
		sock.sendall('n\n')
		print("n\n")

	if "q : 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559" in res and "e : 65537" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		q = 92092076805892533739724722602668675840671093008520241548191914215399824020372076186460768206814914423802230398410980218741906960527104568970225804374404612617736579286959865287226538692911376507934256844456333236362669879347073756238894784951597211105734179388300051579994253565459304743059533646753003894559
		p = 97846775312392801037224396977012615848433199640105786119757047098757998273009741128821931277074555731813289423891389911801250326299324018557072727051765547115514791337578758859803890173153277252326496062476389498019821358465433398338364421624871010292162533041884897182597065662521825095949253625730631876637
		e = 65537
		sock.sendall('y\n')
		print("y\n")
		res = sock.recv(1024)
		print(res)
		n = p*q
		PHi = (q-1)*(p-1)
		gcd, a, b = egcd(e, PHi)
		d = a%PHi
		sock.sendall(str(d))
		sock.sendall('\n')
		print(str(d),'\n')

	if "p : 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433" in res and "e : 65537" in res and "IS THIS POSSIBLE and FEASIBLE?" in res:
		ciphertext = 1191791154385603989017338950457953706444549348977257175840859024439456896961914986634158747079098646147275076768073561042920214249993651808989837779063107922958105481379936383065215869487850820431171263674544580096729254472650575604484973219990255615863148106543105096126096999191988960394375673790215786843107073528379091019699671260953369425507741892996006226548525831549275670809621483441808393283624850199270699755906043632045064848258791734958759503417667092878170518427857289905497710627257839284785457619198191563756900049939096535179455095450168682853409392860360775357790031928613703963238835882564864599021
		p = 153143042272527868798412612417204434156935146874282990942386694020462861918068684561281763577034706600608387699148071015194725533394126069826857182428660427818277378724977554365910231524827258160904493774748749088477328204812171935987088715261127321911849092207070653272176072509933245978935455542420691737433
		e = 65537
		n = 23952937352643527451379227516428377705004894508566304313177880191662177061878993798938496818120987817049538365206671401938265663712351239785237507341311858383628932183083145614696585411921662992078376103990806989257289472590902167457302888198293135333083734504191910953238278860923153746261500759411620299864395158783509535039259714359526738924736952759753503357614939203434092075676169179112452620687731670534906069845965633455748606649062394293289967059348143206600765820021392608270528856238306849191113241355842396325210132358046616312901337987464473799040762271876389031455051640937681745409057246190498795697239
		sock.sendall('y\n')
		print("y\n")
		res = sock.recv(1024)
		print(res)
		q = n/p
		PHi = (q-1)*(p-1)
		gcd, a, b = egcd(e, PHi)
		d = a%PHi
		#P = (ciphertext**d) % n
		P = pow(ciphertext,d,n)
		sock.sendall(str(P))
		sock.sendall('\n')
		print(str(P),'\n')
		flag = hex(P)
		flag = flag[2:]
		flag = flag[:len(flag)-1]
		print(flag,'\n')
		print(bytearray.fromhex(flag).decode())

	if res == "":
		break