Coppersmith part1-----原理

2024-03-18 Read 234 4 comments

概述

首先我们假设我们在$modM$下有度为$d$的系数为整数的首一多项式(对于如何将多项式转换为首一多项式，这里不做阐述):$F(x)=x^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0{\pmod{M}}$

- Read More -

网络安全

香山杯复现

2023-10-23 Read 107 One comment

lift

import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
def pad(s,l):
    return s + os.urandom(l - len(s))
def gen():
    g = getPrime(8)
    while True:
        p = g * random.getrandbits(138) + 1
        if isPrime(p):
            break
    while True:
        q = g * random.getrandbits(138) + 1
        if isPrime(q):
            break
    N = p ** 5 * q
    phi = p ** 4 * (p - 1) * (q - 1)
    d = random.getrandbits(256)
    e = inverse(d, phi)
    E = e * g
    hint = gmpy2.gcd(E, phi)
    return N, E, hint

flag = pad(flag,64)
m = bytes_to_long(flag)
n,e,hint = gen()
c = pow(m,e,n)
print(f'hint = {hint}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
# hint = 251
# n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
# e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
# c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

根据gen函数，我们可以得知：
$n=p^5q,E=e*g,hint=gcd(E,\phi(n)),p=g*a1+1,q=g*a2+1$
又因为：
$$\phi(n)=p^4(p-1)(q-1)=p^4(g*a1)(g*a2)$$
所以g一定是E和$\phi(n)$的公因子，所以g|hint
但我们发现hint是个质数，所以我们可以得知g=hint=251
由于n是多素数组成的，且d仅有256位，所以d是一个小根，因此可以考虑用copper来求解d
$$ed\equiv 1\ (mod\ \phi(n))$$
得到d之后，根据$ed-1=kp^4(p-1)(q-1)$，$n=p^5q$，我们可以知道$gcd(ed-1,n)=p^4$（至少为$p^4$)，所以我们依次可以求出p，q的值
exp部分：

from gmpy2 import *
E = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
g = 251
e = E // g
PR.<d> = PolynomialRing(Zmod(n))
f = e * d - 1
f = f.monic()
ans = f.small_roots(d = 2 ** 256, beta = 0.66)
print('d =', ans[0])
p4 = GCD(e * int(ans[0]) - 1, n)
p = iroot(p4, 4)[0]
print('p =', p)
q = n // (p * p4)
print('q =', q)

得到p，q之后，因为得到c的式子为：
$$c\equiv m^{E}$$
因为E和n不互质，我们无法直接求E逆元，但我们知道e的逆元d，可得到：
$$c^d\equiv m^g\ (mod\ n)$$
因为$n=p^5q$，我们可以想到上式可以拆为：
$$\left\{\begin{array}{rcl}c^d\equiv m^g\ (mod\ p)\\c^d\equiv m^g\ (mod\ q)\\\end{array} \right. $$
然后用AMM算法，我们可以将上述式子求出：
$$\left\{\begin{array}{rcl}m_p\equiv m^g\ (mod\ p)\\m_q\equiv m^g\ (mod\ q)\\\end{array} \right. $$
但是$n=p^5q$，flag被填充到了512位，若是直接用中国剩余定理去求$mod\ pq$下的根是不够的
这里我们可以用Hensel lifting将$mod\ p$下的解提升至$mod\ p^5$下的解

Hensel lifting引理设$k\geq 2$是正整数，p为素数， $f(x)\equiv 0\ (mod\ p^{k-1})$
如果$f'(x)\not\equiv 0\ (mod\ p)$，那么存在在$mod\ p$意义下唯一的整数t，使得$f(x+tp^{k-1})\equiv 0\ (mod p^k)$由$t\equiv -f'(x)^{-1}({f(r) \over p^{k-1}})$给出
如果$f'(x)\equiv 0\ (mod\ p)$且$f(x)\equiv 0\ (mod\ p^k)$，那么对任意正整数t，都有$f(x+tp^{k-1})\equiv 0\ (mod p^k)$
如果$f'(x)\equiv 0\ (mod\ p)$且$f(x)\not\equiv 0\ (mod\ p^k)$，那么对任意正整数t，都有$f(x+tp^{k-1})\not\equiv 0\ (mod p^k)$
详细介绍可以参考：Hensel lifting引理

此题正好有$f(m)=m^g-c^d\ (mod\ p)$，且我们已经用AMM算法求出m的所有可能情况，我们将之转至$\mod p^5$下，可以有$f(m)=m^g-c^d\ (mod\ p^5)$，在模$p^5$情况下得到的m已经足以满足512位的要求，所以此时我们只需要判别是否包含flag标识就可以得到明文m了
exp：

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

def onemod(e, q):
    p = random.randint(1, q - 1)
    while ((powmod(p, (q - 1) // e, q)) == 1):
        p = random.randint(1, q)
    return p

def AMM_rth(x, e, N):
    assert ((N - 1) % e == 0)
    p = onemod(e, N)
    
    t = 0
    s = N - 1
    while (s % e == 0):
        s = s // e
        t += 1
    k = 1
    
    while ((s * k + 1) % e != 0):
        k += 1
    delta = (s * k + 1) // e

    a = powmod(p, e ** (t - 1) * s, N)
    b = powmod(x, e * delta - 1, N)
    c = powmod(p, s ,N)
    h = 1
    for i in range(1, t):
        d = powmod(b, e ** (t - 1 -i), N)
        if d == 1:
            j = 0
        else:
            j = (- math.Log(d, a)) % e
        b = b * (c ** (e ** j)) % N
        h = h * (c ** j) % N
        c = c ** e % N
    result = powmod(x, delta, N) * h
    return result

def ALL_ROOT2(r, q):  
    list1 = set()
    while(len(list1) < r):
        p = powmod(random.randint(1, q - 1), (q - 1) // r, q)
        list1.add(p)
    return list1

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr * m) % q
        mp.append(r)
    return mp


d = 39217838246811431279243531729119914044224429322696785472959081158748864949269
p = 69367143733862710652791985332025152581988181
q = 67842402383801764742069883032864699996366777

n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162
g = 251

c1 = powmod(c, d, n)
cp = c1 % p

mp = AMM_rth(cp, g, p)
rt1 = ALL_ROOT2(g, p)
amp = ALL_Solution(mp, p, rt1, cp, g)

k = 5
for m in amp:
    for i in range(1, k):
        inv_fx = - invert(g * (m ** (g - 1)), p)
        di = (m ** g - c1) // (p ** i)
        t = inv_fx * di % p
        m = m + (p ** i) * t % (p ** ( i + 1))
    if b'flag' in long_to_bytes(m):
        print(long_to_bytes(m))

- Read More -

网络安全

黑龙江省赛复现

2023-10-03 Read 136 3 comments

Easy_RSA

import libnum
import gmpy2
from Crypto.Util.number import *
import flag,e1,e2
#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
ec1=pow(bytes_to_long(str(e1).ljust(20,"D").encode()),3,p*q)
ec2=pow(bytes_to_long(str(e2).ljust(20,"A").encode()),5,p*q)
m=libnum.s2n(flag)
n=p*q
c1=pow(m,e1,n)
c2=pow(m,e2,n)

print("n1=",n)
print("ec1=",ec1)
print("c1=",c1)
print("n2=",n)
print("ec2=",ec2)
print("c2=",c2)

# n1= 27929259512873502442719286790227037320417984116570178470037376373267390909685621247157535458203218619293705428397911754453556082799420494496904478215709219317542924547049229150153308059698341011305505985823374280465467094476511869541135508518055946815227085548571701115773386101962695795789178321155174729047033298389886321980592410739667139376075568555729949442873964097042006391886635957242436522435588904492484342259494858627609438654632887244523845583473711604632109405043439047289868784236481926074763997559971182741918345193506253460323445846136663027639802131457594564405906763806426256107923417802076262573737
# ec1= 24979839185643431898760549059477070141596292955202172081572583839065034831779499992829742773873064296311713734486020739853343887094398935731264
# c1= 17695186679431856780362905635257355413310120106982055323913669124182832151093921194946365178919380690844190324897933591567360925332869903671651849060145290581360223200011298757871213149464298017718829480721410479504940393501845624196721013966839230696831321482946841011452400364600924503121451272593970649100410603943321149604376033957124800064565646929720179239631538966228020882733213221035707244692798307971636126058586394357032072695921642665492919186476321028415907982915011972040971875733852055633796811898421692604356476773910338982400925245494707729878821466569634334862311750349321720627252469986162120031838
# n2= 27929259512873502442719286790227037320417984116570178470037376373267390909685621247157535458203218619293705428397911754453556082799420494496904478215709219317542924547049229150153308059698341011305505985823374280465467094476511869541135508518055946815227085548571701115773386101962695795789178321155174729047033298389886321980592410739667139376075568555729949442873964097042006391886635957242436522435588904492484342259494858627609438654632887244523845583473711604632109405043439047289868784236481926074763997559971182741918345193506253460323445846136663027639802131457594564405906763806426256107923417802076262573737
# ec2= 2838620519239658396968146844964839207179863729944843241951228382052657801460586137213053314019699976475855578055607417923815486109050614096157077528657405905877896929808094661904905136761365045387901486261011216958309860644255996588189249
# c2= 10770781309274554738409447671578241895686779262243081931452089039730277591151694112684863740412412713684216227740930573490322958500198235497947657939304932868457999239593145330718657422535271157683896034543125292529800047408131765376686654378173684648427311300423776510153307756388404568013401217965931456538849277670384454454507752525534110389604969437991055504757081225690155489265359117617764571537216746554060783131168749700810806387918510612057149583061938836035963175555630655718716139689761210220525955656039741684390906935720406757364893793459339618913268943282961044530062475057887777134887741597041684698119

此题的ec1，ec2都经过了填充，但很明显，此处的填充完后只有208=160bits，就算是经过了指数运算后仍然远小于pq。。。
所以我们大可以试试直接将ec1，ec2直接开方
QQ图片20231003102903.png
确实可以开出来（
得到ec1为34967，ec2为65535
之后就是一个简单的共模攻击了
exp：

from Crypto.Util.number import *
import gmpy2

ec1 = 24979839185643431898760549059477070141596292955202172081572583839065034831779499992829742773873064296311713734486020739853343887094398935731264
ec1 = gmpy2.iroot(ec1, 3)[0]
print(long_to_bytes(ec1))
ec2= 2838620519239658396968146844964839207179863729944843241951228382052657801460586137213053314019699976475855578055607417923815486109050614096157077528657405905877896929808094661904905136761365045387901486261011216958309860644255996588189249
ec2 = gmpy2.iroot(ec2, 5)[0]
print(long_to_bytes(ec2))

e1 = 34967
e2 = 65535
n = 27929259512873502442719286790227037320417984116570178470037376373267390909685621247157535458203218619293705428397911754453556082799420494496904478215709219317542924547049229150153308059698341011305505985823374280465467094476511869541135508518055946815227085548571701115773386101962695795789178321155174729047033298389886321980592410739667139376075568555729949442873964097042006391886635957242436522435588904492484342259494858627609438654632887244523845583473711604632109405043439047289868784236481926074763997559971182741918345193506253460323445846136663027639802131457594564405906763806426256107923417802076262573737
c1 = 17695186679431856780362905635257355413310120106982055323913669124182832151093921194946365178919380690844190324897933591567360925332869903671651849060145290581360223200011298757871213149464298017718829480721410479504940393501845624196721013966839230696831321482946841011452400364600924503121451272593970649100410603943321149604376033957124800064565646929720179239631538966228020882733213221035707244692798307971636126058586394357032072695921642665492919186476321028415907982915011972040971875733852055633796811898421692604356476773910338982400925245494707729878821466569634334862311750349321720627252469986162120031838
c2 = 10770781309274554738409447671578241895686779262243081931452089039730277591151694112684863740412412713684216227740930573490322958500198235497947657939304932868457999239593145330718657422535271157683896034543125292529800047408131765376686654378173684648427311300423776510153307756388404568013401217965931456538849277670384454454507752525534110389604969437991055504757081225690155489265359117617764571537216746554060783131168749700810806387918510612057149583061938836035963175555630655718716139689761210220525955656039741684390906935720406757364893793459339618913268943282961044530062475057887777134887741597041684698119

_, s1, s2 = gmpy2.gcdext(e1, e2)
m = pow(c1, s1, n)*pow(c2, s2, n) % n
print(long_to_bytes(m))

Easy_Crypto

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from Crypto.Util.number import *
from secret import FLAG

m = bytes_to_long(FLAG)


def getpq(nbit):
    p = getPrime(nbit)
    q = getPrime(nbit)
    if p > q:
        return p, q
    else:
        return q, p


p, q = getpq(512)
P = (p - q) & ((1 << 130) - 1)
n = p * q

leak_p = p >> 256

c = pow((1 + P * n), m, n ** 3)

print('n =', n)
print('leak_p =', leak_p)
print("c =", c)

# n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
# leak_p = 115314121469787984258489158421056136177545051135641551928888818017665807264468
# c = 1836794759996264077871820946090708779709415760553736759453665641907562256633157424959089180650539327925671892742819931875681606982615287882656254828326465758462357812873839261469783652663796071814218493268788421243190729887313099383264588659922912876424206670310928514588754069909128149471326084547056385690037197908766053620702238356084124023146075698878494434053246157524775269473152458661801907641122308756667762880284617915774590075511686821816948174618196839335059944389423693187930672934293905608970421003536691336581450927887931599275461176935079227494931457562345640133982771901848553204154760760399724074615092290799119053032875792219794072963200108352944441876206386518960615891547166767499506114294860833404421893612197040731184031783165365621722947731966143226777081983415797778111715332055871302609049501876860012070502369090417942239749695034267695710324328867728296996779

p的高位已经给出，很自然联想到可以p高位泄露攻击，但只给了刚好256位，可能不太够，得爆破几位

n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
pbits = 512
for i in range(0,256):
    p4 = 0xfef17ad62b2573f0f1fd707b2f273922860034731234b9ba82fc303b7c4faad400
    p4 = p4 + i
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    roots = f.small_roots(X=2^kbits,beta=0.4,epsilon=0.01)
    if roots:
        p= p4 + int(roots[0])
        print ("n",n)
        print ("p",p)
        print ("q",n/p)

得到p，q
回过头看m加密
可以发现$c \equiv (1+P*n)^{m}\ (mod\ n^{3})$
通过二次项展开可以得到$c \equiv (1+P*n*m)+C_{m}^{2}{P}^{2}{n}^{2}\ (mod\ n^{3})$
转移到$mod\ n^{2}$下得到
$c \equiv (1+P*n*m)\ (mod\ n^{2})$
这样我们便可以通过c，P，n得到m
exp：

from Crypto.Util.number import *
q = 10120465347855011176216116854406657716210971137988515839650722657457130494685812171761795141588424375299868315964294503826721743852498238577704636503052409
p = 13352463043552409670211183534740157814546713901105410408023687926498813469217507846107364405269402732967687839808637375591530105677153038557366731161035343
c = 1836794759996264077871820946090708779709415760553736759453665641907562256633157424959089180650539327925671892742819931875681606982615287882656254828326465758462357812873839261469783652663796071814218493268788421243190729887313099383264588659922912876424206670310928514588754069909128149471326084547056385690037197908766053620702238356084124023146075698878494434053246157524775269473152458661801907641122308756667762880284617915774590075511686821816948174618196839335059944389423693187930672934293905608970421003536691336581450927887931599275461176935079227494931457562345640133982771901848553204154760760399724074615092290799119053032875792219794072963200108352944441876206386518960615891547166767499506114294860833404421893612197040731184031783165365621722947731966143226777081983415797778111715332055871302609049501876860012070502369090417942239749695034267695710324328867728296996779
n = 135133139540786818977969958456509467902948924003478556140490841984247464940261764739984274397650928404945721248284577232814352745333641188749824519153271662051302477973525156608141358709265683759057060630360909926255299541198485901065352661702656282587105799982740927802530997159098015074633017964344230291287
s = n * n
P = (p - q) & ((1 << 130) - 1)
g = P * n
c = c % s - 1
c = c // g
print(long_to_bytes(c))

- Read More -