RSA-1 wp（已知 p、q、e 求 d ）

打开压缩包后得到一个 txt 文件，文件内容如下：

在一次RSA密钥对生成中，假设 p=473398607161 ， q=4511491 ， e=17
求解出d作为flga提交

已知 p 、q 、e，要我们求 d ，直接跑 python 脚本

def extended_gcd1(a,b):    # 扩展欧几里得算法，根据RSA密码原理计算 e 的系数 d
    old_s=t=1
    old_t=s=0
    old_r=a
    r=b
    while r!=0:
        q=old_r//r
        old_s,s=s,old_s-s*q
        old_t,t=t,old_t-t*q
        old_r,r=r,old_r%r
    return (old_r,old_s,old_t)
# d * e + phi_n * x = 1
p=473398607161
q=4511491
e=17
phi_n=(p-1)*(q-1)
d= extended_gcd1(e, phi_n)[1]
print(d)
# 运行结果：125631357777427553

跑出来了直接用 flag{} 包起来

flag{125631357777427553}

RSA-2 wp（已知 p、q、e、c 求解）

源地址：https://buuoj.cn/challenges#rsarsa

打开压缩包后有一个 txt 文件，内容如下：

Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
Use RSA to find the secret message

已知 p、q、e、c ，我们通过 phi_n 求出 d ，通过 d 和 n ( n = p * q ) 来解出明文 m 。不多说了，直接跑脚本。

def extended_gcd1(a,b):
    old_s=t=1
    old_t=s=0
    old_r=a
    r=b
    while r!=0:
        q=old_r//r
        old_s,s=s,old_s-s*q
        old_t,t=t,old_t-t*q
        old_r,r=r,old_r%r
    return (old_r,old_s,old_t)
p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
n=p*q
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
phi_n=(p-1)*(q-1)
# 通过扩展欧几里得算法求出 e的系数 d
d= extended_gcd1(e, phi_n)[1]
# m = c ** d % n 
m=pow(c,d,n)
print(m)
# 运行结果：5577446633554466577768879988

老样子，flag{}包起来直接交

flag{5577446633554466577768879988}

RSA-3 wp（dp、dq 泄露）

源地址：https://buuoj.cn/challenges#RSA2

打开压缩包后有一个 txt 文件，内容如下：

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

dp、dq 泄露了，可以通过 dp 和 dq 以及 p 和 q 可以得到 m，关系和解密公式如下：

dp 和 dq 的关系如下：
d e = 1 mod ( ( p-1) ( q - 1 ) )
dp = d mod ( p - 1 )
dq = d mod ( q - 1 )
m1 和 m2 与 m 的关系如下：
m1 = c ** dp mod p
m2 = c ** dq mod q
q * I mod p = 1 # I 是 p 的逆元，可以通过 gmpy2 . invert ( q , p ) 函数求出
m =( ( ( m1 - m2 ) I ) mod p ) q + m2

关系和解密公式都给了，直接写脚本跑出来

import gmpy2
from Crypto.Util.number import long_to_bytes
def extended_gcd1(a,b):
    old_s=t=1
    old_t=s=0
    old_r=a
    r=b
    while r!=0:
        q=old_r//r
        old_s,s=s,old_s-s*q
        old_t,t=t,old_t-t*q
        old_r,r=r,old_r%r
    return (old_r,old_s,old_t)
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
def dp_dq_m(c, p, q, dp, dq):   # 求解 m
    # 计算 m1 和 m2
    m1 = pow(c, dp, p)
    m2 = pow(c, dq, q)
    # 计算 q 的逆元 mod p ，即 I 
    I = gmpy2.invert(q, p)
    m = (m1 + (m1 - m2) * I % p * q) % (p * q)
    return m
m=crt(c,p,q,dp,dq)
print(long_to_bytes(m))
# 将解出来的数字转换为字节流，得到flag字符
# 运行结果：b'noxCTF{W31c0m3_70_Ch1n470wn}'

将解出的flag包起来

flag{W31c0m3_70_Ch1n470wn}

Problem: 认识RSA

思路

题目已经给出了 p、q、e、c。
根据题目给出的p、q可以求出n和phi_n，
phi_n=(p-q) * (q-1);
n=p * q.
通过e和phi_n可以求出d，
d * e = 1 mod phi_n (可以通过扩展欧几里得算法求出 d ).
通过c、d、n可以求出明文m，
m=c ** d mod n .

脚本直接跑就行了.

EXP

具体攻击代码

from Crypto.Util.number import long_to_bytes
def extended_gcd1(a,b):
  old_s=t=1
  old_t=s=0
  old_r=a
  r=b
  # print('{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}'.format('old_r','r','old_s','s','old_t','t','q'))
  while r!=0:
      q=old_r//r
      # print('{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}'.format(old_r,r,old_s,s,old_t,t,q))
      old_s,s=s,old_s-s*q
      old_t,t=t,old_t-t*q
      old_r,r=r,old_r%r
  # print('{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}{:<20}'.format(old_r, r, old_s, s, old_t, t,'-'))
  return (old_r,old_s,old_t)
p = 10554915510546378513140074459658086644656654144905337809416976066414771647836950941616441505897207397834928781511863699153349798682451297889979721668885951
q = 8246403321715011123191410826902524505032643184038566851264109473851746507405534573077909160292816825514872584170252311902322051822644609979417178306809223
n = p * q
e = 65537
c = 40005881669517895877352756665523238535105922590962714344556374248977905431683140065629966778249773228248201807844489945346731806741025157651474530811920115794270396320935022110691338083709019538562205165553541077855422953438117902279834449006455379382431883650004540282758907332683496655914597029545677184720

phi_n=(p-1)*(q-1)
# 通过扩展欧几里得算法求出 e的系数 d
d= extended_gcd1(e, phi_n)[1]
# 求出明文 m
m=pow(c,d,n)
print(long_to_bytes(m))

总结

对该题的考点总结
基础题，懂得RSA原理及加解密方法即可解出

check_little（2025强网杯线上初赛的一题RSA）

题目内容：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import os

flag, key = open('secret').read().split('\n')

e = 3

while 1:
    p = getPrime(1024)
    q = getPrime(1024)
    phi = (p - 1) * (q - 1)
    if phi % e != 0:
        break
N = p * q
c = pow(key, e, N)

iv = os.urandom(16)
ciphertext = AES.new(key = long_to_bytes(key)[:16], iv = iv, mode = AES.MODE_CBC).encrypt(pad(flag.encode(),16)).hex()

f = open('output.txt', 'w')
f.write(f'N = {N}\n')
f.write(f'c = {c}\n')
f.write(f'iv = {iv}\n')
f.write(f'ciphertext = {ciphertext}\n')

output.txt:

N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2

拿到题，看到 e = 3 ，下意识想到低指数加密攻击……跑半天没出，应该不是了。怎么测都出不来，是我菜了……

比赛时就没做出来……结束后看了佬的wp，

emmm……

N 和 c 不互素！！！ ( gcd(N,c) ! = 1 )，根本想不到。

由于不互素，直接求出 p = gcd( N,c ) ，再求出 q = N // p，验算了一下，确实是对的。难评

接下来就是解出 key，得到明文了。

from Crypto.Util.number import *
from Crypto.Util.Padding import unpad
from Crypto.Cipher import AES
import gmpy2
e=3
N = 18795243691459931102679430418438577487182868999316355192329142792373332586982081116157618183340526639820832594356060100434223256500692328397325525717520080923556460823312550686675855168462443732972471029248411895298194999914208659844399140111591879226279321744653193556611846787451047972910648795242491084639500678558330667893360111323258122486680221135246164012614985963764584815966847653119900209852482555918436454431153882157632072409074334094233788430465032930223125694295658614266389920401471772802803071627375280742728932143483927710162457745102593163282789292008750587642545379046283071314559771249725541879213
c = 10533300439600777643268954021939765793377776034841545127500272060105769355397400380934565940944293911825384343828681859639313880125620499839918040578655561456321389174383085564588456624238888480505180939435564595727140532113029361282409382333574306251485795629774577583957179093609859781367901165327940565735323086825447814974110726030148323680609961403138324646232852291416574755593047121480956947869087939071823527722768175903469966103381291413103667682997447846635505884329254225027757330301667560501132286709888787328511645949099996122044170859558132933579900575094757359623257652088436229324185557055090878651740
iv = b'\x91\x16\x04\xb9\xf0RJ\xdd\xf7}\x8cW\xe7n\x81\x8d'
ciphertext = 'bf87027bc63e69d3096365703a6d47b559e0364b1605092b6473ecde6babeff2'

# RSA 解密
p=gmpy2.gcd(c,N)
q=N//p if int(N//p)==N//p else exit(print("[-] can't factor N!"))
print("[+] N factor success!")
phi_n=(p-1)*(q-1)
d=inverse(e,phi_n)
print("[+] compute d!")
key=long_to_bytes(pow(c,d,N))
print("[+] compute key!")
print('[*] key:',key)
# AES解密
aes=AES.new(key[:16],AES.MODE_CBC,iv)
m=aes.decrypt(bytes.fromhex(ciphertext))
m=unpad(m,16).decode()
print("[+] compute m!")
print('[+] m:',m)
'''
[+] N factor success!
[+] compute d!
[+] compute key!
[*] key: b'\xd1\x9eL\xa2\xaf\xb2\x16B\xba\xf4KHv\x8b\x81\x06\x14\xc2\xe7\x94:U6\x05\xd2\x7f\x061;"\xc8fH\x17\x8c\x8b\x8b\xc4\x8c^\x8c\x8a*\x08\xff\x93\x93?\xa6\xab\x0e\xd8~,X*\xde\xac\xe5c\xec\xb5\xd9\x06\xc4aM\x05\n\x19\xed\xf3*\xbf\x14\x8am\xae\xbb\x14\xaa\xd1\xadi\xf8B$\xd3<\xaeK\x17\xac\xebn\x844\x16\xb1\x15k\x1d,\x12\x95\xc1%\xd6=\x97\xd9\xe3z\xe1j\x94\x90\n\xe7\xd4\x01\xec(\x03\xf0i\x08\xf7'
[+] compute m!
[+] m: flag{m_m4y_6e_divIS1b1e_by_p?!}
'''

flag{m_m4y_6e_divIS1b1e_by_p?!}

RSA练习-1