ISITDTU CTF - Love CryptoGraphy

love_cryptography.py

import random
from gmpy2 import *
from message import mes
from secret import m,n,c

assert "ISITDTU" in mes

s = []
for i in mes:
    x = (m* ord(i) + c) % n
    s.append(x)

print s
# [360575205516272353647725959973923332922859934062623515990157287L, 147121471099487603100103942210642238821212368870164629959708554L, 973776523698456974485285268207248463304785539161797442415515724L, 973776523698456974485285268207248463304785539161797442415515724L, 1989542264845745277130976293069288745712944297723265109141551240L, 2251682090999461666252822948628263912168715816760972058692440747L, 147121471099487603100103942210642238821212368870164629959708554L, 500999802327659646334011021043663318493321568487210306739944859L, 147121471099487603100103942210642238821212368870164629959708554L, 690110490875978577594520719909097376417907156757045161010173205L, 1516765543474947948979702045905703600901480327048677973465980375L, 1446553245069254302636559515370833608116249509836384578091086589L, 1989542264845745277130976293069288745712944297723265109141551240L, 1351997900795094837006304665938116579153956715701467150955972416L, 1516765543474947948979702045905703600901480327048677973465980375L, 1684350025354504872471293852031961738394959051951467495881755709L, 2251682090999461666252822948628263912168715816760972058692440747L, 595555146601819111964265870476380347455614362622127733875059032L, 1162887212246775905745794967072682521229371127431632296685744070L, 2273208297668223674021740841367439832599822680128017390546893759L, 1800431576297426345870466594203854687788358709453430254871322894L, 2251682090999461666252822948628263912168715816760972058692440747L, 2273208297668223674021740841367439832599822680128017390546893759L, 1800431576297426345870466594203854687788358709453430254871322894L, 2251682090999461666252822948628263912168715816760972058692440747L, 1516765543474947948979702045905703600901480327048677973465980375L, 1989542264845745277130976293069288745712944297723265109141551240L, 1705876232023266880240211744771137658826065915318512827736208721L, 690110490875978577594520719909097376417907156757045161010173205L, 2251682090999461666252822948628263912168715816760972058692440747L, 1257442556520935371376049816505399550191663921566549723820858243L, 973776523698456974485285268207248463304785539161797442415515724L, 336232159647806534360613641076076296745797957139999484229936900L, 52566126825328137469849092777925209858919574735247202824594381L, 1022462615435388613059509906002942535658909493007045505935956498L, 2251682090999461666252822948628263912168715816760972058692440747L, 1470896290937720121923671834268680644293311486759008609851306976L, 998119569566922793772397587105095499481847516084421474175736111L, 1470896290937720121923671834268680644293311486759008609851306976L, 2108440654988370562048343461399852810852299068780806568036885800L, 549685894064591284908235658839357390847445522332458370260385633L, 2108440654988370562048343461399852810852299068780806568036885800L, 903564225292763328142142737672378470519554721949504047040621938L, 1422210199200788483349447196472986571939187532913760546330866202L, 1446553245069254302636559515370833608116249509836384578091086589L, 690110490875978577594520719909097376417907156757045161010173205L, 147121471099487603100103942210642238821212368870164629959708554L, 336232159647806534360613641076076296745797957139999484229936900L, 2178652953394064208391485991934722803637529885993099963411779586L, 430787503921965999990868490508793325708090751274916911365051073L, 171464516967953422387216261108489274998274345792788661719928941L, 1754562323760198518814436382566831731180189869163760891256649495L, 1565451635211879587553926683701397673255604280893926036986421149L, 430787503921965999990868490508793325708090751274916911365051073L, 1705876232023266880240211744771137658826065915318512827736208721L, 879221179424297508855030418774531434342492745026880015280401551L, 2178652953394064208391485991934722803637529885993099963411779586L, 879221179424297508855030418774531434342492745026880015280401551L, 1989542264845745277130976293069288745712944297723265109141551240L, 1611320887749107414609956895338420629863773121183595400601094548L, 879221179424297508855030418774531434342492745026880015280401551L, 430787503921965999990868490508793325708090751274916911365051073L, 336232159647806534360613641076076296745797957139999484229936900L, 973776523698456974485285268207248463304785539161797442415515724L, 973776523698456974485285268207248463304785539161797442415515724L, 1327654854926629017719192347040269542976894738778843119195752029L]

solve_love.py

enc = [360575205516272353647725959973923332922859934062623515990157287L, 147121471099487603100103942210642238821212368870164629959708554L, 973776523698456974485285268207248463304785539161797442415515724L, 973776523698456974485285268207248463304785539161797442415515724L, 1989542264845745277130976293069288745712944297723265109141551240L, 2251682090999461666252822948628263912168715816760972058692440747L, 147121471099487603100103942210642238821212368870164629959708554L, 500999802327659646334011021043663318493321568487210306739944859L, 147121471099487603100103942210642238821212368870164629959708554L, 690110490875978577594520719909097376417907156757045161010173205L, 1516765543474947948979702045905703600901480327048677973465980375L, 1446553245069254302636559515370833608116249509836384578091086589L, 1989542264845745277130976293069288745712944297723265109141551240L, 1351997900795094837006304665938116579153956715701467150955972416L, 1516765543474947948979702045905703600901480327048677973465980375L, 1684350025354504872471293852031961738394959051951467495881755709L, 2251682090999461666252822948628263912168715816760972058692440747L, 595555146601819111964265870476380347455614362622127733875059032L, 1162887212246775905745794967072682521229371127431632296685744070L, 2273208297668223674021740841367439832599822680128017390546893759L, 1800431576297426345870466594203854687788358709453430254871322894L, 2251682090999461666252822948628263912168715816760972058692440747L, 2273208297668223674021740841367439832599822680128017390546893759L, 1800431576297426345870466594203854687788358709453430254871322894L, 2251682090999461666252822948628263912168715816760972058692440747L, 1516765543474947948979702045905703600901480327048677973465980375L, 1989542264845745277130976293069288745712944297723265109141551240L, 1705876232023266880240211744771137658826065915318512827736208721L, 690110490875978577594520719909097376417907156757045161010173205L, 2251682090999461666252822948628263912168715816760972058692440747L, 1257442556520935371376049816505399550191663921566549723820858243L, 973776523698456974485285268207248463304785539161797442415515724L, 336232159647806534360613641076076296745797957139999484229936900L, 52566126825328137469849092777925209858919574735247202824594381L, 1022462615435388613059509906002942535658909493007045505935956498L, 2251682090999461666252822948628263912168715816760972058692440747L, 1470896290937720121923671834268680644293311486759008609851306976L, 998119569566922793772397587105095499481847516084421474175736111L, 1470896290937720121923671834268680644293311486759008609851306976L, 2108440654988370562048343461399852810852299068780806568036885800L, 549685894064591284908235658839357390847445522332458370260385633L, 2108440654988370562048343461399852810852299068780806568036885800L, 903564225292763328142142737672378470519554721949504047040621938L, 1422210199200788483349447196472986571939187532913760546330866202L, 1446553245069254302636559515370833608116249509836384578091086589L, 690110490875978577594520719909097376417907156757045161010173205L, 147121471099487603100103942210642238821212368870164629959708554L, 336232159647806534360613641076076296745797957139999484229936900L, 2178652953394064208391485991934722803637529885993099963411779586L, 430787503921965999990868490508793325708090751274916911365051073L, 171464516967953422387216261108489274998274345792788661719928941L, 1754562323760198518814436382566831731180189869163760891256649495L, 1565451635211879587553926683701397673255604280893926036986421149L, 430787503921965999990868490508793325708090751274916911365051073L, 1705876232023266880240211744771137658826065915318512827736208721L, 879221179424297508855030418774531434342492745026880015280401551L, 2178652953394064208391485991934722803637529885993099963411779586L, 879221179424297508855030418774531434342492745026880015280401551L, 1989542264845745277130976293069288745712944297723265109141551240L, 1611320887749107414609956895338420629863773121183595400601094548L, 879221179424297508855030418774531434342492745026880015280401551L, 430787503921965999990868490508793325708090751274916911365051073L, 336232159647806534360613641076076296745797957139999484229936900L, 973776523698456974485285268207248463304785539161797442415515724L, 973776523698456974485285268207248463304785539161797442415515724L, 1327654854926629017719192347040269542976894738778843119195752029L]

xT = 2108440654988370562048343461399852810852299068780806568036885800L
xS = 998119569566922793772397587105095499481847516084421474175736111L
xU = 903564225292763328142142737672378470519554721949504047040621938L

# Took from SO
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b%a,a)
    return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('No modular inverse')
    return x%m

n = 2 * (xT-xS) - (xU-xS)
m = (modinv(1, n) * ((xT - xS) % n))
c = (xT - m * ord('T')) % n

print 'n ', n
print 'm ', m
print 'c ', c

import string
alpha = string.printable

flag = ''
for index in enc:
	for char in alpha:
		if (m * ord(char) + c) % n == index:
			flag += char
			break

print flag