三顺七的笔记
0%

2023-0xGAME-Crypto-WP

发表于 更新于 分类于 Valine：

0xGame2023 Crypto WP

题目在这里→题目地址

第一周：

觅码：

考点：

  • python编程
  • 编码原理

碎碎念：这题的本意是想让大家熟悉一下python的语法，了解信息是如何编码成为一串数字，并进行一系列数学运算操作的，中文flag属实是有点抽象。这道题应该算是本周的签到题，但是解出的人数不太符合预期，在这里给大伙道歉了。该给出的函数都给出了，那么都配置好环境了，接下来的题目应该会顺利多了。

一些小坑：中文编码，因为c1,c2,c3,c4之间可能会有一些比特是连着的构成中文字符，所以单解出部分密文是无法直接decode的。考虑到这点，每串字符里面都有一些英文字符，告诉做题的师傅解出来的是正确的。

小知识：在python中的几个常用的数字表示类型有：

  • 十六进制(0x)开头数字
  • 八进制(0o)开头数字
  • 二进制(0b)开头数字
  • 十进制无特殊开头

在python中，用(b’)做开头的表示bytes类型的数据，一个bytes大小为8bit。

几个常用的函数解释：

1
2
3
4
5
6
7
8
9
10
from gmpy2 import iroot #引入函数库，用来开根用的，gmpy2里面有很多比较好用的密码算法可以使用，推荐使用。

long_to_bytes()#将数字类型的数据转换为bytes类型的数据，一个bytes占据8bit大小，那么0-256的一个数字，就可以表示一个bytes，因为在十进制下这个数字不太好直接书写表示，一般我们用十六进制去表示一个bytes，例如ascii码为65的字母'A'，表示为0x41，比特流b'AAA'表示的十六进制数就是0x414141。
bytes_to_long()#为上一个函数的逆操作。

encode()#将字符串编码成bytes数据，即：'0xGame'->b'0xGame'。
decode()#上一个函数的逆操作。

b64encode()#base64编码操作，作用和encode类似，但是由于算法的原因，其可以将不可打印字符编码成打印字符，具体算法流程可以参考“猜谜”，这道题的编码函数。
b64decode()#解base64编码。

有了上述这些工具基本就能解题了，题目给了三个数字，一个base64编码后的比特流，直接将相应的数字按照python识别数字的办法还原回去，然后long_to_bytes就完了。（不学会编码，接下来学习密码的路咋走嘛？）

exp:

1
2
3
4
5
6
7
8
9
10
11
12
from gmpy2 import iroot
from Crypto.Util.number import *
from base64 import b64decode
c1 = 2607076237872456265701394408859286660368327415582106508683648834772020887801353062171214554351749058553609022833985773083200356284531601339221590756213276590896143894954053902973407638214851164171968630602313844022016135428560081844499356672695981757804756591891049233334352061975924028218309004551
c2 = 10010000100001101110100010100111101000111110010010111010100001101110010010111111101000011110011010000001101011111110011010011000101011111110010110100110100000101110010010111101100101011110011110111100
c3 = b'lueggeeahO+8jOmCo+S5iOW8gOWni+aIkQ=='
c4 = 'e4bbace79a8443727970746fe68c91e68898e590a72121217d'

flag = (long_to_bytes(iroot(c1,5)[0])+long_to_bytes(eval('0b'+str(c2)))+b64decode(c3)+long_to_bytes(eval('0x'+str(c4)))).decode()
print(flag)
#0xGame{ 恭喜你,已经理解了信息是如何编码的，那么开始我们的Crypto挑战吧!!!}

RSA：

考点：

  • RSA的基本概念
  • 欧拉函数定义
  • 逆元的运算与定义
  • 基本分解模数的工具应用

碎碎念：出的是有点杂，基本入门需要掌握的知识都含括在里面了，对初次接触密码领域的新朋友有点小坑。我们可以通过这题知道：逆元可以代替除法在有限域（某个模数下的式子）中进行运算，同时逆元不是百分百存在的（必须与模数互质）。所以题目中的逆元不能直接求出，这是这题的一个小坑。

虽然这个坑不太符合预期，大伙都能直接除以解出来就是了，就当做下降难度了，，，

思路：RSA概念网上已经很多了，应该也不是特别难懂，比较令新人烦恼的可能是(mod)这个概念，就是取余这个操作，慢慢适应就好了。这道题用yafu.exe，还是用factordb网站，或者是自己随便写写就能分解模数，拿到欧拉函数直接解逆元了，得到flag了。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *
n = 93099494899964317992000886585964221136368777219322402558083737546844067074234332564205970300159140111778084916162471993849233358306940868232157447540597
e = 65537
c = 54352122428332145724828674757308827564883974087400720449151348825082737474080849774814293027988784740602148317713402758353653028988960687525211635107801
mask=54257528450885974256117108479579183871895740052660152544049844968621224899247
fact=[2329990801,2436711469,2732757047,2770441151,2821163021,2864469667,2995527113,3111632101,3162958289,3267547559,3281340371,3479527847,3561068417,3978177241,4134768233,4160088337]
phi = 1
for i in fact:
    phi *= i-1
d = inverse(e,phi)
c =pow(c,d,n)
#这是在mask*m > n情况下的解法，虽然我看大伙直接除以就可以得到原文了，权当一种思路去应对以后见到的情况吧，，
mask_inv=(inverse(mask//GCD(mask,n),n)) 
c = c*mask_inv%n
m = long_to_bytes(c//GCD(mask,n))
print(m)
#b'0xGame{Magic_M@th_Make_Crypt0}'

Take my bag

考点：

  • 逆元的运用
  • 超递增数列
  • 加密算法至数学式子的推导

碎碎念：这题主要是背包密码，这里给出数学公式

m=i_{n}i_{n-1}i_{n-2}······i_2i_1(i_k\in{1,0})\ 加密公式：\sum{3^{i_n}}*w=c(modn)

解密逻辑：w已经给出，那么就很自然的可以考虑到用逆元做除法化简式子得到：

c*w{-1}=\sum{3{m_{i_n}}}ww{-1}=\sum{3{m_{i}}}(modn)

接下来通过尝试我们可以知道：

n>\sum{3^n}\ 且有3{n+1}>\sum{3n}>3^{n-1}

那么问题就很简单了，可能只需要对贪心算法有一点点了解，就可以直接写脚本了（如果对你来说贪心算法可能一时半会有点难以理解，或是没接触编程，不要紧，权当学习编程思想也是不错的选择。）

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *

w=16221818045491479713
n=9702074289348763131102174377899883904548584105641045150269763589431293826913348632496775173099776917930517270317586740686008539085898910110442820776001061
c=4795969289572314590787467990865205548430190921556722879891721107719262822789483863742356553249935437004378475661668768893462652103739250038700528111
c = c*inverse(w,n)%n

def decrypt(c):
    index = 0
    m = 0
    while pow(3,index)<c:
        index+=1
    for i in range(index-1,-1,-1):
        if ((pow(3,i+1)>c)&(pow(3,i)<=c)):
            c -= pow(3,i)
            m += pow(2,i)
    return m

print(long_to_bytes(decrypt(c)))
#b'0xGame{Welc0me_2_Crypt0_G@me!#$&%}'

CBC:

考点：

  • 对称加密中的分组模式
  • 密钥爆破

碎碎念：关于分组模式存在的原因，还望大家自行通过搜索引擎获取，一般的加密算法都是通过了世人的长久考验而留下来的，要想通过分析并攻破是及其困难的事情，但是由于分组模式不同而存在的某些缺陷却是可以利用的，在进行更深一步的探索之前，我想通过基本的概念题，让大家理解这个分组是怎么操作的、并有哪些好处和缺陷。关于解密脚本的编写入门，可能对新人不是那么友好，但是通过观察流程图可以发现，很多操作只要看懂了是可以硬抄的，就没啥太大的难度了，那么这题给出两种解法。

exp1:

可以观察得到，密钥空间并不是很大，可以通过穷举爆破的办法一个个尝试得到，接下来写出基本的CBC解密脚本就可以。

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
from Crypto.Util.number import *

def bytes_xor(a,b):
    a,b=bytes_to_long(a),bytes_to_long(b)
    return long_to_bytes(a^b)

def decrypt(text,key):
    result = b''
    for i in text:
        result += ((i^key)).to_bytes(1,'big')
    return result

def CBCinv(enc,iv,key):
    result = b''
    block=[enc[_*8:(_+1)*8] for _ in range(len(enc)//8)]
    for i in block:
        temp = decrypt(i,key)
        tmp = bytes_xor(iv,temp)
        iv = i
        result += tmp
    return result

iv = b'11111111'
enc = enc = b"\x8e\xc6\xf9\xdf\xd3\xdb\xc5\x8e8q\x10f>7.5\x81\xcc\xae\x8d\x82\x8f\x92\xd9o'D6h8.d\xd6\x9a\xfc\xdb\xd3\xd1\x97\x96Q\x1d{\\TV\x10\x11"
for key in range(0xff):
    dec = (CBCinv(enc,iv,key))
    if b'0xGame' in dec:
        print(dec)
#b'0xGame{098f6bcd4621d373cade4e832627b4f6}\x08\x08\x08\x08\x08\x08\x08\x08'
#后面的填充部分就懒得去掉了，，

exp2:

因为已知明文、密钥固定的特点，这里利用了CBC分组模式的特点可以直接逆推出密钥，在这里给出这种解法，目的是让新师傅了解一下利用已知明文解密的这种思想。

1
2
3
4
5
6
7
8
iv = b'11111111'
enc = b"\x8e\xc6\xf9\xdf\xd3\xdb\xc5\x8e8q\x10f>7.5\x81\xcc\xae\x8d\x82\x8f\x92\xd9o'D6h8.d\xd6\x9a\xfc\xdb\xd3\xd1\x97\x96Q\x1d{\\TV\x10\x11"
test = b'0xGame'
key = (iv[0]^test[0]^enc[0])

dec = CBCinv(enc,iv,key)
print(dec)
#b'0xGame{098f6bcd4621d373cade4e832627b4f6}\x08\x08\x08\x08\x08\x08\x08\x08'

猜谜：

考点：

  • 已知明文攻击
  • base64编码算法

碎碎念：考虑到难度，当天还是放出了魔改base64解码函数，通过编码可以将不可打印字符转换成可打印字符(A-Z\a-z\0-9\+)，以便于在网络传输中显示，随便写的算法就看个乐呵就行。重点是已知明文攻击这部分：如果我们知道了部分明文的情况下，可以通过一定的推导得到部分密钥的信息、甚至是密钥，这在密码学中是一个重要的攻击思想。

在这里我们可以知道，一般的正常加解密算法是难以攻破的，如果我们能在现实中通过侧信道攻击，获取了某些关键的信息呢？

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
from Crypto.Util.number import *

def dec(text):
    text = text.decode()
    code = 'AP3IXYxn4DmwqOlT0Q/JbKFecN8isvE6gWrto+yf7M5d2pjBuk1Hh9aCRZGUVzLS'
    unpad = 0
    tmp = ''
    if (text[-1] == '=') & (text[-2:] != '=='):
        text = text[:-1]
        unpad = -1
    if text[-2:] == '==':
        text = text[:-2]
        unpad = -2
    for i in text:
        tmp += str(bin(code.index(i)))[2:].zfill(3)
    tmp = tmp[:unpad]
    result = long_to_bytes(int(tmp,2))
    return result

c = b'IPxYIYPYXPAn3nXX3IXA3YIAPn3xAYnYnPIIPAYYIA3nxxInXAYnIPAIxnXYYYIXIIPAXn3XYXIYAA3AXnx='
enc = dec(c)

mask = b''
kown = b'0xGame{'
for i in range(7):
    mask += (enc[i]^(kown[i]+i)).to_bytes(1,'big')
flag = b''
for i in range(len(enc)):
    flag +=((mask[i%7]^enc[i])-i).to_bytes(1,'big')
print(flag)
#b'0xGame{Kn0wn_pl@intext_Att@ck!}'

维吉尼亚密码

这道古典密码题很简单，有不少师傅甚至直接猜都能猜得出密钥是啥（Game），在目前的CTF赛事中古典密码的题已经很少了。这种传统的加密技术中，就算猜不到密钥是啥，通过统计某些密文和密钥的规律基本都能还原信息。WP就不想写了，，

废话：

确实不可否认的是，第一周我弄得题不是很简单，基本都要沾点python编程，对想入门密码、或者是想尝试CTF的哥们不友好。

但是核心思路都非常简单，而且脚本的编写也不会太复杂（要么可以直接抄题目给的部分代码，要么就是想一下就出来了），因为我并不太想看到新人能够在第一周疯狂上分，然后到后面遇到比较复杂的题就开始放弃了，试着适应可能比较好。

秉持这个态度出题（思路唯一），，相信经过第一周的师傅对密码这个方向有一个初步的认识。那么既然坚持下来了，就开始试着去破译一些好玩的算法吧。

第二周：

中间的那个人

考点：

  • DH算法
  • 简单的爆破

DH算法具体细节和作用，望新师傅们利用搜索引擎了解一下，这里不细谈。这道题比较简单，有些时候面对未知密钥的时候，需要考虑爆破求解，那么这时候就要进行一定的计算量估计，这题不管是求A还是B都是可以出的来的，两者的位数比32位低，也没啥限制，还是可以求的。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
g=2
p=250858685680234165065801734515633434653
Bob=33067794433420687511728239091450927373
Alice=235866450680721760403251513646370485539

x = 3992780394
key = pow(Bob,x,p)
key = sha256(long_to_bytes(key)).digest()
iv = b"0xGame0xGameGAME"
aes = AES.new(key, AES.MODE_CBC, iv)
enc=b's\x04\xbc\x8bT6\x846\xd9\xd6\x83 y\xaah\xde@\xc9\x17\xdc\x04v\x18\xef\xcf\xef\xc5\xfd|\x0e\xca\n\xbd#\x94{\x8e[.\xe8\xe1GU\xfa?\xda\x11w'

flag = aes.decrypt(enc)
print(flag)
#b'0xGame{51393fe1fd5fc2df1bf018d06f0fa11d}\x08\x08\x08\x08\x08\x08\x08\x08'

那么简单的DLP可以通过爆破去求解，但是遇到更加困难的离散对数问题的时候，我们就必须开始考虑是否存在更优的算法去求解这个问题了。

What’s CRT?

考点：

  • 中国剩余定理
  • 对逆元的理解运用
  • 解方程

小彩蛋：公钥260792700是一个QQ号码，因为出题人的Q号拿来做公钥不怎么合适就用小号来玩了。

这题可能是我弄得有点复杂了，因为考虑到第一周逆向题里面大家已经做过解方程的题了，就不直接放出q,p了（本意就是想直接送出q,p,q_,p_的）。

思路：首先解方程

q+p=gift\ q*p=N

用高中知识还是直接用函数库解都可以，我选择用sagemath自带的函数：

1
2
3
4
5
mygift=[15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922, 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098]
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_=84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
var('q p q_ p_')
solve([q+p==gift[0],q*p==n,q_+p_==gift[1],q_*p_==n_],q,p,q_,p_)

拿到因子之后考虑直接求私钥解题，但是可以发现求不出来，原因是：

gcd(e,phi)==4

在上周的题中，我们已经知道只有在e,phi互质的时候才能求出逆元，所以考虑退而求次，求解另外一个逆元：

令e’=\frac{e}{4},求d’ \equiv e’^{-1}(mod\phi(n))\ 得c^{d’} \equiv m^{ed’} \equiv m^{4\frac{e}{4}d’} \equiv m^{4} (modn)\ 但是发现:m{4}>n，m{4}=c^{d’}+kn\ 我们并不能直接开根

此时就需要利用中国剩余定理去将模数进行变换，用来求解以下情况：

\begin{align} \left{ \begin{aligned} x=a_1(modm_1)\ x=a_2(modm_2)\ x=a_3(modm_3)\ x=a_4(modm_4)\ \end{aligned} \right. \end{align}

证明：

proof.png

那么知道公式的情况下，直接按照公式去构造就可以了，需要注意的是不同模数之间必须互质。

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
import gmpy2
from Crypto.Util.number import *
p_=8991690869897246321907509983425307437365288417861457732721314572165773880898701105065818281248373676758405021157703190132511219384704650086565345885727777
q_=9350733807099597101921970461617270659816839029004113803723715480680638784801431578367623576825251918174727017017497634125263419034461866709753181417175321
q = 7687653192574283689842465763299611592007909813801176843577189341409409692975753037402253496632410364594655611337156337669083582400443042348458268161331043
p = 8237763448327424871950828228273863325587732991938648753016149761004918521337676972763871570006722552014080958105888713975090350689060892327170546305946879
e = 260792700
mygift=[15925416640901708561793293991573474917595642805739825596593339102414328214313430010166125066639132916608736569443045051644173933089503934675628814467277922, 18342424676996843423829480445042578097182127446865571536445030052846412665700132683433441858073625594933132038175200824257774638419166516796318527302903098]
mq_=6229615098788722664392369146712291169948485951371133086154028832805750551655072946170332335458186479565263371985534601035559229403357396564568667218817197
mp_=7514598449361191486799480225087938913945061715845128006069296876457814528347371315493644046029376830166983645570092100320566196227210502897068206073043718
n=63329068473206068067147844002844348796575899624395867391964805451897110448983910133293450006821779608031734813916287079551030950968978400757306879502402868643716591624454744334316879241573399993026873598478532467624301968439714860262264449471888606538913071413634346381428901358109273203087030763779091664797
n_=84078907800136966150486965612788894868587998005459927216462899940718213455112139441858657865215211843183780436155474431592540465189966648565764225210091190218976417210291521208716206733270743675534820816685370480170120230334766919110311980614082807421812749491464201740954627794429460268010183163151688591417
c=12623780002384219022772693100787925315981488689172490837413686188416255911213044332780064192900824150269364486747430892667624289724721692959334462348218416297309304391635919115701692314532111050955120844126517392040880404049818026059951326039894605004852370344012563287210613795011783419126458214779488303552
def CRT(r,d):
    M = 1
    l = len(r)
    for i in range(0,l):
        M = d[i] * M
    x = 0
    for i in range(0,l):
        md = M//d[i]
        x = (x + gmpy2.invert(md, d[i])  * md *r[i] )%M
    return int(M+x% M)%M

phi = (q-1)*(p-1)
d = gmpy2.invert(e//4,phi)
m2 = pow(c,d,n)
mq = m2%q
mp = m2%p

m = CRT([mq,mp,mq_,mp_],[q,p,q_,p_])
m = (gmpy2.iroot(m,4))[0]
print(long_to_bytes(m))
#b'0xGame{7881ed67088e9f72b860f8c376599785}'

题后总结，基本解法需要使用到的函数、数学知识在上周都了解过了，剩下的就是一个中国剩余定理的考点，望周知。

以上是预期的解法，下面放出一些非预期解，用SageMath自带的有限域开方的函数nthroot_mod()，也是可以的，还有师傅说能直接phi//4后直接求逆元进行求解也是可以，总之解法蛮多。

有限域开方(同理AMM算法一样是可以的):

1
2
3
4
5
6
7
from sympy.ntheory.residue_ntheory import nthroot_mod
from Crypto.Util.number import long_to_bytes
mq = 5483807329382755718534658156318758332123717229277317863013790997411503349042875734915035632700621630439238266035050249716944006841331162719856335040284265
q = 7687653192574283689842465763299611592007909813801176843577189341409409692975753037402253496632410364594655611337156337669083582400443042348458268161331043
m = nthroot_mod(mq,4,q)
print(long_to_bytes(m))
b'0xGame{7881ed67088e9f72b860f8c376599785}'

在某些特殊情况下（多半是出题人的为难），e和phi是不互素的，

那么当pow(m,gcd(e,phi),n)<n时，我们可以采用直接开方的办法，

当pow(m,gcd(e,phi),n)时，一般我们采用有限域开方、中国剩余定理换模，有些时候有限域开方的办法不同，或者是条件更加特殊(可以参照NCTF2019的题)，就需要在这个基础上去思考更多的问题，感兴趣的师傅可以了解一下。

EzRSA

考点：

  • 费马小定理
  • 光滑数分解
  • 连分数分解

hint已经给出所有考点，题目的交互脚本也给了，本意就是上点送分题的，，

因为交互也不算太复杂，直接连上去之后把数据拖到本地解就可以了，详细的概念和知识点这里就不拓展了，在这里，都有详细的介绍。

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
48
49
50
51
52
#数据从服务器上面拖下来解就好，这里就只做分解，不做解密了

#challenge1
gift = 
N = 
q = GCD(gift-1,N)
p = N//q
print(f'p={p}\nq={q}')

#challenge2
N = 
a = 2
n = 2
while True:
    a = gmpy2.powmod(a, n, N)
    res = gmpy2.gcd(a-1, N)
    if res != 1 and res != N:
        q = N // res
        print("p=",res)
        print("q=",q)
        break
    n += 1

#challenge3
def transform(x,y):    #使用辗转相除将分数x/y转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:   #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回
#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res
 
def wienerAttack(n1,n2):
    for (q2,q1) in sub_fraction(n1,n2):  #用一个for循环来注意试探n1/n2的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if q1==0:
            continue
        if n1%q1==0 and q1!=1:
            return (q1,q2)
    print("该方法不适用")
 
N1=
N2=
print(wienerAttack(N1,N2))

EzLFSR

考点：

  • 矩阵的理解应用
  • 线性反馈移位寄存器
  • SageMath的应用(直接解方程不用也行，这里还是推荐使用)

这题是出题人从网上摁抄的，可能直接搜索都能搜得出原题，重点是想让大家了解异或和按位与这两个操作其实就是mod2下的加法和乘法，以及矩阵的构造(如果是大一新师傅的话，这个时间点应该也学到了矩阵怎么构了)。

从网上搜索就能知道LFSR的概念，这个就是反复的：按照状态位计算，生成新的状态位，直接解了这个128元方程组就好，结合矩阵的知识，用逆矩阵去求解题设的增广矩阵就好了。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#SageMath
from Crypto.Util.number import *
def string2bits(s):
    return [int(b) for b in s]

initState = [0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]
outputState = string2bits('1101111111011101100001000011111101001000111000110100010011110111010011100110100100111001101010110110101110000011110101000110010010000011111111001111000110111001100111101110010100100001101001111110001010000100111101011011100010000000100000100000100111010110')
states = initState + outputState
    
ms = MatrixSpace(GF(2), 128, 128)
mv = []
for i in range(128):
    mv += states[i : i + 128]
m= ms(mv)
    
vs = MatrixSpace(GF(2), 128, 1)
vv = outputState[0:128]
v = vs(vv)
    
secret = m.inverse() * v
M=secret.str().replace('\n','').replace('[','').replace(']','')
print(long_to_bytes(eval('0b'+M)))

Fault!Fault!

考点：

  • 数学推导、数据处理
  • 远程交互脚本的编写

关于推导的过程和原理直接看这篇文章就好，如果没推过的话直接百度“RSA Fault”都能出的来这篇文章，所以我觉得理解这部分应该不会太复杂。

脚本编写部分：首先因为服务器有时间限制、交互要验证等一系列的原因，一般不推荐写好脚本了再去和服务器交互、调试脚本，容易浪费时间、搞自己心态，我的建议是在自己本地上部署一遍题目，或者是模拟题目的条件再调试数据，看看符不符合自己的预期、设定。

其次就是在这种时间限定要拿很多数据的情况下，就不推荐一边拖数据一边做数据处理了，影响速度，建议是写好数据处理的脚本之后，直接从服务器拖下我们需要的1024组数据，本地运算一遍交上去就行，方便故障排查、也不会浪费很多时间。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#part1 拖数据:
from pwn import *
import itertools
import hashlib 
import string

def proof(io):
    io.recvuntil(b"XXXX+")
    suffix = io.recv(16).decode("utf8")
    io.recvuntil(b"== ")
    cipher = io.recvline().strip().decode("utf8")
    for i in itertools.product(string.ascii_letters+string.digits, repeat=4):
        x = f"{i[0]}{i[1]}{i[2]}{i[3]}"
        proof=hashlib.sha256((x+suffix).encode()).hexdigest()
        if proof == cipher: break
    print(x)
    io.sendlineafter(b"XXXX:",x.encode())

f = open('data.txt','a')
io = remote('43.139.107.237',10005)
proof(io)
io.recvuntil(b'>')
io.sendline(b'S')
io.recvuntil(b'>')
io.sendline(b'test')
n = int(io.recvline())
e = int(io.recvline())
c = int(io.recvline())
for i in range(1023):
    io.recvuntil(b'>')
    io.sendline(b'F')
    io.recvuntil(b'>')
    io.sendline(f'{c}'.encode())
    io.recvuntil(b'>')
    io.sendline(f'{i}'.encode())
    io.recvline()
    m_ = int(io.recvline())
    f.write(str(m_)+'\n')

io.close()
f.close()
print(f'n={n}')
print(f'c={c}')

#part2 处理数据:
from Crypto.Util.number import *

m = b'test'
m = bytes_to_long(m)
n=97914749446436063122542581376873112820400732267124998400088179058780712855378248201542023213009277089224170180542304344638059090556781844777641757174279080863658472878763702075705376304717343862101956239090701126225622317784075619757963099253602226642056966461019740454740445226152574361794251236011891077789
c=73133825445675329950286077126832004352164006658709453405485979363609175208129785294437379266100324978770868694885347204515053234232666436453863941132493106687387106354265743735994029551983269772204386433432638435914078485461320417024614354676213557287698752845797412775400104995650602775848941301838035593870

e = 65537

dbin = ''
with open('data.txt','r') as f:
    for i in range(1023):#私钥位数不同可能要判断的数量不同
        m_ = int(f.readline())
        h = (inverse(m,n)*m_)%n
        test = pow(c,2**i,n)
        if h == test:
            dbin += '0'
        elif h == inverse(test,n):
            dbin += '1'

d = eval('0b'+dbin[::-1])#校验
if (pow(c,d,n)==m):
    print(d)
#最后把私钥交上去就拿到flag了

小思考：虽然时间是有一定的限制，但这道题的私钥是固定的，所以我们可以多次交互拿数据推导出这个私钥。

但是如果这个私钥不是固定的呢？我们只有一次交互的机会，多次交互拿数据推导出这个私钥这个思路恐怕不太行，不管怎么优化可能时间都是不太够的，那么我们要如何处理这种情况？哈哈，我们第四周再见。

第三周：

ECC

考点：

  • ECC概念
  • SageMath应用

ECC相关概念可以上网查查看，阿贝尔群下运算，具体概念这里不放了。

我们设：r是加密方的生成随机数\ k是私钥、K是公钥(K=kG)\ 加密：C_1 = M+rK = M+rkG\ 同时告诉解密方：C_2 = rG\ 解密：M = C_1-rkG = C_1-kC_2

SageMath自带DLP问题求解的函数，直接用就行，要注意的是，加密的时候信息一般要编码到曲线上面，但是这题并没有这样做，就导致了C1，C2都不是在曲线上的点，但这个不要紧，照着题目逆向求出来就行了

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
#sagemath
#part1:求私钥
q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568

G = (641322496020493855620384, 437819621961768591577606)
K = (781988559490437792081406, 76709224526706154630278)
E = EllipticCurve(GF(q),[0,0,0,a,b])
G = E.point(G)
K = E.point(K)
print(G.discrete_log(K))
#12515237792257199894
#part2:解密
from Crypto.Util.number import *
def add(P,Q):
    if P[0] != Q[0] and P[1] != Q[1]:
        t = ((Q[1]-P[1]) * inverse(Q[0]-P[0],q)) %q
    else:
        t = ((3*P[0]*P[0]+a) * inverse(2*P[1],q))%q

    x3 = t*t - P[0] - Q[0]
    y3 = t*(P[0] - x3) - P[1]
    return (x3%q, y3%q)

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)


q=1139075593950729137191297
a=930515656721155210883162
b=631258792856205568553568

G = (641322496020493855620384, 437819621961768591577606)
K = (781988559490437792081406, 76709224526706154630278)
C_1=(926699948475842085692652, 598672291835744938490461)
C_2=(919875062299924962858230, 227616977409545353942469)
k = 12515237792257199894
tmp = mul(k,C_2)
tmp = (tmp[0],-tmp[1])
M = add(C_1,tmp)


print(long_to_bytes(M[0])+long_to_bytes(M[1]))
#b'Al1ce_L0ve_B0b'

LLL-FirstBlood

直接规约就可以得到结果

详细的原理这里看

仙人指路1

怕误人子弟，这里就不详细地写出更多概念，原理了。

LLL算法的核心是施密特约化，输入一组向量基，得到一组约化基。

使得我们可以通过一定的构造，去规约出某个向量(一组数字)，那么在这道题中，因为A是正交矩阵，经过LLL算法之后就被“约掉”了，所以我们可以直接得到题设的结果。

exp:

1
2
3
4
5
6
7
8
from Crypto.Util.number import *
C=[[1528140902799730745476264672501768332416990282355490479242339131918301176698899635154781328839496210200676497333428, 2081687444435007467807250373278513114045272585243815458840083487459795021302180077490134099644993120009567147202772, 3080873409460299046339495750746632185307246572817534784703936044874106809413620470006445984962733721029566440253675, 3491734341995174183626991907292607070252197520631412767989879432598743851171175369180080355977574296558734415823458], [2359409535809048127331244699867147546817134802610067329431135227991488324148374065940238308147500809599395748756798, 3191196199160821446351036460385791985682645040446022512790815348810555748825420237291839170774872264097466183208742, 4665346530155386457242345394284286198347336281451530670818113876767736288089400119492317775648206643242839430899283, 5369350746042850276067380638571565496087948799720968959426256192923852197959381101839484196445995828389461004495917], [1641407111066265429602929560264443103285908072677065498760570514577412905392260182334706635555256537745902283191251, 2190536173399177167068153351271988931232272884028569669242062395087922275021628334797729266560930040116807133977244, 3127556759140845426132305699421707182108351516931881411928719802847628408656887897596425133523782526561471050447359, 3707239956529200159380870618471703921011276020439315706352183576289925263316580408968092016782483770373121972835410], [9883814543195849013523934427451407019514807606993414569626142656857168165339, 13190422499129347541373922929251088892868361241120937213742340947017395215646, 18832738552342488056498211782604832513006649329982003661701684946590064734701, 22323329751908690611034666068697427811613727429398087082295754189068333861152]]
C = Matrix(ZZ,C).LLL()
flag = b''
for i in list(C[0]):
    flag +=(long_to_bytes(-i))
print(flag)
#b'0xGame{8e4d5924dc4cd78f11c1eeb99e991ab3}'

LLL-SecondBlood

先推公式：

题设：Am+noise=c(modp)\ 展开：Am+noise=c+kp\ 构造：Am-c+k*p=-noise\ 可以发现左边大部分是已知参数，右边是较小的未知质数

那么我们可以构造这样一个矩阵：

Lattice.png

直接对右边这个构造的矩阵进行规约就好，得到的结果就是下面的矩阵，详细原理在上边。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]

c = [i for i in c_]
mask.append(1)
mask.append(0)
tmp = [[0 for i in range(len(c)+2)] for _ in range(len(c))]
tmp.append(mask)

for i in range(len(c)):
    tmp[i][i]=q
c.append(0)
c.append(pow(2,341))
tmp.append(c)

tmp =matrix(ZZ,tmp) 
tmp = tmp.LLL()
print(long_to_bytes(-tmp[0][4]))
#b'0xGame{19255b5c7b19c790e28d87c8a8bb1d33}'

以上是正解

下面是邪道速通:

Coppersmith

因为未知量的位数都比较小，直接考虑使用多元Coppersmith，这里解释一下多元Coppersmith的思想和作用:

我们想要在有限域中解方程，可以通过展开和一定的方式换到整数域上，把问题变成简单的解方程问题（利用牛顿迭代法），然后再利用LLL算法去对构造的数学式子进行求解。

总而言之就是，实现有限域求根的算法（前提是这个根必须要比模数小很多）。因为求根的时候用到了LLL算法去规约基向量，得到的结果也是一组基（性质更好的），这种问题就被称之为SVP（最短向量）问题。

同理的还有CVP,HNP这些，在将来的格密码学习中会经常打交道，这里就不误人子弟了。

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
48
49
50
51
52
53
54
55
56
57
58
59
import itertools
from Crypto.Util.number import *

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []
q = 9342426601783650861020119568565656404715236059903009041977149778244153930435908024696666887269890479558473622355346816236972767736577737332173213722012253
mask = [6237128445236992920577225644858662677575951126467888858782461334057970069468925833844231116647406833999142659751374620280213290736114576089069396331226747, 6368031389213953889417545256750169233725975229197446803885029159767701479445576860704561593200907482372690851152126782391126462547524526631934408981070841, 5106473460982791188578285397420642137630347289252852045044021197988607082777231839839730169682158507822078412449827976663385282021916120837408192506341443, 6318090842950331228033349517542810123596316850353637421587264886413877142612686177796023049304908696413386218992511112752788640732410845589679820003047667]
c_ = [3823539664720029027586933152478492780438595004453489251844133830947165342839393878831914879334660250621422877333022321117120398528430519794109624186204492, 1721659645750224819953244995460589691120672649732560768435214608167861246790136217219349234604724148039910656573436663379375048145045443527267790379816425, 668633520079344839648950502380059311916108468801009386138810324259146523323704014491547148973835774917331333581475920804677395949854411894556705238578896, 497860586379981076499130281851986010889356253371192266267220334713415782402939318483926418213877341511996918189750595755372560345085899109305344338944066]


A = mask[0]
c = c_[0]
PR.<x,noise> = PolynomialRing(Zmod(q))
f = A*x - c + noise
roots = small_roots(f,(2^320,2^50),2,3)
print(roots)
#[(404417766109752774365993311026206252937822359426120081323087457724287886115277329019989616964477, 585427539127961)]

Matrix

考研真题：大一新师傅的练习册上就有解法的。

已知A^{secret}=C\ 通过相似矩阵得：A=P^{-1}BP\ 那么问题就变成:A{secret}=(P{-1}BP)^{secret}=C\ 对中间的式子展开得到:P{-1}*B{secret}*P\ 其中B是对角矩阵，问题就变成了求对角元素上面的离散对数问题\ 那么之后参照上周的解法就可以了。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#sage
A=[[12143520799533590286, 1517884368, 12143520745929978443, 796545089340, 12143514553710344843, 28963398496032, 12143436449354407235, 158437186324560, 12143329129091084963, 144214939188320, 12143459416553205779, 11289521392968],[12143520799533124067, 1552775781, 12143520745442171123, 796372987410, 12143514596803995443, 28617862048776, 12143437786643111987, 155426784993480, 12143333265382547123, 140792203111560, 12143460985399172467, 10983300063372],[12143520799533026603, 1545759072, 12143520746151921286, 781222462020, 12143514741528175043, 27856210942560, 12143440210529480891, 150563969013744, 12143339455702534403, 135941365971840, 12143463119774571623, 10579745342712],[4857408319806885466, 2428704161425648657, 12143520747462241175, 758851601758, 12143514933292307603, 7286139389566980165, 9714738936567334300, 144947557513044, 12143346444338047691, 130561054163540, 4857352974113333366, 2428714303424782417],[12143520799533339320, 1476842796, 12143520749060275613, 733281428880, 12143515144091549812, 25896324662208, 12143446129977471347, 139126289668080, 12143353609086952433, 125093278125816, 12143467808884068695, 9705993135696],[3469577371288079926, 5204366058378782250, 12143520750775862343, 706665985740, 12143515359139397843, 24876891455539, 12143449149385190675, 5204499435641729607, 1734628523990131469, 119757210113970, 12143470097256549947, 9282407958928],[10986995009101166671, 1734788687033207505, 12143520752514668698, 680173911560, 12143515570582515443, 23883386182656, 12143452072344092516, 10408859957710764174, 8673790006740000925, 4047954924507284041, 12143472277719610437, 8879790035168],[12143520799534210329, 8095680534365818753, 12143520754224346525, 6071761054204856029, 12143515774342357443, 22931775530664, 12143454859049102627, 122586336122081, 12143373761302849103, 109840689548590, 8095634066844843878, 8500892291801],[2428704159899526175, 7286112481016467893, 12143520755876491019, 629765964828, 12143515968446948123, 9714838668887734012, 4857345013259425502, 117630592711632, 12143379764863568374, 105318302849760, 2428659620509049335, 7286120625945355053],[7286112479717322389, 7286112480971640825, 12143520757456628435, 606320684970, 12143516152115449139, 4857429497934652454, 4857347490735050126, 112978994964264, 12143385390297217523, 101086824360217, 7286069740980100293, 7286120294834973633],[7727695054246476847, 1202487728, 12143520758958480293, 584144077140, 12143516325240923843, 20377952745696, 12143462294760579275, 108622249048560, 12143390651947217363, 97133513961120, 12143479741445599772, 8831658996900830432],[12143520799535388887, 1161628182, 12143520760380594623, 563225247585, 12143516488091679443, 19626876325056, 12143464472820678035, 104545135017180, 12143395570399006523, 93441517429260, 12143481309754543787, 7218375794633]]
enc=[[11285847990515095003, 7585413350741918021, 11658254512436412666, 477577914899276103, 2941386515764607825, 11283325421744133699, 4096971712575507616, 8118672870538606033, 2377937081025778041, 6576171711896495163, 6152554374963853172, 5022013484610428974], [8354008012616001452, 7787447107046065118, 9504997911333967278, 1082773427768571094, 6015520658629219637, 11244285744740006951, 4493944053220750368, 3504246247470690014, 1738582001618280397, 2330057776906622572, 3043456814665571080, 2981613454022714952], [2508674373714509177, 3544963739532775937, 7952732753025175616, 11161786730565526285, 3397123486689639675, 6454135592624912854, 6613201018024296927, 9748485344986779929, 1819761609989340766, 1259944825407465767, 1596049024644778041, 7769939905324967788], [4200851163596876950, 11960539098651202761, 3303721151143544462, 2532304102428121556, 11083895221097319129, 1171933471304558017, 1549099593543874478, 6088238862927163233, 6459553630361959801, 947358195425767572, 2090533922210134578, 9023030120605201052], [2271102089902208138, 1614812525306266829, 1546249462332047661, 3168333397191737100, 7678980468150522028, 3128939172985153696, 1146041044751755224, 11870173227065140617, 8351303466095252790, 694704483676649448, 7944218023016968278, 583421745603756386], [10309472503110333289, 1100598261990718822, 10235859400888405310, 910925705831020921, 10771855884237562064, 9970830255165655653, 11678899608458971536, 4368822164222204233, 3104861419162339779, 4540709628196554222, 7851809145727500968, 12086896840826708824], [10973051751637593366, 5039073157846327641, 4855314857834773443, 4416954195828423951, 8243966437000815560, 8250554263390748131, 8093181066366682440, 1145520354143718292, 294729013023637045, 10115389386419597159, 2767140395261835843, 6724257139233017485], [6878768250003631244, 10834164422364241529, 6946589221005878489, 539734218479521833, 2691724062063066048, 3989403041446358401, 815244541494093987, 11168528286389981272, 2021358468726921955, 1123433019094267521, 524639025046508882, 5720273332497702547], [6688451244183880831, 10892730373179989558, 6987453292894341174, 5572212176769878684, 11332149024403380575, 3944612864568504791, 6768594304071589280, 10526434024562201079, 10241323610053039912, 1120473558410865753, 306153635148226248, 3606666063074222104], [7556871914690327290, 11353594909211427742, 747771112781361153, 1245068803956910299, 2831489557155431404, 1800035620948876551, 1050411779595241927, 5665981688041778089, 2028968510484240787, 4386552235402890530, 10334391443650474796, 3883841302951550608], [4485787817401669404, 184501191500952934, 3690661645276970957, 6263309802498749034, 6484490370652685031, 9743108369653588026, 3045941510087387269, 5870433915209047275, 4679598273992216016, 11839352681285251516, 4957980185504231911, 7925596893607015470], [1000449712878466719, 7022601702937838844, 1095849907482791166, 11989051568709522226, 6768031250066783733, 185945517026191241, 4280928696740160411, 5633542561098902406, 10176177574499086410, 5782837249861240943, 7406530879613861823, 1971858224839520916]]
p=12143520799543738643
A = matrix(GF(p), A)
enc = matrix(GF(p), enc)
B,P = A.eigenmatrix_right()
P_inv = P.inverse()
assert P*B*P_inv == A
B_=((P_inv*enc*P)[0])[0]
b=(B[0])[0]
x=discrete_log(mod(B_,p),mod(b,p))
print(x)
#6208835615336459559
#md5后交一下flag就行

Overflow:

签名用的是ElGamal算法，这里这样放出这种题，理由如下：

  • 了解一下ElGamal算法的特点
  • 适应代码审计（有些时候题目代码很长，很容易让人感到害怕）

签名的时候没有对消息做校验，那么导致了我们的签名可以溢出被模数消掉，直接看WP吧，摆烂了。

核心的考点其实不难，只要细心就好了。

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from pwn import *
from Crypto.Util.number import *
io = remote('0.0.0.0',10002)
io.recvuntil(b'key:\n')
pub = eval(io.recvline())
io.recvuntil(b'>')
msg = long_to_bytes(bytes_to_long(b'0xGame')+pub[0]-1)
io.sendline(msg)
io.recvuntil(b'r=')
r = int(io.recvline())
io.recvuntil(b's=')
s = int(io.recvline())
io.recvuntil(b'flag.\n')
io.sendline(str(r).encode())
io.sendline(str(s).encode())
io.interactive()
io.close()
#b'0xGame{24b6edfdc07d71311774ed15248f434e}'

第四周：

Normal ECC:

考点：

  • 椭圆曲线
  • DLP
  • SmartAttack

脚本一把梭就可以了，因为题目生成的模数也比较难找，抽象，直接就抄了别人的参数了，根据题目的Hint很快就就可以搜出这个方法来，本周的送分题。拓展阅读

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
from hashlib import md5

def MD5(m):return md5(str(m).encode()).hexdigest()
p=11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
a=490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671
b=7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466
G=(4045939664332192284605924284905750194599514115248885617006435833400516258314135019849306107002566248677228498859069119557284134574413164612914441502516162, 2847794627838984866808853730797794758944159239755903652092146137932959816137006954045318821531984715562135134681256836794735388745354065994745661832926404)
K=(9857925495630886472871072848615069766635115253576843197716242339068269151167072057478472997523547299286363591371734837904400286993818976404285783613138603, 9981865329938877904579306200429599690480093951555010258809210740458120586507638100468722807717390033784290215217185921690103757911870933497240578867679716)
C1=(4349662787973529188741615503085571493571434812105745603868205005885464592782536198234863020839759214118594741734453731681116610298272107088387481605173124, 10835708302355425798729392993451337162773253000440566333611610633234929294159743316615308778168947697567386109223430056006489876900001115634567822674333770)
C2=(5193866657417498376737132473732737330916570240569047910293144235752602489388092937375844109374780050061859498276712695321973801207620914447727053101524592, 684299154840371832195648774293174908478389728255128448106858267664482339440737099810868633906297465450436417091302739473407943955874648486647511119341978)

E = EllipticCurve(GF(p), [0, 0, 0, a, b])
P = E([K[0],K[1]])
Q = E([G[0],G[1]])
c1 = E([C1[0],C1[1]])
c2 = E([C2[0],C2[1]])

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

r = SmartAttack(P, Q, p)
print(MD5((c1-k*c2).xy()[0]))
#裹上flag就可以了

Drange Leak:

考点

  • Coppersmith的利用
  • 阅读论文的能力
  • 基本数学推导

这题其实比较简单的，看着论文长篇大论的蛮哈人，但其实我们知道一篇论文的顺序是：

  • 引论(这篇论文的背景，解决了什么问题)
  • 引理(用了哪些关键的定理、这些定理的内容是什么)
  • 推导过程和结论(基本上追求速通的话就看这部分就可以)
  • 实验数据
  • 总结，引用文章……

大致上都是这样，所以这里直接快进到中间，这里可以发现：

d = Md_1+d_0\ ed = 1 (modphi)\ 展开：ed=1+kphi\ 再展：e*(Md_1+d_0)-1-kphi=0\ 展：e*(Md_1+d_0)-1-k[N-(q+p-1)]=0\ 到这一步就是题目的关键了

这里引入一个Coppersmith定理：用来求解有限域的小根问题。(给定一个模数下的数学式子，求解其中的较小未知数。)

在论文中可以看到这个Coppersmith实现的一定过程。具体核心思想在上周的WP中已经给出，所以这里直接拿来用：只要找对了关系式，找到较小的根，直接small_roots就完了。

那么在这里，我们先粗略地估算一下位数(不需要太准确，我们只要知道较小的未知数是否存在就行)：

式子：e*(Md_1+d_0)-1-k[N-(q+p-1)]=0\ e:2048位，N:2048位，k:1024位左右可能\ 利用已知信息构造有限域式子：\ ed_0 - 1 - k[N-(q+p-1)]=0(modMe)\ 令q+p-1 =z\ 得ed_0 - 1 - k*(N-z)=0(modM*e)\ d_0:70位，k<1024位，z：512位\ 之后利用small_roots函数去解未知数就可以

其实论文看不看都行，经验熟练了直接拿手推就好。

这里有一点小坑的地方在于，能够常规small_roots函数能求解的位数比较低，我卡的参数也比较极限，有的师傅构造出来了，但是解不出来，原因可能有几个：

  • bounds:这个求解的界卡太准不一定好，卡个差不多就行了，太大、过小都不一定求得出来
  • m:格基规约的维数?总之越大求解的小根就越准确，但是算法的速度也会越慢。
  • d:多项式的次数。

经验之谈：找对办法的情况下，估算好位数之后就可以开始梭哈了。

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
48
49
50
51
52
53
54
55
56
import itertools
from Crypto.Util.number import *

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m+1):
        base = N^(m-i) * f^i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B*monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 20890649807098098590988367504589884104169882461137822700915421138825243082401073285651688396365119177048314378342335630003758801918471770067256781032441408755600222443136442802834673033726750262792591713729454359321085776245901507024843351032181392621160709321235730377105858928038429561563451212831555362084799868396816620900530821649927143675042508754145300235707164480595867159183020730488244523890377494200551982732673420463610420046405496222143863293721127847196315699011480407859245602878759192763358027712666490436877309958694930300881154144262012786388678170041827603485103596258722151867033618346180314221757
e = 18495624691004329345494739768139119654869294781001439503228375675656780205533832088551925603457913375965236666248560110824522816405784593622489392063569693980307711273262046178522155150057918004670062638133229511441378857067441808814663979656329118576174389773223672078570346056569568769586136333878585184495900769610485682523713035338815180355226296627023856218662677851691200400870086661825318662718172322697239597148304400050201201957491047654347222946693457784950694119128957010938708457194638164370689969395914866589468077447411160531995194740413950928085824985317114393591961698215667749937880023984967171867149
c = 7268748311489430996649583334296342239120976535969890151640528281264037345919563247744198340847622671332165540273927079037288463501586895675652397791211130033797562320858177249657627485568147343368981852295435358970875375601525013288259717232106253656041724174637307915021524904526849025976062174351360431089505898256673035060020871892556020429754849084448428394307414301376699983203262072041951835713075509402291301281337658567437075609144913905526625759374465018684092236818174282777215336979886495053619105951835282087487201593981164477120073864259644978940192351781270609702595767362731320959397657161384681459323
leak=136607909840146555806361156873618892240715868885574369629522914036807393164542930308166609104735002945881388216362007941213298888307579692272865700211608126496105057113506756857793463197250909161173116422723246662094695586716106972298428164926993995948528941241037242367190042120886133717
PR.<x,k,z> = PolynomialRing(Zmod(e*leak))
f = e*x - k*n + k*z - 1
roots = small_roots(f,(2^100,2^1024,2^1024),3,3)
print(roots)
#从这里得到的z = (p+q-1)，后续直接解方程就可以了。

LLL-ThirdBlood

考点：

  • 格基的理解
  • DSA算法
  • 签名伪造

详细的文章在这里 一类基于各种DSA的HNP问题求解

其实仔细搜索一下hint的内容，网上应该也有大量的文章，通过大量地搜索发现：阴差阳错之下甚至发现和20年的学长出过的赛题撞了demo。（一周内共有十位师傅，包括一位校内新生做出来了，跪了）

part1:拖取数据

k的位数这里没有卡太死(甚至导致了非预期解)，直接拖四组就行，求稳多拖几组的结果都一样的。

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
#part1:拖取数据
from pwn import *
from hashlib import sha1
from Crypto.Util.number import *

context(os='linux', arch='amd64', log_level='debug')
h = bytes_to_long(sha1(b'test').digest())
s = []
r = []

io = remote('0.0.0.0',10002)

def Sign(target):
    target.sendafter(b'>',b'S')
    target.sendafter(b'>',b'test')
    target.recvuntil(b's = ')
    s_ = int(target.recvline())
    target.recvuntil(b'r = ')
    r_ = int(target.recvline())
    s.append(s_)
    r.append(r_)

io.recvuntil(b'q=')
q=int(io.recvline())
io.recvuntil(b'g=')
g=int(io.recvline())
io.recvuntil(b'y=')
y=int(io.recvline())

for i in range(10):
    Sign(io)
io.close()

print(f'q={q}')
print(f'h={h}')
print(f'r={r}')
print(f's={s}')

part2:求解私钥

仔细想想这一步，其实就是上周LLLSecond的拓展，原理是一个差不多的(甚至构造也能一样?)

以下是论文的构造解：

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
from Crypto.Util.number import inverse
q=
h=
r=
s=
#填入以上数据

A=[]
B=[]
M=[]

t = 120 
#填入k的大概位数，相当于一个上界，比想要求解的向量大一点就行
for i in range(len(r)):
    tmp = [0 for i in range(len(r)+2)]
    tmp[i] = q
    A.append(mod(r[i]*s[0]*inverse_mod(r[0]*s[i],q),q))
    B.append(mod((r[0]*h-r[i]*h)*inverse_mod(r[0]*s[i],q),q))
    M.append(tmp)

A.extend([1,0])
B.extend([0,2^(t)])
M.append(A)
M.append(B)
M = matrix(ZZ, M)
#构造矩阵
T = M.LLL()

s0 = s[0]
s1 = s[1]
r0 =r[0]
k = T[0][0]
x = inverse(r0, q) * (s0 * k - h) % q
print(x)
#获得私钥

以下是学弟的非预期解：

1
2
3
4
5
6
7
8
9
10
11
12
13
q = 
A = 
B = 
M = matrix(ZZ,22,22)
for i in range(20):
    M[i,i]=q
    M[20,i]=A[i]
    M[20,i]=B[i]
M[20,20]=1
M[21,21]=pow(2,160)
res=M.LLL()
assert pow(2,160)=res[-1][-1]
print(abs(res[-1][-1]))

嗯，确确实实的非预期了，而且和题目说的一样，和上周的预期构造是相同，我怎么能如此的粗心大意？

part3:伪造签名

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
from Crypto.Util.number import *
from random import getrandbits,randint
from hashlib import sha1
pri_key = 27462250581507679486

class DSA:
    def __init__(self):
        self.q=
        self.p=
        self.g=
        self.y=
        self.x = pri_key
    def sign(self,m):
        H = bytes_to_long(sha1(m).digest())
        k = getrandbits(128)
        r = pow(self.g,k,self.p)%self.q
        s = (inverse(k,self.q)*(H+r*self.x))%self.q
        return (s,r)

    def verify(self,m,s_,r_):
        H = bytes_to_long(sha1(m).digest())
        u1 = (inverse(s_,self.q)*H)%self.q
        u2 = (inverse(s_,self.q)*r_)%self.q
        r = (pow(self.g,u1,self.p)*pow(self.y,u2,self.p))%self.p%self.q
        if r == r_:
            return True
        else:
            return False

Test = DSA()
s,r = Test.sign(b'admin')
assert Test.verify(b'admin',s,r) == True
print(s,r)

Orac1e

第一周就学过的，CBC分组模式大致是什么流程。

详细文章这里看(看我看我)，下面的代码就不用看了，有点啰嗦的。

介绍视频这里看视频在这里。

这里简单阐述一下：因为CBC分组模式存在的原因，我们可以把解密的处理分为以下流程

  • 密文分组
  • 密文组解密->得到明文组
  • 合并明文组
  • 去填充
  • 检验是否合法

我们将中间解密的这块算法视作一个“黑盒”，

其中因为CBC分组解密流程的原因：密文->黑盒->上组密文->明文，

又因为必须检验填充是否合法的原因：

当且仅当去填充位上的数字==去填充位数，解密才能成功

那么按照第一周的CBC思想，通过已知明文去猜解密钥(中间经过黑盒的向量)，这道题就结束了。

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
from pwn import *
from base64 import b64encode,b64decode
#context(log_level='debug')
io = remote('0.0.0.0',10002)

size = 16

def Orac1e(payload,index):
    data = b64encode(payload)
    io.sendafter(b'>',data)
    tmp = io.recvline()
    if tmp == b' Data update\n':
        print(index)
        return 1
    else:
        return 0

def Oracle(BIV,BC):
    D = []
    for index in range(15,-1,-1):
        I = [0 for _ in range(index)]
        for i in range(256):
            if D == []:
                CIV = bytes(I)+bytes([i])
            else:     
                CIV = bytes(I)+bytes([i])+xor(D,16-index)
            assert len(CIV) == 16
            payload = CIV+BC
            if Orac1e(payload,index):
                D.insert(0,(i^(16-index)))
                break
    return xor(D,BIV)

def Attack(c):
    Block_count = len(c)//16
    print(f'Block_count={Block_count}')
    iv = c[0:16]
    m = b''
    for i in range(1,Block_count):
        m += Oracle(c[size*(i-1):size*i],c[size*i:size*(i+1)])
        #print(m)
    return m
    
io.recvline()
c = io.recvline()[:-1]
c = b64decode(c)
print(Attack(c))