20210706-PWNHUB7月公开赛-CryptoSecPartWriteUp

 

MathCrypto

题目描述

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'flag{********************}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
    for b in plaintext:
        e = randint(1, p)
        n = pow(a, e, p)
        if b == '1':
            ciphertext.append(n)
        else:
            n = -n % p
            ciphertext.append(n)
    return ciphertext


print(encrypt_flag(FLAG))

解题思路

核心代码是
$$
n_i=a^{e_i}mod\ p\notag
$$
已知p是素数，e是[1, p]中的一个随机数，通过n来求这一位是1还是0

我的思路一是费马小定理，因为p是素数所以满足
$$
a^{p-1}\equiv 1\ mod\ p\notag
$$
不过也不知道怎么继续了；二是中国剩余定理，够构造一些列的同余式，但苦于d没有办法爆破得到

尚师傅说可以直接用discrete_log

解题脚本

简单试验了几个

如果找不到离散对数就会报错，可以用异常处理

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# 为了使用Python2的print不换行
from __future__ import print_function

a = 288260533169915
p = 1007621497415251
n = [835573322319412, 194156231145433, 459240835091427, 254691265527581, 452163501868176, 362769806018159, 390335330574588, 795683531947695, 547245847322642, 662157248109028, 973966064208336, 252129990307548, 578699863722488, 486222427902568, 117477413047771, 740421014593358, 863241886290392, 222275563655891, 293327716717603, 708319736688481, 889074509131674, 417808854196549, 131645986814206, 249411728529916, 500308738571101, 178419560186091, 441524245815824, 270385977926445, 134464725515031, 34977330760372, 789037598270288, 871556001954572, 42895524249924, 602041422192220, 45250560584859, 836594396205340, 154261010116600, 906631913900110, 73716306230031, 57491432561272, 937546091143710, 573584711515529, 117838942375694, 108224759885936, 686520256664437, 328396509053949, 964793767786949, 952055129356587, 570054348386776, 132721379375751, 421580578207025, 302791761439275, 558510385173476, 7941240282405, 10928401173457, 382447756114972, 169542347967514, 977453208629407, 460734109220968, 573505124794720, 318306022981107, 120648106475963, 807138639422627, 996507910024607, 102816788391640, 660745079166409, 809890775939749, 832519292688500, 87538065186141, 637100151940331, 382113003094066, 470655145986067, 644778242358267, 517586163010705, 558938708706131, 150978345005135, 102930326517355, 782154305431595, 6219189599369, 243324433725873, 650527665111501, 100280527101388, 1005535261333789, 987714102930385, 1002475950204796, 922079478085088, 906834270364060, 53211341275436, 965041750990423, 77115141669784, 588069693290238, 794822251044102, 930830807276545, 201161070608812, 568151623857765, 678968180937073, 412380912864953, 162493098979490, 631342883381540, 261680062360627, 227532833267531, 251016357185685, 827419020607751, 858376422971452, 362277983384639, 527363637534876, 334777651780889, 210527722411428, 808789791291861, 520556222865899, 704810558642854, 568037991932850, 169208358508287, 413145308937205, 599769322994671, 441328336467023, 849181035363926, 83477340978714, 80594200850041, 660277475107773, 928502236651086, 790965510818429, 135278692982626, 424887158380721, 411620739036446, 135280586082276, 714308921541654, 9109479300877, 650573139284244, 870861989942716, 443255252246208, 70455275832571, 369440682873276, 515899628421991, 612793429865648, 723589985084253, 160660351599873, 846726628855115, 8027417644170, 922790558110918, 329372648478795, 363470140166698, 86704784885484, 854835234890991, 976023205217544, 652708649867132, 388967328647036, 559512066466403, 36971809912721, 335187129410393, 6855900757516, 543488958018354, 287382478990521, 439225225775323, 661397580381098, 773933897777421, 523567536261705, 390598723653906, 417048954790947, 637431635583415, 335090251298424, 206308145752203, 501544720775707, 614789886972475, 357742401606467, 289036983452171, 668519107118940, 92139870679256, 388797793877078, 372191799798178, 1004628632761505, 145521166059580, 576232295004932, 119635574132509, 216801862623375, 155870719957478, 28321309890983, 732905921144578, 791832670754979, 671433181708904, 435663032194545, 316031621753570, 220369837362135, 356539134058642, 360074630241799, 764194424366054, 46729635512483, 924976743846057, 646158916629764, 894838984085320, 757222585897598, 829482878889900, 838347423444759, 590218802707709, 793621010210316, 79947449693367, 739723478650329, 163281924014926, 808389762984067, 208262587169431, 582578916561821, 478856137518673, 650032839378814, 58022200409911, 17291737478946, 919921371618469, 473933973533026, 861870666818810]
a = mod(a, p)
ni = [mod(_, p) for _ in n]
flag = ''
for t in ni:
    try:
        e = discrete_log(t, a)
        flag += '1'
    except:
        flag += '0'
    finally:
        print(flag)
# flag = '0110011001101100011000010110011101111011010100000110000101110100011101000011001101110010011011100111001101011111001100010110111001011111011100100110010100110101011010010110010001110101001100110111001101111101'

for i in range(0, len(flag), 8):
    print(chr(int(flag[i:i+8], 2)), end='')

跑了很久，最后得到flag

flag{Patt3rns_1n_re5idu3s}