【20211008 鹤城杯】Crypto方向WP

这是我写过最短的WP了吧

这至少flag改下吧，一点都不走心

• 鹤城杯
• • easy_crypto
  • a_crypto
  • babyrsa
  • Crazy_Rsa_Tech

社会主义好，社会主义好

lj原题

下班

上班

Striving师傅博客里有，不愧是他

用q的低位得到p的低位，和Yusa美国大选那题类似，然后用CopperSmith解方程，这样范围应该可以

稍微写一下吧

首先我们简单试验下

from Crypto.Util.number import *

p = getPrime(128)
q = getPrime(128)
n = p * q
p1 = p % (2 ** 50)
q1 = q % (2 ** 50)
print(bin(p1 * q1)[2:][-50:])
print(bin(n)[2:][-50:])

11111010001010111111110101111111001001100100000111
11111010001010111111110101111111001001100100000111

得到的结果显示知道n和q的低位，求出p的低位显然不在话下，这个就很想中国海洋大学的那道题的简化版

有师傅说（没有师傅说）这不就是已知p的高位吗，直接用CopperSmith行不行

la佬的博客上也说了，起码知道约 1 2 frac{1}{2} 21​位数才行，而且就算是像corCTF babyrsa可以爆破，但题目是1024左移724位，最多爆破几位也远远不够

所以必须先用q的低位，得到p的低265位，这样相当于知道p的565位了，这样才有一半

其次根据n和p的高300位和低265位求p中间的459位，可以列一式子
p 0 < < 724 + p 1 < < 265 + p 2 = n p_0<<724+p1<<265+p_2=n p0​<<724+p1<<265+p2​=n
位运算不好看就
p 0 × 2 724 + p 1 × 2 265 + p 2 = n p_0times 2^{724}+p_1times 2^{265}+p_2=n p0​×2724+p1​×2265+p2​=n
p 1 p_1 p1​不知道，设为 x x x
p 0 × 2 724 + x × 2 265 + p 2 = n p_0times 2^{724}+xtimes 2^{265}+p_2=n p0​×2724+x×2265+p2​=n
这不就是CopperSmith解一元吗，想了解更多的师傅可以看corCTF babyrand

emmmmmm本来以为差不多，但是没有出来，解出来是空的，也就是范围太大，CopperSmith还是解不了

看了Striving师傅的博客

原来还有这种讲究，我还以为已经一半多了

哦，我记起来了，在corCTF也不是没遇到过，所以多爆几位吧

完整的exp，这个自己想不容易被带偏，当然Striving师傅的博客里有直接推导出p低位的

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from gmpy2 import *
from tqdm import tqdm
import sys

p0 = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q2 = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 0x10001

# q2 -> p2
known_low_bits = 265
n2 = bin(n)[2:][-known_low_bits:]
p2 = ''
for i in range(known_low_bits):
    if bin(int('1' + p2, 2) * q2)[2:].endswith(n2[-(i+1):]):
        p2 = '1' + p2
    else:
        p2 = '0' + p2
p2 = int(p2, 2)
# print(bin(p2 * q2)[2:][-known_low_bit:])
# print(n2)

# p2, p0 -> p
p0 = p0 << 724
unknown_bits = 459
PR. = PolynomialRing(Zmod(n))
for bit in range(10):
    fx = p0 + x * 2 ^ (265 + bit) + p2
    for i in tqdm(range(2**bit)):
        f = fx + i * 2 ^ 265
        f = f.monic()
        kbits = unknown_bits - bit
        p1 = f.small_roots(X=2 ^ kbits, beta=0.4)
        if p1:
            p = p0 + int(p1[0]) * 2 ^ (265 + bit) + p2 + i * 2 ^ 265
            assert n % p == 0
            q = n // p
            print(long_to_bytes(pow(c, invert(e, n-p-q+1), n)))
            sys.exit(0)

广播，sage里crt一把搜就出来了

下班