Article directory
-
- ezRSA
- CB backpack
I didn’t take part in the competition this time. I remembered the time wrongly. I took a look and found that if I tried it, I would probably only be able to solve those two simple questions. I’m still too good at it.
EzRSA
Topic description:
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 = 656340944309270807322561648088332335637326286541603890429776896285125271682568993106622390096105127720205032838425881424 53533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554 634493581962527475555869292091755676130810562421465063412235309
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802 94081085180610443030619593117990209818019916794564952623561363616336267277729896894331921632594950304537710023518170696484640 8396946496139224344270391027205106691880999410424150216806861393
(e1, noise1, c1) = (1743, 4456058807577385361282022743643993751419568073421443194844119034787827418493795238178530283754120270521268 77005211293856327762415376692080887777293553498332154430484663165171107785025082094337926034201587867723392333975836375700062 55153020675167597396958251208681121668808253767520416175569161674463861719776, 6564300935419807518258776655052110706314034098 34338528215808029837360942250364973356074001974796232089153797226469553298556816015512827888546443599679095703602515507669700 54185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853 621152905983)
(e2, noise2, c2) = (1325, 3528200659981374414072126287529239588755856151775972146729178969645942670260039717265562476528153116722178 70360095078334251450712657394867359936314601896297095914560170926610288399513922476016284686215761000357004378921644354240350 04463142959219067199451575338270613300215815894328788753564798153516122567683, 5032763209077818375954475522671011070204685088 02994882597396725420259164221190651798222108846222259453764658020694647823112110312630465931457337015913719503497357095531052 17501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773 715759733714)
c = 1243497629934245316974032993509442077255772909921899483888241249860662695142043138889803210886294624720886310523291280428 37153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177 197863522573410860341245613331398610013697803459403446614221369
'''
Topic analysis:
gen_q:
When you see jacobi(2,n1), you know that it is the knowledge of quadratic remainder.
c
=
(
2
?
a
2
)
e
,when
P
%
2
=
0
c
=
(
2
?
a
)
2
?
e
,when
P
%
2
=
1
c
(
n
1
?
1
)
/
/
2
≡
(
2
?
a
2
)
e
?
(
n
1
?
1
)
/
/
2
≡
?
1
?
1
m
o
d
n
1
①
c
(
n
1
?
1
)
/
/
2
≡
(
2
?
a
)
2
?
e
?
(
n
1
?
1
)
/
/
2
≡
(
2
?
a
)
e
?
(
n
1
?
1
)
≡
1
m
o
d
n
1
②
?
j
a
c
o
b
i
(
e
n
c
i
,
n
1
)
=
?
1
,
p
=
0
+
p
c = (2 * a^2)^e, when P \% 2 = 0\ c = (2 * a)^{2*e}, when P \% 2 = 1\ c^{(n1 – 1) // 2} \equiv (2 * a^2)^{e *(n1 – 1) //2} \equiv -1 * 1 \mod n1 ①\\ \c^{(n1 – 1)//2} \equiv (2*a)^{2*e*(n1 – 1)//2} \equiv(2 * a)^{e * (n1 – 1)} \equiv 1 \mod n1②\ \Rightarrow jacobi(enc_i,n1) = -1,p = 0 + p\
c=(2?a2)e, when P%2=0c=(2?a)2?e, when P%2=1c(n1?1)//2≡(2?a2)e?(n1? 1)//2≡?1?1modn1①c(n1?1)//2≡(2?a)2?e?(n1?1)//2≡(2?a)e?(n1?1)≡ 1modn1②?jacobi(enci?,n1)=?1,p=0 + p
gen_q:
Related news Attacks can be solved directly
exp:
import binascii
import libnum
from gmpy2 import *
from Crypto.Util.number import *
n1 = 656340944309270807322561648088332335637326286541603890429776896285125271682568993106622390096105127720205032838425881424 53533499954947692968978190310627721338357432052800695091789711809256924541784954080619073213358228083200846540676931341013554 634493581962527475555869292091755676130810562421465063412235309
(e1, noise1, c1) = (1743, 4456058807577385361282022743643993751419568073421443194844119034787827418493795238178530283754120270521268 77005211293856327762415376692080887777293553498332154430484663165171107785025082094337926034201587867723392333975836375700062 55153020675167597396958251208681121668808253767520416175569161674463861719776, 6564300935419807518258776655052110706314034098 34338528215808029837360942250364973356074001974796232089153797226469553298556816015512827888546443599679095703602515507669700 54185510197999091645907461580987639650262519866292285164258262387411847857812391136042309550813795587776534035784065962779853 621152905983)
(e2, noise2, c2) = (1325, 3528200659981374414072126287529239588755856151775972146729178969645942670260039717265562476528153116722178 70360095078334251450712657394867359936314601896297095914560170926610288399513922476016284686215761000357004378921644354240350 04463142959219067199451575338270613300215815894328788753564798153516122567683, 5032763209077818375954475522671011070204685088 02994882597396725420259164221190651798222108846222259453764658020694647823112110312630465931457337015913719503497357095531052 17501410716570601397725812709771348772095131473415552527749452347866778401205442409443726952960806789526845194216490544108773 715759733714)
c = 1243497629934245316974032993509442077255772909921899483888241249860662695142043138889803210886294624720886310523291280428 37153718129149149661961926557818023704330462282009415874674794190206220980118413541269327644472633791532767765585035518183177 197863522573410860341245613331398610013697803459403446614221369
n2 = 103670293685965841863872863719573676572683187403862749665555450164387906552249974071743238931253290278574192713467491802 94081085180610443030619593117990209818019916794564952623561363616336267277729896894331921632594950304537710023518170696484640 8396946496139224344270391027205106691880999410424150216806861393
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 = 131893379056413212573721884363538444182807452848754623570196687081675470269606418695132832186726777125903263476014241085 28959315675307896082223561007980457
p = 9473204278465588641589315677772678997836862033858760337441231265335880892205102590571357305720744128962068300763212493598 006400853597404586755248901932203
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!}
CB backpack
Topic description:
from random import shuffle
def gen_e():
e = []
for i in range(8):
ee = [0]*3 + [1]*3
shuffle(ee)
e + = ee
return e
e = gen_e()
nbit = len(e) # 48
flag = 'DASCTF{' + sha256(''.join([str(i) for i in e]).encode()).hexdigest() + '}'
a = [randint(1,2^nbit) for i in range(nbit)]
re = 0
for i in range(nbit):
re + = e[i]*a[i]
print(a)
print(re)
Topic analysis:
When I first saw it, it felt very familiar. Isn’t this a proper backpack encryption? The result. . . I want it to be simple
It also involves knowledge blind spots. I followed the big guy’s wp and did it again, and learned a lot.
In general, the data provided is not large enough, so it cannot be solved directly using the backpack grid. You need to blast a few numbers and test whether the density is up to standard through jsdn (d < 0.9408).
After testing it, we have to blast more than 10 digits to get the result. Although blasting 8 digits satisfies d < 0.9408, we really can’t get the result.
In this case, I will blast 12 bits.
from math import *
n=36
a = [65651991706497, 247831871690373, 120247087605020, 236854536567393, 38795708921144, 256334857906663, 120089773523233, 1653 49388120302, 123968326805899, 79638234559694, 259559389823590, 256776519514651, 107733244474073, 216508566448440, 39327578905 705 5254513808, 221802659519968 , 169686619990988, 23128789035141, 208847144870760, 272339624469135, 269511404473473, 112830627321371, 73203551744776, 4284 3503010671, 118193938825623, 49625220390324, 230439888723036, 241486656550572, 107149406378865, 233503862264755, 269502011971 514.181805192674559. 1190147709444, 124498742419309]
a = a[12:]
d = n / log2(max(a))
N = ceil(1 / 2 * sqrt(n))
assert d < 0.9408, f"Density should be less than 0.9408 but was {<!-- -->d}."
print(d) # 0.7507444846333444
In order to save time, here is the reverse order. It will come out very quickly in 1 minute.
from tqdm import tqdm
a=[65651991706497, 247831871690373, 120247087605020, 236854536567393, 38795708921144, 256334857906663, 120089773523233, 1653 49388120302, 123968326805899, 79638234559694, 259559389823590, 256776519514651, 107733244474073, 216508566448440, 39327578905 705 5254513808, 221802659519968 , 169686619990988, 23128789035141, 208847144870760, 272339624469135, 269511404473473, 112830627321371, 73203551744776, 4284 3503010671, 118193938825623, 49625220390324, 230439888723036, 241486656550572, 107149406378865, 233503862264755, 269502011971 514.181805192674559. 1190147709444, 124498742419309]
re=4051501228761632
A = a[12:]
bits=36
def ju(j):
for i in j:
if abs(i)!=1:
return 0
return 1
for i in tqdm(range(2^12,1,-1)):
temp=[int(j) for j in bin(i)[2:].zfill(12)]
t1,t2=temp[:6],temp[6:12]
if sum(t1)!=3 or sum(t2)!=3:
continue
rr = sum([i*j for i,j in zip(temp,a[:12])])
new_re = re-rr
M=Matrix(ZZ,bits + 1)
for i in range(bits):
M[i,i]=2
M[i,-1]=A[i]
for i in range(bits):
M[-1,i]=1
M[-1,-1]=new_re
res=M.LLL()
if ju(res[0][:-1]):
print('find')
print(temp)
print(res[0])
break
Another idea mentioned in the comments is also the idea given to the master who linked
structure:
M
=
(
1
a
1
1
1
a
2
1
?
?
?
1
a
48
1
r
e
twenty four
)
M = \begin{pmatrix} 1 & amp; & amp; & amp; & amp; & amp;a_1 & amp;1\ & amp;1 & amp; & amp; & amp; & amp;a_2 & amp;1\ & amp; & amp;\ddots & amp; & amp; & amp;\vdots & amp;\vdots\ & amp; & amp; & amp;1 & amp; & amp;a_{48} & amp;1\ & amp; & amp; & amp; & amp; & amp;re & amp;24 \end{pmatrix}
M=
(
e
1
,
e
2
,
.
.
.
,
e
48
,
?
1
,
?
1
)
?
M
=
(
e
1
,
e
2
,
.
.
.
,
e
48
,
0
,
0
)
(e_1,e_2,…,e_{48},-1,-1) * M = (e_1,e_2,…,e_{48},0,0)
(e1?,e2?,…,e48?,?1,?1)?M=(e1?,e2?,…,e48?,0,0)
So the key is the string ee = [0]*3 + [1]*3. I didn’t think about dealing with it. I didn’t consider it well.
You can check out the official wp
CB ezDHKE
This question is very common and very simple, so I won’t go into it.
CB curve
CB cipher
Let’s repeat these two questions when we have time.
Learned backpack grid blasting