Crypto趣题-RSA(一)

该文章主要记录一些RSA相关的趣题，一篇十道题

RSA3

题目来源：2023江苏省领航杯

题目：

from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
p1, q1 = getPrime(512), getPrime(512)
n1 = p1*q1
e = 65537

p2, q2 = getPrime(512), getPrime(512)
n2 = p2*q2

print(f'n1 = {n1}')
print(f'n2 = {n2}')
print(f'c1 = {pow(m,e,n2)}')
print(f'c2 = {pow(n1-m,e,n2)}')

# n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
# n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
# c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
# c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005

题目意图很明确：明文线性相关，所以直接求解多项式gcd是可以做出来的。

不过问题在于，本题e很大，所以如果直接求解gcd，时间会花的较长(约30-40分钟)。因此学习了一波Half-gcd，这是一种能有效减少求解多项式的公因式所需时间的方法。

多项式 gcd 的正确姿势：Half-GCD 算法 - whx1003 - 博客园 (cnblogs.com)

exp.ipynb:

from Crypto.Util.number import *
import sys

def HGCD(a, b):
    if 2 * b.degree() <= a.degree() or a.degree() == 1:
        return 1, 0, 0, 1
    m = a.degree() // 2
    a_top, a_bot = a.quo_rem(x^m)
    b_top, b_bot = b.quo_rem(x^m)
    R00, R01, R10, R11 = HGCD(a_top, b_top)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    q, e = c.quo_rem(d)
    d_top, d_bot = d.quo_rem(x^(m // 2))
    e_top, e_bot = e.quo_rem(x^(m // 2))
    S00, S01, S10, S11 = HGCD(d_top, e_top)
    RET00 = S01 * R00 + (S00 - q * S01) * R10
    RET01 = S01 * R01 + (S00 - q * S01) * R11
    RET10 = S11 * R00 + (S10 - q * S11) * R10
    RET11 = S11 * R01 + (S10 - q * S11) * R11
    return RET00, RET01, RET10, RET11
    
def GCD(a, b):
    print(a.degree(), b.degree())
    q, r = a.quo_rem(b)
    if r == 0:
        return b
    R00, R01, R10, R11 = HGCD(a, b)
    c = R00 * a + R01 * b
    d = R10 * a + R11 * b
    if d == 0:
        return c.monic()
    q, r = c.quo_rem(d)
    if r == 0:
        return d
    return GCD(d, r)

sys.setrecursionlimit(500000)

e = 65537
n1 = 52579135273678950581073020233998071974221658902576724000130040488018033110534210901239397446395736563148970863970460542205225993317478251099451639165369081820130823165642873594136020122857712288395352930384057524510346112486008850200845915783772351449146183974239444691330777565342525218070680067550270554767
n2 = 68210568831848267339414957973218186686176324296418282565773310695862151827108036984694027795077376921170907068110296451176263520249799154781062517066423984526868547296781709439425857993705489037768605485740968600877866332458671029054092942851472208033494968784822459369206497698469167909174346042658361616469
c1 = 42941712708129054668823891960764339394032538100909746015733801598044118605733969558717842106784388091495719003761324737091667431446354282990525549196642753967283958283202592037329821712755519455155110675327321252333824912095517427885925854391047828862338332559137577789387455868761466777370476884779752953853
c2 = 62704043252861638895370674827559804184650708692227789532879941590038911799857232898692335429773480889624046167792573885125945511356456073688435911975161053231589019934427151230924004944847291434167067905803180207183209888082275583120633408232749119300200555327883719466349164062163459300518993952046873724005
R.<x> = PolynomialRing(Zmod(n2))
f = x^e - c1
g = (n1 - x)^e - c2

res = GCD(f,g)

m = -res.monic().coefficients()[0]
print(m)
flag = long_to_bytes(int(m))
print(flag)

flag:

CnHongKe{Fr4nkl1n_R31ter_4nd_gcD}

BUAA^AITMCLAB&Level4

题目来源：BUAA^AITMCLAB

题目：

from random import *

from Crypto.Util.number import *
from libnum import *


def nextprime(n):
    n = (n + 1) | 1
    while not isPrime(n):
        n += 2
    return n


flag = "********************"

m = s2n(flag)
"""
The getPrime() may not function properly, 
but it does not affect your understanding of the problem.
lzh hopes you could attack successfully!
"""
while True:
    try:
        p = getPrime(512)
        q = nextprime(p + randint(0, 2 ** 421))
        n = p * q
        phi = (p - 1) * (q - 1)
        d = randint(0, n ** 0.32)
        e = invmod(d, phi)
        c = pow(m, e, n)
        break
    except:
        continue

print("e = %d" % e)
print("n = %d" % n)
print("c = %d" % c)

'''
e = 127036799282947905048902487711584293137462029654908427023257952239618526367628289911517200900560275901894224980635962598874227610508820071266987288647014766036842887978917984803634331617282487399497533040203094883612898714070428079645997317171821336677275458853187399657424389496685642081231802149635762872559
n = 132088710602356228013302555046538954329350662026107113731378784700414952971644185280357218688811203701759378494801162526951176546636432770036424692378302192072727185223575484138108758895692654294532714346938723454356449079919300753046965831240595578485766587254369907195552714255698916905317581605325719354369
c = 37469551975972446825344827206550506280313465311789923639857075387733761352303008843234906464758618751401773666419762541561815375332688727694620079867717788238335220300725633402928195673814423768862538733435901134624477748268790427128392777900896313025911483334568923415572174037203375831796896263863229112204
'''
# try to find the 「flag」
# and don't forget to submit it to the platform

题目最有用的信息是：

• p和q高位相近
• d小于n^0.32

看到卡了d的界，第一反应就是低解密指数攻击，可以采用wiener attack或者boneh and durfee attack。但是问题在于：

• wiener attack：要求d小于$ \frac{1}{3}n^{\frac{1}{4}}$
• boneh and durfee attack：要求d小于n^0.292

而题目只界定了0.32，超过了两种攻击的范围。不过不要紧，首先试一试boneh and durfee attack，因为有不到1/8的概率成功(d在(0,n^0.32)随机生成，因此有1/8概率落在(0,n^0.29)的区间，因此可能会成功)

可惜的是失败了，那么就只能另寻他法。由题目条件可知，p、q高位相同这个额外信息肯定是需要用上的，以此来扩大能攻击的d的上界，但是并不知道怎么用。最后从Xenny师傅那里得到一篇论文：

http://ijns.jalaxy.com.tw/contents/ijns-v14-n2/ijns-2012-v14-n2-p80-85.pdf

关键部分：

这篇论文证明了：当p、q高位接近到一定程度时，$\frac{e}{n-2\sqrt{n}+1}$ 是 $\frac{k}{d}$ 的收敛子，并且拓宽了可以进行wiener attack攻击的d的上界。

因此只需要把wiener attack中的 n 改为 $n-2\sqrt{n}+1$ 即可。

exp.py：

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

e = 127036799282947905048902487711584293137462029654908427023257952239618526367628289911517200900560275901894224980635962598874227610508820071266987288647014766036842887978917984803634331617282487399497533040203094883612898714070428079645997317171821336677275458853187399657424389496685642081231802149635762872559
n = 132088710602356228013302555046538954329350662026107113731378784700414952971644185280357218688811203701759378494801162526951176546636432770036424692378302192072727185223575484138108758895692654294532714346938723454356449079919300753046965831240595578485766587254369907195552714255698916905317581605325719354369
c = 37469551975972446825344827206550506280313465311789923639857075387733761352303008843234906464758618751401773666419762541561815375332688727694620079867717788238335220300725633402928195673814423768862538733435901134624477748268790427128392777900896313025911483334568923415572174037203375831796896263863229112204

class ContinuedFraction():
    def __init__(self, numerator, denumerator):
        self.numberlist = []  # number in continued fraction
        self.fractionlist = []  # the near fraction list
        self.GenerateNumberList(numerator, denumerator)
        self.GenerateFractionList()

    def GenerateNumberList(self, numerator, denumerator):
        while numerator != 1:
            quotient = numerator // denumerator
            remainder = numerator % denumerator
            self.numberlist.append(quotient)
            numerator = denumerator
            denumerator = remainder

    def GenerateFractionList(self):
        self.fractionlist.append([self.numberlist[0], 1])
        for i in range(1, len(self.numberlist)):
            numerator = self.numberlist[i]
            denumerator = 1
            for j in range(i):
                temp = numerator
                numerator = denumerator + numerator * self.numberlist[i - j - 1]
                denumerator = temp
            self.fractionlist.append([numerator, denumerator])


a = ContinuedFraction(e, n-2*iroot(n,2)[0]+1)
for k, d in a.fractionlist:
    m = pow(c, d, n)
    flag = long_to_bytes(m)
    
    if b'aitmc' in flag:
        print(flag)

flag:

aitmc{W0Oo!!Y0u_3re_a_m3ster_of_W1ener_H3ck!!}

AITMCLAB quiz2

题目来源：AITMCLAB

题目：

# Welcome to quiz2!!!
from AITMCLab.libnum import s2n
from Crypto.Util.number import isPrime
from random import randint

p = 104879397075344024438671231239628115011303349344697797964879592144922079000957 
q = 104879397075344024438671231239628115011303349344697797964879592144922079001013
assert isPrime(p) and isPrime(q)
n = p * q
flag = s2n('flag{************}')
r = randint(1, n)
c = (pow(n + 1, flag, n * n) * pow(r, n, n * n)) % (n * n)
print (c)
# 13134489820394613222282607681686272081419875146946401883172682167011759113388373349180457979897848113275982219264879081189886853062717764580364698888338032141434053832247476010400449272010082460437747190468766740274587999336359171283098137261396013153130265440425676242061845667887640808895666325466803989428

题目本身应该还需要求一下p、q的，但是直接给好了那就用给好的做吧。

发现加密就一步，如下：

$$c\equiv (n+1)^{flag}*r^n\quad(mod\;n^2)$$

其中，r是一个随机数，且题目未给出。

首先，由于模 $ n^2$ 的缘故，$ (n+1)^{flag}$ 可以用二项式定理展开，然后消掉大部分项：

$$(n+1)^{flag} \equiv n*flag+1\quad(mod\;n^2)$$

因此有：

$$c\equiv (n*flag+1)*r^n\quad(mod\;n^2)$$

r 是未知的随机数，因此要消掉，消掉 r 的方式类似于 RSA 的解密过程，如下：

因为：

$$\phi(n^2) = \phi(p^2q^2) = \phi(p^2)\phi(q^2) = pq(p-1)(q-1)$$

所以 ：

$$c^{(p-1)(q-1)} \equiv ((n*flag+1)*r^n)^{(p-1)(q-1)} \quad(mod\;n^2)$$

即 ：

$$c^{(p-1)(q-1)} \equiv (n*flag+1)^{(p-1)(q-1)}*r^{n(p-1)(q-1)} \quad(mod\;n^2)$$

注意到上式中：

$$r^{n(p-1)(q-1)}\equiv r^{\phi(n^2)}\equiv 1\quad(mod\;n^2)$$

因此就消掉了 r，得到：

$$c^{(p-1)(q-1)} \equiv (n*flag+1)^{(p-1)(q-1)} \quad(mod\;n^2)$$

右侧的式子又可以用二项式定理展开，得到：

$$(n*flag+1)^{(p-1)(q-1)}\equiv (p-1)(q-1)n*flag+1 \quad(mod\;n^2)$$

因此：

$$c^{(p-1)(q-1)}\equiv (p-1)(q-1)n*flag+1 \quad(mod\;n^2)$$

减一，除以n后，再求(p-1)(q-1)对n^2的逆元即可，但是会发现求出的模 n^2 下的并不是最终的 flag，猜测可能题目原本题面还有额外信息界定了 flag 的范围，那么转到模 n 下即可得到最终flag。

exp.py：

from Crypto.Util.number import *

p = 104879397075344024438671231239628115011303349344697797964879592144922079000957 
q = 104879397075344024438671231239628115011303349344697797964879592144922079001013
n = p * q
c = 13134489820394613222282607681686272081419875146946401883172682167011759113388373349180457979897848113275982219264879081189886853062717764580364698888338032141434053832247476010400449272010082460437747190468766740274587999336359171283098137261396013153130265440425676242061845667887640808895666325466803989428

m = (pow(c,(p-1)*(q-1),n**2) - 1) // n * inverse((p-1)*(q-1),n**2) % n
print(long_to_bytes(m))

flag：

flag{can_you_find_me??}

2048bit e

题目来源：暂不明确

题目：

from Crypto.Util.number import getPrime, getStrongPrime, bytes_to_long
from sympy import factorial
from random import randint
from secret import flag

p, q = getStrongPrime(1024), getStrongPrime(1024)

def RSAgen(e = None):
    d = 0
    if not e:
        while(d.bit_length() < 2047):
            e = getPrime(2047)
            d = pow(e, -1, (p-1)*(q-1))
    else:
        d = pow(e, -1, (p-1)*(q-1))
    return (p*q, p, q, e, d)

n = p*q
print(f'{n = }')

key = RSAgen()
k = randint(600, 1200)
f = factorial(k)

leak = (pow(key[3], 2) + (key[3]*key[4] - 1)*f)*getPrime(256) + k

# 2048 bit e is very expensive, i should use standard e for my encryption   

key = RSAgen(65537)
e = key[3]
flag = bytes_to_long(flag)
c = pow(flag, e, n)

print(f"{c = }")
print(f"{leak = }")


#OUTPUT
#
#n = 26155610563918771040451217453770153423175480849248932666067623213096628137347700281227651842637531066158966523562535269946270160966349550464316855975843702602386644310622115374093643617687763127399565005930283899166880048303714803385714487858740617133136915034968428269114907303042424391192431406494414712801428682398922655599872605973327217541188045983390427079210204358352343375551675052592229757120847888780576171954181304712725822439789885440973203535622584052397858824995170393109932313608251208103032787250637381098134254687242226624254464180882206386756799922789661143241398308165644172112918996116051241341767
#c = 14882143057207490168145609595794327950964467559973424621597752378687475531116051048471999976592360385753040756962986881197575420871063219354858309758384966841729075968439470757951580317772601028800980369844502945471937420415705013093369495725032356110007789188647453706470456907380267324946203780527015651994928850341098799680560649210763871810476662426271293840410794844793663532229448343601068354829550752842074478598115636890530640204633346276888013284576380941564885085920559055293159358576137659586044231684426664502650956119257574114940925398612801662412390652208379645262117964212231444035372237602987220161154
#leak = 8882329530176003989563469282320326448513961425520889104820115352134009331360402757127024139665879246460280903840841878434886334764358389863635520069842148223207565079555357126011768633841724238023402746185876779525887392481984149029421348288859961294980594601070755980946189936784537926893399566710815892754474482631518313221065280747677073806153015411511245208373763611976120763693741604815436190527484656588721635559583703292529849150438632820886160326184322723507482566078134710656764953471923255683042573911453728381364857973339477093454501755540396376196910045154990604723000628164844678783206034532184996212426411646863562670787117170937484057232253132378686191307517787281075273286073730517840320844224160937065166742670192503005084799125432651202276745876948826479983116284656814139188066381428020724692363565714860614527931752152240198254329317479816158596931824787225489069026346088037877441040453722896865574447079406031506283100005929709985031578939782011738018467829080816081913925121672327305968766974521281843700741425497908524015911173859409613820295440717780859694704848500536323185048069666385294578000406894438137681553061828379901393410655028227052289995544806138411605538810055799529381568985312754486907514057810886832822416112077637141046599291719695931641341477116694041607732362173173111829958139812135983269100274129925726662395368378059697391687349679786945510641238252220381519030943165126475181808810902040710261462429322977874350519175554159491968977598607860470919877896807912649830555310344788510811708640852621939517683512617800947347015328336403343549764926804605586325355602602157724502283094424228440314761426084409569002423419659272529716195776451657960565924304898320195699180560668631806178645741692749524883469846005409211271022431433039546590781549630715275308124729500303196140494010253387465310270348759187686632848767083559239773341844408450815683523679200221818741654323193797457218877776650125241324891467161777274139708214831833313936201971466603547791591622683172049635972772551806007816208466413199652425970868250229578051299718112290796388965170374760048006586491240415960299655674234758022536120132945656010849673271011148857409644260456852793444292102864629782613888832787049959589501287519423225832100567897316528973935415321329220397090613054817402449251249956025659833660199528249628136823951941068620183704359665779941064385612344970878816496323047753331967618070575102035154652470553061929831610193694052912228006377979477318327954292917783836426814224401489211262556447908499035071972531345812915421543036881828636718727357962701875285833936517812391121587399727281240931927431811181444977909594218984279921315492877394195428208756441893687385105650326859023900280137352737660777503064484456016697716191624303099683835521939233782390584505763849676573364198388306561033652480971048175488758111144736636640190185417713883213429725379415164862080052393396741667399031632758281193771891210430178563364662790052209648349668663621672614807647401120518076403133998551484399204398325200361951412241887720441234483010617920388630542945062451586033688057992061925968617174491390233664273716567854279453909892176120950383253842037120054072618389794275273311333932588139102552015371447182882116160259277516530183031644054520783191752410514938160605548110059282703060409667276475969749797140136872904654013231613962248971564712815341527356396922068564215026284215874684201258558000033165916019163319759952566031082383620943938948623145286816988139057606627616639594815749554968862963450819772941547102531289115954195402127419754744687573822011699197232836491588776322734503766502102575418226503487579619923510951731702344792411606628965837547432575532404303417689912716247856960760491417279481456633424179644033150732614552508566990237704498608189201159580503580410535170284429946552129635519661513317741471932078145289068540132823

梳理一下加密流程，题目首先用了默认参数 e=None 生成了一组 RSA 密钥，并基于此密钥泄露了一个信息 leak 。泄漏 leak 之后，用 e=65537 生成了另一组公私钥，并且用另一组公私钥加密明文后，给出密文。

注意到两次 RSAgen() 过程中，n、p、q三个量是不变的。因此解题的思路就是：由第一组 e、d 泄漏的信息 leak，获取 n 的分解，从而解密第二组密文。

那么 leak 究竟泄露了什么？先把表达式写出来：

$$leak = (e_1^2+(e_1d_1-1)k!)a+k$$

其中，

• a是一个256比特的随机素数，未给出
• k是一个(600,1200)之间的整数，未给出

整个 leak 式子里就没有一个参数是知道的，那怎么办？首先就会观察到 k 可能的范围比较小，只有 600 种可能，因此突破口应该在于先找到一种合适的爆破思路，求解出 k。为了达到求解 k 的目的，先把 leak 的表达式拆成更容易理解的形式：

$$leak = ae_1^2+a(e_1d_1-1)k!+k$$

我们在(600,1200)之间取 i 进行爆破，那么当 i 取(600,k) 之间的数时，下面的等式成立：

$$ae_1^2 = leak -i \quad (mod\;i!)$$

这是因为，由于 i < k，所以有 $ i! \mid k!$

而当取的 i 大于 k 时， $ i! \nmid k!$ ，因此模 $ i!$ 无法模掉leak中 $a(e_1d_1-1)(k!)$ 这一部分。这也就是说，如果 $ leak -i \quad (mod\;i!) $ 的计算值的数量级发生了显著变化，就说明我们取得了正确的 k。并且在爆破过程中，我们早就拥有了正确的 $ ae_1^2$

求得了 k 之后，就要想办法求出剩下几个参数，而由于拥有 $ ae_1^2$ ，所以容易想到继续从 a 下手。此时，我们再把 leak 的表达式写成另一个容易理解的形式：

$$leak = a(e_1d_1-1)k!+(ae_1^2+k)$$

为什么说他更容易理解？因为这就写成了一个标准的带余除法形式：

$$a=kb+c\quad,\quad c<b$$

而对这个带余除法，显然有：

$$a \div b = k$$

而放在 leak 组成的带余除法中，由于 $k!$ 的数量级显然大于 $ (ae_1^2+k)$ ，因此就有：

$$leak \div (k!) = a(e_1d_1-1)$$

将得到的值与 $ae_1^2$ 求gcd即可得到 a ，接下来就能恢复 $e_1，d_1$，然后就转化成已知 e，d 分解 n 的问题了。分解出 n 后就可以顺利求解密文。

当然，也可以由：

$$leak - k - ae_1^2 = a(e_1d_1-1)k!$$

用这个与 $ae_1^2$ 求gcd也可得到 a，同时其实也不需要分解n，我们直接求65537关于kphin的模逆当作解密指数即可。

不过其实最简单的方法并不是上面这几种，其实可以直接将leak除以600!就可以得到kphin了，原理也很简单，有兴趣的师傅可以自己想想。

exp.py：

from Crypto.Util.number import *
from sympy import factorial
from gmpy2 import iroot

n = 26155610563918771040451217453770153423175480849248932666067623213096628137347700281227651842637531066158966523562535269946270160966349550464316855975843702602386644310622115374093643617687763127399565005930283899166880048303714803385714487858740617133136915034968428269114907303042424391192431406494414712801428682398922655599872605973327217541188045983390427079210204358352343375551675052592229757120847888780576171954181304712725822439789885440973203535622584052397858824995170393109932313608251208103032787250637381098134254687242226624254464180882206386756799922789661143241398308165644172112918996116051241341767
c = 14882143057207490168145609595794327950964467559973424621597752378687475531116051048471999976592360385753040756962986881197575420871063219354858309758384966841729075968439470757951580317772601028800980369844502945471937420415705013093369495725032356110007789188647453706470456907380267324946203780527015651994928850341098799680560649210763871810476662426271293840410794844793663532229448343601068354829550752842074478598115636890530640204633346276888013284576380941564885085920559055293159358576137659586044231684426664502650956119257574114940925398612801662412390652208379645262117964212231444035372237602987220161154
leak = 8882329530176003989563469282320326448513961425520889104820115352134009331360402757127024139665879246460280903840841878434886334764358389863635520069842148223207565079555357126011768633841724238023402746185876779525887392481984149029421348288859961294980594601070755980946189936784537926893399566710815892754474482631518313221065280747677073806153015411511245208373763611976120763693741604815436190527484656588721635559583703292529849150438632820886160326184322723507482566078134710656764953471923255683042573911453728381364857973339477093454501755540396376196910045154990604723000628164844678783206034532184996212426411646863562670787117170937484057232253132378686191307517787281075273286073730517840320844224160937065166742670192503005084799125432651202276745876948826479983116284656814139188066381428020724692363565714860614527931752152240198254329317479816158596931824787225489069026346088037877441040453722896865574447079406031506283100005929709985031578939782011738018467829080816081913925121672327305968766974521281843700741425497908524015911173859409613820295440717780859694704848500536323185048069666385294578000406894438137681553061828379901393410655028227052289995544806138411605538810055799529381568985312754486907514057810886832822416112077637141046599291719695931641341477116694041607732362173173111829958139812135983269100274129925726662395368378059697391687349679786945510641238252220381519030943165126475181808810902040710261462429322977874350519175554159491968977598607860470919877896807912649830555310344788510811708640852621939517683512617800947347015328336403343549764926804605586325355602602157724502283094424228440314761426084409569002423419659272529716195776451657960565924304898320195699180560668631806178645741692749524883469846005409211271022431433039546590781549630715275308124729500303196140494010253387465310270348759187686632848767083559239773341844408450815683523679200221818741654323193797457218877776650125241324891467161777274139708214831833313936201971466603547791591622683172049635972772551806007816208466413199652425970868250229578051299718112290796388965170374760048006586491240415960299655674234758022536120132945656010849673271011148857409644260456852793444292102864629782613888832787049959589501287519423225832100567897316528973935415321329220397090613054817402449251249956025659833660199528249628136823951941068620183704359665779941064385612344970878816496323047753331967618070575102035154652470553061929831610193694052912228006377979477318327954292917783836426814224401489211262556447908499035071972531345812915421543036881828636718727357962701875285833936517812391121587399727281240931927431811181444977909594218984279921315492877394195428208756441893687385105650326859023900280137352737660777503064484456016697716191624303099683835521939233782390584505763849676573364198388306561033652480971048175488758111144736636640190185417713883213429725379415164862080052393396741667399031632758281193771891210430178563364662790052209648349668663621672614807647401120518076403133998551484399204398325200361951412241887720441234483010617920388630542945062451586033688057992061925968617174491390233664273716567854279453909892176120950383253842037120054072618389794275273311333932588139102552015371447182882116160259277516530183031644054520783191752410514938160605548110059282703060409667276475969749797140136872904654013231613962248971564712815341527356396922068564215026284215874684201258558000033165916019163319759952566031082383620943938948623145286816988139057606627616639594815749554968862963450819772941547102531289115954195402127419754744687573822011699197232836491588776322734503766502102575418226503487579619923510951731702344792411606628965837547432575532404303417689912716247856960760491417279481456633424179644033150732614552508566990237704498608189201159580503580410535170284429946552129635519661513317741471932078145289068540132823

#确定 k = 1000
'''
for k in range(600,1200):
    t = factorial(k)
    ae2 = int((leak-k) % t)
    if(len(bin(ae2)) != 4351):
        print(k-1)
        break
'''

k = 1000
ae2 = int((leak-k) % factorial(k))
temp = leak // factorial(k)
a = GCD(ae2,temp)

e = iroot(ae2//a,2)[0]
d = (((leak - k)//a - e**2) // factorial(k) + 1) // e


#已知e，d分解n
t = e*d - 1
s = 0

while t % 2 == 0:
    s += 1
    t //= 2

for i in range(1, s):
    c1 = pow(2, int(pow(2, i-1, n)*t), n)
    c2 = pow(2, int(pow(2, i, n)*t), n)
    if c1 != 1 and c1 != (-1 % n) and c2 == 1:
        p = GCD(c1 - 1, n)
        q = n // p
        break

phi = (p-1)*(q-1)
d = inverse(65537,phi)
print(long_to_bytes(pow(c,d,n)))

flag:

flag{gcd_is_always_useful}

hardrsa

感谢几位师傅对我提供的帮助，通过这一道题收获了很多。

题目来源：江苏省数据安全竞赛 2023

题目：

from Crypto.Util.number import *
from random import randint
from secret import message

p, q = [getPrime(1024) for _ in range(2)]
n = p * q


def pad(msg: bytes) -> bytes:
    return msg + long_to_bytes(len(msg) & 0xff) * (2048 // 8 - len(msg) - 1)


def f(x: int, poly: list[int]) -> int:
    return sum([
        poly[i] * pow(x, i, n) for i in range(len(poly))
    ]) % n


def commit(m: int, d: int, key: int, poly: list[int]) -> (int, int):
    sig = pow(m, d, n)
    c1 = (sig + pow(key, 8, n) + pow(key, 4, n) + pow(key, 2, n)) % n
    c2 = f(key, poly)
    return c1, c2


def reveal(comm: (int, int), e: int, key: int, poly: list[int]) -> int:
    c1, c2 = comm
    assert f(key, poly) == c2
    sig = (c1 - pow(key, 8, n) - pow(key, 4, n) - pow(key, 2, n)) % n
    return pow(sig, e, n)


def part1(msg):
    e = 233
    assert GCD(e, (p - 1) * (q - 1)) == 1

    m = bytes_to_long(pad(msg))
    c = pow(m, e, n)
    print(f"# Part1: RSA-Encrypted Ciphertext\n"
          f"{e = }\n"
          f"{n = }\n"
          f"{c = }\n")


def part2(msg):
    e = getPrime(256)
    assert GCD(e, (p - 1) * (q - 1)) == 1

    d = inverse(e, (p - 1) * (q - 1))
    key = getPrime(1024)
    poly = [randint(n // 2, n) for _ in range(8)]

    m = bytes_to_long(msg)
    comm = commit(m, d, key, poly)
    print(f"# Part2: RSA-Committed Promise\n"
          f"{e = }\n"
          f"{n = }\n"
          f"{poly = }\n"
          f"{comm = }\n")


part1(message)
part2(message)

数据：

# Part1: RSA-Encrypted Ciphertext
e = 233
n = 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168442639629844443754737406734109480041155382192976640499144347256893867447543190494469466088332396851821283556702874066317163371254358756837283841870127393406798300254660201670728912096447184875821681550977470988174485488514169553325962974156396460297399345856735492168813016282687198473612371220123462499438299
c = 4236463649246394372490570028773321531426122440354351428997745409269923078428264643984899276198044684405861411922920531424639487584475747440112668094733950281377813868988540407013967573584191516922420060508458881142111648007775541541206593622564564631875373635260315932740995440619035591722675173125322220642392862827996987221780888705796026865917969313975598350208578877195524822778355327253625950282635041414028859491576352297298051077024341409125083650148374909480761558443601847884116325029903499801566422663448734010004472905405209374692154735955178855634936508017264189084568424915164265136679303107745093554391

# Part2: RSA-Committed Promise
e = 99181398864848350371016820825262886005052515653150198897546275436659368873943
n = 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168442639629844443754737406734109480041155382192976640499144347256893867447543190494469466088332396851821283556702874066317163371254358756837283841870127393406798300254660201670728912096447184875821681550977470988174485488514169553325962974156396460297399345856735492168813016282687198473612371220123462499438299
poly = [11693140800527031176333218506340138430240732192854115958431704393516665671354696442539228569575338743555295185742126489158430815263152939757778849261704565332700814864041988371030487621611557506812653488873444536543143499111306076278080422306914610758456202844384883419669780999835836102076447921204517046598938140064244383099665415296806730515287813702062130475281955202867695799707516205462251852912274330831232375362037653669046715539164625549785400699583991291522758317569231805551847554593188947041531361947659444681456741424693383958548943092649257246992511287359572983628972516677506780721131000304618999959240, 8649833849514355009128561581797540267452805179286553003531347469534976088903045945255322948772127884435044654450320045837146400545547035413423698519877318250595578140049443137749594587635124784776640002144869420735353810166877391696732603701567388813523929688499591774843294322221335666734637085035509293762539158494372418206937167893545676403532672666734540153869114591107560124251452526082108870638702356111887843199439729119638581693415233654435010304861838471514755642714031294943492873471199466178392719343340089957082809543276507257853855309815913146064538017999492250838671852901021723088900839652630087246141, 10438652195883831412435505413668253747222376993835057512571018586886172468948369796145782100970559858131410652399919261454018181151110711244715955202406007064700539815605400586293839962095578425689125884220411946405356203770630361655071021743875660757465221991116870667245627142015074048387044977823496726850652712591020608153928488470683315016742274925734216097962308837642472645606961264797331661105479206824511239562468503777960135923781994521205671697654968415294210654160582131094288074290198995839634141037654146239631046959485219534841518635072303135929794463631818179287771643492272214514760725403082404954077, 6299797573437298253264628040275849948907328879976403409079992234253896659195171862234483958852183317706433020249500667696777456584466888790659866599735145200280792478137705987287433143791976037155630359309176772317673958151640355448435973240969550879845354695745860375206302178000370970096709147495071090575765018242388707621300316998885753178573503094652529005706228511805022756376570371219075764243214260191102332714962783026379460713478294288812651004299398765770489801066856526467071118037951998756053462219010773133084404686760087508480150118199064293552990969966284945601004840346771690026959557356854894243142, 5983820380221904115440358005660480412823344425839483679019674090060688612423646544886814493835896810583739677554610487986153726859924027361158809156736196645803178995096319914672180274662462472664438431485027075620562484665653780178408855146763748596173882017604170478152671447791422988271913561725716787175269110153429606771827175728957339646431861352878283239969487426243742285835160804730331718691578524218241320715981666141098574100230167376734068738383108974392515927882240711793555447542821660698352614753928088082506778754171275154966436158307349089886252792151153113074617130452582559608047038630881997177039, 8645965524213201512342533940160639034615963495013466945596780273953897799745861434427630308300521898525016597999525817531163934211570038600077012713829688089842641388807750705270930654414851381582193662566863633088157205775657627097344504719056435375579887356258011212827309329133255360061251120340523712584772477488197868145839887008419529501177350232970834479788126170916738231188284692568626261063508315725550701926154671018704631776622326225119240790109750932269682399309418540027656506064831086635915646225839228991353015865676434534451013307891476809505965003364463706502868834742525815830814492484165778659587, 8166140295702705700395932322789090244824428366114951893911644134774959163562810185361333621863609139128772766004899397707351421904667080061768039818505350911041979508989714659275009135159974367690971928143915291585444591471643654394998052988522554930699706249604920467869677602144648519540475773077094544621879816388166112425971849485960827238183936548150306573608653859245355573339051077997289111414512279487536882904628267661230723738630443448632824642827281459881525198877210749057510831197018233179399730814958129875964180438394548470264377690208812256581197996134290095012248199229098363134875105995583143456168, 7886150187486607733887128114395381216280632497989629748521639744973030901762862876238518693357844959238094796545062411041606956447558438012468158689781248611833577676585338278147089873855656470245899229225464314602079901728048645256171396517696354087510327916826422932730522688556064550363916637523771395744826680925934243060230500845916621676929436788265600433752247152028066595489876401981088262668869028915433063354318691392248675089923289405167438193023160255479805758334680481491101176946904940583407560870907209114968515837974428072735042388612237381596523708101955987248270337329833158967647159556534902013893]
comm = (9026467857515594907139807322545643350722792398333959966810869076838279879742354562376888810480050803270079309674260152449220680190968011586239815898932783620194546687257066163982003360839627375768650529178687560019057911732404297565185448089372452182330617296119274984700102752558018626083227105916899465707167123429214371669495986051607781832508462509001195586237627932854012820647829936908023798167666909963391041754465967388417732502397794744032988693994711566201865393143230144593516438201799281519569197057042946810458619730130134659584342739598850633062984339223231306255977280483664354044871774659593149033209, 5887596182170973664955287957462647377802905573127495764035296813527168813405478740764981971139443147816701320451276508908764320611456709375484716332728626903126128547418401252520849124559671921918551772662755206548324883488334170067283423978156495671895979491847768306791576421069205614999618915580196468910801165217204877300901375945537974466575619851388784172797986385425693707736028155214422059085724499916277733254676564775837649200298391496783417808690237433893136207762575843230800924871422368332950754364751040187058272878178869385694948947692002564148365094951441755961075673329949416511183562799400968841515)

简单梳理一下题目的已知信息，可以表达成以下两个式子：

$$(pad(m))^{233} \equiv c\quad(mod\;n) \tag{1}$$ $$m^{d_2}+key^8+key^4+key^2 \equiv commit[0] \quad (mod\;n) \tag{2}$$

然后还有：

$$\sum_{i=0}^7poly[i]*key^i \equiv commit[1] \quad (mod\;n) \tag{3}$$

首先，对于m的pad操作，只有少于256种可能，因此可以用爆破操作求解。

一个比较朴素的思路是：想办法求解出(2)中的d2，然后求(1)(2)两式的Gröbner基，从而直接解出key与m。但是从已知的信息好像并不能简单有效地得出关于d2的信息，因此这个方法作罢。

但是消元是势在必行的，观察到三个式子均在模n环上，因此主要就要想如何消元。首先，根据(2)(3)两式，可以用resultant消去key，转化成一个关于m^d的单变量多项式，然后由(1)(2)两式求gcd就能得到m。

但是，还是老问题，没有d2怎么求gcd呢？所以无论怎么样，这个d2是绕不开的一个问题，而我们能利用的关于d2信息就只有一条：

$$e_2*d_2 \equiv 1 \quad (mod\;\phi(n))$$

关键就在于怎么利用，因为我们现在有的是一个关于m^d2的模n下的多项式，而并不是一个数字，因此没有办法简单的直接求e2次幂。然后在几位师傅的帮助下，学习了一下伴随矩阵的使用：在sage中，如果拥有一个monic的多项式f(x)，那么可以用companion_matrix函数将其转化为一个伴随矩阵F，并且矩阵F的特征多项式就是f(x)。那你可以想到，在这题目里,我们直接把m^d2看作变量x，那么f(x)有根m^d2，而m^d2既是f(x)的根，也是F的特征值。

而矩阵是可以求幂次的，F^e2次方的特征值就是m^(d2*e2)，那么在模n的环下，该特征值就是m，此时我们再用charpoly函数求F^e2的特征多项式，就得到了一个根为m的多项式了。

那么接下来的工作就很容易，把该多项式和(1)式求解gcd，就能得到(x-m)，就能得到明文m了。

exp：

from Crypto.Util.number import *
from tqdm import *

def GCD(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

# Part1: RSA-Encrypted Ciphertext
e1 = 233
n = 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168442639629844443754737406734109480041155382192976640499144347256893867447543190494469466088332396851821283556702874066317163371254358756837283841870127393406798300254660201670728912096447184875821681550977470988174485488514169553325962974156396460297399345856735492168813016282687198473612371220123462499438299
c1 = 4236463649246394372490570028773321531426122440354351428997745409269923078428264643984899276198044684405861411922920531424639487584475747440112668094733950281377813868988540407013967573584191516922420060508458881142111648007775541541206593622564564631875373635260315932740995440619035591722675173125322220642392862827996987221780888705796026865917969313975598350208578877195524822778355327253625950282635041414028859491576352297298051077024341409125083650148374909480761558443601847884116325029903499801566422663448734010004472905405209374692154735955178855634936508017264189084568424915164265136679303107745093554391

# Part2: RSA-Committed Promise
e2 = 99181398864848350371016820825262886005052515653150198897546275436659368873943
n = 11804593083540766953191768473584891632857464298610295673456410319093405751966708262984066641796004658380825990723088997287209884308749055923966759203552497405777188930982989535372734594928432767182748217929177897158889489317608554405915470112027996617864702664597137007278287666634774284031478676422259138168442639629844443754737406734109480041155382192976640499144347256893867447543190494469466088332396851821283556702874066317163371254358756837283841870127393406798300254660201670728912096447184875821681550977470988174485488514169553325962974156396460297399345856735492168813016282687198473612371220123462499438299
poly = [11693140800527031176333218506340138430240732192854115958431704393516665671354696442539228569575338743555295185742126489158430815263152939757778849261704565332700814864041988371030487621611557506812653488873444536543143499111306076278080422306914610758456202844384883419669780999835836102076447921204517046598938140064244383099665415296806730515287813702062130475281955202867695799707516205462251852912274330831232375362037653669046715539164625549785400699583991291522758317569231805551847554593188947041531361947659444681456741424693383958548943092649257246992511287359572983628972516677506780721131000304618999959240, 8649833849514355009128561581797540267452805179286553003531347469534976088903045945255322948772127884435044654450320045837146400545547035413423698519877318250595578140049443137749594587635124784776640002144869420735353810166877391696732603701567388813523929688499591774843294322221335666734637085035509293762539158494372418206937167893545676403532672666734540153869114591107560124251452526082108870638702356111887843199439729119638581693415233654435010304861838471514755642714031294943492873471199466178392719343340089957082809543276507257853855309815913146064538017999492250838671852901021723088900839652630087246141, 10438652195883831412435505413668253747222376993835057512571018586886172468948369796145782100970559858131410652399919261454018181151110711244715955202406007064700539815605400586293839962095578425689125884220411946405356203770630361655071021743875660757465221991116870667245627142015074048387044977823496726850652712591020608153928488470683315016742274925734216097962308837642472645606961264797331661105479206824511239562468503777960135923781994521205671697654968415294210654160582131094288074290198995839634141037654146239631046959485219534841518635072303135929794463631818179287771643492272214514760725403082404954077, 6299797573437298253264628040275849948907328879976403409079992234253896659195171862234483958852183317706433020249500667696777456584466888790659866599735145200280792478137705987287433143791976037155630359309176772317673958151640355448435973240969550879845354695745860375206302178000370970096709147495071090575765018242388707621300316998885753178573503094652529005706228511805022756376570371219075764243214260191102332714962783026379460713478294288812651004299398765770489801066856526467071118037951998756053462219010773133084404686760087508480150118199064293552990969966284945601004840346771690026959557356854894243142, 5983820380221904115440358005660480412823344425839483679019674090060688612423646544886814493835896810583739677554610487986153726859924027361158809156736196645803178995096319914672180274662462472664438431485027075620562484665653780178408855146763748596173882017604170478152671447791422988271913561725716787175269110153429606771827175728957339646431861352878283239969487426243742285835160804730331718691578524218241320715981666141098574100230167376734068738383108974392515927882240711793555447542821660698352614753928088082506778754171275154966436158307349089886252792151153113074617130452582559608047038630881997177039, 8645965524213201512342533940160639034615963495013466945596780273953897799745861434427630308300521898525016597999525817531163934211570038600077012713829688089842641388807750705270930654414851381582193662566863633088157205775657627097344504719056435375579887356258011212827309329133255360061251120340523712584772477488197868145839887008419529501177350232970834479788126170916738231188284692568626261063508315725550701926154671018704631776622326225119240790109750932269682399309418540027656506064831086635915646225839228991353015865676434534451013307891476809505965003364463706502868834742525815830814492484165778659587, 8166140295702705700395932322789090244824428366114951893911644134774959163562810185361333621863609139128772766004899397707351421904667080061768039818505350911041979508989714659275009135159974367690971928143915291585444591471643654394998052988522554930699706249604920467869677602144648519540475773077094544621879816388166112425971849485960827238183936548150306573608653859245355573339051077997289111414512279487536882904628267661230723738630443448632824642827281459881525198877210749057510831197018233179399730814958129875964180438394548470264377690208812256581197996134290095012248199229098363134875105995583143456168, 7886150187486607733887128114395381216280632497989629748521639744973030901762862876238518693357844959238094796545062411041606956447558438012468158689781248611833577676585338278147089873855656470245899229225464314602079901728048645256171396517696354087510327916826422932730522688556064550363916637523771395744826680925934243060230500845916621676929436788265600433752247152028066595489876401981088262668869028915433063354318691392248675089923289405167438193023160255479805758334680481491101176946904940583407560870907209114968515837974428072735042388612237381596523708101955987248270337329833158967647159556534902013893]
comm = (9026467857515594907139807322545643350722792398333959966810869076838279879742354562376888810480050803270079309674260152449220680190968011586239815898932783620194546687257066163982003360839627375768650529178687560019057911732404297565185448089372452182330617296119274984700102752558018626083227105916899465707167123429214371669495986051607781832508462509001195586237627932854012820647829936908023798167666909963391041754465967388417732502397794744032988693994711566201865393143230144593516438201799281519569197057042946810458619730130134659584342739598850633062984339223231306255977280483664354044871774659593149033209, 5887596182170973664955287957462647377802905573127495764035296813527168813405478740764981971139443147816701320451276508908764320611456709375484716332728626903126128547418401252520849124559671921918551772662755206548324883488334170067283423978156495671895979491847768306791576421069205614999618915580196468910801165217204877300901375945537974466575619851388784172797986385425693707736028155214422059085724499916277733254676564775837649200298391496783417808690237433893136207762575843230800924871422368332950754364751040187058272878178869385694948947692002564148365094951441755961075673329949416511183562799400968841515)

P.<x, y> = PolynomialRing(Zmod(n))
x, y = P.gens()
f = sum([poly[i] * x^i for i in range(len(poly))]) - comm[1]
g = x^2 + x^4 + x^8 + y - comm[0]
h = f.sylvester_matrix(g, x).det().univariate_polynomial().monic()
h_coefficients = h.coefficients()
Hd2 = companion_matrix(h_coefficients)
H = Hd2^e2
final = H.charpoly()

for i in trange(200,255):
    length = (2048 // 8 - i - 1)
    f1 = ((x * 256^length + bytes_to_long(long_to_bytes(i) * length))^e1 - c1).univariate_polynomial()
    mm = GCD(final, f1)
    if mm not in ZZ:
        m = int(-mm.monic()[0])
        print(long_to_bytes(m))
        break 
        
#flag{07ba38d7a9affba269a613da6d99a7ff}

其实很多细节我懂的并不透彻，包括各种sage函数的使用，需要多多学习了。

easycrt

题目来源：广东强网杯 2021 个人决赛

题目：

from Crypto.Util.number import getPrime, long_to_bytes
from hashlib import sha1
from random import randint
from libnum import gcd,invmod

p = getPrime(1024)
q = getPrime(1024)
e = 65537
n = p * q
print("n",n)

flag = "flag{" + sha1(long_to_bytes(q)).hexdigest() + "}"

r1 = getPrime(18)
r2 = getPrime(18)
r3 = getPrime(18)
pad = getPrime(18)

d = invmod(e, (p - 1) * (q - 1))
iq = invmod(q*r2,p*r1)
while True:
    m = randint(1, n-1)
    if m % 7 == 6:
        break
print("m",m)

dp = d % (p - 1)
dq = d % (q - 1)
Sp = pow(m + pad, dp, p * r1)
S1 = pow(m, dp % (r1 - 1), r1)
Sq = pow(m, dq, q * r2)
S2 = pow(m, dq % (r2 - 1), r2)
S = Sq + (q * r2) * (iq * (Sp - Sq) % (p * r1))
c1 = (S - S1 + 1) % r1
c2 = (S - S2 + 1) % r2
y = (r3 * c1 + (2**18 - r3) * c2) // 2**18

sig = pow(S, y, n)
print("sig",sig)

enc.txt：

n = 15607652517362093645325317106793899509049466286289406123011562305732952834110025278707770877710387511133525615547749067167022163144871246026729711471170089144091842130735468670759804996736436114870014417745362424832770744726487119356277902631543992047543702092569479132696642375458263796132196310174835558347436349470015821172039278202738123606756327018331739326913099131587338291813228001362150294270185257672772964543656446660394264977076202429526267205338019235884610484301330863633308326891900441046466311908648695612469874605299959023321039907455357375512719105021644958752946075704546448277530349374124925552999
sig = 10529383690563626041913943912548148193819837348659016705087283692659198195639818226546674852244543732342882844923086010181839287638468160452876441986475739097061958400475370429389938633409459705321551413680888540996412276373484717577799632143058273282184901897121998551083953391761808538319274041663569149845813852812460215349964039044454715161276326154052689106577168080671792457943959674009099696029742287088741014864890643610109608810518217249714342499311259749863368245284452473571531519289299316677019474225948437231068806941146456877792741550185160112281625929417877458463803652501300748844407304985956111227832
m = 9221389214846452074650198574187733045048782681343858755771769264298997816865330014844850679483076796014601281496675756079954850050104766792742802672859212829451854911463986483312887597249074612447791144976425525708325445215521780736722325242438897188724275411273730095000042905697065812817717123169837477587937321878898881598591204738992809905166463654289137499334014194236642634848110827034366887478823691109550776819273014443942468214983033609722152912395399288856874022406788892463061718806118721777027702827433908594054906653446257493698282318911042247500866249480426304090761922444970044089807749920717682404402

题目的信息很多，完成这一题的关键就是要注意到其中真正有用的几个信息，如下：

$$S_q = m^{dq} \quad (mod\; r_2q)$$ $$S = S_q + r_2q*(iq*(S_p-S_q) \;mod \;(r_1p))$$ $$sig = S^{y} \quad (mod\;n)$$

这几个信息有用在哪里呢？首先，S其实就是对Sp、Sq的中国剩余定理组合，呼应题目crt。不过没看出来也不重要，我们把这几个式子均放在模q下分析：

$$S_q \equiv m^{dq} \quad (mod\;q)$$ $$S \equiv S_q \quad (mod\;q)$$ $$sig \equiv S^y \quad(mod\;q)$$

首先有：

$$S_q^e \equiv m \quad(mod\;q)$$

因此：

$$sig^e \equiv m^y \quad (mod\;q)$$

而注意到y由如下方式产生：

y = (r3 * c1 + (2**18 - r3) * c2) // 2**18

其中的几个参数均较小，因此y的数量级大约也就在2^18以内，因此我们可以爆破y，从而有：

$$sig^e - m^y = kq$$

求解该式与n的gcd就能得到q，进而恢复flag。

exp：

from Crypto.Util.number import *
from hashlib import *
from tqdm import *

n = 15607652517362093645325317106793899509049466286289406123011562305732952834110025278707770877710387511133525615547749067167022163144871246026729711471170089144091842130735468670759804996736436114870014417745362424832770744726487119356277902631543992047543702092569479132696642375458263796132196310174835558347436349470015821172039278202738123606756327018331739326913099131587338291813228001362150294270185257672772964543656446660394264977076202429526267205338019235884610484301330863633308326891900441046466311908648695612469874605299959023321039907455357375512719105021644958752946075704546448277530349374124925552999
sig = 10529383690563626041913943912548148193819837348659016705087283692659198195639818226546674852244543732342882844923086010181839287638468160452876441986475739097061958400475370429389938633409459705321551413680888540996412276373484717577799632143058273282184901897121998551083953391761808538319274041663569149845813852812460215349964039044454715161276326154052689106577168080671792457943959674009099696029742287088741014864890643610109608810518217249714342499311259749863368245284452473571531519289299316677019474225948437231068806941146456877792741550185160112281625929417877458463803652501300748844407304985956111227832
m = 9221389214846452074650198574187733045048782681343858755771769264298997816865330014844850679483076796014601281496675756079954850050104766792742802672859212829451854911463986483312887597249074612447791144976425525708325445215521780736722325242438897188724275411273730095000042905697065812817717123169837477587937321878898881598591204738992809905166463654289137499334014194236642634848110827034366887478823691109550776819273014443942468214983033609722152912395399288856874022406788892463061718806118721777027702827433908594054906653446257493698282318911042247500866249480426304090761922444970044089807749920717682404402

c1 = pow(sig,65537,n)
for i in trange(2**18):
    if(GCD(c1-pow(m,i,n),n) != 1):
        q = GCD(c1-pow(m,i,n),n)
        print("NSSCTF{" + sha1(long_to_bytes(q)).hexdigest() + "}")
        break

#NSSCTF{947d9f457b224fb7779b84158ea72861b4e72af3}

BABY RSA

题目来源：HITCTF 2021

题目：

#!/usr/bin/env python
# coding=utf-8
from Crypto.Util.number import *
from gmpy2 import *
from binascii import *


size = 4096
next_state = getRandomInteger(size // 2)


def keygen(size):
    q = getPrime(size)
    k = 2
    while True:
        p = q * k + 1
        if isPrime(p):
            break
        k += 1
    g = 2
    while True:
        if pow(g, q, p) == 1:
            break
        g += 1
    A = getRandomInteger(size) % q
    B = getRandomInteger(size) % q
    d = getRandomInteger(size) % q
    h = pow(g, d, p)
    return (g, h, A, B, p, q)


def rand(A, B, M):
    global next_state
    next_state, ret = (B * next_state + A) % M, next_state
    return ret


def enc(pubkey, m):
    g, h, A, B, p, q = pubkey
    assert 0 < m <= p
    r = rand(A, B, q)
    e = 0xfaab
    c1 = (pow(m,e,p) * pow(h, r, p)) % p
    r = rand(A, B, q)
    c2 = (m * pow(h, r, p)) % p
    return (c1, c2)


pubkey= keygen(size)
print(pubkey)

secret = bytes_to_long("HITCTF2021(xxxxxxxxxxxxxxxxxxx)")
c1,c2= enc(pubkey, secret)

print(c1, c2)

#pk = (52, 
#47782489586021221729935382562238217213800826152327617948974334325027793433971508995399461776417812670604694882926777607105164020070178881963632306169611641854448509182837621758791538269408388860349616761041456174827996858614494726877767399938809515247000929894281600963992080920650256329287847887064428158469516438206831721224607859023980203694210651902538562842945949404149023836218548894116477022953606370852246884414011363477543284815671096832245521762246149180260936985618856296642080245029837974725521906177900378634071571992373478242159162403228753252168867425697897820696887070051128304178291193132322824455442092893684929701869625045112839344191126228806117685809636908190595562295591835629941512331963039016185366202513504464795106031092314892430859175307526232632986110464780357940552264674214665391043812843917461961230679207586174459563057178720743465356337218948534837994061644332424634750340190113117958830588820626581860957277456320434445207368613679418733984291985618038226928033006640791987978775285182325347153201516936002001839296455263977479446850434913069389565277028444638437387429263495729274142916464752814676819557878779855996225208596159171827854923873570163767937947956753277454486339143489103105750331110111L,
#433229619560374735022060612660487139311547277564407316269466855779330930804160973325703376198605206390912154427123102710354958367692760474727012214464298979098489170777185729836132968187705068687678796437447631516334893543456227545790012358063578349956636488453355182971532300478038635153420232589545761194907476691636706445176390661463152150169542241304542401678253873515488446133330974312465916350895130227137954122794991542025930903127027608739905609108321738139103065645651901833223353774916656293079960486497159730921219805951217073283062070931854507016733789164315751827862830668829125950364981217520865411859759718244136420504507997449935455788230060974032741364271601426191469331266168231203426316280988734802654397014768828735251891167507794161264913387252048434549271931367148180980260205843989153008044839641263127846901551223167574691783927938948745126094512037792728067785201012834153473172824948188352810070916677679450209134179624791196123158336411804834221293611075447043002901607162001357780058394706516204775756666576041740010288970758149528406172022049389998133360726123682741312251431519423867620962951022993364287241463507027520966721930799696555390707280246584903566049326608205785466271642132178515338520410658L, 
#594494499417894774789048451572687632660208181953899084791149805130704950465573064455173172705283156011806901684972459390817538594318847879599780068410149543731305374894040638491310362570467887919519584736646557258917947483658649575357363123407313011773027073062592473100264464401987309633458687673513776139455296286685115396610808047870099635374955339289799615102534094497730932884838674370338192153202045642565170696704452991192684466848026383861073123033948004049599266417667125680356386669226827901570782628388996520826906941293858994180130505009152517646592286697346622724843482147801718703310671546709185342317509441259927498881276856470161174444209513355803640646947368551446328198695259259829546707119878154837158880677882305548928799964929213106969848547576414765380870575558771867763848114411251654245747231121164090765647221739709450477815688276801154266722035408374135871417564206013020997849375553619152730479571927135850379285559873197371293312934173379820835252091990919727655797413411368987930118553258247264348519581466374312010472449698571319621067244494880512957538208007914329691196084901181642263713183616896210154681618376310287185315262021479758282631576946335858068664109425856174388362174761355148787245515144L, 
#261181509476485410165375351178418657075805043256124045823778754055035546150122155335065215645750231604267318872693494310557376958843829685914382636208107544361140482291909865660810395856913449414106045946602124226832733980696161639105193768954092281635195760991693212657816181524313660831938528737461195472275606167593968953647934279724693129491600232382201769523725243272086370087058597321533767924008747705935388941121530345216164771817150616453601212026925759807092457510188966636612860912597984231762129535299227711879953931847880037605415987083573556274570400085013894504645789376654166259691075373526751505971657856429187752015665407876751018316490729668209646098952144838144486106489379202197360745365239628186669447122272538227142855706247593556669905666428363734481409983627496127639634726855140379146669911302677456457202808949896992958886949162850488164457334796828240069980922051762068458877051063958308363343196940785994299643315504146607392461323382470475501119070077564995866998018505817611171892860136485534016608294708527673407517876647349723758712907513973353401204912431800080247493896815299218218930415151745986776831977527196435124521552249406640177674130330651411672455343809240941664288436809369136070604763156723L, 
#781980567294866497501123805923409152921571985796778580310714832500106425599168129745704238460330034743315325966148186558555020834861765526689768371880561510063294857161406783415599987595549249742832472894018336008481239463162160596123334637587102639626334613747584469035377788994951080335145295621141303809208401699383140579784234370433212962549701294557490327915345039736785539182810171621358586598828585945914338147070450135377738837775900049262279077924927424572133106317931037834170242253287377939407573458979723688263335125293054004806634691866986695432845509236568546421095177774413671436200824471636980556801370827632298658729537149331589875199074040922783371553748936641151156007453231144303475285524669545469070200964887839003421723671399980708592531935414262678088053843196096190537828523518384368702604524858315737895816793263164649577505835816917629234902199990503712784374018119048109158314524143587749590847895032293396106716513485468884408566836474462501500356497238218550499994067382687458598481617175106389271282319486609800621311007926196777720697327886147764674266204885628982776927834776344964727336572310616726876742447686216871630304048650918084364293803385183867282800430566589645701462385656793820570672943583L)
#c1,c2 = (94439884067875866926510480826480805218086956848743547499198006820458557396798764306362789177343865957780128049481100649740991723046823411381255593998762330282701428367295145704749575923764033888430043419432755523895502809914793389377786178823780078298402526077689075100615167801149188073166609798060195606072633000544828049766057724062947725409167355039403877440527580919770561607036599124342541749265192021823491918944278440530549040290346018294412510920437610359378345321588108996817523300112050660236797578506114472897358316471445079369284771733206616722439988368610144077799745808242486800244677553898369876207696781377538070465563883203111584722721805287175889444151342208592141472448213468221732504380079996468560634932304003913239528756529682825338927264423302712140156109639630352986070846491530710979222740690647201189995078959423441714667664068681190006816257273563900319001844315873583504406793282181337548468252678860728542345494826571860793722889527787190697802307747398283993641414712543326007228545296721676768940364724157476527100408795556913732012808496296586935767075610857696900781575977854898411278115773743046743452254128886824788564219765260031723480676483312846917497210349237445933078576069670523680684713623446L, 36397082263544765924779841921119370016762339442058655416586193728619075025998163340396086334077244844310435402140631243689371206933579011146142036715931618067708305508617210563902014072058872403638202493268214994615135134434419245572034705984431586848768861656760831721539666418749603708776469542844144251059399582543923184073020411373179905155719536662312209785364646479188735299232303697790049147771382959302788060004896713986087257232599766636580823138965201801581260077589060485570410897810958498454358737888682940093471597533949463149992040055832220962541050083923086389598838921222167415555331634007862804183991931445726265293675584802614392692457772587297132115782027787479633548163420352103982803350538152059924978489540395956166707435927694988026192837010341182919501051673735679100778154041581361254807291072654267471473503037873994575370262350787611333206450177404857861689910339996980215797433744385047164909022377659304404477322770853683922772248965438499817404000913895236832920522508813098567854697829563333570746651008308539370730448094601234580689549622502198266967939450827346984012446321546195185770288650359658551649011648788273482810013579385313367223458143686448798406205345442061625590854243243883117300950978940L)

题目参数较多，因此需要梳理一下各个参数的产生方式以及各个函数的作用。

首先是参数：

• p、q均为素数，且有 p = kq+1
• 选取一个阶为q的数g
• 随机生成三个小于q的参数A、B、d
• 计算h=g^d % p，返回参数(g, h, A, B, p, q)

然后是函数：

• rand函数，实现一个LCG功能
• enc函数，将flag进行如下加密，并返回c1、c2：

$$c1 \equiv m^eh^r \quad(mod\;p)$$ $$c2 \equiv mh^{Br+A \;(mod\;q)} \quad(mod\;p)$$

首先观察到c1、c2中未知的参数一共只有m与r，而m是我们需要求解的flag，因此需要想办法消掉r。而r在指数上并且模了q，所以要先判断出这个模q的作用。

而在参数生成中，我们分析过g是一个阶为q的元素，而h=g^d % p，那么由元素的阶的相关知识可以知道，h的阶为：

$$\frac{q}{gcd(d,q)}$$

而由于q是个素数，因此h也是一个阶为q的素数，所以满足：

$$h^q \equiv 1 \quad(mod\;p)$$

这样说只是为了了解的更清楚一点，实际上只需要将h=g^d代入计算也能发现上式。而这个式子的作用就是消除模q在指数上的影响，如下：

$$h^{Br+A \;(mod\;q)} \equiv h^{Br+A+kq} \equiv h^{Br+A}*(h^q)^k \equiv h^{Br+A} \quad (mod\;p)$$

所以在消元过程中，我们其实不需要关注q。因此消元分析步骤如下：

$$c2 \equiv mh^{rB}h^A \quad(mod\;p)$$ $$c1^B \equiv m^{eB}h^{rB} \quad(mod\;p)$$

所以：

$$c1^Bc2^{-1}h^A \equiv m^{eB}h^{rB}*m^{-1}h^{-rB}h^{-A}*h^A \equiv m^{eB-1} \quad (mod\;p)$$

因此我们获得了：

$$m^{eB-1} \quad (mod\;p)$$

可以直接RSA解密，但是发现eB-1与p-1有公因子167，因此需要先求解部分逆元后AMM开根。

exp：

from Crypto.Util.number import *
import random

(g, h, A, B, p, q) = (52, 47782489586021221729935382562238217213800826152327617948974334325027793433971508995399461776417812670604694882926777607105164020070178881963632306169611641854448509182837621758791538269408388860349616761041456174827996858614494726877767399938809515247000929894281600963992080920650256329287847887064428158469516438206831721224607859023980203694210651902538562842945949404149023836218548894116477022953606370852246884414011363477543284815671096832245521762246149180260936985618856296642080245029837974725521906177900378634071571992373478242159162403228753252168867425697897820696887070051128304178291193132322824455442092893684929701869625045112839344191126228806117685809636908190595562295591835629941512331963039016185366202513504464795106031092314892430859175307526232632986110464780357940552264674214665391043812843917461961230679207586174459563057178720743465356337218948534837994061644332424634750340190113117958830588820626581860957277456320434445207368613679418733984291985618038226928033006640791987978775285182325347153201516936002001839296455263977479446850434913069389565277028444638437387429263495729274142916464752814676819557878779855996225208596159171827854923873570163767937947956753277454486339143489103105750331110111,433229619560374735022060612660487139311547277564407316269466855779330930804160973325703376198605206390912154427123102710354958367692760474727012214464298979098489170777185729836132968187705068687678796437447631516334893543456227545790012358063578349956636488453355182971532300478038635153420232589545761194907476691636706445176390661463152150169542241304542401678253873515488446133330974312465916350895130227137954122794991542025930903127027608739905609108321738139103065645651901833223353774916656293079960486497159730921219805951217073283062070931854507016733789164315751827862830668829125950364981217520865411859759718244136420504507997449935455788230060974032741364271601426191469331266168231203426316280988734802654397014768828735251891167507794161264913387252048434549271931367148180980260205843989153008044839641263127846901551223167574691783927938948745126094512037792728067785201012834153473172824948188352810070916677679450209134179624791196123158336411804834221293611075447043002901607162001357780058394706516204775756666576041740010288970758149528406172022049389998133360726123682741312251431519423867620962951022993364287241463507027520966721930799696555390707280246584903566049326608205785466271642132178515338520410658, 594494499417894774789048451572687632660208181953899084791149805130704950465573064455173172705283156011806901684972459390817538594318847879599780068410149543731305374894040638491310362570467887919519584736646557258917947483658649575357363123407313011773027073062592473100264464401987309633458687673513776139455296286685115396610808047870099635374955339289799615102534094497730932884838674370338192153202045642565170696704452991192684466848026383861073123033948004049599266417667125680356386669226827901570782628388996520826906941293858994180130505009152517646592286697346622724843482147801718703310671546709185342317509441259927498881276856470161174444209513355803640646947368551446328198695259259829546707119878154837158880677882305548928799964929213106969848547576414765380870575558771867763848114411251654245747231121164090765647221739709450477815688276801154266722035408374135871417564206013020997849375553619152730479571927135850379285559873197371293312934173379820835252091990919727655797413411368987930118553258247264348519581466374312010472449698571319621067244494880512957538208007914329691196084901181642263713183616896210154681618376310287185315262021479758282631576946335858068664109425856174388362174761355148787245515144, 261181509476485410165375351178418657075805043256124045823778754055035546150122155335065215645750231604267318872693494310557376958843829685914382636208107544361140482291909865660810395856913449414106045946602124226832733980696161639105193768954092281635195760991693212657816181524313660831938528737461195472275606167593968953647934279724693129491600232382201769523725243272086370087058597321533767924008747705935388941121530345216164771817150616453601212026925759807092457510188966636612860912597984231762129535299227711879953931847880037605415987083573556274570400085013894504645789376654166259691075373526751505971657856429187752015665407876751018316490729668209646098952144838144486106489379202197360745365239628186669447122272538227142855706247593556669905666428363734481409983627496127639634726855140379146669911302677456457202808949896992958886949162850488164457334796828240069980922051762068458877051063958308363343196940785994299643315504146607392461323382470475501119070077564995866998018505817611171892860136485534016608294708527673407517876647349723758712907513973353401204912431800080247493896815299218218930415151745986776831977527196435124521552249406640177674130330651411672455343809240941664288436809369136070604763156723, 781980567294866497501123805923409152921571985796778580310714832500106425599168129745704238460330034743315325966148186558555020834861765526689768371880561510063294857161406783415599987595549249742832472894018336008481239463162160596123334637587102639626334613747584469035377788994951080335145295621141303809208401699383140579784234370433212962549701294557490327915345039736785539182810171621358586598828585945914338147070450135377738837775900049262279077924927424572133106317931037834170242253287377939407573458979723688263335125293054004806634691866986695432845509236568546421095177774413671436200824471636980556801370827632298658729537149331589875199074040922783371553748936641151156007453231144303475285524669545469070200964887839003421723671399980708592531935414262678088053843196096190537828523518384368702604524858315737895816793263164649577505835816917629234902199990503712784374018119048109158314524143587749590847895032293396106716513485468884408566836474462501500356497238218550499994067382687458598481617175106389271282319486609800621311007926196777720697327886147764674266204885628982776927834776344964727336572310616726876742447686216871630304048650918084364293803385183867282800430566589645701462385656793820570672943583)
c1,c2 = (94439884067875866926510480826480805218086956848743547499198006820458557396798764306362789177343865957780128049481100649740991723046823411381255593998762330282701428367295145704749575923764033888430043419432755523895502809914793389377786178823780078298402526077689075100615167801149188073166609798060195606072633000544828049766057724062947725409167355039403877440527580919770561607036599124342541749265192021823491918944278440530549040290346018294412510920437610359378345321588108996817523300112050660236797578506114472897358316471445079369284771733206616722439988368610144077799745808242486800244677553898369876207696781377538070465563883203111584722721805287175889444151342208592141472448213468221732504380079996468560634932304003913239528756529682825338927264423302712140156109639630352986070846491530710979222740690647201189995078959423441714667664068681190006816257273563900319001844315873583504406793282181337548468252678860728542345494826571860793722889527787190697802307747398283993641414712543326007228545296721676768940364724157476527100408795556913732012808496296586935767075610857696900781575977854898411278115773743046743452254128886824788564219765260031723480676483312846917497210349237445933078576069670523680684713623446, 36397082263544765924779841921119370016762339442058655416586193728619075025998163340396086334077244844310435402140631243689371206933579011146142036715931618067708305508617210563902014072058872403638202493268214994615135134434419245572034705984431586848768861656760831721539666418749603708776469542844144251059399582543923184073020411373179905155719536662312209785364646479188735299232303697790049147771382959302788060004896713986087257232599766636580823138965201801581260077589060485570410897810958498454358737888682940093471597533949463149992040055832220962541050083923086389598838921222167415555331634007862804183991931445726265293675584802614392692457772587297132115782027787479633548163420352103982803350538152059924978489540395956166707435927694988026192837010341182919501051673735679100778154041581361254807291072654267471473503037873994575370262350787611333206450177404857861689910339996980215797433744385047164909022377659304404477322770853683922772248965438499817404000913895236832920522508813098567854697829563333570746651008308539370730448094601234580689549622502198266967939450827346984012446321546195185770288650359658551649011648788273482810013579385313367223458143686448798406205345442061625590854243243883117300950978940)
e = 0xfaab

#c = pow(m,eB-1,p)
c = pow(c1,B%q,p)*inverse(c2,p)*pow(h,A%q,p) % p
E = e*B-1
d = inverse(E//167,p-1)
c1 = pow(c,d,p)

def onemod(e, q):
    p = random.randint(1, q-1)
    while(pow(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = pow(p, r**(t-1)*s, q)
    b = pow(o, r*a-1, q)
    c = pow(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = pow(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (pow(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp


def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = pow(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

cp = c1 % p

mp = AMM_rth(cp, 167, p)

rt1 = ALL_ROOT2(167, p)

amp = ALL_Solution(mp, p, rt1, cp, 167)

for i in amp:
    if(b"HITCTF" in long_to_bytes(int(i))):
        print(long_to_bytes(int(i)))

#HITCTF2021{Numb3r_Th30ry_1s_Funny!}

ISITDTU_RSA

题目来源：ISITDTU CTF 2023

题目：

from Crypto.Util.number import bytes_to_long
from FLAG import flag

p1 = 401327687854144602104262478345650053155149834850813791388612732559616436344229998525081674131271
p2 = 500233813775302774885494989064149819654733094475237733501199023993441312997760959607567274704359
p3 = 969568679903672924738597736880903133415133378800072135853678043226600595571519034043189730269981
e1 = 398119
e2 = 283609
e3 = 272383

c = bytes_to_long(flag)
c = pow(c, e1, p1)
c = pow(c, e2, p2)
c = pow(c, e3, p3)

print(f"{c = }")
# c = 104229015434394780017196823454597012062804737684103834919430099907512793339407667578022877402970

题目将flag依次用类似RSA加密的方式连续加密了三次每次使用一个不同的素数ei作为加密指数，使用一个不同的素数pi作为模数。最直接的想法自然就是直接求解解密指数di，然后连续解密三次就能得到明文。

但是，实际操作时发现，任何一个解密指数都不存在，这是因为每一个ei都被pi-1整除，因此无法求解逆元。而这个时候，正常思路来想的话自然马上就会想到AMM算法。

但是直接用AMM算法会遇到一些问题：

• 指数数量级相对较大，可能AMM速度会比较慢
• 每一次AMM开根会开出ei个根，而下一次进行AMM开根时，需要对上一次AMM开根得到的所有根再进行一次开根。比如第二次开根时，我们需要对第一次AMM得到的272383个根均进行一次AMM算法，在第三次开根时则更多，这个数量级是不可接受的

不管怎么样先开一次根试试，实际操作一下会发现，AMM开几十万次方根并得到所有解其实也只需要三四分钟，因此第一个问题并不用特别关心，主要就是要解决第二个问题：如何处理这个三个加密指数相乘的超大复杂度？

要解决这一点需要注意到以下事实，由于：

$$c1 = m^{e1} \quad(mod\;p1)$$ $$c2 = c1^{e2} \quad(mod\;p2)$$ $$c3 = c2^{e3} \quad(mod\;p3)$$

也就是说，在我们AMM算法开出的e3个根中，正确的根需要满足是模p2下的e2次剩余；同理，第二次AMM算法后，正确的根需要满足是模p1下的e1次剩余。

而一个数是否是模p下的k次剩余这个问题，可以通过类似于判断模p下的二次剩余的方法，也就是运用欧拉判别式如下：

$$a^{\frac{p-1}{k}} \equiv 1 \quad (mod\;p)$$

如果一个数a满足上式，那么他就是模p下的k次剩余。那么有了这个判别方式后，对于第一次AMM算法得到的e3个根，我们可以先判断其是否是模p2下的e2次剩余，然后找到符合要求的根，再对其进行AMM算法开e2次根，以此类推，最后由于flag头未知(做出来前不知道这是什么比赛的什么题，别的师傅问我的)，最后一次AMM得到的e1个根中，可以采用判断字节流转成的字符串中没有”\x”来确定是flag串。

那么实际耗时也就是三次独立的AMM算法的总耗时，约10分钟。

exp：

from Crypto.Util.number import *
import random

p1 = 401327687854144602104262478345650053155149834850813791388612732559616436344229998525081674131271
p2 = 500233813775302774885494989064149819654733094475237733501199023993441312997760959607567274704359
p3 = 969568679903672924738597736880903133415133378800072135853678043226600595571519034043189730269981
e1 = 398119
e2 = 283609
e3 = 272383
c = 53439232235483323845772940768628860612955240528996700091904547428796321356639732497361321352956

def onemod(e, q):
    p = random.randint(1, q-1)
    while(pow(p, (q-1)//e, q) == 1):  # (r,s)=1
        p = random.randint(1, q)
    return p

def AMM_rth(o, r, q):  # r|(q-1
    assert((q-1) % r == 0)
    p = onemod(r, q)

    t = 0
    s = q-1
    while(s % r == 0):
        s = s//r
        t += 1
    k = 1
    while((s*k+1) % r != 0):
        k += 1
    alp = (s*k+1)//r

    a = pow(p, r**(t-1)*s, q)
    b = pow(o, r*a-1, q)
    c = pow(p, s, q)
    h = 1

    for i in range(1, t-1):
        d = pow(int(b), r**(t-1-i), q)
        if d == 1:
            j = 0
        else:
            j = (-math.log(d, a)) % r
        b = (b*(c**(r*j))) % q
        h = (h*c**j) % q
        c = (c*r) % q
    result = (pow(o, alp, q)*h)
    return result

def ALL_Solution(m, q, rt, cq, e):
    mp = []
    for pr in rt:
        r = (pr*m) % q
        # assert(pow(r, e, q) == cq)
        mp.append(r)
    return mp

def ALL_ROOT2(r, q):  # use function set() and .add() ensure that the generated elements are not repeated
    li = set()
    while(len(li) < r):
        p = pow(random.randint(1, q-1), (q-1)//r, q)
        li.add(p)
    return li

cp3 = c % p3
mp3 = AMM_rth(cp3, e3, p3)
rt3 = ALL_ROOT2(e3, p3)
amp3 = ALL_Solution(mp3, p3, rt3, cp3, e3)

for i in amp3:
    if(pow(int(i),(p2-1)//e2,p2)==1):
        c2 = int(i)
print("3 Done!")

cp2 = c % p2
mp2 = AMM_rth(cp2, e2, p2)
rt2 = ALL_ROOT2(e2, p2)
amp2 = ALL_Solution(mp2, p2, rt2, cp2, e2)

for i in amp2:
    if(pow(int(i),(p1-1)//e1,p1)==1):
        c1 = int(i)
print("2 Done!")

cp1 = c % p1
mp1 = AMM_rth(cp1, e1, p1)
rt1 = ALL_ROOT2(e1, p1)
amp1 = ALL_Solution(mp1, p1, rt1, cp1, e1)

for i in amp1:
    temp = str(long_to_bytes(int(i)))
    if("\\x" not in temp):
        print(temp)

#ISITDTU{s0_m4ny_m0dul4r_r00t5}

同时注意，正常来说应该把所有符合条件的ei次剩余都进行一次AMM算法，但是这个题实际做下来每次AMM后都确实只有一个根符合要求，因此可以这么写。

sus

题目来源：ImaginaryCTF 2023

题目描述：

Apparently, there is something weird happening with the prime generation.

题目：

from Crypto.Util.number import getPrime, isPrime, bytes_to_long


def sus(sz, d):
    while True:
        p = getPrime(sz)
        pp = sum([p**i for i in range(d)])
        if isPrime(pp):
            return p, pp


p, q = sus(512, 3)
r = getPrime(512 * 3)
n = p * q * r
e = 65537
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = pow(m, e, n)

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

n = 1125214074953003550338693571791155006090796212726975350140792193817691133917160305053542782925680862373280169090301712046464465620409850385467397784321453675396878680853302837289474127359729865584385059201707775238870232263306676727868754652536541637937452062469058451096996211856806586253080405693761350527787379604466148473842686716964601958192702845072731564672276539223958840687948377362736246683236421110649264777630992389514349446404208015326249112846962181797559349629761850980006919766121844428696162839329082145670839314341690501211334703611464066066160436143122967781441535203415038656670887399283874866947000313980542931425158634358276922283935422468847585940180566157146439137197351555650475378438394062212134921921469936079889107953354092227029819250669352732749370070996858744765757449980454966317942024199049138183043402199967786003097786359894608611331234652313102498596516590920508269648305903583314189707679
e = 65537
c = 27126515219921985451218320201366564737456358918573497792847882486241545924393718080635287342203823068993908455514036540227753141033250259348250042460824265354495259080135197893797181975792914836927018186710682244471711855070708553557141164725366015684184788037988219652565179002870519189669615988416860357430127767472945833762628172190228773085208896682176968903038031026206396635685564975604545616032008575709303331751883115339943537730056794403071865003610653521994963115230275035006559472462643936356750299150351321395319301955415098283861947785178475071537482868994223452727527403307442567556712365701010481560424826125138571692894677625407372483041209738234171713326474989489802947311918341152810838321622423351767716922856007838074781678539986694993211304216853828611394630793531337147512240710591162375077547224679647786450310708451590432452046103209161611561606066902404405369379357958777252744114825323084960942810

最近学习了一下商环，然后偶然发现了这道题，解法很有意思，因此记录一下。

题目加密过程很简单：

• 生成512比特的素数p，并按如下方式生成q，保证q为素数：

$$q = 1+p+p^2$$

• 生成512*3比特的素数r，然后计算n=pqr，并按RSA方式加密flag，给出公钥n、e以及密文c，要求还原flag

我们的目标肯定是获得n的分解，而n具有如下形式：

$$n = p(1+p+p^2)r$$

第一个想法是，能否直接copper解出模pq下的小根p，但是马上就会发现不行：因为r是一个1536比特的大素数，同时写出的f(x)=x(1+x+x^2)的度也不低，p肯定远远超过了理论小根的上界。

那么就换思路，肯定要利用素数q的特殊生成方式：

$$q = 1+p+p^2$$

看这个形式应该不难与立方差联系起来：

$$p^3-1 = (p-1)(1+p+p^2) = (p-1)q$$

但是接下来怎么用就完全没思路了，然后就只能看wp和请求认识的师傅帮助。最后发现解法对于我来说是真的很有想象力，原wp如下：

Pick a random polynomial $f(x)=x^3+ax^2+bx+c$, and pick a random element $a$ in $\mathbb{R}=\mathbb{Z}_n[x]/f(x)$. If $f(x)$ is irreducible in $\mathbb{F}_p[x]$ then $\mathbb{K}=\mathbb{F}_p[x]/f(x)=\mathbb{F}_{p^3}$ will be a field with order $p^3-1=(p-1)(p^2+p+1)$.

We raise $a$ to the power of $n=pqr=p(p^2+p+1)r$ then $a^n$ would probably be of order $p-1$, which implies it will be in the form of $u+0x+0x^2$ in $\mathbb{K}$. This means we can take the degree 1 or 2 coefficient of $a^n$ in $\mathbb{R}$ and gcd it with $n$ to get $p$, then we can fully factor $n$ to decrypt the flag.

This is basically the same idea as Pollard’s p-1 or Williams’ p+1 factorization algorithm, but we are doing it in a field with higher degree.

其实已经讲得非常清楚了，接下来我会对其中一些原理具体说明一下，有不严谨或者错误的地方欢迎各位师傅指出。

首先就是，要利用上立方差公式，我们就要构造一个阶为p^3-1的群，并找某个群中的生成元g，这样就有：

$$g^n = g^{p(1+p+p^2)r} = (g^{(1+p+p^2)})^{pr}$$

我们就可以计算出g^n的阶为：

$$order(g^n) = \frac{p^3-1}{gcd(n,p^3-1)} = \frac{p^3-1}{1+p+p^2} = p-1$$

我们要想办法利用这一点。那么接下来就产生了两个待解决的问题：

• 如何建立一个阶为p^3-1的群？
• 如何利用g^n的阶为p-1这一条性质？

如何建立阶为p^3-1的群

要明白这个问题需要对有限域、多项式环有一定了解。具体说来，我们先定义两个多项式环：

$$Ring1 = Z_n[x]$$ $$Ring2 = F_p[x]$$

以这两个多项式环为基础，我们选择一个度为3的Ring1下的随机多项式f(x)，也就是：

$$f(x) = x^3 + ax^2 + bx + c$$

然后，以这个多项式为基础，我们定义两个多项式商环：

$$N = Z_n[x]/f(x)$$ $$P = F_p[x]/f(x)$$

如果我们随机选择的f(x)在Ring2中不可约，那么我们可以证明，商环P其实就是一个大小为p^3的有限域，也就是：

$$P = F_p[x]/f(x) = F_{p^3}$$

对于他是域，这一点的证明是这样的：

而对于这个域大小为p^3，这一点很好想通，其实就是每一项的系数共有p种选择，然后最高是二次项，所以域中共有p^3种不同的元素，因此其大小为p^3。

但是这个域与我们需要的大小为p^3-1的循环群好像还差一点，但其实我们把域中的0去除掉，那么剩下的p^3-1个元素其实就构成了一个乘法循环群，这就是我们所需要的了。

而好像我们没有p，只能构造出模n的多项式商环：

$$N = Z_n[x]/f(x)$$

但是我们要注意到，P环应该是N的子环，这一点我们会在之后用到。

如何利用g^n的阶为p-1

我们继续在P环下分析，假设我们能取得其上的一个随机元素为生成元g，那么由前面我们知道，g^n的阶为p-1。

然后我们又要用到一个比较重要的性质：

也就是说，我们刚才去除0的乘法循环群的阶为p^3-1，那么也就是说，阶为p-1的元素一共也就只有：

$$\phi(p-1)$$

这么多个，然后我们又知道g^n为度最大为2的多项式，也就是：

$$g^n = ax^2 + bx +c$$

而阶为p-1的任意元素t在该循环群中都应当满足：

$$t^{p-1} = 1$$

然后我们又知道，对于任意0<a<p，以下式子在该群中都成立：

$$(a + 0x + 0x^2)^{p-1} = 1$$

而a有p-1种取值，显然大于phi(p-1)，所以g^n其实只能在这样形式的多项式中产生：

$$a + 0x + 0x^2$$

也就是说，g^n均只存在常数项，一次项和二次项系数均为0。而由于P是N的子环，所以我们在N上运算g^n，得到的一次项系数和二次项系数在模n意义下，就应该等于kp。因此我们将g^n的一次项或二次项系数与n求解gcd即可得到p，进而得到n的全部分解，从而求解密文。

(2.11更新)

在好几个师傅提问后，我发现上面的说法对下面这一点的确讲的不是很清楚：

g^n其实只能在这样形式的多项式中产生：

$$a + 0x + 0x^2$$

所以在这里重新组织一下说法。首先从这一点出发：

• 对我们刚才生成的大小为p^3-1的循环群，记他为G，那么G中所有满足g^(p-1)=1的元素g会构成一个大小为p-1的循环群，记他为K

而要说清楚这一点主要是要说清楚三个方面：

• K是群。这个很好验证，因为显然K中任意元素a、b均满足 $ab^{-1} \in K$

• K是循环群。因为我们构造的是有限域，有限域的乘法群是循环群，而K是他的子群，所以K就也是个循环群。

• K大小为p-1。因为生成元的阶是p-1，也就是K的阶

现在我们知道，K是一个大小为p-1的循环群，他包含了所有G中所有满足g^(p-1)=1的元素g。也就是说，这样的元素g一共只有p-1个。

那么显然下面这样的元素g都在K中，且两两不相同：

$$a + 0x + 0x^2$$

这样的元素一共有p-1个，刚好等于K的大小，这说明K其实就是由所有常数项构成的群。而g^n由定义又都在K里(因为$(g^n)^{p-1}=1$)，所以就证明了这个结论。

exp(搬运原wp中的exp)：

from Crypto.Util.number import *

n = 1125214074953003550338693571791155006090796212726975350140792193817691133917160305053542782925680862373280169090301712046464465620409850385467397784321453675396878680853302837289474127359729865584385059201707775238870232263306676727868754652536541637937452062469058451096996211856806586253080405693761350527787379604466148473842686716964601958192702845072731564672276539223958840687948377362736246683236421110649264777630992389514349446404208015326249112846962181797559349629761850980006919766121844428696162839329082145670839314341690501211334703611464066066160436143122967781441535203415038656670887399283874866947000313980542931425158634358276922283935422468847585940180566157146439137197351555650475378438394062212134921921469936079889107953354092227029819250669352732749370070996858744765757449980454966317942024199049138183043402199967786003097786359894608611331234652313102498596516590920508269648305903583314189707679
e = 65537
c = 27126515219921985451218320201366564737456358918573497792847882486241545924393718080635287342203823068993908455514036540227753141033250259348250042460824265354495259080135197893797181975792914836927018186710682244471711855070708553557141164725366015684184788037988219652565179002870519189669615988416860357430127767472945833762628172190228773085208896682176968903038031026206396635685564975604545616032008575709303331751883115339943537730056794403071865003610653521994963115230275035006559472462643936356750299150351321395319301955415098283861947785178475071537482868994223452727527403307442567556712365701010481560424826125138571692894677625407372483041209738234171713326474989489802947311918341152810838321622423351767716922856007838074781678539986694993211304216853828611394630793531337147512240710591162375077547224679647786450310708451590432452046103209161611561606066902404405369379357958777252744114825323084960942810
k = 3

R = Zmod(n)["x"]
while True:
    Q = R.quo(R.random_element(k))
    pp = gcd(ZZ(list(Q.random_element() ^ n)[1]), n)
    if pp != 1:
        qq = sum([pp**i for i in range(k)])
        rr = n // (pp * qq)
        assert n == pp * qq * rr
        break
phi = (pp - 1) * (qq - 1) * (rr - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m))

#ictf{idk_if_it_solvable_if_q_is_2+p+p^2_instead}

中间有些地方阐述的可能会出错，欢迎各位师傅提出。

Complex_RSA

题目来源：暂不明确

题目：

import os
import hashlib
from Crypto.Util.number import *
from secret import flag, totient
# where totient is a function used to calculate phi

class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im
    
    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)
    
    def show(self):
        print([self.re, self.im])

def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

def pad(msg, length):
    pad_length = length - len(msg) - 1
    pad_data = os.urandom(pad_length)
    return msg + b'\x00' + pad_data

def unpad(msg):
    return msg.split(b"\x00")[0]

bits = 512
p = getPrime(bits)
q = getPrime(bits)
n = p * q

sha_flag = hashlib.sha256(flag).digest()

m1 = Complex(
        int.from_bytes(sha_flag[:len(sha_flag)//2], "big"),
        int.from_bytes(sha_flag[len(sha_flag)//2:], "big"),
    )

m2 = Complex(
        int.from_bytes(pad(flag[:len(flag)//2], bits//4-1), "big"),
        int.from_bytes(pad(flag[len(flag)//2:], bits//4-1), "big"),
    )

phi = totient(p, q)
e = q * inverse(p, phi)
c1 = complex_pow(m1, e, n)
c2 = complex_pow(m2, e, n)

c1.show()
c2.show()
print(f'n = {n}')

"""
[90554536599623574119664951128649936419332926063696768860765928746438458550068553748440108394673303800443215316190882880737918820592384729010491685487061658710808286341751196450604089438847354206384322610922839055308138101241906861635339635907663440043442187064090630207952625897567214431195621589834131462698, 9144096375153318849308858335764188418198064372272913164911615933938183103747900881824918069830188301084043148828961577193063557255905230182831945580084452509300200269659063051152684191139872067872645370760797859584822240361290678189844670289832298393156571913616456958845361092243648857334156534377833472900]
[62925714576233017213228404230949787334346543378320798964656732359587152905032848271156799538355748406136742979043729040728123730886381468564779041856310262770766050213464073568850702827835472680885186487027698395099598698463717279017013124488699475168052581476224742146967412904416266652605031934025266540003, 62818668456104375760667670741457826560706388018921820295286033114468271151921637926389738844622672202424650967678199715932465104135980734708459543588178208672956785650944371545080965650112025782049517299538052360417245732776384089052839997333049599655001615752078742624898059780909287845495731050387891926520]
n = 94040393367054633265453751757391098049234338193258976478647369399924701067077628840760704857546243644552533845934146003988635403227234096447871132283820920489003286967145732739404245319615714787916756200564828237043658350145929927911058782352154997346295194977765305107634012698472977467843980475009837261877
"""

题目基于一个复数类，在复数的基础上实现了一次RSA加密。

具体来说，题目的加密流程是：

• 生成两个512比特的素数p、q，计算其乘积n
• 将flag进行sha256哈希后，分为前后两部分分别作为m1的实部与虚部值
• 将flag分为前后两部分，并分别填充至127字节，作为m2的实部与虚部值
• 对m1、m2两个复数分别进行RSA加密，并给出密文

值得注意的是，这里的加密指数e是一个特殊值：

$$e = q*inverse(p,phi)$$

那么切入点肯定也就是这个e的取值。首先需要明白一个地方，复数中如何计算欧拉函数？这里先给出结论：

$$totient(p,q) = (p^2-1)(q^2-1)$$

详细说明可以参考这里：

singular1.pdf (cnrs.fr)

我的理解是，虽然是复数域上的欧拉函数，但欧拉函数值仍然应该代表小于p且与p互素的复数数量。而从0到p的所有复数应该是：

$$a + bi \quad , \quad a \in[0,p),b \in [0,p)$$

显然一共有p^2个复数，所以去除0后，欧拉函数值就是(p^2-1)。

先把这个当作一点预备知识。从这里开始，我们先把这个题目当作整数域看待，看看如何解题(因为方法相通，整数域解出来后迁移到复数域上就好)，我们对加密指数e进行如下推导。

由于有：

$$e = q*inverse(p,phi)$$

所以：

$$ep \equiv q \quad(mod\;phi)$$

两边同乘q，可以得到：

$$epq \equiv q^2 \quad (mod\;phi)$$

即：

$$en \equiv q^2 \quad (mod\;phi)$$

那么我们把这个放在指数上，对c1进行乘方操作：

$$c_1^{n} \equiv m_1^{en} \equiv m_1^{q^2} \quad(mod\;n)$$

转到模q下，由欧拉定理就有：

$$c_1^n \equiv m_1 \quad(mod\;q)$$

然后注意，m1是一个sha256值，小于等于256比特，因此可以算作一个模q下的小根。所以我们可以copper解出m1，然后用c1^n-m1与n求gcd就能得到q，然后就可以用q去解m2了。

而放在复数域里这也是一样。并且由于拆成了实虚部两个部分，每一部分只有128比特的数量级，完全符合copper的界。所以我们只需要取实部或虚部其中一个进行copper就能得到n的分解。

得到n的分解后就可以计算复数域中的phi(n)，然后对复数c2进行RSA解密操作即可。

exp：

from Crypto.Util.number import *

class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)
    
    def show(self):
        print([self.re, self.im])

    def getvalue(self):
        return self.re, self.im

def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

c1 = Complex(90554536599623574119664951128649936419332926063696768860765928746438458550068553748440108394673303800443215316190882880737918820592384729010491685487061658710808286341751196450604089438847354206384322610922839055308138101241906861635339635907663440043442187064090630207952625897567214431195621589834131462698, 9144096375153318849308858335764188418198064372272913164911615933938183103747900881824918069830188301084043148828961577193063557255905230182831945580084452509300200269659063051152684191139872067872645370760797859584822240361290678189844670289832298393156571913616456958845361092243648857334156534377833472900)
c2 = Complex(62925714576233017213228404230949787334346543378320798964656732359587152905032848271156799538355748406136742979043729040728123730886381468564779041856310262770766050213464073568850702827835472680885186487027698395099598698463717279017013124488699475168052581476224742146967412904416266652605031934025266540003, 62818668456104375760667670741457826560706388018921820295286033114468271151921637926389738844622672202424650967678199715932465104135980734708459543588178208672956785650944371545080965650112025782049517299538052360417245732776384089052839997333049599655001615752078742624898059780909287845495731050387891926520)
n = 94040393367054633265453751757391098049234338193258976478647369399924701067077628840760704857546243644552533845934146003988635403227234096447871132283820920489003286967145732739404245319615714787916756200564828237043658350145929927911058782352154997346295194977765305107634012698472977467843980475009837261877

#part1 get p,q
m1 = complex_pow(c1, n, n).getvalue()
n = 94040393367054633265453751757391098049234338193258976478647369399924701067077628840760704857546243644552533845934146003988635403227234096447871132283820920489003286967145732739404245319615714787916756200564828237043658350145929927911058782352154997346295194977765305107634012698472977467843980475009837261877
PR.<x> = PolynomialRing(Zmod(n))
f = x-m1[0]
f= f.monic()
res = f.small_roots(X=2^130,beta=0.4,epsilon=0.03)
m1_=int(res[0])
q = GCD(m1[0]-m1_,n)
p = n // q


#part2 get flag
phi = (p^2-1)*(q^2-1)
e = q * inverse(p, phi)
d = inverse(e,phi)
flag = complex_pow(c2, d ,n).getvalue()
print(long_to_bytes(int(flag[0])))
print(long_to_bytes(int(flag[1])))

#flag{3ef6db06-b837-11ed-9825-00155dfcdef9}