20211008-鹤城杯-CryptoSecPartWriteUp

Posted on Edited on In , Views: Symbols count in article: 4k Reading time ≈ 4 mins.

 

babyrsa

题目描述

  • task.py

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    from Crypto.Util.number import getPrime, bytes_to_long
    from secret import flag

    p = getPrime(1024)
    q = getPrime(1024)
    n = p * q
    e = 65537
    hint1 = p >> 724
    hint2 = q % (2 ** 265)
    ct = pow(bytes_to_long(flag), e, n)
    print(hint1)
    print(hint2)
    print(n)
    print(ct)

  • out.txt

    1
    2
    3
    4
    1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
    40812438243894343296354573724131194431453023461572200856406939246297219541329623
    21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
    19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188

RSA，已知p的高300位和q的低265位

知道q的低位，可以求p的低256位，然后可以CopperSmith解个小根
$$
p_0<<724+p1<<265+p_2=n\notag
$$
完整的exp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#!/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