题目收集

发表于 2023-07-17 更新于 2024-07-12 阅读次数： Waline：本文字数： 13k 阅读时长 ≈ 46 分钟

记录一些长知识的题目

easyrandom

from random import Random
from hashlib import md5
rng = Random()
leak = []
for i in range(1250):
    leak.append(rng.getrandbits(16))
m = rng.getrandbits(64)
flag = "flag{"+str(m)+"}"
print(flag)
flag_md5 = md5(flag.encode()).hexdigest()
f = open("output.txt","w")
f.write(f"leak = {leak}\n")
f.write(f"flag_md5 = {flag_md5}\n")
f.close()

1
2

leak = [47945, 50431, 10861, 5794, 26338, 2641, 58647, 52422, 35384, 50426, 58144, 2744, 7864, 25333, 3500, 59273, 38075, 38630, 18760, 19660, 54418, 53538, 20251, 25758, 4500, 14384, 40765, 43841, 62662, 64548, 6468, 8997, 20572, 9920, 64146, 49443, 32054, 56082, 21773, 38390, 14905, 47230, 43126, 37449, 1016, 23685, 48461, 13070, 58381, 51813, 48909, 10953, 31195, 1703, 33439, 54463, 63977, 29188, 44901, 53588, 32843, 9923, 2188, 42503, 53555, 44818, 55094, 40544, 25787, 34965, 65151, 37069, 6342, 36889, 51214, 58386, 34925, 9558, 33552, 29554, 30350, 20166, 4221, 61353, 50656, 7337, 1001, 18279, 27268, 49581, 37870, 54591, 12438, 13649, 42007, 33542, 18118, 48407, 34338, 12147, 19178, 8925, 31109, 12296, 52419, 392, 9296, 16055, 64775, 46394, 58494, 24157, 62237, 16211, 23935, 10368, 48440, 60061, 47813, 49032, 50836, 18404, 30552, 7142, 44142, 44549, 36078, 63112, 28345, 39821, 10004, 32221, 16021, 32152, 53113, 13857, 49328, 11817, 27777, 43088, 43453, 29962, 16338, 44353, 27974, 25145, 56050, 34129, 39236, 46167, 64639, 54581, 33004, 35652, 16294, 11109, 19396, 51476, 30332, 24701, 43628, 44507, 27688, 37172, 61339, 9893, 45217, 7969, 33523, 2495, 15578, 55444, 48564, 5055, 16048, 8512, 1819, 19702, 13388, 41099, 30256, 10592, 46063, 30881, 8338, 41214, 55255, 50060, 65028, 9114, 8417, 43767, 62760, 49830, 50660, 19358, 22142, 53025, 37930, 49155, 2150, 56194, 36251, 49654, 32395, 33677, 48743, 12627, 30575, 64001, 60220, 26908, 44207, 23532, 18430, 45511, 33553, 62631, 55155, 58715, 59152, 20864, 14790, 32774, 48679, 24325, 54109, 2747, 17046, 19083, 60413, 11773, 42188, 17011, 13361, 2105, 23067, 45439, 1122, 54117, 31435, 49692, 59556, 51893, 24342, 11073, 52326, 23237, 22930, 12691, 38125, 36714, 54043, 34880, 53599, 18609, 36631, 24367, 49135, 26821, 64486, 12154, 37534, 14100, 33744, 37183, 7652, 26403, 42166, 12290, 32315, 19153, 55490, 4558, 60768, 44149, 26258, 38676, 31228, 43610, 39357, 36475, 29434, 41437, 64762, 5251, 33641, 43819, 29769, 38136, 8348, 33123, 17571, 18343, 50569, 55502, 7371, 14515, 41553, 12979, 1276, 45454, 56057, 51518, 30382, 30678, 60443, 58274, 50882, 64918, 34569, 58195, 34410, 47490, 13676, 37502, 61987, 7616, 11528, 13577, 51098, 5435, 51972, 63061, 55995, 21627, 2439, 47554, 6891, 53790, 62563, 38921, 30600, 49498, 49671, 38844, 42840, 49982, 16503, 13854, 63825, 25195, 41078, 36872, 36288, 63461, 29293, 28630, 23547, 57332, 43051, 49205, 14579, 23897, 944, 47223, 6819, 61851, 57886, 10858, 14380, 35796, 4509, 52576, 47112, 44349, 56553, 45075, 31505, 2779, 17216, 47395, 15024, 26498, 25299, 26548, 39954, 33242, 65187, 33291, 38861, 6956, 4371, 11762, 41126, 54447, 56384, 34835, 595, 52198, 13324, 38653, 21103, 34301, 20781, 64650, 17773, 1921, 46490, 37683, 27720, 7812, 49737, 20423, 16452, 52475, 27896, 49613, 60121, 54986, 30680, 37740, 8407, 30833, 29431, 62841, 27957, 57755, 59153, 44802, 42423, 28202, 54075, 3879, 25261, 57958, 53266, 22806, 64334, 34962, 57708, 20653, 17925, 59244, 38640, 31264, 7962, 5234, 16995, 35712, 39263, 33764, 9168, 59263, 6297, 28879, 54753, 31041, 42448, 57238, 52395, 61412, 29370, 52297, 21906, 36837, 62511, 13185, 53251, 47459, 47320, 24874, 5152, 63178, 20614, 808, 6789, 37043, 9713, 31692, 18319, 60295, 9628, 1053, 54874, 26808, 28046, 27964, 7534, 43316, 51573, 51143, 41954, 16366, 19618, 23676, 63245, 28329, 25170, 55118, 49376, 22296, 41638, 42595, 49291, 51001, 21173, 17098, 11956, 33292, 28909, 63160, 63480, 32649, 49809, 24112, 59503, 38840, 22914, 17473, 51978, 25420, 64060, 58894, 35793, 57163, 59038, 58787, 64067, 55780, 61906, 1696, 156, 25499, 57706, 47842, 47243, 14668, 17052, 57195, 53288, 49178, 2557, 31221, 17492, 11560, 23012, 9147, 44260, 22094, 53197, 40404, 21209, 30940, 18586, 48011, 60631, 8838, 13044, 5480, 19584, 20231, 15078, 58154, 8305, 55680, 49974, 2861, 58626, 61041, 47937, 42776, 35207, 39418, 12989, 1507, 5082, 23278, 26969, 10328, 18480, 34160, 55965, 59869, 197, 38066, 17097, 49306, 12749, 21846, 9946, 12323, 39813, 19141, 14950, 15987, 33630, 14715, 52499, 15978, 24078, 60217, 32262, 11645, 1649, 50062, 21979, 30545, 1450, 48657, 41697, 23357, 17880, 27613, 38277, 54988, 11074, 57591, 183, 62803, 8532, 61133, 26944, 63400, 53095, 8663, 59702, 19325, 24726, 51297, 21286, 2373, 38774, 20677, 29443, 24693, 20621, 14031, 45485, 34645, 9926, 12620, 1406, 41462, 50338, 25841, 61724, 41722, 11520, 48377, 34111, 50805, 23351, 64363, 50091, 35487, 49978, 41001, 37117, 17133, 54868, 58918, 17295, 16857, 45165, 5732, 46277, 54359, 64982, 2336, 61929, 40501, 18901, 39938, 949, 45839, 7519, 36935, 55287, 21096, 44443, 12240, 16160, 28355, 42275, 27747, 13398, 12395, 33973, 17137, 60697, 37064, 27782, 45671, 22264, 505, 20989, 57585, 4283, 43110, 28497, 25900, 16383, 13961, 24192, 29296, 34776, 36286, 18398, 55882, 28748, 54021, 673, 22723, 23699, 48463, 17316, 55309, 54229, 28342, 11147, 16132, 24344, 53367, 45597, 42843, 27078, 4034, 16975, 18534, 29674, 36962, 60773, 8030, 17118, 7392, 41627, 44768, 51104, 10876, 16293, 54589, 65082, 62573, 2679, 23869, 61905, 52526, 51584, 57063, 27294, 51821, 9070, 30961, 38741, 36309, 57422, 58231, 32775, 57469, 2306, 43632, 6110, 17478, 3399, 60718, 23947, 21488, 41712, 43552, 34154, 35374, 17522, 16603, 53459, 52136, 49823, 21443, 35049, 4854, 25769, 63782, 21355, 11189, 17330, 41173, 6620, 24475, 40910, 26100, 34752, 10491, 39327, 561, 24612, 36253, 41875, 1589, 44536, 64133, 37260, 24719, 21955, 40847, 8529, 12294, 22158, 31784, 32185, 18438, 9983, 9362, 46554, 8294, 11447, 38253, 32008, 44252, 14392, 36259, 40422, 53018, 41387, 61549, 43601, 24082, 64942, 50817, 18470, 52024, 19769, 38618, 54451, 44579, 48552, 52967, 3546, 13047, 19986, 752, 25560, 33608, 55220, 35170, 17378, 3632, 7932, 12764, 28016, 51153, 42067, 22380, 11170, 35549, 14546, 6725, 50718, 40157, 54482, 45086, 50180, 44396, 19469, 48734, 9003, 32234, 4973, 19031, 32744, 15216, 11167, 31666, 50585, 28017, 56213, 23276, 62789, 19240, 52247, 51360, 23933, 2117, 23909, 20136, 11108, 55792, 10848, 42772, 52949, 20973, 49997, 20027, 26803, 34251, 18768, 1273, 21372, 57638, 43004, 27339, 51671, 4505, 7193, 64268, 15856, 9038, 63520, 62076, 41936, 27929, 23469, 55533, 25007, 31555, 15349, 11603, 51345, 44304, 49007, 35765, 50361, 48434, 41407, 41415, 27322, 45767, 56009, 17808, 36797, 55785, 18842, 27904, 55984, 54213, 25742, 30451, 13819, 37675, 23224, 18337, 63137, 40370, 39116, 53931, 7352, 5724, 14040, 13609, 34023, 39058, 59660, 20699, 5752, 594, 53440, 58700, 58977, 11902, 11358, 54271, 52581, 63883, 4496, 65446, 8092, 32955, 1788, 7547, 30827, 42738, 51248, 13433, 52570, 45277, 4811, 59546, 17021, 32981, 6168, 45440, 41446, 43907, 44327, 22960, 48214, 53682, 39618, 65392, 31131, 36083, 31230, 15227, 1530, 21222, 11049, 27763, 5251, 56978, 12249, 55352, 54216, 24824, 65111, 21374, 42945, 57027, 3920, 32541, 65155, 12251, 19929, 19866, 58236, 22788, 54575, 53449, 16521, 55829, 14990, 8653, 55846, 6198, 24332, 28673, 50260, 60726, 55293, 35325, 4142, 28883, 19302, 31711, 10833, 62836, 27199, 14853, 21172, 61281, 43290, 23364, 62192, 58280, 64481, 40708, 17966, 54004, 1651, 1008, 12674, 54156, 48976, 60163, 47799, 14781, 37556, 58786, 14677, 16666, 22398, 41273, 22312, 49859, 4327, 54222, 52527, 35043, 35462, 33939, 30396, 17371, 10883, 42056, 31285, 7486, 33758, 62824, 58144, 19003, 17210, 28590, 39138, 20818, 58339, 7397, 30592, 54635, 33004, 6524, 54578, 21592, 33877, 37330, 51484, 18861, 26317, 426, 6365, 34363, 21922, 33037, 22209, 63283, 6463, 22503, 32397, 54053, 8538, 37449, 39658, 34111, 49684, 27364, 55762, 2892, 64875, 17558, 45202, 37747, 61781, 39006, 5, 55444, 4965, 65360, 45810, 23739, 51172, 37274, 39909, 58863, 28111, 449, 14406, 62190, 13688, 57145, 23653, 56791, 4065, 13079, 59309, 57940, 59317, 17968, 28037, 27233, 53242, 30901, 10758, 57188, 9100, 51760, 16566, 20555, 50514, 35271, 59680, 24646, 14768, 13335, 30246, 39364, 51795, 5031, 38107, 32158, 443, 10384, 6774, 47929, 15499, 50368, 51827, 54022, 18908, 2157, 9827, 14658, 16901, 40891, 5884, 51302, 10387, 10960, 16761, 26793, 55085, 35673, 35137, 13497, 28211, 60579, 60497, 47403, 9106, 59526, 10327, 8063, 41945, 5754, 57621, 26709, 22739, 25547, 24703, 20746, 3895, 44111, 51320, 42212, 59781, 29064, 44610, 16431, 39515, 18156, 14210, 27507, 47206, 41530, 44123, 29499, 47242, 50363, 3339, 57490, 36566, 48636, 49784, 10942, 64447, 26791, 52829, 53204, 55163, 32261, 32157, 58261, 41129, 60614, 30034, 55489, 55576, 25052, 4263, 32514, 1419, 22605, 56589, 48192, 44655, 61295, 8855, 42987, 26448, 33214, 46651, 56194, 28472, 12965]
flag_md5 = f5accae4111e6f6db6d4342a7662b970

exp:

from sage.all import *
from random import Random
from tqdm import *
prng = Random()
length = 19968

def myState():
    state = [0]*624
    i = 0
    while i<length:
        ind = i//32
        expont = i%32
        state[ind] = 1<<(31-expont)
        s = (3,tuple(state+[0]),None)
        yield s
        state[ind] = 0
        i += 1


def getRow():
    rng = Random()
    gs = myState()
    for i in range(length):
        s = next(gs)
        rng.setstate(s)
#         print(s[1][0])
        data=[]
        for i in range(length // 16):
            data.extend(list(bin(rng.getrandbits(16))[2:].zfill(16)))
        data=[int(i) for i in data]
        row = vector(GF(2),data)
        yield row

def buildBox():
    b = matrix(GF(2),length,length)
    rg = getRow()
    for i in tqdm(range(length)):
        b[i] = next(rg)
    return b


def test():
    prng = Random()
    originState = prng.getstate()
    # 这里都是用的MSB,如果采用不同的二进制位(如LSB)最后的矩阵T 也会不同
    leak=[]
    for i in range(length // 16):
        leak.extend(list(bin(prng.getrandbits(16))[2:].zfill(16)))
    leak=[int(i) for i in leak]
    leak = vector(GF(2),leak)
    T = buildBox()
    with open("Matirx","w") as f:
        for i in trange(T.nrows()):
            for j in range(T.ncols()):
                f.write(str(T[i,j])+'n')
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i*32:(i+1)*32],2)
        state.append(tmp)
    prng.setstate(originState)
    prng.getrandbits(16)
    originState = [x for x in prng.getstate()[1][:-1]]
    print(originState[1:] == state[1:])
#     print(state)
    return state,T

from sage.all import *
from random import Random
from tqdm import tqdm
from build_matrix import test
# 根据文件中的信息，构造矩阵
length = 19968

def buildMatrix():
    with open("Matrix","r") as f:
        data = [int(x) for x in f.read().split('n')]
    m=matrix(GF(2),length,length,data)
    return m




# X = Z*(T^-1)
def recoverState(T,leak):
    x = T.solve_left(leak)
    x = ''.join([str(i) for i in x.list()])
    state = []
    for i in range(624):
        tmp = int(x[i * 32:(i + 1) * 32], 2)
        state.append(tmp)
    return state


# 根据题型2,还原state,有两种可能,这时候可以用暴破
def backfirst(state):
    high = 0x80000000
    low = 0x7fffffff
    mask = 0x9908b0df
    tmp = state[623] ^ state[396]
    if tmp & high == high:
        tmp ^= mask
        tmp <<= 1
        tmp |= 1
    else:
        tmp <<= 1
    return (1 << 32 - 1) | tmp & low, tmp & low


def main():
    _, T = test()
    print('构建完成')
    print("T完成")
    prng = Random()
    originState = prng.getstate()
    leak=[47945, 50431, 10861, 5794, 26338, 2641, 58647, 52422, 35384, 50426, 58144, 2744, 7864, 25333, 3500, 59273, 38075, 38630, 18760, 19660, 54418, 53538, 20251, 25758, 4500, 14384, 40765, 43841, 62662, 64548, 6468, 8997, 20572, 9920, 64146, 49443, 32054, 56082, 21773, 38390, 14905, 47230, 43126, 37449, 1016, 23685, 48461, 13070, 58381, 51813, 48909, 10953, 31195, 1703, 33439, 54463, 63977, 29188, 44901, 53588, 32843, 9923, 2188, 42503, 53555, 44818, 55094, 40544, 25787, 34965, 65151, 37069, 6342, 36889, 51214, 58386, 34925, 9558, 33552, 29554, 30350, 20166, 4221, 61353, 50656, 7337, 1001, 18279, 27268, 49581, 37870, 54591, 12438, 13649, 42007, 33542, 18118, 48407, 34338, 12147, 19178, 8925, 31109, 12296, 52419, 392, 9296, 16055, 64775, 46394, 58494, 24157, 62237, 16211, 23935, 10368, 48440, 60061, 47813, 49032, 50836, 18404, 30552, 7142, 44142, 44549, 36078, 63112, 28345, 39821, 10004, 32221, 16021, 32152, 53113, 13857, 49328, 11817, 27777, 43088, 43453, 29962, 16338, 44353, 27974, 25145, 56050, 34129, 39236, 46167, 64639, 54581, 33004, 35652, 16294, 11109, 19396, 51476, 30332, 24701, 43628, 44507, 27688, 37172, 61339, 9893, 45217, 7969, 33523, 2495, 15578, 55444, 48564, 5055, 16048, 8512, 1819, 19702, 13388, 41099, 30256, 10592, 46063, 30881, 8338, 41214, 55255, 50060, 65028, 9114, 8417, 43767, 62760, 49830, 50660, 19358, 22142, 53025, 37930, 49155, 2150, 56194, 36251, 49654, 32395, 33677, 48743, 12627, 30575, 64001, 60220, 26908, 44207, 23532, 18430, 45511, 33553, 62631, 55155, 58715, 59152, 20864, 14790, 32774, 48679, 24325, 54109, 2747, 17046, 19083, 60413, 11773, 42188, 17011, 13361, 2105, 23067, 45439, 1122, 54117, 31435, 49692, 59556, 51893, 24342, 11073, 52326, 23237, 22930, 12691, 38125, 36714, 54043, 34880, 53599, 18609, 36631, 24367, 49135, 26821, 64486, 12154, 37534, 14100, 33744, 37183, 7652, 26403, 42166, 12290, 32315, 19153, 55490, 4558, 60768, 44149, 26258, 38676, 31228, 43610, 39357, 36475, 29434, 41437, 64762, 5251, 33641, 43819, 29769, 38136, 8348, 33123, 17571, 18343, 50569, 55502, 7371, 14515, 41553, 12979, 1276, 45454, 56057, 51518, 30382, 30678, 60443, 58274, 50882, 64918, 34569, 58195, 34410, 47490, 13676, 37502, 61987, 7616, 11528, 13577, 51098, 5435, 51972, 63061, 55995, 21627, 2439, 47554, 6891, 53790, 62563, 38921, 30600, 49498, 49671, 38844, 42840, 49982, 16503, 13854, 63825, 25195, 41078, 36872, 36288, 63461, 29293, 28630, 23547, 57332, 43051, 49205, 14579, 23897, 944, 47223, 6819, 61851, 57886, 10858, 14380, 35796, 4509, 52576, 47112, 44349, 56553, 45075, 31505, 2779, 17216, 47395, 15024, 26498, 25299, 26548, 39954, 33242, 65187, 33291, 38861, 6956, 4371, 11762, 41126, 54447, 56384, 34835, 595, 52198, 13324, 38653, 21103, 34301, 20781, 64650, 17773, 1921, 46490, 37683, 27720, 7812, 49737, 20423, 16452, 52475, 27896, 49613, 60121, 54986, 30680, 37740, 8407, 30833, 29431, 62841, 27957, 57755, 59153, 44802, 42423, 28202, 54075, 3879, 25261, 57958, 53266, 22806, 64334, 34962, 57708, 20653, 17925, 59244, 38640, 31264, 7962, 5234, 16995, 35712, 39263, 33764, 9168, 59263, 6297, 28879, 54753, 31041, 42448, 57238, 52395, 61412, 29370, 52297, 21906, 36837, 62511, 13185, 53251, 47459, 47320, 24874, 5152, 63178, 20614, 808, 6789, 37043, 9713, 31692, 18319, 60295, 9628, 1053, 54874, 26808, 28046, 27964, 7534, 43316, 51573, 51143, 41954, 16366, 19618, 23676, 63245, 28329, 25170, 55118, 49376, 22296, 41638, 42595, 49291, 51001, 21173, 17098, 11956, 33292, 28909, 63160, 63480, 32649, 49809, 24112, 59503, 38840, 22914, 17473, 51978, 25420, 64060, 58894, 35793, 57163, 59038, 58787, 64067, 55780, 61906, 1696, 156, 25499, 57706, 47842, 47243, 14668, 17052, 57195, 53288, 49178, 2557, 31221, 17492, 11560, 23012, 9147, 44260, 22094, 53197, 40404, 21209, 30940, 18586, 48011, 60631, 8838, 13044, 5480, 19584, 20231, 15078, 58154, 8305, 55680, 49974, 2861, 58626, 61041, 47937, 42776, 35207, 39418, 12989, 1507, 5082, 23278, 26969, 10328, 18480, 34160, 55965, 59869, 197, 38066, 17097, 49306, 12749, 21846, 9946, 12323, 39813, 19141, 14950, 15987, 33630, 14715, 52499, 15978, 24078, 60217, 32262, 11645, 1649, 50062, 21979, 30545, 1450, 48657, 41697, 23357, 17880, 27613, 38277, 54988, 11074, 57591, 183, 62803, 8532, 61133, 26944, 63400, 53095, 8663, 59702, 19325, 24726, 51297, 21286, 2373, 38774, 20677, 29443, 24693, 20621, 14031, 45485, 34645, 9926, 12620, 1406, 41462, 50338, 25841, 61724, 41722, 11520, 48377, 34111, 50805, 23351, 64363, 50091, 35487, 49978, 41001, 37117, 17133, 54868, 58918, 17295, 16857, 45165, 5732, 46277, 54359, 64982, 2336, 61929, 40501, 18901, 39938, 949, 45839, 7519, 36935, 55287, 21096, 44443, 12240, 16160, 28355, 42275, 27747, 13398, 12395, 33973, 17137, 60697, 37064, 27782, 45671, 22264, 505, 20989, 57585, 4283, 43110, 28497, 25900, 16383, 13961, 24192, 29296, 34776, 36286, 18398, 55882, 28748, 54021, 673, 22723, 23699, 48463, 17316, 55309, 54229, 28342, 11147, 16132, 24344, 53367, 45597, 42843, 27078, 4034, 16975, 18534, 29674, 36962, 60773, 8030, 17118, 7392, 41627, 44768, 51104, 10876, 16293, 54589, 65082, 62573, 2679, 23869, 61905, 52526, 51584, 57063, 27294, 51821, 9070, 30961, 38741, 36309, 57422, 58231, 32775, 57469, 2306, 43632, 6110, 17478, 3399, 60718, 23947, 21488, 41712, 43552, 34154, 35374, 17522, 16603, 53459, 52136, 49823, 21443, 35049, 4854, 25769, 63782, 21355, 11189, 17330, 41173, 6620, 24475, 40910, 26100, 34752, 10491, 39327, 561, 24612, 36253, 41875, 1589, 44536, 64133, 37260, 24719, 21955, 40847, 8529, 12294, 22158, 31784, 32185, 18438, 9983, 9362, 46554, 8294, 11447, 38253, 32008, 44252, 14392, 36259, 40422, 53018, 41387, 61549, 43601, 24082, 64942, 50817, 18470, 52024, 19769, 38618, 54451, 44579, 48552, 52967, 3546, 13047, 19986, 752, 25560, 33608, 55220, 35170, 17378, 3632, 7932, 12764, 28016, 51153, 42067, 22380, 11170, 35549, 14546, 6725, 50718, 40157, 54482, 45086, 50180, 44396, 19469, 48734, 9003, 32234, 4973, 19031, 32744, 15216, 11167, 31666, 50585, 28017, 56213, 23276, 62789, 19240, 52247, 51360, 23933, 2117, 23909, 20136, 11108, 55792, 10848, 42772, 52949, 20973, 49997, 20027, 26803, 34251, 18768, 1273, 21372, 57638, 43004, 27339, 51671, 4505, 7193, 64268, 15856, 9038, 63520, 62076, 41936, 27929, 23469, 55533, 25007, 31555, 15349, 11603, 51345, 44304, 49007, 35765, 50361, 48434, 41407, 41415, 27322, 45767, 56009, 17808, 36797, 55785, 18842, 27904, 55984, 54213, 25742, 30451, 13819, 37675, 23224, 18337, 63137, 40370, 39116, 53931, 7352, 5724, 14040, 13609, 34023, 39058, 59660, 20699, 5752, 594, 53440, 58700, 58977, 11902, 11358, 54271, 52581, 63883, 4496, 65446, 8092, 32955, 1788, 7547, 30827, 42738, 51248, 13433, 52570, 45277, 4811, 59546, 17021, 32981, 6168, 45440, 41446, 43907, 44327, 22960, 48214, 53682, 39618, 65392, 31131, 36083, 31230, 15227, 1530, 21222, 11049, 27763, 5251, 56978, 12249, 55352, 54216, 24824, 65111, 21374, 42945, 57027, 3920, 32541, 65155, 12251, 19929, 19866, 58236, 22788, 54575, 53449, 16521, 55829, 14990, 8653, 55846, 6198, 24332, 28673, 50260, 60726, 55293, 35325, 4142, 28883, 19302, 31711, 10833, 62836, 27199, 14853, 21172, 61281, 43290, 23364, 62192, 58280, 64481, 40708, 17966, 54004, 1651, 1008, 12674, 54156, 48976, 60163, 47799, 14781, 37556, 58786, 14677, 16666, 22398, 41273, 22312, 49859, 4327, 54222, 52527, 35043, 35462, 33939, 30396, 17371, 10883, 42056, 31285, 7486, 33758, 62824, 58144, 19003, 17210, 28590, 39138, 20818, 58339, 7397, 30592, 54635, 33004, 6524, 54578, 21592, 33877, 37330, 51484, 18861, 26317, 426, 6365, 34363, 21922, 33037, 22209, 63283, 6463, 22503, 32397, 54053, 8538, 37449, 39658, 34111, 49684, 27364, 55762, 2892, 64875, 17558, 45202, 37747, 61781, 39006, 5, 55444, 4965, 65360, 45810, 23739, 51172, 37274, 39909, 58863, 28111, 449, 14406, 62190, 13688, 57145, 23653, 56791, 4065, 13079, 59309, 57940, 59317, 17968, 28037, 27233, 53242, 30901, 10758, 57188, 9100, 51760, 16566, 20555, 50514, 35271, 59680, 24646, 14768, 13335, 30246, 39364, 51795, 5031, 38107, 32158, 443, 10384, 6774, 47929, 15499, 50368, 51827, 54022, 18908, 2157, 9827, 14658, 16901, 40891, 5884, 51302, 10387, 10960, 16761, 26793, 55085, 35673, 35137, 13497, 28211, 60579, 60497, 47403, 9106, 59526, 10327, 8063, 41945, 5754, 57621, 26709, 22739, 25547, 24703, 20746, 3895, 44111, 51320, 42212, 59781, 29064, 44610, 16431, 39515, 18156, 14210, 27507, 47206, 41530, 44123, 29499, 47242, 50363, 3339, 57490, 36566, 48636, 49784, 10942, 64447, 26791, 52829, 53204, 55163, 32261, 32157, 58261, 41129, 60614, 30034, 55489, 55576, 25052, 4263, 32514, 1419, 22605, 56589, 48192, 44655, 61295, 8855, 42987, 26448, 33214, 46651, 56194, 28472, 12965]
    leak1=[int(j) for j in "".join([bin(i)[2:].zfill(16) for i in leak[:19968//16]])]
    leak1 = matrix(GF(2), leak1)
    # 恢复state
    state = recoverState(T,leak1)
    print("state恢复完成")
    # 两种可能
    guess1, guess2 = backfirst(state)
    print(guess1, guess2)
    state[0] = guess1
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("first")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(16) for i in range(1250)]
        if now == leak:
            print("true")
            print(prng.getrandbits(64))
            return
    state[0] = guess2
    s = state
    prng.setstate((3, tuple(s + [0]), None))
    if True:
        print("second")
        prng.setstate((3, tuple(s + [0]), None))
        now =  [prng.getrandbits(16) for i in range(1250)]
        if now == leak:
            print("true")
            print(prng.getrandbits(64))
            return
main()

*CTF2022——ezRSA

from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag

p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)

print(hex(n))
#0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

print(hex(c))
#0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

考点是高位攻击，不过没那么明显

高124位

因为q=next_prime(p^((1<<900)-1)^getrandbits(300))，异或并不影响高124位，所以$p$和$q$的高124位一样

思路1

第一种方法是把$n$的前248位进行开根号得到$p,q$的高位

1
2
3

import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
x = int(gmpy2.iroot(n>>(2048-248),2)[0])

思路2

第二种方法是解方程

先是令$p = p_{h} + p_l$，$q = q_h+q_l$，$p_h = q_h = x$

于是$n = pq = 2^{1800}x^2+2^{900}x×(2^{900}-1+c) + p_lq_l\longrightarrow n = 2^{1800}x^2+2^{1800}x + t$

$t$相对来说比较小，可以忽略，解$n = 2^{1800}x^2 + 2^{1800}x$就可以得到高位

#sage
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

var('x')

f = x^2 + x - n//2^1800					
print(solve([f],[x]))
# x = 20226195070633070235386534147535171929

中间600位

思路1

对于中间300~900共600位，是不受后面一个异或影响的，p和q每位都是相反的

于是$p+q \approx 2(x<<900) + \color{red}2^{900}-2^{300}$

根据费马分解$n = \frac{(p+q)^2}{4}-\frac{(p-q)^2}{4}$

所以有$\because p-q = \sqrt{4n - (p+q)^2}$，

$\therefore p = \frac{(p+q)+(p-q)}{2} = \frac{2(x<<900)+2^{900}-2^{300}+\sqrt{4n-(p+q)^2}}{2}$

思路2

已知p,q的300~900位是相反的，将这一段设为极端情况——p全为1，q全为0。

根据基本不等式，p、q的差值越大，积就越大

当$pq<n$时，表示这个位置的数正确

import gmpy2
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
x = int(gmpy2.iroot(n>>(2048-248),2)[0])

p = x<<900 | (2**900 - 1)		#低900位全是1
q = x<<900						#低900位全是0

for i in range(899, 300, -1):
    cur = 1<<i
    # 下面的操作是把p的1变成0,q的0变成1
    # 如果改变后的pq小于n，说明是对的
    if (p^cur) * (q^cur) < n:
        p ^= cur
        q ^= cur

低位

最后就是用copper

疑惑点就是这里，两种思路求出这个近似的p之后，不是只差低300位不知道了吗？

为什么small_roots(X)的X上限不是$2^{300}$

最后我觉得的可能应该small_roots()的应用前提是已知576位，然后差了(1024-576 = 448)位，所以把上限定在了

$2^{450}$

三胞胎素数

题目来源[TSGCTF 2021]Beginner’s Crypto 2021

from secret import e
from Crypto.Util.number import getStrongPrime, isPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q
phi = (p - 1) * (q - 1)

with open('flag.txt', 'rb') as f:
    flag = int.from_bytes(f.read(), 'big')

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)

print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
"""
p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

注意到

1
2
3

assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))

满足这样条件的$e$只有$e=3$

一些定义：

孪生素数

指差等于2的两个素数。

三胞胎素数

指三个连续素数，使得其中最大的一个减去最小一个的差不超过6。

事实上，除了最小的两组三胞胎素数：$(2, 3, 5)$ 和 $(3, 5, 7)$，其它的三胞胎素数都是相差达到6的三元数组。除了以上两个特例以外，三胞胎素数分为两类：

A类三胞胎素数，构成为$p$，$p+2$，$p+6$，相差2的两个孪生素数在前面，例如：$(5，7，11)$；$(11，13，17)$； $(17，19，23)$；等等。

B类三胞胎素数，构成为$p$，$p+4$，$p+6$，相差2的两个孪生素数在后面，例如：(7，11，13)；(13，17，19)；(37，41，43)；等等。

当素数p 大于3时，可以证明形同$p$，$p+2$，$p+4$的数组不可能是三胞胎素数。事实上，这三个数对3的模两两不同，所以必然有一个能被3整除。然而这三个数都比3要大，因此一定有一个是3的倍数，从而这个数不是素数。

详见：三胞胎素数 - 维基教科书，自由的教学读本 (wikibooks.org)

题解

知道$e=3$之后就已知$e_1,e_2,e_3$，然后共模攻击

from Crypto.Util.number import *
import gmpy2
import hashlib

p = 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
q = 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837

N = p * q
phi = (p - 1) * (q - 1)
e = 3

e1 = pow(e, 0x10001, phi)
e2 = pow(e + 2, 0x10001, phi)
e3 = pow(e + 4, 0x10001, phi)

ee = [e1,e2,e3]
cc = [c1,c2,c3]
for i in range(len(ee)):
    for j in range(len(ee)):
        if i != j:
            s,x,y = gmpy2.gcdext(ee[i],ee[j])
            m = pow(cc[i],x,N) * pow(cc[j],y,N) % N
            print(long_to_bytes(m))

以下是有关论文的题目

N = ma^2 + nb^2 = mc^2 + nd^2

论文：A Note on Euler’s Factoring Problem on JSTOR

另外一个链接：[elementary number theory - A generalization of Euler Factorization with $N = m a^2 + n b^2 = m c^2 + n d^2$ - Mathematics Stack Exchange](https://math.stackexchange.com/questions/4712807/a-generalization-of-euler-factorization-with-n-m-a2-n-b2-m-c2-n-d2#:~:text=John Brillhart discusses a generalization of this method,%3D ma2 %2B nb2 %3D mc2 %2B nd2%2C)

题目来源 NSSCTF#Round11——[ez_fac]

from Crypto.Util.number import *
import random
from secret import flag,a0,a1,b0,b1

p = getPrime(512)
q = getPrime(512)
e = getPrime(128)
n = p*q
assert pow(a0,2) + e * pow(b0,2) == n
assert pow(a1,2) + e * pow(b1,2) == n
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c=",c)
print("n=",n)
print("a0=",a0)
print("a1=",a1)
print("b0=",b0)
print("b1=",b1)

论文大体内容就是：

如果$N = ma^2 + nb^2$，且$N=mc^2+nd^2$

$N$即可分解为$N= (N,ad-bc)×\frac{n}{(N,ad-bc)}$，括号就是最大公因数

所以$p = gcd(N,ad-bc)$

本题还需要推导一下e

exp:

from Crypto.Util.number import *
import gmpy2

c= 34007465638566836660852768374211870538357285529060206826620688555044780516477877596651414637089490522614456532732711803500304737160162560168303462221485961593760966240770414498297915175227814336224871400766371471776600674705757656616409870237891336752248110367865552469248343708419900511716030176178698949179
n= 70043427687738872803871163276488213173780425282753969243938124727004843810522473265066937344440899712569316720945145873584064860810161865485251816597432836666987134938760506657782143983431621481190009008491725207321741725979791393566155990005404328775785526238494554357279069151540867533082875900530405903003
a0= 8369195163678456889416121467476480674288621867182572824570660596055739410903686466334448920102666056798356927389728982948229326705483052970212882852055482
a1= 8369195163678456889416121462308686152524805984209312455308229689034789710117101859597220211456125364647704791637845189120538925088375209397006380815921158
b0= 25500181489306553053743739056022091355379036380919737553326529889338409847082228856006303427136881468093863020843230477979
b1= 31448594528370020763962343185054872105044827103889010592635556324009793301024988530934510929565983517651356856506719032859

tmp = a0*b1 - a1*b0
e = (n - pow(a0,2)) // pow(b0,2)

p = gmpy2.gcd(tmp,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(m))

n = p^r×q

题目来源[D^3CTF 2022] ——d3factor

论文：399.pdf (iacr.org)

from Crypto.Util.number import bytes_to_long, getPrime
from secret import msg
from sympy import nextprime
from gmpy2 import invert
from hashlib import md5

flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
p = getPrime(256)
q = getPrime(256)
assert p > q
n = p * q
e = 0x10001
m = bytes_to_long(msg)
c = pow(m, e, n)

N = pow(p, 7) * q
phi = pow(p, 6) * (p - 1) * (q - 1)
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))
e1 = invert(d1, phi)
e2 = invert(d2, phi)

print(f'c = {c}')
print(f'N = {N}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
'''
c = 
N = 
e1 = 
e2 = 
'''

论文内容及证明过程

论文大致内容就是对于$N = p^rq$，当两个解密密钥$d_1$,$d_2$差值不超过$N^{\frac{r(r-1)}{(r+1)^2}}$

即$|d_1-d_2| < N^{\frac{r(r-1)}{(r+1)^2}}$的时候，可以在多项式的时间内分解出$p$

其证明过程如下：

$\because N =p^rq$，$\phi(N) = p^{r-1}(p-1)(q-1)$

有
$$
\left{\begin{matrix}
e_1d_1 \equiv 1 \mod \phi(N) \quad ①\
e_2d_2 \equiv 1 \mod \phi(N) \quad ②\
\end{matrix}\right.\
$$
把①式乘$e_2$，②式乘$e_1$再相减得

$e_1e_2(d_1-d_2)-(e_2-e_1) \equiv 0 \mod \phi(N)$

根据论文，把$\phi(N)$用$p^{r-1}$替代掉

则有$e_1e_2(d_1-d_2)-(e_2-e_1) \equiv 0 \mod p^{r-1}$

$d_1-d_2$就是$e_1e_2x - (e_2-e_1) \equiv 0 \mod p^{r-1}$的根

可以用coppersmith求出$x$

然后计算$gcd(e_1e_2x - (e_2-e_1),N) = gcd(k×p^{r-1}(p-1)(q-1),p^rq) = g$

利用这个g
$$
p =
\left{\begin{matrix}
g^{\frac{1}{r-1}},\quad if\quad g = p^{r-1}\
g^{\frac{1}{r}},\quad if \quad g = p^r\
\frac{N}{g},\quad if\quad g = p^{r-1}q
\end{matrix}\right.
$$

本题解答

根据

N = pow(p, 7) * q
phi = pow(p, 6) * (p - 1) * (q - 1)
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))

可以判断出$|d_1-d_2|\approx 1000bit$，$N= 2048bbit$，所以$|d_1-d_2|<N^{\frac{r(r-1)}{(r+1)^2}} \approx 1344bit $

满足论文条件

from Crypto.Util.number import *
from hashlib import md5
import gmpy2

e = 65537
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919

a = e1 * e2
b = (e2 - e1)


R.<x> = PolynomialRing(Zmod(N))			
f = a*x - b
f = f.monic()
res =  f.small_roots(2^1000,beta = 0.4)		#根据d1-d2大概的范围确定上限

ans = int(res[0])

g = gcd(a*ans - b,N)
#print(g.nbits())
#g = 1534bit

p = gmpy2.iroot(g,6)[0]
q = N // (p^7)
n = p*q
d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,n)
msg = long_to_bytes(int(m))

flag = "d3ctf{" + md5(msg).hexdigest() + '}'
print(flag)

$\because g = 1534bit$，$\therefore p = g^{\frac{1}{6}}$

RSA与格结合，且多组n,e,c

题目来源[NUSTCTF 2022 新生赛]——lattice

论文：IJCSI-9-2-1-311-314.pdf

题目

from Crypto.Util.number import *
from random import randint
from secret import flag

flag = bytes_to_long(flag)
d = getPrime(randint(370, 390))


def enc(i):
    print()
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    phi = (p - 1) * (q - 1)
    e = inverse(d, phi)
    c = pow(flag, e, n)
    print(f'e_{i} =', e)
    print(f'n_{i} =', n)
    print(f'c_{i} =', c)


if __name__ == '__main__':
    for i in range(3):
        enc(i)

# e_0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
# n_0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
# c_0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

# e_1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
# n_1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
# c_1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

# e_2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
# n_2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
# c_2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606

令$M = \sqrt{N_{max}}$，$M$是一组$N$中最大的$N$并且开根号。这组$N$满足：$N_1<N_2<\dots<N_r <2N_1$

又$\because e_id \equiv 1 (\mod \phi(N_i))$

这里把它写成$e_id = 1+k_i\phi{N_i}$

假设$\phi(N_i)$可以写成$k_i(N_i-s_i)$的形式。其中$|s_i<3N_i^{\frac{1}{2}}|$

则$e_id = 1 + k_i(N_i-s_i)$

化简得$e_id-k_iN_i = 1-k_is_i$

所以我们有$r+1$个等式:

写成矩阵相乘的形式

因为最后的目标向量满足LLL算法，所以我们可以得到$dM$

求得$dM$之后，我们可以求得$d$

exp:

import libnum
import gmpy2

e0 = 37389635736858807810703086504264263440188928763651776502954117173983775626039037008534821321761858567723984257427640816113325770208734640385635663643682102780255726244659849205653007212192504491177021176624605722718152646889627480051142935241036578957272339153039961711802753021931124235464986935316295647379
n0 = 87704526707772151782606625126900349506318713860335977395824997219721333991491994027303721441548488339412359519408127174109547119019245873976917916080340858937125736650376514406944094998893225164676363063781400756374403299951466867573215964360920244878373810391250391475087527409213204756990192602517961590163
c0 = 78656123855003406993963573497876652287109947684890741747390020445306861422604130132525802389554149844489256622057009394678814584233565675702142297935509191018145970589418173328145004732595569847696022333024124469320873194195223535859964387627938665526123562969554622541694399263934496631337485091067073489148

e1 = 28535169211141109871379321582501492434722235009040085167442370469971731780018594508141105234950857774463438226249819106596920677559656398153362076685288045484306156454558741088396794170762527953573082734587618137075161676392362016474076363311708889307420903699720319611668580377903356783222664068961626803615
n1 = 134298877057487865189085342936485527664167450453080897084604607959501054859295769447683135156167266222961308751016451904929475702646252122360203167489936020076488657815646993920082535307414536854323149177250531362615850689341066360635074886835720438532107976530111551202845697404444502476862934946146194420313
c1 = 3208711484494445700905074340207543865325589037128163311082565190422756093807236786011349707275838139469873445326457948489588753029946395247710197747538418278782966047404435385208682596795152082296050804126524129644617710791433973098499266439604632728957505961744280687343384601998774018570047292904007768763

e2 = 27653153186459366670449283776658896188717513017934031993526241644501850206894800647711159987946276669184047769965182746812351757618147642060630769822810070480507035319320426666128599562714143342910248758055424582501972900763786232170145957578683616604737178839977216709381529813768748145393798635858691196687
n2 = 82113192811251631639012300385672674439485256963081847790431181633372052788107703751257606763043873164706839243919206719171536710944060815484051324239120708906418093409305166299531826404505861042666985630956832163750255358332156122245372899824101210233079028706971698312018388678352739819636695333269309456613
c2 = 79145689398302968140315554300835109898158799236562716569497147385375487041207363302776833573990584370222316102267792795080448018216133931915984139305260191001847394275311719986838969706049641052337337102739487620502723651258075501409442088938776353037366614208693030741599888985069155346722608948495955447606


n = [n0,n1,n2]
M = isqrt(max(n))

ge = [[M,e0,e1,e2],
    [0,-n0,0,0],
    [0,0,-n1,0],
    [0,0,0,-n2]]
Ge = Matrix(ZZ,ge)

dM = Ge.LLL()[0][0]
d = abs(dM) // M
m = pow(c0,d,n0)
print(libnum.n2s(int(m)))

cve of RSA

论文：The Return of Coppersmith’s Attack:Practical Factorization of Widely Used RSA Moduli (muni.cz)

如果p,q是以$p = k×M + 65537^a \mod M$的形式产生的，M是个光滑数

攻击脚本：jvdsn/crypto-attacks: Python implementations of cryptographic attacks and utilities. (github.com)

根据结论调参

from secret import flag
from Crypto.Util.number import *


kbits = 37
abit = 62
m = bytes_to_long(flag)
M = 962947420735983927056946215901134429196419130606213075415963491270
while True:
    k = getRandomNBitInteger(kbits)
    a = getRandomNBitInteger(abit)
    p = k * M + pow(0x10001, a, M)
    if isPrime(p):
        break
while True:
    l = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(abit)
    q = l * M + pow(0x10001, b, M)
    if isPrime(q):
        break

N = p * q
c = pow(m, 0x10001, N)
print('N =', N)
print('c =', c)
# N = 10375505512698590697230540440656541719204263636911186773264796164624307537559854575146689396086897683887657357280574643827597720286007334491967184402911331
# c = 9452671754308991307639149928469686004498992794878178108851267184995226471125632100149955622693448809888842182351036616823747409631021412523576720606919605

exp:

import logging
import os
import sys
from math import log2

from sage.all import Zmod
from sage.all import factor

path = os.path.dirname(os.path.dirname(os.path.dirname(os.path.realpath(os.path.abspath(__file__)))))
if sys.path[1] != path:
    sys.path.insert(1, path)

from shared.small_roots import howgrave_graham


def _prime_power_divisors(M):
    divisors = []
    for p, e in factor(M):
        for i in range(1, e + 1):
            divisors.append(p ** i)

    divisors.sort()
    return divisors


# Algorithm 2.
def compute_max_M_(M, ord_):
    for p in _prime_power_divisors(M):
        ordp = Zmod(p)(65537).multiplicative_order()
        if ord_ % ordp != 0:
            M //= p

    return M


# Section 2.7.2.
def _greedy_find_M_(n, M):
    ord = Zmod(M)(65537).multiplicative_order()
    while True:
        best_r = 0
        best_ord_ = ord
        best_M_ = M
        for p in _prime_power_divisors(ord):
            ord_ = ord // p
            M_ = compute_max_M_(M, ord_)
            r = (log2(ord) - log2(ord_)) / (log2(M) - log2(M_))
            if r > best_r:
                best_r = r
                best_ord_ = ord_
                best_M_ = M_

        if log2(best_M_) < log2(n) / 4:
            return M

        ord = best_ord_
        M = best_M_


def factorize(N, M, m, t, g=65537):
    """
    Recovers the prime factors from a modulus using the ROCA method.
    More information: Nemec M. et al., "The Return of Coppersmith’s Attack: Practical Factorization of Widely Used RSA Moduli"
    :param N: the modulus
    :param M: the primorial used to generate the primes
    :param m: the m parameter for Coppersmith's method
    :param t: the t parameter for Coppersmith's method
    :param g: the generator value (default: 65537)
    :return: a tuple containing the prime factors
    """
    logging.info("Generating M'...")
    M_ = _greedy_find_M_(N, M)
    zmodm_ = Zmod(M_)
    g = zmodm_(g)
    c_ = zmodm_(N).log(g)
    ord_ = g.multiplicative_order()

    x = Zmod(N)["x"].gen()
    X = int(2 * N ** 0.5 // M_)
    logging.info("Starting exhaustive a' search...")
    for a_ in range(c_ // 2, (c_ + ord_) // 2 + 1):
        f = M_ * x + int(g ** a_)
        for k_, in howgrave_graham.modular_univariate(f, N, m, t, X):
            p = int(f(k_))
            if N % p == 0:
                return p, N // p
      
N=10375505512698590697230540440656541719204263636911186773264796164624307537559854575146689396086897683887657357280574643827597720286007334491967184402911331
M=962947420735983927056946215901134429196419130606213075415963491270
m = 5
t = 6
p,q = factorize(N,M,m,t)
print("p=",p)
print("q=",q)

这个脚本我是在sagemath跑的

得到p,q后有手就行

from Crypto.Util.number import *
import gmpy2

p=85179386137518452231354185509698113331528483782580002217930594759662020757433
q=121807704694511224555991770528701515984374557330058194205583818929517699002107
e = 65537
c = 9452671754308991307639149928469686004498992794878178108851267184995226471125632100149955622693448809888842182351036616823747409631021412523576720606919605

d = gmpy2.invert(e,(p-1)*(q-1))
m = pow(c,d,p*q)
print(long_to_bytes(m))

有限域上的不可约多项式RSA体制

TCTF2019——babyrsa

#!/usr/bin/env sage
# coding=utf-8

from pubkey import P, n, e
from secret import flag
from os import urandom

R.<a> = GF(2^2049)

def encrypt(m):
    global n
    assert len(m) <= 256
    m_int = Integer(m.encode('hex'), 16)
    m_poly = P(R.fetch_int(m_int))
    c_poly = pow(m_poly, e, n)
    c_int = R(c_poly).integer_representation()
    c = format(c_int, '0256x').decode('hex')
    return c

if __name__ == '__main__':
    ptext = flag + os.urandom(256-len(flag))
    ctext = encrypt(ptext)
    with open('flag.enc', 'wb') as f:
        f.write(ctext)

from sage.all import GF, PolynomialRing

P=PolynomialRing(GF(2),'x')
e = 31337
n = P(省略)

R.fetch_int(m_int)：把整型数据转化成环R上的元素

R(c_poly).integer_representation()：把环R上的元素变成整型数据

exp:

from Crypto.Util.number import *
import gmpy2

R.<a> = GF(2^2049)
P = PolynomialRing(GF(2),'x')
e = 31337

n = P('x^2048 + x^2046 + x^2043 + x^2040 + x^2036 + x^2035 + x^2034 + x^2033 + x^2031 + x^2029 + x^2025 + x^2024 + x^2022 + x^2019 + x^2018 + x^2017 + x^2012 + x^2007 + x^2006 + x^2004 + x^2000 + x^1999 + x^1998 + x^1997 + x^1993 + x^1992 + x^1991 + x^1986 + x^1982 + x^1981 + x^1979 + x^1978 + x^1977 + x^1975 + x^1970 + x^1964 + x^1963 + x^1962 + x^1961 + x^1960 + x^1959 + x^1958 + x^1955 + x^1954 + x^1952 + x^1951 + x^1949 + x^1947 + x^1942 + x^1939 + x^1938 + x^1936 + x^1934 + x^1933 + x^1932 + x^1930 + x^1928 + x^1927 + x^1923 + x^1922 + x^1919 + x^1918 + x^1915 + x^1914 + x^1913 + x^1912 + x^1911 + x^1910 + x^1908 + x^1903 + x^1902 + x^1900 + x^1899 + x^1897 + x^1893 + x^1891 + x^1890 + x^1886 + x^1881 + x^1880 + x^1879 + x^1878 + x^1875 + x^1874 + x^1873 + x^1872 + x^1871 + x^1870 + x^1869 + x^1865 + x^1863 + x^1862 + x^1860 + x^1856 + x^1855 + x^1853 + x^1852 + x^1845 + x^1841 + x^1839 + x^1837 + x^1836 + x^1835 + x^1833 + x^1832 + x^1829 + x^1828 + x^1827 + x^1826 + x^1824 + x^1823 + x^1822 + x^1821 + x^1820 + x^1819 + x^1818 + x^1817 + x^1813 + x^1812 + x^1810 + x^1809 + x^1808 + x^1807 + x^1803 + x^1799 + x^1797 + x^1796 + x^1794 + x^1792 + x^1790 + x^1786 + x^1783 + x^1782 + x^1779 + x^1778 + x^1776 + x^1775 + x^1774 + x^1772 + x^1767 + x^1766 + x^1765 + x^1764 + x^1763 + x^1762 + x^1759 + x^1757 + x^1756 + x^1754 + x^1753 + x^1752 + x^1750 + x^1749 + x^1741 + x^1734 + x^1730 + x^1729 + x^1726 + x^1725 + x^1723 + x^1722 + x^1721 + x^1716 + x^1714 + x^1713 + x^1712 + x^1710 + x^1709 + x^1706 + x^1705 + x^1703 + x^1702 + x^1700 + x^1698 + x^1693 + x^1692 + x^1691 + x^1690 + x^1683 + x^1682 + x^1681 + x^1680 + x^1679 + x^1677 + x^1672 + x^1670 + x^1669 + x^1666 + x^1663 + x^1662 + x^1661 + x^1659 + x^1655 + x^1653 + x^1651 + x^1649 + x^1648 + x^1647 + x^1646 + x^1644 + x^1643 + x^1642 + x^1640 + x^1639 + x^1638 + x^1634 + x^1633 + x^1628 + x^1620 + x^1619 + x^1618 + x^1616 + x^1614 + x^1611 + x^1610 + x^1608 + x^1605 + x^1604 + x^1603 + x^1599 + x^1597 + x^1595 + x^1594 + x^1590 + x^1588 + x^1587 + x^1585 + x^1583 + x^1580 + x^1579 + x^1577 + x^1574 + x^1573 + x^1572 + x^1568 + x^1566 + x^1565 + x^1563 + x^1562 + x^1560 + x^1555 + x^1554 + x^1552 + x^1550 + x^1549 + x^1548 + x^1545 + x^1544 + x^1542 + x^1540 + x^1538 + x^1537 + x^1536 + x^1535 + x^1534 + x^1533 + x^1532 + x^1531 + x^1528 + x^1526 + x^1525 + x^1523 + x^1522 + x^1521 + x^1519 + x^1517 + x^1515 + x^1510 + x^1509 + x^1506 + x^1504 + x^1502 + x^1499 + x^1498 + x^1497 + x^1488 + x^1483 + x^1480 + x^1477 + x^1472 + x^1471 + x^1469 + x^1468 + x^1467 + x^1466 + x^1464 + x^1462 + x^1457 + x^1456 + x^1455 + x^1454 + x^1453 + x^1452 + x^1448 + x^1446 + x^1444 + x^1443 + x^1442 + x^1441 + x^1440 + x^1436 + x^1435 + x^1431 + x^1428 + x^1425 + x^1424 + x^1422 + x^1420 + x^1415 + x^1414 + x^1411 + x^1410 + x^1408 + x^1406 + x^1405 + x^1403 + x^1402 + x^1399 + x^1397 + x^1396 + x^1395 + x^1394 + x^1393 + x^1391 + x^1388 + x^1385 + x^1377 + x^1376 + x^1372 + x^1371 + x^1370 + x^1369 + x^1367 + x^1363 + x^1361 + x^1357 + x^1355 + x^1354 + x^1349 + x^1343 + x^1339 + x^1338 + x^1337 + x^1336 + x^1335 + x^1332 + x^1329 + x^1327 + x^1326 + x^1324 + x^1321 + x^1315 + x^1314 + x^1312 + x^1310 + x^1309 + x^1305 + x^1304 + x^1303 + x^1302 + x^1299 + x^1298 + x^1296 + x^1295 + x^1293 + x^1291 + x^1290 + x^1289 + x^1284 + x^1283 + x^1282 + x^1281 + x^1280 + x^1278 + x^1277 + x^1276 + x^1275 + x^1272 + x^1270 + x^1269 + x^1268 + x^1267 + x^1259 + x^1257 + x^1254 + x^1252 + x^1251 + x^1249 + x^1247 + x^1246 + x^1244 + x^1240 + x^1238 + x^1233 + x^1232 + x^1229 + x^1222 + x^1219 + x^1217 + x^1211 + x^1209 + x^1208 + x^1205 + x^1204 + x^1203 + x^1202 + x^1200 + x^1197 + x^1196 + x^1195 + x^1193 + x^1192 + x^1189 + x^1187 + x^1186 + x^1185 + x^1184 + x^1183 + x^1182 + x^1181 + x^1177 + x^1176 + x^1173 + x^1170 + x^1167 + x^1166 + x^1162 + x^1161 + x^1160 + x^1159 + x^1158 + x^1156 + x^1155 + x^1154 + x^1153 + x^1151 + x^1146 + x^1143 + x^1141 + x^1139 + x^1138 + x^1137 + x^1135 + x^1131 + x^1129 + x^1128 + x^1125 + x^1124 + x^1122 + x^1116 + x^1115 + x^1114 + x^1112 + x^1111 + x^1107 + x^1106 + x^1105 + x^1104 + x^1103 + x^1102 + x^1098 + x^1097 + x^1095 + x^1094 + x^1092 + x^1088 + x^1087 + x^1085 + x^1077 + x^1076 + x^1075 + x^1072 + x^1069 + x^1068 + x^1061 + x^1060 + x^1059 + x^1057 + x^1055 + x^1054 + x^1053 + x^1050 + x^1047 + x^1046 + x^1044 + x^1043 + x^1042 + x^1036 + x^1029 + x^1025 + x^1024 + x^1023 + x^1022 + x^1019 + x^1016 + x^1013 + x^1012 + x^1010 + x^1008 + x^1007 + x^1006 + x^1004 + x^1000 + x^996 + x^995 + x^993 + x^992 + x^989 + x^985 + x^983 + x^978 + x^977 + x^975 + x^972 + x^971 + x^970 + x^969 + x^967 + x^963 + x^957 + x^956 + x^952 + x^950 + x^948 + x^945 + x^942 + x^941 + x^940 + x^938 + x^937 + x^936 + x^935 + x^932 + x^931 + x^930 + x^928 + x^927 + x^926 + x^923 + x^921 + x^918 + x^916 + x^914 + x^913 + x^909 + x^906 + x^905 + x^904 + x^902 + x^897 + x^895 + x^892 + x^889 + x^888 + x^887 + x^886 + x^885 + x^884 + x^882 + x^881 + x^879 + x^876 + x^870 + x^868 + x^867 + x^865 + x^862 + x^861 + x^859 + x^858 + x^856 + x^854 + x^848 + x^847 + x^846 + x^843 + x^839 + x^837 + x^836 + x^832 + x^831 + x^830 + x^829 + x^826 + x^823 + x^821 + x^820 + x^817 + x^815 + x^812 + x^809 + x^808 + x^805 + x^803 + x^802 + x^800 + x^799 + x^797 + x^795 + x^793 + x^792 + x^788 + x^786 + x^784 + x^780 + x^775 + x^774 + x^770 + x^768 + x^766 + x^764 + x^761 + x^760 + x^753 + x^752 + x^751 + x^750 + x^747 + x^744 + x^742 + x^741 + x^737 + x^734 + x^732 + x^728 + x^727 + x^724 + x^722 + x^721 + x^719 + x^717 + x^715 + x^714 + x^713 + x^710 + x^709 + x^705 + x^703 + x^701 + x^698 + x^697 + x^695 + x^690 + x^687 + x^685 + x^684 + x^682 + x^681 + x^680 + x^677 + x^676 + x^674 + x^673 + x^672 + x^671 + x^670 + x^669 + x^665 + x^663 + x^659 + x^652 + x^651 + x^650 + x^649 + x^648 + x^647 + x^646 + x^645 + x^642 + x^640 + x^638 + x^632 + x^631 + x^630 + x^629 + x^627 + x^626 + x^623 + x^622 + x^621 + x^620 + x^616 + x^615 + x^610 + x^605 + x^602 + x^601 + x^600 + x^599 + x^598 + x^596 + x^594 + x^593 + x^591 + x^583 + x^581 + x^579 + x^578 + x^577 + x^576 + x^575 + x^573 + x^572 + x^571 + x^570 + x^569 + x^565 + x^563 + x^562 + x^561 + x^559 + x^557 + x^555 + x^552 + x^551 + x^546 + x^544 + x^542 + x^541 + x^540 + x^539 + x^538 + x^537 + x^535 + x^533 + x^530 + x^527 + x^523 + x^522 + x^520 + x^519 + x^515 + x^513 + x^511 + x^509 + x^507 + x^505 + x^504 + x^503 + x^499 + x^497 + x^496 + x^495 + x^493 + x^492 + x^488 + x^486 + x^481 + x^480 + x^479 + x^478 + x^477 + x^472 + x^470 + x^468 + x^467 + x^464 + x^463 + x^460 + x^459 + x^455 + x^454 + x^453 + x^446 + x^445 + x^444 + x^443 + x^440 + x^438 + x^437 + x^432 + x^431 + x^428 + x^427 + x^426 + x^420 + x^419 + x^416 + x^415 + x^414 + x^413 + x^412 + x^411 + x^405 + x^404 + x^401 + x^396 + x^393 + x^392 + x^391 + x^388 + x^387 + x^383 + x^381 + x^380 + x^377 + x^376 + x^369 + x^364 + x^362 + x^358 + x^357 + x^356 + x^355 + x^353 + x^351 + x^349 + x^340 + x^339 + x^338 + x^337 + x^336 + x^335 + x^334 + x^332 + x^330 + x^328 + x^327 + x^326 + x^324 + x^320 + x^318 + x^316 + x^315 + x^309 + x^302 + x^298 + x^292 + x^291 + x^290 + x^289 + x^287 + x^286 + x^285 + x^284 + x^281 + x^279 + x^278 + x^276 + x^274 + x^273 + x^272 + x^271 + x^267 + x^266 + x^264 + x^263 + x^262 + x^260 + x^259 + x^256 + x^254 + x^253 + x^252 + x^251 + x^249 + x^248 + x^247 + x^245 + x^244 + x^241 + x^239 + x^235 + x^234 + x^233 + x^232 + x^231 + x^230 + x^226 + x^224 + x^221 + x^219 + x^218 + x^216 + x^215 + x^214 + x^209 + x^207 + x^206 + x^202 + x^201 + x^198 + x^197 + x^194 + x^193 + x^192 + x^191 + x^189 + x^188 + x^183 + x^182 + x^181 + x^180 + x^179 + x^178 + x^177 + x^175 + x^172 + x^169 + x^168 + x^166 + x^165 + x^164 + x^163 + x^158 + x^157 + x^153 + x^152 + x^149 + x^147 + x^146 + x^144 + x^140 + x^139 + x^136 + x^128 + x^127 + x^126 + x^124 + x^123 + x^122 + x^121 + x^116 + x^115 + x^113 + x^112 + x^109 + x^108 + x^107 + x^106 + x^104 + x^103 + x^102 + x^101 + x^100 + x^99 + x^97 + x^95 + x^94 + x^93 + x^92 + x^87 + x^84 + x^83 + x^82 + x^80 + x^79 + x^78 + x^76 + x^73 + x^70 + x^69 + x^68 + x^67 + x^66 + x^65 + x^63 + x^60 + x^59 + x^57 + x^55 + x^52 + x^51 + x^47 + x^46 + x^45 + x^43 + x^42 + x^40 + x^36 + x^35 + x^30 + x^29 + x^28 + x^27 + x^23 + x^20 + x^17 + x^14 + x^9 + x^7 + x^3 + 1')
c = 23931938409134006846469410550487073743925192650755116938225541794524723083910240603620279453298714584321800170326063144616472531553643627071552202613402950579120189960424183462876292590831564884347025119938858471788053191321980663696621632084753893732784657023312407591768406322125753947265987815937165961039424015628319982913336402297718720925447102042668906173729998301139577468193468132305331072754842771657432484688590927575895743853584931297836925498250475231655832566787366689988158399203844420168837827423836936015638932385609040452870954522482255864355639427304567768665723098741671323173831781775755570779256
c_poly = P(R.fetch_int(c))

p,q = factor(n)[0][0],factor(n)[1][0]
phi = (2^p.degree()-1)*(2^q.degree()-1)
d = gmpy2.invert(e,phi)

m_poly = pow(c_poly, d, n)
m_int = R(m_poly).integer_representation()
print(long_to_bytes(m_int))

watevrCTF 2019——Swedish RSA

flag = bytearray(raw_input())
flag = list(flag)
length = len(flag)
bits = 16

## Prime for Finite Field.
p = random_prime(2^bits-1, False, 2^(bits-1))

file_out = open("downloads/polynomial_rsa.txt", "w")
file_out.write("Prime: " + str(p) + "\n")

## Univariate Polynomial Ring in y over Finite Field of size p
R.<y> = PolynomialRing(GF(p))

## Analogous to the primes in Z
def gen_irreducable_poly(deg):
    while True:
        out = R.random_element(degree=deg)
        if out.is_irreducible():
            return out


## Polynomial "primes"
P = gen_irreducable_poly(ZZ.random_element(length, 2*length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2*length))

## Public exponent key
e = 65537

## Modulus
N = P*Q
file_out.write("Modulus: " + str(N) + "\n")

## Univariate Quotient Polynomial Ring in x over Finite Field of size 659 with modulus N(x)
S.<x> = R.quotient(N)

## Encrypt
m = S(flag)
c = m^e

file_out.write("Ciphertext: " + str(c))
file_out.close()

out = R.random_element(degree=deg)，作用是从一个给定的环或域 R 中生成一个随机元素，并限定该随机元素的次数（degree）。就是会生成一个环R中次数不超过deg的多项式

is_irreducible()：作用是判断一个多项式是不是不可约的，如果是不可约的就返回True

R.quotient ，用于计算环或域 R 的商环或商域

先把N分解了，得到一个65次的多项式和一个112次的多项式。

然后重点是计算$\phi(N)=\phi(p)×\phi(q)$

1
2

对于整数n来讲，欧拉函数phi(n)表示所有小于或等于n的正整数中与n互质的数的数目。
对于多项式P(y)来讲，欧拉函数phi(P(y))表示所有不高于P(y)幂级的环内所有多项式中，与P(y)无除1以外的公因式的其他多项式的个数。

这篇论文指出了欧拉函数的计算方法

本题中，$p$，$q$都是环R上的多项式，而且$p$，$q$都不可约

$\therefore \phi(N) = (p^{65}-1)×(p^{112}-1)$

然后就是常规RSA解法(我表示很震惊)，而且最后 flag的提取也很奇怪

exp:

#sage
from Crypto.Util.number import *
import gmpy2

e = 65537
P = 43753
R.<y> = PolynomialRing(GF(P))
N = 34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
S.<x> = R.quotient(N)
C = 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659

p,q = factor(N)
p,q = p[0],q[0]

phi = (P^p.degree() - 1)*(P^q.degree()-1)
d = gmpy2.invert(e,phi)
m = C^d
print(m)
print(m.list())
flag = ''.join([chr(c) for c in m.list()])
print(flag)

m.list()是把m这个多项式中每一项的系数按照次幂上升的顺序进行排列

2021强网拟态——OnlyRSA

#!/usr/bin/env python
from Crypto.Util.number import *
from secret import flag

n = 
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(c)
# c =

exp:

n = 
e = 65537
c = 

from Crypto.Util.number import *

digits = n.digits(11)
f = 0
for i, each in enumerate(digits):
    f += each * x ^ i

factors = f.factor_list()

p = factors[0][0]
q = factors[1][0]

p = p(x=11)
q = q(x=11)

d = inverse_mod(65537,(p-1))
m = pow(c,d,p)
print(long_to_bytes(int(m)))

coppersmith

恢复OAEP私钥

题目来源：[蓝帽杯 2022 初赛]corrupted_key

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from secret import flag

key = RSA.generate(1024)
open("flag.enc",'wb').write(PKCS1_OAEP.new(key.publickey()).encrypt(flag))
open('priv.pem','wb').write(key.exportKey('PEM'))

priv.pem:

私钥文件缺失信息

上网找pem文件的解析

PKCS#1的私钥文件包含以下信息：

RSAPrivateKey ::= SEQUENCE {
 version Version,
 modulus INTEGER, -- n
 publicExponent INTEGER, -- e
 privateExponent INTEGER, -- d
 prime1 INTEGER, -- p
 prime2 INTEGER, -- q
 exponent1 INTEGER, -- d mod (p-1)
 exponent2 INTEGER, -- d mod (q-1)
 coefficient INTEGER -- (inverse of q) mod p 
}

标签头：

3082025C# 标签头
020100 # 整型
028181 # 整型 长度 为 129 字节 (0x81)，内容：模数 n (modulus)
0203 # 整型 长度 为 3 字节(0x03)，内容：e (公钥指数)
028180 # 整型 长度 为 128 字节(0x80)，内容：d (私钥指数)
0241 # 整型 长度 为 65 字节(0x41)，内容：p (素数)
0241 # 整型 长度 为 65 字节(0x41)，内容：q (素数)
0240 # 整型 长度 为 64 字节(0x40)，内容：d mod(p-1)
0240 # 整型 长度 为 64 字节(0x40)，内容：d mod(q-1)
0241 # 整型 长度 为 65 字节(0x41)，内容：(1/q)mod p <即 invert(q,p)>

把priv的内容base64解码，再转16进制，并且根据标签头提取信息：

n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
dq = 0xc90bcecf1cbab3358585e8a041d1b1
inv = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598

即已知$dq \equiv d \mod (q-1)$，$q^{-1} \mod p$，需要注意的是这里的dq不是完整的dq，而是低120位

$\because dq \equiv d \mod (q-1)$，$dq = d+k(q-1)$

$\therefore dq × e = ed + kd(q-1)$即$dq ×e = k_1(p-1)(q-1) + 1 + kd(q-1)$，可以写成$dq ×e = k(q-1) + 1$

$\therefore dq ×e + k-1 = kq$

两边同模$2^{120}$得$dq×e+k-1 \equiv kq \mod 2^{120}$

$\therefore q \equiv k^{-1}(dq×e +k-1) \mod 2^{120}$

$\because dq < q-1 ,\therefore e > k$

于是我们便能求出$q$的低120位的可能取值

$\because inv ×q \equiv 1 \mod p $，即$inv×q -1 = kp$，两边同乘q得$inv×q×q -q = kn$

即$inv × q×q -q \equiv 0 \mod (n)$

于是可以用coppersmith恢复求得q

区别于$inv×q-1 \equiv 0 \mod p$

exp:

#sage
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from gmpy2 import *
from tqdm import *

n = 0xd7152506aa9cec05e5335d6b46f5491407c3199fd51091f1f6030d3762b9e03f49c9dcdc075054e0cc148b974b41854bd93b4ee16a2a876ee62005e80ef806b7aa3b64b1bf9b1fa773e353d0cdb9ff9783ddd5f5e67499ad10f361e938d00b82a6a4c42a0535c5e76721798e86b45cd4b8d03b0d7e75c2be8766a1e843bdc641
e = 0x10001
inv = 0xe3016cb3609c1d643c167439c3b938b881f4237f24860d3b1cb85a626d5ccd4726964e0f8270d6c4df9ebfebcc538e4ee5e1a7b7368ede51ec6ae917f78eb598
d_low = 0xc90bcecf1cbab3358585e8a041d1b1
q_low = []
c = open("flag.enc",'rb').read()

for i in trange(1,e):
    try:
        q0 = invert(i, 2 ** 120) * (e * d_low + i - 1) % 2 ^ 120
        q_low.append(q0)
    except:
        continue

PR.<x> = PolynomialRing(Zmod(n))

for i in trange(len(q_low)-1,-1,-1):
    f = inv * (2^120*x + int(q_low[i]))^2 - (2^120*x + int(q_low[i]))
    f = f.monic()
    root = f.small_roots(X = 2^(512-120))
    if root:
        q = 2^120 * int(root[0]) + int(q_low[i])
        p = n // q
        if p * q == n:
            d = gmpy2.invert(e, (p - 1) * (q - 1))
            print("p = ",p)
            print("q = ",q)
            print("d = ",d)
            key = RSA.construct((int(n),int(e),int(d),int(p),int(q)))
            newkey = PKCS1_OAEP.new(key)
            flag = newkey.decrypt(c)
            print(flag)
            break

参考：(PKCS1) RSA 公私钥 pem 文件解析 - 知乎 (zhihu.com)

RSA密钥格式解析 - 简书 (jianshu.com)

comedy（先搁着）

题目

import gmpy2, libnum
from secret import flag1, flag2

m = libnum.s2n(flag1)
assert m.bit_length() < 200
B = gmpy2.next_prime(libnum.s2n(flag2))
A = (2022 - 2023 * m) % B
leak = pow(2, 2023, B)
print(A)
print(leak)
# 493275281479560936332761096886786925792234184811353209227551802099268192839677496844153534128991899414803550843408607188612593757622064753867565869035222715177143938385039508273050267347710495512806264863554858016145161165422812554800693811328453743229819656381224407015421235005940088439590887928051969351426291843586132741521121351667152673680122929827805479163871436776753859965413192837591532468372
# 238829196127128263156194898141748280130190920343265228257398802867203846004703877952990524473329125233083096275276064071930416561616135910190674099345267027039386328203653489152769309498199556401574021633071022874689081585677578010276529507102304828451681000682208089162940529052283763507244593173690786957816545746540436261888398732172965945762569416702401859253725696471593023885944262561159982327952

高位攻击

from secrets import flag
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print('n =', n)
print('c =', c)
print('p0 =', ((p>>128)<<128))
# n = 12722276084782012506939748218137061976694333623308770803193278921311358642857520720238223717188895787376761058057320570031791633540549052360890626849683959794619430207976509336964838302913532815872846936103400538093765972176693960613553754981804951861018999147210521057815783304998144581807982126753283124281516688846477783545704858051397854514128591265938874177108889498151756070102637171159497913559176230984485047937009449456335164657258487948113487961895079102836099947427765851897399603733885367848305266219390271858890481731238036781050541110612526113637880146841891893392904381138771618976655066294938275191591
# c = 7016802271682704586027412586496213357494728781654536670879262263911645812024904159932204545849316301445405237966933240237035426118442003499546014556123485534516682277683392394418823209992176414301314576069643211825678886511259850322068086838470004809816539278374905405029448429356654864943156018053547494263664714952593505357117355251742922245508277007069593675629222770814317602710615647062020095140444497647478051326857816298790397174877223117345612840890905447851689835046066164443064435495141117872095457539285213399905708851752673701650986197704683439495235659865937503527178246189185724246027890778434827868479
# p0 = 121612618057439377491893234820394610861816815559052233952438700644930219565204914707604533201740057532331014637555250302342831261394993528125583478630623993361944114671033382653887624385660705353904988324932092635052885387222723368916634052933090217574600695084708857274271614116870074627080278200070403260416

p高位泄露，未知位是128bit

exp:


import gmpy2
from Crypto.Util.number import *

n = 12722276084782012506939748218137061976694333623308770803193278921311358642857520720238223717188895787376761058057320570031791633540549052360890626849683959794619430207976509336964838302913532815872846936103400538093765972176693960613553754981804951861018999147210521057815783304998144581807982126753283124281516688846477783545704858051397854514128591265938874177108889498151756070102637171159497913559176230984485047937009449456335164657258487948113487961895079102836099947427765851897399603733885367848305266219390271858890481731238036781050541110612526113637880146841891893392904381138771618976655066294938275191591
c = 7016802271682704586027412586496213357494728781654536670879262263911645812024904159932204545849316301445405237966933240237035426118442003499546014556123485534516682277683392394418823209992176414301314576069643211825678886511259850322068086838470004809816539278374905405029448429356654864943156018053547494263664714952593505357117355251742922245508277007069593675629222770814317602710615647062020095140444497647478051326857816298790397174877223117345612840890905447851689835046066164443064435495141117872095457539285213399905708851752673701650986197704683439495235659865937503527178246189185724246027890778434827868479
e = 65537
high_p = 121612618057439377491893234820394610861816815559052233952438700644930219565204914707604533201740057532331014637555250302342831261394993528125583478630623993361944114671033382653887624385660705353904988324932092635052885387222723368916634052933090217574600695084708857274271614116870074627080278200070403260416

R.<x> = PolynomialRing(Zmod(n))
f = high_p + x
x = f.small_roots(X = 2^128,beta = 0.4)
if x:
    p = high_p + int(x[0])
    q = n // p
    d = gmpy2.invert(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))

#flag{W0W_y0u_rea1ly_go0d_at_us3_s4g3!}

在异或基础上夹杂移位

from secret import flag
from Crypto.Util.number import *


p, q = getPrime(1024), getPrime(1024)
N = p * q
p0 = p ^ (bytes_to_long(flag)<<444)
m = bytes_to_long(flag)
c = pow(m, 65537, N)
print(len(flag))
print('c=',c)
print('N=',N)
print('p0=',p0)

# 54
# c= 6187845844052645335477666563187579997555293403110620879123121166924703361821847984760733842049752886698011561451715570810292323756091403783920480396052120046379755571530451812078574368413924390017994278703794257118954968480994077586245800902748815905644287545189605031883291488844527496906890127546594960138582150272568163575590734246290813150131949296550974206595456421136190026954855755623761557179760444906148376433584795779131477110538212742401420633087881506416368853221110426491868881029814841479615979710066371796507692025126150957315754738584387325388998533227577023142894876376702128870643448600352603905149
# N= 14195810221536708489210274086946022255792382922322850338983263099316341767896809249586174293795778082892237356582757544364274847341220303582304283372889068290282580493623042441421715338444710303281638639785784613434328659529884972238348336971186339482788748316527376410510261228354155806341136524162787121212184386900663470590652770503564816948407257603737938414126069053610568675347826390537145556511048774030823322301932088595499671755944744816524811272617200683384649389274196659297432212847319503330409792704612575414010711158873031786577877685578976140462539734553598745329712188216200905451774357282278403189943
# p0= 111984935426070810628244029907949697819351004665202173622240566580193974673163315128983603277856218378729883402496424467491406698035050254407170555432448523469880166015507303737468316933545613178461925283040643344197452758878116752692499745309765526523083790825015522124083482964296662782850606081657447935191

看到异或就想起LitCTF那道Babyxor，但这题不大一样，因为把m进行了左移操作

因为m左移444位，这样子m后面444位都是0，所以异或之后，不影响p低位444值

而且54长度的flag转成int型数据是432，左移444位后是876位，异或之后p高(1024-876)=148位也是不变的

所以考点就是p部分高位和部分低位泄露

先取了444低位：plow = p0 % 2^445

然后得到148高位：phigh = (p0 >> 876) << 876

exp:

import gmpy2
from Crypto.Util.number import *

p0 = 111984935426070810628244029907949697819351004665202173622240566580193974673163315128983603277856218378729883402496424467491406698035050254407170555432448523469880166015507303737468316933545613178461925283040643344197452758878116752692499745309765526523083790825015522124083482964296662782850606081657447935191
c = 6187845844052645335477666563187579997555293403110620879123121166924703361821847984760733842049752886698011561451715570810292323756091403783920480396052120046379755571530451812078574368413924390017994278703794257118954968480994077586245800902748815905644287545189605031883291488844527496906890127546594960138582150272568163575590734246290813150131949296550974206595456421136190026954855755623761557179760444906148376433584795779131477110538212742401420633087881506416368853221110426491868881029814841479615979710066371796507692025126150957315754738584387325388998533227577023142894876376702128870643448600352603905149
n = 14195810221536708489210274086946022255792382922322850338983263099316341767896809249586174293795778082892237356582757544364274847341220303582304283372889068290282580493623042441421715338444710303281638639785784613434328659529884972238348336971186339482788748316527376410510261228354155806341136524162787121212184386900663470590652770503564816948407257603737938414126069053610568675347826390537145556511048774030823322301932088595499671755944744816524811272617200683384649389274196659297432212847319503330409792704612575414010711158873031786577877685578976140462539734553598745329712188216200905451774357282278403189943
e = 65537

phigh = (p0>>876)<<876
plow = p0 % 2**444

R.<x> = PolynomialRing(Zmod(n))

f = phigh + x*2**444 + plow
f = f.monic()
root = f.small_roots(X=2^432,beta=0.4)
if root:
    p = int(phigh + root[0]*2**444+plow)
    print("p=",p)
    q = n // p
    d = gmpy2.invert(e,(p-1)*(q-1))
    m = pow(c,d,n)
    print(long_to_bytes(int(m)))
else:
    print(0)

高位攻击结合加法

from Crypto.Util.number import *
import random
with open('flag.txt', 'r') as f:
    flag = f.read().encode()

m = bytes_to_long(flag)


def get_Prime(nbits):
    cnt = random.randint(1, 50)
    a = 678649776854118956235519899207445775941738710575390362283588104409625449204123832879
    b = 782005138760169933127526591821947364276106050094468540051784488164681554419515591399
    n = 959495185099860764003383321572335140174084694495020493292570101529012627928646710561
    if nbits > n.bit_length():
        n = n << (nbits - n.bit_length())
    seed = m

    while cnt != 0:
        while not isPrime(seed % pow(2, nbits)):
            seed = (a * seed + b) % n
        cnt -= 1

    return seed % pow(2, nbits)


p = getPrime(1024)
q = get_Prime(1024)
r = get_Prime(256)

leak1 = p * q
leak2 = p + r
print('leak1 =', leak1)
print("leak2 =", leak2)
"""
leak1 = 1726975620674482360213233806170947389541096108697994658733084655845389659114785301178576637466986314063371421235058595065888582231342820140568936192868977804603369486433318090941058139588565791324218134357184323086216185739954390473991279905043631888896016473122377727070109213645260572190927015695514811455255973089661406134295506499664743661249339253830939615669712520262820531049038976606781161641581457130675569478698323490748401496084828842168678572095280512663203781775164764035921218962082539851900388875197643683923415508978600441502826319004922595635629466742721341100368916333951643193549875170423774879551
leak2 = 112318855182255283836167471766806168213410186797367822915324918687801558224308427598350852972681526722686984900181855405532137931103674353513321543274324576313279396633244245181304978516377298223713109442863413211695328144733089915971055510790022499917701465412122183985372344800810303472010586670294890532292
"""

先从p,r入手，因为p(1024bit)的比特远大于r(256bit)的比特，即p的前768位(并不一定是这么多)并不受到r的影响，可用coppersmith恢复p

得到p后，看定义的函数，就是一个不知道多少次的lcg加密过程

n = n << (nbits - n.bit_length())这里保证了模数n足够大，因为再加密过程中，如果n不够大的话，会导致明文的数据丢失一些

再用q解密，需要注意的是用q解密的时候，这个n已经是移位过后的n

exp:

import gmpy2
from Crypto.Util.number import *

a = 678649776854118956235519899207445775941738710575390362283588104409625449204123832879
b = 782005138760169933127526591821947364276106050094468540051784488164681554419515591399
n = 959495185099860764003383321572335140174084694495020493292570101529012627928646710561
leak1 = 1726975620674482360213233806170947389541096108697994658733084655845389659114785301178576637466986314063371421235058595065888582231342820140568936192868977804603369486433318090941058139588565791324218134357184323086216185739954390473991279905043631888896016473122377727070109213645260572190927015695514811455255973089661406134295506499664743661249339253830939615669712520262820531049038976606781161641581457130675569478698323490748401496084828842168678572095280512663203781775164764035921218962082539851900388875197643683923415508978600441502826319004922595635629466742721341100368916333951643193549875170423774879551
leak2 = 112318855182255283836167471766806168213410186797367822915324918687801558224308427598350852972681526722686984900181855405532137931103674353513321543274324576313279396633244245181304978516377298223713109442863413211695328144733089915971055510790022499917701465412122183985372344800810303472010586670294890532292

R.<x> = PolynomialRing(Zmod(leak1))

high = (leak2>>256)<<256


f = high + x
x = f.small_roots(X=2^256,beta=0.4)
if x:
    p = high + x[0]
    print(p)
    q = leak1 // int(p)
    seed = q
    n = n << (1024 - 729)
    while 1:
        ani = gmpy2.invert(a,n)
        seed = ani*(seed - b) % n
        flag = long_to_bytes(seed)
        if b'flag' in flag:
            print(flag)
            break

二元copper

参考：二元coppersmith - 顶真珍珠 - 博客园 (cnblogs.com)

代码:

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

其中m为移位（shifts），d 为多项式中的最高幂。

[CISCN 2021华南]small

import random, hashlib
from Crypto.Util.number import getPrime
from secret import x, y, flag

BITS = 70

assert(2**BITS < x < 2**(BITS+1))
assert(2**BITS < y < 2**(BITS+1))

m = str(x) + str(y)
h = hashlib.sha256()
h.update(m.encode())
assert(flag == "flag{" + h.hexdigest() + "}")


p = getPrime(512)
a = getPrime(510)
b = getPrime(510)
c = (1 + a * x * y ** 2 + b * x ** 2 * y) % p
print("p = " + str(p))
print("a = " + str(a))
print("b = " + str(b))
print("c = " + str(c))

'''
p = 
a = 
b = 
c = 
'''

题目给出$x,y$都介于$2^{70}$和$2^{71}$之间

exp:

import hashlib
import itertools

p = 8813834626918693034209829623386418111935369643440896703895290043343199520112218432639643684400534953548489779045914955504743423765099014797611981422650409
a = 2817275225516767613658440250260394873529274896419346861054126128919212362519165468003171950475070788320195398302803745633617864408366174315471102773073469
b = 1763620527779958060718182646420541623477856799630691559360944374374235694750950917040727594731391703184965719358552775151767735359739899063298735788999711
c = 2298790980294663527827702586525963981886518365072523836572440106026473419042192180086308154346777239817235315513418426401278994450805667292449334757693881

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots

    return []

R.<x,y>=PolynomialRing(Zmod(p))

f = (1 + a * x * y ** 2 + b * x ** 2 * y) - c
#print(small_roots(f,bounds=(2^70,2^71)))
x,y = small_roots(f,bounds=(2^70,2^71))[0]
m = str(x) + str(y)

flag = "NSSCTF{" + hashlib.sha256(m.encode()).hexdigest() + "}"
print(flag)

P，Q产生方式由拼接而成

这里只是做个记录

原文：CTFtime.org / Crypto CTF 2021 / Hamul / Writeup

Hamul

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    P = int(str(p) + str(q))
    Q = int(str(q) + str(p))
    PP = int(str(P) + str(Q))
    QQ = int(str(Q) + str(P))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode('utf-8'))
if m < n:
    c = pow(m, 65537, n)
    print('n =', n)
    print('c =', c)

# n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043
# c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399

注意到，PP,QQ的产生方式：

令$x=str(P),y=str(Q)$，于是能把P,Q写成这样的形式：$P=10^xp + q$，$Q=10^yq+p$

再令$x’ = str(PP),y’=str(QQ)$，于是$PP = 10^{x’}P+Q$，$Q=10^{y’}Q+P$

$\because N = PP×QQ$，这个N可以写成$10^{x+x’+y+y’}pq+…+pq$，每一项都含有pq。

因为$x+x’+y+y’$很大，所以存在$str(N)[:?]=str(pq)[:?]$，$str(N)[?:]=str(pq)[?:]$

测试发现$str(N)[:18]=str(pq)[:18]$,$str(N)[-18:]=str(pq)[-18:]$

也有出现前18位，后19位一样，前19位，后18位一样的情况

因为$len(str(pq))=38或39$，可以爆破两位的方式求得pq

exp:

from Crypto.Util.number import *
from tqdm import tqdm

def decrypt_RSA(c, e, p, q):
    phi = (p-1) * (q-1)
    d = inverse(e, phi)
    m = pow(c, d, p*q)
    print(long_to_bytes(int(m)))

n = 
c = 

low = str(n)[-18:]
high = str(n)[:18]
pq_prob = []

for i in range(10):
    for j in range(10):
        pq_prob.append(int(high + str(i) + str(j)+ low))
        
for x in tqdm(pq_prob):
    f = factor(x)
    if (len(f) == 2 and f[0][0].nbits() == 64):
        p, q = f[0][0], f[1][0]
        break

P = int(str(p) + str(q))
Q = int(str(q) + str(p))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
N = PP * QQ
print(N == n)
decrypt_RSA(c, 65537, PP, QQ)

HamburgerRSA

from Crypto.Util.number import *

flag = open('flag.txt').read()
nbit = 64

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PP = int(str(p) + str(p) + str(q) + str(q))
    QQ = int(str(q) + str(q) + str(p) + str(p))
    if isPrime(PP) and isPrime(QQ):
        break

n = PP * QQ
m = bytes_to_long(flag.encode())
c = pow(m, 65537, n)
print('n =', n)
print('c =', c)

类似上面那道题

不同的是爆破位数变成了1

from Crypto.Util.number import *
from tqdm import tqdm

def decrypt_RSA(c, e, p, q):
    phi = (p-1) * (q-1)
    d = inverse(e, phi)
    m = pow(c, d, p*q)
    print(long_to_bytes(int(m)))

n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096

low = str(n)[-18:]
high = str(n)[:18]
pq_prob = []

def boom1(low,high):    
    for i in range(10):
        pq_prob.append(int(high + str(i)+ low))
        
    for x in tqdm(pq_prob):
        f = factor(x)
        if (len(f) == 2 and f[0][0].nbits() == 64):
            p, q = f[0][0], f[1][0]

            P = int(str(p) + str(p))
            Q = int(str(q) + str(q))
            PP = int(str(P) + str(Q))
            QQ = int(str(Q) + str(P))
            N = PP * QQ
            if (N == n):
                decrypt_RSA(c, 65537, PP, QQ)
                break
                
def boom2(low,high):    
    for i in range(10):
        for j in range(10):
            pq_prob.append(int(high + str(i)+ str(j)+low))
        
    for x in tqdm(pq_prob):
        f = factor(x)
        if (len(f) == 2 and f[0][0].nbits() == 64):
            p, q = f[0][0], f[1][0]

            P = int(str(p) + str(p))
            Q = int(str(q) + str(q))
            PP = int(str(P) + str(Q))
            QQ = int(str(Q) + str(P))
            N = PP * QQ
            if (N == n):
                decrypt_RSA(c, 65537, PP, QQ)
                break

def boom3(low,high):    
    for i in range(10):
        for j in range(10):
            for k in range(10):
                pq_prob.append(int(high + str(i) + str(j) + str(k)+ low))
        
    for x in tqdm(pq_prob):
        f = factor(x)
        if (len(f) == 2 and f[0][0].nbits() == 64):
            p, q = f[0][0], f[1][0]

            P = int(str(p) + str(p))
            Q = int(str(q) + str(q))
            PP = int(str(P) + str(Q))
            QQ = int(str(Q) + str(P))
            N = PP * QQ
            if (N == n):
                decrypt_RSA(c, 65537, PP, QQ)
                break

boom1(low,high)
boom2(low,high)
boom3(low,high)

根据题目改点东西

黑盾杯2020 Change

from flag import FLAG
from Crypto.Util.number import *
import gmpy2
import random

while True:
    p = int(gmpy2.next_prime(random.randint(10**399, 10**400-1)))
    q = int(str(p)[200:]+str(p)[:200])
    if gmpy2.is_prime(q):
        break

m = bytes_to_long(FLAG)
n = p*q
e = 65537
c = pow(m,e,n)

with open("enc","wb") as f:
    f.write(str(c))
    f.write("\n")
    f.write(str(n))

记$p$的高位为$ph$，低位为$pl$，易知$ph$,$pl$都是$10^{200}$左右的数

则$p = ph×10^{200}+pl$，$q = pl×10^{200}+ph$

于是$n = (ph×pl)×10^{400}+ph^2×10^{200}+pl^2×10^{200}+ph×pl$

因为$n$大概是$10^{800}$大小的数

记$ph×pl$的高位为$pph$，低位为$ppl$，都是$10^{200}$左右的数

$pph = \frac{n}{10^{600}}$，$ppl = n % 10^{200}$

求出$pph$和$ppl$后，即可求得$ph×pl$

再联立$n = (ph×pl)×10^{400}+ph^2×10^{200}+pl^2×10^{200}+ph×pl$

求解$pl和ph$

exp:

from sympy import symbols,solve
import gmpy2
from Crypto.Util.number import *

c = 
n = 
e = 0x10001

pph = n // pow(10, 600)
ppl = n % pow(10, 200)
phpl = pph*pow(10, 200) + ppl

n -= pow(10, 400)*phpl + phpl

tmp = pow(10, 200)

ph = symbols('ph')
pl = symbols('pl')
s = solve([ph*pl-phpl, tmp*ph*ph + tmp*pl*pl - n], [ph, pl])
for i in s:
    ph,pl = int(i[0]), int(i[1])
    p = ph*tmp + pl
    q = pl*tmp + ph
    if p > 0 and q > 0 and gmpy2.is_prime(p) and gmpy2.is_prime(q):
        break

d = gmpy2.invert(e, (p-1)*(q-1))

print(long_to_bytes(pow(c, d, p*q)))

-------------已经到底啦！-------------