Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

RSA

RSA 加密算法是一种非对称加密算法，广泛应用于公开密钥加密和电子商务中。该算法于 1977 年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）提出，RSA 的名称来源于他们三位创始人的姓氏首字母。

RSA 算法的安全性基于大整数分解的难度。换句话说，分解一个非常大的整数越困难，RSA 算法就越安全。如果有人找到快速分解整数的算法，那么使用 RSA 加密的信息的安全性将会大幅下降。然而，找到这样的算法的可能性非常小。目前，只有短的 RSA 密钥可能会受到强力破解的威胁。

数论基础

整除

设 a，b 是两个整数，且 \(b \neq 0 \) ，如果存在整数 c 使 \( a = bc \)，则称 a 被 b 整除，或 b 整除 a。

素数

在大于 1 的自然数中，除了 1 和它本身外，不能被其他自然数整除的数称为素数（Prime Number），否则称为合数。素数也被称作质数。换句话说，素数只有两个正因数：1 和它本身。

例如，7 和 11 是素数。最小的素数是 2。

互素

互素指的是两个整数之间的最大公因数为 1。换句话说，两个数互素意味着它们没有其他公因数，除了 1。

例如，数字 8 和 15 是互素的，因为它们的最大公约数是 1。数字 12 和 18 不是互素的，因为它们的最大公约数是 6。

欧拉函数

欧拉函数通常用 \( \varphi(n) \) 表示。

$$ \varphi(n) = \text{小于等于 n 的正整数中，与 n 互素的个数} $$

如\( \varphi(1) = \varphi(2) = 1 \)，\( \varphi(3) = \varphi(4)=2 \)。显然，当 n 为素数时， \( \varphi(n) = n-1 \)；当 n 为合数时， \( \varphi(n) < n-1 \)。

同余式

中国剩余定理

RSA 算法简述

  1. 随机选择两个不同的大素数 \( p \) 和 \( q \)，计算 \( N = p \times q \)
  2. 根据欧拉函数，求\( \varphi(N) = \varphi(p)\varphi(q) = (p-1)(q-1) \)
  3. 随机选择一整数\( e \)（解密指数），满足\( 0 < e < \varphi(N) \)，且\( e \)和\( \varphi(N) \)互素
  4. 计算加密指数\( d \)，满足\( ed \equiv 1\ ( \bmod \varphi(N)) \)，\( d \)为\( e \)关于\( \varphi(N) \)的模反元素
  5. 销毁\( p \)、\( q \)

其中\( (N,e) \)为公钥，\( (N,d) \)为私钥。假定\( c \)为密文，\( m \)为明文，则

加密过程为\( c = m^e \bmod N \)

解密过程为\( m = c^d \bmod N \)

import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long

p = 885320963
q = 238855417
n = p*q
phin = (p-1)*(q-1)
print('phin:', phin) # 211463706672030192
e = 65537
d = gmpy2.invert(e, phin)
print('d:', d) # 34737907838794529

# 加密
m = b'abc'
print("m_to_long:", bytes_to_long(m)) # 6382179
c = gmpy2.powmod(bytes_to_long(m), e, n)
print('encrypt:', c) # 151999436028678347

# 解密
m1 = gmpy2.powmod(c, d, n)
print('plain_long:',m1) # 6382179
print('plain_text:',long_to_bytes(m1)) # b'abc'

环境准备

  • Python 3 依赖安装
    • gmpy2是一个用于高精度算术运算的 Python 库，要求 Python 3.7 to 3.13。
    • pycryptodome是PyCrypto的替代品，提供更强大的加密算法支持。
pip install gmpy2 pycryptodome -i https://mirrors.aliyun.com/pypi/simple

常见攻击方法

模数分解（因数分解）

模数分解（因数分解）是指将 RSA 公钥中的模数 \( n \) 分解为两个素数 \( p、q \) 的乘积。

直接分解

在实际应用中，RSA 算法使用的素数长度在 1024 位、2048 位或更高。在 CTF 赛题中，若模数 \( n \) 的位数比较小，则可以直接因式分解模数\( n \)，进而获得\( p、q \)。

因式分解的工具有Yafu、factordb.com是一个专门用于存储和查询整数的因数分解结果的在线数据库，以及其他的因式分解算法。

例如，在 DeconstruCT.F 2021 的 RSA-1 题目中，发现模数\( n \)比较小，考虑分解模数\( n \)。

Ever used RSA Encryption?

cyphertext = 10400286653072418349777706076384847966640064725838262071
n = 23519325203263800569051788832344215043304346715918641803
e = 71

方法一：factordb.com是一个专门用于存储和查询整数的因数分解结果的在线数据库。

方法二：本地工具Yafu

获取\( p、q \)后，可以直接编写代码进行解密。参考 Python 3 代码如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

c = 10400286653072418349777706076384847966640064725838262071
p = 4655885807254867892895911581
q = 5051525354555657585960616263
n = 23519325203263800569051788832344215043304346715918641803
e = 71

phin = (p-1)*(q-1)
d = gmpy2.invert(e, phin)
m = gmpy2.powmod(c, d, n)

print(long_to_bytes(m)) # b'dsc{t00_much_m4th_8898}'

方法三：使用RsaCtfTool

./RsaCtfTool.py -n 23519325203263800569051788832344215043304346715918641803 -e 71 --decrypt 10400286653072418349777706076384847966640064725838262071

利用公因数

如果在两次公钥的加密过程中使用的\( n_1 \) 和\( n_2 \)具有相同的素因子，那么可以利用欧几里得算法直接将\( n_1 \)和\( n_2 \)分解。

通过欧几里得算法可以直接求出\( n_1 \)和\( n_2 \)的最大公因数\( p \)：

  • 识别：题目往往给了若干不相同的模数\( n \)，且使用相同的加密指数\( e \)，那么可以考虑模数是否有公约数，进而进行模数分解
p1 = getPrime(512)
p2 = getPrime(512)
q = getPrime(512)
n1 = p1*q
n2 = p2*q

$\left| p-q \right|$较小

\( \left| p-q \right| \) 很小，即\( p、q \) 相差过小，可以使用费马分解法 (Fermat's factorization method)来快速分解模数\( n \)。

0x41414141 CTF factorize，题目提供了密文\( c \)、模数$n$以及factorize.py文件。

c: 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255
n: 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663

factorize.py：

import binascii
import random
from Crypto.Util.number import isPrime

flag = open("flag.txt", "rb").read().strip()
m = int(binascii.hexlify(flag), 16)

def genPrimes(size):
    base = random.getrandbits(size // 2) << size // 2 # 生成一个512位的随机整数，并将这个整数左移512位
    base = base | (1 << 1023) | (1 << 1022) | 1
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            p = temp
            break
    while True:
        temp = base | random.getrandbits(size // 2)
        if isPrime(temp):
            q = temp
            break
    return (p, q)

p, q = genPrimes(1024)
n = p * q
e = 0x10001

print("c:", pow(m, e, n))

from Crypto.Util.number import isPrime, getStrongPrime
from gmpy import next_prime
from secret import flag

# Anti-Fermat Key Generation
p = getStrongPrime(1024)
q = next_prime(p ^ ((1<<1024)-1))
n = p * q
e = 65537

# Encryption
m = int.from_bytes(flag, 'big')
assert m < n
c = pow(m, e, n)

print('n = {}'.format(hex(n)))
print('c = {}'.format(hex(c)))

from math import isqrt
from Crypto.Util.number import inverse, long_to_bytes

n = 0x1ffc7dc6b9667b0dcd00d6ae92fb34ed0f3d84285364c73fbf6a572c9081931be0b0610464152de7e0468ca7452c738611656f1f9217a944e64ca2b3a89d889ffc06e6503cfec3ccb491e9b6176ec468687bf4763c6591f89e750bf1e4f9d6855752c19de4289d1a7cea33b077bdcda3c84f6f3762dc9d96d2853f94cc688b3c9d8e67386a147524a2b23b1092f0be1aa286f2aa13aafba62604435acbaa79f4e53dea93ae8a22655287f4d2fa95269877991c57da6fdeeb3d46270cd69b6bfa537bfd14c926cf39b94d0f06228313d21ec6be2311f526e6515069dbb1b06fe3cf1f62c0962da2bc98fa4808c201e4efe7a252f9f823e710d6ad2fb974949751
c = 0x60160bfed79384048d0d46b807322e65c037fa90fac9fd08b512a3931b6dca2a745443a9b90de2fa47aaf8a250287e34563e6b1a6761dc0ccb99cb9d67ae1c9f49699651eafb71a74b097fc0def77cf287010f1e7bd614dccfb411cdccbb84c60830e515c05481769bd95e656d839337d430db66abcd3a869c6348616b78d06eb903f8abd121c851696bd4cb2a1a40a07eea17c4e33c6a1beafb79d881d595472ab6ce3c61d6d62c4ef6fa8903149435c844a3fab9286d212da72b2548f087e37105f4657d5a946afd12b1822ceb99c3b407bb40e21163c1466d116d67c16a2a3a79e5cc9d1f6a1054d6be6731e3cd19abbd9e9b23309f87bfe51a822410a62
e = 65537

def FermatFactors(n):
    a = (((1 << 1024)-1) + 1)//2

    while True:
        b1 = a * a - n
        b = isqrt(b1)
        if b * b == b1:
            break
        a += 1
    return a - b, a + b

p, q = FermatFactors(n)
assert p*q == n
phi = (p-1)*(q-1)
d = inverse(e, phi)
print(long_to_bytes(pow(c, d, n)).decode())

dp 泄露

  • 识别：已知$n、e、dp、c$

$$ dp = d(\bmod p-1) $$

from Crypto.Util.number import long_to_bytes
import gmpy2

# 已知参数
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751


# 计算 p
for k in range(1, e):
    p = ((dp * e - 1) // k) + 1
    if n % p == 0:
        break

# 计算 q
q = n // p

# 计算 d
phi_n = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi_n)

# 解密密文
m = gmpy2.powmod(c, d, n)

# 打印解密后的明文
print(long_to_bytes(m))  # b'flag{wow_leaking_dp_breaks_rsa?_98924743502}'

dq、dp 泄露

  • 识别：已知$p、q、dp、dq、c$

$$ \begin{align} dq=d(\bmod q-1) \ dp=d(\bmod p-1) \ InvQ=q^{−1} (\bmod p) \end{align} $$

例题 PicoCTF 2017 Weird RSA

c: 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p: 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q: 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp: 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq: 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

import gmpy2
from Crypto.Util.number import long_to_bytes

c = 95272795986475189505518980251137003509292621140166383887854853863720692420204142448424074834657149326853553097626486371206617513769930277580823116437975487148956107509247564965652417450550680181691869432067892028368985007229633943149091684419834136214793476910417359537696632874045272326665036717324623992885
p = 11387480584909854985125335848240384226653929942757756384489381242206157197986555243995335158328781970310603060671486688856263776452654268043936036556215243
q = 12972222875218086547425818961477257915105515705982283726851833508079600460542479267972050216838604649742870515200462359007315431848784163790312424462439629
dp = 8191957726161111880866028229950166742224147653136894248088678244548815086744810656765529876284622829884409590596114090872889522887052772791407131880103961
dq = 3570695757580148093370242608506191464756425954703930236924583065811730548932270595568088372441809535917032142349986828862994856575730078580414026791444659

qinv = gmpy2.invert(q,p)
m1 = gmpy2.powmod(c,dp,p)
m2 = gmpy2.powmod(c,dq,q)
h = qinv * (m1-m2)
m = m2 + h*q

print(long_to_bytes(m)) # b'Theres_more_than_one_way_to_RSA'

低加密指数小明文攻击

  • 识别：已知加密指数\( e \)较小，通常为 3

如果明文\( m \)非常小，且加密指数\( e \)较小，通常为 3。若满足\( m^3 < n \)，那么\( c = m^3 \)，可直接计算密文\( c \)的立方根来恢复明文\( m \)。

例题，已知题目信息如下，得\( e=3 \)，且密文\( c \)比\( n \)小，可直接计算密文的立方根。

e: 3
c: 2780321436921227845269766067805604547641764672251687438825498122989499386967784164108893743279610287605669769995594639683212592165536863280639528420328182048065518360606262307313806591343147104009274770408926901136562839153074067955850912830877064811031354484452546219065027914838811744269912371819665118277221
n: 23571113171923293137414347535961677173798389971011031071091131271311371391491511571631671731791811911931971992112232272292332392412512572632692712772812832933073113133173313373473493533593673733793833893974014094194214314334394434494574614634674794874914995035095215235415475575635695715775875935996016076136176196316416436476536596616736776836917017097197277337397437517577617697737877978098118218238278298398538578598638778818838879079119199299379419479539679719779839919971009101310191431936117404941729571877755575331917062752829306305198341421305376800954281557410379953262534149212590443063350628712530148541217933209759909975139820841212346188350112608680453894647472456216566674289561525527394398888860917887112180144144965154878409149321280697460295807024856510864232914981820173542223592901476958693572703687098161888680486757805443187028074386001621827485207065876653623459779938558845775617779542038109532989486603799040658192890612331485359615639748042902366550066934348195272617921683

脚本如下：

import gmpy2
from Crypto.Util.number import long_to_bytes

c = 2780321436921227845269766067805604547641764672251687438825498122989499386967784164108893743279610287605669769995594639683212592165536863280639528420328182048065518360606262307313806591343147104009274770408926901136562839153074067955850912830877064811031354484452546219065027914838811744269912371819665118277221
m = gmpy2.iroot(c, 3)[0]
print(long_to_bytes(m)) # b'dsc{t0-m355-w1th-m4th-t4k35-4-l0t-0f-sp1n3}'

RsaCtfTool -n 2357..3 -e 3 --decrypt 2780...21 --attack cube_root

如果密文虽然大于，但不是特别大， 练习题：NahamCon CTF 2024: Magic RSA

import gmpy2
from Crypto.Util.number import long_to_bytes

ciphertext = [1061208, 1259712, 912673, 1092727, 1860867, 175616, 166375, 941192, 185193, 1030301, 941192, 185193, 912673, 140608, 175616, 185193, 140608, 941192, 970299, 1061208, 175616, 912673, 117649, 912673, 185193, 148877, 912673, 125000, 110592, 1030301, 132651, 132651, 1061208, 117649, 117649, 1061208, 166375, 1953125]
N = 292661735803169078279687796534368733968232055929694715453717384181208539846645017378459508481927733219065809706996972833902743250671173212610674572380079245835772007065919936022084401497853611610920914306013040436502207047619016113234947051878549793269852855316328078769491183468515501156324665790842023112309668506350354977653838139155232422868462129041940364012648613391176971689126513558396465218392059219609662829793504680423032430634001779369250142543104703669906030549585514247663929431837546466696121103600101025434247152431200408744676625328330247569014313252820778269086840631297075563756934662979588351413726196027845505808290890109883253252054958997436359016852222176230489468164288277709046892991459049248340800616885136366469783271661343653314539194467688757972713531491290238432270971346559967725437118531023032768463200227986539449334624183071042562539584305305367245588508498775214112729500313280502474837332653452065755426475638743763861804587979560695676963674789819860296303566053542883415223272958687917330474367563315425617320128680682444959701586681495270336801802382200546403246134181793704030611664095075430115127507174884551339452808218398863888817

def cube_root_attack(ciphertext, N):
    decrypted = []
    for c in ciphertext:
        m = gmpy2.iroot(c, 3)[0]
        decrypted.append(long_to_bytes(m))
    return decrypted

decrypted_plaintext = cube_root_attack(ciphertext, N)
for pt in decrypted_plaintext:
   print(pt.decode(), end='')

低加密指数广播攻击

  • 已知多组模数$n_i$、密文$c_i$

对于相同明文$m$，使用相同的低加密指数$e$（如$e=3$），在不同的模数$n_1,n_2,...,n_i$进行加密（$i \geq e$），得到$i$组密文，可以使用中国剩余定理解出明文。

from functools import reduce
import gmpy2
from Crypto.Util.number import long_to_bytes


def crt(a, n):
    sum = 0
    prod = reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * gmpy2.invert(p, n_i)*p
    return sum % prod


# 已知变量
e = 3
n1 = int('331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004', 5)
c1 = int('310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243', 5)

n2 = int('302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114', 5)
c2 = int('112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344', 5)

n3 = int('332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323', 5)
c3 = int('10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242', 5)

# 使用 gmpy2 的 crt 方法计算 m^e
m_e = crt([c1, c2, c3], [n1, n2, n3])

# 计算 m^e 的整数根
m, exact = gmpy2.iroot(m_e, e)

if exact:
    print(f"解密得到的消息 m 为: {long_to_bytes(m)}") # b'noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}
else:
    print("未能找到整数根")

低解密指数攻击（Wiener's attack，维纳攻击）

如果加密指数\( e \)非常大，由于\( ed \)在乘积时地位对等，解密指数\( d \)可能较小，可以进行维纳攻击。

值得注意的是，在实际应用中，加密指数\( e \)通常选择为一个较小的固定值65537，以便保证安全性的同时提高加密和解密的效率。

n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381
e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205
c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635

./RsaCtfTool.py -n 1096..1 -e 494..5 --decrypt 103..5 --attack wiener
#

共模攻击

共模攻击（Common Modulus Attack）的前提是同一个明文\( m \) 使用相同的模数\( n \)但不同的加密指数\( e_1, e_2, \ldots, e_k \)进行加密。

假设有同一个明文\( m \)使用相同的模数$n \)但不同的加密指数\( e_1 \)和\( e_2 \)进行加密，分别得到密文\( c_1 \)和\( c_2 \)：

$$ c_1 = m^{e_1} \mod n $$ $$ c_2 = m^{e_2} \mod n $$

如果\( e_1 \)和\( e_2 \)互素，即\( \gcd(e_1, e_2) = 1 \)，则可以使用扩展欧几里得算法找到整数\( a \)和\( \)，使得：

$$ a \cdot e_1 + b \cdot e_2 = 1$$

然后可以通过以下步骤恢复消息\( m$：

  1. 计算\( c_1^a \mod n$和\( c_2^b \mod n \)。
  2. 如果\( a \)是负数，则计算\( c_1^{-a} \mod n \)，这相当于计算$(c_1^{-1})^a \mod n \)，其中\( c_1^{-1}$是\( c_1$在模\( n \)下的逆元。
  3. 同理，如果\( b \)是负数，则计算\( c_2^{-b} \mod n \)。
  4. 最终消息\( m$可以通过\( m = (c_1^a \cdot c_2^b) \mod n \)恢复。

例题分析

示例代码

以下是使用 Python 和 gmpy2 库实现 RSA 共模攻击的示例代码：

import gmpy2
from Crypto.Util.number import long_to_bytes

def common_modulus_attack(c1, c2, e1, e2, n):
    # 扩展欧几里得算法找到 a 和 b
    g, a, b = gmpy2.gcdext(e1, e2)

    # 确保 e1 和 e2 互质
    if g != 1:
        raise ValueError("e1 和 e2 必须互质")

    # 计算 c1^a 和 c2^b
    if a < 0:
        c1 = gmpy2.invert(c1, n)
        a = -a
    if b < 0:
        c2 = gmpy2.invert(c2, n)
        b = -b

    m1 = gmpy2.powmod(c1, a, n)
    m2 = gmpy2.powmod(c2, b, n)

    # 恢复消息 m
    m = (m1 * m2) % n
    return m

# 示例
n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1 = 773
e2 = 839
c1 = 3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2 = 5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
m = common_modulus_attack(c1, c2, e1, e2, n)
print(long_to_bytes(m))

解释

  1. 扩展欧几里得算法：

    • 使用 gmpy2.gcdext 计算$e_1$和$e_2$的最大公约数以及系数$a$和$b$。

  2. 检查互质性：

    • 确保$e_1$和$e_2$互质，否则攻击无法进行。

  3. 计算逆元：

    • 如果$a$或$b$为负数，则计算相应密文的逆元。

  4. 恢复消息：

    • 通过$m = (c_1^a \cdot c_2^b) \mod n$恢复原始消息。

通过上述步骤和代码，可以利用 RSA 共模攻击在特定条件下恢复原始消息。保护 RSA 系统的安全性，避免使用相同的模数$n$是非常重要的。

Coppersmith's High Attack

RSA LSB Oracle

练习题

BUUCTF RSAROLL

import gmpy2
from Crypto.Util.number import long_to_bytes

p = 18443
q = 49891
n = 920139713
e = 19
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)

flag = b''
with open('data.txt', 'r') as f:
    for line in f.readlines():
        # print(line)
        m = gmpy2.powmod(int(line), d, n)
        flag += long_to_bytes(m)
print(flag)
# b'flag{13212je2ue28fy71w8u87y31r78eu1e2}'

Jarvis OJ - Crypto- MediumRSA

PEM（Privacy Enhanced Mail）文件是一种用于存储和传输加密数据的格式，通常用于存储证书、私钥、公钥等加密信息。PEM 文件使用 Base64 编码，并包含特定的头部和尾部标签，以便于识别和处理。

PEM 文件的内容通常包含以下部分：

  1. 头部标签：标识文件的类型，例如 -----BEGIN CERTIFICATE----- 或 -----BEGIN RSA PRIVATE KEY-----。
  2. Base64 编码的数据：实际的加密数据，以 Base64 编码表示。
  3. 尾部标签：标识文件的结束，例如 -----END CERTIFICATE----- 或 -----END RSA PRIVATE KEY-----。

GUET-CTF 2019 BabyRSA

p+q : 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
(p+1)(q+1) : 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e : 0xe6b1bee47bd63f615c7d0a43c529d219
d : 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag : 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

$$ \begin{align} (p+1)(q+1) &= pq + p + q + 1 = n + p + q + 1 \ n &= (p+1)(q+1) - (p + q) - 1 \end{align} $$

import gmpy2
from Crypto.Util.number import long_to_bytes

# p+q用a表示
a = 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
# (p+1)(q+1)用b表示
b = 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
d = 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
c = 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

n = b - a - 1
m = gmpy2.powmod(c, d, n)
print(long_to_bytes(m))
# flag{cc7490e-78ab-11e9-b422-8ba97e5da1fd}

BUUCTF-RSA2

[HDCTF2019]bbbbbbrsa

from base64 import b64decode
import gmpy2
from Crypto.Util.number import *

p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = "==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3MjM"

q = n // p

print(q)

phi = (p-1)*(q-1)
c = int(b64decode(c[::-1]))
for e in range(50000,70000):
    if gmpy2.gcd(e, phi) == 1:
        d = gmpy2.invert(e, phi)
        m = gmpy2.powmod(c,d,n)
        flag = str(long_to_bytes(m))
        print(flag)

BUUCTF RSA5

import gmpy2
from Crypto.Util.number import long_to_bytes

n1 = 20474918894051778533305262345601880928088284471121823754049725354072477155873778848055073843345820697886641086842612486541250183965966001591342031562953561793332341641334302847996108417466360688139866505179689516589305636902137210185624650854906780037204412206309949199080005576922775773722438863762117750429327585792093447423980002401200613302943834212820909269713876683465817369158585822294675056978970612202885426436071950214538262921077409076160417436699836138801162621314845608796870206834704116707763169847387223307828908570944984416973019427529790029089766264949078038669523465243837675263858062854739083634207
c1 = 974463908243330865728978769213595400782053398596897741316275722596415018912929508637393850919224969271766388710025195039896961956062895570062146947736340342927974992616678893372744261954172873490878805483241196345881721164078651156067119957816422768524442025688079462656755605982104174001635345874022133045402344010045961111720151990412034477755851802769069309069018738541854130183692204758761427121279982002993939745343695671900015296790637464880337375511536424796890996526681200633086841036320395847725935744757993013352804650575068136129295591306569213300156333650910795946800820067494143364885842896291126137320

n2 = 20918819960648891349438263046954902210959146407860980742165930253781318759285692492511475263234242002509419079545644051755251311392635763412553499744506421566074721268822337321637265942226790343839856182100575539845358877493718334237585821263388181126545189723429262149630651289446553402190531135520836104217160268349688525168375213462570213612845898989694324269410202496871688649978370284661017399056903931840656757330859626183773396574056413017367606446540199973155630466239453637232936904063706551160650295031273385619470740593510267285957905801566362502262757750629162937373721291789527659531499435235261620309759
c2 = 15819636201971185538694880505120469332582151856714070824521803121848292387556864177196229718923770810072104155432038682511434979353089791861087415144087855679134383396897817458726543883093567600325204596156649305930352575274039425470836355002691145864435755333821133969266951545158052745938252574301327696822347115053614052423028835532509220641378760800693351542633860702225772638930501021571415907348128269681224178300248272689705308911282208685459668200507057183420662959113956077584781737983254788703048275698921427029884282557468334399677849962342196140864403989162117738206246183665814938783122909930082802031855

n3 = 25033254625906757272369609119214202033162128625171246436639570615263949157363273213121556825878737923265290579551873824374870957467163989542063489416636713654642486717219231225074115269684119428086352535471683359486248203644461465935500517901513233739152882943010177276545128308412934555830087776128355125932914846459470221102007666912211992310538890654396487111705385730502843589727289829692152177134753098649781412247065660637826282055169991824099110916576856188876975621376606634258927784025787142263367152947108720757222446686415627479703666031871635656314282727051189190889008763055811680040315277078928068816491
c3 = 4185308529416874005831230781014092407198451385955677399668501833902623478395669279404883990725184332709152443372583701076198786635291739356770857286702107156730020004358955622511061410661058982622055199736820808203841446796305284394651714430918690389486920560834672316158146453183789412140939029029324756035358081754426645160033262924330248675216108270980157049705488620263485129480952814764002865280019185127662449318324279383277766416258142275143923532168798413011028271543085249029048997452212503111742302302065401051458066585395360468447460658672952851643547193822775218387853623453638025492389122204507555908862

n4 = 21206968097314131007183427944486801953583151151443627943113736996776787181111063957960698092696800555044199156765677935373149598221184792286812213294617749834607696302116136745662816658117055427803315230042700695125718401646810484873064775005221089174056824724922160855810527236751389605017579545235876864998419873065217294820244730785120525126565815560229001887622837549118168081685183371092395128598125004730268910276024806808565802081366898904032509920453785997056150497645234925528883879419642189109649009132381586673390027614766605038951015853086721168018787523459264932165046816881682774229243688581614306480751
c4 = 4521038011044758441891128468467233088493885750850588985708519911154778090597136126150289041893454126674468141393472662337350361712212694867311622970440707727941113263832357173141775855227973742571088974593476302084111770625764222838366277559560887042948859892138551472680654517814916609279748365580610712259856677740518477086531592233107175470068291903607505799432931989663707477017904611426213770238397005743730386080031955694158466558475599751940245039167629126576784024482348452868313417471542956778285567779435940267140679906686531862467627238401003459101637191297209422470388121802536569761414457618258343550613

n5 = 22822039733049388110936778173014765663663303811791283234361230649775805923902173438553927805407463106104699773994158375704033093471761387799852168337898526980521753614307899669015931387819927421875316304591521901592823814417756447695701045846773508629371397013053684553042185725059996791532391626429712416994990889693732805181947970071429309599614973772736556299404246424791660679253884940021728846906344198854779191951739719342908761330661910477119933428550774242910420952496929605686154799487839923424336353747442153571678064520763149793294360787821751703543288696726923909670396821551053048035619499706391118145067
c5 = 15406498580761780108625891878008526815145372096234083936681442225155097299264808624358826686906535594853622687379268969468433072388149786607395396424104318820879443743112358706546753935215756078345959375299650718555759698887852318017597503074317356745122514481807843745626429797861463012940172797612589031686718185390345389295851075279278516147076602270178540690147808314172798987497259330037810328523464851895621851859027823681655934104713689539848047163088666896473665500158179046196538210778897730209572708430067658411755959866033531700460551556380993982706171848970460224304996455600503982223448904878212849412357

n6 = 21574139855341432908474064784318462018475296809327285532337706940126942575349507668289214078026102682252713757703081553093108823214063791518482289846780197329821139507974763780260290309600884920811959842925540583967085670848765317877441480914852329276375776405689784571404635852204097622600656222714808541872252335877037561388406257181715278766652824786376262249274960467193961956690974853679795249158751078422296580367506219719738762159965958877806187461070689071290948181949561254144310776943334859775121650186245846031720507944987838489723127897223416802436021278671237227993686791944711422345000479751187704426369
c6 = 20366856150710305124583065375297661819795242238376485264951185336996083744604593418983336285185491197426018595031444652123288461491879021096028203694136683203441692987069563513026001861435722117985559909692670907347563594578265880806540396777223906955491026286843168637367593400342814725694366078337030937104035993569672959361347287894143027186846856772983058328919716702982222142848848117768499996617588305301483085428547267337070998767412540225911508196842253134355901263861121500650240296746702967594224401650220168780537141654489215019142122284308116284129004257364769474080721001708734051264841350424152506027932

n7 = 25360227412666612490102161131174584819240931803196448481224305250583841439581008528535930814167338381983764991296575637231916547647970573758269411168219302370541684789125112505021148506809643081950237623703181025696585998044695691322012183660424636496897073045557400768745943787342548267386564625462143150176113656264450210023925571945961405709276631990731602198104287528528055650050486159837612279600415259486306154947514005408907590083747758953115486124865486720633820559135063440942528031402951958557630833503775112010715604278114325528993771081233535247118481765852273252404963430792898948219539473312462979849137
c7 = 19892772524651452341027595619482734356243435671592398172680379981502759695784087900669089919987705675899945658648623800090272599154590123082189645021800958076861518397325439521139995652026377132368232502108620033400051346127757698623886142621793423225749240286511666556091787851683978017506983310073524398287279737680091787333547538239920607761080988243639547570818363788673249582783015475682109984715293163137324439862838574460108793714172603672477766831356411304446881998674779501188163600664488032943639694828698984739492200699684462748922883550002652913518229322945040819064133350314536378694523704793396169065179

n8 = 22726855244632356029159691753451822163331519237547639938779517751496498713174588935566576167329576494790219360727877166074136496129927296296996970048082870488804456564986667129388136556137013346228118981936899510687589585286517151323048293150257036847475424044378109168179412287889340596394755257704938006162677656581509375471102546261355748251869048003600520034656264521931808651038524134185732929570384705918563982065684145766427962502261522481994191989820110575981906998431553107525542001187655703534683231777988419268338249547641335718393312295800044734534761692799403469497954062897856299031257454735945867491191
c8 = 6040119795175856407541082360023532204614723858688636724822712717572759793960246341800308149739809871234313049629732934797569781053000686185666374833978403290525072598774001731350244744590772795701065129561898116576499984185920661271123665356132719193665474235596884239108030605882777868856122378222681140570519180321286976947154042272622411303981011302586225630859892731724640574658125478287115198406253847367979883768000812605395482952698689604477719478947595442185921480652637868335673233200662100621025061500895729605305665864693122952557361871523165300206070325660353095592778037767395360329231331322823610060006

n9 = 23297333791443053297363000786835336095252290818461950054542658327484507406594632785712767459958917943095522594228205423428207345128899745800927319147257669773812669542782839237744305180098276578841929496345963997512244219376701787616046235397139381894837435562662591060768476997333538748065294033141610502252325292801816812268934171361934399951548627267791401089703937389012586581080223313060159456238857080740699528666411303029934807011214953984169785844714159627792016926490955282697877141614638806397689306795328344778478692084754216753425842557818899467945102646776342655167655384224860504086083147841252232760941
c9 = 5418120301208378713115889465579964257871814114515046096090960159737859076829258516920361577853903925954198406843757303687557848302302200229295916902430205737843601806700738234756698575708612424928480440868739120075888681672062206529156566421276611107802917418993625029690627196813830326369874249777619239603300605876865967515719079797115910578653562787899019310139945904958024882417833736304894765433489476234575356755275147256577387022873348906900149634940747104513850154118106991137072643308620284663108283052245750945228995387803432128842152251549292698947407663643895853432650029352092018372834457054271102816934

n10 = 28873667904715682722987234293493200306976947898711255064125115933666968678742598858722431426218914462903521596341771131695619382266194233561677824357379805303885993804266436810606263022097900266975250431575654686915049693091467864820512767070713267708993899899011156106766178906700336111712803362113039613548672937053397875663144794018087017731949087794894903737682383916173267421403408140967713071026001874733487295007501068871044649170615709891451856792232315526696220161842742664778581287321318748202431466508948902745314372299799561625186955234673012098210919745879882268512656931714326782335211089576897310591491
c10 = 9919880463786836684987957979091527477471444996392375244075527841865509160181666543016317634963512437510324198702416322841377489417029572388474450075801462996825244657530286107428186354172836716502817609070590929769261932324275353289939302536440310628698349244872064005700644520223727670950787924296004296883032978941200883362653993351638545860207179022472492671256630427228461852668118035317021428675954874947015197745916918197725121122236369382741533983023462255913924692806249387449016629865823316402366017657844166919846683497851842388058283856219900535567427103603869955066193425501385255322097901531402103883869

n11 = 22324685947539653722499932469409607533065419157347813961958075689047690465266404384199483683908594787312445528159635527833904475801890381455653807265501217328757871352731293000303438205315816792663917579066674842307743845261771032363928568844669895768092515658328756229245837025261744260614860746997931503548788509983868038349720225305730985576293675269073709022350700836510054067641753713212999954307022524495885583361707378513742162566339010134354907863733205921845038918224463903789841881400814074587261720283879760122070901466517118265422863420376921536734845502100251460872499122236686832189549698020737176683019
c11 = 1491527050203294989882829248560395184804977277747126143103957219164624187528441047837351263580440686474767380464005540264627910126483129930668344095814547592115061057843470131498075060420395111008619027199037019925701236660166563068245683975787762804359520164701691690916482591026138582705558246869496162759780878437137960823000043988227303003876410503121370163303711603359430764539337597866862508451528158285103251810058741879687875218384160282506172706613359477657215420734816049393339593755489218588796607060261897905233453268671411610631047340459487937479511933450369462213795738933019001471803157607791738538467

n12 = 27646746423759020111007828653264027999257847645666129907789026054594393648800236117046769112762641778865620892443423100189619327585811384883515424918752749559627553637785037359639801125213256163008431942593727931931898199727552768626775618479833029101249692573716030706695702510982283555740851047022672485743432464647772882314215176114732257497240284164016914018689044557218920300262234652840632406067273375269301008409860193180822366735877288205783314326102263756503786736122321348320031950012144905869556204017430593656052867939493633163499580242224763404338807022510136217187779084917996171602737036564991036724299
c12 = 21991524128957260536043771284854920393105808126700128222125856775506885721971193109361315961129190814674647136464887087893990660894961612838205086401018885457667488911898654270235561980111174603323721280911197488286585269356849579263043456316319476495888696219344219866516861187654180509247881251251278919346267129904739277386289240394384575124331135655943513831009934023397457082184699737734388823763306805326430395849935770213817533387235486307008892410920611669932693018165569417445885810825749609388627231235840912644654685819620931663346297596334834498661789016450371769203650109994771872404185770230172934013971

n13 = 20545487405816928731738988374475012686827933709789784391855706835136270270933401203019329136937650878386117187776530639342572123237188053978622697282521473917978282830432161153221216194169879669541998840691383025487220850872075436064308499924958517979727954402965612196081404341651517326364041519250125036424822634354268773895465698920883439222996581226358595873993976604699830613932320720554130011671297944433515047180565484495191003887599891289037982010216357831078328159028953222056918189365840711588671093333013117454034313622855082795813122338562446223041211192277089225078324682108033843023903550172891959673551
c13 = 14227439188191029461250476692790539654619199888487319429114414557975376308688908028140817157205579804059783807641305577385724758530138514972962209062230576107406142402603484375626077345190883094097636019771377866339531511965136650567412363889183159616188449263752475328663245311059988337996047359263288837436305588848044572937759424466586870280512424336807064729894515840552404756879590698797046333336445465120445087587621743906624279621779634772378802959109714400516183718323267273824736540168545946444437586299214110424738159957388350785999348535171553569373088251552712391288365295267665691357719616011613628772175

n14 = 27359727711584277234897157724055852794019216845229798938655814269460046384353568138598567755392559653460949444557879120040796798142218939251844762461270251672399546774067275348291003962551964648742053215424620256999345448398805278592777049668281558312871773979931343097806878701114056030041506690476954254006592555275342579529625231194321357904668512121539514880704046969974898412095675082585315458267591016734924646294357666924293908418345508902112711075232047998775303603175363964055048589769318562104883659754974955561725694779754279606726358588862479198815999276839234952142017210593887371950645418417355912567987
c14 = 3788529784248255027081674540877016372807848222776887920453488878247137930578296797437647922494510483767651150492933356093288965943741570268943861987024276610712717409139946409513963043114463933146088430004237747163422802959250296602570649363016151581364006795894226599584708072582696996740518887606785460775851029814280359385763091078902301957226484620428513604630585131511167015763190591225884202772840456563643159507805711004113901417503751181050823638207803533111429510911616160851391754754434764819568054850823810901159821297849790005646102129354035735350124476838786661542089045509656910348676742844957008857457

n15 = 27545937603751737248785220891735796468973329738076209144079921449967292572349424539010502287564030116831261268197384650511043068738911429169730640135947800885987171539267214611907687570587001933829208655100828045651391618089603288456570334500533178695238407684702251252671579371018651675054368606282524673369983034682330578308769886456335818733827237294570476853673552685361689144261552895758266522393004116017849397346259119221063821663280935820440671825601452417487330105280889520007917979115568067161590058277418371493228631232457972494285014767469893647892888681433965857496916110704944758070268626897045014782837
c15 = 14069112970608895732417039977542732665796601893762401500878786871680645798754783315693511261740059725171342404186571066972546332813667711135661176659424619936101038903439144294886379322591635766682645179888058617577572409307484708171144488708410543462972008179994594087473935638026612679389759756811490524127195628741262871304427908481214992471182859308828778119005750928935764927967212343526503410515793717201360360437981322576798056276657140363332700714732224848346808963992302409037706094588964170239521193589470070839790404597252990818583717869140229811712295005710540476356743378906642267045723633874011649259842

n16 = 25746162075697911560263181791216433062574178572424600336856278176112733054431463253903433128232709054141607100891177804285813783247735063753406524678030561284491481221681954564804141454666928657549670266775659862814924386584148785453647316864935942772919140563506305666207816897601862713092809234429096584753263707828899780979223118181009293655563146526792388913462557306433664296966331469906428665127438829399703002867800269947855869262036714256550075520193125987011945192273531732276641728008406855871598678936585324782438668746810516660152018244253008092470066555687277138937298747951929576231036251316270602513451
c16 = 17344284860275489477491525819922855326792275128719709401292545608122859829827462088390044612234967551682879954301458425842831995513832410355328065562098763660326163262033200347338773439095709944202252494552172589503915965931524326523663289777583152664722241920800537867331030623906674081852296232306336271542832728410803631170229642717524942332390842467035143631504401140727083270732464237443915263865880580308776111219718961746378842924644142127243573824972533819479079381023103585862099063382129757560124074676150622288706094110075567706403442920696472627797607697962873026112240527498308535903232663939028587036724

n17 = 23288486934117120315036919418588136227028485494137930196323715336208849327833965693894670567217971727921243839129969128783853015760155446770590696037582684845937132790047363216362087277861336964760890214059732779383020349204803205725870225429985939570141508220041286857810048164696707018663758416807708910671477407366098883430811861933014973409390179948577712579749352299440310543689035651465399867908428885541237776143404376333442949397063249223702355051571790555151203866821867908531733788784978667478707672984539512431549558672467752712004519300318999208102076732501412589104904734983789895358753664077486894529499
c17 = 10738254418114076548071448844964046468141621740603214384986354189105236977071001429271560636428075970459890958274941762528116445171161040040833357876134689749846940052619392750394683504816081193432350669452446113285638982551762586656329109007214019944975816434827768882704630460001209452239162896576191876324662333153835533956600295255158377025198426950944040643235430211011063586032467724329735785947372051759042138171054165854842472990583800899984893232549092766400510300083585513014171220423103452292891496141806956300396540682381668367564569427813092064053993103537635994311143010708814851867239706492577203899024

n18 = 19591441383958529435598729113936346657001352578357909347657257239777540424811749817783061233235817916560689138344041497732749011519736303038986277394036718790971374656832741054547056417771501234494768509780369075443550907847298246275717420562375114406055733620258777905222169702036494045086017381084272496162770259955811174440490126514747876661317750649488774992348005044389081101686016446219264069971370646319546429782904810063020324704138495608761532563310699753322444871060383693044481932265801505819646998535192083036872551683405766123968487907648980900712118052346174533513978009131757167547595857552370586353973
c18 = 3834917098887202931981968704659119341624432294759361919553937551053499607440333234018189141970246302299385742548278589896033282894981200353270637127213483172182529890495903425649116755901631101665876301799865612717750360089085179142750664603454193642053016384714515855868368723508922271767190285521137785688075622832924829248362774476456232826885801046969384519549385428259591566716890844604696258783639390854153039329480726205147199247183621535172450825979047132495439603840806501254997167051142427157381799890725323765558803808030109468048682252028720241357478614704610089120810367192414352034177484688502364022887

n19 = 19254242571588430171308191757871261075358521158624745702744057556054652332495961196795369630484782930292003238730267396462491733557715379956969694238267908985251699834707734400775311452868924330866502429576951934279223234676654749272932769107390976321208605516299532560054081301829440688796904635446986081691156842271268059970762004259219036753174909942343204432795076377432107630203621754552804124408792358220071862369443201584155711893388877350138023238624566616551246804054720492816226651467017802504094070614892556444425915920269485861799532473383304622064493223627552558344088839860178294589481899206318863310603
c19 = 6790553533991297205804561991225493105312398825187682250780197510784765226429663284220400480563039341938599783346724051076211265663468643826430109013245014035811178295081939958687087477312867720289964506097819762095244479129359998867671811819738196687884696680463458661374310994610760009474264115750204920875527434486437536623589684519411519100170291423367424938566820315486507444202022408003879118465761273916755290898112991525546114191064022991329724370064632569903856189236177894007766690782630247443895358893983735822824243487181851098787271270256780891094405121947631088729917398317652320497765101790132679171889

n20 = 26809700251171279102974962949184411136459372267620535198421449833298448092580497485301953796619185339316064387798092220298630428207556482805739803420279056191194360049651767412572609187680508073074653291350998253938793269214230457117194434853888765303403385824786231859450351212449404870776320297419712486574804794325602760347306432927281716160368830187944940128907971027838510079519466846176106565164730963988892400240063089397720414921398936399927948235195085202171264728816184532651138221862240969655185596628285814057082448321749567943946273776184657698104465062749244327092588237927996419620170254423837876806659
c20 = 386213556608434013769864727123879412041991271528990528548507451210692618986652870424632219424601677524265011043146748309774067894985069288067952546139416819404039688454756044862784630882833496090822568580572859029800646671301748901528132153712913301179254879877441322285914544974519727307311002330350534857867516466612474769753577858660075830592891403551867246057397839688329172530177187042229028685862036140779065771061933528137423019407311473581832405899089709251747002788032002094495379614686544672969073249309703482556386024622814731015767810042969813752548617464974915714425595351940266077021672409858645427346

n = [n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11,
     n12, n13, n14, n15, n16, n17, n18, n19, n20]

for i in range(len(n)):
    for j in range(i+1, len(n)):
        if (gmpy2.gcd(n[i], n[j]) != 1):
            print(i, j)

e = 65537

p = gmpy2.gcd(n5,n18)
print(p)
q = n5 // p
phi = (p-1)*(q-1)
d = gmpy2.invert(e, phi)

m = gmpy2.powmod(c5,d,n5)
print(long_to_bytes(m))
# b'flag{abdcbe5fd94e23b3de429223ab9c2fdf}'

BUUCTF RSA & what

import base64
import gmpy2
from Crypto.Util.number import long_to_bytes

def common_modulus_attack(c1, c2, e1, e2, n):
    # 扩展欧几里得算法找到 a 和 b
    g, a, b = gmpy2.gcdext(e1, e2)

    # 确保 e1 和 e2 互质
    if g != 1:
        raise ValueError("e1 和 e2 必须互质")

    # 计算 c1^a 和 c2^b
    if a < 0:
        c1 = gmpy2.invert(c1, n)
        a = -a
    if b < 0:
        c2 = gmpy2.invert(c2, n)
        b = -b

    m1 = gmpy2.powmod(c1, a, n)
    m2 = gmpy2.powmod(c2, b, n)

    # 恢复消息 m
    m = (m1 * m2) % n
    return m


n = 785095419718268286866508214304816985447077293766819398728046411166917810820484759314291028976498223661229395009474063173705162627037610993539617751905443039278227583504604808251931083818909467613277587874545761074364427549966555519371913859875313577282243053150056274667798049694695703660313532933165449312949725581708965417273055582216295994587600975970124811496270080896977076946000102701030260990598181466447208054713391526313700681341093922240317428173599031624125155188216489476825606191521182034969120343287691181300399683515414809262700457525876691808180257730351707673660380698973884642306898810000633684878715402823143549139850732982897459698089649561190746850698130299458080255582312696873149210028240898137822888492559957665067936573356367589784593119016624072433872744537432005911668494455733330689385141214653091888017782049043434862620306783436169856564175929871100669913438980899219579329897753233450934770193915434791427728636586218049874617231705308003720066269312729135764175698611068808404054125581540114956463603240222497919384691718744014002554201602395969312999994159599536026359879060218056496345745457493919771337601177449899066579857630036350871090452649830775029695488575574985078428560054253180863725364147
e1 = 1697
e2 = 599

c1 = []
c2 = []

with open('HUB1') as f:
    for line in f.readlines():
        c1.append(line.strip())

with open('HUB2') as f:
    for line in f.readlines():
        c2.append(line.strip())


m = b''
for c_1, c_2 in zip(c1,c2):
    m += long_to_bytes(common_modulus_attack(int(c_1), int(c_2), e1, e2, n))

# Base64隐写
base64chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
bin_str = ''
for line in m.split(b'\n'):
    stegb64 = str(line, 'utf-8').strip('\n')
    rowb64 = str(base64.b64encode(base64.b64decode(stegb64)), 'utf-8').strip('\n')
    offset = abs(base64chars.index(stegb64.replace('=', '')[-1]) - base64chars.index(rowb64.replace('=', '')[-1]))

    equalnum = stegb64.count('=')  # no equalnum no offset
    if equalnum:
        bin_str += bin(offset)[2:].zfill(equalnum * 2)
    res = [chr(int(bin_str[i:i + 8], 2)) for i in range(0, len(bin_str), 8)]

flag = ''.join(res)
print(flag)

# 7c86d8f7d6de33a87f7f9d6b005ce640

参考资料

TMUCTF 2021

from Crypto.Util.number import *
from functools import reduce


def encrypt(msg, n):
    enc = pow(bytes_to_long(msg), e, n)
    return enc


e = 65537

primes = [getPrime(2048) for i in range(5)]
n = reduce(lambda a, x: a * x, primes, 1)
print(n)

x1 = primes[1] ** 2
x2 = primes[2] ** 2
x3 = primes[1] * primes[2]
y1 = x1 * primes[2] + x2 * primes[1]
y2 = x2 * (primes[3] + 1) - 1
y3 = x3 * (primes[3] + 1) - 1
print(x2 + x3 + y1)
print(y2 + y3)

with open('flag', 'rb') as f:
    flag = f.read()
    print(encrypt(flag, n))

\[\begin{align} n &= p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 \

x_2 + x_3 + y_1 &= p_2^2 + p_1p_2 + p_1^2p_2 + p_2^2p_1 = p_2(p_1+p_2)(p_1+1) = h_1 \

\therefore p_2 &= \gcd(n,h_1)

\end{align}\]

\( n \)和$x_2 + x_3 + y_1 \)有公约数\( p_2 \)，进而通过解一元二次方程可求\( p_1 \)

\[ p_1^2p_2 + (p_2^2 + p_2)p_1 + (p_2 - h_1) = 0 \ \]

\[ \therefore p_1 = \frac{-(p_2^2 + p_2) \pm \sqrt{(p_2^2 + p_2)^2 - 4p_2(p_2 - h_1)}}{2p_2} \]

求\( p_3 \)

\[ \begin{align*} y_2 + y_3 &= p_2^2 \cdot (p_3 + 1) - 1 + p_1p_2 \cdot (p_3 + 1) - 1 = (p_3 + 1)(p_2^2 + p_1p_2) = h_2 \ h_2 + 2 &= (p_3 + 1) \cdot (p_2^2 + p_1 \cdot p_2) \ p_3 &= \frac{(h_2 + 2)}{(p_2^2 + p_1 \cdot p_2)} - 1 \end{align*} \]

#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import *

n = 2870378965838324591930716372043943202857808446139955114178972466357197191646555386310681233993639582571871810351336802365212612829432807326876330070965674249357286034347008657883629500396346167749508691814871533203247809103597516756034759095100637453841622270471713637175966387708675681650825362129940918643196769504213592200456774778948694877618977617011530883570013644245183319361244368215398610979149060320165814554577615652211730789657513270358973557241707978338139984414979470166202562114202380919071164176972055791789476453657467515306951139381362369978138151345609568127199377878026652554062731521632501476705069316208464363846111869669167682507916421047852441782552255491492824812854004513204360809331798274954243569021433963906972169417423418831314860109084130511234616069241809687828168649890352090249712449906176079861456197001597695071378819897916782564243557316380779536239285819430145429214343617897807321057453881231873109668847371444981597545948164776111805671836878974593063507806022594658899187647227705150195530817678931698098259376629125579883657290675365061062988342506737677539253213873486072882314916722654639439974767729667348308089822272618812141734747518190918131475394008358752485820114352585363697943409142405397187811488425763607870435598703473283558863875082511735753198985761770194691897333996772347209579690094484306582887604607085834235579991339081114877411129747659636913741732353593602493602935647498099959376575507080043282822039059772712513621914435714472997174303938650778721067511657786410145042462581432379653230157438512241441297394613009093982995995721488753402291657942043365728675978004538612865075473060797997060824242663659400972803009150895091065010288979279208343727383126907536910816233381252213949988179391769784859432462536001028414576853626404313552019318821609411415846740546897494827049963081729773556670009694396655902808674253954003664489541274216766985514320658655385155404804471285629385163182065527325960787883285164384400671878810956747078706832300082761043350763868511932582950753204256098035119847645083342729287063167616495769840389702639642784779646124394274187760742667519368210034941587941073935227051959905320338654629277413407444919186684576561532634097854731829455621571431402040561443044139818425476711378475625762558700335148767065032908314020963523681108498054768101383636397920349166462138683843364568104852099786972138269207828354678771871957631305996408564918629611147162610100969994085549017653854895147761379806516965159036735885697873629236958604838297316909096866364056640064200671318939446575088736134834054178902097259981395846912668763412552618135586399374878369079393695944896480784503275721233694160817424918386850099538763638119036532611566641652505437494379272489263685110137046574303306123483008690943610001403933721637756187395490525025216826398321326468190996213618276820580272764947465497924136451423383678199000687060571477421196675667167891260178408652655959836575935636974063946514718181746525031519883430143656783652516536859306736796341726896446635046579279623124614077795247335483809777
h1 = 12189833951051730908370223331850919218243946952509718500560332838832804241963905158328421240593088009803147267463017892895712859666255758374859924227795693977692365712139787589267299790301022569583587926463070427550028215313969101326713297706315888193599192042874908901003626554054277955414415385731879026734954423731345798786722561845058120971545040892322209486011914785265062492920550158388814114563652053556586072198675716423094480300266767587890740892336081818352390563087579428787330255230317293748493589325405374600751428190100372051406745392483110379355174892921101536441200795867134576643519454074015675127266952070892796128379921598800605300182483946129377809823776730697790309647647190307296418381398693697240748290194721934318854836676911877413259621512269954316351093519057413607079769428640924051837599266617014518297183874986708528679104069884291849234025193207298171674607085234765320663128701647504631036578515249726222498212335082588627266250272379931767054363936707282364911659508871646177814796817889070190457673852047527357122774587607849820636184925240369923701314690600711989307878295308586902537853388274176578719581752448488589031302166298788451585838083076238353895213222535414766363665801955518856592943846521495707362179018672726109435436743723238172556767198562368516144637629110267835795311939660130673691902395560229758574266655957155862216872908603510940031334166746559195296408939506394470132257044581183533463281253397503463926598923844457702097679565967501579961386522021817780961888842972793029114864422478835769322906292819387383748603289494044561725080616097794190650081867485792883883943744138857860775053197775476414639386004107927910470986208356664914803636501181816689051948285860692212458532201937837589900582214489550639269506433713180672869129866286880957012266595540883727015907677897402607614096813204000
h2 = 10685466258462426438601930063854796559353071021872734112422666943995273083147678402485604005469990666166510724614508657976179169486278649913444601773228981194010779012945440827279478889951033722845969569487499109114807920422465585370352647531485228491726069752258604141544095143726497561287074963919306162501333879324320431815063767836881722714585596416818455332140968159290951800146179728839649549885714902391429304093259377977040947324691472037003260741076844850530123289350979761389302226559515709663477520315215796685387805223395013156063533568746725754875786890572455450963004254041206457627272694223378868063657567852741748730175173641019445706089775572094353061394171203735646557579595881047090069929263278434116703002648581646489410683234908239597741887334283851760107425225954878508549100715448112116790430791154066542690753466803004681805878269979001221299212426591974298670638899337600244969172572955344326969720268282445856163235666525453179028071857247486445419793906307197739042430106158187925914823345884448535360673122213977744765084269696399126350806729338388901052234851028732099724640679744428962810579433414095277730427540297789173682400086721025827804724736734372677509987948167038979141434755652392244734118982644329505761227780128318076798321983092557417882569724665849318066642854479540185619304472196160849810402529549850401440730174222018187759986936759639741288629098555521157461858554745777119186003733147607872641752914478401134544544581877108606144844955497062864711396338329584713840695858914573229254445387595034317081334732222156791041901660170883047145528155203729023944309061959449827690809614300474069217485344927501901373264278607167662413547572497683805087479857076246143962932587232903893219862365333270757997373558132982228573327073639550742090562057353483860863787775987229835303262050707215194078693398663198
c = 1295564702637495685309272079895645034267002212576577351176786924725825901033456751565363132227845395192636014504044948379030468685845611242265523726539023437126669783303765124723915472786629678436713048730755297486348344599742142845784560313837239832937917360379066282667491918054529416764918515780567145928364634646722930481542026187360739697820492335622597715014255829089436910724972509085963133800806856075152036053630879580926838241308921405124424958500485001162000846198656477271924822124768722799190195854806533587717469450248664509344104461703840455934612539385694033634268205463024167234754553081069919678171898669570723347606172526826003367647892759191360901723076962059024693433937573808414595918813154817183122218324304727720231993955442001953029300266308755291774280607633683770298830407751731984235360718897231362141728129903067324174378760053260419744395257753779565716943029464080442902252184316484343234160161564121269883788523966796266675498603214422442299610994620373055814615356464754724264668947373104292350153322562799134518201535870142301501474217531998628211638040128486684200215958700680344308113382908656637378359217107811764695801417920230331446471475336055801665419851805385433677261916024902543165187462517860936690178095112472342793009281361928879367602088695738746822374043544415398979893735410561210643701354068887205774369902436302903034048756740583183966251194450689131063910079690811851244607443172434856486129471747053074648343069627212505795579741010868965206480675568896896528625130571758075102146302306655426190892962618128161759734724982773347245232038629926619247273436934947196867813659364951484832193239178102156204300353342841972762595259292048840326449938071520689839586933982775979336248771535685895403976612898604059800532915376510948151614460338199157528220842025853852584958511622657382701623309639101678362821929006062524756352592131742510350318470015268920615837821556797760508924258618057921324240995910743034414956163701330735308503014893515707188853735706296571253748889626515245648558769422283608966241496382223293119306642490794180175154686106323945765280777140420938641267467633112805720348438191023736935327334544026698324629536721807051447503613438954736205208639453193587326470160505597834244792859179593877840449441035962707113092034561698560285482507381177956117498938436596192528337690808299050972992206796450167499247505347105318901580848542927515381051973057219542622235114029773502036331075236848879130640275120244541018979621405480997745366565533911987665660584132852855158311718515145400486762846976972483867689062569575052791463761762637757579908921446285546575036947648139847182684615282524513693899858284291993167395096893612172061860682116974864364966362118833708791957224527084022917788839602167742342150067548893185747653708657029597051779997866982601553339504636518951723213334104705177572536156329378433835224612846933662252315126902599937489337158843870992464520248466088492159756466651557918397098886626028193224320040156124777562920457488126430654110240828124538167742484933802988652725530546987842196376
e = 65537

p2 = gmpy2.gcd(h1, n)
p22 = p2**2
p1 = (-(p22+p2) + gmpy2.isqrt((p22+p2)**2 - 4*p2*(p22-h1))) // (2*p2)
p3 = (h2+2)//(p22 + p1*p2) - 1

assert all(isPrime(p) for p in [p1,p2,p3])

N = p1*p2*p3
phi = (p1-1)*(p2-1)*(p3-1)
d = gmpy2.invert(e, phi)
m = gmpy2.powmod(c,d,N)
print(long_to_bytes(m))

# TMUCTF{Y35!!!__M4Y_N0t_4lW4y5_N33d_4ll_p21M3_f4c70R5}