526互联

NISACTF新生赛，密码学RSAwp

发布时间 2023-10-24 08:23:05作者: 欢黎明陌

比赛官网链接：http://156.224.26.249/

eeezRSA

考点：暴力破解

  1. 使用 在线工具分解大质数

  2. 使用拓欧得到私钥d

    def exgcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        gcd, x, y = ex(b % a, a)
        return (gcd, y - (b // a) * x, x)

  3. 计算flag bytes_to_long后的变量m

    m = pow( c , d , n )

  4. 将整数m转化为字符串flag

    m = 11604008605541818712966720001582142618375831382642459409129147724359509689501272522137152998605953387230762300554700585488547840790592562824581160993059033

# 将整数转化为字节串
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')

# 输出字节串
print(flag)

Baby_RSA

因为 c = ( m ^ e ) % n

所以 c = ( m ^ e ) - k * n , 其中 k∈ N*

题目已知 c , e , n，求m；且 c 和 n 都是比较大的数，相对接近。

故可以枚举 k 的值，得到m的值

def solve( c , e , n ):
	k = 0
	while 1:
	    m = c + k * n
    	result , check = gmpy2.iroot(m, e)#求大整数x开n次根,result是返回的结果，check来判断是否正常返回
    	if check == 1:
            return check
        k += 1
m = solve( c , e , n )
print(long_to_bytes(m))

Crt_RSA

n是两个大质数的乘积，因为数太大而导致解密缓慢

使用中国剩余定理可以帮助优化解密过程，将模幂运算分解为对不同模数的模幂运算，从而降低复杂度

e = 3
n = [n1,n2,n3]
c = [c1,c2,c3]
M, mod = crt(n, c)#M是CRT的结果，即合并多个RSA模数后得到的结果
m, check = gmpy2.iroot(M, e)
print(long_to_bytes(m))

算法的正确性：

模重建性质确保解密的结果m是正确的

由于CRT的合并步骤是模运算，其中模重建性质确保答案是唯一的，因此用CRT算法合并的结果m是正确的

EmbryoRSA

  1. 计算n和φ(n)

    n = p * q
pn = (p-1) * (q-1)

  2. 使用扩展欧几里德算法找到d

    def extended_gcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        gcd, x, y = extended_gcd(b % a, a)
        return (gcd, y - (b // a) * x, x)

  3. 得到私钥d

    gcd, x, y = extended_gcd(e, phi_n)
d = x % pn

  4. 得到flag

    m = pow( c , d , n )
print( ans )
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(flag)