MRCTF 2020 Crypto writeup

古典密码知多少

一张图，标准银河字母+圣堂武士+猪圈变形，在网上找密码表对照解出 FGCPFLIRTUASYON ,栅栏栏数3，FLAGISCRYPTOFUN。

flag：MRCTF{CRYPTOFUN}

天干地支+甲子

网上找天干地支对应的数字表，都加上 60 转 ascii 得到 Goodjob。

flag：MRCTF{Goodjob}

keyboard

对照九键键盘，重复次数就是某个按键的第几个字母，mobilephone。

flag：MRCTF{mobilephone}

vigenere

复制到在线网站就可以解了….比如这个 ，解开看最后一行。

flag：mrctf{vigenere_crypto_crack_man}

babyRSA

这题利用 P_p 和 P_factor 计算出 _P ，用 Q_1 ，Q_2 ，sub_Q 计算出 _Q ，然后解 RSA 就可以了。

P_p 往前找 9 个素数，约隔 1500 出现一个素数，递减枚举即可得到 P[0] ，得到 P 列表，然后就是解一个多素因子 n 的 RSA ，得到 _P .

_Q 就更简单了…把出题人故意写的 sub_Q ** Q_2 % Q_1 改成 pow(sub_Q,Q_2,Q_1) 就可以了。快速幂取模算法当然远比计算出结果再取模快得多。

exp：

import sympy
import random
from gmpy2 import gcd, invert
from Crypto.Util.number import *
from z3 import *
base = 65537
Ciphertext =  1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832
 
#计算_P
P_p =206027926847308612719677572554991143421
P_factor =213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
t=0
while t<9:
      P_p-=2
      if isPrime(P_p):t+=1
#print(P_p)
#206027926847308612719677572554991142909
 
P = [0 for i in range(17)]
P[0] = 206027926847308612719677572554991142909
for i in range(1, 17):
      P[i] = sympy.nextprime(P[i-1])
phi_n=1
n=1
for i in range(17):
      phi_n *= P[i]-1
      n *= P[i]
p=pow(P_factor,invert(base,phi_n),n)
_P=sympy.nextprime(p)
 
#计算_Q
def gen_q():
      Q_1=103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521
      Q_2=151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743
      sub_Q=168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651
      Q = pow(sub_Q,Q_2,Q_1)
      return sympy.nextprime(Q)
_Q = gen_q()
 
#解RSA
_E = base
_M = pow(Ciphertext, invert(_E,(_P-1)*(_Q-1)), _P * _Q)
M=long_to_bytes(_M)
print(M)
flag：MRCTF{
    sti11_@_b@by_qu3st10n}

Easy_RSA

这题还是计算出 _P 和 _Q 解 RSA 的题。

1. 先是利用 n 和 phi_n ，算出 p 和 q，n=p∗q ，phi_n=(p−1)∗(q−1)=p∗q−p−q−1 , 所以 p+q=n−phi_n−1 , 令 k=n−phi_n−1,把 p=k−q 带入到 n=p∗q 中就可以作为二次函数利用单调性二分法求解了，时间复杂度 O(logn) 相当快，脚本在这里。这样 _P 就有了。

2. 另一个问题是用给出的 n 和 e*d 分解出 p 和 q , 这个算法可以直接用…
   
   exp:

import base64
from random import randint
import sympy
from Crypto.Util.number import bytes_to_long, getPrime, getRandomNBitInteger,isPrime, long_to_bytes
from gmpy2 import gcd, invert

Ciphertext = 40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021
_E = 65537
q = 118975085954858660642562584152139261422493348532593400307960127317249511761542030451912561362687361053191375307180413931721355251895350936376781657674896801388806379750757264377396608174235075021854614328009897408824235800167369204203680938298803752964983358298299699273425596382268869237139724754214443556383
p = 118153578345562250550767057731385782963063734586321112579869747650001448473633860305142281504862521928246520876300707405515141444727550839066835195905927281903880307860942630322499106164191736174201506457157272220802515607939618476716593888428832962374494147723577980992661629254713116923690067827155668889571
assert (p < q)
factor2 = 2021 * p + 2020 * q
_P = sympy.nextprime(factor2)

Q_n = 20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
Q_E_D = 100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
f, s, tem = Q_E_D-1, 0, 1
while f % 2 == 0:
    f = f // 2
    s += 1
i, a, t = s, 2, f
b = pow(a, t, Q_n)
while b == 1:
    a = sympy.nextprime(a)
    b = pow(a, t, Q_n)

while i != 1:
    c = pow(b, 2, Q_n)
    if c != 1:
        b = c
        i -= 1
    else:
        break
if b == Q_n-1:
    a = sympy.nextprime(a)
    b = pow(a, t, Q_n)
    while b == 1:
        a = sympy.nextprime(a)
        b = pow(a, t, Q_n)

p = gcd(b-1, Q_n)
q = Q_n//p
factor2 = 2021 * p - 2020 * q
if factor2 < 0:
    factor2 = (-1) * factor2
_Q = sympy.nextprime(factor2)

_M = pow(Ciphertext, invert(_E, (_P-1)*(_Q-1)), _Q*_P)
m = long_to_bytes(_M)
print(m)

flag：MRCTF{Ju3t_@_31mp13_que3t10n}

real_random

感觉这题主要代码就是下面截取的部分，对 x 进行若干次 (b * x + c) % m 运算，最后会得到 gen_N(flag[t]) ，所以只要知道第几个 i 是满足random[t][i] = gen_N(flag[t]) 就可以了，尝试了几次发现得到的 i 是和 c 是无关的，当然也是和 gen_N(flag[t]) 无关。

x = ((gen_N(flag[t]) - c) * _b) % m
for i in range(2**d):
    x = (b * x + c) % m
for i in range(times):
    x = (b * x + c) % m
    random[t][i] = x

既然 i 的值仅与 p , q , d 等变量有关，那么就可以自定义一个数 K 来代替 flag[t] ，本地利用给出的 p , q , d 算出其他变量(p q 很容易用 M 枚举出来)，一模一样的跑一遍和服务器上一样的程序，本地得到的 i 就一定是服务器上的 i ，send 上去就可以了。

得到的是 (flag * 16^2) + flag 的结果，对 16^2 取模就是 flag 。

exp：

from pwn import *
from Crypto.Util.number import*
from gmpy2 import*
import re
 
host, port = ('38.39.244.2', 28101)
r = remote(host, port)
 
null = r.recvline().decode()
null = r.recvline().decode()
 
def gen_N(flag):
    return (flag * 16**2) + flag
 
def reM(M):
    p = getPrime(6)
    q = getPrime(6)
    while (p-1)*(q-1) != M:
        p = getPrime(6)
        q = getPrime(6)
    m = p * q * 2 ** 5
    b = 4 * p * q + 1
    return (b, m)
 
def Slove(M, d):
    b, m = reM(M)
    c = getPrime(10)
    _b = invert(b, m)
    times = getPrime(19)
    x = ((gen_N(102) - c) * _b) % m
    for i in range(2**d):
        x = (b * x + c) % m
    for i in range(times):
        x = (b * x + c) % m
        if x == gen_N(102):
            return i
            break
 
ans = b''
while True:
    r. recvuntil('m:  ')
    M = r.recv(4).decode()
    r. recvuntil('d:  ')
    d = r.recv(2).decode()
    M = int(M)
    d = int(d)
    r. recvuntil('Now guess where the flag is ^_^ ')
    I = Slove(M, d)
    print('I=', str(I))
    r. send(str(I)+'\n')
    r. recvuntil('\n')
    k = int(r. recvline().strip(). decode())
    k %= 16**2
    ans += long_to_bytes(k)
    print(ans)

flag：MRCTF{It_13_n0t_r3@11y_r@nd0m}