RSA 进阶 中

数论

二项式定理

费马小定理

基础练习

[金盾信安杯2023]babyrsa

题目：

#! /usr/bin/env python
from libnum import *
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from secret import p1, q1, p2, q2, e, d, flag, N
from random import randintdef round1(m):e = 10N = open('round1.txt', 'r').read()N = eval(N)c = []for n in N:c.append(pow(m, e, n))FILE = open('round1.txt', 'a+')FILE.write('#' * 100 + '\n')FILE.write(str(c)+'\n')FILE.close()return c, Ndef round2(m, n):e1 = 65537e2 = 84731c1 = pow(m, e1, n)c2 = pow(m, e2, n)c = [c1, c2]open('round2.txt', 'w').write(str(c) + '\n')def round3(m, n):assert p1 * q1 == nrand = randint(1, n - 1)test_enc = pow(rand, e, n)assert pow(test_enc, d, n) == randkey = e * dnew_e = 65537c = pow(m, new_e, n)f = open('round3.txt', 'w')f.write(str(key) + '\n')f.write(str(c) + '\n')f.close()def round4(m, n):p, q = p2, q2e = 65537c = pow(m, e, n)f = open('round4.txt', 'w')f.write(str(c) + '\n')f.write(str(pow(p + q, 2019, n)) + '\n')f.write(str(pow(p + 2019, q, n)) + '\n')f.close()n1, n2, n3, n4 = N
print 'n1 =', n1
# n1 = 11177704342647691670070109831808378482821379302566268464943167206480241387551242120970561253786504223799891058773501288553907233379501460184102021531940602831324488818584481982166938165369946708273616214479706319082928159418133324715707808391767322038274030554057692976849636562898606740933056248870247255267420120488136713203337167713048960270135675134979523980774070773134748108563438318851158022122836766753248988837577239024669497444315476147384635493684855045085484618938995056978709390818568630471778630936743950045419782341697342117812959693992029294299582179507853091511833090186389981102903683178276414062363round1(n2)
round2(n3, n2)
round3(n4, n3)
round4(bytes_to_long(flag), n4)

思路：
低加密指数广播攻击+共模攻击+已知n和e*d+数论推导
解：

import gmpy2
import sympy
from functools import reduce
from Crypto.Util.number import *# .txt删除了[]、L和部分换行
path1 = r'D:\Downloads\Crypto-babyrsa\round1 - n.txt'
path2 = r'D:\Downloads\Crypto-babyrsa\round1 - c.txt'
path3 = r'D:\Downloads\Crypto-babyrsa\round2 - n.txt'
path4 = r'D:\Downloads\Crypto-babyrsa\round3.txt'
path5 = r'D:\Downloads\Crypto-babyrsa\round4.txt'# 中国剩余定理
def chinese_remainder(modulus,remainders):sum = 0prod = reduce(lambda a,b:a*b,modulus)for m_i,r_i in zip(modulus,remainders):p = prod // m_isum += r_i * (inverse(p,m_i)*p)return sum % prod# 低加密指数广播攻击
def de_round1():e = 10n = []c = []with open(path1, 'r') as f:data = f.read()n = data.split("L, ")n = [item.rstrip('L') for item in n]n = list(map(lambda x: int(x), n))with open(path2, 'r') as f:data = f.read()c = data.split("L, ")c = [item.rstrip('L') for item in c]c = list(map(lambda x: int(x), c))pow_m_e = chinese_remainder(n,c)m = gmpy2.iroot(pow_m_e, e)[0]# print(m)return m# 共模攻击
def de_round2(n):e1 = 65537e2 = 84731c = []with open(path3, 'r') as f:data = f.read()c = data.split("L, ")c = [item.rstrip('L') for item in c]c = list(map(lambda x: int(x), c))r , s1 , s2 = gmpy2.gcdext(e1,e2)m = (gmpy2.powmod(c[0],s1,n)*gmpy2.powmod(c[1],s2,n)) % n# print(m)return m# 已知n和e*d
def de_round3(n):e = 65537with open(path4, 'r') as f:data = f.readlines()data = [line.strip("\n") for line in data]data = list(map(lambda x: int(x), data))ed = data[0]c = data[1]p = 0q = 2k = ed - 1while q:k=k//2p=gmpy2.gcd(gmpy2.powmod(q,k,n)-1,n)%nif p>1:q = n//pbreakelse:q=int(sympy.nextprime(q))z = (p-1)*(q-1)d = gmpy2.invert(e,z)m = gmpy2.powmod(c,d,n)# print(m)return m# 数论推导
def de_round4(n):e = 65537with open(path5, 'r') as f:data = f.readlines()data = [line.strip("\n") for line in data]data = list(map(lambda x: int(x), data))c = data[0]hint1 = data[1]hint2 = data[2]p = gmpy2.gcd(hint1 - pow(hint2-2019, 2019, n), n)# p = gmpy2.gcd(hint2 - pow(2019, n, n), n)q = n // pz = (p-1)*(q-1)d = inverse(e, z)m = gmpy2.powmod(c, d, n)return mif __name__ == "__main__":n2 = de_round1()n3 = de_round2(n2)n4 = de_round3(n3)m = de_round4(n4)print(bytes.fromhex(hex(m)[2:]))

flag{y0U_R_th3_ch0sen_on3_1n_the_field_of_Crypt0gr4phy}