通过狄利克雷近似解决HNP-2H
最近在复现Crypto CTF 2024的时候碰到一道题考察了HNP-2H（Hidden Number Problem with 2 Holes，双洞隐藏数问题），在做题的时候，找到了一篇论文：Extended Hidden Number Problem and Its Cryptanalytic Applications，并通过这篇论文了解到可以通过狄利克雷近似定理来将HNP-2H约化为我们熟悉的HNP来解决。
HNP-2H的定义
这里直接引用论文中的定义：
设\(N\)是一个质数，并设\(x\in \mathbb{Z}_n\)是一个部分未知的整数满足以下\(d\)条同余式： \[
\alpha_ix+\rho_{i,1}k_{i,1}+\rho_{i,2}k_{i,2}\equiv \beta_i\pmod{N},\ 1\le i\le d
\] 其中\(\alpha_i\)满足\(\alpha_i\mod{N}\neq0\)，\(\alpha_i,\rho_{i,1},\rho_{i,2}\)以及\(\beta_i\)（\(1\le i\le d\)）为已知量，未知量\ ...
已知两质因数半数以上随机位的大整数分解
在解决RSA问题的过程中，我们往往会需要对一个大整数\(n\)进行质因数分解，在已知部分连续位的时候，我们经常会考虑使用Copper Smith方法来进行分解，但是若我们知道的是随机分散的位，Copper Smith方法将会失效，例如我们知道由两个质因数相乘得到的一个大整数\(n=pq\)如下：
104158954646372695568095796310479805403678314919693272509836778997179683485437763692891984254171869987446475357518587344178264028334102088429629785065036660148146855007349113784322098795994839040721664806905084554147298456659074384855277678993200563966327086005547016327991986225930798076081014377904788085807
又已知\(p\)的部分已知位（二进制表示，其中下划线为未知位，下同）：
10 ...
若尔当标准型与矩阵离散对数问题
想写这篇好久了，一直没空，考完期末水一下
第一部分：若尔当标准型概述
参考资料：《高等代数（第五版）》（北京大学数学系前代数小组 编）:P213-P219,P236-P239
定义：形为
\pmb{J}(\lambda_0,k)=
\left(\begin{matrix}
\lambda_0&0&0&\cdots&0&0&0\\
1&\lambda_0&0&\cdots&0&0&0\\
0&1&\lambda_0&\cdots&0&0&0\\
\vdots&\vdots&\vdots& &\vdots&\vdots&\vdots\\
0&0&0&\cdots&1&\lambda_0&0\\
0&0&0&\cdots&0&1&\lambda_0
\end{matrix}\right)_{k×k}的矩阵称为若尔当块，其中$\lambda_0$为复数.由若干个若尔当块组成的准对角矩阵
\pmb{A}=\left(
\begin{matrix}
\pmb{J}(\lambda_1,k_1)&&&\\
&\pmb{J}(\lambda_2,k_2)&&\\
&&\ddots&&\\
&&& ...
XYCTF2024-疯狂大杂烩！九转功成复现WP
题目描述你能突破九大关卡修成神仙吗？
hint1：压缩包密码为比赛名称+8位什么来着？忘了。哈哈哈！
hint2：flag格式：XYCTF{md5(flag)}
hint3：第三层非夏多，看看交点
hint4：第六层键盘画图，狼蛛键盘最新版你值得拥有！
开头由提示猜测压缩包密码XYCTF20240401
炼气第一层是天书加密，用随波逐流就可以解出压缩包密码。
第二层是一张图片，修改高就可以看到flag的第一部分：
XYCTF{T3e_c0mb1nation_
筑基第一层是BubbleBabble编码，在线解码就能解出压缩包密码。
第二层是一张图片，010看不出什么东西，用StegSolve通过LSB可以找到一串Base64编码，解码可得flag第二部分：
0f_crypt0_and_
结丹（全复现）给出一张图片
hint说看交点，可能跟Begin CTF 2023的下一站上岸差不多，四个交点为”-”，三个交点为空格，一个交点为”.”，可以转化为：
- .... . ..--.- - .... .. .-. -..
摩斯密码解码就可以得到压缩包的密码
打开压缩包发现还有一层压缩 ...
PicoCTF2024 Crypto部分WP
感想这可能是我打的第一个参与度比较高的国外的CTF，前面四道没什么难度，但是被flag_printer卡了很久，估计一时半会忘不掉这道题.
interencdec签到题
密文如下
YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclgyZzBOMm8yYXpZNWZRPT0nCg==
显然是Base64编码，解码得到结果如下：
b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrX2g0N2o2azY5fQ=='
去除b’’之后进行Base64解码结果如下：
wpjvJAM{jhlzhy_k3jy9wa3k_h47j6k69}
进行一次偏移量为7的凯撒解密可以得到flag：
picoCTF{caesar_d3cr9pt3d_a47c6d69}
Custom encryption题目给出加密代码如下：
from random import randintimport sysdef generator(g, x, p): return pow(g, x) % p#实际上 ...
向量空间（Vector Space）学习笔记
由于近期高等代数课程正在讲向量空间，所以想着结合一下高中对于向量空间的学习整理一下一些知识点和笔记。
参考书籍：《高等代数（第五版）》（北京大学数学系前代数小组 编，高等教育出版社）（以下简称北大版），《高等代数（第五版）》（张禾瑞、郝鈵新 编，高等教育出版社）（以下简称北师大版）
向量空间的定义设$V$是一个非空集合，$F$为一个数域.在集合$V$的元素之间定义一代数运算，称为加法，即给出一个法则，对于$V$中任意两个元素$\pmb{\alpha}$与$\pmb{\beta}$，在$V$中都有唯一的一个元素$\pmb{\gamma}$，称为$\pmb{\alpha}$与$\pmb{\beta}$的和，记为$\pmb{\gamma}=\pmb{\alpha}+\pmb{\beta}$，在数域$F$与集合$V$的元素之间还定义了一种运算，称为数量乘法，即对于数域$F$中任一数$k$与$V$中任意元素$\pmb{\alpha}$，在$V$中都有唯一的一个元素$\pmb{\delta}$与它们对应，称为$k$与$\pmb{\alpha}$的数量乘积（简称数乘），记为$\pmb{\delta} ...
连分数（Continued Fractions）笔记
本篇部分整理自《初等数论（第四版）》（闵嗣鹤，严士健编）
连分数的定义形如：
a_1+\frac{1}{a_2+\frac{1}{\begin{matrix}a_3+\\&&\ddots\\&&&&+\frac{1}{a_n}\end{matrix}}}\tag{1}的分数被称作连分数。
在平常的使用中，为了节省篇幅，我们一般使用以下符号来表示上述连分数：
a_1+\frac{1}{a_2+}\frac{1}{a_3+}\frac{1}{a_4+}\cdots\frac{1}{a_n}或[a_1,a_2,\cdots ,a_n]其中第二种表示方式最常用。
有关连分数的一些定理&定义定义1（连分数的渐进分数）：$[a_1,a_2,\cdots ,a_k]=\frac{p_k}{q_k}\ (1\le k\le n)$叫做连分数$(1)$的第$k$个渐进分数
定义2（简单连分数）：若$a_1$是整数，$a_2,a_3,\cdots,a_k,\cdots$是正整数，则连分数
[a_1,a_2,\cdots,a_k,\cdots]称为简单连分数，若$a$的个数有限，则称为有限 ...
LCG笔记
LCG，全称线性同余方发生器（Linear congruential generator），是一种伪随机序列生成器算法，生成器由下式定义：
X_{n+1}\equiv aX_n+b\ (mod\ p)在CTF中，一般有以下题型：
一.求逆所谓求逆，其实即为已知a,b,p,c后求解方程：
c\equiv(ax+b)\ (mod\ p)由数论知识我们很容易可以知道：
x\equiv(c-b)a^{-1}\ (mod\ p)对于这类题目，我们只需利用以上公式即可快速解出。
二.求参数a,b后求逆这类题型一般都会给出一列连续经过几次线性同余的数据后得出的数据和p，我们需要通过这些有限的数据来求解原来的数据，在此之前我们需要先求解a和b，大致过程如下：
假设已知x_{n},x_{n+1},x_{n+2}，我们有：
x_{n+1}\equiv ax_n+b\ (mod\ p)\\ x_{n+2}\equiv ax_{n+1}+b\ (mod\ p)所以我们有：
x_{n+2}-x_{n+1}\equiv a(x_{n+1}-x_n)\ (mod\ p)所以：
a\equiv (x_{n ...
Anshel–Anshel–Goldfeld 密钥交换体系(Anshel–Anshel–Goldfeld key exchange)
原理（代数密钥建立协议，The algebraic key establishment protocol） We now present an algebraic key establishment protocol which, in its most general form consists of a five–tuple
(U, V,\beta,\gamma_1, \gamma_2)where $U$ and $V$ are feasibly computable monoids, and
\beta:U× U\rightarrow V,\ \ \ \gamma_i:U× V\rightarrow V\ \ (i=1,2)are feasibly computable functions satisfying the following properties.
(i) For all elements $x, y_1, y_2 \in U$ ,
\beta(x,y_1\cdot y_2)=\beta(x,y_1)\cdot \beta(x,y_2) ...
Triode的RSA学习笔记（1）
在进行RSA解密之前，我们先要理解RSA的加密原理：
已知明文$a$，公钥对$(n,e)$，加密过程如下:
b\equiv a^e\ (mod\ n)若要对已知的密文进行解密，我们就需要得到私钥(Private Key)：
设对于上述加密过程所得出的私钥为$d$，则：
a\equiv b^d\ (mod\ n)很明显：
b^{ed}\equiv a^e\equiv b\ (mod\ n)所以：
b^{ed-1}\equiv 1\ (mod\ n)一般情况下，$gcd(n,b)=1$，故先对这种情况进行考虑
由欧拉定理：我们知道
b^{\varphi(n)}\equiv 1\ (mod\ n)很显然：
ed-1=k\varphi(n)可以看出：
ed\equiv1\ (mod\ \varphi(n))所以：
d=inv(e,\varphi(n))\ (inv(e,\varphi(n))为e模\varphi(n)的乘法逆元)
已知n,e,c在一般情况下（n可通过软件进行质因数分解）的解密此时，我们有：
n=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{ ...