【20211008 鹤城杯】Crypto方向WP_4XWi11的博客-程序员宅基地

技术标签: python  树哥让我天天写之Crypto  

这是我写过最短的WP了吧

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

鹤城杯

easy_crypto

社会主义好,社会主义好

a_crypto

lj原题

下班


上班

babyrsa

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行不行

image-20211009143059578

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_0\times 2^{724}+p_1\times 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_0\times 2^{724}+x\times 2^{265}+p_2=n p0×2724+x×2265+p2=n
这不就是CopperSmith解一元吗,想了解更多的师傅可以看corCTF babyrand

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

看了Striving师傅的博客

image-20211009152100154

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

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

image-20211009152240651

完整的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.<x> = 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)

image-20211009175518651

Crazy_Rsa_Tech

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

下班

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_49109277/article/details/120676445

智能推荐

随便推点