Geek2021 密码wp

记录一下极客的解题过程

easy house of Classic Crypto

一道简单的古典密码题，附件中的五段密文都是以不同的形式加密，将他们解密再拼接到一起即可。

T0s=

base64编码，解码得到“OK”

4e6577

十六进制转文本，解码得到“New”

-.-- --- ..-

摩尔斯密码，解密得到“you”

ABABAABBABABBBABABBA

培根密码，解密得到“know

jung vf pynffvp pelcgb

凯撒密码，偏移量13，解密得到“what is classic crypto”

将所有明文拼在一起，得到的英文作为解压密码解压压缩包，得到flag：SYC{Meaningless_crypto}

baby house of rsa

这一道题由四道rsa组成，还有一个压缩文件。与easy house of Classic Crypto相同，需要解压密码才能得到flag。

分别将四道题解出来

得到的数字转十六进制再转文本，得到8848

得到的数字转十六进制再转文本，得到114514（好臭)

得到的数字转十六进制再转文本，得到226

得到的数字转十六进制再转文本，得到1919810

将所有数字拼在一起组成解压密码，得到flag：SYC{RSA_is_really_easy}

Classical music

先从名字入手，看到classical想到古典密码，于是尝试了凯撒、变异凯撒、栅栏，但是都没有结果，于是我开始分析hint。本以为hint是一段密文，加密方式与附件中的一样，我就尝试着去解hint，依旧没有结果。

将hint拿去百度，结果跳出了舒伯特的《鳟鱼》，与classical music的意思相符，所以我就对应着歌词拿去爆破，但还是没有得到flag。最终在百度古典密码后，才知道维吉尼亚密码。密文开头有一段字母的数量与歌词相符，于是我对照着维吉尼亚密码表找出了密钥：ILOVECLASSICALMUSIC，解密之后发现末尾有段话：theflagislowercasekey，得到了flag：SYC{iloveclassicalmusic}

三个也可以

根据题目与附件中的数据，可知这是RSA的三素数问题。求解过程与二素数的RSA一样。

得到的十进制数转十六进制再转字符串，得到flag：SYC{now_you_solve_it}

Superposition under the starry sky

hint中提示了prng(伪随机数算法)，分析给出的代码，判断为线性同余算法生成伪随机数。写出数学原理，找出逆运算，编写为代码可解

得到flag：SYC{The_rain_drenched_the_sky}

Random

此题的加密方式是我从未涉及过的内容，因此只能从代码入手

题目分析

flag = b'????????????'
l = len(bin(bytes_to_long(flag))[2:])
if l % 32 == 0:
    l //= 32
else:
    l = l // 32 + 1

先是通过bytes_to_long将flag转换为长整型数据，再通过bin()函数将十进制转为二进制，最后切割掉‘0b’，然后通过len()函数获取了长度，最后进行if的选择

rand = ''
Rand = []   #10个数的list
for _ in range(l):  #l=9
    pro = random.getrandbits(32)      #生成10个32比特的随机数
    rand += bin(pro)[2:].zfill(32)     #去掉0b用0补足32位
    Rand.append(pro)    #添加pro到Rand列表里

这一部分就是生成了一个320位的字符串

s = bin(bytes_to_long(flag))[2:].zfill(len(rand))    #len(rand)=320
c = ''  #320位二进制字符串
for i in range(len(s)):   #len(s)=10
    c += str(int(s[i]) ^ int(rand[i]))      
print(c)

此处出现破题口，c为s与i各元素异或后的组合，根据a^bb=a可知，解出rand即可得解

def change(number):
    number = number ^ (number >> 11)
    number = number ^ ((number << 7) & 2636928640)
    number = number ^ ((number << 15) & 4022730752)
    number = number ^ (number >> 18)

    return number & 0xffffffff

此处是对Rand[]中的元素进行变换

1
2
3

for i in range(len(Rand)):
    Rand[i] = change(Rand[i])
print(Rand)

这里输出了变换后的数据

求解过程

在查阅资料后得知，此题为梅森旋转算法，与Superposition under the starry sky的用途一样，都是用来产生伪随机数。

通过分析得知，只要逆运算题中change函数的算法，后面求解flag易如反掌。于是我开始对change函数进行分析。

为此我找了一个8位二进制数进行运算

原 11000100
右移shift位(此处设shift=5) 00000110
异或后结果 11000010

发现原数与结果的最高shift位相同，这是由于右移后空出的位数用0补足，而任何数与0异或都等于其本身，于是现在就可以反推原数的最高shift位。

方法为：将结果与一个二进制遮罩(11111111<<(length-shift))取与运算

过程为：

结果 11000010
二进制遮罩取与 11111000
原数最高shift位 11000000 记为原数part1

得到了原数的最高shift位后，就可以将遮罩右移shift位，再与结果异或(a^b=c,c^b=a)，保证最高shft位不变的同时求解最高2*shift位

过程为：

结果 11000010
原数part1右移shift位 00000110
原数最高2*shift位 11000100

(因为我设的是8位，而shift为5，所以算到2*shift时就可以得出原数)

相同的过程计算3*shift

直至i*shift>=位数，即可解出原数

左移的求解原数过程与右移求解类似

编写代码求解

from Crypto.Util.number import *
Rand = [389902299, 3515959351, 2216779731, 2601284435, 514154742, 4172047173, 2921107804, 2217826537, 4248207905, 1322376767]
c = '01101100010001011100100011111110110000101111000001100001110010001100111000110010111101011111100101011100111011110100001010100111100000010101100011001000011111110111111001010000010000111000101000011111011101001011110001010100100011001010001001111110011111100101111010000010101011100010001111011001010010001010001110001111'
def inverse_right_move_and_xor(result,shift):
    i,value = 0,0
    while i * shift < 32:
        part_mask = (0xffffffff << (32-shift) & 0xffffffff) >> (i*shift)
        part = result & part_mask
        result ^= part >> shift
        value ^= part
        i += 1
    return value
def inverse_left_move_and_xor(result,shift,num):
    i,value = 0,0
    while i * shift <32:
        part_mask = (0xffffffff >> (32-shift) & 0xffffffff) << (i *shift)
        part = result & part_mask
        result ^= (part << shift) & num
        value ^= part
        i += 1
    return value
rand = ''
for i in range (len(Rand)):
    n1 = Rand[i]
    n2 = inverse_right_move_and_xor(n1,18)
    n3 = inverse_left_move_and_xor(n2,15,4022730752)
    n4 = inverse_left_move_and_xor(n3,7,2636928640)
    n5 = inverse_right_move_and_xor(n4,11)
    rand += bin(n5)[2:].zfill(32)
s = ''
for i in range(len(rand)):
    s += str(int(c[i]) ^ int(rand[i]))
flag = int(s,2)
print(long_to_bytes(flag))

得到flag：SYC{1s-rand0m-or-not-That-i5-a-qu3stion}

step by step

拿到题目，首先开始分析

题目分析

flag = bytes_to_long(flag)
p = getPrime(100)   
q = getPrime(100)   
n = p * q

将字符型数据flag转为长整型数据，并取了100bits内的两个质数，得到两质数之积

clist = []
for i in bin(flag)[2:]:    #i为1或0  bin(flag)[2:]为167位的二进制数
    while True:
        x = random.randint(1, n)   #随机生成(1,n)之间的一个数
        if gp.gcd(x, n) == 1:   #如果生成的x与n互质
            c = (pow(3, int(i) + x * 2, n) * x**2) % n    
            clist.append(c)
            break

每计算一次c，x就会重新取一次

最后给出了n与clist，因此只需要计算出每一个c所对应的i，就可以得到flag

求解过程

因为每一个c所对应的x不同，所以需要一种计算方法来绕过x，直接求解i。hint中的文章给出了二次同余方程的求解方法，但我看完了依然不知道怎么用。于是我在其它地方去搜索了二次同余方程求解，看见了两个解题的关键——GM加密算法与勒让德符号

(一).勒让德符号

勒让德符号的推广——雅可比符号其中是a对p_i的勒让德符号

定义补充：在m为奇素数时雅可比符号就是勒让德符号

(二).GM加密算法

具体过程：

1.密钥产生：

(1).获得大素数p、q，得到n=p*q

(2).任取R，满足 J( )为雅可比符号

(3).得到公钥(R,n)，私钥(p,q)

2.加密

(1).B将明文转化为二进制数字 (2)对于每一个m_i都应选取一个x_i{1,n-1}

若m_i=1,c_i=R*x_i² mod n

若m_i=0,c_i=x_i² mod n

(3)c={c₁,c₂,c₃...c_n},将这个c发送给A

3.解密

对于每一个c_i都求 $与$ 若都=1，m_i=0；若都=-1，m_i=1

根据雅可比符号的性质，直接计算就可以解出flag

from Crypto.Util.number import *
import gmpy2
clist=[112490766735794793494258589897687977797993914062877995369853, 423825989606899409733986824741778284626898537704684650054048, 1239912440099782777043012567198356769914426423982980091061342, 1078272043845620437375344423460688188703277391763226546180151, 159286594418951337823608883690981934876156746053051292254402, 189434397083734065502133592439774066008070864031834709620441, 264105932521685455831442874483122006851812174082486446496525, 252479590298382195780257510632414277760400686563367629394825, 34602153293813328946647556336715300088648653636913843351330, 808692976248223555967993480457680585654329233137701900525232, 836623390705731389723338030121423143060093415003999783847569, 1218829648463542488706300570862499177531816513847669694517865, 571795296699927140597629733281737316938588378300113684751321, 324408602401500017634991400429058861929441907523133040616718, 652309276856121062936275131393396513436481452168222192943617, 135368324264829776566203256490111602190045577103623626459391, 677807894471260530035795635544578014296111908610448488780236, 1135708831589387209825610411788217272141435421502826225558333, 196882176169680492388044653063809988445336200851553236565493, 1130705847039352086713022625138307016610235729598245321418537, 974627899979016730650505688458957247745733629797568884460037, 948987355716018600108888773982169186615279073844787201014331, 364200727831752453880724784142441918092136276002472196567297, 811786724825671349602848333002825903390189436235744947667153, 248544601758659627780643527412918707686666534454807514221527, 1078860601713092925823762998344218082511712606733279204236487, 634851505432770176888905188832078431577879067601938324607512, 232972021265122845242665536151391828176473610240017058444456, 1080796896535347345799923528377657622102130648424673730618155, 622059452832122796944248249707923610120342427983134655552340, 837257289852652447556360719449396492271622453092839975184158, 626327369687614106133688347844033161113612134573404258486630, 1233019194503373412608053469954621323121044455057773900406773, 912564467902216938034173803480737819092198560216579817988291, 408076399689155479697691914877522087726703540593136498587215, 1118745562641959211267518507476218888452509349041078337285098, 1103228775032586830415033772993541541820163005491285279882940, 680899077364553221002722115625274809744677788062477442312086, 355349436487753936000721704075588637048102593449252106813298, 5254361838244723184679801326407268664182654715017847086461, 480145671282471097574354032682584083826945502763658946101104, 249136810947175342894562520096603076879372702701088690594445, 175216547555975039599856545426098941943382367602172941744494, 436310864447848960706296122266108102033486860525693191197797, 342620466614509535208918527767209905005823047382938223113086, 369848992268737575958936185907214270590887322936419642815242, 278575045025661827978388874494219837629182438978526195181637, 1189171180780533071473125545247289861677955100195126109964590, 256190182678715266654387215899616014762531664768736561586327, 719160215933023695898776016718481385742508618676368640641809, 147033122794177086112261858085593706727904275426698884436011, 247466503394960387825735598976068779045757078494832316444804, 787155643450160361724955357286670519256662665704845721250609, 112101120505278148126370035869523081506090979629681063614381, 890009544685851814191758439205974159586245412054287515881584, 1168625756997945588141764967298286550498540363325170551587334, 946031342434770434479581499217378781992921204179509449159996, 759124753621557368233069144948668001126536400499520990700641, 930584421635842804698880452391670787414151645249729141739148, 140981825203074314092967178062754008486703246602401550271041, 880126454149733441805446179826584472107299085899567279467558, 510129631452465708304688340114214360026947205003705062663759, 857274757020001316639221394675820731579775247610619594760511, 444486969413575687285961819261097401974268741167841964919716, 645830958128126799221416466698967430939726760487764050203821, 128864469762235652994228226148325614187747349331618451490354, 732913002124581119538173953534485652651112140400076340646452, 1245672039639609341331477592944058028011275464117654972595670, 1160765030758624190775369713232721901616189349905945190302338, 745734132091942990384796294800038299023052878196943617322617, 34973161572808799782240527358912894045293050940490682156733, 507586651070816931641904112686082840821460472219390068396982, 359195216122538975934588740641220005777478961423841727365432, 60506687352654743312206686911057762445232526009857863834444, 402036521271253699065227780662896890228371046068283711170220, 465427226677337673103293964961886503610313835775181975449721, 925246962888172144515172444374190859841851825972285013006527, 542176614893876361668218387162168517498644799220587472896002, 852215132196560596695876248813488364201491362280912035912061, 945548964927065532651141821562204387565145712002346337639711, 736943822066388892909878515650831955490636214039062998720510, 766357526983761241394182000478355475617711906398422036954152, 77156525593382594092608158744099524034892127423492520631820, 562562817542804973601572838378263130638457829485887327130286, 768093992370198202822524520006977816845162154854939167515517, 1099957424762490943973557935337350760135180754563993547358098, 698816668614997174913438496891169625976027534942525487303513, 417641699919584202170293946436276552973997395211792288687960, 1006229610175567855209117721408416419896921240126676949824724, 4206431689326446028142220658552064336105749936096602165359, 893846509909828693967573302731018066461118006150050253703744, 878425189026235350891203121924637130803808920422558040493294, 730047416245095988472212050949689633327186823542036387345181, 648095719945750715387983948406690533087473721929975873848169, 213513454359755001454814601053555627585345770061082141021326, 350001050012957205656929492039628823072469208940960439158263, 1016858635000037892730835311903706149371704230428070443107320, 1040987439471207869975679257301693610464700899302787643642354, 1194690615352550474729309715449838057220521596135246725909553, 508165053077110820797186371383859674371399129952105597675096, 266494438294281492504556232035584920066331725618646155019547, 28469482072427012244441092412738741355431846649166066368980, 790175775999108776289865518368056397969387298334297622465909, 590581138260907253939363764832940322585129285968275409510634, 221909012579985462013325803334419731308959816500415305934495, 1063780559219791515938747204569742799329237935871594345400252, 977747525495509380693721486866821791065499754056415279744653, 346306061371595730004513789139807509540063462412619321003626, 456103179467597859705969406860196938169100856240100927540401, 969300078509189631808517876996065933181606409375207150288464, 1029806631220370012120597683927351131622576733031694535189521, 344896431603140401163996810922500893279239069499717183710501, 430000423804197030568046280589772094106128395099434235915031, 700179843567016021775399107572964843751703290591400960796112, 961227906080189143689698720420426659986080298413605666115640, 607209606799750473714271393200060455739097869884727178692312, 106958847163040842225140399905505511449479709017540851084532, 953369942103273809257762268859167463617831445026988544378658, 428269440686506672744282327102546440435442014650795927162711, 56621803434665963032193024056111306570802155743250152849716, 800707635631355839166448276143596444307614901816577459076131, 1032256515703247765067950588859299047987257001987777631061065, 813725055801254665600156259482200403981770576173968929131487, 940024839745068011043019236327963504645352520797347949823455, 1065005324140908547287467504568283884363143527586278243210801, 1087828777506290663525994551834233065465427418753806182842291, 668387132001968449612224853010931354244797738682007519611989, 563185246196177998134932666270526715161378776103340983046580, 148292872313931508344196679476720973752571125303712466045656, 413889563851226543249984374872220761253120628252088546262699, 853542105910386365929770611480736086723126396438880650918917, 59730458840715910492468261806200793684923819793480597554146, 792260492800286127199649276659137441324248689470594987965190, 753608630500639136668081531883097047491651258191552267413126, 33514911499472634865669915075769163328171019557849259474018, 634963859228206842307837566519244534650818456901841184879977, 219354096455968590219445072777282329948785844491217770978344, 1123377226439583158729762969668999276741275445803396272436031, 357765295513680388973981712560200525235334734759663454993805, 385868499980630535766019957877752149506518574529845752144666, 138578212294299392480319417966870656714476525885983752756188, 1110526796192425688386237355263892073046060477008920073455044, 244699783645221387947312903861559688207612147588246639081699, 583209905862562678600202085212425597809036630416117298854978, 1207854793808762194414317661151529169444903662139065050090746, 1127506983223466275821900811940356395242309493951089427884032, 526185119576631048584313761548704536031634598332129570964689, 266882032196696984660521486449809902101615921156569537960109, 1188118705564450461919200724390473040524626320052324478509883, 682831747455078454647149830819696088960233603851250102828667, 669419928942561433130809268138650695825596612075801278942980, 1077750630919867687880983437504767304166615787212813240073843, 486023540111308483450127320955599047045479654684477043315645, 409429366346146233850088863324915025465847596238000661872172, 779883595226131237594759409249289551033410304517183865388408, 1155872225708857920911178110668279174877878422508206228579940, 411063490066038942009369947241345843238439795078686488373864, 1243453053541946030699872676712518536022061850799945414120045, 871711034820169700581685353768658469631429266493677466057997, 601920686459160120670719526703980120744719013393032353678765, 329932100141177850249406090412821976994089707958551194468769, 558327299751202100333335353826111016492585371503632197870640, 113444032302978611299580451314055133491399096282744687816086, 152525914892717139057165748051966776217223953242540511499945, 965404850400527912039904270871065001313018148780552532312669, 313557099445185696402013375071955475516203519824979749629786, 952254159335810337756614972813240144837526566801182319987154]
mlist=''
n=1254676922968308054473282588201432441748387886551758353389559
p=1072611454669505004706159340329
q=1169740372905957258783752547871
for i in range(len(clist)):
    a1=gmpy2.jacobi(clist[i],n)
    if a1==(-1):
       mlist+='1'
    if a1==1:
        mlist+='0'
print(mlist)
s=int(mlist,2)
print(long_to_bytes(s))

解出flag：SYC{run_to_the_light}

Misc

圣嘉然

得到文件后，将其打开，但没有对应的打开方式，我选择用typora打开。打开后在一段乱码中看见了“请用winrar解压“，于是我将文件后缀修改为.rar。用WinRAR打开的时候提升文件损坏，于是我卡在了这一步。后来在用WinRAR时分析它有修复功能，将文件修复后解压，再通过360压缩打开，得到一个文豪野鼠.txt

利用hint给出的网站中的工具，得到一段打乱了顺序的字符串：s!yl}ce{gdniaa_nyam!ye0rua

将其进行栅栏密码的解码，栏数14，得到flag：syc{diana!y0u_are_my_angel!}

Canzik's Blog