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 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}

参考链接：
https://blog.csdn.net/XiongSiqi_blog/article/details/130175464