分圆多项式
本原单位根在复数域$C$中，对于多项式$x^n-1$有$n$个根：
x=\cos\frac {2\pi k}n+i\sin \frac {2\pi k}n,k=0,1,...,n-1根据欧拉公式：
e^{ix}=\cos(x)+i\sin(x)可以写成$x=e^{\frac{2\pi ik}n}=\exp \frac{2\pi ik}n$。
$\exp$是指数函数的缩写。
可以记$\omega_n=\exp \frac{2\pi i}n$，能得到$\omega_n^k=\exp \frac{2\pi ik}n$。那么$x^n-1$的根可以写成$1,\omega,…,\omega^{n-1}$。可以将这个多项式转化：
x^n-1=(x-1)(x-\omega)...(x-\omega^{n-1})根据公式$\omega_n^k=\exp \frac{2\pi ik}n$，这$n$个数关于乘法构成了$n$阶循环群（单位根群），$\omega_n$是这个群的一个生成元。
如果一个$n$阶单位根$\omega^k_n$，满足对于任意$i=1,2,…,n-1$，$\omega^{ki} ...
同源密码学
同源密码属于能抵抗量子攻击的后量子密码体制，基于椭圆曲线密码。
参考论文：1321.pdf (iacr.org)，550.pdf (iacr.org)
前置知识扩域如果域$F$是$K$的子域，那么$K$是$F$的扩域或者域的扩张，记作$K|F$。例如对于某个有限域$F_p$，它的二次扩张为$F_{p^2}$。
超奇异同源Diffie-Hellman (SIDH) 秘钥交换算法就是在这个$F_{p^2}$有限域下工作的，可以知道这个有限域的大小为$p^2$，即为有$p^2$个元素，表示这个有限域元素的一个简便的表示方法就是写为复数形式：$$u+vi\ \ (u,v\in F_p)$$
同源性同源（isogeny）指的是两条椭圆曲线之间的同态。相当于把一条椭圆曲线的点映射到另一条椭圆曲线上。例如：对于在$F_q$的椭圆曲线$E_1,E_2$，对于映射$\phi:\phi(P_1)=P_2,P_1\in E_1,P_2\in E_2$可以称作一个同源。
同源映射到的曲线$E’$是这个同源的陪域（codomain）。
一些性质：
同源满足满同态，每一个映射后的曲线中的点都有原像与之对 ...
HNP学习笔记
HNP参考文章：HNP学习笔记 | Tover’ Blog
格密码中的HNP（Hidden number problem）是隐藏数问题：给出$n$组方程：
\beta_i\equiv \alpha_ix\pmod q提供$q,\alpha_i$，提供每个方程中的$\beta_i$的一部分，想求出$x$。
假设$q$为$m$位，$\beta_i$共泄露$s$位，当$s(n+1)≥m$，$n$为构造的格基维数，那么HNP可能有解。
给问题换个符号好好描述：把$\alpha_i$换成$A_i$，$\beta_i$拆成泄露的高位$B_i$和未知的低位$b_i$相加：
A_ix\equiv B_i+b_i\pmod q赛题2022高校密码数学挑战赛赛题二提供参数，$q$为模数，$s$为已知比特分位数，$n$为方程数，$Coeff$表示$n$维系数向量$(\alpha_1,…\alpha_n)$，$KnownNonce$为每个元素已知的比特分位值。
Lv11234567891011121314151617181920212223242526272829303132333435363738394 ...
近期比赛复现Vol.2
0xGame2023Vigenere10dGmqk{79ap4i0522g0a67m6i196he52357q60f}
维吉尼亚解密，根据flag头手动爆一下密码即可，密码为game。
密码，觅码，先有*再密1234567891011121314151617181920212223242526from secret import flag #从中导入秘密的flag，这是我们要破解的信息from Crypto.Util.number import bytes_to_long #从函数库导入一些编码函数from base64 import b64encode#hint:也许下列函数库会对你有些帮助，但是要怎么用呢……from base64 import b64decodefrom gmpy2 import irootfrom Crypto.Util.number import long_to_bytesflag = flag.encode()lent = len(flag)flag = [flag[i*(lent//4):(i+1)*(lent//4)] for i i ...
ElGamal算法
简介ElGamal 算法的安全性是基于求解离散对数问题的困难性，既可以用来加密也可以用来进行数字签名。
密钥生成选择一个大素数$p$，使得在$Z_p$上求解离散对数是困难的。
选择$Z^*_p$的生成元$g$。
随机选取$0≤k≤p-2$，计算$g^k\equiv y\pmod p$。
私钥为$k$，公钥为$p,g,y$。
加密Alice选择随机数$r\in Z_{p-1}$，对明文$m$进行加密：
\begin{cases}y_1\equiv g^r\pmod p\\y_2\equiv my^r\pmod p\end{cases}解密
y_2(y_1^k)^{-1}\bmod p\equiv m(g^{kr})(g^{kr})^{-1}\equiv m\bmod pElGamal数字签名数字签名由公钥密码发展而来，用于对数字消息进行签名，防止消息伪造或篡改，也可以用在通信双方的身份鉴别。
数字签名依赖非对称密码：
先利用相同的方式生成公钥：
选择一个随机质数$p$，选择$Z^*_p$的生成元$g$，随机选择整数$0≤d≤p-2$，计算：
g^d\equiv y (\bmod p ...
RSA学习笔记（六）
RSA学习是不能停止的，不是吗？
优秀资源：风二西/rsa_f2x - 码云 - 开源中国 (gitee.com)
共素数RSA摘自文章：Common Prime RSA 笔记 | 独奏の小屋 (hasegawaazusa.github.io)
Wiener提出，在RSA中，当$p,q$为素数，当$p-1$和$q-1$有一个大数因子，可以反制维纳攻击，将这种$p-1$和$q-1$含有一个共同大素数因子的RSA称为共素数RSA。
对于公因子大素数$g$，让$p=2ga+1,q=2gb+1$，这里让$a,b$互素，且$h=2gab+a+b$也是素数，这样就可以确保$\gcd(p-1,q-1)=2g$，且$\frac {pq-1}2=gh$和$N=pq$大小接近。
发现：
\lambda(pq)=lcm(p-1,q-1)=lcm(2ga,2gb)=2gab
\phi(pq)=(p-1)(q-1)=2ga2gb=2g\lambda(pq)所以还需要规定$e,d$还要和$\lambda(pq)$互素。
N=pq=(2ga+1)(2gb+1)=2g(2gab+a+b)+1=2gh+1
N-1= ...
格密码和维纳攻击
扩展阅读：有关$Ax\equiv y\pmod P$文章：Wiener’s v.s Lattices —— Ax≡y(mod P)的方程解法笔记 | Tover’ Blog
对于方程$Ax\equiv y\pmod P$，$P$通常为素数，$A$为大数，$x,y$是较小的数，上述方程可以写为：
Ax-kP=y对于几个参数，有如下大小关系：
A=\Theta(P)
x,y≤\omicron(P^\frac 12)
$A = Θ(P)$表示上限，也称为渐进紧确界。符号$Θ$表示”渐进紧确界”，表示函数的增长率上下界相当。
$x = O(P^\frac 12)$表示渐进上界，下界不确定。
易得到$k$的量级也在$k≤P^{\frac 12}$上，现在知道$A,P$，需要求解$x,y$，同时我们也不知道$k$，一个方程有三个未知数是不能解的，但是通过知道大小关系，就可以进行求解。
Wiener’s Attack对于一个连分数展开（$a_0$为整数，$a_1,…,a_n$都是正整数）：
a_0+\frac 1{a_1+\frac1{a_2+\frac 1{...+\frac 1n}}}连 ...
哈希函数
概要哈希函数将任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值，得到hash（散列），下面是一般模型：
由于哈希函数的输出空间是有限的，而输入空间是无限的，因此在理论上存在多个不同的输入可以生成相同的哈希值，这就是所谓的哈希冲突。对于任何一个哈希值，存在着若干消息与之对应，称为碰撞。
同样的，这种转换是不可逆的，因为散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来唯一的确定输入值。
对于一个哈希函数，需要满足：
输入长度可变、输入长度固定、效率高、单向加密（对于哈希值$h$，无法直接得到$H(x)=h$）、抗弱碰撞（对于任意消息$x$，很难通过计算找到另一消息$y$使得$H(x)=H(y)$）、抗强碰撞（找到任意一对$H(x)=H(y)$在计算上不可行）、伪随机性。
常用的哈希函数有MD5、sha1、sha256、sha512。
哈希函数还具有明显的雪崩效应。
雪崩效应：密码学术语，指当输入发生最微小的改变也会导致输出的不可区分改变。
Proof_Of_Work各大比赛经常会有的 ...
misc速成（一）
权当备战省赛了，以后如果还需要misc应该还能用得到（后记：事实上并没有去打省赛，后来又去参与了山东省首届数据安全大赛（基本就是misc），还拿了第一名，感觉不亏。
编码Emoji-AES21年巅峰极客出过一道题，有emoji还有key：emoji-aes (aghorler.github.io)
语言转换2022虎符CTF题目。base64解码后发现很奇怪，其实是转换成了小语种，当前的字符集不显示：
1dOBRO POVALOWATX NA MAT^, WY DOLVNY PEREWESTI \TO NA ANGLIJSKIJ QZYK. tWOJ SEKRET SOSTOIT IZ DWUH SLOW. wSE BUKWY STRO^NYE. qBLO^NYJ ARBUZ. vELAEM WAM OTLI^NOGO DNQ.
可以使用linux下的iconv命令进行编码格式转换，转换到俄文：
1iconv -f koi-7 1.txt
九键键盘密码193 53 63 71 51 63 41 51 83 63 23 23 93 62 61 94 93 71 41 92 41 71 ...
DES加密
概念DES算法属于对称加密算法的分组加密算法。DES 使用一个 56 位的密钥以及附加的 8 位奇偶校验位，总共为64位，产生64位的分组，输入和输出块均为64位（八个bytes）。这是一个迭代的分组密码，加密结构也被称为是Feistel网络，其中将加密的文本块分成两半。使用子密钥对其中一半应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两半，这一过程会继续下去，但最后一个循环不交换。DES 使用 16 个循环，使用异或，置换，代换，移位操作四种基本运算。
密钥的每个第八位设置为奇偶校验位，密钥实际长度为56位。
加密流程
理解一下每一轮的加密流程：$$L_{i+1}=R_i$$
$$R_{i+1}=L_i\oplus F(R_i,K_i)$$
DES加密算法有四个步骤：初始置换、生成子密钥、迭代过程、逆置换。核心的部件包括初始置换和$F$函数（$E$扩展置换，$S$盒替代，$P$盒置换）以及逆置换，$F$函数的流程如图：
使用python进行DES加密时可以使用pyDes库进行加解密，也可以使用pycryptodome库的DES模块进行加解密，由 ...
