[Python知识库]DASCTF八月挑战赛_Crypto_复现

easymath

$keywords:$ 位移运算，模运算中逆元与模数非互质情况

$Description$

assert(len(open('flag.txt', 'rb').read()) < 50)
assert(str(int.from_bytes(open('flag.txt', 'rb').read(), byteorder='big') << 10000).endswith(
   '1862790884563160582365888530869690397667546628710795031544304378154769559410473276482265448754388655981091313419549689169381115573539422545933044902527020209259938095466283008'))

$Analysis$

首先明确flag长度小于$50$，也就是说大概给出了flag的数值范围

然后已知一个这样的式子$c\equiv flag?2^{10000}(\mathrm{m}\mathrm{o}\mathrm{d}10^{175})$

为什么可以有这样一个式子呢？

首先位移运算就相当于乘以$2^n$；然后endwith()函数给出数字末尾的数值，那么就相当于模掉这个数值的长度（是$10$进制的长度）

可以看出我们只需要知道$2^{10000}$对于模数$10^{175}$的逆元即可

而这两者是非互质的，所以不能直接求解，但是我们可以通过把模数进一步减小达到两者互质的条件

在原来式子的基础上再取模$5^{175}$，此时式子变为$c\equiv flag?2^{10000}(\mathrm{m}\mathrm{o}\mathrm{d}{5}^{175})$

直接求逆元乘以$c$解flag即可

$Solvingcode$

from Crypto.Util.number import *
import gmpy2

c = 1862790884563160582365888530869690397667546628710795031544304378154769559410473276482265448754388655981091313419549689169381115573539422545933044902527020209259938095466283008
# print(len(str(c)))
# print(gmpy2.invert(2**10000,5**175))
flag = c * gmpy2.invert(2**10000,5**175) % pow(5,175)
print(long_to_bytes(flag))

let’s play with rsa~

$keywords:$ 毫无难点的rsa

$Description$

from sympy import isprime,nextprime
from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
flag='flag{***************}'

def play():
    p=getprime(1024)
    q=getprime(1024)

    n=p*q
    e=65537

    print "Hello,let's play rsa~\n"
    print 'Now,I make some numbers,wait a second\n'
    n1=getprime(200)
    n2=getprime(200)
    number=n1*n2
    print "Ok,i will send two numbers to you,one of them was encoded.\n"
    print "Encode n1:%d,\n"%(pow(n1,e,n))
    print "And n2:%d.\n"%n2

    print "Information that can now be made public:the public key (n,e):(%d,%d)\n"%(n,e)
    while True:
        try:
            c=int(raw_input("ok,now,tell me the value of the number (encode it for safe):"))
        except:
            print "Sorry,the input is illeagal, and the integer is accept~"
        else:
            break
    d=inverse(e,(p-1)*(q-1))
    m=pow(c,d,n)
    if m==number:
        print "It's easy and interesting,didn't it?\n"
        print "This is the gift for you :"+flag
    else:
        print "Emmmmm,there is something wrong, bye~\n"

if __name__ == '__main__':
    play()

$Analysis$

题目要求传递的是密文$c$，只要该密文解密之后得到的明文等于$n_1?n_2$即可

而我们已知$c_1\equiv n_1^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$；以及$n_2$

求$c\equiv (n_1?n_2{)}^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$

拆开也就是$c\equiv c_1?n_2^e(\mathrm{m}\mathrm{o}\mathrm{d}n)$

同余式左边参数都已知，那么直接代入就好了

$Solvingcode$

from Crypto.Util.number import *
import gmpy2
from pwn import *

io = remote("node4.buuoj.cn","27103")
io.recvuntil(b"n1:")
c1 = int(bytes.decode(io.recvuntil(b",")[:-1]))
# print(c1)
io.recvuntil(b"n2:")
n2 = int(bytes.decode(io.recvuntil(b".")[:-1]))
# print(n2)
io.recvuntil(b':')
temp = io.recvline()
# print(temp.split(b':'))
temp2 = temp.split(b":")[1]
n, e = int(bytes.decode(temp2.split(b",")[0][1:])), int(bytes.decode(temp2.split(b",")[1][:-2]))
# print(n,e)

c = c1 * pow(n2,e,n) % n
io.recvuntil(b":")
io.sendline(str(c).encode())
io.interactive()

ezRSA

$keywords:$ 同余式的转换

$Description$

from secret import flag
from Crypto.Util.number import *
from random import getrandbits
from hashlib import sha256


class EzRsa:
    def __init__(self):
        self.E = 0x10001
        self.P = getPrime(1024)
        self.Q = getPrime(1024)
        while GCD((self.P-1)*(self.Q-1), self.E) != 1:
            self.Q = getPrime(1024)
        self.N = self.P*self.Q

    def encrypt(self):
        f = getrandbits(32)
        c = pow(f, self.E, self.N)
        return (f, c)

    def encrypt_flag(self, flag):
        f = bytes_to_long(flag)
        c = pow(f, self.E, self.N)
        return c


def proof():
    seed = getrandbits(32)
    print(seed)
    sha = sha256(str(seed).encode()).hexdigest()
    print(f"sha256({seed>>18}...).hexdigest() = {sha}")
    sha_i = input("plz enter seed: ")
    if sha256(sha_i.encode()).hexdigest() != sha:
        exit(0)


if __name__ == "__main__":
    proof()
    print("welcome to EzRsa")
    print("""
    1. Get flag
    2. Encrypt
    3. Insert
    4. Exit
    """)
    A = EzRsa()
    coin = 5
    while coin > 0:
        choose = input("> ")
        if choose == "1":
            print(
                f"pow(flag,e,n) = {A.encrypt_flag(flag)}\ne = 0x10001")
            exit(0)
        elif choose == "2":
            f, c = A.encrypt()
            print(f"plain = {f}\ncipher = {c}")
            coin -= 1
        elif choose == "3":
            q = getrandbits(1024)
            n = A.P*q
            f = getrandbits(32)
            c = pow(f, 0x10001, n)
            print(f"plain = {f}\ncipher = {c}")
            coin -= 1
        elif choose == "4":
            print("bye~")
        else:
            print("wrong input")
    print("Now you get the flag right?")

$Analysis$

proof函数，从来没有遇到过这么无语的proof函数

直接把程序打印出来的seed再提交上去就好了

def proof():
    seed = getrandbits(32)
    print(seed)

然后分析主程序

分为三个功能：Get flag，Encrypt，Insert

分别是得到flag的密文c_flag；得到一组明文及密文plaint1,cipher1（以$(n,e)$作为公钥）；得到一组明文及密文plaint2,cipher2（以$(p?q_{other},e)$作为公钥）

总共可以执行$5$次上述功能；此时对于flag的RSA加密，我们只知道$e$的大小

很快分析出，Encrypt一定是用来求得$n$的，Insert一定是用来求得$p$从而把$n$分解的

两个功能的加密过程是相似的，猜测两个功能都要分别执行两次

推导：Encrypt功能
$$\{\begin{array}{l}plain{t}_1^e=c_1(\mathrm{m}\mathrm{o}\mathrm{d}n)\\ plain{t}_2^e=c_2(\mathrm{m}\mathrm{o}\mathrm{d}n)\end{array}$$
$$?\{\begin{array}{l}plain{t}_1^e?c_1=k_1?p?q\\ plain{t}_2^e?c_2=k_2?p?q\end{array}$$

同余式左侧的参数我们都已知，那么两者的最大公约数一定整除$n$，因为可能$k_1$和$k_2$之间也有公约数，所以两者的最大公约数不直接等于$n$

我们得到
$$n\mid gcd(plain{t}_1^e?c_1,plain{t}_2^e?c_2)$$
而他们之间的倍数很小（等于$k_1$和$k_2$的最大公约数，所以可以直接爆破$1000$以内的数作为倍数）

Insert功能
$$\{\begin{array}{l}plain{t}_3^e\equiv c_3(\mathrm{m}\mathrm{o}\mathrm{d}p?q_{other1})\\ plain{t}_4^e\equiv c_4(\mathrm{m}\mathrm{o}\mathrm{d}p?q_{other2})\end{array}$$

$$?\{\begin{array}{l}plain{t}_3^e?c_3=k_3?p?q_{other3}\\ palin{t}_4^e?c_4=k_4?p?q_{other4}\end{array}$$

和Encrypt的分析过程一致，可以得到
$$p\mid gcd(plain{t}_3^e?c_3,plain{t}_4^e?c_4)$$
其中两者的倍数大小依然是等于$k_3$和$k_4$的最大公约数

$Solvingcode$

from Crypto.Util.number import *
from pwn import *
import gmpy2

io = remote("node4.buuoj.cn","29721")
seed = int(bytes.decode(io.recvline()))
# print(seed)
io.recvuntil(b":")
io.sendline(str(seed).encode())

e = 65537
plaint1 = []
cipher1 = []
for _ in range(2):
    io.recvuntil(b">")
    io.sendline(b"2")
    io.recvuntil(b'=')
    plaint1.append(int(bytes.decode(io.recvuntil(b"\n")[:-1])))
    io.recvuntil(b"=")
    cipher1.append(int(bytes.decode(io.recvuntil(b"\n")[:-1])))
# print(plaint1)
# print(cipher1)

n = gmpy2.gcd(plaint1[0]**e - cipher1[0],plaint1[1]**e - cipher1[1])
k = 2
while True:
    if n % k == 0:
        n = n // k
        k = 2
        continue
    else:
        k += 1
    if k > 1000:
        break
# print(n)

plaint2 = []
cipher2 = []
for _ in range(2):
    io.recvuntil(b">")
    io.sendline(b"3")
    io.recvuntil(b'=')
    plaint2.append(int(bytes.decode(io.recvuntil(b"\n")[:-1])))
    io.recvuntil(b"=")
    cipher2.append(int(bytes.decode(io.recvuntil(b"\n")[:-1])))
# print(plaint2)
# print(cipher2)
p = gmpy2.gcd(plaint2[0]**e - cipher2[0],plaint2[1]**e - cipher2[1])
k = 2
while True:
    if p % k == 0:
        p = p // k
        k = 2
        continue
    else:
        k += 1
    if k > 1000:
        break
# print(p)

assert n % p == 0
q = n // p
fai_n = (p-1)*(q-1)
d = gmpy2.invert(e,fai_n)

io.recvuntil(b">")
io.sendline(b'1')
io.recvuntil(b"=")
c_flag = int(bytes.decode(io.recvuntil(b"\n")[:-1]))

flag = pow(c_flag,d,n)
print(long_to_bytes(flag))

io.close()