UNCTF2021-baby_rsa

​ 和室友一起参加了UNCTF2021，分别获得第二和第三；总的来说题目比较基础，AK了密码和杂项。只记录一道题。

​ 题目：

import gmpy2
import libnum
import random
import uuid
flag="unctf{"+str(uuid.uuid4())+"}"
m=libnum.s2n(flag)

p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=65537
c=pow(m*p+n,e,n)
print("n=",n)
print("c=",c)
print("e=",e)
#n= 27023180567533176673625876001733765250439008888496677405372613659387969480500400831799338479404533734632060401129194207025095826786316107611502577395964365591899893794206238112244571942694129959717225168573059987542436467778426312967832431595178558711258027999897974942046398583397445299861338203860420721585460676138091828032223153425728023656897880166788811969523526091221520293020106530587453637600349533427641518473788620430866128331962450325767202417824455886116760280239705754222948387172102353564657340216229891342124971948458724351338597649821310431397426705701275774039588035776573373417654649168810548916141
#c= 3489599657527403893851973553294684608504140532554562294027722218597464669848608337663997115805201027340092733823019661706872544231209523772845492398492677185660213963118144668038183924970370481476141221609706208064428560732214361469135212057355342825193598971775551833240699393482839422273480793244841531126642199202744610656153155545415859410361595564197685655133074582118230993519133935533313364233668337427608419528430102794052261190930670933657287272452581248934890029409559234507626012423255430699687038808658327174609660874748540185589263800447650242593224189976058739054174360024536594384447518687126891675059
#e= 65537

​ 根据已知信息化简得到一个关系：c=pow（m*p，e，n），再根据这个关系可以推出p其实就是c和n的最大公因数，那么可以求出p从而得到q，d求出明文，脚本：

import gmpy2
from Crypto.Util.number import *


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a    #辗转相除法

n= 27023180567533176673625876001733765250439008888496677405372613659387969480500400831799338479404533734632060401129194207025095826786316107611502577395964365591899893794206238112244571942694129959717225168573059987542436467778426312967832431595178558711258027999897974942046398583397445299861338203860420721585460676138091828032223153425728023656897880166788811969523526091221520293020106530587453637600349533427641518473788620430866128331962450325767202417824455886116760280239705754222948387172102353564657340216229891342124971948458724351338597649821310431397426705701275774039588035776573373417654649168810548916141
c= 3489599657527403893851973553294684608504140532554562294027722218597464669848608337663997115805201027340092733823019661706872544231209523772845492398492677185660213963118144668038183924970370481476141221609706208064428560732214361469135212057355342825193598971775551833240699393482839422273480793244841531126642199202744610656153155545415859410361595564197685655133074582118230993519133935533313364233668337427608419528430102794052261190930670933657287272452581248934890029409559234507626012423255430699687038808658327174609660874748540185589263800447650242593224189976058739054174360024536594384447518687126891675059
e= 65537
p=gcd(n,c)
print(p)
q=n//p
print(q)
phi=(p-1)*(q-1)
print(n==p*q)
d=gmpy2.invert(e,phi)
print(d)
m0=pow(c,d,n)
m=(m0)//p
flag=long_to_bytes(m)
print(flag)