install g6k in Sage 本文记录了在sagemath中安装g6k的过程。 由于github 上g6k库安装说明没有包括sage的情况,而且sage本身就已经安装了fplll等库。因此为避免下次遇到同样的问题,本文特此记录了本地g6k安装全过程。 下载g6k库 1git clone https://github.com/fplll/g6k.git 安装所需要的库 这个已经包含在 requirements.txt里,只需要运 2024-02-19 knowledge #Configure
BSGS BSGS 算法介绍 大步小步算法利用的是中间相遇的思想,使得计算复杂度从暴力枚举 O(n)O(n)O(n) 降为 O(n)O(\sqrt{n})O(n)。 考虑离散对数问题 gx≡c mod qg^x\equiv c\bmod qgx≡cmodq,x∈[0,q−1]x\in [0, q-1]x∈[0,q−1]。我们设 m=⌈q⌉m=\lceil \sqrt{q}\rceilm=⌈q⌉,并记 x 2024-01-22 competition #algorithm
Elliptic Curve - Divide by 2 问题引入 对于一条椭圆曲线 E:y2=x3+ax+bE:y^2=x^3+ax+bE:y2=x3+ax+b ,如果我们知道其中的一个点 Q=2PQ=2PQ=2P 要如何求 PPP 呢? 如果 EEE 的阶是奇数,那么通过求2的逆元可以很快算出 PPP,但阶是偶数情况要如何处理? 解决方法 通过查阅相关资料 finite field - Elliptic Curve - Divide by 2 - C 2023-10-31 knowledge #Math
CRC 本文主要介绍CRC的定义,以及CRC的相关变种。 CRC 循环冗余校验(英语:Cyclic redundancy check,通称“CRC”)是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。 CRC的一个重要性质是仿射函数。确切的说,CRC(x⊕y)=CRC(x)⊕CRC(y)⊕c\mathrm{CRC}(x\opl 2023-10-30 knowledge #Math
Dual RSA 本文主要介绍ACTF2023中的MidRSA一题。 首先介绍一下什么是 Dual RSA 和 Common private exponent RSA。 Dual RSA 对偶 RSA 是指对于一副公钥 eee 和 ddd 满足: ed=k1(N1−p1−q1+1)+1ed=k2(N2−p2−q2+1)+1ed=k_1(N_1-p_1-q_1+1)+1\\ ed=k_2(N_2-p_2-q_2+1) 2023-10-30 knowledge #RSA
Noisy Chinese remaindering Noisy Chinese remaindering 本文主要介绍 noisy Chinese remaindering 问题,以及在SekaiCTF中的一道相关的题目。 问题重述 Problem (Noisy Chinese remaindering): 令 0≤N≤B0\le N\le B0≤N≤B,且 p1,⋯ ,pnp_1,\cdots,p_np1,⋯,pn是互素的整数。给定nnn个 2023-08-28 knowledge #Math
RSA construct 函数漏洞 本文整理了国赛Ciscn两道利用RSA.construct函数漏洞的题目 Ciscn-badkey1 123456789101112131415161718192021222324252627282930313233signal.alarm(10)print("Give me a bad RSA keypair.")try: p = int(input('p = 2023-05-30 knowledge #RSA
ahssp d3pack is a crypto challenge I made in d3ctf. d3pack This challenge is based on the affine hidden subset sum problem[1]^{[1]}[1]. Given h,e,p\mathbf{h},\mathbf{e},ph,e,p satisfying h+se=α1x1+α1x1+⋯+α1 2023-02-25 knowledge #lattice
NTRU attack NTRU 常见攻击 本文总结了几种NTRU攻击,包括经典格攻击、多次加密同一明文攻击。 NTRU加密流程 有些时候 h=p∗Fq∗gh=p*F_q*gh=p∗Fq∗g,e≡r∗h+m (mod q)e \equiv r*h+m \;(mod\;q)e≡r∗h+m(modq) ,如果这样做,ppp 理论上可以不公开。 条件 q>(6d+1)pq>(6d+1)pq>(6d+1 2023-01-26 knowledge #lattice
Half-GCD 整数内环多项式求GCD sage 自带的多项式GCD方法对大数环会报错,下面是Half-GCD的代码,对此进行了实现: 123456789101112131415161718192021222324252627282930313233343536# https://github.com/rkm0959/rkm0959_implements/tree/main/Half_GCDdef HGCD(a, 2023-01-24 knowledge #Math