Dawn_whisper's blog

LCG发现自己没有整过线性同余生成器的东西，今天专门来总解一下 参考资料 1、线性同余生成方法设A,B,M是一定常数，按照递推公式 $state_{i+1}=(A\times state_i+B)\pmod{M}$ ，其中A称为乘数(multiplier)，B称为增量(increment)，M称为模数(modulus) LCG的生成周期理论上应该是M，但大部分情况下会小于M，如果想要追求LCG的最大周期，应符合以下几个条件： A与B都是正整数 A、B、N[0]都比M要小 B与M互质 M的所有质因数都能整除A-1 2、攻击方法我们把state均简称为s 1、B未知只需获取中间的两个状态值 1s_1 = (s_0*A+B)%M 显然 $B = s_1 - s_0\times a\pmod{M}$ 2、A与B未知只需获取中间的三个状态值 12s_1 = (s_0*A+B)%Ms_2 = (s_1*A+B)%M 线性方程，解起来还是挺简单的 显然 $A = \frac{s_2-s_1}{s_1-s_0}\pmod{M}$ ，于是就转化成了问题1了 3、 ...

Discrete logarithm problem发现自己只是知道离散对数很难求，而且自己拿这玩意也没办法，专门来学一下带老婆问题 基本定义生成元​ 在一个群 G 中，如果 g 是 G 的生成元，即所有 G 中的所有元素都可以被表示成 $y = g^x$ ，此时的 x 我们称为 y 在 G 中的对数 阶​ 设 $m\geq 1$ ， $gcd(a,m)=1$ ，使得 $a^d=1\pmod{m}$ 成立的最小正整数 d 称为 a 对模 m 的指数或者阶，我们一般将其记为 $\delta_m(a)$ ​ 另：满足 $a^d=1\pmod{m}$ 的d一定满足 $d\mid\varphi(m)$ 原根​ 当 $\delta_m(a)=\varphi(m)$ 时，称 a 是模 m 的原根，简称 m 的原根 ​ 只有 $m=2,4,p^\alpha,2p^\alpha （p为奇素数，\alpha为正整数）$ 时，模 m 的剩余系存在原根（充要条件） 离散对数暴力枚举万物皆可暴力 1234def ForceDLP(A,B,P): ...

A study for MT19937寒假前被一个伪随机数卡了，终于有时间来看看 前言如前文，不会就得学（悲 参考博客 MT19937​ MT19937是许多语言的默认伪随机数生成器，其优点为：周期非常长（达到 $2^{19937}-1$ ）、在 $1\leq k\leq 623$ 的维度之间都可以均等分布、速度较快。 ​ MT19937算法主要分为三个部分： 1231、基础的梅森旋转链2、输出处理算法（Tamper）3、旋转链的旋转算法（Twist） python中Random类采用MT19937算法，getrandbits(32)返回一个32位随机数，详细代码如下： 1234567891011121314151617181920212223242526272829def _int32(x): return int(0xFFFFFFFF & x)class MT19937: def __init__(self, seed): self.mt = [0] * 624 self.mt[0] = seed self.mti ...

WP for *ctf2021第一次和V&N的师傅们打比赛就冲到了第六，好耶！ 最后没AK，不好（悲） Weblottery again看源码，找关键代码 加密部分 解密部分 兑换彩票部分 分析函数可以发现在兑换彩票的时候，会对彩票密文进行解码，通过解码得到的彩票lottery内容从数据库中找到对应数据，取得可兑换的coin数量，并把coin加到解码得到的user账号的硬币中。 分析代码可知，从密文中取得的user账号没有与在数据库中的信息进行验证，故如果我们可以篡改密文中对应的user信息，那么就可以让a用户购买的彩票，给b用户使用，从而让b用户达到白嫖的目的。 我们发现加密方式为MCRYPT_RIJNDAEL_256，ECB模式，通过手动测试发现该算法的分组方式为32字节为一组，在这样的前提下，我们可以尝试替换储存在其中的user数据。 以下来逐步分析如何替换全部user-uuid信息 我们已有的密文数据是： 1234{"lottery":"b52d5239-24a5-4627-ba46-58a00645c3e4" ...

Wp for 华为XCTF2020鸿蒙计算专场’s crypto RRSSAA题目分三个level，加密了三次，我们反过来解密就好了 level3观察e的生成代码，发现存在 $e=4\times (1+k\times (p-1))+3$ 这一关系，即 $e=7+k\times(p-1)$ ，所以由费马小定理有 $m^e=m^7\ (mod\ p)$ ，所以可知 $p\mid m^e-m^7$ ，那么可以算出 $p=gcd(m^e-m^7,n)$ level2因为t = next_prime(o) u = next_prime(s)，所以p1q1、p1q2、p2q1、p2q2都比较相近，联想费马分解，因为 $n=x^2-y^2=(x+y)\times(x-y)=a\times b$ ，所以我们使用费马分解在 $\sqrt{n}$ 附近寻找x并计算y，而此时我们得到的 (x,y) 则是p1q1与p2q2、p1q2与p2p1、p1p2与q1q2中的其中一个，那当我们得到两组合法的(x,y)后，即可通过gcd来得到p1,p ...

Wp for SWPUTF2020's Crypto很无语，T1刚开始数据给错，T2T3连不上，活活让人等到中午才更新 Happy基础RSA，题目给出 $q+q\cdot p^3$ 和 $q\cdot p+q\cdot p^2$ 我们简记为 $data_1$ 与 $data_2$ ，那么显然有 $data_1=q\cdot(p^3+1)$ 、 $data_2=q\cdot(p^2+p)$ 、 $data_1+3\cdot data_2=q\cdot(p^3+3p^2+3p+1)=q\cdot(p+1)^3$ 且 $gcd(data_1,data_2)=q\cdot(p+1)$ ，那么显然可得 $p=\sqrt{ \frac{data_1+3\cdot dota_2}{gcd(data_1,data_2)}}-1$ ，随后可得 $q=\frac{data_1}{p^3+1}$ 然后RSA相关的数据都有了，直接解密即可 1234567891011121314151617181920from Crypto. ...

Wp for C1CTF2020's Crypto先放一句话role=Tsunate; 题目倒是蛮好玩的 Base的千层套路拿到的是一个base编码后的结果，写个脚本一直解码，最后得到flag c1ctf{Ba5e_3nc0ding_i5_e4sy} PigIsSoCute题目给了一个piggggggg.txt，打开是base64编码的一个图片，在线转换一下得到一个图片 猪圈密码解一下得到一个字符串，根据题目描述尝试栅栏后得到一个有意义的字符串 c1ctf{pigissocutebutporkissoexp} ezrsa刚开始看到 $e=3$ ，而且三个密文都一样，并且比 $n$ 小得多，尝试直接开三次方后无果，其实是出题人自己把数据给错了，给的c根本就不是立方，直接就是flag。 后来更新了附件， $c$ 和 $n$ 大小差不多，但是给了三次加密，拓展欧几里得合并一下就有了 MITM刚开始出题人把题目名称写错了哈哈哈哈哈 既然是中间人攻击，那么我们就应该在与A交互时伪装成B，在与B交互时伪装成A 过了pow之后给了 $g$ 和 $p$ ，这里 ...

Wp for NCTF2020's Crypto题目很难，嗯，就是很难 题目质量（我啥也不会也不敢评论） 我是废物！（大声） RRSA签到题，看完代码后发现是共膜，而且可以拿五次c，exgcd解决即可 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364from string import digits, ascii_lettersfrom pwn import *from hashlib import sha256from Crypto.Util.number import *from gmpy2 import *table = '1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'r = remote("42.192.180.50", "30002")de ...

数论笔记垃圾Dawn_whisper的数论学习史 同余费马小定理 设 $a$ 为整数， $p$ 为质数，则 $a^{p-1}\equiv 1\ (mod\ p)$ 可写为 $a^p\equiv a\ (mod\ n)$ 可用于求逆元 $a*a^{p-2}\equiv 1\ (mod\ p)$ gcd相关 $gcd(a,b)=gcd(b,a)$ $gcd(a,b)=gcd(a-b,b)\ (a\geq b)$ $gcd(a,b)=gcd(a\ % \ b,b)$ $gcd(a,b,c)=gcd(gcd(a,b),c)$ $gcd(a,0)=a$ $lcm(a,b)=\frac{a\times b}{gcd(a,b)}$ 拓展欧几里得考虑方程 $a\cdot x+b\cdot y=c$ ，a、b、c都是已知正整数 方程有解的充要条件为 $gcd(a,b)|c$ 简化问题：考虑方程 $a\cdot x+b\cdot y=gcd(a,b)$ ，它的解为 $$\begin{cases}x=x_ ...

Many time pad attack前言看到了 2020HGAME week1 里的一道题，随手复现一下 题目懒得搭docker部署服务器了，就自己写个函数调用着假装交互 1234567891011121314151617181920import osimport randomimport stringimport binasciiimport base64from flag import flagflag = flag.encode()assert flag.startswith(b'flag{') and flag.endswith(b'}') flag_len = len(flag)def xor(s1, s2): #assert len(s1)==len(s2) return bytes(map((lambda x: x[0] ^ x[1]), zip(s1, s2)))def get_data(): random.seed(os.urandom(8)) keystream =  ...