EzRSA

1、题目信息

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

def padding(f):
    random_chars = bytes([random.randint(0, 255) for _ in range(32)])
    f = f + random_chars
    return f

def guess_p(p):
    e = 65537
    
    P = p
    n1 = getPrime(512)*getPrime(512)
    with open('enc.txt', 'w+') as f:
        while jacobi(2,n1) == 1:
            n1 = getPrime(512)*getPrime(512)
        while P:
            pad = random.randint(0, 2**2023)**2 
            message = pad << 1 + P % 2
            cipher = pow(message, e, n1)
            f.write(str(cipher)+'n')
            P //= 2
    print("n1 = "+ str(n1) )    
    
def guess_q(q):
    
    def encrypt(q, n):
        e = random.randint(1000,2000)
        noise = random.randint(0, n - 1)
        c = pow(q+noise,e,n)
        return e, noise,c 
    
    n2 = getPrime(512)*getPrime(512)
    e1, noise1, c1 = encrypt(q, n2)
    e2, noise2, c2 = encrypt(q, n2)
    print("n2 = "+ str(n2) ) 
    print('(e1, noise1, c1) =', (e1,noise1,c1))
    print('(e2, noise2, c2) =', (e2,noise2,c2))
p = getPrime(512)
q = getPrime(512)

n = p*q
guess_p(p)
guess_q(q)
e = 0x10001
flag = padding(flag)
m = bytes_to_long(flag)
c = pow(m,e,n)

print("c = " + str(c))
'''
n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393
(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369
'''

题目分析：
看到jacobi(2,n1)知道是二次剩余的知识

相关消息攻击直接解

exp

import binascii
import libnum
from gmpy2 import *
from Crypto.Util.number import *
n1 = 65634094430927080732256164808833233563732628654160389042977689628512527168256899310662239009610512772020503283842588142453533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554634493581962527475555869292091755676130810562421465063412235309
(e1, noise1, c1) = (1743, 44560588075773853612820227436439937514195680734214431948441190347878274184937952381785302837541202705212687700521129385632776241537669208088777729355349833215443048466316517110778502508209433792603420158786772339233397583637570006255153020675167597396958251208681121668808253767520416175569161674463861719776, 65643009354198075182587766550521107063140340983433852821580802983736094225036497335607400197479623208915379722646955329855681601551282788854644359967909570360251550766970054185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853621152905983)
(e2, noise2, c2) = (1325, 35282006599813744140721262875292395887558561517759721467291789696459426702600397172655624765281531167221787036009507833425145071265739486735993631460189629709591456017092661028839951392247601628468621576100035700437892164435424035004463142959219067199451575338270613300215815894328788753564798153516122567683, 50327632090778183759544755226710110702046850880299488259739672542025916422119065179822210884622225945376465802069464782311211031263046593145733701591371950349735709553105217501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773715759733714)
c = 124349762993424531697403299350944207725577290992189948388824124986066269514204313888980321088629462472088631052329128042837153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177197863522573410860341245613331398610013697803459403446614221369
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802940810851806104430306195931179902098180199167945649526235613636163362672777298968943319216325949503045377100235181706964846408396946496139224344270391027205106691880999410424150216806861393

ciphers = []
with open('enc.txt') as f:
    for line in f.read().split('n'):
        if line.strip():
            ciphers.append(int(line.strip()))

p = ''
for i in ciphers:
    if jacobi(i,n1) == -1:
        p = '0' + p
    else:
        p = '1' + p

p = int(p,2)

def franklinReiter(n,e1,e2,c1,c2,noise1,noise2):
    PR.<x> = PolynomialRing(Zmod(n))
    g1 = (x + noise1)^e1 - c1
    g2 = (x + noise2)^e2 - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic() # 
    return -gcd(g1, g2)[0]

q=franklinReiter(n2,e1,e2,c1,c2,noise1,noise2)
q = 13189337905641321257372188436353844418280745284875462357019668708167547026960641869513283218672677712590326347601424108528959315675307896082223561007980457
p = 9473204278465588641589315677772678997836862033858760337441231265335880892205102590571357305720744128962068300763212493598006400853597404586755248901932203
e = 0x10001
phi = (p - 1) * (q - 1)
d = inverse(e,phi)
print(long_to_bytes(int(pow(c,d,p * q))))
# DASCTF{W05-y03r_m2st1r-j2c0b1_2nd_p01yn0mi2l!}