太菜了太菜了太菜了, 虽然说跑出去玩了两天, 但还是花了半天时间做的, 一道Coppersmith’s short-pad attack没有想到调$\beta$, 做了半天都没出来, 属实拉了. 最后也就做了个改表的base64….算是除了签到就没出吧(还有道古典不想查了5555

0x00 Real_Base

problem

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
#py2
import string
import random
from secret import flag,b_char

def encode(s):
res=''
binstr=[ bin(ord(s[i])).replace('0b','').zfill(8) for i in range(len(s))]
p1=len(binstr) // 3
p2=len(binstr) % 3
part1 = binstr[0:3*p1]

for i in range(p1):
str_p1=binstr[i*3]+binstr[i*3+1]+binstr[i*3+2]
tmp_str = [str_p1[x: x + 6] for x in [0, 6, 12, 18]]
tmp_res = [b_char[int(x,2)]for x in tmp_str]
res+=''.join(tmp_res)

if p2:
part2 = binstr[3*p1:]
str_p2 = ''.join(part2)+(3-p2)*'0'*8
tmp_str = [str_p2[x: x + 6] for x in [0, 6, 12, 18]][:p2+1]
tmp_res = [b_char[int(x,2)]for x in tmp_str]
res+=''.join(tmp_res)
res +='='*(3-p2)
return res

m1=random.sample(list(b_char),50)
print ''.join(m1)
print encode(m1)
print encode(flag)
# rTcb1BR8YVW2EOUjweXpIiLt5QCNg7ZAsD9muq3ylMhvofnx/P
# 2Br9y9fcu97zvB2OruZv0D3Bwhbj0uNQnvfdtC2TwAfPrdBJ3xeP4wNn0hzLzCVUlRa=
# tCvM4R3TzvZ7nhjBxSiNyxmP28e7qCjVxQn91SRM3gBKzxQ=

看了一下整个过程, 就是个base64, 但是表未知, 直接通过一对明文和密文回推表, 得出部分表基本上就能猜出整个表了, 直接用改过的表解码就行了.

exp

当时做的时候的脚本不见了5555555

0x01 你们一天天的不写代码, 难道是在等待爱情

古典大混合, 什么银河字母, 古精灵…..不找了

0x02 ChildRSA

problem

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
#childrsa.py
from Crypto.Util.number import *
from gmpy2 import iroot
from os import *
from secret import flag1,flag2,padding1,padding2
assert len(flag1)==20
assert len(flag1)>len(flag2)
assert len(flag2)==len(padding2)
def init1():
m=(padding1*2**200+bytes_to_long(flag1))*2**200
r1=getPrime(170)
r2=getPrime(170)
p=getPrime(1024)
q=getPrime(1024)
N=p*q

return m,r1,r2,N

def enc1(m,r1,r2,N):
c1=pow(m+r1,3,N)
c2=pow(m+r2,3,N)
return c1,c2

def init2():
prefix = 2**1000
r3 = prefix+flag2*2**200
r4 = 2*prefix+padding2*2**200
return r3,r4

def enc2(r3,r4):
c3 = pow(r3*r4,3)
return c3

(m,r1,r2,N) = init1()
(c1,c2)=enc1(m,r1,r2,N)
(r3,r4) = init2()
c3 = enc2(r3,r4)
print N
print(c1,c2,c3)

# output.txt
N= ...
(c1,c2,c3)= ...

就是这道题做了半天都没出来, 当时试了好久的Coppersmith’s short-pad attack(后面简写为Csp atk, 连$\epsilon$都从0.01遍历到1了, 依旧没有出结果, 看了官方wp, WTF??? $\beta$调成1???, 为什么?

抱着这个问题我又重新翻了一下Sagemath文档, 找到了small_roots()的解释:

sage.rings.polynomial.polynomial_modn_dense_ntl.small_roots(self, X=None, beta=1.0, epsilon=None, **kwds)

​ Let $N$ be the characteristic of the base ring this polynomial is defined over: N = self.base_ring().characteristic(). This method returns small roots of this polynomial modulo some factor $b$ of $N$ with the constraint that $b>=N^β$. Small in this context means that if $x$ is a root of $f$ modulo $b$ then $|x|<X$. This $X$ is either provided by the user or the maximum $X$ is chosen such that this algorithm terminates in polynomial time. If $X$ is chosen automatically it is $X=ceil(1/2N^{β^2/δ−ϵ})$. The algorithm may also return some roots which are larger than X. This algorithm in this context means Coppersmith’s algorithm for finding small roots using the LLL algorithm. The implementation of this algorithm follows Alexander May’s PhD thesis referenced below.

INPUT:

  • X – an absolute bound for the root (default: see above)
  • beta – compute a root mod $b$ where $b$ is a factor of N and $b ≥N^β.$ ( Default: 1.0, so $b=N$. )
  • epsilon – the parameter $ϵ$ described above. (Default: $β/8$)
  • **kwds – passed through to method Matrix_integer_dense.LLL().

REFERENCES:

Don Coppersmith. Finding a small root of a univariate modular equation. In Advances in Cryptology, EuroCrypt 1996, volume 1070 of Lecture Notes in Computer Science, p. 155–165. Springer, 1996. http://cr.yp.to/bib/2001/coppersmith.pdf

Alexander May. New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn, 2003. http://www.cs.uni-paderborn.de/uploads/tx_sibibtex/bp.pdf

文档里面给出了small_roots()使用的算法的paper, 有时间好好看一下.
这个函数需要注意的有三个参数X,beta,epsilon, 其中betaepsilon也就是$\beta$和$ \epsilon$ .

来看看这三个参数都该怎么填

  • $X$: 这个算是最好填的, 可以理解成smallroot的上界, 一般来说题目中给出了要解的小根的位数kbits就设置$X = 2^{kbits}$. 而在Csp atk中, 理论可解上界是$N.nbits \over e^2$
  • $\beta$: 这个$\beta$可以理解成$N$的因子的下界, 对于常规RSA中的$N$, 一般就只有$1,N,p,q$四个因子, 我们可以选取$N,p,q$作为算法使用的因子, 所以其实$\beta$可以从0取到1, 因为都可能成立, 但真正用的时候一般取$[0.4,0.6] \cup {1}$.
  • $\epsilon$: 神奇的参数, 不填就是$\beta \over 8$, 文档中给出了一个关系式$X=ceil(1/2N^{β^2/δ−ϵ})$, 其实这个$ceil$可以暂时忽略掉, 所以就有$2X=N^{\beta^2/\delta-\epsilon}$, 文档里并没有给出$\delta$ 到底该如何取, 但从这题的官方wp中是给出了$\delta = e^2$, 其实就是多项式的次数. 所以对于Csp atk来说, $\epsilon = \beta^{2} / e^2 - x$, $x$的取法为$N^x = X.nbits $

所以说,$\beta$填1也是阔以的! 因为factor里面是有$N$的!

按着上面的分析, 把从La佬那边拿来的Csp atk的板子稍微修改一下( 以后就用改进过的板子了嘿嘿嘿….

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
44
45
46
47
def short_pad_attack(c1, c2, e, n , kbits = 0):
if kbits == 0 :
kbits = n.nbits()//(e*e)
PRxy.<x,y> = PolynomialRing(Zmod(n))
PRx.<xn> = PolynomialRing(Zmod(n))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+y)^e - c2
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)
h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()
x = ceil(n.nbits() // kbits)
for b in [0.4,0.5,0.6,1]:
eps = (b^2) / (e^2) - (1/x)
print(eps)
if eps <= 0:
eps = b / 8
print('[+] try beta={} epsilon={}'.format(float(b),float(eps)))
diff = h.small_roots(X=2^kbits, beta=b,epsilon=eps)
if len(diff) > 0 :
print('[+] find diff with beta={} and epsilon={}'.format(b,eps))
return diff

print('[-] can not find the diff')
return diff

def related_message_attack(c1, c2, diff, e, n):
PRx.<x> = PolynomialRing(Zmod(n))
g1 = x^e - c1
g2 = (x+diff)^e - c2
def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]

from Crypto.Util.number import long_to_bytes as l2b
n = ...
(c1,c2,c3)= ...
e= 3
diff = short_pad_attack(c1,c2,e,n,kbits=170)[0]
res = related_message_attack(c1,c2,diff,e,n)
l2b(res)
# b'\xd4!I\x80M\xf0\x80\\\xd9>\x19\xad\xdd^\x1d$\x99\xc1V\xc9/+\xdc\x97"\xb3 \x03\xef3\xd1\xea\x04\xf4\x81z$\xd2]{\xcb\xc4\x93\xe7\xf6\xb7\x9a\xb2\xe6a\x9fl\x99\xady\xa8\x9e\xa2\xf5\'\xa2\xfc\xe0Z\xa1\x1c\x15\rQ\x7fM\x99T\x93\x04\xc5\xdd\xdc\x80\xe4\x0f\x85)\x9f\xc3p\xdc\x03j.\x87kU\'Ud\x0bD")\x00\x00\x00\x00\x00Nep{Nep_n3p_ba4_bad_\x00\x00\x00\x03\tx@Q2\x1b3\x1f\r\xb2\x95\x86?kE\x1f\xe6\xaay\xf1\xe5'

可以看到flag已经出来一部分了Nep{Nep_n3p_ba4_bad_

来看看怎么求flag2, 先把给的条件写出来, 我们记$flag_2 = f , padding = pd$
$$
r_3 = 2^{1000}+ 2^{200}f \\
r_4 = 2^{1001}+ 2^{200}pd \\
(r_3r_4)^3 = c_3
$$
官方wp上面说想考一下二元的Coopersmith, 先放着, 有空了学习一波. 这题还可以直接解一元二次方程直接出

解方程解法

我们可以直接通过开三次方得出$r_3r_4 = R$
咱们先联立一下$r3,r4$的两个式子
$$
2^{2001} + 2^{1200}pd +2^{1201}f+ 2^{400} pd \cdot f = r_{34} \tag1
$$
这里要注意一下, $pd,f \le 2^{160}$, 也就是说$2^{400} pd \cdot f < 2^{1200}$所以其实咱们可以直接有
$$
2^{2001} + 2^{1200}pd +2^{1201}f+ 2^{400} pd \cdot f \equiv 2^{400}pd \cdot f \equiv r_{34} \mod 2^{1200} \\
2^{400}pd \cdot f = r_{34} % \ 2^{1200}
$$
这样我们就能求出$pd \cdot f = a$了, 然后我们直接$(1)$式两边同时乘$f$, 把$pd \cdot f$带入, 就可以构造出一个关于$f$的一元二次方程了.
$$
2^{2001} \cdot f + 2^{1200} a +2^{1201}f^2+ 2^{400} a \cdot f = r_{34} \cdot f
$$
解出$f$发现…是假flag, md我算了那么久居然是个假的??? 突然想到会不会padding2才是真正的flag, 又把padding2算出来了, 果然….padding2才是真flag

exp

1
2
3
4
5
6
7
8
c = int(c3.nth_root(3) % (2^2001))
pdf = int(c %2^1200 // 2^400)
x = var('x')
f = 2^1200 * pdf - c * x + 2^1201 * x^2 + 2^400 * x * pdf
flag2 = int(f.roots()[0][0])
padding = pdf // flag2
l2b(padding)
# b'1_l0v3_9ou}'

所以最后的flag就是Nep{Nep_n3p_ba4_bad_1_l0v3_9ou}

0x03 easyEncryption

暂时还没时间, 有空看看

0x04 lowExponent

暂时还没时间, 有空看看