Skip to content

Random_RSA

Category: Cryptography

Source: 祥云杯2021

Author: unknown

Score: 10

Description

一把梭，好像不行哦。

Random_RSA.zip

题目描述

题目基于RSA，[公式]。题目给出flag加密的密文[公式]。

题目给出了关于[公式]的提示：题目给了随机种子列表。对于每个随机种子，题目会基于这个随机种子生成一个随机数列表，每次都从列表里面指定位置抠掉一个数，并且给出其他数组成的列表；用被抠掉那个数作为流密钥，与[公式]的十进制表示字符串对应字节进行异或，得到一个密文。

我的解答

首先我们先尝试搞出[公式]：我们通过设随机种子，得到列表。发现只有python 2生成的列表才能对得上，所以我们需要用python 2跑程序，并生成正确的流密钥。然后就是异或得到[公式]。

之后就是根据[公式]枚举[公式]，尝试[公式]是否不为1。若是的话，那这个值就是[公式]。进而得到[公式]的分解并对flag的密文进行解密。得到[公式]的代码如下：

import random
c2 = '[[58, 53, 122] [145, 124, 244] [5, 19, 192] [255, 23, 64] [57, 113, 194] [246, 205, 162] [112, 87, 95] [215, 147, 105] [16, 131, 38] [234, 36, 46] [68, 61, 146] [148, 61, 9] [139, 77, 32] [96, 56, 160] [121, 76, 17] [114, 246, 92] [178, 206, 60] [168, 147, 26] [168, 41, 68] [24, 93, 84] [175, 43, 88] [147, 97, 153] [42, 94, 45] [150, 103, 127] [68, 163, 62] [165, 37, 89] [219, 248, 59] [241, 182, 8] [140, 211, 146] [88, 226, 2] [48, 150, 56] [87, 109, 255] [227, 216, 65] [23, 190, 10] [5, 25, 64] [6, 12, 124] [53, 113, 124] [255, 192, 158] [61, 239, 5] [62, 108, 86] [123, 44, 64] [195, 192, 30] [30, 82, 95] [56, 178, 165] [68, 77, 239] [106, 247, 226] [17, 46, 114] [91, 71, 156] [157, 43, 182] [146, 6, 42] [148, 143, 161] [108, 33, 139] [139, 169, 157] [71, 140, 25] [28, 153, 26] [241, 221, 235] [28, 131, 141] [159, 111, 184] [47, 206, 11] [220, 152, 157] [41, 213, 97] [4, 220, 10] [77, 13, 248] [94, 140, 110] [25, 250, 226] [218, 102, 109] [189, 238, 66] [91, 18, 131] [23, 239, 190] [159, 33, 72] [183, 78, 208] [209, 213, 101] [111, 50, 220] [166, 104, 233] [170, 144, 10] [187, 87, 175] [195, 59, 104] [165, 179, 179] [99, 247, 153] [195, 61, 100] [223, 159, 165] [230, 93, 184] [87, 28, 35] [35, 122, 38] [158, 188, 163] [229, 192, 222] [12, 12, 192] [207, 95, 224] [127, 113, 137] [22, 114, 143] [13, 45, 144] [70, 140, 211] [57, 101, 42] [132, 62, 129] [40, 128, 124] [1, 132, 161] [164, 33, 133] [252, 201, 32] [8, 18, 247] [1, 88, 55] [201, 135, 186] [101, 254, 125] [236, 196, 39] [148, 24, 103] [101, 29, 253] [97, 156, 64] [90, 103, 91] [50, 48, 80] [206, 22, 93] [11, 114, 174] [61, 132, 247] [215, 32, 232] [95, 128, 90] [57, 35, 228] [163, 143, 107] [178, 250, 28] [64, 107, 225] [106, 115, 207] [85, 134, 21] [118, 201, 76] [234, 34, 22] [241, 236, 122] [111, 185, 127] [1, 26, 164] [254, 57, 117] [243, 27, 32] [161, 88, 80] [50, 165, 93] [87, 182, 216] [184, 159, 63] [167, 166, 123] [37, 78, 33] [186, 81, 58] [48, 3, 239] [70, 186, 13] [56, 108, 178] [54, 55, 235] [105, 180, 105] [16, 194, 98] [136, 11, 41] [18, 203, 79] [185, 114, 170] [148, 181, 223] [118, 57, 160] [23, 250, 181] [235, 219, 228] [44, 151, 38] [185, 224, 134] [42, 162, 122] [3, 9, 158] [129, 245, 2] [66, 241, 92] [80, 124, 36]]'
res2 = [55, 5, 183, 192, 103, 32, 211, 116, 102, 120, 118, 54, 120, 145, 185, 254, 77, 144, 70, 54, 193, 73, 64, 0, 79, 244, 190, 23, 215, 187, 53, 176, 27, 138, 42, 89, 158, 254, 159, 133, 78, 11, 155, 163, 145, 248, 14, 179, 23, 226, 220, 201, 5, 71, 241, 195, 75, 191, 237, 108, 141, 141, 185, 76, 7, 113, 191, 48, 135, 139, 100, 83, 212, 242, 21, 143, 255, 164, 146, 119, 173, 255, 140, 193, 173, 2, 224, 205, 68, 10, 77, 180, 24, 23, 196, 205, 108, 28, 243, 80, 140, 4, 98, 76, 217, 70, 208, 202, 78, 177, 124, 10, 168, 165, 223, 105, 157, 152, 48, 152, 51, 133, 190, 202, 136, 204, 44, 33, 58, 4, 196, 219, 71, 150, 68, 162, 175, 218, 173, 19, 201, 100, 100, 85, 201, 24, 59, 186, 46, 130, 147, 219, 22, 81]
seeds2 = [4827, 9522, 552, 880, 7467, 7742, 9425, 4803, 6146, 4366, 1126, 4707, 1138, 2367, 1081, 5577, 4592, 5897, 4565, 2012, 2700, 1331, 9638, 7741, 50, 824, 8321, 7411, 6145, 1271, 7637, 5481, 8474, 2085, 2421, 590, 7733, 9427, 3278, 5361, 1284, 2280, 7001, 8573, 5494, 7431, 2765, 827, 102, 1419, 6528, 735, 5653, 109, 4158, 5877, 5975, 1527, 3027, 9776, 5263, 5211, 1293, 5976, 7759, 3268, 1893, 6546, 4684, 419, 8334, 7621, 1649, 6840, 2975, 8605, 5714, 2709, 1109, 358, 2858, 6868, 2442, 8431, 8316, 5446, 9356, 2817, 2941, 3177, 7388, 4149, 4634, 4316, 5377, 4327, 1774, 6613, 5728, 1751, 8478, 3132, 4680, 3308, 9769, 8341, 1627, 3501, 1046, 2609, 7190, 5706, 3627, 8867, 2458, 607, 642, 5436, 6355, 6326, 1481, 9887, 205, 5511, 537, 8576, 6376, 3619, 6609, 8473, 2139, 3889, 1309, 9878, 2182, 8572, 9275, 5235, 6989, 6592, 4618, 7883, 5702, 3999, 925, 2419, 7838, 3073, 488, 21, 3280, 9915, 3672, 579]

c2 = eval(c2.replace('] [', '], ['))
myc = []
for i in range(0, len(seeds2)):
    random.seed(seeds2[i])
    rands = []
    for j in range(0,4):
        rands.append(random.randint(0,255))
    myc.append(rands[i % 4])

dp = [x ^ y for x, y in zip(myc, res2)]
dp = int(bytearray(dp))

print(dp)

得到[公式]的分解进而解密[公式]的代码如下：

from Crypto.Util.number import *

n=81196282992606113591233615204680597645208562279327854026981376917977843644855180528227037752692498558370026353244981467900057157997462760732019372185955846507977456657760125682125104309241802108853618468491463326268016450119817181368743376919334016359137566652069490881871670703767378496685419790016705210391
ct=61505256223993349534474550877787675500827332878941621261477860880689799960938202020614342208518869582019307850789493701589309453566095881294166336673487909221860641809622524813959284722285069755310890972255545436989082654705098907006694780949725756312169019688455553997031840488852954588581160550377081811151

dp = 5372007426161196154405640504110736659190183194052966723076041266610893158678092845450232508793279585163304918807656946147575280063208168816457346755227057

e=0x10001

for k in range(1, 100000):
    p = (e * dp - 1) // k + 1
    if (n % p == 0):
        break

q = n // p
d = inverse(e, (p-1)*(q-1))

m = pow(ct, d, n)
print(long_to_bytes(m))

Flag

flag{74281db3-c6f0-e59a-4da6-39b8c71250fe}

Reference

Writeup from https://zhuanlan.zhihu.com/p/402690414