piece_of_cake 两个函数大概都是一个类似 RSA 的操作，加上一个加密算法，之前的一篇博客有介绍， An Introduction to Mathematical Cryptography 书里称这个算法是 “a toy model of a real public key cryptosystem”。（bitlength 凑的刚刚好可以保证解密，很巧妙） make_cake()这边的cake很小（256bits）符合正常解密的条件，可以直接用高斯格基规约算法，然而eat_cake()这边的cake是比较大的（768bits）就会导致在取模的时候值容易发生改变，所以给它加上几个g，并使用给出的pow来验证是否是正确的cake。 规约得到的密钥对 $(F, G)$ 是不一定等于原来的密钥对 $(f, g)$，但它们在解密过程是等价的，我们得到的密钥对 长度都是 768bits。 exp 多跑几次就能得到 flag。 from gmpy2 import iroot, sqrt, invert from pwn import remote from string import ascii_letters, digits from hashlib import sha256 r = remote('170.106.35.18', 8631) def proof_of_work(txt, Hash): for a in ascii_letters+digits: for b in ascii_letters+digits: for c in ascii_letters+digits: if sha256((a+b+c+txt).encode()).hexdigest() == Hash: return a+b+c def gaussian(v1, v2): while True: if sqrt(v2[0]**2 + v2[1]**2) < sqrt(v1[0]**2 + v1[1]**2): v1, v2 = v2, v1 m = int((v1[0]*v2[0] + v1[1]*v2[1]) / (v1[0]**2 + v1[1]**2)) if m == 0: return (v1, v2) v2 = [v2[0] - m * v1[0], v2[1] - m * v1[1]] r.recvuntil("XXX+") nonce = r.recv(17).decode() r.recvuntil(" == ") target = r.recv(64).decode() r.recvuntil("\nGive me XXX:") w = proof_of_work(nonce, target) r.send(str(w)+"\n") r.recvuntil("What's your choice?\n") r.send("1\n") r.recvline() temp = r.recvline().strip().decode().split(" ") q, h, c = [int(i) for i in temp] N = int(r.recvline().strip().decode()) cip = int(r.recvline().strip().decode()) s1, s2 = gaussian([1, h], [0, q]) f, g = s1[0], s1[1] cake = (c * f % q) % g cake = invert(f, g) * cake % g for k in range(10000): if pow(cake, 0x10001, N) == cip: print("cake is: ", cake) break cake += g r.send(str(cake) + "\n") print(r.recvline().strip().decode()) #WMCTF{Wh4t_A_pi3ce_of_CAKE!} babySum 密度接近 0.8 的子集和问题（Subset sum problem），BKZ-24 跑得比较慢好在成功率高一点。 ...

Crypto RSA 同一个解密指数用了三次加密同一段明文，这本书第129页介绍了 Common Private Exponent Attack： CRYPTANALYSIS OF RSA AND ITS VARIANTS 这题的情况和里面的样例是一样的，可以直接套用这个格子然后LLL即可算出d： from binascii import hexlify, unhexlify e0 = 0x9a7dc3e0f2a3531035b18541df28b8407502c2101970862d19b107ea7dc37554e5ac620b3ce4be38e5d6fd6b1920aef9e017aa383e3c1dd8e7847dc7715832fa450d1b572cfe133c702c598ed022d40ad193608bcfeb9b9aebc910dd3257caa42e503764475b89bb99056822e21ba5723d9eee3196a6fca3debd1c7687fd310d n0 = 0xa98c363cf72b3bce39bae63a9d3d5ba0acaa7e81f9b1191ce20bb0b54a8c19216d20af640121c482e882c0772671280af9f42c764128a94104266dd65c0bcd93766e0f0ce119072302b7f3e5cc4b5cfece38e4124041a8f8dcbdb9193f35bede2c284e40f80398bf0ba0609229fa27faa2d51c552ff1ed911a6f6f220b7b6fed c0 = 0x57fcf94d27451fc35386e0f6eff53c6540ccff51862c992f4b59d0d49fa350493041c5be2f54a37f3afe81aa5e9a738461b3b709a4611a7289c83d769cb02f3c5d18e65d68f6fff1df0418c8a7351be1d7cce1a7514797c9bdc67d969224d783a5d004d67a5ef986d564ab1945e5c83a53d8d1dcb5e45323764a200e737b80c e1 = 0xbb31e6433057edfed88b6a37e4419a828d1575b2b9d04a5058cd912d5efb06b2f0c5c06c5d0dd35ebeda8afa8a9cc945c244c13fc501c76e720c2c04cab70c9f906c4a810defdd84c3a38507cdf79b4e4b0c7770cc3d2d862ea9bd5fe2469290d9d2a09c8164437e9d5b7b3a9c49d111e5caa9577f8ed1ef1916ec4cb71bbb8d n1 = 0xbcc2c4f4f51abb236b411f1f9d86d71133eb2d4ffe45a319b6ab6df1174b9ee619e696666702655b6c185735298cc008e9b7df842c480d3d42bb67228b6c7408a7afe68ab85ee1c80f43c8c52764c79ffdecc6e3a5ea76c1123affe9f02c649e5f5ca0a4082107ce4a2040e5756bf6a2b34757aefa5fb6fec6d7a9e86f0c8159 c1 = 0xacf91d2b6a300a60193485ef2e1127b5863c69da71ab9e7d71a3213e960a73e42f8e8031bf0ef20184ae0a259fd50260aacce06546af2f8bbef8a2f360c8f7511ad9c99d8715012ce0a4fa8dbba8c10d74f477156076bdfda80dc449eec3b45c7cd82802ecce7635e186d29744df04fcf812dc7e2d2f3c8cd751e4fcea43db1e e2 = 0x332f82f338c8b84524103d310d59fc541b66705948c57eaf972b26bb209a6ddde3d6930948a559ac1a3a26790cb1a133a90b999b164d4e22014b27660dad4e5639ffc19bcd2e4961c5b00b9116f49c3c02880bb3ad32972287442d6a86a9c86cd3981ee1084df4322edb9c5da39146e10de0586c8b5433a851d649a45c5a73cd n2 = 0xd0ad4d11576bb041ea2ce53f354dba362a93411a37f4a529e8b5eeae83a3437df6bd5e4e1f87a4d324a6ce2850f3568c929f5d5f73fef45bda03fa7bff00304a1eb833ce3535ee3552aa62b644f0d3c1679fe2c57b978c695f03e5b2d18d9b0821c7e0ca332f552b12e2b7109210d051bbe9d9b9e3cc3b16c81e77ebca65aca3 c2 = 0xc59078ae7cb454c970f272f595da71ae2b681156a1ce7112d9b96346f38bcdca87192ea39ac273851210e9f98f0d89f1bc657ce69ca14708cba8b319160a1f67b8cfc3643dc9b6a70769d8d64a9a3504d799f3d9afca7c7114880f4ccb5bef35738e660e4ede1c884f4a60f1f0e559fb754abd8e4b905ad3626a876bea43ec8e M = isqrt(max(n0, n1, n2)) M = 10704523536419069847275584063070587220303695362157261593514212717132031073368631333467085885236049291630529090309346493924305038011673707087598638071644281 B = matrix(ZZ, [ [M, e0, e1, e2], [0, -n0, 0, 0], [0, 0, -n1, 0], [0, 0, 0, -n2], ]) BL = B.LLL() temp = int(BL[0, 0]) if temp < 0: temp *= -1 d = int(temp // M) m = hex(pow(c2, d, n2))[2:] print(unhexlify(m)) print(d) #b'SCTF{673ff064da31c0d7aee56884b01a09}' #1235666648165896286568418878956456259719846117790808720561608081687435539909970845494445047046945948132187344353861 Lattice 这题是109维的NTRU加密，在An Introduction to Mathematical Cryptography书里有介绍使用格基规约攻击NTRU的算法，如图构建一个格子，然后进行约减，一开始用LLL，没有找到合适的约减基，然后用BKZ-24很容易找到了，可能由于格比较稀疏，尽管格子相当于是218维，测试了BKZ-32都可以在20秒之内规约完成，取约减后的最短向量，就得到了 $f’$ 和 $g’$（前 $n$ 位是 $f’$，后 $n$ 位 $g’$）。 ...

NLFSR task.py from flag import a, b, c, d, flag assert flag == "De1CTF{" + ''.join([hex(i)[2:] for i in [a, b, c, d]]) + "}" assert [len(bin(i)[2:]) for i in [a, b, c, d]] == [19, 19, 13, 6] ma, mb, mc, md = 0x505a1, 0x40f3f, 0x1f02, 0x31 def lfsr(r, m): return ((r << 1) & 0xffffff) ^ (bin(r & m).count('1') % 2) def combine(): global a, b, c, d a = lfsr(a, ma) b = lfsr(b, mb) c = lfsr(c, mc) d = lfsr(d, md) [ao, bo, co, do] = [i & 1 for i in [a, b, c, d]] return (ao*bo) ^ (bo*co) ^ (bo*do) ^ co ^ do def genkey(nb): s = '' for i in range(nb*8): s += str(combine()) open("data", "w+").write(s) genkey(128 * 1024) LFSR部分把r左移一位，m和r二进制值共同为1位数的奇偶决定空位补1或0。 ...

“not_RSA” in DASCTF 看了大佬的博客才知道是 Paillier cryptosystem，wtcl… 不过还是记录一下自己推导的解题过程 直接使用现成的 Paillier cryptosystem 解密算法解决这题非常容易，分解 n 然后直接套 decrypt 函数就解开了… 题目： from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse from secret import flag,p,q from sympy import isprime,nextprime import random m = bytes_to_long(flag) n = p * q g = n + 1 r = random.randint(1, n) c = (pow(g, m, n * n) * pow(r, n, n * n)) % (n * n) print('c =', c) print('n =', n) 主要加密过程是： ...

Notes for $An\ Introduction\ to\ Mathematical\ Cryptography$ “A toy model of a real public key cryptosystem” 这里以 An Introduction to Mathematical Cryptography 书中的一个简单的加密模型为例，简单介绍一下通过高斯格基规约算法（Gaussian Lattice Reduction）解决二维的格上的寻找最短向量问题。 最近在书中看到这个，刚好 西电新生赛@Mini L-CTF 有两个题目刚好是用这个模型实现的，当做例题写个 writeup。 task.py from Crypto.Util.number import bytes_to_long, getPrime, inverse from gmpy2 import iroot q = getPrime(1024) f = getPrime(511) g = getPrime(511) while g < iroot(q//4, 2)[0] or g > iroot(q//2, 2)[0]: g = getPrime(511) f_inv_q = inverse(f, q) h = f_inv_q * g % q m = bytes_to_long(b'flag') # flag is base**(flag) r = getPrime(510) e = (r * h + m) % q print(f) print(g) print(q) print(e) ''' f = 4685394431238242086047454699939574117865082734421802876855769683954689809016908045500281898911462887906190042764753834184270447603004244910544167081517863 g = 5326402554595682620065287001809742915798424911036766723537742672943459577709829465021452623299712724999868094408519004699993233519540500859134358256211397 q = 172620634756442326936446284386446310176482010539257694929884002472846127607264743380697653537447369089693337723649017402105400257863085638725058903969478143249108126132543502414741890867122949021941524916405444824353100158506448429871964258931750339247018885114052623963451658829116065142400435131369957050799 e = 130055004464808383851466991915980644718382040848563991873041960765504627910537316320531719771695727709826775790697704799143461018934672453482988811575574961674813001940313918329737944758875566038617074550624823884742484696611063406222986507537981571075140436761436815079809518206635499600341038593553079293254 ''' 其中私钥为 $(f, g)$ ，公钥为 $(q, h)$，已经给出了私钥，所以解密过程非常简单。 ...

模数两两互素时 from Crypto.Util.number import inverse from functools import reduce def crt(a, m): '''Return a solution to a Chinese Remainder Theorem problem. ''' M = reduce(lambda x, y: x * y, m) Mi = [M // i for i in m] t = [inverse(Mi[i], m[i]) for i in range(len(m))] x = sum([a[i] * t[i] * Mi[i] for i in range(len(m))]) return x % M 不满足模数两两互素时 这种情况有最小解 $x$ 满足条件，很多博客也讲的很详细，但是没找到 Python 写的… ...

HGAME 2020 week1 writeup Web Cosmos 的博客 看提示去 GitHub 上找这个网站的源代码，搜索 Cosmos Hgame 就可以找到，点开 3 commits，点开 new file 就可以看到： aGdhbWV7ZzF0X2xlQGtfMXNfZGFuZ2VyMHVzXyEhISF9 base64 解码得到 flag: hgame{g1t_le@k_1s_danger0us_!!!} Crypto InfantRSA 题目： p = 681782737450022065655472455411; q = 675274897132088253519831953441; e = 13; c = pow(m, e, p * q) = 275698465082361070145173688411496311542172902608559859019841 exp： p = 681782737450022065655472455411 q = 675274897132088253519831953441 e = 13 c = 275698465082361070145173688411496311542172902608559859019841 def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m d = modinv(e, (p - 1) * (q - 1)) m = pow(c, d, p * q) print(hex(m)) Affine 题目: ...