确实不会，简单记一下

题一

[*CTF-2022]ezrsa

题目描述：

from Crypto.Util.number import getStrongPrime
from gmpy import next_prime
from random import getrandbits
from flag import flag

p=getStrongPrime(1024)
q=next_prime(p^((1<<900)-1)^getrandbits(300))
n=p*q
e=65537

m=int(flag.encode('hex'),16)
assert m<n
c=pow(m,e,n)

print(hex(n))
n = 0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3

print(hex(c))
c = 0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

exp:

# 对N开方得到p的高位，异或关系得到p中间几位，coppersmith得到p的低位
from Crypto.Util.number import *
n=0xe78ab40c343d4985c1de167e80ba2657c7ee8c2e26d88e0026b68fe400224a3bd7e2a7103c3b01ea4d171f5cf68c8f00a64304630e07341cde0bc74ef5c88dcbb9822765df53182e3f57153b5f93ff857d496c6561c3ddbe0ce6ff64ba11d4edfc18a0350c3d0e1f8bd11b3560a111d3a3178ed4a28579c4f1e0dc17cb02c3ac38a66a230ba9a2f741f9168641c8ce28a3a8c33d523553864f014752a04737e555213f253a72f158893f80e631de2f55d1d0b2b654fc7fa4d5b3d95617e8253573967de68f6178f78bb7c4788a3a1e9778cbfc7c7fa8beffe24276b9ad85b11eed01b872b74cdc44959059c67c18b0b7a1d57512319a5e84a9a0735fa536f1b3
c=0xd7f6c90512bc9494370c3955ff3136bb245a6d1095e43d8636f66f11db525f2063b14b2a4363a96e6eb1bea1e9b2cc62b0cae7659f18f2b8e41fca557281a1e859e8e6b35bd114655b6bf5e454753653309a794fa52ff2e79433ca4bbeb1ab9a78ec49f49ebee2636abd9dd9b80306ae1b87a86c8012211bda88e6e14c58805feb6721a01481d1a7031eb3333375a81858ff3b58d8837c188ffcb982a631e1a7a603b947a6984bd78516c71cfc737aaba479688d56df2c0952deaf496a4eb3f603a46a90efbe9e82a6aef8cfb23e5fcb938c9049b227b7f15c878bd99b61b6c56db7dfff43cd457429d5dcdb5fe314f1cdf317d0c5202bad6a9770076e9b25b1

PR.<x> = PolynomialRing(Zmod(n))
pm=int(sqrt(n))>>900
p = (1<<900)-1
q = 1<<300-1
p+=pm*(1<<900)
q+=pm*(1<<900)
#in the rest place, '1' either belong to p or q
for i in range(898, 301, -1):
    cur = 1<<i
    if (p^^cur) * (q^^cur) < n:
	p ^^= cur
	q ^^= cur
	
f=x+p
roots=f.small_roots(X=2**450,beta=0.4)
p=p+roots[0]
q=n//int(p)
fn=(p-1)*(q-1)
d=inverse(65537,fn)
print(hex(int(pow(c,d,n)))[2:-1].decode('hex'))

题二

多项式RSA

([watevrCTF-2019]Swedish RSA)

题目描述:

flag = bytearray(raw_input())
flag = list(flag)
length = len(flag)
bits = 16

## Prime for Finite Field.
p = random_prime(2^bits-1, False, 2^(bits-1))

file_out = open("downloads/polynomial_rsa.txt", "w")
file_out.write("Prime: " + str(p) + "\n")

## Univariate Polynomial Ring in y over Finite Field of size p
R.<y> = PolynomialRing(GF(p))

## Analogous to the primes in Z
def gen_irreducable_poly(deg): # 生成一个不可约多项式
    while True:
        out = R.random_element(degree=deg) # 随机生成次数为deg的元素
        if out.is_irreducible():
            return out


## Polynomial "primes"
P = gen_irreducable_poly(ZZ.random_element(length, 2*length))
Q = gen_irreducable_poly(ZZ.random_element(length, 2*length))

## Public exponent key
e = 65537

## Modulus
N = P*Q
file_out.write("Modulus: " + str(N) + "\n")

## Univariate Quotient Polynomial Ring in x over Finite Field of size 659 with modulus N(x)
S.<x> = R.quotient(N)

## Encrypt
m = S(flag)
c = m^e

file_out.write("Ciphertext: " + str(c))
file_out.close()

'''
Prime: 43753
Modulus: 34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814
Ciphertext: 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659
'''

题目分析：
明显是基于多项式的RSA
对使用factor对N进行分解得到p,q

from Crypto.Util.number import *
from gmpy2 import *
p = 43753
R.<y> = PolynomialRing(GF(p))
N = R('34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814')
c = R('5209

 - List item

*y^176 + 10881*y^175 + 31096*y^174 + 23354*y^173 + 28337*y^172 + 15982*y^171 + 13515*y^170 + 21641*y^169 + 10254*y^168 + 34588*y^167 + 27434*y^166 + 29552*y^165 + 7105*y^164 + 22604*y^163 + 41253*y^162 + 42675*y^161 + 21153*y^160 + 32838*y^159 + 34391*y^158 + 832*y^157 + 720*y^156 + 22883*y^155 + 19236*y^154 + 33772*y^153 + 5020*y^152 + 17943*y^151 + 26967*y^150 + 30847*y^149 + 10306*y^148 + 33966*y^147 + 43255*y^146 + 20342*y^145 + 4474*y^144 + 3490*y^143 + 38033*y^142 + 11224*y^141 + 30565*y^140 + 31967*y^139 + 32382*y^138 + 9759*y^137 + 1030*y^136 + 32122*y^135 + 42614*y^134 + 14280*y^133 + 16533*y^132 + 32676*y^131 + 43070*y^130 + 36009*y^129 + 28497*y^128 + 2940*y^127 + 9747*y^126 + 22758*y^125 + 16615*y^124 + 14086*y^123 + 13038*y^122 + 39603*y^121 + 36260*y^120 + 32502*y^119 + 17619*y^118 + 17700*y^117 + 15083*y^116 + 11311*y^115 + 36496*y^114 + 1300*y^113 + 13601*y^112 + 43425*y^111 + 10376*y^110 + 11551*y^109 + 13684*y^108 + 14955*y^107 + 6661*y^106 + 12674*y^105 + 21534*y^104 + 32132*y^103 + 34135*y^102 + 43684*y^101 + 837*y^100 + 29311*y^99 + 4849*y^98 + 26632*y^97 + 26662*y^96 + 10159*y^95 + 32657*y^94 + 12149*y^93 + 17858*y^92 + 35805*y^91 + 19391*y^90 + 30884*y^89 + 42039*y^88 + 17292*y^87 + 4694*y^86 + 1497*y^85 + 1744*y^84 + 31071*y^83 + 26246*y^82 + 24402*y^81 + 22068*y^80 + 39263*y^79 + 23703*y^78 + 21484*y^77 + 12241*y^76 + 28821*y^75 + 32886*y^74 + 43075*y^73 + 35741*y^72 + 19936*y^71 + 37219*y^70 + 33411*y^69 + 8301*y^68 + 12949*y^67 + 28611*y^66 + 42654*y^65 + 6910*y^64 + 18523*y^63 + 31144*y^62 + 21398*y^61 + 36298*y^60 + 27158*y^59 + 918*y^58 + 38601*y^57 + 4269*y^56 + 5699*y^55 + 36444*y^54 + 34791*y^53 + 37978*y^52 + 32481*y^51 + 8039*y^50 + 11012*y^49 + 11454*y^48 + 30450*y^47 + 1381*y^46 + 32403*y^45 + 8202*y^44 + 8404*y^43 + 37648*y^42 + 43696*y^41 + 34237*y^40 + 36490*y^39 + 41423*y^38 + 35792*y^37 + 36950*y^36 + 31086*y^35 + 38970*y^34 + 12439*y^33 + 7963*y^32 + 16150*y^31 + 11382*y^30 + 3038*y^29 + 20157*y^28 + 23531*y^27 + 32866*y^26 + 5428*y^25 + 21132*y^24 + 13443*y^23 + 28909*y^22 + 42716*y^21 + 6567*y^20 + 24744*y^19 + 8727*y^18 + 14895*y^17 + 28172*y^16 + 30903*y^15 + 26608*y^14 + 27314*y^13 + 42224*y^12 + 42551*y^11 + 37726*y^10 + 11203*y^9 + 36816*y^8 + 5537*y^7 + 20301*y^6 + 17591*y^5 + 41279*y^4 + 7999*y^3 + 33753*y^2 + 34551*y + 9659')
e = 65537
factor(N)

# P = (34036) * (y^65 + 39688*y^64 + 22199*y^63 + 41942*y^62 + 7803*y^61 + 19710*y^60 + 14794*y^59 + 41388*y^58 + 2418*y^57 + 19208*y^56 + 39941*y^55 + 36392*y^54 + 19813*y^53 + 33864*y^52 + 29099*y^51 + 15484*y^50 + 27185*y^49 + 27721*y^48 + 31508*y^47 + 19404*y^46 + 10134*y^45 + 43481*y^44 + 3899*y^43 + 32849*y^42 + 3534*y^41 + 32086*y^40 + 14221*y^39 + 42982*y^38 + 1403*y^37 + 1619*y^36 + 36054*y^35 + 33615*y^34 + 6628*y^33 + 31709*y^32 + 6968*y^31 + 28517*y^30 + 12938*y^29 + 21124*y^28 + 10400*y^27 + 28889*y^26 + 7273*y^25 + 36442*y^24 + 14935*y^23 + 29365*y^22 + 4869*y^21 + 43562*y^20 + 6435*y^19 + 4403*y^18 + 32311*y^17 + 7575*y^16 + 28199*y^15 + 28065*y^14 + 23870*y^13 + 37314*y^12 + 15299*y^11 + 7082*y^10 + 36230*y^9 + 18367*y^8 + 12531*y^7 + 25906*y^6 + 26878*y^5 + 43073*y^4 + 11582*y^3 + 4482*y^2 + 35044*y + 31388)
# Q = (y^112 + 31097*y^111 + 15815*y^110 + 17170*y^109 + 43684*y^108 + 16873*y^107 + 17269*y^106 + 10853*y^105 + 10690*y^104 + 24864*y^103 + 10224*y^102 + 28704*y^101 + 16049*y^100 + 1154*y^99 + 40034*y^98 + 29922*y^97 + 27404*y^96 + 32514*y^95 + 40962*y^94 + 32858*y^93 + 36590*y^92 + 41302*y^91 + 20803*y^90 + 43521*y^89 + 13746*y^88 + 19857*y^87 + 21539*y^86 + 36888*y^85 + 16032*y^84 + 35825*y^83 + 24705*y^82 + 31143*y^81 + 22088*y^80 + 6686*y^79 + 37947*y^78 + 5661*y^77 + 29405*y^76 + 36071*y^75 + 35492*y^74 + 28985*y^73 + 36015*y^72 + 24095*y^71 + 34920*y^70 + 6615*y^69 + 9606*y^68 + 4255*y^67 + 22981*y^66 + 3910*y^65 + 23897*y^64 + 22711*y^63 + 23350*y^62 + 7969*y^61 + 8558*y^60 + 8001*y^59 + 8431*y^58 + 3314*y^57 + 23364*y^56 + 39391*y^55 + 32722*y^54 + 2543*y^53 + 22196*y^52 + 24189*y^51 + 19420*y^50 + 10649*y^49 + 19070*y^48 + 23863*y^47 + 19597*y^46 + 39699*y^45 + 7620*y^44 + 25067*y^43 + 29912*y^42 + 14998*y^41 + 14492*y^40 + 31322*y^39 + 43145*y^38 + 32006*y^37 + 38976*y^36 + 32534*y^35 + 6972*y^34 + 37351*y^33 + 30104*y^32 + 6032*y^31 + 33729*y^30 + 27110*y^29 + 5268*y^28 + 2974*y^27 + 2985*y^26 + 31610*y^25 + 28364*y^24 + 34924*y^23 + 17414*y^22 + 28813*y^21 + 43680*y^20 + 32175*y^19 + 18248*y^18 + 25171*y^17 + 31185*y^16 + 30125*y^15 + 36836*y^14 + 7218*y^13 + 11292*y^12 + 31123*y^11 + 40360*y^10 + 34093*y^9 + 39606*y^8 + 2788*y^7 + 27277*y^6 + 21835*y^5 + 1331*y^4 + 32614*y^3 + 25020*y^2 + 20981*y + 12108)

多项式中phi != (P-1)*(Q-1)
整数中phi是指与n互质且小于n的正整数的个数
多项式中phi是与n没有公共多项式的且不高于其幂级的多项式的个数
此处p,q均是不可约多项式，故$phi=(p^{65}-1)\ast (p^{112}-1)$，由此可得到d = invert(e,phi)
整数中m = pow(c,d,n)，而此处c是多项式，d是整数，说是这也写得到的m并不是在有限域$GF(p)$上

from Crypto.Util.number import *
from gmpy2 import *
p = 43753
R.<y> = PolynomialRing(GF(p))
N = R('34036*y^177 + 23068*y^176 + 13147*y^175 + 36344*y^174 + 10045*y^173 + 41049*y^172 + 17786*y^171 + 16601*y^170 + 7929*y^169 + 37570*y^168 + 990*y^167 + 9622*y^166 + 39273*y^165 + 35284*y^164 + 15632*y^163 + 18850*y^162 + 8800*y^161 + 33148*y^160 + 12147*y^159 + 40487*y^158 + 6407*y^157 + 34111*y^156 + 8446*y^155 + 21908*y^154 + 16812*y^153 + 40624*y^152 + 43506*y^151 + 39116*y^150 + 33011*y^149 + 23914*y^148 + 2210*y^147 + 23196*y^146 + 43359*y^145 + 34455*y^144 + 17684*y^143 + 25262*y^142 + 982*y^141 + 24015*y^140 + 27968*y^139 + 37463*y^138 + 10667*y^137 + 39519*y^136 + 31176*y^135 + 27520*y^134 + 32118*y^133 + 8333*y^132 + 38945*y^131 + 34713*y^130 + 1107*y^129 + 43604*y^128 + 4433*y^127 + 18110*y^126 + 17658*y^125 + 32354*y^124 + 3219*y^123 + 40238*y^122 + 10439*y^121 + 3669*y^120 + 8713*y^119 + 21027*y^118 + 29480*y^117 + 5477*y^116 + 24332*y^115 + 43480*y^114 + 33406*y^113 + 43121*y^112 + 1114*y^111 + 17198*y^110 + 22829*y^109 + 24424*y^108 + 16523*y^107 + 20424*y^106 + 36206*y^105 + 41849*y^104 + 3584*y^103 + 26500*y^102 + 31897*y^101 + 34640*y^100 + 27449*y^99 + 30962*y^98 + 41434*y^97 + 22125*y^96 + 24314*y^95 + 3944*y^94 + 18400*y^93 + 38476*y^92 + 28904*y^91 + 27936*y^90 + 41867*y^89 + 25573*y^88 + 25659*y^87 + 33443*y^86 + 18435*y^85 + 5934*y^84 + 38030*y^83 + 17563*y^82 + 24086*y^81 + 36782*y^80 + 20922*y^79 + 38933*y^78 + 23448*y^77 + 10599*y^76 + 7156*y^75 + 29044*y^74 + 23605*y^73 + 7657*y^72 + 28200*y^71 + 2431*y^70 + 3860*y^69 + 23259*y^68 + 14590*y^67 + 33631*y^66 + 15673*y^65 + 36049*y^64 + 29728*y^63 + 22413*y^62 + 18602*y^61 + 18557*y^60 + 23505*y^59 + 17642*y^58 + 12595*y^57 + 17255*y^56 + 15316*y^55 + 8948*y^54 + 38*y^53 + 40329*y^52 + 9823*y^51 + 5798*y^50 + 6379*y^49 + 8662*y^48 + 34640*y^47 + 38321*y^46 + 18760*y^45 + 13135*y^44 + 15926*y^43 + 34952*y^42 + 28940*y^41 + 13558*y^40 + 42579*y^39 + 38015*y^38 + 33788*y^37 + 12381*y^36 + 195*y^35 + 13709*y^34 + 31500*y^33 + 32994*y^32 + 30486*y^31 + 40414*y^30 + 2578*y^29 + 30525*y^28 + 43067*y^27 + 6195*y^26 + 36288*y^25 + 23236*y^24 + 21493*y^23 + 15808*y^22 + 34500*y^21 + 6390*y^20 + 42994*y^19 + 42151*y^18 + 19248*y^17 + 19291*y^16 + 8124*y^15 + 40161*y^14 + 24726*y^13 + 31874*y^12 + 30272*y^11 + 30761*y^10 + 2296*y^9 + 11017*y^8 + 16559*y^7 + 28949*y^6 + 40499*y^5 + 22377*y^4 + 33628*y^3 + 30598*y^2 + 4386*y + 23814')
c = R('5209*y^176 + 10881*y^175 + 31096*y^174 + 23354*y^173 + 28337*y^172 + 15982*y^171 + 13515*y^170 + 21641*y^169 + 10254*y^168 + 34588*y^167 + 27434*y^166 + 29552*y^165 + 7105*y^164 + 22604*y^163 + 41253*y^162 + 42675*y^161 + 21153*y^160 + 32838*y^159 + 34391*y^158 + 832*y^157 + 720*y^156 + 22883*y^155 + 19236*y^154 + 33772*y^153 + 5020*y^152 + 17943*y^151 + 26967*y^150 + 30847*y^149 + 10306*y^148 + 33966*y^147 + 43255*y^146 + 20342*y^145 + 4474*y^144 + 3490*y^143 + 38033*y^142 + 11224*y^141 + 30565*y^140 + 31967*y^139 + 32382*y^138 + 9759*y^137 + 1030*y^136 + 32122*y^135 + 42614*y^134 + 14280*y^133 + 16533*y^132 + 32676*y^131 + 43070*y^130 + 36009*y^129 + 28497*y^128 + 2940*y^127 + 9747*y^126 + 22758*y^125 + 16615*y^124 + 14086*y^123 + 13038*y^122 + 39603*y^121 + 36260*y^120 + 32502*y^119 + 17619*y^118 + 17700*y^117 + 15083*y^116 + 11311*y^115 + 36496*y^114 + 1300*y^113 + 13601*y^112 + 43425*y^111 + 10376*y^110 + 11551*y^109 + 13684*y^108 + 14955*y^107 + 6661*y^106 + 12674*y^105 + 21534*y^104 + 32132*y^103 + 34135*y^102 + 43684*y^101 + 837*y^100 + 29311*y^99 + 4849*y^98 + 26632*y^97 + 26662*y^96 + 10159*y^95 + 32657*y^94 + 12149*y^93 + 17858*y^92 + 35805*y^91 + 19391*y^90 + 30884*y^89 + 42039*y^88 + 17292*y^87 + 4694*y^86 + 1497*y^85 + 1744*y^84 + 31071*y^83 + 26246*y^82 + 24402*y^81 + 22068*y^80 + 39263*y^79 + 23703*y^78 + 21484*y^77 + 12241*y^76 + 28821*y^75 + 32886*y^74 + 43075*y^73 + 35741*y^72 + 19936*y^71 + 37219*y^70 + 33411*y^69 + 8301*y^68 + 12949*y^67 + 28611*y^66 + 42654*y^65 + 6910*y^64 + 18523*y^63 + 31144*y^62 + 21398*y^61 + 36298*y^60 + 27158*y^59 + 918*y^58 + 38601*y^57 + 4269*y^56 + 5699*y^55 + 36444*y^54 + 34791*y^53 + 37978*y^52 + 32481*y^51 + 8039*y^50 + 11012*y^49 + 11454*y^48 + 30450*y^47 + 1381*y^46 + 32403*y^45 + 8202*y^44 + 8404*y^43 + 37648*y^42 + 43696*y^41 + 34237*y^40 + 36490*y^39 + 41423*y^38 + 35792*y^37 + 36950*y^36 + 31086*y^35 + 38970*y^34 + 12439*y^33 + 7963*y^32 + 16150*y^31 + 11382*y^30 + 3038*y^29 + 20157*y^28 + 23531*y^27 + 32866*y^26 + 5428*y^25 + 21132*y^24 + 13443*y^23 + 28909*y^22 + 42716*y^21 + 6567*y^20 + 24744*y^19 + 8727*y^18 + 14895*y^17 + 28172*y^16 + 30903*y^15 + 26608*y^14 + 27314*y^13 + 42224*y^12 + 42551*y^11 + 37726*y^10 + 11203*y^9 + 36816*y^8 + 5537*y^7 + 20301*y^6 + 17591*y^5 + 41279*y^4 + 7999*y^3 + 33753*y^2 + 34551*y + 9659')
e = 65537
# factor(N)
# 或
# P = N.factor()[0][0]
# Q = N.factor()[1][0]

phi = (p ^ 65 - 1) * (p ^ 112 - 1)
d = inverse(e,phi)

result = R("1") 
# 快速幂算法
while True:
    if d % 2 == 1:
        # 如果d为奇数的话，很显然不能直接进行快速幂，那么就把多余的一项先乘入result中，在把c继续进行快速幂算法
        result = (result * c) % n
        d = d - 1
    c = (c * c) % n
    d = d / 2
    if d == 0:
        break
print(result) 

result = str(result)
terms = result.split(' + ')
coefficients = []
for term in terms:
    coefficients.append(int(term.split('*')[0]))

for i in coefficients[::-1]:
    print(chr(i),end = '')

# watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}

reference: https://blog.csdn.net/qq_51999772/article/details/122373872

题三

多项式dlp

([赣政杯-2023]crypto)

题目描述：
task.sage:

# you can get x1,x2,x3 here. data in output.txt.
from Crypto.Cipher import AES
from hashlib import md5
from Crypto.Util.number import *
from Crypto.Util.Padding import pad


n = getPrime(1024) * getPrime(1024)
x1 = getPrime(50)
m1 = b'Summer'
m2 = b'\x1b5Z\xd2$\x8c\xfdV\x9fG&\xc4'
m3 = b"\xf1XNW&'\xf4'}\xf9\xd1?\xc4\xa6h\xa3\xf8\x1d\x14\xc16)\xca\xab\xa4\x00\x18\x83 "
c1 = pow(bytes_to_long(m1),x1,n)
c2 = pow(bytes_to_long(m2),x1,n)
c3 = pow(bytes_to_long(m3),x1,n)
print(c1)
print(c2)
print(c3)
print('-------')

x2 = getPrime(79)
mod = 60901

R.<x> = PolynomialRing(GF(mod))
N = 25084*x^255 + 32363*x^254 + 21665*x^253 + 24571*x^252 + 20587*x^251 + 17472*x^250 + 30654*x^249 + 31322*x^248 + 23385*x^247 + 14049*x^246 + 27853*x^245 + 18183*x^244 + 33130*x^243 + 29218*x^242 + 3412*x^241 + 28875*x^240 + 1551*x^239 + 15231*x^238 + 32794*x^237 + 8541*x^236 + 23025*x^235 + 21145*x^234 + 11858*x^233 + 34388*x^232 + 21092*x^231 + 22355*x^230 + 1768*x^229 + 5868*x^228 + 1502*x^227 + 30644*x^226 + 24646*x^225 + 32356*x^224 + 27350*x^223 + 34810*x^222 + 27676*x^221 + 24351*x^220 + 9218*x^219 + 27073*x^218 + 21176*x^217 + 2139*x^216 + 8244*x^215 + 1887*x^214 + 3854*x^213 + 24362*x^212 + 10981*x^211 + 14237*x^210 + 28663*x^209 + 32272*x^208 + 29911*x^207 + 13575*x^206 + 15955*x^205 + 5367*x^204 + 34844*x^203 + 15036*x^202 + 7662*x^201 + 16816*x^200 + 1051*x^199 + 16540*x^198 + 17738*x^197 + 10212*x^196 + 4180*x^195 + 33126*x^194 + 13014*x^193 + 16584*x^192 + 10139*x^191 + 27520*x^190 + 116*x^189 + 28197*x^188 + 31755*x^187 + 10917*x^186 + 28271*x^185 + 1152*x^184 + 6118*x^183 + 27171*x^182 + 14265*x^181 + 905*x^180 + 13776*x^179 + 854*x^178 + 5397*x^177 + 14898*x^176 + 1388*x^175 + 14058*x^174 + 6871*x^173 + 13508*x^172 + 3102*x^171 + 20438*x^170 + 29122*x^169 + 17072*x^168 + 23021*x^167 + 29879*x^166 + 28424*x^165 + 8616*x^164 + 21771*x^163 + 31878*x^162 + 33793*x^161 + 9238*x^160 + 23751*x^159 + 24157*x^158 + 17665*x^157 + 34015*x^156 + 9925*x^155 + 2981*x^154 + 24715*x^153 + 13223*x^152 + 1492*x^151 + 7548*x^150 + 13335*x^149 + 24773*x^148 + 15147*x^147 + 25234*x^146 + 24394*x^145 + 27742*x^144 + 29033*x^143 + 10247*x^142 + 22010*x^141 + 18634*x^140 + 27877*x^139 + 27754*x^138 + 13972*x^137 + 31376*x^136 + 17211*x^135 + 21233*x^134 + 5378*x^133 + 27022*x^132 + 5107*x^131 + 15833*x^130 + 27650*x^129 + 26776*x^128 + 7420*x^127 + 20235*x^126 + 2767*x^125 + 2708*x^124 + 31540*x^123 + 16736*x^122 + 30955*x^121 + 14959*x^120 + 13171*x^119 + 5450*x^118 + 20204*x^117 + 18833*x^116 + 33989*x^115 + 25970*x^114 + 767*x^113 + 16400*x^112 + 34931*x^111 + 7923*x^110 + 33965*x^109 + 12199*x^108 + 11788*x^107 + 19343*x^106 + 33039*x^105 + 13475*x^104 + 15822*x^103 + 20921*x^102 + 25100*x^101 + 9771*x^100 + 5272*x^99 + 34002*x^98 + 16026*x^97 + 23104*x^96 + 33331*x^95 + 11944*x^94 + 5428*x^93 + 11838*x^92 + 30854*x^91 + 18595*x^90 + 5226*x^89 + 23614*x^88 + 5611*x^87 + 34572*x^86 + 17035*x^85 + 16199*x^84 + 26755*x^83 + 10270*x^82 + 25206*x^81 + 30800*x^80 + 21714*x^79 + 2088*x^78 + 3785*x^77 + 9626*x^76 + 25706*x^75 + 24807*x^74 + 31605*x^73 + 5292*x^72 + 17836*x^71 + 32529*x^70 + 33088*x^69 + 16369*x^68 + 18195*x^67 + 22227*x^66 + 8839*x^65 + 27975*x^64 + 10464*x^63 + 29788*x^62 + 15770*x^61 + 31095*x^60 + 276*x^59 + 25968*x^58 + 14891*x^57 + 23490*x^56 + 34563*x^55 + 29778*x^54 + 26719*x^53 + 28611*x^52 + 1633*x^51 + 28335*x^50 + 18278*x^49 + 33901*x^48 + 13451*x^47 + 30759*x^46 + 19192*x^45 + 31002*x^44 + 11733*x^43 + 29274*x^42 + 11756*x^41 + 6880*x^40 + 11492*x^39 + 7151*x^38 + 28624*x^37 + 29566*x^36 + 33986*x^35 + 5726*x^34 + 5040*x^33 + 14730*x^32 + 7443*x^31 + 12168*x^30 + 24201*x^29 + 20390*x^28 + 15087*x^27 + 18193*x^26 + 19796*x^25 + 32514*x^24 + 25252*x^23 + 15090*x^22 + 2653*x^21 + 29310*x^20 + 4037*x^19 + 6440*x^18 + 16780*x^17 + 1891*x^16 + 20592*x^15 + 11890*x^14 + 25769*x^13 + 29259*x^12 + 23814*x^11 + 17565*x^10 + 16797*x^9 + 34151*x^8 + 20893*x^7 + 2807*x^6 + 209*x^5 + 3217*x^4 + 8801*x^3 + 21964*x^2 + 16286*x + 1207

S.<x> = R.quotient(N)
g = x
c = g ^ x2
print(mod)
print(c)
print('-------')

A =  [
     [1287397632974625907369332145667695136576732725719,  999149001044306271168727399637009399486427921379,   1046504160269652701583906344218556291030141088947,  724446625683754938181565321149725788430461092168,    1071845980147173642753960259602135592110139561915],
     [947603660931904341080240982051313712707367037453,   312289846563741934103580532543082761760226637905,   494739786803547247505263837170488583876166831850,   680540462980071181450018491798299105995449257198,    2602258415762368797405060707505977243346704576],
     [996213673531855992829525358578006610606634622631,   1025711294257038288640877971869685565227647136954,  1432432135773706484846126533752827108541355741973,  1238541870126055576875033883691918425137600727481,   1130938956963588695293783764965618873887596017827],
     [1320933266015680090206505704792362493057963931979,  1151746112645644166669332171392580649376526147475,  117512451110908867093773368598681106589771485221,   78071463743800894350883457304401524272336187149,     350437511649326676405126284689545814008237687775],
     [438339253001275654203062260777687750937184662400,   372483950165136927369598298270629892810999203086,   859008773869616460027135965589262417694174453098,   1174526536643808668299968641952541506024584582818,   13201859260259503932772826643483081858286638179]
    ]

p = 1461501637330902918203684832716283019655932542983
A=Matrix(GF(p),A)
x3=randint(1,p-1)
enc=A ^ x3
print(enc)
print('-------')

# print(x1)
# print(x2)
# print(x3)

output.txt:

6642405920901856169444016797176854597511451869985089651222713756777328966941476058604740455313616649917187991048303850631108347661320663913557624152718957853756249151837319676066099077333534697206386691941331448958684021832562207954154873697814883115658290031936751010644432299888242593402862504138835921966726681417223379481462802829351047480186956868100845641554180786970034400113962411824354147963669819689032778624971549900555093828130900263372445564238059617835820174579230777360658751552380263147079230363339891599173117866703038100650069898243259407309606964270874516077211813084737872899450015333976760281703
12813265737443697551929767989570751888750511705348484641903902149955312616711153251092445655940484450690399380028749856807646105728043629274795851279862876474531555369892719879557046790927230728065906684723947834712460717801290713839457680590114020295500667651057326890424493250921935414989955491994447207088436387696477722392644270158235224792084194369936504271283334716001838217357724081502237230541364101629570586471163819753729676633882730583741430969604274129791655908106575499122099979016198784279229993793071830074860802254279441203206755560219988997867608365962558150456294230932902402240597836935823436345325
1074141404749280436711035717954232277868634448571610901178443079135403105955266644476567782025394567854097847885741302725302674986645525117336324292432565639695685409234514683062042319986450119065154690941584345281490656949110971489042530766614666018893998646120537235040632473971665446852454893601407555006747727810374360063434824501882913369912060331769975224417255887064285623738576301509295176265159320045368758095953721139289667647294584221175836778442865350736512281839062157810162651549604905844209087574264828233087914336817381862828345301138732008264028314915885909590652794738236676550466058502328912137350
-------
60901
55401*x^254 + 24633*x^253 + 53111*x^252 + 14311*x^251 + 11518*x^250 + 23162*x^249 + 19288*x^248 + 30770*x^247 + 37701*x^246 + 50355*x^245 + 48262*x^244 + 42287*x^243 + 58804*x^242 + 40341*x^241 + 42984*x^240 + 9389*x^239 + 49125*x^238 + 60022*x^237 + 48187*x^236 + 46353*x^235 + 20268*x^234 + 8938*x^233 + 54277*x^232 + 14687*x^231 + 28231*x^230 + 35733*x^229 + 5007*x^228 + 18273*x^227 + 60425*x^226 + 31385*x^225 + 39337*x^224 + 50374*x^223 + 30358*x^222 + 6588*x^221 + 11729*x^220 + 42187*x^219 + 23510*x^218 + 32410*x^217 + 5738*x^216 + 28534*x^215 + 25891*x^214 + 9972*x^213 + 56326*x^212 + 13038*x^211 + 47315*x^210 + 39424*x^209 + 3796*x^208 + 9154*x^207 + 59008*x^206 + 21473*x^205 + 49133*x^204 + 29560*x^203 + 44646*x^202 + 27705*x^201 + 55455*x^200 + 23699*x^199 + 22960*x^198 + 50525*x^197 + 13268*x^196 + 20970*x^195 + 40280*x^194 + 25203*x^193 + 39185*x^192 + 48453*x^191 + 890*x^190 + 5123*x^189 + 60749*x^188 + 951*x^187 + 18721*x^186 + 57419*x^185 + 7257*x^184 + 22621*x^183 + 26819*x^182 + 47248*x^181 + 45994*x^180 + 15573*x^179 + 16713*x^178 + 20203*x^177 + 897*x^176 + 7488*x^175 + 32050*x^174 + 3270*x^173 + 53472*x^172 + 40622*x^171 + 32333*x^170 + 4378*x^169 + 32201*x^168 + 44995*x^167 + 52649*x^166 + 29917*x^165 + 22557*x^164 + 13994*x^163 + 49091*x^162 + 45306*x^161 + 8177*x^160 + 6303*x^159 + 17569*x^158 + 3355*x^157 + 30530*x^156 + 59558*x^155 + 18321*x^154 + 35517*x^153 + 11883*x^152 + 13925*x^151 + 14679*x^150 + 50233*x^149 + 11787*x^148 + 39593*x^147 + 58739*x^146 + 57338*x^145 + 41399*x^144 + 42906*x^143 + 14458*x^142 + 41910*x^141 + 28416*x^140 + 8139*x^139 + 44971*x^138 + 38875*x^137 + 2802*x^136 + 59482*x^135 + 50068*x^134 + 18055*x^133 + 12860*x^132 + 26353*x^131 + 31779*x^130 + 27078*x^129 + 39282*x^128 + 44523*x^127 + 55970*x^126 + 47567*x^125 + 25213*x^124 + 48363*x^123 + 7496*x^122 + 51295*x^121 + 34384*x^120 + 28460*x^119 + 23547*x^118 + 1159*x^117 + 21655*x^116 + 57089*x^115 + 37023*x^114 + 23899*x^113 + 22581*x^112 + 27488*x^111 + 23946*x^110 + 49523*x^109 + 44072*x^108 + 47188*x^107 + 21628*x^106 + 34880*x^105 + 57871*x^104 + 49327*x^103 + 10140*x^102 + 36170*x^101 + 33307*x^100 + 60839*x^99 + 48178*x^98 + 39916*x^97 + 14610*x^96 + 42438*x^95 + 57662*x^94 + 54241*x^93 + 35070*x^92 + 31061*x^91 + 43269*x^90 + 38150*x^89 + 53239*x^88 + 45189*x^87 + 41485*x^86 + 47902*x^85 + 54667*x^84 + 649*x^83 + 56191*x^82 + 6057*x^81 + 370*x^80 + 39935*x^79 + 17960*x^78 + 20082*x^77 + 25163*x^76 + 54283*x^75 + 57334*x^74 + 13449*x^73 + 19038*x^72 + 26849*x^71 + 18729*x^70 + 45227*x^69 + 3179*x^68 + 60390*x^67 + 6694*x^66 + 46032*x^65 + 53506*x^64 + 22716*x^63 + 44127*x^62 + 20626*x^61 + 488*x^60 + 49145*x^59 + 24392*x^58 + 29665*x^57 + 30051*x^56 + 24849*x^55 + 3007*x^54 + 2459*x^53 + 13880*x^52 + 24094*x^51 + 7240*x^50 + 38191*x^49 + 33081*x^48 + 32018*x^47 + 20931*x^46 + 19671*x^45 + 35881*x^44 + 10575*x^43 + 1044*x^42 + 31649*x^41 + 8001*x^40 + 43071*x^39 + 698*x^38 + 50473*x^37 + 55442*x^36 + 54956*x^35 + 29000*x^34 + 53562*x^33 + 4782*x^32 + 6186*x^31 + 44930*x^30 + 45144*x^29 + 54107*x^28 + 42204*x^27 + 57096*x^26 + 8851*x^25 + 33377*x^24 + 34744*x^23 + 26925*x^22 + 41418*x^21 + 27187*x^20 + 20530*x^19 + 60503*x^18 + 6434*x^17 + 18420*x^16 + 19968*x^15 + 58669*x^14 + 7105*x^13 + 8018*x^12 + 51214*x^11 + 33099*x^10 + 17268*x^9 + 3428*x^8 + 50013*x^7 + 41048*x^6 + 19008*x^5 + 60810*x^4 + 53565*x^3 + 53558*x^2 + 46914*x + 8721
-------
[ 413094434584570995591398694224537386587890607099 1402178500605886628335320740160364976151966833746  224676119140512070289814098697316498283294186394   95207433392533133044965499790275028893073229005   84512728483260378812263046639161852722157440007]
[ 839641252733812478258826056657933667891721005509   75137116131174621187044431124685200657840877273 1044263592468227991738016566259580451830359820713 1361901709492224001881896595585166393645078000241  221917499090658247675093423011067065018034308218]
[1315301968215025397304836809076224100542432312513  605129393630472476299035900160790679472470273413  646531256186931146929304242983362631690900265566  594693457384017930182031564738973940589363805344  257106427346401942506852090636774640149629554885]
[ 640857434829813923255563118801415401588598205004 1148607850128743270967140556534752603625719960014 1134547787797381481449954822815892367870034266876  918295327097055894660693563263545537961722685932  545082959137454541579388693351505124519462125367]
[ 295894481010831543767846527675639322564996024436  145286734860912325389688024767333261487525476401 1420994667286333898883659969797582246266387486713  201795652532043659128421325330456874668634095998  914687479458311475079089248841757161330206386647]
-------

求x1,x2,x3
x1:
已知$m2=m{1}^2,m3=m{1}^5$,通过gcd求n（ps剔除小分子23）,之后离散对数求出x1
x2：
参考la佬博客-离散对数篇-多项式dlp
分解多项式计算出其阶，然后将阶进行分解
x3:
参考la佬博客-离散对数篇-矩阵dlp
别问，这里我也不熟，只是单纯记录一下花时间看过这题
x1:

from Crypto.Util.number import *
import gmpy2

m1 = bytes_to_long(b'Summer')
c1 = 6642405920901856169444016797176854597511451869985089651222713756777328966941476058604740455313616649917187991048303850631108347661320663913557624152718957853756249151837319676066099077333534697206386691941331448958684021832562207954154873697814883115658290031936751010644432299888242593402862504138835921966726681417223379481462802829351047480186956868100845641554180786970034400113962411824354147963669819689032778624971549900555093828130900263372445564238059617835820174579230777360658751552380263147079230363339891599173117866703038100650069898243259407309606964270874516077211813084737872899450015333976760281703
c2 = 12813265737443697551929767989570751888750511705348484641903902149955312616711153251092445655940484450690399380028749856807646105728043629274795851279862876474531555369892719879557046790927230728065906684723947834712460717801290713839457680590114020295500667651057326890424493250921935414989955491994447207088436387696477722392644270158235224792084194369936504271283334716001838217357724081502237230541364101629570586471163819753729676633882730583741430969604274129791655908106575499122099979016198784279229993793071830074860802254279441203206755560219988997867608365962558150456294230932902402240597836935823436345325
c3 = 1074141404749280436711035717954232277868634448571610901178443079135403105955266644476567782025394567854097847885741302725302674986645525117336324292432565639695685409234514683062042319986450119065154690941584345281490656949110971489042530766614666018893998646120537235040632473971665446852454893601407555006747727810374360063434824501882913369912060331769975224417255887064285623738576301509295176265159320045368758095953721139289667647294584221175836778442865350736512281839062157810162651549604905844209087574264828233087914336817381862828345301138732008264028314915885909590652794738236676550466058502328912137350
n = gmpy2.gcd(c1**2-c2,c1**5-c3)//23
x1 = discrete_log_lambda(c1,m1,(1,2**50))
print(x1)

x2:

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

def brute_dlp(gi, ci, n, lim):
	bi = gi
	for i in range(1, lim+1):
		if bi == ci:
			return i
		bi = (bi * gi) % n
	print("[-] NOT in the range")
	print("[-] Something's Wrong, you gotta check the range", lim)

def pohlig_hellman(g, c, s, n, factors):
	res = []
	modulus = []
	for q in factors:
		e=1
		assert pow(g, s//(q**e), n) != 1
		gi = pow(g, s//(q**e), n)
		ci = pow(c, s//(q**e), n)
		dlogi = brute_dlp(gi, ci, n, q**e)
		print("[+] dlog modulo {0} == {1}".format(q**e, dlogi))
		res.append(dlogi)
		modulus.append(q**e)
	print("\n[*] res = ", res)
	print("[*] modulus = ", modulus)
	dlog = CRT(res, modulus)
	return dlog

p = 60901
P = PolynomialRing(Zmod(p), name='x')
x = P.gen()
n = 25084*x^255 + 32363*x^254 + 21665*x^253 + 24571*x^252 + 20587*x^251 + 17472*x^250 + 30654*x^249 + 31322*x^248 + 23385*x^247 + 14049*x^246 + 27853*x^245 + 18183*x^244 + 33130*x^243 + 29218*x^242 + 3412*x^241 + 28875*x^240 + 1551*x^239 + 15231*x^238 + 32794*x^237 + 8541*x^236 + 23025*x^235 + 21145*x^234 + 11858*x^233 + 34388*x^232 + 21092*x^231 + 22355*x^230 + 1768*x^229 + 5868*x^228 + 1502*x^227 + 30644*x^226 + 24646*x^225 + 32356*x^224 + 27350*x^223 + 34810*x^222 + 27676*x^221 + 24351*x^220 + 9218*x^219 + 27073*x^218 + 21176*x^217 + 2139*x^216 + 8244*x^215 + 1887*x^214 + 3854*x^213 + 24362*x^212 + 10981*x^211 + 14237*x^210 + 28663*x^209 + 32272*x^208 + 29911*x^207 + 13575*x^206 + 15955*x^205 + 5367*x^204 + 34844*x^203 + 15036*x^202 + 7662*x^201 + 16816*x^200 + 1051*x^199 + 16540*x^198 + 17738*x^197 + 10212*x^196 + 4180*x^195 + 33126*x^194 + 13014*x^193 + 16584*x^192 + 10139*x^191 + 27520*x^190 + 116*x^189 + 28197*x^188 + 31755*x^187 + 10917*x^186 + 28271*x^185 + 1152*x^184 + 6118*x^183 + 27171*x^182 + 14265*x^181 + 905*x^180 + 13776*x^179 + 854*x^178 + 5397*x^177 + 14898*x^176 + 1388*x^175 + 14058*x^174 + 6871*x^173 + 13508*x^172 + 3102*x^171 + 20438*x^170 + 29122*x^169 + 17072*x^168 + 23021*x^167 + 29879*x^166 + 28424*x^165 + 8616*x^164 + 21771*x^163 + 31878*x^162 + 33793*x^161 + 9238*x^160 + 23751*x^159 + 24157*x^158 + 17665*x^157 + 34015*x^156 + 9925*x^155 + 2981*x^154 + 24715*x^153 + 13223*x^152 + 1492*x^151 + 7548*x^150 + 13335*x^149 + 24773*x^148 + 15147*x^147 + 25234*x^146 + 24394*x^145 + 27742*x^144 + 29033*x^143 + 10247*x^142 + 22010*x^141 + 18634*x^140 + 27877*x^139 + 27754*x^138 + 13972*x^137 + 31376*x^136 + 17211*x^135 + 21233*x^134 + 5378*x^133 + 27022*x^132 + 5107*x^131 + 15833*x^130 + 27650*x^129 + 26776*x^128 + 7420*x^127 + 20235*x^126 + 2767*x^125 + 2708*x^124 + 31540*x^123 + 16736*x^122 + 30955*x^121 + 14959*x^120 + 13171*x^119 + 5450*x^118 + 20204*x^117 + 18833*x^116 + 33989*x^115 + 25970*x^114 + 767*x^113 + 16400*x^112 + 34931*x^111 + 7923*x^110 + 33965*x^109 + 12199*x^108 + 11788*x^107 + 19343*x^106 + 33039*x^105 + 13475*x^104 + 15822*x^103 + 20921*x^102 + 25100*x^101 + 9771*x^100 + 5272*x^99 + 34002*x^98 + 16026*x^97 + 23104*x^96 + 33331*x^95 + 11944*x^94 + 5428*x^93 + 11838*x^92 + 30854*x^91 + 18595*x^90 + 5226*x^89 + 23614*x^88 + 5611*x^87 + 34572*x^86 + 17035*x^85 + 16199*x^84 + 26755*x^83 + 10270*x^82 + 25206*x^81 + 30800*x^80 + 21714*x^79 + 2088*x^78 + 3785*x^77 + 9626*x^76 + 25706*x^75 + 24807*x^74 + 31605*x^73 + 5292*x^72 + 17836*x^71 + 32529*x^70 + 33088*x^69 + 16369*x^68 + 18195*x^67 + 22227*x^66 + 8839*x^65 + 27975*x^64 + 10464*x^63 + 29788*x^62 + 15770*x^61 + 31095*x^60 + 276*x^59 + 25968*x^58 + 14891*x^57 + 23490*x^56 + 34563*x^55 + 29778*x^54 + 26719*x^53 + 28611*x^52 + 1633*x^51 + 28335*x^50 + 18278*x^49 + 33901*x^48 + 13451*x^47 + 30759*x^46 + 19192*x^45 + 31002*x^44 + 11733*x^43 + 29274*x^42 + 11756*x^41 + 6880*x^40 + 11492*x^39 + 7151*x^38 + 28624*x^37 + 29566*x^36 + 33986*x^35 + 5726*x^34 + 5040*x^33 + 14730*x^32 + 7443*x^31 + 12168*x^30 + 24201*x^29 + 20390*x^28 + 15087*x^27 + 18193*x^26 + 19796*x^25 + 32514*x^24 + 25252*x^23 + 15090*x^22 + 2653*x^21 + 29310*x^20 + 4037*x^19 + 6440*x^18 + 16780*x^17 + 1891*x^16 + 20592*x^15 + 11890*x^14 + 25769*x^13 + 29259*x^12 + 23814*x^11 + 17565*x^10 + 16797*x^9 + 34151*x^8 + 20893*x^7 + 2807*x^6 + 209*x^5 + 3217*x^4 + 8801*x^3 + 21964*x^2 + 16286*x + 1207
c = 55401*x^254 + 24633*x^253 + 53111*x^252 + 14311*x^251 + 11518*x^250 + 23162*x^249 + 19288*x^248 + 30770*x^247 + 37701*x^246 + 50355*x^245 + 48262*x^244 + 42287*x^243 + 58804*x^242 + 40341*x^241 + 42984*x^240 + 9389*x^239 + 49125*x^238 + 60022*x^237 + 48187*x^236 + 46353*x^235 + 20268*x^234 + 8938*x^233 + 54277*x^232 + 14687*x^231 + 28231*x^230 + 35733*x^229 + 5007*x^228 + 18273*x^227 + 60425*x^226 + 31385*x^225 + 39337*x^224 + 50374*x^223 + 30358*x^222 + 6588*x^221 + 11729*x^220 + 42187*x^219 + 23510*x^218 + 32410*x^217 + 5738*x^216 + 28534*x^215 + 25891*x^214 + 9972*x^213 + 56326*x^212 + 13038*x^211 + 47315*x^210 + 39424*x^209 + 3796*x^208 + 9154*x^207 + 59008*x^206 + 21473*x^205 + 49133*x^204 + 29560*x^203 + 44646*x^202 + 27705*x^201 + 55455*x^200 + 23699*x^199 + 22960*x^198 + 50525*x^197 + 13268*x^196 + 20970*x^195 + 40280*x^194 + 25203*x^193 + 39185*x^192 + 48453*x^191 + 890*x^190 + 5123*x^189 + 60749*x^188 + 951*x^187 + 18721*x^186 + 57419*x^185 + 7257*x^184 + 22621*x^183 + 26819*x^182 + 47248*x^181 + 45994*x^180 + 15573*x^179 + 16713*x^178 + 20203*x^177 + 897*x^176 + 7488*x^175 + 32050*x^174 + 3270*x^173 + 53472*x^172 + 40622*x^171 + 32333*x^170 + 4378*x^169 + 32201*x^168 + 44995*x^167 + 52649*x^166 + 29917*x^165 + 22557*x^164 + 13994*x^163 + 49091*x^162 + 45306*x^161 + 8177*x^160 + 6303*x^159 + 17569*x^158 + 3355*x^157 + 30530*x^156 + 59558*x^155 + 18321*x^154 + 35517*x^153 + 11883*x^152 + 13925*x^151 + 14679*x^150 + 50233*x^149 + 11787*x^148 + 39593*x^147 + 58739*x^146 + 57338*x^145 + 41399*x^144 + 42906*x^143 + 14458*x^142 + 41910*x^141 + 28416*x^140 + 8139*x^139 + 44971*x^138 + 38875*x^137 + 2802*x^136 + 59482*x^135 + 50068*x^134 + 18055*x^133 + 12860*x^132 + 26353*x^131 + 31779*x^130 + 27078*x^129 + 39282*x^128 + 44523*x^127 + 55970*x^126 + 47567*x^125 + 25213*x^124 + 48363*x^123 + 7496*x^122 + 51295*x^121 + 34384*x^120 + 28460*x^119 + 23547*x^118 + 1159*x^117 + 21655*x^116 + 57089*x^115 + 37023*x^114 + 23899*x^113 + 22581*x^112 + 27488*x^111 + 23946*x^110 + 49523*x^109 + 44072*x^108 + 47188*x^107 + 21628*x^106 + 34880*x^105 + 57871*x^104 + 49327*x^103 + 10140*x^102 + 36170*x^101 + 33307*x^100 + 60839*x^99 + 48178*x^98 + 39916*x^97 + 14610*x^96 + 42438*x^95 + 57662*x^94 + 54241*x^93 + 35070*x^92 + 31061*x^91 + 43269*x^90 + 38150*x^89 + 53239*x^88 + 45189*x^87 + 41485*x^86 + 47902*x^85 + 54667*x^84 + 649*x^83 + 56191*x^82 + 6057*x^81 + 370*x^80 + 39935*x^79 + 17960*x^78 + 20082*x^77 + 25163*x^76 + 54283*x^75 + 57334*x^74 + 13449*x^73 + 19038*x^72 + 26849*x^71 + 18729*x^70 + 45227*x^69 + 3179*x^68 + 60390*x^67 + 6694*x^66 + 46032*x^65 + 53506*x^64 + 22716*x^63 + 44127*x^62 + 20626*x^61 + 488*x^60 + 49145*x^59 + 24392*x^58 + 29665*x^57 + 30051*x^56 + 24849*x^55 + 3007*x^54 + 2459*x^53 + 13880*x^52 + 24094*x^51 + 7240*x^50 + 38191*x^49 + 33081*x^48 + 32018*x^47 + 20931*x^46 + 19671*x^45 + 35881*x^44 + 10575*x^43 + 1044*x^42 + 31649*x^41 + 8001*x^40 + 43071*x^39 + 698*x^38 + 50473*x^37 + 55442*x^36 + 54956*x^35 + 29000*x^34 + 53562*x^33 + 4782*x^32 + 6186*x^31 + 44930*x^30 + 45144*x^29 + 54107*x^28 + 42204*x^27 + 57096*x^26 + 8851*x^25 + 33377*x^24 + 34744*x^23 + 26925*x^22 + 41418*x^21 + 27187*x^20 + 20530*x^19 + 60503*x^18 + 6434*x^17 + 18420*x^16 + 19968*x^15 + 58669*x^14 + 7105*x^13 + 8018*x^12 + 51214*x^11 + 33099*x^10 + 17268*x^9 + 3428*x^8 + 50013*x^7 + 41048*x^6 + 19008*x^5 + 60810*x^4 + 53565*x^3 + 53558*x^2 + 46914*x + 8721
g = x
nfactors = n.factor()
s = 1
for i in nfactors:
	s *= p**(i[0].degree()) - 1   

factors = [1249 , 2281 , 3121 , 7489 , 7937 , 8009,57809]
x2 = pohlig_hellman(g,c,s,n,factors) # c = g ^ x2 ,s为阶，n为模数
print(x2)

x3:

#sage
n = 5
p = 1461501637330902918203684832716283019655932542983
A =  [
     [1287397632974625907369332145667695136576732725719,  999149001044306271168727399637009399486427921379,   1046504160269652701583906344218556291030141088947,  724446625683754938181565321149725788430461092168,    1071845980147173642753960259602135592110139561915],
     [947603660931904341080240982051313712707367037453,   312289846563741934103580532543082761760226637905,   494739786803547247505263837170488583876166831850,   680540462980071181450018491798299105995449257198,    2602258415762368797405060707505977243346704576],
     [996213673531855992829525358578006610606634622631,   1025711294257038288640877971869685565227647136954,  1432432135773706484846126533752827108541355741973,  1238541870126055576875033883691918425137600727481,   1130938956963588695293783764965618873887596017827],
     [1320933266015680090206505704792362493057963931979,  1151746112645644166669332171392580649376526147475,  117512451110908867093773368598681106589771485221,   78071463743800894350883457304401524272336187149,     350437511649326676405126284689545814008237687775],
     [438339253001275654203062260777687750937184662400,   372483950165136927369598298270629892810999203086,   859008773869616460027135965589262417694174453098,   1174526536643808668299968641952541506024584582818,   13201859260259503932772826643483081858286638179]
    ]
B = [[ 413094434584570995591398694224537386587890607099,1402178500605886628335320740160364976151966833746,224676119140512070289814098697316498283294186394,95207433392533133044965499790275028893073229005,84512728483260378812263046639161852722157440007],
[ 839641252733812478258826056657933667891721005509,75137116131174621187044431124685200657840877273,1044263592468227991738016566259580451830359820713,1361901709492224001881896595585166393645078000241,221917499090658247675093423011067065018034308218],
[1315301968215025397304836809076224100542432312513,605129393630472476299035900160790679472470273413,646531256186931146929304242983362631690900265566,594693457384017930182031564738973940589363805344,257106427346401942506852090636774640149629554885],
[ 640857434829813923255563118801415401588598205004,1148607850128743270967140556534752603625719960014,1134547787797381481449954822815892367870034266876,918295327097055894660693563263545537961722685932,545082959137454541579388693351505124519462125367],
[ 295894481010831543767846527675639322564996024436,145286734860912325389688024767333261487525476401,1420994667286333898883659969797582246266387486713,201795652532043659128421325330456874668634095998,914687479458311475079089248841757161330206386647]]

G = matrix(GF(p), n, n, A)
H = matrix(GF(p), n, n, B)

G_Jor, P = G.jordan_form(transformation=True)
H_Jor = ~P * H * P
x3 = G_Jor[3][3]*H_Jor[3][4]//H_Jor[4][4]
print(x3)

来源：https://blog.csdn.net/luochen2436/article/details/132332081?spm=1001.2014.3001.5502
不是很会，值得记录