Quiz from bzb
前言&题目
前段时间学习信安数基，助教学长就配套出了道Quiz，来给我们练手。
先上题目
import math
from AITMCLab.Crypto.Util.number import long_to_bytes
from AITMCLab.Crypto.Util.number import bytes_to_long
from AITMCLab.Crypto.Util.number import getRandomNBitInteger
from AITMCLab.Crypto.Util.number import getPrime
from AITMCLab.Crypto.Util.number import isPrime
from AITMCLab.Crypto.Util.number import inverse
from secret import flag
def nextPrime(n):
n += 2 if n & 1 else 1
while not isPrime(n):
n += 2
return n
def init(S, K):
j = 0
k = []
K = list(K)
for i in range(len(K)):
K[i] = ord(K[i])
for i in range(256):
S.append(i)
k.append(K[i % len(K)])
for i in range(256):
j = (j + S[i] + k[i]) % 256
S[i], S[j] = S[j], S[i]
def Encrypt(key, D):
S=[]
init(S, key)
i = j = 0
result = ''
for a in D:
a = ord(a)
i = (i + 1) % 256
j = (j + S[i]) % 256
S[i], S[j] = S[j], S[i]
k = chr(a ^ S[(S[i] + S[j]) % 256])
result += k
return result
def Decrypt(key, D):
S = []
init(S, key)
i = j = 0
result = ''
for a in D:
a = ord(a)
i = (i + 1) % 256
j = (j + S[i]) % 256
S[i], S[j] = S[j], S[i]
k = chr(a ^ S[(S[i] + S[j]) % 256])
result += k
return result
if __name__ == "__main__":
key = long_to_bytes(getRandomNBitInteger(100))
print 'key =', bytes_to_long(key)
e = getPrime(512)
print 'e =', e
E = nextPrime(e)
f = math.factorial(e) % E
d = long_to_bytes(f)
c1 = bytes_to_long(Encrypt(key, d))
print 'c1 =', c1
c2 = bytes_to_long(Encrypt(key, flag))
print 'c2 =', c2
# e = 11248112333656902878308992204660514716130692202019193081806766887380465145401754698746718075268681481388695805324253817155823465013590321091178897918430457
# c1 = 11792816667683654209610238149228683194178884298019505853565076663183883681365400495420305428570416004628438524072440231323696408946395141935772862600031614
# c2 = 81946333492800053045881242964212560642046177081574600318494251620269838444004879162713842
思路
首先阅读主函数部分，显然这道题需要先通过e, E求解f，以此得到d，随后再利用d, c1, c2来求解flag。
求解f
题目中的 $f=e!\mathrm{mod} E$ ，但由于 e 过大，显然无法直接计算得到。观察发现，$e!$ 当中的绝大多数部分可以两两配对组成模 $E$ 的逆元，因此猜测可能存在类似于 $(E-1)!\equiv 1\ (\mathrm{mod}\ E)$ 的规律，如果满足这个规律，我们就可以通过计算 $\prod\limits_{i=e+1}^{E-1}i\ (\mathrm{mod}\ E)$ 的逆元得到f。
经过几次简单的检验，猜测规律为 $(E-2)!\equiv 1\ (\mathrm{mod}\ E)$ （后得知为Wilson定理，当时还没学…），因此只需要计算$tmp\equiv \prod\limits_{i=e+1}^{E-2}i\ (\mathrm{mod}\ E),\ f\cdot tmp\equiv 1\ (\mathrm{mod}\ E)$ 即可得到 $f$。
求解flag
得到了 f 后，可以直接利用 long_to_bytes(f) 来得到 d 。为求解 flag，初步设想为利用加密函数求解 key，随后直接利用解密函数求解 flag。阅读 Encrypt 函数和 Decrypt 函数后发现加解密函数完全一致，且实际的加解密过程只有异或运算，说明 d 到 c1 的运算步骤与 flag 到 c2 的运算步骤完全相同且可逆，因此求解时没必要求出 key。进一步分析后发现加密算法大致是将 key 转化成某个固定的数组，并与明文依次进行异或运算得到密文，也就是说经过了 init 函数和多次交换位置（交换的次序也是固定的）后的数列才是真正的密钥。
因此，只需要将 c1, c2 和 d 转换成 bytes，然后对每一位取 ord 后进行异或运算，组成的数字取 chr 后加到答案字符串后面，即可得到 flag。
exp
import math
from AITMCLab.libnum.modular import invmod
from AITMCLab.Crypto.Util.number import long_to_bytes
from AITMCLab.Crypto.Util.number import bytes_to_long
from AITMCLab.Crypto.Util.number import isPrime
def nextPrime(n):
n += 2 if n & 1 else 1
while not isPrime(n):
n += 2
return n
if __name__ == "__main__":
e = 11248112333656902878308992204660514716130692202019193081806766887380465145401754698746718075268681481388695805324253817155823465013590321091178897918430457
c1 = 5120829596353532760839054347975234579355835073413768618360492980516438193909447500996222328143719619379838946544412967584025416378147246422705451415437468
c2 = 17985907282297772406857113433926323639543183645704827789984971602150950301590677893419082
E = nextPrime(e)
f_1 = 1
i = e + 1
while i < E - 1:
f_1 *= i
f_1 %= E
i += 1
f = invmod(f_1, E)
# 以上为求解f的过程
d = long_to_bytes(f)
c1_bytes = long_to_bytes(c1)
c2_bytes = lone_to_bytes(c2)
flag = ""
for i in range(len(c2_bytes)):
flag += chr(ord(c2_bytes[i]) ^ ord(c1_bytes[i]) ^ ord(d[i]))
print flag
# flag{Congratulation!_quiz1_passed!!!}
[DAS2020 April]not RSA
题目
from AITMCLab.libnum import gcd, invmod, s2n
from Crypto.Util.number import isPrime
from secret import flag
p = 104879397075344024438671231239628115011303349344697797964879592144922079000957
q = 104879397075344024438671231239628115011303349344697797964879592144922079001013
assert isPrime(p) and isPrime(q)
n = p * q
flag = s2n(flag)
r = randint(1, n)
c = (pow(n + 1, flag, n * n) * pow(r, n, n * n)) % (n * n)
print c
# c = 13134489820394613222282607681686272081419875146946401883172682167011759113388373349180457979897848113275982219264879081189886853062717764580364698888338032141434053832247476010400449272010082460437747190468766740274587999336359171283098137261396013153130265440425676242061845667887640808895666325466803989428
思路
代码很简单，就是道纯数学题
由源码：
$c\equiv (n+1)^f\cdot r^n\ (\mathrm{mod}\ n^2)$
根据二项式定理：
$c\equiv (fn+1)\cdot r^n\ (mod\ n^2)$
左右两式同乘 $\varphi(n)$ 次方，得 $c^{\varphi(n)}\equiv (fn+1)^{\varphi(n)}\cdot r^{n\varphi(n)}\ (mod\ n^2)$
由 $\varphi(n^2)=n\cdot \varphi(n)$ 且当 $r\neq p$ 或 $r\neq q$ 时有，$gcd(r,n)=1$ 可知，$r^{n\varphi(n)}\equiv 1\ (mod\ n^2)$，可得：
$c^{\varphi(n)}\equiv (fn+1)^{\varphi(n)}\ (mod\ n^2)$
因为 r 为随机数，所以 $r\neq p,q$ 的概率为 $\dfrac{2}{n}$，可认为 $gcd(r,n)=1$ 成立。
再次使用二次项定理，可得 $c^{\varphi(n)}\equiv fn\varphi(n)+1\ (mod\ n^2)$
由费曼小定理可知 $c^{\varphi(n)}\equiv 1\ (mod\ n)$，即 $n|c^{\varphi(n)}-1$，因此将1移到同余式左边并对同余式同除n，得：
$\dfrac{c^{\varphi(n)}-1}{n}\equiv f\varphi(n)\ (mod\ n)$
对于左式，设 $\dfrac{c^{\varphi(n)}-1}{n}=kn+r'$
$c^{\varphi(n)}=kn^2+rn+1$
只需求解出 $rn+1$ 即可，因此可以对 $c^{\varphi(n)}$ 进行模 $n^2$，实现时可直接使用 python 中的 pow 函数。
将左式求解后，化为求解 $\varphi(n)\cdot f\equiv r’\ (mod\ n)$，即 $f\equiv \varphi(n)^{-1}\cdot r’\ (mod\ n)$
代码
from AITMCLab.libnum import s2n, invmod, n2s
c = 131344898203946132222826076816862720814198751469464018831726821670 117591133883733491804579798978481132759822192648790811898868530627 177645803646988883380321414340538322474760104004492720100824604377 471904687667402745879993363591712830981372613960131531302654404256 76242061845667887640808895666325466803989428
p = 104879397075344024438671231239628115011303349344697797964879592144 922079000957
q = 104879397075344024438671231239628115011303349344697797964879592144 922079001013
phi_n = (p - 1) * (q - 1)
n = p * q
r = (pow(c, phi_n, n * n) - 1) // n
print n2s(r * invmod(phi_n, n) % n)
# flag{can_you_find_me??}
总结
纯数学题
学长带着推了一遍。。。这也太难了。。。
听说是 paillier 加密，果然是 not RSA
[N1CTF2019]BabyRSA
题目
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
while m:
padding = random.randint(0, 2**1000) ** 2
message = padding << 1 + m % 2
cipher = pow(message, e, N)
f.write(hex(cipher)+'n')
m /= 2
思路
首先阅读代码。
while m:
# several operations
m /= 2
由上述代码部分以及过程中出现了 m % 2 操作可知，flag 的二进制数据每一位被存进了 key.enc 文件的每行数据中，因此对 key.enc 文件的每一行进行读取，只要能够判断该位为0还是1，即可完成解密。
padding = random.randint(0, 2**1000) ** 2
message = padding << pow(m, p - 1, p) + m % 2
cipher = pow(message, e, N)
由上述代码可知，$c\equiv m^e\ (\mathrm{mod}\ N), m = r^2\cdot 2^{1+flag%2}$ （r为random结果），因此 m % 2 = 1 时，有$c\equiv r^2\cdot 2^2\equiv (2^er^e)^2\ (\mathrm{mod}\ N)$，而 m % 2 = 0 时，有$c\equiv 2^e\cdot r^{2^e}$。
首先猜测可以通过破解RSA密码，将加密信息还原为明文信息，判断该数整除 2 的奇数次方还是偶数次方即可得知该位的二进制数。使用 factordb 网站失败后贼心不死，又尝试了网上找的多种攻击脚本，发现均无法分解，于是寻找其它方法。
观察README.md发现，本题可以尝试用二次剩余求解。m % 2 = 1 时，有 $c\equiv (2^er^e)^2\ (\mathrm{mod}\ N)$，m% 2 = 0 时，有 $c\equiv (2\cdot r^2)^e\ (\mathrm{mod}\ N)$，因此，当 c 为 N 的二次剩余时，对应m % 2 = 1，c 为 N 的二次非剩余时，对应 m % 2 = 0。
可以使用 Jacobi 判断是否为二次剩余。只需满足 $\left(\dfrac{2^e\cdot r^{2^e}}{N}\right)=-1$ 即可求解。由于 $\left(\dfrac{2^e\cdot r^{2^e}}{N}\right)=\left(\dfrac{2}{p}\right)\left(\dfrac{2}{q}\right)$，所以当 m % 2 = 0 时，Jacobi 计算结果仅取决于 p 和 q，且在实际计算中发现存在 Jacobi 计算结果为 -1 的情况，又因为 m % 2 = 1 时 Jacobi 计算结果必然为 1，说明本题中 2 分别是 p 和 q 的二次剩余和二次非剩余，可得
当 $m\equiv 0\pmod 2$，$\left(\dfrac{c}{N}\right)= \left(\dfrac{2}{p}\right)\left(\dfrac{2}{q}\right)=-1$
当 $m\equiv 1\pmod 2$，$\left(\dfrac{c}{N}\right)= 1$
因此可以用 Jacobi 来计算 flag 的二进制结果。
exp
from AITMCLab.Crypto.Util.number import long_to_bytes
def jacobi(a, b):
res = 1
if a == 2:
return (-1) ** ((b * b - 1) / 8)
if a == b - 1:
return (-1) ** ((b - 1) / 2)
if a == 1:
return 1
while a % 2 == 0:
res *= jacobi(2, b)
a /= 2
res *= (-1)**((a - 1) * (b - 1) / 4) * jacobi(b % a, a)
return res
n = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
flag = 0
i = 0
with open('key.enc', 'r') as f:
for line in f:
line = line.strip("L\n") # Filter out "L\n" at the end of line
cur = int(line, 16) # Convert hax string to number
if (jacobi(cur, n) == 1):
flag += 1 << i
i += 1
print flag
print flag
print long_to_bytes(flag)
# N1CTF{You_can_leak_the_jacobi_symbol_from_RSA}
首先从key.enc中逐行读取，并对每一行结尾的’L\n’进行过滤，将其转换为整数cur后，计算Jacobi符号$J\left( cur, N\right)$。计算Jacobi符号时主要使用二次互反律进行计算（可以再使用其它定律进行加速，但没必要）。
由于第一行储存的为flag的最后一位（即从后往前储存），因此进行flag += 1 << i即可将相应位置的二进制结果还原。
总结
这道题在代码阅读上难度较低，唯一需要留意的地方就是padding << pow(m, p - 1, p) + m % 2这个运算的优先级问题（感谢bg的注释提示）。把代码转换成数学公式后，二次剩余的方法就比较明显了，需要注意的是Jacobi符号无法准确判断二次剩余与二次非剩余（感谢bg指出了这个问题），简单推导后发现这个方法有一定的使用条件，如果题目中的p和q不满足一定的条件，这个方法就无法正确区分0和1。
后经 ssgss 师傅提醒发现这道题用的是 Goldwasser-Micali 密码（上课走神实锤了）。简单对比发现，当GM密码选取的x满足
J(x, p) = 1且J(x, q) = -1时，可能能够利用本题的方法进行破解。因此选取的 x 不能仅满足是 n 的二次非剩余，需要同时是 p 和 q 的二次非剩余。