這是 ISITDTU 的一道密碼學(xué)題目不傅，題目是這樣的
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]
可以看到需要我們求的是 mes，加密過程為從 mes 中依次取出每一個字符赏胚，對該字符的ascii碼進行線性運算再取模（ (m * ord(i) + c) mod n ）访娶，而mnc都是未知的
麻煩因為取模運算的存在 使加密的結(jié)果變得無法預(yù)測
突破點在于我們知道 mes 中的一部分信息，包含 'ISITDTU'
對于相同的元素觉阅，經(jīng)過加密之后的結(jié)果一定是相同的崖疤，而這里包含的 'I' 'T' 都是相同的秘车，因此寫腳本求出他們對應(yīng)的值
設(shè)輸出的結(jié)果為 list a
for i in xrange(len(a)-5):
if a[i] == a[i+2] and a[i+3] == a[i+5]:
print i
然后我們就可以得到這些字符加密后的值
1470896290937720121923671834268680644293311486759008609851306976 I 73
998119569566922793772397587105095499481847516084421474175736111 S 83
1470896290937720121923671834268680644293311486759008609851306976 I
2108440654988370562048343461399852810852299068780806568036885800 T 84
549685894064591284908235658839357390847445522332458370260385633 D 68
2108440654988370562048343461399852810852299068780806568036885800 T
903564225292763328142142737672378470519554721949504047040621938 U 85
觀察這里幾個比較接近的字符 S T U 的 ascii 碼分別為 83 84 85，據(jù)此猜測出 m, n 的值
m = t - s
n = t + m - u
對每一個結(jié)果我們寫出解密函數(shù)
def dec(x):
k = -50
while k < 45:
k += 1
if (x + k * m - s) % n == 0:
return chr(ord('S') - k)
return '?'
然后解密即可得到flag
>>> for x in a:
... ss += dec(x)
...
>>> ss
'Hello everybody, this is your flag: ISITDTU{break_LCG_unknown_all}'
