WriteUp for crypto in InCTF2021
WriteUp for InCTF
gold_digger
|
|
The main problem
|
|
if $flag_i$ is 1 ,the bin_r + i well be odd
else the $r+i$ well be even
we can determine the flag by calculating Jacobi symbol of c to N
solution
|
|
Lost Baggag
In this challenge , we need to analyze a backpack encryption system
the challenge give us only pubkey and cipher
so,i tried Lattice reduction algorithm to solve it
sagemath lattice reduction code:
|
|
The matrix is looks like:
$$\begin{pmatrix} 2&0&0&\cdots&0&PK_1\\
0&2&0&\cdots&0&PK_2 \\
0&0&2&\cdots&0&PK_3 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0&0&0&\cdots& 2 & PK _ n \\
1&1&1&\cdots &1&ct
\end{pmatrix}
$$
Lets check the LLLdata.txt
fortunately,I find a vector only have 1 and -1
try to docode it and get the flag
|
|
Right Now Generator
This challenge is easy after analysing
It’s more like a reverse than a crypto….
analysis and implement
Our major trouble is to find The Inverse function of functioncs below,
And how we think about finding seed-sequence from a-sequence given by the attachment
|
|
With a simple algebraic calculation
We can write out Inverse function easily
from a-sequence get seed-sequence:
|
|
inv_wrap:
|
|
Combined them into decryption code
Solution
|
|
Eazy Xchange
there we can exchange gen_key into a simple form
|
|
and the tmp is small $(tmp <1024)$
and there tell us $B=tmp*G$
|
|
so
$SS=tmp_1*tmp_2 * G$
and $SS=tmp_1*tmp_2<1024 * 1024$
We can try out $tmp_1*tmp_2$ easily
|
|
Encrypted Operations
这个太哈人了 全是cpp(我tm直接吓出母语)😫😫😫
审了一天
发现印度老哥这个vector的理解和我不一样,缝缝补补终于搞出来了
反正这个题应该很难有复现环境了
(其实能把homomorphic_system复写一遍应该还是可以的?放在docker里面还是比较好部署的)
就干脆简单说一下三个部分的思路好了🐫
prat1
|
|
拿导外面跑一下发现其实就是对切片求和,由于temp1里面本质上是个等差数列,找一下规律就可以了
part2同理
payload1
|
|
level2 对 p1 p2 取反使其抵消掉numVec里面除了m1[row[2]]以外的所有向量
在 userinp生成处,往后多选了一位,这个操作可以在EncryptedOperations中对m1[row[2]]右移一位抵消掉影响,最有一位并不会消失,而是会将vector的长度扩展一位
|
|
exp
|
|
shell
|
|