数论
二项式定理
费马小定理
基础练习
[金盾信安杯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 randint
def round1(m):
e = 10
N = 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, N
def round2(m, n):
e1 = 65537
e2 = 84731
c1 = 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 == n
rand = randint(1, n - 1)
test_enc = pow(rand, e, n)
assert pow(test_enc, d, n) == rand
key = e * d
new_e = 65537
c = 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, q2
e = 65537
c = 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 = 11177704342647691670070109831808378482821379302566268464943167206480241387551242120970561253786504223799891058773501288553907233379501460184102021531940602831324488818584481982166938165369946708273616214479706319082928159418133324715707808391767322038274030554057692976849636562898606740933056248870247255267420120488136713203337167713048960270135675134979523980774070773134748108563438318851158022122836766753248988837577239024669497444315476147384635493684855045085484618938995056978709390818568630471778630936743950045419782341697342117812959693992029294299582179507853091511833090186389981102903683178276414062363
round1(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 = 0
prod = reduce(lambda a,b:a*b,modulus)
for m_i,r_i in zip(modulus,remainders):
p = prod // m_i
sum += r_i * (inverse(p,m_i)*p)
return sum % prod
# 低加密指数广播攻击
def de_round1():
e = 10
n = []
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 = 65537
e2 = 84731
c = []
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 = 65537
with 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 = 0
q = 2
k = ed - 1
while q:
k=k//2
p=gmpy2.gcd(gmpy2.powmod(q,k,n)-1,n)%n
if p>1:
q = n//p
break
else:
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 = 65537
with 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 // p
z = (p-1)*(q-1)
d = inverse(e, z)
m = gmpy2.powmod(c, d, n)
return m
if __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}