*CTF 2022 crypto

发表于 更新于 分类于

ezRSA

方法1

p,q的900位以后的高位hb都是一样的，可以先求出来

设\(p=hb+y\)，那么\(q=hb+2^{900}-y+z\)，z为300位的随机数，可以得到 \[ p+q=2hb+2^{900}+z,\ p-q=2y-2^{900}-z \] 因为\(n=pq\)，\(p+q\)的高位（低300位未知）已知，可以由\(p-q=\sqrt{(p+q)^2-4n}\)求出\(p-q\)的近似值相应的y的近似值也能求出，再用coppersmith求出y的低位从而求出p 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
import gmpy2
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

prefix=gmpy2.iroot(n,2)[0]
prefix=(prefix>>900)<<900
hb=gmpy2.iroot(n,2)[0]
hb=(hb>>900)<<900
paq=2*hb+2**900

psq=gmpy2.iroot(paq**2-4*n,2)[0]
y=(psq+2**900)//2
p=hb+y
print(p)
# 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371506437683672869879650195774368524468044540434185235653504063937932618450991608706715382905688880285112977572901480973791888259637

1
2
3
4
5
6
7
8
9
10
11
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
p_=170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371506437683672869879650195774368524468044540434185235653504063937932618450991608706715382905688880285112977572901480973791888259637


PR.<x>=PolynomialRing(Zmod(n))

f=p_+x
a=f.small_roots(X=2^450,beta=0.4)[0]
p=p_+a
print(p)
# 170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371527964357773254659131885022323526864655742577256932209187678896131068422973326545184343697783650940422950445390573562429093050687
1
2
3
4
p=170966211863977623201944075700366958395158791305775637137148430402719914596268969449870561801896130406088025694634815584789789278534177858182071449441084789053688828370314062664371527964357773254659131885022323526864655742577256932209187678896131068422973326545184343697783650940422950445390573562429093050687
q=n//p
d=inverse(0x10001,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

方法2

其实都差不多

\(p+q\)可以表示为\(p+\frac{n}{p}=q+\frac{n}{q}=2hb+2^{900}+z\)

忽略z，有\(p+\frac{n}{p}=q+\frac{n}{q}\approx2hb+2^{900}\)

可以直接把p,q的近似值求出来

这里用二分法逼近min{p,q}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
import gmpy2
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

hb=gmpy2.iroot(n,2)[0]
hb=(hb>>900)<<900
paq=2*hb+2**900

l=1
r=int(gmpy2.iroot(n,2)[0])

while abs(r-l)>1:
    m=(r+l)//2
    x=m+n//m
    if x>paq:
        l=m
    else:
        r=m

print(r)

之后把r替换成方法1的p_继续做就行了

Inverseproblem2

LLL算法，非最小向量，但在LLL求出的基里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import numpy as np
L=[]

A=np.loadtxt(r'C:\Users\Administrator\Desktop\A.txt')
A=A*10**18


b=np.loadtxt(r'C:\Users\Administrator\Desktop\b.txt')

b=b*10**18

a=np.vstack([A.T,b])
Lm=np.hstack([a,np.identity(51)])


for row in Lm:
    L.append([int(i) for i in row])
print(L)
1
2
3
4
5
6
7
8
9
L=matrix(ZZ,L)
r=L.LLL()
for i in r:
    if abs(i[-1])==1:
        s=i[50:]*(-i[-1])
        
for i in s:
    if 0<i<128:
        print(chr(i),end='')