多项式RSA

Crypto , Comments

多项式RSA

整数RSA加解密原理

多项式RSA推倒

在上面RSA原理的基础上将多项式的代入整数进行分析。

引用：以上原理、推导

phi的问题

不可约多项式的欧拉函数求法：回到欧拉函数定义本身，欧拉函数是小于或等于n的正整数中与n互素的数的数目。

再看不可约多项式p(x)，除了0，长度为n每一个多项式都与p(x)互素，因此

明文与多项式系数

加密： 将明文每个字符转ascii，每一位对应一项多项式的系数。
解密： 将每一位多项式系数转换为ascii，连起来就是原文。

1
2
m = pow(c, d, N) 
m = "".join([chr(c) for c in m.list()])

例题：[watevrCTF 2019]Swedish RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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)
        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
'''

exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
R.<y> = PolynomialRing(GF(43753))
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")
print(factor(N))

e = 65537
phi = (43753^65-1)*(43753^112-1)
d = inverse_mod(e, phi)

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")

m = pow(C, d, N)
m = "".join([chr(c) for c in m.list()])

print(m)

#watevr{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}
#flag{RSA_from_ikea_is_fun_but_insecure#k20944uehdjfnjd335uro}

另一篇很好的讲解：多项式RSA
exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
p = 43753

R.<x> = PolynomialRing(GF(p))

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

P, Q = N.factor()
P, Q = P[0], Q[0]
phi = (p ** P.degree() - 1) * (p ** Q.degree() - 1)
e = 0x10001
d = inverse_mod(e, phi)

m = pow(c, d, N)
m = "".join([chr(c) for c in m.list()])
print(m)

实例

buuctf dasctf nov crypto easyrsa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
from gmpy2 import *
from Crypto.Util.number import *
import random
#from secrets import flag
p1=getPrime(128)
q=getPrime(128)
n=p1**2+q**2
print('n=',n)
q=q+63066105847160076051036559850646146794

def gen_prime():
    while True:
        prime = sum([random.getrandbits(16) * q**i for i in range(6)])
        if isPrime(prime):
            return prime


p, q, r = [gen_prime() for i in range(3)]
n2=p*q*r
print('n2=',n2)

while True:
    p1=next_prime(p1)
    p=next_prime(p)
    q=next_prime(q)
    r=next_prime(r)
    if (p-1)%7==0 and (q-1)%7 ==0 and (r-1)%7==0 and (p1-1)%7==0:
        break

n3=p1**3*p*q*r
e=7

m=bytes_to_long(flag)
c=pow(m,e,n3)
print('c=',c)

'''
n=86073852484226203700520112718689325205597071202320413471730820840719099334770
n2= 77582485123791158683121280616703899430016469065264033598472741751344256774648355531493586310864150337351815051848231793841751148287075688226384710343269278032576253497728407800522536152937473072438970839941923618053297480433385258911357458745700958378269978384670108026994918504237309072908971746160378531040480539649223970964653553804442759847964633088481940435582792404175653758785321463055628690804551479982557193366035172983893595403859872458966844805671311011033726279121149599533093604586152158331657286488305064843651636225644328162652701896037366058322959361248649656784810609391313
c= 260434870216758498838321584935711394249835963213639852217120194663627852693180232036075839403208332707552953757185774603238436545434522971149891312380970896040823539050341723863717581297624370198483155582245220695123793458717418658539983101802256991837534210806768587736557644192367876024337837658337683388449336720569707094997412847022794461117019613124291022681935875774139147643806772608929174881451749463825639214096129554621195116737322890163556732291246108250543079041977037626755130422879778449546701988814607595746282148723362288451970833214072743929855505520539885650891349827459470540263153862109871050950881032032388185414677989393461533362690744724752363346530211163516319373099647590952338730
'''

exp.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#!/usr/bin/env sage
# coding: utf-8

# In[1]:


n = 86073852484226203700520112718689325205597071202320413471730820840719099334770
p, q = two_squares(n)


# In[2]:


print(p)
print(q)


# In[21]:


base = q + 63066105847160076051036559850646146794
n2 = 77582485123791158683121280616703899430016469065264033598472741751344256774648355531493586310864150337351815051848231793841751148287075688226384710343269278032576253497728407800522536152937473072438970839941923618053297480433385258911357458745700958378269978384670108026994918504237309072908971746160378531040480539649223970964653553804442759847964633088481940435582792404175653758785321463055628690804551479982557193366035172983893595403859872458966844805671311011033726279121149599533093604586152158331657286488305064843651636225644328162652701896037366058322959361248649656784810609391313

poly = sum(e * x^i for i,e in enumerate(Integer(n2).digits(base)))
res = poly.factor_list()
print(res)


# In[22]:


primes = []
for r in res:
    f = r[0]
    primes.append(f(base))
primes

再求exp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from gmpy2 import *
from Crypto.Util.number import *
import random
n = 86073852484226203700520112718689325205597071202320413471730820840719099334770
p, q, r = [65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570356277,
 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406261919,
 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326195251]
c = 260434870216758498838321584935711394249835963213639852217120194663627852693180232036075839403208332707552953757185774603238436545434522971149891312380970896040823539050341723863717581297624370198483155582245220695123793458717418658539983101802256991837534210806768587736557644192367876024337837658337683388449336720569707094997412847022794461117019613124291022681935875774139147643806772608929174881451749463825639214096129554621195116737322890163556732291246108250543079041977037626755130422879778449546701988814607595746282148723362288451970833214072743929855505520539885650891349827459470540263153862109871050950881032032388185414677989393461533362690744724752363346530211163516319373099647590952338730
n2 = 77582485123791158683121280616703899430016469065264033598472741751344256774648355531493586310864150337351815051848231793841751148287075688226384710343269278032576253497728407800522536152937473072438970839941923618053297480433385258911357458745700958378269978384670108026994918504237309072908971746160378531040480539649223970964653553804442759847964633088481940435582792404175653758785321463055628690804551479982557193366035172983893595403859872458966844805671311011033726279121149599533093604586152158331657286488305064843651636225644328162652701896037366058322959361248649656784810609391313
p1 = 200170033707580057053975766783012322797
assert p * q * r == n2

while True:
    p1=next_prime(p1)
    p=next_prime(p)
    q=next_prime(q)
    r=next_prime(r)
    if (p-1)%7==0 and (q-1)%7 ==0 and (r-1)%7==0 and (p1-1)%7==0:
        break

print(f'p1 = %d' %p1)
print(f'p = %d' %p)
print(f'q = %d' %q)
print(f'r = %d' %r)
'''
p1 = 200170033707580057053975766783012328327
p = 65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570389431
q = 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406292679
r = 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326229291
'''

最后sage：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
p1 = 200170033707580057053975766783012328327
p = 65852498339760915228594889597136378107876107334695562152983809050259001488139010835535729480582643283480229654777004862320849604335829446520865511011593811440123502620735962409526109695434570389431
q = 42974281584522050062504679441184925920720278381761957641733614118720547476055402383959476142344396618643274705251619494499668048977089541037606316780609473959806621223833644762635231018066406292679
r = 27414656307685249691067705927388582241684529669740981719565564735302197575673076783872355553268011939023273356472727941960439764826793614011976095106476097211511966378338911454193294048309326229291
n = p1 ** 3 * p * q * r
from Crypto.Util.number import *
c = 260434870216758498838321584935711394249835963213639852217120194663627852693180232036075839403208332707552953757185774603238436545434522971149891312380970896040823539050341723863717581297624370198483155582245220695123793458717418658539983101802256991837534210806768587736557644192367876024337837658337683388449336720569707094997412847022794461117019613124291022681935875774139147643806772608929174881451749463825639214096129554621195116737322890163556732291246108250543079041977037626755130422879778449546701988814607595746282148723362288451970833214072743929855505520539885650891349827459470540263153862109871050950881032032388185414677989393461533362690744724752363346530211163516319373099647590952338730
PR.<x> = Zmod(p)[]
f = x ^ 7 - c
res = f.roots()
print(res)
for i in res:
    if b'DASCTF' in long_to_bytes(int(i[0])):
        print(long_to_bytes(int(i[0])))
# b'DASCTF{I_d0nt_kn0w_wh@t_i_w@nt_t0_d0_ju3t_d0_it_attack_we@k_prim4!!!}'

fevergunCtfer & Reverse & Crypto

Reverse , Crypto